e很大的dp泄露攻击

附件如下

from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*80

p = getPrime​​(512)
q = getPrime​​(512)

n = p*q
e = getPrime​​(128)
d = inverse​​(e, ​​(p-1)*​​(q-1))

dp = d % ​​(p-1)

m = bytes_to_long​​(flag)

c = pow​​(m, e, n)

print​​(f'n = {n}')
print​​(f'e = {e}')
print​​(f'c = {c}')
print​​(f'dp = {dp}')

'''
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
'''

我们知道dp*e = 1mod​​(p-1) => dp * e =k​​(p-1) +1

也就是说如果我们可以构造出一个式子使其求出来的解为kp或者k,那么我们就可以利用gcd来求出p.我们发现如果将其进行模p运算会发现其结果为a，同时也构成了kp

这个是时候进行构造\\
令gcd(a,p)=1,则
一个式子a^{dp*e}mod(p) \  ==>\\
a^{k(p-1)+1} mod(p)==>a^{kp-1}+a mod(p) ==> a  \ mod(p)\\
\\有费马小定理得到a^{p-1} \equiv \ 1 \ mod(p) == >  \ \   a^{dp*e} =  a^{k(p-1)+1}  \equiv \ 1^{k}*a\ mod(p) \\
kp=a^{dp}-a

代码如下

from Crypto.Util.number import long_to_bytes
from gmpy2 import *
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
k=1
a=2
p=gcd​​(powmod​​(a,dp*e,n)-a,n)
q=n//p
print​​(p*q==n)
phi=​​(p-1)*​​(q-1)
print​​(gcd​​(e,phi))
d=invert​​(e,phi)
m=powmod​​(c,d,n)
print​​(long_to_bytes​​(m))

NSSCTF{p_leak_but_with_huge_e}

d泄露攻击

题目如下

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

p = getPrime​​(512)
q = getPrime​​(512)

ass​​ert p < q

n = p*q
e = 65537
phi = ​​(p-1)*​​(q-1)
d = invert​​(e, phi)

print​​(f'n = {n}')
print​​(f'd = {d}')
print​​('flag is NSSCTF{md5​​(p)}')

'''
n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
flag is NSSCTF{md5​​(p)}
'''

题目中得知我们需要求解的是p，并且我们以知dne求解q

d=
n=
e=

根据之前的练习可以推断出 d *e = 1 mod​​(phi)，既然n=p * q.然后这个式子能不能找到与n的关系如下

phi=(p-1)*(q-1)\\
d * e = 1\ \ mod(phi)
\\令 r=de-1\\
r=k*(p-1)*(q-1)
\\取一个数a,条件式gcd(a,p,q)=1\\
a^{r}mod(p)=\ a^{k(p-1)(q-1)}\\
由费马小定理得到 a^{p-1} \equiv 1 \mod(p) 和a^{q-1} \equiv 1\ mod(q)
\\所以可以得到
a^{r} \equiv 1  \ mod(p) \ \ \ a^{r} \equiv 1 \ mod(q) \\
利用CRT或者式同于可以得到a^{r} \equiv 1 \ mod(n)

然后得到这个之后。我们令其r=2^s*t.

然后计算出s,t的值。这个时候我们就可以利用这个s,t来进行还原r的值了。因为我们选取的是2^s+t的值，那么其还原的过程如下

x=a^{t}\ \ mod(n)\\
x_1=x^{2}=a^{2^1*b}\ \ mod(n)\\
x_2=x1^{2}=a^{2^2*b}\ \ mod(n)\\
x_{i+1}=x_i^{2}\ \ mod(n)\\
\\\
\\\
x_{s-1} =a^{2^{s-1}*t}\ \ mod(n)\\
最后得到
\\x_s=a^{2^s*t}=a^{ed-1} \ \ mod(n) \equiv 1

有最后一步我们可以知道 X_s-1^2 = 1 mod​​(n),那么我们就可以利用其非平凡根来进行求解p,或者q.

p=gcd​​(X-1,n)或者是q=gcd​​(x+1,n)

为什么X_s-1^2 = 1 mod​​(n)可以得到p,q的倍数然后与n进行求解

下面为了方便我用x来进行代替\\
x^{2} \equiv \ 1 \ mod(n) \\
(x-1)*(x+1) \equiv \ 0 \ mod(n)\\
因为求解的是p,q，所以我们要对n进行拆分成 p,q\\
(x-1)*(x+1) \equiv \ 0 \mod(p) \\
得到两个接 x=1 , x=-1\\
同理在模q下也会有两个解x=1,x=-1\\
组合一起就是
(1 mod(q),1 mod(p))\\
(-1 mod(q),-1 mod(p))\\
(1 mod(q),-1 mod(p))\\
(-1 mod(q),1 mod(p))\\

然后因为我们要找的是非平凡因子，前两个是平凡因子。所以我们使用后面两个进行运算所以

x \ = 1 \mod(q),\ \ \ x\equiv-1\mod(p) ==>\\
x-1 \ = 0 \mod(q),\ \ \ x+1 \equiv \ 0 \mod(p)
\\
剩下的一个同理，然后你会发现得到的x-1对应的值有两个可能是q，也肯能是p.

import math
import hashlib
from gmpy2 import gmpy2
n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
e = 65537
a=e*d-1
s=0
b=0
while a%2==0:
    s+=1
    a=a//2
    b = a % 2
r=a
a=2
x=pow​​(a,r,n)
i=0
for _ in range​​(s):
    i+=1
    y=pow​​(x,2,n)
    if y==1 and x!=1 and x!=n-1:
        p=math.gcd​​(x+1,n)
        q=n//p
        p=min​​(p,q)
        print​​('NSSCTF{%s}' % hashlib.md5​​(str​​(p).encode​​()).hexdigest​​())
        print​​(i)
        break
    x = y

wiener

题目类型一般为d很大然后可以利用渐分数来获得其中所有近似的值，然后进行寻找其中的对应的d的值

题目如下

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

flag = b'NSSCTF{******}'

p = getPrime​​(256)
q = getPrime​​(256)

n = p*q
d = getPrime​​(128)
e = inverse​​(d, ​​(p-1)*​​(q-1))
m = bytes_to_long​​(flag)

c = powmod​​(m, e, n)

print​​(f'n = {n}')
print​​(f'e = {e}')
print​​(f'c = {c}')

'''
n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837
'''

根据欧拉法则我们可以得到

e*d \equiv \ 1  \ mod(n) \\
e*d-1 = k*n \ => \ 近似于 \ ed=k*n \ =>得到
\\ \frac{e}{n} \  = \ \frac{k}{d}

然后在我们得到d的候选者的情况下我们可以利用

phi=(p-1)*(q-1)=n-q-p+1\\
p+q=n+1-phi\\
s=p+q \ \ \ \ n=p*q\\则我们可以构造\\
x^2 - s*x + n = 0\\
然后利用根的判别式进行来进行筛选,令s=p+q\\
delta =s^2 - 4n\\
delta=delta = (p + q)^2 - 4pq=》delta = p^2 + 2pq + q^2 - 4pq=>delta = p^2 - 2pq + q^2==>\\
delta = (p - q)^2

那么着表明data的值一定为完全平方数。到这里整体的解题思路就没有了接下来就是来进行讲解如何获取候选d了

在形式上渐分数就是将一个分数拆解成带分数的形式，最后让其以整数结尾方便进行运算其逻辑如下

现在对其\frac{415}{93}进行渐分数拆解\\
其思路就是先对其进行分子分母反转，然后进行化简让其分母<1，然后继续化简直到反转之后为整数\\
\frac{415}{93}=4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}

其中我们进行每一个轮的值都是我们的候选d，由于在代码中为了方便进行编写我们采用分布计算的形式。先对其进行提取运算之后的整数也就是[4,2,6,7].然后我们将其进行还原每一步的值，这里在运算的时候有一个地推公式其证明如下：

现在我们知道前两组的值为[4,2,x]\\
我们可以运算得到抢两个值为4和\frac{9}{2}\\
对于第三个x对应的值为\\
4 + \frac1 {(2 + \frac1{x})}\\
4+\frac{1}{\frac{2x+1}{x}}=>4+\frac{x}{2x+1}\\
\frac{9x+4}{2x+1}\\
对于分子为x*上一个的分子+上上个的分子\ \ 分母同理\\
x_i=\frac{h_{i-1}x+h_{i-2}}{k_{i-1}x+k_{i-2}}

现在对于从第三个开始就比较好算了之前套公式就是了，应为他们的前面都有两项，但是对于前俩项我们去却没有，那么我们就需要对其进行构建前两项的值了还是根据例子进行观察前两项

第一项就是 \frac{4}{1}\\
第二项就是 4+\frac{1}{2}=\frac{9}{2}\\
对于第一个来说带入递推公式
\\x_i=\frac{4}{1}=\frac{h_{i-1}4+h_{i-2}}{k_{i-1}4+k_{i-2}}\\
那么令 \\
h_{i-1}=1,h_{i-2}=0\\
k_{i-1}=0,k_{i-2}=1\\
带入而中\\
x_2=\frac{4*2+1}{1*2+0}\\
成立符合，即构造

import owiener
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot, gmpy2, powmod

n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837
def a​​(n,e):
    while e:
        p=n//e

        yield p
        n,e=e,n-p*e

def  jianfenshu​​(arr):
    hi1=1;hi2=0#hil1
    ki1=0;ki2=1
    for x in arr:
        h=x*hi1+hi2
        k=x*ki1+ki2
        yield h,k
        hi1,hi2=h,hi1
        ki1,ki2=k,ki1
def attack​​(e,n):
    for k,d in jianfenshu​​(a​​(e,n)):
        if k==0:
            continue
        if ​​(e*d-1)%k!=0:
            continue
        phi=​​(e*d-1)//k
        s=n+1-phi
        data=s*s-4*n
        if iroot​​(data,2)[1]==True:
            print​​('分解成功')
            t=iroot​​(data,2)[0]#p-q.s=p+q
            p=​​(t+s)//2
            q=​​(s-t)//2
            if p*q==n:
                m=powmod​​(c,d,n)
                print​​(long_to_bytes​​(m))
            return d

    print​​('失败')
    return None
attack​​(e, n)

b'NSSCTF{e_is_so_huge}'