西湖论剑2020-BrokenSystems

可爱桃子的博客

题目名称：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)