【Crypto】RSA

参考：CTF中关于RSA的常见题型_abtgu的博客-CSDN博客_ctf rsa题目

p,q->n,φ(n)
φ(n)->e
e,φ(n)->k,d：d = gmpy2.invert(e,(p-1)*(q-1))
e,n->公钥
d,n->私钥
c = pow(m, e, n)

1.已知(p,q,e),求d

import gmpy2
p = 
q = 
e = 
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(d)

2.已知(p,q,e,c)，求m

密文c，明文m

import gmpy2 
import binascii

c = 
e =  
p = 
q = 
 
# 计算私钥 d
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
 
# 解密 m
m = gmpy2.powmod(c,d,p*q)
print(binascii.unhexlify(hex(m)[2:]))

3.已知(p,q,dp,dq,c)，求m

import gmpy2
import binascii
p =
q =
dp =
dq =
c =

I = gmpy2.invert(p,q)
mp = gmpy2.powmod(c,dp,p)
mq = gmpy2.powmod(c,dq,q)

m = ((I*(mp-mq))%q)*p+mp
print(binascii.unhexlify(hex(m)[2:]))

4.已知(e,dp,n,c)，求m

import gmpy2
import binascii
e = 
n =
dp =
c =
for i in range(1,e):
    if (e*dp-1)%i == 0 and n%((e*dp-1)//i+1)==0:
        q = n//((e*dp-1)//i+1)
        phi = (q-1)*((e*dp-1)//i)
        d = gmpy2.invert(e,phi)
        m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

5.已知(n,e1,e2,c1,c2)，求m

import gmpy2
import binascii

n =
c1 = 
c2 = 
e1 = 
e2 = 

s = gmpy2.gcdext(e1,e2)
a = s[1]
b = s[2]

if a<0:
    a = -a
    c1 = gmpy2.invert(c1,n)
else:
    b = -b
    c2 = gmpy2.invert(c2,n)

m = (gmpy2.powmod(c1,a,n)*gmpy2.powmod(c2,b,n))%n

print(binascii.unhexlify(hex(m)[2:]))

6.已知(e,n1,c1,n2,c2)，求m

解题思路： 两组数中e相同，n，c不同，求出n1与n2的最大公因数即为p，之后就可以得到q和d，从而求解m。

import gmpy2
import binascii
 
e = 
n1 = 
c1 = 
n2 = 
c2 = 

p1 = gmpy2.gcd(n1,n2)
q1 = n1 // p1
phi1 = (p1-1)*(q1-1)
 
d1 = gmpy2.invert(e,phi1)
m1 = gmpy2.powmod(c1,d1,n1)

print(binascii.unhexlify(hex(m1)[2:]))

p2 = gmpy2.gcd(n2,n1)
q2 = n2 // p2
phi2 = (p2-1)*(q2-1)

d2 = gmpy2.invert(e,phi2)
m2 = gmpy2.powmod(c2,d2,n2)

print(binascii.unhexlify(hex(m2)[2:]))

7.已知(p+q,p-q,e,c)，求m

import gmpy2
import binascii
e=
a=
b=
c=

p = (a+b)//2
q = (a-b)//2

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)

m = gmpy2.powmod(c,d,p*q)
print(binascii.unhexlify(hex(m)[2:]))

7.已知(e,n,c)，求m

解题思路：
可以分解n得到p,q

在线分解大整数网址:

http://www.factordb.com/index.php

分解质因数工具 - 整数分解最多为70位

注意：在factordb中因为数过大而显示不全时，可以点击show查看完整数据，但是在复制数据时注意它的每一行都有空格，粘贴后要去掉

若以上都不好用，则用yafu计算

import gmpy2
import binascii

e = 
n = 
c = 
p = 
q = 

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

8.已知(e,n,c)，求m（e极小，如3，低加密指数攻击）

import gmpy2
import binascii

e =
n =
c =

i = 0
while True:
    if gmpy2.iroot((c+i*n),3)[1] == True:
        m = gmpy2.iroot((c+i*n),3)[0]
        break
    i += 1

print(binascii.unhexlify(hex(m)[2:]))

9.已知(e,n,c)，求m（e很大，低解密指数攻击）

解题思路： 题中e很大，故可知是低解密指数攻击。
可以使用破解脚本：求出d的值，文件下载地址GitHub - pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme.
（注意，这里要将破解脚本和rsa-wiener-attack的py文件放在同一个目录下）

import gmpy2
import binascii
import RSAwienerHacker

e =
n =
c =

d = RSAwienerHacker.hack_RSA(e,n)
m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

10.已知(c,n,p*(q-1),q*(p-1))，求m

import gmpy2
from Crypto.Util.number import *
#pq = p*(q-1)
#qp = q*(p-1)
c= 
n= 
pq= 
qp= 

e = 65537
p = n - pq
q = n - qp
phi = (p - 1)*(q - 1)

d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))