这次参加国赛初赛，密码题只会这一道套路题，rsa的大数分解n分解不出来，lsfr的脚本写不出来，还是要继续努力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p-1) * (q-1)
while True:
    d = getRandomNBitInteger(200)
    if GCD(d, phi) == 1:
        e = inverse(d, phi)
        break
c = pow(m, e, N)
print(c, e, N, sep='\n')
#37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
#46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
#86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289

很显然，我们看到e非常的大，我们可以采用低解密指数攻击（Wiener Attack）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# -*- coding: utf-8 -*-
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 = 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
n = 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
d=wienerAttack(e,n)
print("d=",d)