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位,对于这么大的一个数字来说肯定不会直接计算它的幂次的值,再取模。对于这些问题,后续再找个时间补充。

暂无评论