一些CTF比赛中用到的RSA题目脚本
e,p,q,c
import gmpy2 as gp
import binascii
p = gp.mpz()
q = gp.mpz()
e = gp.mpz()
c = gp.mpz()
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(m)
e,n,dp,c
import gmpy2 as gp
e =
n = gp.mpz()
dp = gp.mpz()
c = gp.mpz()
for x in range(1, e):
if(e*dp%x==1):
p=(e*dp-1)//x+1
if(n%p!=0):
continue
q=n//p
phin=(p-1)*(q-1)
d=gp.invert(e, phin)
m=gp.powmod(c, d, n)
if(len(hex(m)[2:])%2==1):
continue
print('--------------')
print(m)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))
p,q,dp,dq,c
import gmpy2 as gp
p = gp.mpz()
q = gp.mpz()
dp = gp.mpz()
dq = gp.mpz()
c = gp.mpz()
n = p*q
phin = (p-1)*(q-1)
dd = gp.gcd(p-1, q-1)
d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
print(d)
m = gp.powmod(c, d, n)
print('-------------------')
print(m)
print(hex(m)[2:])
n,e（e长度较大）
import RSAwienerHacker
n=
e=
d = RSAwienerHacker.hack_RSA(e,n)
if d:
print(d)
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
print(flag)
p,q,e求d
import gmpy2
from Crypto.Util import number
p = 473398607161
q = 4511491
e = 17
d = gmpy2.invert(e,(p-1)*(q-1))
print(d)
n,e,d求p,q
from gmpy2 import next_prime, gcd
def Factorize(n, e, d):
g = 2
while True:
k = e * d - 1
while not k & 1:
k //= 2
p = int(gcd(pow(g, k, n) - 1, n)) % n
if p > 1:
return (p, n // p)
g = int(next_prime(g))
if __name__ == "__main__":
n = 0x75be564267f8bf6c2038dd0cadfeecbc3158acfc27e679dd0bdb0db0e90bd5198a0a7edc0626f357a2d75f3c37ede045b7f7ca6bda79e5bf6fc0aea0aa7beda587388599d2b77b538fc3e666784493ffaf731e2ae232e8e9e9f9f2a4df25c19b7680f5bf6c485bd87923f01c17d8ec35438772c28e361774e6e7681d67ecbe19
e = 0x14b367bf01efd4dc667b8e62975479c612c96e78f7f1f55242b2973c882ddcb33a65c52174d8ae1273764ce429054ea3f2fdc38ff205443c92ef4198739f05aa11fc10d3fc6ff30c8f5f05a04f43e3d8fc9bfffe916b2e0360560a162729e91b7775bda70177e0f875626e0a81bd4eacea9948b02232a82659f8d9aa9b4c754f
d = 105446909057629013379692394355251350740773777593653963988108428818399001716079
print(Factorize(n, e, d))
共模攻击(n,m相同,c,e不同)
from libnum import n2s,s2n
from gmpy2 import invert
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def main():
n =
c1 =
c2 =
e1 =
e2 =
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
s1 = - s1
c1 = invert(c1, n)
elif s2<0:
s2 = - s2
c2 = invert(c2, n)
m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(hex(m))
if __name__ == '__main__':
main()
共模攻击（分解e1e2并爆破判别）
n=
c1=
c2=
e1e2=
import libnum
import gmpy2
def rsa_gong_N_def(e1,e2,c1,c2,n): #共模攻击函数
e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
print("e1,e2:",e1,e2)
s = gmpy2.gcdext(e1, e2)
print("mpz:",s)
s1 = s[1]
s2 = s[2]
if s1 < 0:
s1 = - s1
c1 = gmpy2.invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = gmpy2.invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
return int(m)
def de(c, e, n): #因为此时的m不是真正的m，而是m^k，所以对m^k进行爆破
k = 0
while k<1000: #指定k小于1000
mk = c + n*k
flag, true1 = gmpy2.iroot(mk, e) #返回的第一个数值为开方数，第二个数值为布尔型，可整除为true，可自行测试
if True == true1:
# print(libnum.n2s(int(flag)))
return flag
k += 1
for e1 in range(2,e1e2):
if e1e2%e1==0: #爆破可整除的e
e2=e1e2//e1
c=rsa_gong_N_def(e1, e2, c1, c2, n)
e=gmpy2.gcd(e1,e2)
m1=de(c, e, n)
if m1: #指定输出m1
print(libnum.n2s(int(m1)))
e,m相同，存在两个n有公约数
import gmpy2
from gmpy2 import invert, iroot
import gmpy2 as gp
from libnum import xgcd, invmod
n=[,,,,,,,,,,,,,,,,,,,]
for i in n:
for j in n:
if (i<>j):
pub_p=gmpy2.gcdext(i,j)
if (pub_p[0]<>1)&(i>j):
print i
print j
print pub_p[0]
a=i,p=pub_p[0]
q=a/p
p = gp.mpz()
q = gp.mpz()
e = gp.mpz()
c = gp.mpz()
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(hex(m))
根据enc文件,p,q,e求d和key
import gmpy2
import rsa
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
e = 65537
n = p * q
d = gmpy2.invert(e,(q-1)*(p-1))
print(d)
d = 81176168860169991027846870170527607562179635470395365333547868786951080991441
key = rsa.PrivateKey(n,e,d,p,q)
print(key)
with open("flag.enc","rb") as f:
print(rsa.decrypt(f.read(),key).decode())
根据pem文件解密
RSA public key encryption and decryption
or 用kali跑openssl
e=1
import binascii
import gmpy2
N_hex=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e_hex=0x1
c_hex=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
c_hex = gmpy2.mpz(c_hex)
N_hex = gmpy2.mpz(N_hex)
i = 0
while i<10:
m_hex = hex(c_hex + gmpy2.mpz(hex(i))*N_hex)
print(m_hex[2:])
try:
print(binascii.a2b_hex(m_hex[2:]).decode("utf8"))
except binascii.Error as e:
print("位数非偶数，跳过...")
i += 1
e=2
import gmpy
import string
from Crypto.PublicKey import RSA
# 读取公钥参数
with open('./tmp/pubkey.pem', 'r') as f:
key = RSA.importKey(f)
N = key.n
e = key.e
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
with open('./tmp/flag.enc', 'r') as f:
cipher = f.read().encode('hex')
cipher = string.atoi(cipher, base=16)
# print(cipher)
# 计算yp和yq
yp = gmpy.invert(p,q)
yq = gmpy.invert(q,p)
# 计算mp和mq
mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)
# 计算a,b,c,d
a = (yp * p * mq + yq * q * mp) % N
b = N - int(a)
c = (yp * p * mq - yq * q * mp) % N
d = N - int(c)
for i in (a,b,c,d):
s = '%x' % i
if len(s) % 2 != 0:
s = '0' + s
print(s.decode('hex'))
e=3
import gmpy2
from Crypto.PublicKey import RSA
public_key = "./tmp/pubkey.pem"
cipher_file = "./tmp/flag.enc"
#读入公钥
with open(public_key, "r") as f:
key = RSA.importKey(f)
n = key.n
e = key.e
#读入密文
with open(cipher_file, "r") as f:
cipher = f.read().encode("hex")
cipher = int(cipher, 16)
#print(cipher)
#破解密文
def get_flag():
i = 0
while True:
if(gmpy2.iroot(cipher+i*n, 3)[1] == True):
flag_bin = int(gmpy2.iroot(cipher+x*n, 3)[0])
flag = hex(flag_bin)[2:-1].decode("hex")
print(flag)
break
i += 1
def get_flag_for():
for x in xrange(118600000, 118720000):
if(gmpy2.iroot(cipher+x*n, 3)[1] == 1):
flag_bin = int(gmpy2.iroot(cipher+x*n, 3)[0])
flag = hex(flag_bin)[2:-1].decode("hex")
print(flag)
break
if __name__ == "__main__":
get_flag_for()
#get_flag()
工具
参考文章