2023香山杯

2023香山杯——Crypto

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

根据论文攻击：399.pdf (iacr.org)

此处$z = 1$,$x = d$

$d : 256bit,N:874 bit$，$d < N^{\frac{r(r-1)}{(r+1)^2}} = N^{\frac{20}{36}}$满足论文攻击条件

x用small_roots求解，这里用small_roots()是为了求解$d$，所以$X = 2^{256}$

$\because \phi(N) = p^4(p-1)(q-1)$，$\therefore gcd(ed - 1,N) = p^4 = g$

$\because \frac{p^4}{N} = 0.67$，$\therefore \beta = 0.67$，则small_roots()的beta（表示公因子的和N的比值） = 0.67（或者更小）

求解x之后进而求得p

在解RSA的时候发现e和phi存在公因数251，用本人已知的处理方法都没处理成功

然后想到在子群中先求解$m^{251}\equiv c^{d} \mod \phi(p_i)$，再用中国剩余定理结合，$p_i$指的是$n$的因子

处理方法参考了：HWS | hengxinyan’blog

exp:

from Crypto.Util.number import *
import itertools
import gmpy2

hint = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

R.<x> = PolynomialRing(Zmod(n))

f = e*x - 251
f = f.monic()
root = f.small_roots(X = 2^256,beta=0.16)
# print(root)
# 解得x = 39217838246811431279243531729119914044224429322696785472959081158748864949269

tmp = int(f(root[0])) #这里是ex-251的值

t = gmpy2.gcd(tmp,n) #求公因数
# print(t.)
p = gmpy2.iroot(t,4)[0]
q = n // p ^ 5
print("p =",p)
print("q =",q)

p_list = [p,q]
mi = [5,1]                #n = p^5 * q  这里存放的是因子的指数

n_list = [ZZ(p_list[i]) ** mi[i] for i in range(len(mi))] #就是[p^5 , q]
res = []

for pi in n_list:
    d = inverse(int(e//251),euler_phi(pi))     # 对n_list 每一个 pi 求欧拉函数
    m = pow(c,d,pi)                            # 在子群求解m^251
    res.append(Zmod(pi)(m).nth_root(251, all=True))   #这里用.nth_root是为了求所有可能的根？
    
for vc in itertools.product(*res):
    _c = [int(x) for x in vc]
    m = crt(_c, n_list)
    flag = long_to_bytes(int(m))
    if b"flag" in flag:
        print(flag)
        break

euler_phi(pi)直接计算欧拉函数

这里的 nth_root() 函数和gmpy2.iroot()的区别可能是前者能计算所有的根，而后者只计算出一个根

*res将res列表中的元素展开为多个独立的参数。

相当于是先在子群中求解，然后再用中国剩余定理