【 ? 】strange_rsa

本题虽然是防ak题，但还是简单说一下

观察一下这个式子

e = inverse_mod(d,(p**2+2)*(q**2+2))

inverse_mod是求逆元的意思

我们对它变一下形

e * d = 1 m o d (p^{2} + 2) * (q^{2} + 2) e * d = 1 + k * (p^{2} + 2) * (q^{2} + 2)

为方便书写，将

(p^{2} + 2) * (q^{2} + 2)

记为

p hi

,继续往下推:

e * d = 1 + k * p hi \frac{e * d}{p hi} = \frac{1}{p hi} + k \frac{e}{p hi} = \frac{1}{p hi * d} + \frac{k}{d} \frac{e}{p hi} - \frac{k}{d} = \frac{1}{p hi * d}

然后下面给一个连分数定理，如果存在 $α \in Q, c, d \in Z$ 满足

$∣ α - \frac{c}{d} ∣ < \frac{1}{2 * d ^{2}}$
则 $\frac{c}{d} 就是 α$ 的有理近似，即能够在 $α$ 的连分数找到 $\frac{c}{d}$

我们把视线切换回这道题，对于这题来说有:

\frac{e}{p hi} - \frac{k}{d} = \frac{1}{p hi * d}

由于

p hi

肯定大于

2 * d

所以肯定有：

\frac{e}{p hi} - \frac{k}{d} < \frac{1}{2 * d ^{2}}

那么肯定能在

\frac{e}{p hi}

的连分数里找到

\frac{k}{d}

，但是

p hi

不知道喵，这里注意一下，这个定理最神奇的地方在于它是有理近似，即你是不是

\frac{e}{p hi}

不重要，你只要能找到近似的值，它就能解。对于这题而言我们来试着找一找

p hi

的近似:

p hi = (p^{2} + 2) * (q^{2} + 2) = n^{2} + 2 * (p^{2} + q^{2}) + 4 = n^{2} + 2 * ((p + q)^{2} - 2 * n) + 4

我们将

p + q

用

2 * n

来近似，最后得到的式子为:

n^{2} + 2 * (4 * n - 2 * n) + 4 = n^{2} + 4 * n + 4

但是，有个更神奇的事，经过测试发现，这题只用

n^{2}

去近似

p hi

就能得到。最后的思路就是用

\frac{e}{p hi}

做连分数展开，寻找

d

。

连分数展开网上也有脚本，我只是简单改了一下

最后将 $p hi$ 与 $n$ 联立求解方程，解出 $p$ 和 $q$

from Crypto.Util.number import *
import gmpy2
def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
    
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):#用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        
        phi=(e*d-1)//k
        
        if is_prime(d) and int(d).bit_length() == 512: #找出d
            return d,phi
    
c = 12956557937383167105700562085868583488773222138122313505481611592691910504255708934030064860086770507477728706913986188451457461347636241031541919768956809563410145428312483609731977950383346101943382705186560156735715816414371589270039161992966449459847006265245042830193713158234358839530752435471408663425
n = 85237209301421558545124091811415820249470803544372134223951283875690939462440242717757605654620177763019192447672454664723814741942705046977202040621354749978950179460350196080744073445181637616299621894903087477614623828273077713362906245144387147211585165355024499194991495058937144579535048531964112156883
e =  1739958784330054976229698137375913453322936192180504618797675194809604561382914541289989653058249202276502036177048869750543061299056451906842735622258473626293370875729843269286203844098721390285522935597991293485396671703596086055519958931173885766442848639912555679704829275106062460006352366051176252888959162186192425126958970324578423596389917646077683361121389387720071607515592275348821053114084715003702961746887620492058536147687137343667920008141222649215554688002900985398123071244142171817632853217781024669969615680170073737458468369163042720029314784309028174957599880895607713730217840596535287639089

d,phi=wienerAttack(e,n**2)
var('p,q')
solve([(p**2+2)*(q**2+2) == phi, p*q == n],p,q)

对于本题而言求解出来的 $d$ 并不能真正解出我们的密文，根据RSA的解密原理，能解出密文的应该是 $e$ 在模 $n$ 的欧拉函数下的逆元才是真正的私钥 $d$ ，即如下：

d = inverse_mod(e , (p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))
#b'nex{wI3n3r_4Nd_COPper_ArE_cooI_5peC1AI}'

NEX 文档站

【 ? 】strange_rsa