加密算法之RSA(一)

张彤 2021年10月31日 320次浏览

对于服务器部署在云或者公网上的情况,登录方式一般都不会采用简单的密码登录。
可以使用以下命令查看不同ip猜密码的情况

cat /var/log/secure

当然,你可以在云端限制ip,然而更好的办法是使用密钥登录。

centos7 密钥登录

本文不是介绍如何添加及使用密钥的,而是密码学里一个非常有趣的算法,RSA。


  • RSA 中文名称公钥加密算法,可以这样说,它是现代计算机通讯安全的基石。

在1976年之前,即便是复杂的英格玛机(一种二战德国的加密机器)也要服从以下两条原则

1, Alice使用一种特定的加密规则对信息加密
2,Bob如果想要解密,则需要知道Alice的机密规则

这种加密方法,统称为对称加密

那么,麻烦也就是来了,保存和传递密钥就成了大难题。
天天换密钥也是有风险的,当Alice每天把密钥发给Bob时,如果这把钥匙是每天更换还好,如果连续几周不更换,那么密文被破译的几率将会几何倍数增加。

难道从凯撒密码到英格玛机,人类的加密办法穷尽了吗?
当然不可能了!
1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了大名鼎鼎的迪菲赫尔曼交换密钥算法。
这个时候,人们意识到加密和解密是可以使用不同规则进行的。

这种办法被成为 非对称加密

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。
RSA算法也是三位大神名字首字母的组合。
rsa.jpg

那么在正式介绍RSA实现方法前,需要了解一些数学知识,别紧张,只要有点数论基础就可以啦~~~

互质关系

  • 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系,也有叫互素关系的。

需要注意的是,互质关系的两个数,不仅仅是质数,比如 3和 10 就是互质关系,但很明显,10不是质数

关于互质,有以下特性

  1. 两个不同的质数一定是互质数。
  2. 一个质数,另一个不为它的倍数,这两个数为互质数。
  3. 1不是质数也不是合数,它和任何一个自然数(1本身除外)在一起都是互质数。
  4. 相邻的两个自然数是互质数.
  5. 相邻的两个奇数是互质数。
  6. 较大数是质数的两个数是互质数
  7. 两个数都是合数(二数差又较大),较小数所有的质因数,都不是较大数的约数,这两个数是互质数。
  8. 两个数都是合数(二数差较小),这两个数的差的所有质因数都不是较小数的约数,这两个数是互质数。
  9. 两个数都是合数,较大数除以较小数的余数(不为“0”且大于“ 1”)的所有质因数,都不是较小数的约数,这两个数是互质数。

判断一个数是否为质数,python实现如下:

def is_prime(a):
    return all(a % i for i in xrange(2, a))

按照互质定义,判断两个数是否互质的函数 python实现如下:

#c 接口实现,速度更快
from math import gcd as bltin_gcd
def is_coprime(a,b):
    return bltin_gcd(a,b) == 1

#不使用内置math库实现
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

欧拉函数

对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。

在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

欧拉函数的值讨论

  1. 第一种情况
    φ(1)=1(小于等于1的正整数中唯一和1互质的数就是1本身)
  2. 第二种情况
    如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。
  3. 如果n是质数的某一个次方,即 n = pk (p为质数,k为大于等于1的整数)
    $$\phi(p
    k) = pk - p$$
    欧拉函数1.png
  4. 如果n可以分解成两个互质的整数之积
    $$\because n = p_1 \times p_2$$
    $$\therefore \phi(n) = \phi(p_1p_2) = \phi(p_1)\phi(p_2)$$
    欧拉函数2.png
    即积的欧拉函数等于各个因子的欧拉函数之积。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
  5. 由4 可以推广出 欧拉函数是积性函数,这也是RSA的基础。
    因为任意一个大于1的正整数,都可以写成一系列质数的积。
  • $$ n = p_1p_2p_3\cdots p_r $$
  • $$ \phi(n) = \phi(p_1)\phi(p_2)\phi(p_3) \cdots \phi(p_r)$$
  • $$\phi(n) = p_1p_2p_3\cdots p_r(1 -\frac1)(1 -\frac1)(1 -\frac1) \cdots(1 -\frac1)$$
  • $$ \phi(n) = n (1 -\frac1)(1 -\frac1)(1 -\frac1) \cdots(1 -\frac1)$$

欧拉函数3.png

具体的推导过程大家可以结合2,3步进行理解。
关于欧拉函数是积性函数的证明,可以参考以下链接

欧拉函数的性质

欧拉函数的python实现

from math import gcd

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount

欧拉定理

既然知道了欧拉函数,那么它有什么用呢?
它的用处在于欧拉定理。
欧拉定理定义如下

  • 如果两个正整数a和n互质(gcd(a,n)=1),则n的欧拉函数 φ(n) 可以让下面的等式成立
    $$a^{\varphi(n)}\equiv 1 (\mod n) $$
    欧拉定理1.png
    a的φ(n)次方减去1,可以被n整除
    欧拉定理的证明涉及群论,比较复杂,有兴趣的同学可以深入了解一下,参考链接:

Euler’s Theorem: proof by modular arithmetic

欧拉定理的重要作用在于

很大程度地简化幂的模运算

欧拉定理的一个特例,就是费马小定理
假设正整数a与质数p互质,因为质数p的φ( p)等于p-1,则欧拉定理可以写成
$$a^
= 1(\mod p)$$
欧拉定理2.png
欧拉定理是RSA算法的核心,理解这个定理,对于理解RSA在解密端快速解密有很大帮助。

模反运算 / 模逆元

如果两个正整数a和n互质,
那么一定可以找到整数b,使得 ab-1 被n整除,
或者说ab被n除的余数是1
$$ab\equiv1(\mod n)$$
模逆.png
比如:3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。

显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素
即如果b是a的模反元素,则 b+kn 都是a的模反元素。

python 实现模逆元

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

ok,数学知识补充了一大堆,下一篇文章,
开始介绍RSA算法的具体实现方法!~