RSA（二）

1.p-1光滑攻击

练习平台NSSCTF

光滑攻击

当一个数的最大素因子组不大于B时，我们可以称其为B-光滑数，例如6=2*3可以称其为3-光滑数，12=2^2*3可以称其为4-光滑（因为2^2是最大的素因子组）数（注意我们也可以叫它5-光滑、6-光滑、n-光滑​​(n>3)）。那么对于*p*来说它是p-光滑数（因为它是素数），但*p*−1包含很多小素数因子，我们假设*p*−1为k-光滑数，存在这样的一个数*M*

M = \prod_i{p_i}^{\log_{p_i}{k}}

这保证了构造出来的M=mk如

p=10的素因子为 2 3 7 5
那么M1=2^log2 10=2^3 //向下取整
M2=3^3
M=2^3*3^3*7*5

因为得到的M大于p的最大素因子然后我们就可以得到

​​(p-1)|M
gcd​​(M,N)=p

题目如下

from Crypto.Util.number import *
from random import choice

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

def getMyPrime​​(nbits):
    while True:
        p = 1
        while p.bit_length​​() <= nbits:
            p *= choice​​(sieve_base)
        
        if isPrime​​(p+1):
            return p+1

p = getMyPrime​​(256)
q = getMyPrime​​(256)

n = p*q
e = 65537
m = bytes_to_long​​(flag)
c = pow​​(m, e, n)

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

'''
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
'''

首先要先看懂部分代码，这个题目的加密逻辑为随机选取素数​​(sieve_base生成一串素数)与p相乘，当p+1为素数是就停止循环。

那么我们可以知道p是有多个素数相乘得到的 （1）

更具前面的知识我们应该构造一个M然后对其进行解题，但是M我们利用代码表示不好表示，所以我们对其进行扩大找其k!

a^{M}=a^{t*(p-1)}\equiv \ 1^{t} mod(p) =>
\\gcd(a^M-1,n)=p
\\应为M|k!  =>
\\gcd(a^{k!}-1,n)=p  =>
\\a^{k!}\equiv \ 1\ \ \ mod(p)

然后对于求解a^k!

\\
我们可以将1进行代换掉，式子等价于
\\  a^{(k+1)!} \equiv  (a^{k!} \ mod(p)\ )^{(k+1)} \ \ mod(p)

求出之后利用gcd​​(a^{k!}-1,n)=p进行判断如何p不是1和n那么就表示分解成功

from  Crypto.Util.number import *
from math import *

from gmpy2 import powmod_exp_list, gmpy2, invert, powmod

n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
a=2
m=2
ass​​ert gcd​​(a,n)==1
while 1:
    a=gmpy2.powmod​​(a, m,n)
    p=gcd​​(a-1,n)
    if p!=1 and p!=n:
        break
    m+=1
q=n//p
phi=​​(p-1)*​​(q-1)
d=invert​​(e,phi)
m=powmod​​(c,d,n)
print​​(long_to_bytes​​(m))

b'NSSCTF{p-1_smooth_with_factor}'

2.dp&dq泄露

首先对于dp和dq的含义为d在模p下的运算，或者是d在模q下的运算

我们知道在对于一般情况来说我们的加密是c=pow​​(m,e,n),而解密是m=pow​​(c,d,n).但是应为n=p*q，所以此时根据中国剩余定理我们可以得到 m1=pow​​(c,d,p),m2=pow​​(c,d,q)。

我们让其d%​​(p-1) 也就等价于 d=k​​(p-1)+r

m1 \equiv \ pow(c,d,n) => \ \ m1= c^d \ mod(p) \\
\\m1 = c^{k(p-1)+r}\ \ mod(p)
\\应为费马gcd(c,p)=1 => \ c^{p-1} \equiv \ 1  \ mod(p)\\
m1=c^{r} \ \ mod(p)

而我们这里的题目给出的dp就等价于这里的r,应为我们将n进行拆分了所以我们将其在计算m的时候也需要进行合并。

但是如果m<p,m<q。话就不需要应为他的求模还是他自己，所以我们得到的m就是真正的flag，但是如果当

m>q.m>p的时候我们就需要将其进行CRT和并了

应为我们得到mp,mq相当于是m在模p.q下的取值。所以

m_p\ \equiv \ m\mod(p)\\
m_q\ \equiv \ m\mod(q)\\
m_p+k_2p\ =m \\
m_q+k_1q\ =m \\
m_q\ =k_2p+m_p \ \ mod(q) \\
k_2p= m_q \ -m_p \ mod(q)\\
k_2=(m_q-m_p)*invert(p,q) mod(q)
\\
\\m=m_p+k2*p

from Crypto.Util.number import long_to_bytes

from gmpy2 import gmpy2, invert

p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
mp=pow​​(c,dp,p)
mq=pow​​(c,dq,q)
invp = invert​​(p, q)
k=​​(mq-mp)*invert​​(p,q)%q
m=mp+k*p
print​​(long_to_bytes​​(m))

或者应为m<p,q，mq和mp就是m

from Crypto.Util.number import long_to_bytes

from gmpy2 import gmpy2, invert

p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
mp=pow​​(c,dp,p)
mq=pow​​(c,dq,q)
print​​(long_to_bytes​​(mq))

3.dp泄露攻击

from Crypto.Util.number import *

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

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

n = p*q
e = 65537
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'c = {c}')
print​​(f'dp = {dp}')

'''
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
'''

题目给出dp和e,根据dp和d的关系我们知道

dp \equiv \ d \ mod(p-1) \\ \
dp*e \  \equiv \ d*e \ mod(p-1) \\
e*d \ \equiv \ 1 \ mod(phi) => phi=(p-1)*(q-1) => e*d \equiv 1 \ mod(p-1)

所以ed-1 = k*​​(p-1),然后反接p

from Crypto.Util.number import long_to_bytes
from gmpy2 import gmpy2
d=1
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
e=65537
for k in range​​(1,e):
    if ​​(dp*e-1)%k!=0:
        continue
    p=​​(dp*e-1)//k+1
    print​​(k)

    if n%p==0:
        phi = ​​(p - 1) * ​​(n//p-1)
        d=gmpy2.invert​​(e,phi)
        m=pow​​(c,d,n)
        print​​(long_to_bytes​​(m))
        break