from Crypto.Util.number import * from secret import flag
nbits = 512 p = getPrime(nbits) q = getPrime(nbits) n = p * q phi = (p-1) * (q-1) whileTrue: kk = getPrime(128) rr = kk + 2 e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1 if gcd(e, phi) == 1: break m = bytes_to_long(flag) c = pow(m, e, n)
e = e >> 200 << 200 print(f'n = {n}') print(f'e = {e}') print(f'c = {c}')
""" n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967 e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104 c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823 """
defpartial_p(p0, kbits, n): PR.<x> = PolynomialRing(Zmod(n)) nbits = n.nbits() f = x + p0 f = f.monic()
roots = f.small_roots(X=2^(kbits), beta=0.4)
if roots: x0 = int(roots[0]) p = gcd(x0 + p0, n) returnint(p)
deffind_p(eh, kbits, n): P.<x> = PolynomialRing(RealField(1000)) f = (65538+rr*(n+1))*x + (kk+ rr) * x**2 + rr * n - eh*x res = f.monic().roots() if res: for i in res: ph = int(i[0]) # print(ph) p = partial_p(ph, kbits, n) if p and isPrime(p): return p
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967 e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104 c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823 rr = e // n kk = rr - 2 p = find_p(e, 200, n) if p: q = n // p e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1 d = inverse(e, (p-1)*(q-1)) print(long_to_bytes(pow(c, d, n))) # flag{b5f771c6-18df-49a9-9d6d-ee7804f5416c}
ezrsa(复现)
题目:
点击展开代码
from Crypto.Util.number import * from Crypto.PublicKey import RSA import random from secret import flag
m = bytes_to_long(flag) key = RSA.generate(1024) passphrase = str(random.randint(0,999999)).zfill(6).encode() output = key.export_key(passphrase=passphrase).split(b'\n') for i inrange(7, 15): output[i] = b'*' * 64 withopen("priv.pem", 'wb') as f: for line in output: f.write(line + b'\n') """ 私钥文件 -----BEGIN RSA PRIVATE KEY----- Proc-Type: 4,ENCRYPTED DEK-Info: DES-EDE3-CBC,435BF84C562FE793 9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh WiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdD ig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH **************************************************************** **************************************************************** **************************************************************** **************************************************************** **************************************************************** **************************************************************** **************************************************************** **************************************************************** hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSI jLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg== -----END RSA PRIVATE KEY----- """ withopen("enc.txt", 'w') as f: f.write(str(key._encrypt(m))) """ 密文 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989 """
from binascii import a2b_base64, unhexlify from Crypto.Hash import MD5 from Crypto.Cipher import DES3 from Crypto.Protocol.KDF import PBKDF1 import tqdm
defsolve(data, salt): # 爆破一下passphrase for i in tqdm.trange(1000000): passphrase = str(i).zfill(6).encode() # We only support 3DES for encryption key = PBKDF1(passphrase, salt, 16, 1, MD5) key += PBKDF1(key + passphrase, salt, 8, 1, MD5) objenc = DES3.new(key, DES3.MODE_CBC, salt) # Encrypt with PKCS#7 padding data1 = objenc.decrypt(data).hex() if data1[:6] == "308202"and"010001"in data1: print("", data1) iv = a2b_base64(b"hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSIjLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==")[:8] objenc = DES3.new(key, DES3.MODE_CBC, iv) c1 = a2b_base64(b"hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSIjLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==") data1 = objenc.decrypt(c1)[8:].hex() print(data1) return passphrase
n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81 e = 0x010001
from tqdm import * from Crypto.Util.number import * from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP
n = 0xa18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81 e = 65537 dq_leak= 0x8f2363b340e5 inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989
defcoppersmith(k): R.<x> = PolynomialRing(Zmod(n)) tmp = e * (x * 2^48 + dq_leak) + k - 1 f = inv * tmp^2 - k*tmp f = f.monic() x0 = f.small_roots(X=2^464,beta=1,epsilon=0.09) return x0
for k in trange(1,e): x0 = coppersmith(k) if x0 != []: dq = int(x0[0]) * 2^48 + dq_leak q = (e*dq + k - 1) // k p = n // q d = inverse(e,(p-1)*(q-1)) m = pow(c,d,n) print(long_to_bytes(int(m))) break """ 73%|███████▎ | 47793/65536 [11:46<04:22, 67.62it/s] b'flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}' """
defshash(value): """ Returns a Python 2.7 hash for a string. Logic ported from the 2.7 Python branch: cpython/Objects/stringobject.c Method: static long string_hash(PyStringObject *a) Args: value: input string Returns: Python 2.7 hash """
length = len(value)
if length == 0: return0
mask = 0xffffffffffffffff x = (Hash.ordinal(value[0]) << 7) & mask for c in value: x = (1000003 * x) & mask ^ Hash.ordinal(c)
x ^= length & mask
# Convert to C long type x = ctypes.c_long(x).value
if x == -1: x = -2
return x
@staticmethod defordinal(value): """ Converts value to an ordinal or returns the input value if it's an int. Args: value: input Returns: ordinal for value """
return value ifisinstance(value, int) elseord(value)
# sage10.3 from Crypto.Util.number import * from gmpy2 import * import hashlib, binascii
# 计算多项式的系数 mask = 0xffffffffffffffff PR.<v0,v1,v2,v3,v4,v5,v6> = PolynomialRing(ZZ) x = v0*128 for c in [v0,v1,v2,v3,v4,v5,v6]: x = 1000003 * x+c coe = x.coefficients()
#造格 t = (7457312583301101235^^7)&mask M = identity_matrix(ZZ, 9) bel=2^200 for i inrange(7): M[i, -1]=coe[i]*bel M[-2, -2] = 1 M[-1, -1] = 2**64*bel M[-2, -1] = -t*bel
''' 调平这里,其实直接调出矩阵的对应部分乘上2**20即可: M[:,-1:] *= 2^200 ''' res = M.LLL()[:-1] for i in res: if i[-1] == 0and i[-2]==1: res = i[:-2]
# 还原key a1 = invert(1000003, 2**64) key = b'' for i in res[::-1]: xa = (t-i)%(2^64) x = t^^xa key += long_to_bytes(x) t = (xa * a1)%(2**64) print(key) c = 13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017 m = int(hashlib.sha384(binascii.hexlify(key[::-1])).hexdigest(), 16) ^^ c print(long_to_bytes(m)) # flag{bdb537aa-87ef-4e95-bea4-2f79259bdd07}