RSA算法详解一：初识RSA

1. 简介

RSA算法是一种比较经典的公钥算法，可用来加解密和签名。

如果你不想从数学证明方面理解这个算法，你只需要知道他利用的是

大质数分解的复杂性就可以了。

当然你也可以简单的看一下，数学描述和证明。

所需要的数学知识就是初等数论的一些基本定理，附在了文后。

2. 算法简单描述

（1） 选定两个质数$p,q$, $n$表示为两个质数的乘积$n=pq$。

（2）选取公钥指数$e$满足$\gcd (e,\varphi (n))=1$， $\gcd (e,\varphi (n))=1$是
为了保证$e$在模$\varphi (n)$下有逆元$d$； 其中$\varphi (n)$是欧拉函数，$\varphi (n)=(p-1)(q-1)$。

（3）计算$d$在模$\varphi (n)$下的逆元，也就是满足$ed\equiv 1(\mathrm{mod}\varphi (n))$

（4）选取明文$m,0\le m<n$， 执行加密操作$c=m^e\mathrm{mod}n$

（5）将得到的密文操作$c$, 执行解密操作$m=c^d\mathrm{mod}n$

3. 数学证明

实际上我们需要证明的就是
$$c^d\equiv (m^e\mathrm{mod}n{)}^d\equiv m(\mathrm{mod}n)$$
根据同余的性质，我们可以得到
$$(m^e\mathrm{mod}n{)}^d\equiv m^{ed}(\mathrm{mod}n)$$
因此我们的证明目标变成了
$$m^{ed}\equiv m(\mathrm{mod}n)$$
已知$ed\equiv 1(\mathrm{mod}\varphi (n))$, 那么$ed$可表示为
$$ed=k\varphi (n)+1$$
证明等价于
$$m^{k\varphi (n)+1}\equiv m(\mathrm{mod}n)$$
若$\gcd (m,n)=1$, 根据欧拉定理可得
$$\begin{gathered} m^{\varphi (n)}\equiv 1(\mathrm{mod}n) \\ {m}^{k\varphi (n)}\equiv 1(\mathrm{mod}n) \\ {m}^{k\varphi (n)+1}\equiv m(\mathrm{mod}n) \end{gathered}$$
若$\gcd (m,n)\ne 1$，那么必有$p\mid m$或者$q\mid m$; 我们假设$m=sp$, 即$p$整除$m$。

那么显然有
$$m^{k\varphi (n)+1}\equiv m^{\varphi (n)}\equiv m\equiv 0(\mathrm{mod}p)$$
将$\varphi (n)$展开代入$m^{\varphi (n)}$
$$m^{\varphi (n)}=m^{(p-1)(q-1)}$$
由于$\gcd (q,m)=1$，根据欧拉定理或者费马小定理我们有
$$m^{q-1}\equiv 1(\mathrm{mod}q)$$
因此
$$\begin{gathered} m^{k(p-1)(q-1)}\equiv (m^{q-1}{)}^{k(p-1)}\equiv 1(\mathrm{mod}q) \\ {m}^{k(p-1)(q-1)+1}\equiv m(\mathrm{mod}q) \end{gathered}$$
由于$\gcd (p,q)=1$, 又有
$$\begin{gathered} m^{k\varphi (n)+1}\equiv m(\mathrm{mod}p) \\ {m}^{k\varphi (n)+1}\equiv m(\mathrm{mod}q) \end{gathered}$$
因此
$$m^{k\varphi (n)+1}\equiv m(\mathrm{mod}n=pq)$$

4. 代码

由于$RSA$现在推荐使用的位数已经到了2048位置，所以随机选取$m$
$\gcd (m,n)\ne 1$的概率是非常低的，所以可以忽略不计。

在$pq$选取很小的时候，如果$\gcd (m,n)\ne 1$时，是容易出现加密后$c=m$的情况的。

#include <iostream>using ll = long long;template<typename T>
T gcd(T a,T b)
{while (b) {T tmp = b;b = a % b;a = tmp;}return a;
}
template<typename T>
T fpow(T a, T b, T MOD)
{T base = a;T res  = 1;while (b) {if ( b & 1) res = (res * base) % MOD;base = (base * base) % MOD;b >>= 1;}return res;
}
template<typename T>
T exgcd(T a, T b, T &x, T &y)  {if ( b == 0) {x = 1;y = 0;return a;}T x_0;T y_0;T d = exgcd( b, a % b, x_0, y_0);x = y_0;y = x_0 - (a / b) * y_0;return d;
}ll choose_e( ll phi_N)
{for ( ll i = 10; i < phi_N; i++) {if ( gcd(phi_N, i) == 1) return i;}return -1;
}
bool get_e_and_d( ll phi_N, ll &e, ll &d)
{for ( ll i = 10; i < phi_N; i++) {if ( gcd(phi_N, i) != 1) continue;ll tmp;exgcd( i, phi_N, d, tmp);if ( d < 0) d += phi_N;e = i;if (i != d) {return true;}else {printf("warning: e = d = %lld\n", e);return true;}}return false;
}
void rsa() 
{ll p = 11;ll q = 17;ll N = p * q;ll phi_N = (p - 1) * (q - 1);ll e;ll d;if (!get_e_and_d( phi_N, e, d)) {printf("get e and d failed!!!\n");return;}printf("e: %lld, d: %lld\n", e, d);for ( ll i = 1; i < q; i++) {ll m = i * p;ll c = fpow( m, e, N);printf("plain: %lld\n", m );if ( c == m) {printf("cipher is equal to plain!!!\n");}else {printf("cipher is: %lld\n", c);}ll dc = fpow(c, d, N);printf("decrypt is %lld\n", dc);if ( dc == m) {printf("rsa encode decode success!!!\n");}else {printf("rsa encode decode failed!!!\n");}printf("\n");}}void test_gcd()
{printf("gcd(12, 15) = %d\n", gcd(12, 15));printf("gcd(3,5) = %d\n", gcd( 3, 5));printf("gcd(32, 48) = %d\n", gcd( 32, 48));}int main()
{//test_gcd();rsa() ;return 0;
}

5. 相关数学知识

• 质数： 一个除只能被$1$和本身整除，如$3571113$

• 公因数：能同时整除多个数的数，比如$2$是$4$和$6$的公因数

• 最大公因数：用$\gcd ()表示$，如$\gcd (4,6)=2$

• 互质：两个数的的公因数为$1$,$\gcd (5,3)=1$

• 整除：$\mid$表示， 一个数是另外一个数的因数。比如$5\mid 10$，$2\times 5=10$。

• 取余（模）：用$\mathrm{mod}$表示,指一个数整除另外一个数余下的数，比如$12\mathrm{mod}5=2$， 因为$12=2\times 5+2$

• 同余：指两个数模另外一个数余下的数相同，用$\equiv$表示。就是两个数相减是模数的倍数。$a\equiv b(\mathrm{mod}n)\Rightarrow n\mid (a-b)$。例子$2$和$7$对$5$同余。$2\equiv 7(\mathrm{mod}5)$

• 同余性质：

  • 取模
    $$a\equiv b\iff (a\mathrm{mod}n)\equiv b\iff a\equiv (b\mathrm{mod}n)$$
  • 如果$a\equiv b(\mathrm{mod}n)$ , 那么有
    $$\begin{gathered} a\pm c\equiv b\pm c(\mathrm{mod}n) \\ ac\equiv bc(\mathrm{mod}n) \end{gathered}$$

• 引理：用作证明的最后一步
  $$\begin{gathered} \gcd (m,n)=1 \\ a\equiv b(\mathrm{mod}m) \\ a\equiv b(\mathrm{mod}n) \\ \Rightarrow a\equiv b(\mathrm{mod}mn) \end{gathered}$$

• 费马小定理: 如果$p$是一个质数，那么
  $$a^{p-1}\equiv 1(\mathrm{mod}p)$$

• 欧拉函数$\varphi (n)$：小于等于$n$的正整数中与$n$互质的数的个数，比如$\varphi (12)=4$, 其中$15711$和$12$互质。

• 欧拉定理：费马小定理的升级版，如果$\gcd (a,n)=1$,那么
  $$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

参考

di-mgt
ctf-wiki
感觉ctf-wiki也像是抄得上面那个网页上的。。。