一文读懂RSA
一文读懂RSA
本文来聊聊RSA, 这是一个非对称密码，和之前所提到的AES与DES不同的是，这个加密方式有两个密钥，一个是公钥，一个是私钥，公钥用来加密，私钥用来解密。相比于对称密码，非对称密码大多基于某个数学难题，比如接下来要谈论的RSA即基于大整数分解的困难性来的，因此为了说明白这个加密算法，首先要先补充"一"点点数学知识。
数学基础
RSA用到的数学知识还是比较少的，基本上只是小学学过的一些关于整数的一些知识，相信看到这里的读者应该都能理解，在这里我不打算去讲过多的证明，只是说一些结论，想看证明的大佬，可以去参考文章后面参考资料里面的书籍。
素数
素数，也就是除了1和它本身，没有其他的约数的数字，我当时学的时候，一直都是叫的素数，也有叫质数的，我还是沿用我之前的习惯，叫素数了，有不同叫法的注意一下，说的是一个东西。
算数基本定理
对于任意的整数(n > 1)，都可以唯一的分解为:
其中均为素数，这个定理比较好理解，任何一个合数都可以被分解成为若干个素数的乘积，这个小学的因式分解应该就讲过。
费马小定理
如果p是素数，a是正整数并且不能被p整除，则:
费马小定理还有一种表示形式，若p为素数，并且a为任意正整数，则:
欧拉函数()
这个函数表示小于n并且与n互素的元素的个数，特别的我们定义。
在RSA当中，我们用到了下面一个关系式，对于素数p来说显然有:
假设有两个素数p和q，则有:
欧拉定理
对于任意互素的两个数a和n, 有:
同费马小定理一样，还有另一种表示形式:
同样，这里也不要求a和n互素。
到这里，所用到的数学知识就都介绍完了，是不是发现并不多，而且大多都比较好理解。
RSA算法描述
RSA是基于大整数分解这个困难问题的，为什么说这是一个困难问题呢，比如我现在给出一个数字3220479853, 我说这是两个素数的乘积，如果要找出这两个素数，相信如果不用计算器，纯靠笔算的话估计一时半会也不会算出来吧,当然要是有超级大脑哪种水平，有可能能直接看出结果，这种情况除外，但是如果计算这个106649*30197这个值相信各位读者用笔稍稍计算一会就可以得出结果了，对于计算机来说，如果n足够大(2048bit)的话，基本也不太可能在有效时间能计算出结果，当然这里我说的是有效时间，而不是绝对算不出来，如果算力无限或者时间无限的的话，这是肯定能计算出来的，实际显然不会是时间无限或者算力无限，啰嗦了这么久，下面进入正题了，来聊聊RSA具体是怎么运作的。
- 第一步: 选取两个大素数p和q
- 第二步: 计算这两个素数的乘积
- 第三步: 计算
- 第四步: 选取e, 并且满足和
- 第五步: 计算
- 第六步: 公开(e, n)作为公钥，保密(d, p, q)作为私钥。
- 第七步: 加密过程, 计算
- 第八步: 解密过程, 计算
注意，为了安全，n要取2048bit大小的数字，从上面可以看出，如果M的长度大于n, 则会丢失一部分明文信息，因此RAS加密信息的长度和密钥长度相关，并且由于这里做了模幂运算，因此性能相对于之前所讲过的分组密码来说，要差的多，因此不建议采用RSA加密过长的信息，因为性能想对来说比较差，如果消息长度大于n, 也可以采用之前提到的连接模式，只不过这里的分组长度变成了密钥的长度，按照同样规则进行处理即可。
对于RSA正确性的证明，我就不在这里啰嗦了，有兴趣的读者可以自行查阅相关书籍，在我后文的参考资料里面也有相关的知识，包括前面所提到的所有数学知识的证明也都有。
注意上面所说的rsa是理论上的rsa, 没有进行填充，rfc的标准实现里面是要求进行PKCS1Padding#2的方式进行padding的，关于这个padding是如何处理的，可以参考我之前写过的关于padding的文章，也可以参考文末给出的rfc，下面我给出的代码实现也是没有padding的，要注意这一点。
代码实现
这里用到了rust的大数运算的库，需要自行添加一下依赖，这个实现，我并没有添加找素数的过程，默认是有公钥和私钥的，只是实现了加密和解密算法。
// num_bigint = 0.4.2 use num_bigint::{BigUint, BigInt}; use std::ops::{Sub, Mul}; use num_traits::{FromPrimitive, zero, one}; pub struct PublicKey { pub n: BigUint, pub e: BigUint, } pub struct PrivateKey { pub n: BigUint, pub d: BigUint, } pub struct KeyPair { pub private_key: PrivateKey, pub public_key: PublicKey, } impl PublicKey { pub fn new(n: BigUint, e: BigUint) -> PublicKey { return PublicKey { n, e }; } } impl PrivateKey { pub fn new(n: BigUint, d: BigUint) -> PrivateKey { return PrivateKey { n, d }; } } pub fn phi(p: BigUint, q: BigUint) -> BigUint { return p.sub(BigUint::from_u8(1).unwrap()).mul(q.sub(BigUint::from_u8(1).unwrap())); } pub fn mod_inv(u: &BigUint, v: &BigUint) -> BigUint { let mut q: BigUint; let mut t1: BigUint; let mut t3: BigUint; let (mut u1, mut u3, mut v1, mut v3) = (BigUint::from(1u8), u.clone(), BigUint::from(0u8), v.clone()); let mut iter: i8 = 1; while &v3 != &zero() { q = &u3 / &v3; t3 = &u3 % &v3; t1 = &u1 + &q * &v1; u1 = v1; v1 = t1; u3 = v3; v3 = t3; iter = -iter; } if &u3 != &one() { return zero(); } if iter < 0 { return v - u1; } u1 } impl KeyPair { pub fn from_keys(private_key: PrivateKey, public_key: PublicKey) -> KeyPair { return KeyPair { private_key, public_key, }; } fn encrypt(&self, message: &[u8]) -> Vec<u8> { let res = BigUint::from_bytes_be(message); return res.modpow(&self.public_key.e, &self.public_key.n).to_bytes_be(); } fn decrypt(&self, message: &[u8]) -> Vec<u8> { let res = BigUint::from_bytes_be(message); return res.modpow(&self.private_key.d, &self.private_key.n).to_bytes_be(); } } #[cfg(test)] mod test { use crate::rsa::{KeyPair, PublicKey, PrivateKey, phi, mod_inv}; use num_bigint::{BigUint, BigInt}; use std::str::FromStr; #[test] fn test_phi() { let p = BigUint::from_str("253510634729688379261").unwrap(); let q = BigUint::from_str("719924526944767849").unwrap(); assert_eq!(phi(p, q).to_string(), "182508523783238741385145482544078032480") } #[test] fn test_mod_inv() { let result = mod_inv(&mut BigUint::from_str("65537").unwrap(), &mut BigUint::from_str("182508523783238741385145482544078032480").unwrap()); assert_eq!(result.to_string(), "148798319159955634674933143465449706753"); } #[test] fn test() { let key = KeyPair::from_keys( PrivateKey::new(BigUint::from_str("182508523783238741639376041800711179589").unwrap(), BigUint::from_str("148798319159955634674933143465449706753").unwrap()), PublicKey::new(BigUint::from_str("182508523783238741639376041800711179589").unwrap(), BigUint::from_str("65537").unwrap())); let result = key.encrypt("AAAA".as_bytes()); println!("{:?}", result); println!("{:?}", key.decrypt(&result)); } }
