HGAME 2024 WEEK1 Crypto Misc
CRYPTO(已解决3/4)ezRSA
题目描述：一个简单的RSA
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
n=p*q
phi=(p-1)*(q-1)
e=0x10001
c=pow(m,e,n)
leak1=pow(p,q,n)
leak2=pow(q,p,n)
print(f'leak1={leak1}')
print(f'leak2={leak2}')
print(f'c={c}')
"""
leak1=149127170073611271968182576751290331559018441805725310426095412837589227670757540743929865853650399839102838431507200744724939659463200158012469676979987696419050900842798225665861812331113632892438742724202916416060266581590169063867688299288985734104127632232175657352697898383441323477450658179727728908669
leak2=116122992714670915381309916967490436489020001172880644167179915467021794892927977272080596641785569119134259037522388335198043152206150259103485574558816424740204736215551933482583941959994625356581201054534529395781744338631021423703171146456663432955843598548122593308782245220792018716508538497402576709461
c=10529481867532520034258056773864074017027019578041866245400647840230251661652999709715919620810933437191661180003295923273655675729588558899592524235622728816065501918076120812236580344991140980991532347991252705288633014913479970610056845543523591324177567061948922552275235486615514913932125436543991642607028689762693617305246716492783116813070355512606971626645594961850567586340389705821314842096465631886812281289843132258131809773797777049358789182212570606252509790830994263132020094153646296793522975632191912463919898988349282284972919932761952603379733234575351624039162440021940592552768579639977713099971
"""我的解答：
根据题目关系式我们可以写出：
leak1 = pq mod q
leak2 = qp mod p
根据费马小定理：
ap−1 ≡ 1 mod p
推出：
leak1 = p
leak2 = q
exp:
import gmpy2
from Crypto.Util.number import *
p=149127170073611271968182576751290331559018441805725310426095412837589227670757540743929865853650399839102838431507200744724939659463200158012469676979987696419050900842798225665861812331113632892438742724202916416060266581590169063867688299288985734104127632232175657352697898383441323477450658179727728908669
q=116122992714670915381309916967490436489020001172880644167179915467021794892927977272080596641785569119134259037522388335198043152206150259103485574558816424740204736215551933482583941959994625356581201054534529395781744338631021423703171146456663432955843598548122593308782245220792018716508538497402576709461
c= 10529481867532520034258056773864074017027019578041866245400647840230251661652999709715919620810933437191661180003295923273655675729588558899592524235622728816065501918076120812236580344991140980991532347991252705288633014913479970610056845543523591324177567061948922552275235486615514913932125436543991642607028689762693617305246716492783116813070355512606971626645594961850567586340389705821314842096465631886812281289843132258131809773797777049358789182212570606252509790830994263132020094153646296793522975632191912463919898988349282284972919932761952603379733234575351624039162440021940592552768579639977713099971
e = 65537
n = p*q
phi = (p-1) * (q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#hgame{F3rmat_l1tt1e_the0rem_is_th3_bas1s}ezMath
题目描述：一个简单的数学题
from Crypto.Util.number import *
from Crypto.Cipher import AES
import random,string
from secret import flag,y,x
def pad(x):
return x+b'\x00'*(16-len(x)%16)
def encrypt(KEY):
cipher= AES.new(KEY,AES.MODE_ECB)
encrypted =cipher.encrypt(flag)
return encrypted
D = 114514
assert x**2 - D * y**2 == 1
flag=pad(flag)
key=pad(long_to_bytes(y))[:16]
enc=encrypt(key)
print(f'enc={enc}')
#enc=b"\xce\xf1\x94\x84\xe9m\x88\x04\xcb\x9ad\x9e\x08b\xbf\x8b\xd3\r\xe2\x81\x17g\x9c\xd7\x10\x19\x1a\xa6\xc3\x9d\xde\xe7\xe0h\xed/\x00\x95tz)1\\\t8:\xb1,U\xfe\xdec\xf2h\xab`\xe5'\x93\xf8\xde\xb2\x9a\x9a"我的解答：
考点：佩尔方程
解方程得到y，然后AES即可。
exp:
# sage
from Crypto.Util.number import *
from Crypto.Cipher import AES
a = 1
b = 114514
enc=b"\xce\xf1\x94\x84\xe9m\x88\x04\xcb\x9ad\x9e\x08b\xbf\x8b\xd3\r\xe2\x81\x17g\x9c\xd7\x10\x19\x1a\xa6\xc3\x9d\xde\xe7\xe0h\xed/\x00\x95tz)1\\\t8:\xb1,U\xfe\xdec\xf2h\xab`\xe5'\x93\xf8\xde\xb2\x9a\x9a"
numTry = 1500
def solve_pell(N, numTry):
cf = continued_fraction(sqrt(N))
for i in range(numTry):
denom = cf.denominator(i)
numer = cf.numerator(i)
if numer^2 - N * denom^2 == 1:
return numer, denom
return None, None
def pad(x):
return x+b'\x00'*(16-len(x)%16)
N = b//a
x,y = solve_pell(N,numTry)
print(y)
key = pad(long_to_bytes(y))[:16]
cipher = AES.new(key,AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)
# hgame{G0od!_Yo3_k1ow_C0ntinued_Fra3ti0ns!!!!!!!} ezPRNG
题目描述：一个简单的随机数
from Crypto.Util.number import *import uuiddef PRNG(R,mask): nextR = (R
页:
[1]