香山杯复现
lift
import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
return s + os.urandom(l - len(s))
def gen():
g = getPrime(8)
while True:
p = g * random.getrandbits(138) + 1
if isPrime(p):
break
while True:
q = g * random.getrandbits(138) + 1
if isPrime(q):
break
N = p ** 5 * q
phi = p ** 4 * (p - 1) * (q - 1)
d = random.getrandbits(256)
e = inverse(d, phi)
E = e * g
hint = gmpy2.gcd(E, phi)
return N, E, hint
flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
# hint = 251
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
# c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
根据gen函数,我们可以得知:
$n=p^5q,E=e*g,hint=gcd(E,\phi(n)),p=g*a1+1,q=g*a2+1$
又因为:
$$\phi(n)=p^4(p-1)(q-1)=p^4(g*a1)(g*a2)$$
所以g一定是E和$\phi(n)$的公因子,所以g|hint
但我们发现hint是个质数,所以我们可以得知g=hint=251
由于n是多素数组成的,且d仅有256位,所以d是一个小根,因此可以考虑用copper来求解d
$$ed\equiv 1\ (mod\ \phi(n))$$
得到d之后,根据$ed-1=kp^4(p-1)(q-1)$,$n=p^5q$,我们可以知道$gcd(ed-1,n)=p^4$(至少为$p^4$),所以我们依次可以求出p,q的值
exp部分:
from gmpy2 import *
E = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
g = 251
e = E // g
PR.<d> = PolynomialRing(Zmod(n))
f = e * d - 1
f = f.monic()
ans = f.small_roots(d = 2 ** 256, beta = 0.66)
print('d =', ans[0])
p4 = GCD(e * int(ans[0]) - 1, n)
p = iroot(p4, 4)[0]
print('p =', p)
q = n // (p * p4)
print('q =', q)
得到p,q之后,因为得到c的式子为:
$$c\equiv m^{E}$$
因为E和n不互质,我们无法直接求E逆元,但我们知道e的逆元d,可得到:
$$c^d\equiv m^g\ (mod\ n)$$
因为$n=p^5q$,我们可以想到上式可以拆为:
$$\left\{\begin{array}{rcl}c^d\equiv m^g\ (mod\ p)\\c^d\equiv m^g\ (mod\ q)\\\end{array} \right. $$
然后用AMM算法,我们可以将上述式子求出:
$$\left\{\begin{array}{rcl}m_p\equiv m^g\ (mod\ p)\\m_q\equiv m^g\ (mod\ q)\\\end{array} \right. $$
但是$n=p^5q$,flag被填充到了512位,若是直接用中国剩余定理去求$mod\ pq$下的根是不够的
这里我们可以用Hensel lifting将$mod\ p$下的解提升至$mod\ p^5$下的解
Hensel lifting引理 设$k\geq 2$是正整数,p为素数, $f(x)\equiv 0\ (mod\ p^{k-1})$
如果$f'(x)\not\equiv 0\ (mod\ p)$,那么存在在$mod\ p$意义下唯一的整数t,使得$f(x+tp^{k-1})\equiv 0\ (mod p^k)$由$t\equiv -f'(x)^{-1}({f(r) \over p^{k-1}})$给出
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\equiv 0\ (mod\ p^k)$,那么对任意正整数t,都有$f(x+tp^{k-1})\equiv 0\ (mod p^k)$
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\not\equiv 0\ (mod\ p^k)$,那么对任意正整数t,都有$f(x+tp^{k-1})\not\equiv 0\ (mod p^k)$
详细介绍可以参考:Hensel lifting引理
此题正好有$f(m)=m^g-c^d\ (mod\ p)$,且我们已经用AMM算法求出m的所有可能情况,我们将之转至$\mod p^5$下,可以有$f(m)=m^g-c^d\ (mod\ p^5)$,在模$p^5$情况下得到的m已经足以满足512位的要求,所以此时我们只需要判别是否包含flag标识就可以得到明文m了
exp:
from Crypto.Util.number import *
from gmpy2 import *
import random
def onemod(e, q):
p = random.randint(1, q - 1)
while ((powmod(p, (q - 1) // e, q)) == 1):
p = random.randint(1, q)
return p
def AMM_rth(x, e, N):
assert ((N - 1) % e == 0)
p = onemod(e, N)
t = 0
s = N - 1
while (s % e == 0):
s = s // e
t += 1
k = 1
while ((s * k + 1) % e != 0):
k += 1
delta = (s * k + 1) // e
a = powmod(p, e ** (t - 1) * s, N)
b = powmod(x, e * delta - 1, N)
c = powmod(p, s ,N)
h = 1
for i in range(1, t):
d = powmod(b, e ** (t - 1 -i), N)
if d == 1:
j = 0
else:
j = (- math.Log(d, a)) % e
b = b * (c ** (e ** j)) % N
h = h * (c ** j) % N
c = c ** e % N
result = powmod(x, delta, N) * h
return result
def ALL_ROOT2(r, q):
list1 = set()
while(len(list1) < r):
p = powmod(random.randint(1, q - 1), (q - 1) // r, q)
list1.add(p)
return list1
def ALL_Solution(m, q, rt, cq, e):
mp = []
for pr in rt:
r = (pr * m) % q
mp.append(r)
return mp
d = 39217838246811431279243531729119914044224429322696785472959081158748864949269
p = 69367143733862710652791985332025152581988181
q = 67842402383801764742069883032864699996366777
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
g = 251
c1 = powmod(c, d, n)
cp = c1 % p
mp = AMM_rth(cp, g, p)
rt1 = ALL_ROOT2(g, p)
amp = ALL_Solution(mp, p, rt1, cp, g)
k = 5
for m in amp:
for i in range(1, k):
inv_fx = - invert(g * (m ** (g - 1)), p)
di = (m ** g - c1) // (p ** i)
t = inv_fx * di % p
m = m + (p ** i) * t % (p ** ( i + 1))
if b'flag' in long_to_bytes(m):
print(long_to_bytes(m))
看的我热血沸腾啊https://www.ea55.com/