Python's library written in Rust to quickly factor n = pq when around >50% bits of p and q are known which are distributed at random. Used mainly for CTF challenges, especially about RSA.
>>> import factor >>> factor.from_str(91, "110_", "0__1") (13, 7) >>> factor.from_vector(91, [1, 1, 0, -1], [0, -1, -1, 1]) (13, 7) >>> n = 104158954646372695568095796310479805403678314919693272509836778997179683485437763692891984254171869987446475357518587344178264028334102088429629785065036660148146855007349113784322098795994839040721664806905084554147298456659074384855277678993200563966327086005547016327991986225930798076081014377904788085807 >>> p_bits_str = "1010101111000___11000___11100___11010___0___0___0___100110000___0___0___0___11000___0___0___110110010___11001100100111010___100011000___0___0___0___11111000111111100___1101110010000___0___0___0___10110___0___0___0___0___0___1100101111000___0___1001111011110___0___10000___0___0___11010___1010101110110___0___0___0___0___10010___1011101011100___110111010___0___0___0___101010110___0___10000___1000101011000___0___0___0___101010000___11010___111010000___0___11110___0___10010___111010010___0___0___10100___0___0___" >>> q_bits_str = "110111010___111011110___0___1000100110001110100111100___0___10110___11000___0___10110___11100___10000___0___0___11111100110010100___10000___11100___0___110010110___101110010___10010___11110___11110___0___1101111011000___101010110___10100___0___10100___1010101011010___0___0___100110110___0___10000___0___0___1000101110010___1111110010110___0___0___0___101110100___0___1100101111000___10100___0___0___0___0___0___0___10010___0___0___10100___10010___0___0___0___101011110___0___111110000___0___11110___0___10100___" >>> p_q = factor.from_str(n, p_bits_str, q_bits_str) >>> assert p_q is not None >>> p, q = p_q >>> assert p * q == nIn addition, of course, this can be used in Rust program. See examples/factor_cui.rs.
$ cargo run --release --example factor_cui 3233 1_0__1 1___01 53, 61# If you have not yet installed Rust, run command below $ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh # Install as a Python package $ pip install -r requirements.txt $ python setup.py installYou can also use a docker environment.
$ docker run -it --rm y011d4/factor-from-random-known-bits:0.1.0 Python 3.9.6 (default, Jun 29 2021, 19:27:32) [GCC 8.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>>There are some examples in examples directory.
- "This is RSA" in SECCON CTF 2020
- "regulus-calendula" in HSCTF 8
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.