d (p) 泄露

前置知识

欧拉降幂

$m_1 \equiv m \equiv (c^d \mod n) \mod p \\$

由模运算的性质，大模和小模在一起时，取外面的小模

$\therefore m_1 \equiv c^d \mod p$

由欧拉定理可知，当c与p互素时， 有

$c^{\phi(p)} = c^{p-1} \equiv 1 \mod p$

令 $d = k(p-1) + r$

则 $r = d \mod {p-1}$
(p-1) 是为了使用欧拉定理， 因为 r 没有任何限制， 所以总会存在 r 使得满足$d = k(p-1) + r$

$\begin{aligned} m_1 &\equiv c^d \\ &\equiv c^{k(p-1)+r} \\ &\equiv (c^k)^{p-1} \cdot c^r \\ &\equiv c^r \pmod{p} \\ &\equiv c^{d \pmod {p-1}} \pmod{p} \\ &\equiv c^{d_p} \pmod{p} \end{aligned}$

dp, dq是啥

$d_p = d \mod {p-1} \\ d_q = d \mod {q-1}$

dp & dq 泄露

nss

源码：

from Crypto.Util.number import *

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

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

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

dp = d % (p-1)
dq = d % (q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'c = {c}')
print(f'dp = {dp}')
print(f'dq = {dq}')

'''
p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
'''

分析

加密过程：
e, d 完全不知道，但给了 dp, dq

根据模运算的性质，大模和小模在一起时，取外面的小模， 有：

$m_1 \equiv m \equiv (c^d \mod n) \mod p \equiv c^d \mod p \\ m_2 \equiv m \equiv (c^d \mod n) \mod q \equiv c^d \mod q \tag{1}$

由欧拉降幂，有：

$m_1 \equiv c^{d_p} \mod p \tag{2} \\ m_2 \equiv c^{d_q} \mod q$

既然题目提供了 dp, dq 的值， 那么可以直接求出 m1, m2

将 m1 带入 (1)中 ，有：

$c^d = kp + m_1 \tag{3}$

将 $c^d$带入到 (1) 的 m2 中，有：

$m_2 \equiv (kp + m_1) \mod q$

即：

$(m_2 - m_1) p^{-1} \equiv k \mod q$

将 k 带入到 (3) 中：

$c^d = ((m_2 - m_1) p^{-1} \mod q) \cdot p + m_1$

由此，我们得到了一个 $c^d$ 的新求法， 不需要 e,d

exp

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

p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469

invt = inverse(p, q) # 计算在模q下 p ^ -1
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
c_d = (m1 - m2) * invt % q * p + m1 # 套公式
n = p*q
m = c_d % n
print(long_to_bytes(m))

dp 泄露(e较小)

nss

源码：

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
'''

分析

少了 dq ，但给了e
已知：

$d_p \equiv d \mod (p-1)$

那么有：

$d_p = d - k(p-1)$

乘e得：

$d_p \cdot e = d \cdot e - k \cdot e \cdot (p-1)$

很显然，模上 (p-1) 后有：

$d_p \cdot e \equiv d \cdot e \mod (p-1) \tag{1}$

对于 d, e 有：

$d \cdot e \equiv 1 \mod (p-1)(q-1)$

那么有：

$d \cdot e = k(p-1)(q-1) + 1$

带入到 (1) 中 ， 得到：

$\begin{aligned} d_p \cdot e &\equiv k(p-1)(q-1) + 1 \\ &\equiv 1 \mod (p-1) \end{aligned}$

去同余符号得：

$d_p \cdot e = k(p-1) + 1 \tag{2}$

$\because d_p < p-1$
$\therefore e > k$

从[1, e)遍历 k 的值，找到满足等式 (2) 的整数解，即可求出 p

判断条件
dp * e - 1 是 k 的整数倍
即 (dp * e - 1) % k == 0
且k可能有多个符号条件
所以要加上 n % p == 0 保证 p 是 n 的因子

exp

from Crypto.Util.number import *
from tqdm import *

n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
e = 65537

def dp_leak(result):
    for k in trange(1, e):
        temp = result % k
        if temp == 0:
            p = result // k + 1
            if n % p == 0: # 确保p是n的因子
                q = n // p
                return p, q

result = dp * e - 1
p, q = dp_leak(result)
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

dp 泄露(e很大)

nss

源码：

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 泄露，依然可以得出关系式

$d_p \cdot e = 1 + k(p-1)$

因为 k 的范围是 [1,e) , 当 e 比较小时可以爆破出 k 的值 ， 但现在 e 是128位素数，非常大，显然不可能爆破

看到

$d_p \cdot e \equiv 1 \mod (p-1)$

这个(p-1) ， 再次联想到欧拉降幂
随机选取一个与 p 不互素的数 a ，有：

$a^{d_p \cdot e} \equiv a^{d_p \cdot e \mod (p-1)} \equiv a \pmod p$

那么可以得到关系式：

$a^{d_p \cdot e} = kp + a$

进一步得到：

$a^{d_p \cdot e} - a = kp$

所以 $a^{d_p \cdot e}$ 有因子 p，只需要和 n 做 gcd 就能得到 p

注意
这里的 a 选取也比较有讲究

1. 首先必须和 p 互素，才能使用欧拉降幂
2. kp 也有可能是 n 的倍数，这时我们 gcd 得到的结果就会是 n

此外我们发现这题还有一个约束条件 ， 就是 $a^{d_p \cdot e} > p-1$ , 否则使用不了欧拉降幂，当 e 非常大时通常可以满足，但也有 dp 非常小的情况， 我们之后再讨论

exp

from Crypto.Util.number import *
from tqdm import *

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

dpe = dp*e
def dp_leak_e_big(dpe):
    a = getPrime(64)
    attemption = pow(a, dpe, n) - a # 为什么pow(a, dpe, n)， a^dpe 还要模n？
    p = GCD(attemption, n)
    if p > 1 and p < n:
        q = n // p
        if q > 1 and q < n:
            return p, q

p, q = dp_leak_e_big(dpe)
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

d 泄露

nss

源码：

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

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

assert 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)}
'''

直接给出了私钥， 要求还原公钥