公钥：e、n，私钥：d、n，加密：C=M^e % n，解密：M=C^d % n。其中：n=p*q（p 和 q 为大质数），1<e<ϕ(n)，gcd(e,ϕ(n))=1，ed % ϕ(n)=1，M 为信息，C 为密文

数论基础

1. 质数：又称素数，一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数
2. 模运算：求余运算，整除运算中，求 a 除以 b 的余数，可用 mod 表示，即 r = a mod b
3. 同余：两个整数 a、b，若它们除以正整数 m 所得的余数相等，则称 a、b 相对于模 m 同余，记作: a≡b(mod m)
4. 最大公因数：指两个或多个整数共有因数中最大的一个，a 和 b 的最大公因数记作：gcd(a,b)
5. 互质：若 N 个整数的最大公因数是 1，我们就称这 N 个整数互质，即 gcd(a,b)=1，a 和 b 互质
6. 欧拉函数：对于正整数 n，小于 n 的正整数中与 n 互质的数的个数，记为ϕ(n)，特别的ϕ(1)=1
7. 欧拉定理：若两个正整数 a 和 m 互质，那么 a 的φ(m)次方除以 m 的余数为 1，即 a^ϕ(m)≡1(mod m)
8. 模反元素：如果两个正整数 a 和 n 互质，则一定可以找到整数 b，使得a×b-1被 n 整除，或者说 ab≡1(mod n)，称 b 为 a 相对于 n 的模反元素

比如，3 和 11 互质，那么 3 相对于 11 的模反元素就是 4，因为 (3 × 4)- 1 可以被 11 整除

a^(ϕ(n)-1) 为 a 相当于 n 的模反元素，因a^ϕ(n)≡1(mod n) => a^(1+ϕ(n)-1)≡1(mod n) => a×a^(ϕ(n)-1)≡1(mod n)

同余相关性质

1. 若 a≡b(mod m)，b≡c(mod m)，则 a±c≡b±d(mod m)
2. 若 a≡b(mod m)，b≡c(mod m)，则 a×c≡b×d(mod m)
3. 若 a≡b(mod m)，那么 a^n≡b^n(mod m)
4. 若 a≡b(mod m)，n 为 m 因数, 则 a≡b(mod n)

互质相关性质

1. 任意两个质数是互质数
2. 较小数是质数，较大数不为它的倍数，这两个数是互质数
3. 较大数是质数的两个数是互质数
4. 1 和任意一个自然数是是互质数
5. 2 和任何奇数是互质数
6. 相邻的两个自然数是互质数
7. 相邻的两个奇数是互质数

欧拉相关性质

1. ϕ(1)=1，ϕ(2)=1
2. 当 n 是质数时，ϕ(n)=n-1
3. 当 p 为质数时，k 为自然数，那么ϕ(p^k)=p^k - p^(k-1)
4. 当 a 和 b 互质时，ϕ(ab)=ϕ(a)ϕ(b)，故当 n 是奇数时，ϕ(2n)=ϕ(n)
5. 任意一个大于 1 的正整数，都可以写成一系列质数的积

只有 p 的倍数与 p^k 互质，共有 p^(k-1)个，即 1p、2p、3p...p^(k-1)p，把它们去除，剩下的就是与 p^k 互质的数了，即ϕ(p^k)=p^k - p^(k-1)

算法

1. 选择两个大质数 p 和 q
2. 计算 n =p×q，计算欧拉函数ϕ(n)=(p-1)×(q-1)
3. 选择一个数 e，满足：1<e<ϕ(n)，且 e 与ϕ(n)互质
4. 计算 e 相对于ϕ(n)的模反元素 d，即 ed≡1(mod ϕ(n))
5. 公钥为 {e，n}，私钥为{d，n}
6. 加密：C=M^e(mod n)，解密：M=C^d(mod n)，M 为信息，C 为密文，M 需小于 n

• RSA 签名可用私钥加密信息摘要，验证者用公钥解密签名，和给出的签名进行一致性判断 *

大质数生成

1. 随机构造一个满足最终大质数长度的奇数 n

2. 判断 n 是不是质数，如果是则输出 n，否则 n =n+ 2 并重复此步骤

   1. 使用质数定义判断，将 n 除以 2 到 n 的算术平方根之间的所有数，如果余数都不为 0，则此数一定为质数
   2. 使用素性检测算法（Fermat、Miller–Rabin 等等），多次判断此数都为质数的情况下，则此数极大概率为质数

查找互质数

1. 利用互质特性直接得出结果（两个相邻的自然数是互质数，较小质数与不是倍数的较大数互质）
2. 使用辗转相除法计算两个数的最大公约数，如果是 1，则两数互质

计算模反元素

1. 随机选择一个正整数 k
2. 根据定义：a×b % n = 1，则 a 相对于 n 的模反元素 b = (k×n + 1) / a

快速幕模算法

1. 计算 a^b%n(a<n)，如果 a 和 b 很大，可以使用同余的性质来快速计算结果
2. 根据同余性质，有 (a × a) % n = (a%n × a%n) % n
3. 若 b 为偶数，则 a^b%n = (a^(b/2)%n × a^(b/2)%n) % n
4. 若 b 为奇数，则 a^b%n = (a^(b/2)%n × a^(b/2)%n × a) % n
5. 令 b'= b/2，有 a^(b/2)%n = a^b'%n
6. 故这里可以使用递归的方式计算 a^b%n，不断将 b 除 2，直到 1 为止

安全性

1. 随机数：使用完全随机的算法，避免潜在的安全，如果随机数被预测，私钥就有可能被破解
2. 密钥长度：为了保持算法的安全性，必须选择足够大的密钥长度，最低需要 1024 位，推荐使用 2048 位
3. 参数选择：尽量不重复使用大质数 p 和 q，也不要选择太大或太小的 e 和 d

证明

证明：M=C^d mod n (C=M^e mod n, 0<M<n)

C^d mod n                       代入C = M^e mod n
= (M ^ e mod n)^d mod n         同余化简(a mod n) mod n = a mod n
= M ^ (e × d) mod n             代入e × d = k × ϕ(n) + 1（k为任意正整数），因ed互为ϕ(n)的逆元
= M ^ (k × ϕ(n) + 1) mod n      等价转换
= M ^ (ϕ(n) × k) × M mod n      接下来需要证明此式等于M即可

由 n =p×q，M<n，可知 M 有三种情况：与 n 互质、p 的倍数、q 的倍数

若 M 和 n 互质

M ^ (ϕ(n) × k) × M mod n        代入M^ϕ(n) mod n = 1（欧拉定理）
= 1^k × M mod n                 代入1^k mod n = 1
= M mod n
= M

若 M 为 p 的倍数，则 M 必和 q 互质，

M ^ (ϕ(n) × k) × M mod n              代入ϕ(n) = ϕ(p) × ϕ(q)
= M ^ (ϕ(p) × ϕ(q) × k) × M mod n     因q为n的因数，使用a mod n = a mod q转换
= M ^ (ϕ(p) × ϕ(q) × k) × M mod q     代入M ^ ϕ(q) mod q = 1 （欧拉定理）
= 1^(ϕ(p) × k) × M mod q              代入1^(ϕ(p) × k) mod q = 1
= M mod q
= M

同理可证 M 为 q 的倍数的情况