search

jvdsn / crypto-attacks

Python implementations of cryptographic attacks and utilities.
MIT License
935 stars 121 forks source link

how to use "Branch and prune for the case with p, q, and d bits known"? #8

Closed b3yondgui closed 2 years ago

b3yondgui commented 2 years ago

how to use "Branch and prune for the case with p, q, and d bits known"?

jvdsn commented 2 years ago

See https://github.com/jvdsn/crypto-attacks/blob/master/test/test_factorization.py#L46

        # 182 known, 330 unknown.
        p_bits = "?0??0?????01?1??0??0?10?1???1001?1???????0?????1??0??1??1?1??01??01???0?1?????0???0??????0?0???1??010?1?10?????0???0?1?????1?????00???1?10??11?0?11???11?????0?0??0?0??0??1??1???0?????110?100??1?1?????????1????0?1?11?0????1?0????1?1?100???1?00??0111??1???1?00????1??1?????000??110?0???0?1?1???110?01????0??0???0?1?1???00?1?10?11??????1??1?01???0??????11?100?1?1100??001????1110?1?????????????0??1??0???1??000?????0?1?1?0??00???????0???111???10?1?0?0??????0?????0??0???????11?????????1??1??0?????0??1????0??1??0??1"
        # 182 known, 330 unknown.
        q_bits = "???0????0?????0???????1??????01?1??00???10??1????0?????1?1???0??0???0?????10??????????11???1???0???0?0?1??1????0??0?0????0???????0???1???0?1???0??000?0?????1101?01??1011???0??1???0?0??0??????0?10??0?01??1?101?????????0??0??1???100?????011???????00????0010?????????1?1???01?111??1?1???1??10???????????0?01?????????????00?????0?0??1?0?110?000111?0?0????0??????10???????0??1????00??1?11???101????01110??1?1?0??????1?0???0?0?110?01???010?01?01??1???1???1??1?0??10?11?011??????1011??110????10?1???10????1?00?0?01?1?0?"
        # 364 known, 660 unknown.
        d_bits = "0???1?1?0?????????0?????0??????1???110????1101???0?00??10????0?1??00???1?1????1?0?0?1?111??1100?0???1?0?1?1????11??1???????0100????0?0??0?1????0??0?0??????0??0?0??0??010?0110??1????????0??10???00??1??0?1?10??0???1??????0?00??????1???????1??1?11?????1????????1??1?01?????011????111?????10?11?1???00?1??11?1??11?0?10??1???0???0?10???????????0???1??00???0???11???0?????0?101000?10??0?1?1????0????001???0?0??????????10?11??????0100??01?1?1100?1???0??1??01????000????????110??????1000???1?01?1?11?????0?00????10?01??0?0??11?00?0??0?00?10??01??0??0????0??10?????11???0???11??1???1?1?0?????00????1???001??????100?0????1??1?0?0?0??????1?0???0?1?00??1?????1???0?1001?????0?????0??1??0?0???10?????0???1?1???0????111?????0??????0?0?1101???0??????????????1???00?????0????1??????1?00??0??101?1???111?1000?0???0???0??11?1?1?1???????1?1???0?1??????1??0??1????01??????0?????????1????1???01???1????00??0?0???1?0?1?????0??????1???0?1?10??0?01??0?000?????0??????0???0????11???1????01?1?11??10?1???0?????0100?10?111?0?0?10??1?01????0????0????01"
        p_, q_ = branch_and_prune.factorize_pqd(N, e, PartialInteger.from_bits_be(p_bits), PartialInteger.from_bits_be(q_bits), PartialInteger.from_bits_be(d_bits))
        self.assertIsInstance(p_, int)
        self.assertIsInstance(q_, int)
        self.assertEqual(N, p_ * q_)