KMA chall 2022

Note : A JOURNEY TO GAIN KNOWLEDGE

source:

from secret import FLAG
from Crypto.Util.number import *

p = getStrongPrime(1024, e=0x10001)
q = getStrongPrime(1024, e=0x10001)
N = p*q
e = 2 * 0x10001

FLAG = bytes_to_long(FLAG)
c = pow(FLAG, e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"ciphertext = {c}")
print(p % 2**512)
print(q >> 512)

# N = 18910545158433895311017976433974842225873138180083042550870420538415203269752883500224333487494376229967747084260188610967920664152599733009191872477449844841785688806010738822120581049479510815765848849941789387407715277300634889483552609571876355341076486622993071502816768861570178416391586901834893920841200069842220170134169935766916187768074486733172999438256124632181174047240011194528279026184940278477441177578281318407406143120541280566271858175707003062491025629054504904010092172978103522562525859171319671854981467535719276900851538594481527446065749540188016100811026229055527121411814531421045088483837
# e = 131074
# ciphertext = 7362481830404392047664837838556926549311841593051901696187851099151061211138554275061641581558469769502595893079842091538079729512325409246800752557333922269153226569840831777141998914719603673363182666758803871593922342676737558049804117753673245537656307713264114579918497926666819438681382940114958138711793370545338527188732586324989046199876903156868370546023758613536267939573281825775671153904381332471792167996397299563209124350865381432065656953336036553680045431703415002858541886127944445284102973377051887011768441895612460168143216404745709101619663605908624568223694365225147027706681095456443832144436
# 521468929680474884091011215884454544987549263491985884283567835275855947321769295885892649835741192991524977575899827264430526969136286493288488887723735
# 11019812861216301828226396115240639104472459628705478207269886119821568688155991169957938945514247981464639255134756191897811386935866573873834830312309470

Ta thấy đây là 1 bài RSA với p và q là 1024 bit. Đề cho ta biết 512 bit đầu của p và 512 bit cuối của q Mình sẽ dưạ vào 512 bit cuối của q để tìm lại 512 bit cuối của p. Vì k bit thấp nhất của p và q sẽ ảnh hưởng đến k bit thấp nhất của n nên mình sẽ brute force các bit của p để thỏa điều kiện trên Có p ta dễ dàng tìm lại q và decode như RSA thông thường

document

solve:

from Crypto.Util.number import *
import gmpy2
from sympy.ntheory.modular import crt

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
    assert legendre(n, p) == 1, "not a square (mod p)"
    q=p-1
    s=0
    while(q%2==0):
        q=q//2
        s+=1
    if s==1:
        return pow(n,(p+1)//4,p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m=s
    t2=0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r

n = 18910545158433895311017976433974842225873138180083042550870420538415203269752883500224333487494376229967747084260188610967920664152599733009191872477449844841785688806010738822120581049479510815765848849941789387407715277300634889483552609571876355341076486622993071502816768861570178416391586901834893920841200069842220170134169935766916187768074486733172999438256124632181174047240011194528279026184940278477441177578281318407406143120541280566271858175707003062491025629054504904010092172978103522562525859171319671854981467535719276900851538594481527446065749540188016100811026229055527121411814531421045088483837
e = 131074
c = 7362481830404392047664837838556926549311841593051901696187851099151061211138554275061641581558469769502595893079842091538079729512325409246800752557333922269153226569840831777141998914719603673363182666758803871593922342676737558049804117753673245537656307713264114579918497926666819438681382940114958138711793370545338527188732586324989046199876903156868370546023758613536267939573281825775671153904381332471792167996397299563209124350865381432065656953336036553680045431703415002858541886127944445284102973377051887011768441895612460168143216404745709101619663605908624568223694365225147027706681095456443832144436
first_p = 11019812861216301828226396115240639104472459628705478207269886119821568688155991169957938945514247981464639255134756191897811386935866573873834830312309470
last_q = 521468929680474884091011215884454544987549263491985884283567835275855947321769295885892649835741192991524977575899827264430526969136286493288488887723735
first_p = bin(first_p)[2:]
tmp = bin(last_q)[2:]
last_p = 'x'* (1024-len(first_p))
last_p = list(last_p)

for i in range(1,len(last_p)+1):
    q_ = tmp[-i:]
    for j in range(2):
        last_p[-i] = str(j)
        p_ = ''.join(last_p[-i:])
        if (int(p_,2)*int(q_,2)) % pow(2,i) == n%pow(2,i) :
            last_p[-i] = str(j)
            #print('here: ',last_p)
            break
p = int(first_p+''.join(last_p),2)
q = n//p
phi = (p-1)*(q-1)
#print(gmpy2.gcd(e,phi))
d = inverse(e,phi)
m = pow(c,d,n)
# CRT
p1=tonelli(m,p)
p2=p-p1
q1=tonelli(m,q)
q2=q-q1
list_num = [p1,p2]
list_num2 = [q1,q2]
for i in list_num:
    for j in list_num2:
        m = [p,q]
        v = [i,j]
        flag = crt(m, v)
        flag = (long_to_bytes(int(flag[0])))
        if b'KMA' in flag:
            print(flag)
# b'...............................KMA{RSA-f0r-3v3ry0n3}.........................................................................................................................................................................'

Thanks for reading. Have a good day ❤️ !