exp:
#解剩余定理,r=[余数],m=[模数]
def crt(r, m):
from functools import reduce
from Crypto.Util.number import inverse
from operator import mul
assert len(r) == len(m)
M = reduce(lambda x,y:x*y, m)
#M = [M//mi for mi in m]
t = [inverse(M//x,x)*(M//x) for x in m]
res = sum(map(mul,r,t)) % M
return res
#求解x^e = c mod p^order
def nthRoot_amm(c,e,p,order=1):
from gmpy2 import is_prime
from Crypto.Util.number import getRandomRange, inverse, GCD
assert is_prime(p) and is_prime(e) and (p-1)%e==0
cp = c%p**order if c>p**order else c
phi = (p - 1) * p**(order-1)
mod = p**order
for i in range(9999):
rho = getRandomRange(1, mod)
if pow(rho, phi // e, mod) != 1:
#print(f'i = {i}')
break
s = phi
t = 0
while s % e == 0:
s //= e
t += 1
assert GCD(s, e) == 1
#print(f't = {t} ')
alpha = inverse(e, s)
a = pow(rho, s*e**(t-1), mod)
b = pow(cp, e*alpha-1, mod)
c = pow(rho, s, mod)
h = 1
for i in range(1, t):
d = pow(b, e**(t-1-i), mod)
if d == 1:
j = 0
else:
j = e - next(filter(lambda x: pow(a,x,mod)==d, range(e)))
b = b * pow(c, e*j, mod) % mod
h = h * pow(c, j, mod) % mod
c = pow(c, e, mod)
root = pow(cp, alpha, mod) * h % mod
#找到其它根
from gmpy2 import next_prime
all_roots = set()
all_roots.add(root)
g = 3
while len(all_roots) < e:
newRoot = root
g = int(next_prime(g))
u = pow(g, phi//e, mod)
for i in range(e-1):
newRoot = (newRoot * u) % mod
all_roots.add(newRoot)
return list(all_roots)
def expUnrsa5():
from Crypto.Util.number import GCD, long_to_bytes
from itertools import product
from gmpy2 import iroot
e = 0x14
p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
n = p*q
c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642
print('gcd(e,p-1)',GCD(e,p-1))
print('gcd(e,q-1',GCD(e,q-1))
e1 = 5
cp1 = nthRoot_amm(c,e1,p)
cq1 = nthRoot_amm(c,e1,q)
cp1 = [nthRoot_amm(x,2,p) for x in cp1]
cq1 = [nthRoot_amm(x,2,q) for x in cq1]
mp = []
mq = []
for cp in cp1:
for cpp in cp:
mp.extend(nthRoot_amm(cpp,2,p))
for cq in cq1:
for cqq in cq:
mq.extend(nthRoot_amm(cqq,2,q))
for m1,m2 in product(mp,mq):
m = crt([m1,m2],[p,q])
flag = long_to_bytes(m)
if b'flag' in flag:
print(flag)
break
if __name__ == '__main__':
expUnrsa5()
2. 密码挑战系列
2.1. 真·Beginner
- 这题还真没做出来
2.2. 真·guessguess
- 利用已知的部分明文,使用z3求出key,然后解密即可
2.3. Lousy RSA
- 盲猜flag格式为flag{.*}那么第一位为f第二位为l
- 利用同余关系求出r,然后逐位爆破即可
- 部分exp
ct = c[0]
c0 = c[1]
c1 = c[2]
m0 = ord('f')
m0 = pow(m0,3,n)
m1 = ord('l')
m1 = pow(m1,3,n)
c0 = (c0 - pow(m0,3,n) - ct) * invert(3,n) * invert(m0,n) % n
c1 = (c1 - pow(m1,3,n) - ct) * invert(3,n) * invert(m1,n) % n
b0 = invert(m0,n) * m0**2 % n
b1 = invert(m1,n) * m1**2 % n
r = (c0 - c1) * invert(b0-b1,n) % n
2.4. Not That Right Use
- 做出来之后发现可能是非预期解,因为flag为
flag{NTRU_..........}
- 这里分享下我的解法
- 分析可知,解密的关键在于f和g必须小于一定的值,从而使得gr+mf<q
- 只要f和g足够小,就可以完成解密,并不需要使用加密时候的值
- f,h,g,q四个数满足关系:
- $f\cdot h = g\ mod\ q$
- h和q是已知确定的
- 可以通过辗转取余的方法,来约束g的值,从而求出f的值
- 部分exp
s = q % h
g = h % s
for i in range(10000):
g, s = g%s, s%g
if g <2**4000:
print(i)
break
f = h * gmpy2.invert(g,q) % q
f = gmpy2.invert(f,q)
d = gmpy2.gcd(f,g)
assert d == 1
flen = len(f"{f:b}")
print('flen =',flen)
print(decrypt(c,f,g,h,q))
2.5. so Damn big e?
- 这里走了不少弯路
- e除了过小意外,e再大都是没有攻击方式的,有攻击方式只可能是d出了问题
- 这题三组n,e,c根据提示, 为共享d攻击
- 没仔细研究,直接抄的脚本
- 部分exp
#sage
n = [n0,n1,n2]
e = [e0,e1,e2]
c = [c0,c1,c2]
M = isqrt(max(n))
A = Matrix(ZZ, len(e) + 1, len(e) + 1)
A[0] = [M] + e
for i in range(len(e)):
A[i + 1, i + 1] = -n[i]
AL = A.BKZ()
d = abs(AL[0, 0]) // M
print(f'found d with {d.nbits()} bits')
print(long_to_bytes(pow(c[0], d, n[0])))
2.6. Hammingway
- 直接爆破翻转, parity一致即为正确的值
- 部分exp
def unparity(slist):
res = ''
res = [slist[2]] + slist[4:7] + slist[8:]
return ''.join(res)
def strparity(slist):
for i in [0,1,3,7]:
slist[i] = '0'
parity = reduce(lambda a, b: a^b, [j+1 for j, bit in enumerate(slist) if int(bit)])
parity = list(reversed(list(str(format(parity, "04b")))))
return parity
def exp():
from itertools import product
c = open("enc", "r").read()
c = [list(c[i:i+15]) for i in range(0,len(c),15)]
strBin = ''
for cc in c:
for idx in range(len(cc)):
flip_cc = cc.copy()
flip_cc[idx] = str(1^int(flip_cc[idx]))
p1 = flip_cc[:2] + [flip_cc[3]] + [flip_cc[7]]
p2 = strparity(flip_cc)
if p1 == p2:
strBin +=unparity(flip_cc)
break
plain_str = ''.join([chr(int(strBin[i:i+8],2)) for i in range(0,len(strBin),8)])
print(plain_str)
if __name__ == '__main__':
exp()
2.7. o
- 简单,略
2.8. rsa-rsa-rsa-rsa
- 这题可能也是非预期解
- 直接套的类似d泄露的方法,解同余方程组, 感觉有点傻
- 四个方程跑出来几分钟到一个小时不等..
- 主要也是太菜了,没想到别的更好的方法
- 部分exp
#sage
def find_p(d0, kbits, e, n,r=1):
X = var('X')
nn = n//r
assert nn * r == n
for k in range(1, e+1):
results = solve_mod([e*d0*X - k*(r-1)*(nn*X-X^2-nn+X) == X], 2^kbits)
#results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)#p700*q1400
#results = solve_mod([e*d0*X - k*(X*nn-nn-X^2+X)*(r-1)== X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
print(k,'p0 = ',p0.nbits(),gcd(p0,nn))
if gcd(p0,nn) != 1:
return p0
if __name__ == '__main__':
e = 1667
c = 4863472644674217870502565424693713184000486927536995099651919590240866271469253214344182197334842137507506086858073884082195321114866653889949375924127756080834433032454456087411507323678798402153608823661022078160023141062260191255620270915331691502139415828179122879192294099884444457864136735926806260011876510858736421882145300532909608975279197160825647548849553174913916658119199697996174288038879828745214652265872117421930778762203853307243931789294163101430752597851152391642867666313642265617715322464199460030394197177929755093316075034884004768661209784916266357741690678348488199658622049287166258613947571770322996041
beta = 0.5
n = 3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591
r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421
d0 = 6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595
d0 = d0 % 2**700
nbits = n.nbits()
kbits = d0.nbits()
#kbits = 1050
print("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = int(find_p(d0, kbits, e, n,r))
print("found p: %d" % p)
2.9. EasyBits
- 这题本身的逻辑倒是不难
- 只是分解密文的时候factordb有一个大合数没有分解成功,需要使用yafu本地分解,小跑一段时间即可
- 部分exp
-
def baseTx(n,base):
res = []
for i in range(9999):
a = n % base
b = n//base
res.append(a)
n = b
if n == 0:
break
return res[::-1]
def getstr(sq):
sq0, sq1 = sq
res = []
for i in range(len(sq0)):
res.append(sq0[i])
if i < len(sq1):
res.append(sq1[i])
if len(sq1) > len(sq0):
res.append(sq1[-1])
res_bin = ''
bin_str = 0
for r in res:
res_bin += str(bin_str)*r
bin_str ^= 1
return ''.join([chr(int(res_bin[i:i+8],2)) for i in range(0,len(res_bin),8)])
c0 = open('ciphertext','rb').read()
c0 = bytes_to_long(c0)
from operator import mul
clist =
c = reduce(mul,clist)
print(c==c0)
from itertools import combinations,product
for k in range(1,len(clist)):
for sq in combinations(clist,k):
n0 = reduce(mul,sq)
n1 = c//n0
for n0_base,n1_base in product(range(5,8),range(5,8)):
sq = [baseTx(n0,n0_base),baseTx(n1,n1_base)]
flag = getstr(sq)
if checkflag(flag):
print('find flag',flag)
