鸽了快一个月,终于好好学了学,看了看。

背景

1976年以前,所有的加密方法都是同一种模式:

  1. 甲方选择某一种加密规则,对信息进行加密;
  2. 乙方使用同一种规则,对信息进行解密。
    例如,Alice现在需要把消息m告诉Bob,她选取的密钥为e,加密方式为m+e=c
    那么Alice就可以把密文c公开,把e告诉Bob.
    Bob拿到c和e后,只需要通过解密方式c-e就可得到原文m。

    由于加密和解密使用同样规则(简称"密钥"),这被称为"对称加密算法"(Symmetric-key algorithm)。
    这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。保存和传递密钥,就成了最头疼的问题。

人们认识到,加密和解密如果使用不同的规则,只要这两种规则之间存在某种对应关系,这样就避免了直接传递密钥。这样的新的加密模式被称为"非对称加密算法"

  1. 乙方生成两把密钥(公钥e和私钥d),e公开,任何人都可以知道,d则是保密。
  2. 甲方获取乙方的公钥,然后利于它对信息进行加密。
  3. 乙方得到加密后的信息,用私钥进行解密。
  4. 如果公钥加密只有私钥才能解开,那么只要私钥不泄露,通信就是安全的。

基于以上的背景,我们可以知道非对称加密满足以下几个性质:

  1. 正向加密容易,即发送方知道m和e后,可以很容易的进行$c=f_{e}(m)$加密运算;
  2. 在不知道私钥d的情况下,反向解密不可行,即外人只知道加密后的c和e,计算$m=f^{-1}(c)$不可行;
  3. 在知道密钥d的情况下,反向计算容易,接收方知道c和d后,计算$m=f_d^{-1}(c)$是很容易的。

对于以上的条件,若仅满足(1),(2)的函数$f$称为单向函数,在现实生活中这样的例子很多,比如把盘子打碎很简单,但是把碎片复原却很难。数学中也有很多函数满足这样的性质,比如大素数相乘要比其乘积的因式分解要容易得多。第(3)条性质称为陷门性,其中密钥d称为陷门信息,也就是对陷门函数来说,如果没有附加信息,那么他就是单向函数,有了陷门信息,计算就容易得多。生活中,比如把一个手表拆分为数千个细小的零件不难,但是把零件重新组合成一个可工作的手表却很难,这就需要我们知道陷门信息(手表的结构图)才能进行组合。

自1976年公钥密码体制的思想提出后,国际上已经出现了许多种公钥加密体制,例如基于大整数因数分解的公钥加密基于有限域乘法群上的离散对数的公钥加密基于椭圆曲线的离散对数问题的公钥加密等。
而本文讨论的就是基于大整数因数分解的公钥加密,由Rivest,Shamir,Adlema联合提出的RSA公钥加密体制。

数论基础

graph LR; A(数论)-->B(素数与互素); A-->c(欧拉函数); A-->E(欧拉定理); A-->F(模反元素)

素数与互素

一个大于1的自然数,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为素数(质数);否则称为合数。1既不是素数也不是合数。
如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互素(互质)关系。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。
每个整数n ≥ 2,均可分解成k个素数幂之积:
$$
n=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}
$$

欧拉函数

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法叫欧拉函数,用$\phi(n)$来表示,在1到8之中,与8形成互素的有1,3,5,7,所以$\phi(8)=4$。
对于欧拉函数,有以下几个性质:

  1. 若$n$为某个素数,则$\phi(n)=n-1$

  2. 若$n$为两个互素的数p,q相乘,则$\phi(n)=\phi(p)\times\phi(q)$

    比如$6=2 \times3,则\phi(6)=\phi(2) \times\phi(3)=1\times2=2$
    此性质可以推广到n为多个互素的数相乘
    证明需要用到"中国剩余定理",等完全梳理了再补上。

  3. 若$n$为某个素数的k次方,即$n=p^k$,则$\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$

    比如 8=23,则$\phi(8)=8-4=4$
    可以看出来,第一种情况就是k为1的一种特例。

  4. 对于整数n≥2,我们已经得知$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}$
    由2可以得知
    $$
    \phi(n)=\phi(p_1^{e_1})\phi(p_2^{e_2})\phi(p_3^{e_3})...\phi(p_k^{e_k})
    $$
    由3可以得知
    $$
    \begin{align}
    \phi(n)&=p_1^{e_1}p_2^{e_2}...p_k^{e_k}(1-\frac{1}{p_1})(1-\frac{2}{p_2})(1-\frac{k}{p_k}) \\
    &=n(1-\frac{1}{p_1})(1-\frac{2}{p_2})(1-\frac{k}{p_k})
    \end{align}
    $$

    比如$18=2\times3^2$,则$\phi(18)=18(1-\frac{1}{2})(1-\frac{1}{3})=6$
    1,5,7,11,13,17

欧拉定理

如果两个正整数a和n互素,则n的欧拉函数满足
$$
a^{\phi(n)} \equiv 1\pmod n
$$
也就是,a的$\phi(n)$ 次方被n除余1,比如3与7互质,7的欧拉函数为6,则36(729)被7除于1.
欧拉函数的证明,之后再放上。
欧拉函数有一个特殊情况:
若正整数a与素数p互素,因为$\phi(p)=p-1$,则
$$
a^{p-1} \equiv 1\pmod p
$$
这就是著名的费马小定理,费马大家都懂,经常是抛出一个定理留给后人证明,欧拉定理就是建立在费马小定理的基础上。
欧拉定理是RSA算法的核心,了解了它即可理解RSA。

模反元素

如果两个正整数a和n互质,那么可以找到整数b,使得ab-1被n整除,或者说ab被n除的余数为1
记作 $ab \equiv 1\pmod n$
b叫做a的模反元素,或称为a模n的逆,记作 $a^{-1}\pmod n$,在模数指明的情况下,即可记作$a^{-1}$
$3 \times4\equiv 1 \pmod {11} $,即3的模反元素为4,4的模反元素为3。
欧拉定理可以用来证明模反元素必然存在。
$$
a^{\phi(n)}=a\times a^{\phi(n)-1} \equiv 1\pmod n
$$
可以看出,a的$\phi(n)-1$次方就是a的模反元素。
比如2和5互质,5的欧拉函数为4,$2^4=2 \times 2^3 =16 \equiv 1\pmod 5$,则2模5的逆为23=8
显然,模反元素不止一个,$a^{-1}$加减n的整数倍都是a的模反元素。
不过通常,我们用Euclid拓展算法来计算模反元素。
欧几里得拓展算法:
在已知x,y,求解一组解a,b使得$ax+by=GCD(x,y)$
GCD(x,y)为x,y的最大公倍数,在x与y互素的情况下这个值即为1。

from gmpy2 import*
x=17
y=65537
print(gcdext(x,y))
#(mpz(1), mpz(30841), mpz(-8))

则求得a=30841,b=-8
求模反元素中,$ab \equiv 1\pmod n$,即$ab-kn=1$,带入脚本求出b即为a的模反元素
在python中,也有直接求模反元素的函数

from gmpy2 import invert
print(invert(17,65537))
#30841

原理

步骤 说明 描述 备注
1 找出质数 $p,q$ -
2 计算公共模数 $n=p \times q$ -
3 欧拉函数 $\phi(n)=(p-1)(q-1)$ -
4 取公钥e $1<e<\phi(n)$ $e与\phi(n)$必须互素​
5 取私钥d $e \times d\equiv1 \pmod {\phi(n)}$ d为e对$\phi(n)$的模反元素
6 加密 $c\equiv m^e\pmod n $ c:密文 m:明文
7 解密 $m\equiv c^d\pmod n $ c:密文 m:明文

我们通过一个例子,来理解RSA算法。
假如Alice要和Bob通信,接收方Bob选择p=43,q=59,e=13。$n=p\times q=43 \times 59=2537,\phi(2537)=42 \times 58=2436$
e=13,根据$13d\equiv1\pmod{2436}$,带入欧几里得拓展算法求得私钥d=937
Bob把公钥(n,e)=(2537,13)打包公开,d=937自己藏好。
Alice想要发送的消息为cybergreatwall,先把消息分块:cy、be、rg、re、at、wa、ll,按照英文字母表顺序a=00,b=01......z=25进行编码,得到:
0224,0104,1706,0019,2200,1111
假设对第一块0224进行加密,则${0224}^{13} \mod 2537 = 1692 =c_1$,对其他组进行同样的加密,最后c=1692 0803 1359 2299 1254 0724
Bob拿到c后,利用自己的d开始解密,
$m_1={c_1}^{d} \mod 2537 = 0224 $,剩下的密文用同样的方式,即可还原m。

攻击手段

最后修改:2020 年 12 月 31 日 02 : 20 PM