ferogram_crypto/
factorize.rs

1// Copyright (c) Ankit Chaubey <ankitchaubey.dev@gmail.com>
2// SPDX-License-Identifier: MIT OR Apache-2.0
3//
4// ferogram: async Telegram MTProto client in Rust
5// https://github.com/ankit-chaubey/ferogram
6//
7// Based on layer: https://github.com/ankit-chaubey/layer
8// Follows official Telegram client behaviour (tdesktop, TDLib).
9//
10// If you use or modify this code, keep this notice at the top of your file
11// and include the LICENSE-MIT or LICENSE-APACHE file from this repository:
12// https://github.com/ankit-chaubey/ferogram
13
14//! Pollard-rho (Brent variant) integer factorization: used for PQ step.
15
16fn gcd(mut a: u128, mut b: u128) -> u128 {
17    while b != 0 {
18        let t = b;
19        b = a % b;
20        a = t;
21    }
22    a
23}
24
25fn modpow(mut n: u128, mut e: u128, m: u128) -> u128 {
26    if m == 1 {
27        return 0;
28    }
29    let mut result = 1;
30    n %= m;
31    while e > 0 {
32        if e & 1 == 1 {
33            result = result * n % m;
34        }
35        e >>= 1;
36        n = n * n % m;
37    }
38    result
39}
40
41fn abs_sub(a: u128, b: u128) -> u128 {
42    a.max(b) - a.min(b)
43}
44
45fn factorize_with(pq: u128, c: u128) -> (u64, u64) {
46    if pq.is_multiple_of(2) {
47        return (2, (pq / 2) as u64);
48    }
49
50    let mut y = 3 * (pq / 7);
51    let m = 7 * (pq / 13);
52    let mut g = 1u128;
53    let mut r = 1u128;
54    let mut q = 1u128;
55    let mut x = 0u128;
56    let mut ys = 0u128;
57
58    while g == 1 {
59        x = y;
60        for _ in 0..r {
61            y = (modpow(y, 2, pq) + c) % pq;
62        }
63        let mut k = 0;
64        while k < r && g == 1 {
65            ys = y;
66            for _ in 0..m.min(r - k) {
67                y = (modpow(y, 2, pq) + c) % pq;
68                q = q * abs_sub(x, y) % pq;
69            }
70            g = gcd(q, pq);
71            k += m;
72        }
73        r *= 2;
74    }
75
76    if g == pq {
77        loop {
78            ys = (modpow(ys, 2, pq) + c) % pq;
79            g = gcd(abs_sub(x, ys), pq);
80            if g > 1 {
81                break;
82            }
83        }
84    }
85
86    let p = g as u64;
87    let q = (pq / g) as u64;
88    (p.min(q), p.max(q))
89}
90
91/// Factorize `pq` into two prime factors `(p, q)` where `p ≤ q`.
92pub fn factorize(pq: u64) -> (u64, u64) {
93    let n = pq as u128;
94    for attempt in [43u128, 47, 53, 59, 61] {
95        let c = attempt * (n / 103);
96        let (p, q) = factorize_with(n, c);
97        if p != 1 {
98            return (p, q);
99        }
100    }
101    panic!("factorize failed after fixed attempts");
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107    #[test]
108    fn t1() {
109        assert_eq!(factorize(1470626929934143021), (1206429347, 1218991343));
110    }
111    #[test]
112    fn t2() {
113        assert_eq!(factorize(2363612107535801713), (1518968219, 1556064227));
114    }
115}
ferogram_crypto/factorize.rs

ferogram_crypto/
factorize.rs
