公钥因子重组

首先说明适用情况：flag较短，多个因子，求不出逆元

姿势：

对因子重组，选出新的n，然后直接rsa解密

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *

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

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

e = 65537
while True:
    r = 2*getPrime(100)*e+1
    if isPrime(r):
        break

n = p*q*r

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'r = {r}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197
'''

n由多因子p, q, r构成。 p,q都是512位的素数，r有些特殊，r = 2*getPrime(100)*e+1

如果直接套多因子求phi的公式，会报错：
ZeroDivisionError: invert() no inverse exists

这是为什么捏~

回忆一下求d=inverse(e,ϕ)d = inverse(e, \phi)的过程，
有一个前提条件：e与ϕ互素e与\phi互素

在这道题中

ϕ=(p−1)∗(q−1)∗(r−1)=(p−1)∗(q−1)∗(2∗getPrime(100)∗e)\phi = (p-1)*(q-1)*(r-1)\\=(p-1)*(q-1)*(2*getPrime(100)*e)

∴ϕ一定是e的倍数\therefore \phi 一定是e的倍数
∴ϕ与e不互素\therefore \phi 与 e不互素
不互素则逆元不存在，那为什么inverse()还是能求解呢(虽然答案是错的),其实我们可以打印一下inverse()求得的d,会发现d=1d=1，它并没有进行数据校验

逆元不存在则私钥不存在，难道不可解了吗？
nonononono~

  • 观察题目发现，flag：NSSCTF{******}的长度非常小，则flag转成数字后的数m也非常小，小于512位的p,q，那么肯定也小于p∗q∗rp*q*r, 即小于n

那么有：

mmod  pq≡mmod  nm \mod pq \equiv m \mod n

什么意思呢，也就是说m不仅比n(这里的n=pqr)小，也比pq小，所以取模得到的结果是相同的

  • 对于同时mod  n,mod  pq,n>pq\mod n , \mod pq, n>pq

由模运算的性质有：

(amod  n)mod  pq=amod  pq(a \mod n) \mod pq = a \mod pq

设有：

c1=cmod  pq=(memod  n)mod  pq=memod  pqed1≡1mod  pqc1d1≡mmod  pqc_1 = c \mod pq = (m^e \mod n) \mod pq = m^e \mod pq\\ ed_1 \equiv 1 \mod pq\\ c_1^{d_1} \equiv m \mod pq

把pq看成新的n，直接rsa解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *

p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197

n = p*q*r
phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, p*q)

print(long_to_bytes(m))