title: “RSA”
date: 2024-06-03 10:42:02
updated: 2024-06-05 07:32:22
tag: [“notion”, “Algorithm”, “轮子”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘
RSA公钥加密系统中，公钥和密钥的产生：
假设密文为 c ，明文为 m
RSA的加密过程为：$c = m^e\pmod n$
RSA的解密过程为：$m = c^d\pmod n$
这里是公钥加密，私钥解密。
如果用于数字签名，则与之相反，即私钥加密公钥解密。
素数分布函数$\pi(n)$描述了小于或等于n的素数的数目。例如$\pi(n) = 4$，分别为$2,3,5,7$
素数定理
$\lim \limits_{n \rightarrow \infty}\frac{\pi(n)}{n/\ln n} = 1$
对于较小的n，近似式$n/\ln n$能精确的给出$\pi(n)$的估计值，如：$n=10^9$，误差不超过6%
为了找一个长度与n相同的质数大概需要在n的附近找大约$\ln n$个数，如找一个1024位长度的质数，大约需要测试$\ln 2^{1024} \approx 710$个随机选取的长度为1024位长的整数素性。
// rand big prime in 2^15
ll rand_prime(ll rd) {
ll prime = time(NULL) * rd % (2LL << 15);
while (!miller_rabin(prime, 10)) {
prime++;
// cout << prime << endl;
}
return prime;
}
简单的方法是试除。最坏时间复杂度为$O(\sqrt n)$。
费马小定理
如果p是质数，则$a^{p-1}\equiv 1\pmod {p}$，其中$a = 1, 2, \cdots, p-1$
如果能找到任意的$a \in \bold z^{+}_{n}$，使得n不满足$a^{n-1}\equiv 1\pmod {n}$，那么n就是合数。
令人惊讶的是它的逆否命题几乎成立。
// is a^(n-1) = 1 (mod n)
bool witness(ll a, ll n) {
ll u = n - 1, t = 0;
while (u & 1 == 0)
u >>= 1, t++;
// n - 1 = 2^t * u
ll x = modular_exponentiation(a, u, n);
// 二次探测定理
// 如果一个数p是质数，对于一个x∈(0,p)且x∈Z，方程x^2≡1(modp)的解有且只有两个：x=1或x=p−1。
for (int i = 0; i < t; i++) {
int xp = x;
x = x * x % n;
if (x == 1 && xp != 1 && xp != n - 1)
return true;
}
if (x != 1)
return true;
return false;
}
// test n times a^(n-1) = 1 (mod n), rand a
bool miller_rabin(ll n, ll s) {
for (int i = 0; i < s; i++) {
ll a = time(NULL) * (ll)rand() % (n - 1) + 1;
// cout << "a " << a << "n " << n << endl;
if (witness(a, n))
return false;
}
return true;
}
求$a^{b}\pmod {n}$的高效算法，时间复杂度$O(logb)$
ll modular_exponentiation(ll a, ll b, ll n) {
ll rt = 1;
while (b) {
if (b & 1)
rt = rt * a % n;
a = a * a % n;
b >>= 1;
}
return rt;
}
比如$a=3,b=13 = 1101_2$
如果直接for循环则需要13次。
但是可以预处理出$a,a^2,a^4,a^8\cdots$，然后根据b的二进制位进行选择。
$a^{13} = a^{1101_2} = a^{1000_2}a^{100_2}a^{1_2} = a^{8}a^{4}a^1$
已知a，b，n求解x，满足$ax\equiv b\pmod {n}$，这样的方程可能没有解，可能有一个或多个解。
该式子实际上可以转化为$ax+kn=b$，如果$b$是$gcd(a,b)$的倍数就有解，解的个数是$\frac{b}{gcd(a,b)}$
而对于已知的a，b，拓展欧几里得可以计算出满足$d = gcd(a,b) = ax+by$
// extend eculid , d = gcd(a,b) = ax+by
void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
ex_gcd(b, a % b, d, x, y);
ll t = *x;
*x = *y;
*y = t - (a / b) * (*y);
}
}
在RSA密钥生成过程中
$ed + k\phi(n) = gcd(e, \phi(n)) = 1$
有唯一解
// e*d = 1 (mod phi_n) => e*d +k*phi_n = 1
// rsa private key
ll private_key(ll e, ll phi_n) {
ll d, x, y;
ex_gcd(e, phi_n, &d, &x, &y);
return (x + phi_n) % phi_n;
}
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#define ll long long
using namespace std;
#define print(a, b) cout << a << ": " << b << endl
// extend eculid , d = gcd(a,b) = ax+by
void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
ex_gcd(b, a % b, d, x, y);
ll t = *x;
*x = *y;
*y = t - (a / b) * (*y);
}
}
// a^b%n
////a<n a*n < MAX n*n < MAX
ll modular_exponentiation(ll a, ll b, ll n) {
ll rt = 1;
while (b) {
if (b & 1)
rt = rt * a % n;
a = a * a % n;
b >>= 1;
}
return rt;
}
// is a^(n-1) = 1 (mod n)
bool witness(ll a, ll n) {
ll u = n - 1, t = 0;
while (u & 1 == 0)
u >>= 1, t++;
// n - 1 = 2^t * u
ll x = modular_exponentiation(a, u, n);
// 二次探测定理
// 如果一个数p是质数，对于一个x∈(0,p)且x∈Z，方程x^2≡1(modp)的解有且只有两个：x=1或x=p−1。
for (int i = 0; i < t; i++) {
int xp = x;
x = x * x % n;
if (x == 1 && xp != 1 && xp != n - 1)
return true;
}
if (x != 1)
return true;
return false;
}
// test n times a^(n-1) = 1 (mod n), rand a
bool miller_rabin(ll n, ll s) {
for (int i = 0; i < s; i++) {
ll a = time(NULL) * (ll)rand() % (n - 1) + 1;
// cout << "a " << a << "n " << n << endl;
if (witness(a, n))
return false;
}
return true;
}
// rand big prime in 2^15
ll rand_prime(ll rd) {
ll prime = time(NULL) * rd % (2LL << 15);
while (!miller_rabin(prime, 10)) {
prime++;
// cout << prime << endl;
}
return prime;
}
// e*d = 1 (mod phi_n) => e*d +k*phi_n = 1
// rsa private key
ll private_key(ll e, ll phi_n) {
ll d, x, y;
ex_gcd(e, phi_n, &d, &x, &y);
return (x + phi_n) % phi_n;
}
// rsa public key
ll public_key(ll phi_n) {
ll e = rand();
while (gcd(e, phi_n) != 1)
e++;
return e;
}
void test() {
srand((unsigned int)time(NULL));
ll p = rand_prime(rand());
ll q = rand_prime(rand());
ll e = rand_prime(rand());
// public_key e>max(p,q) so gcd(e, phi_n=(p-1)(q-1)) = 1
if (p > e)
swap(e, p);
if (q > e)
swap(e, q);
ll n = p * q;
ll phi_n = (p - 1) * (q - 1);
// ll e = public_key(phi_n);
ll d = private_key(e, phi_n);
print("p", p);
print("q", q);
print("n", n);
print("phi_n", phi_n);
print("e", e);
print("d", d);
ll msg = 1314;
ll code_msg = modular_exponentiation(msg, e, n);
ll decode_msg = modular_exponentiation(code_msg, d, n);
print("code_msg", code_msg);
print("decode_msg", decode_msg);
/*
e*d = 1 (mod phi_n)
m^e = c
c^d = m
m^{e*d} = m (mod n)
*/
}
int main() {
// cout << pow_mod(2, 10, 2000);
test();
return 0;
}
p: 16649
q: 32831
n: 546603319
phi_n: 546553840
e: 59809
d: 136453409
code_msg: 365022407
decode_msg: 1314
p: 17519
q: 18047
n: 316165393
phi_n: 316129828
e: 63211
d: 294359675
code_msg: 15110090
decode_msg: 1314
p: 22073
q: 4441
n: 98026193
phi_n: 97999680
e: 27647
d: 86011583
code_msg: 17550476
decode_msg: 1314
设密文为 c ，明文为 m，$c = m^e\pmod n$，$m = c^d\pmod n$
所以有$m\equiv m^{ed}\pmod {n}$
由于$ed\equiv 1\pmod {\phi(n)}$，其中$\phi(n) = (p-1)(q-1)$，所以$ed = 1+k(p-1)(q-1)$$\begin{array}{llllc}
m^{ed} & \equiv & m(m^{p-1})^{k(q-1)} & \pmod p & \
& \equiv & m((m \mod p))^{p-1})^{k(q-1)} & \pmod p & \
& \equiv & m(1)^{k(q-1)} & \pmod p & 费马小定理\
& \equiv & m & \pmod p & \
\end{array}$
类似地，有$m^{ed} \equiv m \pmod q$
根据中国剩余定理，$m^{ed} \equiv m \pmod n$
对外公开公钥$p=(e,n)$，已知n是两个质数p和q的乘积，如果能分解找到p和q。那么便可以通过拓展欧几里得算法求出$ed\equiv 1\pmod {(p-1)(q-1)}$的d。从而可以得到密钥$s=(d,n)$
RSA的加密系统的安全性主要来源于对于大整数进行因式分解的困难性。如果对方能够对公钥中的模n进行分解，就可以更具公钥推出密钥，这是因为对方和公钥创建者以相同的方法使用因子p和q。因此，如果能够轻易分解大整数，也就能轻易打破RSA加密系统。
经过20多年的研究，人们还没有发现比分解模n更容易的方法来打破RSA加密系统。
通过随机选取两个1024为的质数并求它们的积，就可以创造无法用可行技术可行时间内破解的公钥。所以在数论算法的设计方法还缺乏根本突破的情况下，RSA算法加密系统可以为实际应用提供高度的安全性。
RSA从提出到至今，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
但RSA算法也是有缺点的。
因此，RSA通常只用于少量数据加密。实际应用中一般用来加密对称算法的密钥，而密文多用对称加密算法加密传输。