cryptography/Wiener.py at main · Lyutoon/cryptography · GitHub

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
from math import isqrt
from libnum import *

def gen_q(a, b):
    r0, r1 = a, b
    q_lst = []
    while r0 % r1 != 0:
        q_lst.append(r0 // r1)
        r0, r1 = r1, r0 % r1
    q_lst.append(r0 // r1)
    return q_lst

def Wiener(n, e):
    q_lst = gen_q(e, n)
    c_lst = [1, q_lst[0]]
    d_lst = [0, 1]
    for i in range(1, len(q_lst)):
        c_lst.append(q_lst[i] * c_lst[i] + c_lst[i-1])
        d_lst.append(q_lst[i] * d_lst[i] + d_lst[i-1])
        pair = (d_lst[i + 1] * e - 1, c_lst[i + 1])
        if pair[1] !=0 and pair[0] % pair[1] == 0:
            phi = pair[0] // pair[1]
            delta = (n-phi+1) ** 2 - 4*n
            if delta >= 0 and isqrt(delta)**2 == delta:
                d = invmod(e, phi)
                assert (e * d - 1) % phi == 0
                print(f"d = {d}")
                return d

e = 1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679
n = 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
c = 1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452
d = Wiener(n, e)