RSA Key Recovery

rsa.py

#!/usr/bin/env python3
p0 = int("""
908184469103574984795932265928358354638054796
66217317017699423700239659749759815002441863307634
99150890684320005999042526897004097380363781161708
80775006330512846700651037295237503225333489046629
82319494212743792747685757003399230261027519567689
38470257948129097699067032084002260996647823433544
0662981624111
""".replace("\n", ""))

q0 = int("""
135044955989092961396943348486953259213974756
34214374784133985504852983427793079334803888550077
57589668353488262875993517263552193008567235060251
99675288038760308572499990382097482214099733260624
07376756400703388129499110708588815825136005901591
32526681110769656895334181363863449279991251070375
09005787966171
""".replace("\n", ""))

n = int("""
1226457322682747124246324615249853197057234789
94214972832512400539086450534379092938315506057875
93277692058409582628623271406215920183514666777222
12567022250308250047333103693832502106159391093667
16586399569402936040420537816633679194443170816852
06963925232328953423349970739168169969366563115021
93566126650535580289714963151184253515379094166410
13783165371553570901071015078627063573221736384892
58881986235220166369251019495576340719704025700350
54583251438970178259844585479535186512167412125823
81940545729109354284080505807182994993833975529558
16959629924188838627973112767813949614808272827956
642744187979107282933
""".replace("\n", ""))

k = 2048

#p0 = 9
#q0 = 3
#n = 143
#k = 8

def main():
    candidates = set([(p0, q0)])

    for i in range(1, k):
        for candidate in candidates.copy():
            (p, q) = candidate
            mod = 2**i
            x = n % mod
            y = (p*q) % mod

            if x != y:
                bit = 2**(i-1)
                is_p_unset = (p & bit) >> i != 1
                is_q_unset = (q & bit) >> i != 1
                if is_p_unset:
                    next_candidate = ((p | bit), q)
                    candidates.add(next_candidate)
                if is_q_unset:
                    next_candidate = (p, (q | bit))
                    candidates.add(next_candidate)
                if is_p_unset and is_q_unset:
                    next_candidate = ((p | bit), (q | bit))
                    candidates.add(next_candidate)
                candidates.remove(candidate)
    print('{}'.format(candidates))

main()