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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| import gmpy2
def continuedFra(x, y):
"""计算连分数
:param x: 分子
:param y: 分母
:return: 连分数列表
"""
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
"""计算传入列表最后的渐进分数
:param cf: 连分数列表
:return: 该列表最后的渐近分数
"""
numerator = 0
denominator = 1
for x in cf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
"""使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
:param a:x^2的系数
:param b:x的系数
:param c:pq
:return:p，q
"""
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
"""计算列表所有的渐近分数
:param cf: 连分数列表
:return: 该列表所有的渐近分数
"""
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
"""
:param e:
:param n:
:return: 私钥d
"""
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
e = 4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
pq = 78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053
n = pq**2
d=wienerAttack(e, n)
import random
from hashlib import md5
import libnum
def factor_with_ed(e,d,n):
p=1
q=1
while p==1 and q==1:
k = e*d -1
g = random.randint(1,n)
while k%2==0:
k //= 2
x = pow(g,k,n)
if x>1 and libnum.gcd(x-1,n)>1:
p = libnum.gcd(x-1,n)
q = n//p
return p,q
n = 78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053
e = 4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
p,q = factor_with_ed(e,d,n)
flag = "qsnctf{" + md5(str(p + q).encode()).hexdigest() + "}"
print(flag)
|
