RSA算法-01

RSA加密过程

1.选两个质数p , q

2.将p，q相乘，得到一个数n

3.将(p - 1) 乘 (q - 1)得到欧拉函数fy

4.获取一个公钥e，需满足 1 < e < fy ， 且e和fy互质

5.获取一个私钥d, 需满足条件：

e * d 的积除以欧拉函数fy，其余数为1
假设e * d 除以 fy的商为s，则 e * d = fy * s + 1，即：
d = (fy * s + 1) / e

通过前面的步骤就有了公钥和私钥，假设需要加密的数字是m，加密和解密步骤如下

6.加密：

取m的e次幂，e是刚才获取的公钥e，将m**e除以n得到余数c，n是刚才p,q的积，c就是加密后的数字。

7.解密：

取c的d次幂，d是刚才获取的私钥d，将c**d除以n得到余数m_，m_就是解密后的数字。

如果对于它背后的数论知识很感兴趣(有的同学喜欢打破砂锅问到底)，可以看看或者回顾下这些：

欧拉函数

质因数分解

蒙哥马利算法

假设不清楚这些呢?也不打紧，把RSA涉及到的数学知识当做公理即可，不影响整个对整个流程的理解。

代码实现

以python为例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 次幂计算后取余数
def e_mod(base,e,n):
    return base ** e % n
    
# 生成公钥和私钥
def gen_key(p,q):
    n = p * q
    fy = (p - 1) * (q - 1)
    # 为了便于说明，直接取比n小1的数作为公钥
    e = fy - 1

    # 取私钥
    d = False
    for x in range(1, fy*fy): # 简单取个范围，用做示例
        a = fy * x + 1
        if a % e == 0:
            k = int(a / e)
            if k != e:
                d = k
                break

    if not d:
        return False

    return ((e,n),(d,n))

# 加密
def encrypt(m, pubkey):
    e = pubkey[0]
    n = pubkey[1]
    return e_mod(m,e,n)

# 解密
def decrypt(c, privateKey):
    d = privateKey[0]
    n = privateKey[1]
    return e_mod(c,d,n)

if __name__ == '__main__':
    keys = gen_key(19,29)
    if not keys:
        print('未生成,请检查p,q是否正确')
    p_key = keys[0]
    s_key = keys[1]
    m = 99 # 需加密的数字
    c = encrypt(m,p_key) # 得到加密后的内容
    print(c)
    m_ = decrypt(c,s_key) # 得到解密后的内容
    print(m_)

后续

这里的例子比较简单，粗浅地描述了下RSA的整个过程，细节性的问题，计算性能的问题等并未做说明。 比如实际使用的RSA算法至少都是1024位，对于这么大的一个数字来说肯定不会直接计算它的幂次的值，再取模。对于这些问题，后续再找个时间补充。