题目名称:BrokenSystems
题目内容:Successfully modified the encryption module of the encryption system, and then it's up to you.
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open("public.key","w")
f.write(public_key.decode())
f.close()
rsakey=RSA.importKey(open("public.key","r").read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open("message","wb")
f.write(msg)
f.close()
题目给出了public.key和message
1.读public.key
RSA常见解题思路及技巧
在线公钥解析网站
from Crypto.PublicKey import RSA
public = RSA.importKey(open('public.key').read())
n = long(public.n)
e = long(public.e)
print(n)
#n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
print(e)
#e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
2.求d
e特别大,需要使用维纳攻击,在这里我套用了脚本
import gmpy2
def transform(x, y): # 使用辗转相处将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return denominator, numerator # 得到渐进分数的分母和分子,并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res))))) # 将连分数的结果逐一截取以求渐进分数
return res
def get_pq(a, b, c): # 由p+q和pq的值通过维达定理来求解p和q
par = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得,开根号一定是整数,因为有解
x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1, x2
def wienerAttack(e, n):
for (d, k) in sub_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数,直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况,排除
continue
if (e * d - 1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的话,(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue
phi = (e * d - 1) // k # 这个结果就是 φ(n)
px, qy = get_pq(1, n - phi + 1, n)
if px * qy == n:
p, q = abs(int(px)), abs(int(qy)) # 可能会得到两个负数,负负得正未尝不会出现
d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求ed=1 (mod φ(n))的结果,也就是e关于 φ(n)的乘法逆元d
return d
print("该方法不适用")
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
d = wienerAttack(e, n)
print("d=", d)
3.分解n
from gmpy2 import *
import random
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727
def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1 :
k = d*e - 1
g = random.randint(0,n)
while p ==1 and q==1 and k%2 == 0:
k =k // 2
x = pow(g,k,n)
if x!=1 and gcd(x-1,n)>1:
p = gcd(x-1,n)
q = n//p
return (p,q)
p,q = getpq(n,e,d)
print("p:",p)
print("q:",q)
4.求m (需要使用PKCS1_OAEP填充规则进行解密)
from Crypto.PublicKey import RSA
rsakey = RSA.importKey(open("public.key", "r").read())
privatekey = RSA.construct((n,e,d,p,q))
rsa = PKCS1_OAEP.new(privatekey)
m = rsa.decrypt(open("message", "rb").read())
print(m)
文章评论