我已经实现了 RSA 算法的一个非常基本的 Rust 实现。一切似乎都很好，但我在测试中发现加密/解密过程有一个奇怪的行为。因为它工作了 3/4 次，这真的很奇怪..
图书馆可以在这里找到:https://github.com/CPerezz/rust-rsa
代码如下:
math.rs(每个函数都经过测试通过)
//! Math functions to build keys with trusted primes
use std::str::FromStr;
use rand::Rng;
use num_bigint::{ToBigUint, BigUint, RandBigInt, BigInt, Sign};
use num::{Zero, One, Integer, FromPrimitive};
use crate::helpers::generics::*;
// Generates a big number of lenght = u32 param.
pub fn gen_big_num(bit_len: &u32) -> BigUint {
// RNG depends on rng_core crate.
let mut rng = rand::thread_rng();
let mut a = rng.gen_biguint(bit_len.to_owned() as usize);
a
}
// Given lenght, generates a prime number of that lenght approximately.
// That prime number is prime with probability = 4^-threshold
pub fn gen_big_prime(size: &u32, threshold: u32) -> BigUint {
let mut proposal = gen_big_num(size);
// Remove all even numbers to reduce the iterations a half.
if proposal.is_even() {
proposal = proposal + BigUint::one();
}
while !is_prime(&proposal, threshold) {
// Steps of 2 to avoid the even numbers on the iterations.
proposal = proposal + 2.to_biguint().unwrap();
}
proposal
}
// Posible to remove and implement it on gen big prime
// Given a prime proposal, compute Rabin Miller's algorithm.
fn is_prime(proposal: &BigUint, threshold: u32) -> bool {
if !rabin_miller(proposal, threshold) {return false}
true
}
// Rabin-Miller is a probabilistic algorithm that checks if a number is prime based on Riemmann's conjecture.
// Implemented from psoudocode found on: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Primality_Testing
// The function recieves a prime proposal and the threshold probability of a false positive
// due to composite numbers reported as primes.
// The pobability of a false positive is 4^-threshold. With t=9 => P(false_positive) = 3/1_000_000
fn rabin_miller(proposal: &BigUint, t: u32) -> bool {
// Needed constants
let (z, o, tw) = gen_basic_biguints();
let (zero, one, two) = (&z, &o, &tw);
// If proposal <= 1 Rabin-Miller has to fail.
if proposal.clone() <= one.to_owned() {return false};
// If proposal != 2 and modulus 2 = 0, Rabin-Miller fails.
if proposal.clone() != two.to_owned() && proposal.clone() % two == zero.to_owned() {return false};
// Getting exp to execute mulmod.
let (s,d) = refactor(proposal);
let mut counter = 0;
while counter < t {
// Gen rand biguint from a range (2, proposal-2)
let mut rng = rand::thread_rng();
let a = rng.gen_biguint_range(&two , &(proposal - two) );
let mut x = mod_exp_pow(&a, &d, proposal);
if x != one.to_owned() && x != proposal.to_owned() - one {
let mut i = zero.clone();
loop {
x = mod_exp_pow(&x, &two, proposal);
if x == proposal.to_owned() - one {break;}
if x == one.to_owned() || i >= s.clone()- one{return false;};
i = i.clone() + one;
}
}
counter +=2;
}
true
}
// Modular exponentiation implemented on binary exponentiation (squaring)
pub fn mod_exp_pow(base: &BigUint, exp: &BigUint, md: &BigUint) -> BigUint {
let mut res = BigUint::one();
let (zero, one, _) = gen_basic_biguints();
let (mut base, mut exponent) = (base.clone(), exp.clone());
while exponent > zero {
if exponent.clone() & one.clone() > zero {
res = (res * base.clone()) % md;
}
// Shifting 1 bit of the exponent as a binary number.
exponent >>= 1;
// Generating next base by squaring
base = (base.clone() * base.clone()) % md;
}
res
}
// Given a number n, write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
fn refactor(n: &BigUint) -> (BigUint, BigUint) {
let (mut s, one, two) = gen_basic_biguints();
let mut d = n.clone() - one.clone();
while d.is_even() {
d = d / two.clone();
s = s + one.clone();
}
(s, d)
}
// Extended Euclidean Algorithm
// Returns gcd(a,b) and Bézout's identity coefficients
// ax + by = gcd(a,b)
pub fn egcd<'a>(a: &'a mut BigInt, b: &'a mut BigInt) -> (BigInt, BigInt, BigInt) {
// base case
if a.to_owned() == BigInt::from(0 as u32) {
(b.clone(), BigInt::from(0 as i32), BigInt::from(1 as i32))
} else {
let mut b_mod_a = b.clone() % a.clone();
let ref_b_mod_a = &mut b_mod_a;
let (g, x, y) = egcd(ref_b_mod_a, a);
let mut b_div_a = b.clone() / a.clone();
let ref_b_div_a = &mut b_div_a;
(g, (y - ref_b_div_a.clone() * x.clone()), x)
}
}
// Given a fi_n, find on the interval (fi_n/2, fi_n) a number
// that is co-prime with fi_n
pub fn found_e(fi_n: &BigUint) -> Result<BigUint, bool> {
// Gen random number on interval
let mut rng = rand::thread_rng();
//Get fi_n as
let sign = Sign::Plus;
let mut fi_n = BigInt::from_biguint(sign, fi_n.clone());
let (zero, one, two) = gen_basic_bigints();
let mut a = rng.gen_bigint_range(&(fi_n.clone()/two.clone()) , &((BigInt::from(3) * fi_n.clone())/BigInt::from(4) ));
//We want to avoid the even random numbers.
if a.is_even() {a = a + one.clone()};
let mut res = zero;
while res != one.clone() && a <= fi_n.clone() - one.clone() {
let (res2, _, _) = egcd(&mut fi_n, &mut a);
res = res2;
a = a.clone() + two.clone();
}
if res == one {
a = a.clone() - two.clone();
return Ok(biguint_from_bigint(&a));
}
Err(false)
}
#[test]
fn generates_random_biguint() {
let a = gen_big_num(&1024);
assert_ne!(a, BigUint::zero());
}
#[test]
fn mod_exp_works() {
let res = mod_exp_pow(&BigUint::from(4 as u32), &BigUint::from(13 as u32), &BigUint::from(497 as u32));
assert_eq!(res, BigUint::from(445 as u32));
let res2 = mod_exp_pow(&BigUint::from(5 as u32), &BigUint::from(3 as u32), &BigUint::from(13 as u32));
assert_eq!(res2, BigUint::from(8 as u32));
}
#[test]
fn rabin_miller_works() {
//Small primes
let res = rabin_miller(&179425357u32.to_biguint().unwrap(), 9);
assert_eq!(res, true);
let res2 = rabin_miller(&82589933u32.to_biguint().unwrap(), 64);
assert_eq!(res2, true);
// Big primes
let known_prime_str =
"118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
let known_prime: BigUint = FromStr::from_str(known_prime_str).unwrap();
assert!(rabin_miller(&known_prime, 64));
}
#[test]
fn gen_big_prime_works() {
let res = gen_big_prime(&2056u32, 9);
println!("The generated prime of 1024 bits is: {}", res);
}
#[test]
fn egcd_test() {
use num_bigint::ToBigInt;
use std::str::FromStr;
// small primes
let a = &mut 179425357u32.to_bigint().unwrap();
let b = &mut 97u32.to_bigint().unwrap();
let (g, x, y) = egcd(a, b);
assert_eq!(a.clone()*x + b.clone()*y, g);
// small primes
let a = &mut 1024u32.to_bigint().unwrap();
let b = &mut 512u32.to_bigint().unwrap();
let (g, x, y) = egcd(a, b);
assert_eq!(512u32.to_bigint().unwrap(), g);
// big primes
let known_prime_str = "118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
let known_prime_str_2 = "357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997";
let mut a: BigInt = FromStr::from_str(known_prime_str).unwrap();
let mut b: BigInt = FromStr::from_str(known_prime_str_2).unwrap();
let a_r = &mut a;
let b_r = &mut b;
let (g, x, y) = egcd(a_r, b_r);
assert_eq!(a_r.clone()*x + b_r.clone()*y, g);
}
这里是进行加密和解密的类型:
use num_bigint::{BigUint, BigInt, ToBigInt, Sign};
use crate::helpers::math::*;
use crate::helpers::generics::*;
use num::{Signed, One};
use std::fmt;
use std::ops::Neg;
use std::str::{FromStr, from_utf8};
#[derive(Clone, PartialEq)]
pub struct KeyPair {
pub pk: PublicKey,
pub sk: SecretKey,
pub size: u32,
pub threshold: u32
}
#[derive(Clone, PartialEq)]
pub struct PublicKey {
n: BigUint,
e: BigUint
}
#[derive(Clone, PartialEq)]
pub struct SecretKey {
n: BigUint,
d: BigUint
}
#[derive(Clone, Copy, PartialEq)]
pub struct Threshold {
value: u32
}
impl Threshold {
// Creates a Threshold with a default error probability of generating a prime of 4^-64
pub fn default() -> Self {
let threshold = Threshold {
value: 9 as u32
};
threshold
}
// Creates a Threshold with a selected value as thresholf of P(err). P(err prime) = 4^-threshold.
pub fn new(th: &u32) -> Self {
let th = Threshold {
value: *th
};
th
}
// Gets the value of a Threshold and returns it as u32.
pub fn value(th: Self) -> u32 {
th.value
}
}
// Implementation of Display for KeyPair Struct.
impl fmt::Display for KeyPair {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "\nPublic Key: \n{}\nSecret Key: \n{}\nSize: {}\nThreshold: {} which gives a P(err_primes_gen) = 4^(-{})", self.pk, self.sk, self.size, self.threshold, self.threshold)
}
}
impl KeyPair {
// Generate a new KeyPair Struct from scratch by giving the size of the key desired (in bits) and the threshold of P(err) while assuming that
// a number is prime. Statistic methods are used to found that numbers. P(err) = 4^-threshold (As is demonstraded on the Rabin-Miller algorithm)
pub fn new(size: &u32, threshold: &Threshold) -> Result<Self, &'static str> {
// Gen basic needed variables
let (_, one, _) = gen_basic_biguints();
// Gen p q primal base
let p = gen_big_prime(size, threshold.value);
let q = gen_big_prime(size, threshold.value);
// Gen n and fi_n
let n = &p * &q;
let fi_n = (&p - &one) * (&q - &one);
// Find a positive integer minor than fi_n , co-prime with fi_n
let e = found_e(&fi_n).unwrap();
// Building Pk Struct
let pk = PublicKey::new(&n, &e).unwrap();
// Finding d and building Secret Key Struct
let (_, _,mut d) = egcd(&mut fi_n.to_bigint().unwrap(), &mut e.to_bigint().unwrap());
if d.is_negative() {
d = d.neg();
}
let sk = SecretKey::new(&n, &biguint_from_bigint(&d)).unwrap();
//Building KeyPair struct
let kp = KeyPair {
pk: pk,
sk: sk,
size: size.to_owned(),
threshold: threshold.value.to_owned()
};
// Return the KeyPair struct
Ok(kp)
}
}
// Implementation of Display for KeyPair Struct.
impl fmt::Display for PublicKey {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "n: {}\ne: {}", self.n, self.e)
}
}
impl PublicKey {
// Generate a PublicKey struct from n and d co-prime factors.
fn new(_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
Ok(PublicKey {
n: _n.to_owned(),
e: _e.to_owned()
})
}
// Generate a PublicKey struct from n, fi_n and d params with the co-prime property checking.
fn new_from_fi_n_e(_n: &BigUint, _fi_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
let (_, _one, _) = gen_basic_bigints();
match egcd(&mut BigInt::from_biguint(Sign::Plus, _fi_n.to_owned()), &mut BigInt::from_biguint(Sign::Plus, _e.to_owned())) {
(possible_one, _, _) => {
if possible_one.is_one() {
return Ok(PublicKey {
n: _n.to_owned(),
e: _e.to_owned()
}
)
}else {
return Err("Params passed to Sk builder haven't the properties to be a Public Key")
}
}
}
}
// Encrypts the data passed on the params.
fn encrypt(&self, msg: &str) -> Result<&str, &'static str> {
if !msg.is_ascii(){
return Err("Message isn't ASCII like. Please remove non-ASCII characters.")
}else{
println!("Message as bytes: {:?}", msg.as_bytes());
let res = BigUint::from_bytes_be(msg.as_bytes());
println!("COPRIMES IF ONE ---->> {:?}", egcd(&mut BigInt::from_biguint(Sign::Plus, res.clone()), &mut BigInt::from_biguint(Sign::Plus, self.n.clone())).0);
Ok(string_to_static_str(format!("{}", mod_exp_pow(&res, &self.e, &self.n))))
}
}
}
// Implementation of Display for KeyPair Struct.
impl fmt::Display for SecretKey {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "n: {}\nd: {}", self.n, self.d)
}
}
impl SecretKey {
// Generate a SecretKey struct from n and d co-prime factors.
fn new(_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
Ok(SecretKey {
n: _n.to_owned(),
d: _e.to_owned()
})
}
// Generate a SecretKey struct from n, fi_n and d params with the co-prime property checking.
pub fn new_from_fi_n_e(_n: &BigUint, _fi_n: &BigUint, _d: &BigUint) -> Result<Self, &'static str> {
let (_, _one, _) = gen_basic_bigints();
match egcd(&mut BigInt::from_biguint(Sign::Plus, _fi_n.to_owned()), &mut BigInt::from_biguint(Sign::Plus, _d.to_owned())) {
(possible_one, _, _) => {
if possible_one.is_one() {
return Ok(SecretKey {
n: _n.to_owned(),
d: _d.to_owned()
}
)
}else {
return Err("Params passed to Sk builder haven't the properties to be a Public Key")
}
}
}
}
// Decrypts the cyphertext giving back an &str
fn decrypt(&self, text: &str) -> Result<&str, &'static str> {
let c = BigUint::from_str(text).unwrap();
let result_as_bytes = mod_exp_pow(&c, &self.d, &self.n).to_bytes_be();
println!("C as bytes: {:?}", result_as_bytes);
let res_decrypt = std::str::from_utf8(&result_as_bytes).unwrap();
Ok(string_to_static_str(format!("{}", res_decrypt)))
}
}
问题是当我运行测试时:
#[test]
fn encrypts_decrypts_info(){
let kp = KeyPair::new(&512u32, &Threshold::new(&10)).unwrap();
let msg = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum";
let cyphertext = kp.pk.encrypt(msg).unwrap();
let res_decrypt = kp.sk.decrypt(&cyphertext).unwrap();
println!("Result of decryption is: {}", res_decrypt);
assert_eq!(res_decrypt, "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum")
}
当测试出现错误时，我得到这个:
running 1 test
Message as bytes: [76, 111, 114, 101, 109, 32, 105, 112, 115, 117, 109, 32, 100, 111, 108, 111, 114, 32, 115, 105, 116, 32, 97, 109, 101, 116, 44, 32, 99, 111, 110, 115, 101, 99, 116, 101, 116, 117, 114, 32, 97, 100, 105, 112, 105, 115, 99, 105, 110, 103, 32, 101, 108, 105, 116, 46, 32, 80, 114, 97, 101, 115, 101, 110, 116, 32, 110, 111, 110, 32, 110, 117, 110, 99, 32, 101, 116, 32, 105, 112, 115, 117, 109, 32, 116, 101, 109, 112, 117, 115, 32, 102, 101, 114, 109, 101, 110, 116, 117, 109]
COPRIMES IF ONE ---->> BigInt { sign: Plus, data: BigUint { data: [1] } }
C as bytes: [61, 207, 34, 84, 216, 183, 90, 189, 50, 169, 219, 109, 65, 100, 222, 105, 115, 8, 229, 173, 114, 40, 162, 83, 121, 184, 99, 167, 157, 98, 165, 91, 226, 140, 203, 84, 185, 161, 137, 201, 231, 132, 35, 112, 96, 89, 32, 253, 249, 175, 57, 133, 235, 65, 230, 250, 50, 142, 54, 70, 123, 203, 51, 145, 82, 129, 249, 79, 236, 30, 107, 210, 49, 139, 232, 69, 248, 48, 108, 215, 234, 223, 51, 88, 64, 223, 218, 54, 117, 137, 136, 226, 166, 144, 96, 111, 203, 239, 121, 129, 158, 21, 191, 227, 119, 79, 109, 124, 103, 204, 243, 143, 86, 60, 19, 162, 247, 253, 96, 150, 49, 134, 41, 94, 58, 122, 89, 44]
thread 'types::encrypts_decrypts_info' panicked at 'called `Result::unwrap()` on an `Err` value: Utf8Error { valid_up_to: 1, error_len: Some(1) }', src/libcore/result.rs:1009:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
1: std::sys_common::backtrace::_print
at src/libstd/sys_common/backtrace.rs:71
2: std::panicking::default_hook::{{closure}}
at src/libstd/sys_common/backtrace.rs:59
at src/libstd/panicking.rs:211
3: std::panicking::default_hook
at src/libstd/panicking.rs:227
4: std::panicking::rust_panic_with_hook
at src/libstd/panicking.rs:491
5: std::panicking::continue_panic_fmt
at src/libstd/panicking.rs:398
6: rust_begin_unwind
at src/libstd/panicking.rs:325
7: core::panicking::panic_fmt
at src/libcore/panicking.rs:95
8: core::result::unwrap_failed
at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/macros.rs:26
9: <core::result::Result<T, E>>::unwrap
at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/result.rs:808
10: rsa_rust::types::SecretKey::decrypt
at src/types.rs:191
11: rsa_rust::types::encrypts_decrypts_info
at src/types.rs:217
12: rsa_rust::types::encrypts_decrypts_info::{{closure}}
at src/types.rs:211
13: core::ops::function::FnOnce::call_once
at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/ops/function.rs:238
14: <F as alloc::boxed::FnBox<A>>::call_box
at src/libtest/lib.rs:1471
at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/ops/function.rs:238
at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/liballoc/boxed.rs:673
15: __rust_maybe_catch_panic
at src/libpanic_unwind/lib.rs:102
test types::encrypts_decrypts_info ... FAILED
所以在这一点上，如果错误来自错误的 key 生成或错误的字节编码/解码过程，请判断错误。
感谢您的宝贵时间。
最佳答案
错误消息意味着解密的缓冲区(您的跟踪中的“C as bytes”)不是有效的 UTF-8，因此 str::from_utf8 失败。如果我正确理解您的代码，“C as bytes”应该与“Message as bytes”相同，因为我不认为您的加密或解密代码中存在错误，但我不能告诉您是哪个。
关于algorithm - 具有奇怪行为的 Rust RSA 实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54814343/