抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

MoeCtf Crypto

发布于：2024年11月6日

MoeCTF Crypto Wp

Week 1（个人wp）

1、现代密码学入门指北

image-20240815203723915

简单的RSA题，通过把p和q的欧拉函数相乘得到n的欧拉函数，再通过n的欧拉函数对公钥e求逆元得到私钥d，有了私钥便可通过RSA计算方法来求模得到明文，以下为解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import long_to_bytes
from sympy import totient

n = 40600296529065757616876034307502386207424439675894291036278463517602256790833
p = 197380555956482914197022424175976066223
q = 205695522197318297682903544013139543071
c = 36450632910287169149899281952743051320560762944710752155402435752196566406306
"""print(totient(p))
print(totient(q))
print(totient(p)*totient(q))"""
n1 = 40600296529065757616876034307502386207021363597740489824398537549413141181540
print(n1)
d = pow(65537, -1, n1)
# print(d)
# print(pow(c,d,n))
flag = pow(c, d, n)
flag = long_to_bytes(flag)
print(flag.decode())

得到flag：moectf{the_way_to_crypto}

2、Signin

题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import*
from secret import flag


m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
pq = (p-1)*(q-2)
qp = (q-1)*(p-2)
p_q = p + q


print(f"{c = }")
print(f"{pq = }")
print(f"{qp = }")
print(f"{n = }")
print(f"{p_q = }")
'''
c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496
'''

对于已知的p+q和p*q，可以利用韦达定理构造一元二次方程，然后p，q即分别为一元二次方程的俩个解，即可通过求根公式计算p和q的值。计算得出pq后，则可以运用与第一题相同的脚本进行计算来得出最后的明文

以下为解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import math
from Crypto.Util.number import long_to_bytes
from sympy import totient

c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496
"""delta = p_q * p_q - 4 * n
# print(delta)
# print(math.isqrt(delta) * math.isqrt(delta) == delta)
delta_2 = math.isqrt(delta)
p = (p_q + delta_2) // 2
q = (p_q - delta_2) // 2
print(p,q)"""
p=101195416461091716428326199733504078281010548412226222689665080411126731520752210150756388683557219973649948209094722629248795549538890771346214761833764975454769057589710497693291150424006859232283601953197097456280805871953601208233200402046794268614613979577032173301390416040533984248749301081715040789947
q=178338290116410075141414468862040433639046406531958347823522397596424464310941218439142159656193846577575476581439833972909039919079954450077429211036906580907431676882688830353669165640857711931567509254251656241699372519476443505864264464477044478438521412625815994217480304109274071433871779911283706475549

p1 = totient(p)
q1 = totient(q)
# n1 = p1*q1
n1 = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687255426204315287869495874138670280567022874762911382115560275904390866009817253284783718458110150911167755618230130060239145682239588567994124466321400429710873869517543382716217001003156983565553369868228038096556318508300800891271344655503389828192751000492654983689665130352528504936760171744582637453240408
print(n1)
d = pow(65537, -1, n1)
flag = pow(c, d, n)
flag = long_to_bytes(flag)
print(flag.decode())

得到flag：moectf{Just_4_signin_ch4ll3ng3_for_y0u}

3、ez_hash

源代码：

1
2
3
4
5
6
7
8
from hashlib import sha256
from secret import flag, secrets

assert flag == b'moectf{' + secrets + b'}'
assert secrets[:4] == b'2100' and len(secrets) == 10
hash_value = sha256(secrets).hexdigest()
print(f"{hash_value = }")
# hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'

我们初步读题，可以看见secret是有部分提示条件的，即公有10位，并且前四位是确定的，与此同时也给出了flag的格式，根据题目，对secret的加密是SHA-256哈希算法，对此题没有什么思路，于是尝试着数字遍历爆破，最终刚好能得到secret，阴差阳错的得到了答案

以下为解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from hashlib import sha256

from Crypto.Util.number import long_to_bytes

hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'
a = b'2100'
for i in range(2100000000,2200000000):
    i = str(i)
    # print(i)
    hash_value1 = sha256(i.encode()).hexdigest()
    # print(hash_value1)
    if hash_value1 == hash_value:
        # print(i)
        break

flag = 2100360168
hash_value = sha256(b'2100360168').hexdigest()
print(hash_value)
secrets = b'2100360168'
flag2 = b'moectf{' + secrets + b'}'
print(flag2)

得到flag：moectf{2100360168}

4、Big and small

以下为源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
from secret import flag
from Crypto.Util.number import*
m = long_to_bytes(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
c = pow(m,e,n)
'''
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
'''

通过看题目， 可以得到e的值为3，属于典型的公钥e极小的RSA算法题目，仔细思考RSA的本质，加密过程是明文的e次方对n取模，这道题就是3次方，我们还可以发现，密文的3次方还是小于n的，所以呢，明文就等于密文的三次方，即直接对明文求三次方根就可以得到答案了，以下为题解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import long_to_bytes
from gmpy2 import gmpy2

c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787

print(c**3 < n)

m, exact = gmpy2.iroot(c, e)
flag = m
flag = long_to_bytes(flag)
print(flag.decode())

得到flag：flag{xt>is>s>b}

5、baby_equation

源代码如下：

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

l = len(flag)
m1, m2 = flag[:l//2], flag[l//2:]
a = bytes_to_long(m1)
b = bytes_to_long(m2)
k = 0x2227e398fc6ffcf5159863a345df85ba50d6845f8c06747769fee78f598e7cb1bcf875fb9e5a69ddd39da950f21cb49581c3487c29b7c61da0f584c32ea21ce1edda7f09a6e4c3ae3b4c8c12002bb2dfd0951037d3773a216e209900e51c7d78a0066aa9a387b068acbd4fb3168e915f306ba40
assert ((a**2 + 1)*(b**2 + 1) - 2*(a - b)*(a*b - 1)) == 4*(k + a*b)

本题第一步是在最后一个方程上，我们对他化简后得到，4k=(a+1)(a+1)(b-1)(b-1)

对4k开根号，能得到

image-20240815230518868

下面是因数，这时候想到随机组合爆破，会利用到py的一个函数from itertools import combinations

1
2
3
4
5
6
7
8
9
10
def find_all_valid_combinations(k2, k3, factors):
    valid_combinations = []
    for r in range(1, len(factors) + 1):
        for combo in combinations(factors, r):
            current_k3 = k3 * math.prod(combo)
            if len(str(k2 // current_k3)) == len(str(current_k3)):
                valid_combinations.append((combo, current_k3, k2 // current_k3))

    return valid_combinations

这样就从列表随机取样了，然后来判别前几位，即moectf

1
2
3
4
5
6
7
8
9
10
def lamb(a1, b1):
    a = a1 - 1
    b = b1 + 1
    a = long_to_bytes(a)
    b = long_to_bytes(b)
    try:
        flag = (a + b).decode('latin-1')
        return flag
    except Exception as e:
        return False

在此之前先码一个算出flag的公式。

最后码出判断条件，和输出结果

1
2
3
4
5
6
7
8
for combo, final_k3, result in valid_combinations:
    if lamb(final_k3, result)[:6] == 'moectf' or lamb(result, final_k3)[:6] == 'moectf':
        print(f"组合: {combo}")
        print(f"最终的 k3: {final_k3}")
        print(f"k2 // k3 的结果: {result}")
        print(f"k2 // k3 的位数: {len(str(result))}")
        print(lamb(final_k3, result))
        print(lamb(result, final_k3))

得到flag：moectf{7he_Fund4m3nt4l_th30r3m_0f_4rithm3tic_i5_p0w4rful!}

更新于：2025年5月6日

Crypto

评论