RSA常见题型

一、普通解密(给出e,c，且已知p,q或较易分解的n)

可以直接根据RSA的基本原理写出脚本，对于较易分解的n可以使用factor网站在线质因数分解，也可以使用yafu工具进行分解。

基本解密过程：

phi(n)=(p-1)*(q-1) #计算欧拉函数

ed≡1 mod phi(n) #通过该表达式求密钥d

c**d≡m mod n #最后求得明文m

注意：计算出的m是一串数字，要得到真正意义上的明文，还得将其转化成字符。（不排除某些题目直接以m作为明文。）

二、给出了n,p,q,dp,dq,c但未给出e

由于没有e我无法直接利用原理解出d，而使用中国剩余定理会因为p-1和q-1不互质而受到阻碍。

自己就推导了一个公式（因为看不懂别人写的解法）：

c**dp≡m mod p

(dp换成dq也是可以的，但对应的p就要换成q）

推导过程如下：

dp≡d mod p-1

d=dp+k*(p-1)#k为整数

c**d=c**(dp+k*(p-1))

c**d≡m mod n

c**(dp+k*(p-1))≡m mod n

n=p*q

c**(dp+k*(p-1))≡m mod p

由费马小定理：a**(p-1)≡1 mod p

c**(p-1)≡1 mod p

c**k(p-1)≡1 mod p#k为整数时可由二项式定理证得，而当k为负数时，计算要先取逆元再-k次方，仍然可证。

c**dp≡m mod p

三、 共模攻击（给出一个n和多组e,c）

寻找一组互质的e1,e2,再由欧几里得扩展算法可得：

e1*s1+e2*s2 = 1

之后想方设法拼凑表达式利用该条件

c1 = m**e1 mod n

c2 = m**e2 mod n

(c1**s1*c2**s2) mod n = ((m**e1 mod n)**s1*(m**e2 mod n)**s2)%n

(c1**s1*c2**s2) mod n = ((m**e1)**s1*(m**e2)**s2) mod n

(c1**s1*c2**s2) mod n = (m**(e1*s1+e2*s2)) mod n

c1**s1*c2**s2≡ m mod n

import gmpy2 as gp
import libnum
n=int(input("请输入n： "))
e1=int(input("请输入e1: "))
c1=int(input("请输入c1: "))
e2=int(input("请输入e2: "))
c2=int(input("请输入c2: "))
s=gp.gcdext(e1,e2)
s1=s[1]
s2=s[2]
if s1<0:
    s1=-s1
    c1r=gp.invert(c1,n)
    m=pow(c1r**s1*c2**s2,n)
else:
    s2=-s2
    c2r=gp.invert(c2,n)
    m=pow(c1**s1*c2r**s2,n)
print(libnum.n2s(m))

四、 给出pem,enc 文件（或者其他将flag和解密信息放在文件中的题目）

1.

使用openssl工具（这个Linux自带）使用命令:

openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem

得到n,e,此时利用工具对n进行分解得到p,q。

再用 rsatool 生成私钥文件: private.pem python rsatool.py -o private.pem -e 65537 -p XXXXX -q XXXX

最后用 private.pem 解密 flag.enc openssl rsautl -decrypt -in flag.enc -inkey private.pem

可以得到答案。

2.

查看公钥文件也可以直接使用Python的一些库来完成操作。

from Crypto.PublicKey import RSA

pub1=RSA.importKey(open('./publickey1.pem').read())
n1= pub1.n
e1= pub1.e

该操作可以直接读取公钥文件中的数据。

之后就是正常解密流程，得到，p,q,d。

import rsa

privatekey = rsa.PrivateKey(n,e,d,p,q)
str=f.read()
print(rsa.decrypt(str,privatekey).decode())

直接得到Privatekey,并志杰用其解密flag所在的文件，输出flag。

五、 多组n,c，求m（低指数广播攻击）

对于多组，n,c,且已知e或e较小的情况。

利用中国剩余定理可以直接解出m**e,然后直接开根解得m。

import gmpy2 as gp
from Crypto.Util.number import long_to_bytes
n1=0xe096219878f492bcdb2a2d03995521e7a65125733bae18e7d0005e35343fea3653698de60231d29b2d1b44a0b4ffd3183855b9042275f769e1702fa8843062df0938821db0258af40ab3cda8e54eb6ac826d545df91dfe76266cb01b1d6fad39e6ef13ce730c1c2395136b0bbdf22c6b0daba63701d71c6ae70d4e06935b9941
c1=0xff24bddc5a7b327535af92dba58c5d62a22d542e6ba1df6f91c98c7563d8e48e770fb623bfcc2f09ed49788293306ff709670b225da32ea134422d5e403b11c39ef6b144f96b2fe94b3aa136432ecea86a4069a4cb0b4d8570edb3fb5bb2cf0693184ef0c589887b012ebe6ea94e854a71a7eb768133d15e784e388976877db
n2=0xa36b15a395edf3e99927f658e22d5f4aefd83434972c96cca5242a1aaa517ad83739451269723092dd9e73c00682dd3bbd74a985546def88196119b6d57b397283bc7b8b6029916df84284bec1725f6e5d3d29042af685c508a58ab6fb4e5bfeb326ae49330e3f4426abc1860ca4412feb976ee571075a47b854c9a6f5f0ebff
c2=0x895f8283e2200bab1bf938ce3b5e42147b53a5178e436ea0b64a2380ba99776d5ba8046ef722858b20d9650ee68c09e905030f1634e0b32397b7b12236a5a301e5923a294ef1bdf16458f4fc8677370ce2ce3d0fd957da7466e5b104191d454455917147f3187b758c1c468db1b35514391e5b36bd1ac39e91bbb24fdbc07872
n3=0x9d4732db2539d1166dc6865670be11951bf49295bc8c472f34682a0fb7f2b3ba96dcfa1945c2e4685dfeae5255abe2ab3b7fb2282971bb16ce02d14082f71755e8a65c956e114336914a409a9f1158fb362a92c4e169fa3c460ea26fb5c6693447b14f1c3156a2d9308dd993d7ea708a00ad149fb77109d8a5f77de1703ba249
c3=0x3bead3d6760bff4de22562978d4722bb21ee4792ebdb32703b6df9ff5176e033e97ad8fc81467f4b3df7bd4e8bcae09462f3eca93a3da1cd9d7e8de3e464471fdd0b70112c1c738b0daa2a37a65331eaa8954b81b410f62a0280da32eb3e305782d5f774d814ca0adb13344687387cf72657dc21724bcf69da810d7635b99467
n1=int(n1)
c1=int(c1)
n2=int(n2)
c2=int(c2)
n3=int(n3)
c3=int(c3)
t1=gp.invert(n2*n3,n1)
t2=gp.invert(n1*n3,n2)
t3=gp.invert(n1*n2,n3)
weim=(c1*t1*n2*n3+c2*t2*n1*n3+c3*t3*n1*n2)%(n1*n2*n3)
m=gp.iroot(weim,3)
print(m)#这里先把m打印出来，可以得到类似mpz(....)这种数据，括号内就是所需的m数值，但这个带括号的数据不能直接使用long_to_bytes转化，所以这里先把m打出来然后直接复制到下面的函数里转化。
print(long_to_bytes(11667486319353623306221917311659938391432552876667393571592853766459303917362695551586161498975732393341))

但是如果已知e，也是可以直接爆破的，因为c≡m** e mod n,可以推出m**e=c+k *n,且一般k会大于零，因为根据rsa原理，我们是由m**e%n直接得到c，（因为如果c大于n，会有无数个解），所以可以直接把可能的k值带进去得到答案。

六、给出n,e,dp,c的题目。

d=dp+k1*(p-1)

de=1+k2*(p-1)*(q-1)

将这两个式子结合得：

e*dp+e*k1*(p-1)=k2*(p-1)+1

再将这个式子两边对（p-1）同时取余可得：

e*dp☰1 mod p-1

即：

e*dp=k*(p-1)+1

又因为dp<p-1,k*(p-1)<e*dp

所以e>k;

接下来利用该表达式对k进行遍历就可以了，遍历范围(0,e)。