Extended Euclidean Algorithm to find modular inverse
(a: i64, m: i64)
| 26 | |
| 27 | // Extended Euclidean Algorithm to find modular inverse |
| 28 | fn mod_inv(a: i64, m: i64) -> i64 { |
| 29 | let (mut m0, mut x0, mut x1) = (m, 0, 1); |
| 30 | let mut a = a; |
| 31 | |
| 32 | while a > 1 { |
| 33 | let q = a / m0; |
| 34 | let t = m0; |
| 35 | m0 = a % m0; |
| 36 | a = t; |
| 37 | let t = x0; |
| 38 | x0 = x1 - q * x0; |
| 39 | x1 = t; |
| 40 | } |
| 41 | |
| 42 | if x1 < 0 { |
| 43 | x1 += m; |
| 44 | } |
| 45 | |
| 46 | x1 |
| 47 | } |
| 48 | |
| 49 | // RSA key generation (with hardcoded small primes for simplicity) |
| 50 | fn generate_keys() -> (PublicKey, PrivateKey) { |