defcontinuedFra(x, y): """计算连分数 :param x: 分子 :param y: 分母 :return: 连分数列表 """ cf = [] while y: cf.append(x // y) x, y = y, x % y return cf defgradualFra(cf): """计算传入列表最后的渐进分数 :param cf: 连分数列表 :return: 该列表最后的渐近分数 """ numerator = 0 denominator = 1 for x in cf[::-1]: # 这里的渐进分数分子分母要分开 numerator, denominator = denominator, x * denominator + numerator return numerator, denominator defsolve_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) defgetGradualFra(cf): """计算列表所有的渐近分数 :param cf: 连分数列表 :return: 该列表所有的渐近分数 """ gf = [] for i inrange(1, len(cf) + 1): gf.append(gradualFra(cf[:i])) return gf
defwienerAttack(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
n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497 e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705 c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380 d=wienerAttack(e, n) m=pow(c, d, n) print(libnum.n2s(m).decode()) #DASCTF{e694f0b4e9556021d1bc9e8deedba575}