运行环境：C、Python
创作作者：左手の明天
磊精选专栏：python
推荐专栏：算法研究
——————————————————————————
大家好珞珞珞，我是左手の明天！
最近更新：2022 年 5 月 1 日，左手の明天的第 236 篇原创博客
更新于专栏：算法研究
——————————————————————————
RSA加解密算法今天是五一劳动节，在这里左手の明天祝大家节日快乐
- 1 前言
- 2 公钥密码算法理论
- ⭐️2.1 公钥密码体系
- ⭐️2.2 公钥密码系统工作原理
- 3 RSA密码算法
- ⭐️3.1 RSA 公钥密码系统工作流程
- ⭐️3.2 RSA密钥对生成
- ⭐️3.3 RSA加密算法
- ⭐️3.4 RSA解密算法
- ⭐️3.5 RSA算法实例
- ⭐️3.6 RSA数字签名算法
- 4 RSA实现（C语言）
- ⭐️4.1 大数的加法运算
- ⭐️4.2 大数的减法运算
- ⭐️4.3 大数的乘法运算
- ⭐️4.4 大数的除法运算
- ⭐️4.5 完整代码
- 5 基于PyCryptodome的RSA设计与实现
- ⭐️5.1 PyCryptodome库相关函数
- ⭐️5.2 RSA加密算法设计
- 5.2.1 生成密钥对
- 5.2.2 RSA数据加密
- 5.2.3 RSA解密算法
- 5.2.4 RSA数据签名
- ⭐️5.3 消息内容的AES加密与解密
密码学和安全协议是通信系统安全的技术核心。传统的密码技术主要是建立在基本的替代和置换工具上的对称密钥加密技术，包括有 DES，3DES，IDEA，AES，Blowfish 等。Diffie 和 Hellman 在1976年首次公开引进公开密钥密码技术的概念，但并没有给出一种有效的算法，直到两年后由 MIT（麻省理工学院）的 Ron Rivest，Adi Shamir 和 Len Aleman 提出了 RSA 的通用公开加密方法，从而使得公开加密技术在国防、商业上获得越来越广泛的应用，国际上ISO，ITU，SWIFT 等标准化组织已把 RSA 体制作为标准。
RSA 密码体制是目前较流行的一种公钥密码算法。
2 公钥密码算法理论公钥密码学的提出是为了解决对称密码学中密钥分配和数字签名两个难题 。1976 年 Diffe 和Hellman 首次公开提出了公钥密码学的概念，并设计了在不安全公共网络上进行安全传输密钥的协议问题。公钥密码学系统的安全性是基于单向陷门函数的安全性,所谓单向陷门函数就是正向计算函数值很容易，在缺少附加信息时计算函数的逆是不可行的，一般满足下列条件：
1）若 k 和 X 已知，则可计算
Y
=
f
k
(
X
)
Y = f_{k}(X)
Y=fk(X)
2）若 k 和 Y 已知，则可计算
X
=
f
k
(
Y
)
X = f_{k}(Y)
X=fk(Y)
3）若 Y 已知，但 k 未知，则计算出
X
=
f
k
−
1
(
Y
)
X = f_{k}^{-1}(Y)
X=fk−1(Y)不可行。
从集合论角度看，一个公钥密码系统可以定义为一个九元组集合：{M,C,K,m,X,e,d,E,D}
- 1）M 为明文集合，或称作明文空间；
- 2）C 为密文集合，或称作密文空间；
- 3）K 为密钥集合，或称作密钥空间；
- 4）m∈M，是明文集合的一个子集；
- 5）X∈C，是密文集合的一个子集；
- 6）e为公钥，d为私钥，(e,d)∈K，且 e≠d；
- 7）E为加密函数，D为解密函数；由于 m∈M，X∈C，使用公钥
e
k
e_{k}
ek，加密如下：
X = E e k ( m ) X=E_{e_{k}}(m) X=Eek(m) - 8）D为解密函数，使用私钥
d
k
d_{k}
dk，则：
X = D d k ( m ) X=D_{d_{k}}(m) X=Ddk(m)
满足：
D d k ( X ) = D d k ( E e k ( m ) ) = M D_{d_{k}}(X)=D_{d_{k}}(E_{e_{k}}(m))=M Ddk(X)=Ddk(Eek(m))=M
公钥密码系统工作原理如图所示：
RSA 密码体制属于分组密码，是目前最流行、应用最广泛的公钥密码系统。假设 Bob向 Alice发送消息，RSA 公钥密码系统工作流程如图所示：
RSA密码算法可以假设为一个八元组：{M，C，K，e，d，N，E，D}
- 1）M 为明文空间；
- 2）C 为密文空间；
- 3）K 为密钥空间；
- 4）e为公钥，d为私钥；
- 5）E 为加密函数；
- 6）D 为解密函数；
- 7）N 为 p 和 q 两个大素数之积，且 p、q 位数不小于 100，{(e,N),(d,N)}∈K 且 e≠d，同时满足 ed≡1(modφ(N))，φ(N)=(p-1)(q-1)。
RSA算法产生密钥的过程：
- Bob 随机生成两个大小相当的大素数p, q（保密），且 p≠q；
- 计算n=pq（公开），欧拉函数Φ(n)=(p-1)(q-1)(保密) ，这里的整数 n 是RSA 算法的模；
- Bob 再选择一个随机数 e∈N，这样 1
- 使用扩展欧几里德算法，计算出 d∈N,且 1
- 使用扩展欧几里德算法，计算出 d∈N,且 1
假设明文消息 m∈M 是数值形式，且 m 加密时首先将明文比特串进行分组，使得每个分组对应的串在数值上小于 N，即分组的二进制长度小于 1092 N。然后，对每个明文分组 m，作加密运算。过程如下： 1）Bob通过公共数据库获得 Alice的公钥(n,e)； 当 Alice 接收到加密消息 c 时，使用私钥 d 和要加密的明文 m 进行
m
≡
c
d
(
m
o
d
n
)
m≡c^{d}(modn)
m≡cd(modn)进行计算。 取p=47， q=71，则n = p * q = 3337， Φ(n)=(p-1)(q-1)=3220，随机选择加密密钥e，e与Φ(n)互素，若取e=79，则 d=79-1(mod n)=1019。 假设要加密的明文是m=6882326879666683，首先，根据n的大小将m进行分组，这里我们把明文m分成六个组，即： 接着分别对各个分组进行加密运算，第一个分组加密为 类似的，对其余各个分组分别进行加密运算，得到如下密文： 解密时用私钥1019分别对明文进行解密运算，即： 对其余的密文用同样的计算方法就可以把密文恢复出来，即得到密文。 RSA 的主要应用之一是数字签名，数字签名是一种将信息绑定到实体的机制，并且包含一个验证过程。 1）初始化阶段 2）签 名 3）验 证 目前在 32 位机器上能表示的最大整数只有
2
32
−
1
2^{32}-1
232−1，RSA 中几百位甚至上千位的大数的加法运算用一般机器上定义的加法运算是无法满足的，必须定义与大数存储方式符合的运算方式来计算大数相加。 函数的功能是计算 A+B，并将计算结果保存到 C 中。 大数加法运算的原理与普通的加法计算一样，是从低位单元依次相加，若有进位则将进位 1 先加到C 的高一个单元中，最后计算的结果存放在 C 中。 同大数的加法运算一样，也必须自己定义大数的减法运算。 函数的功能是计算 SA-SB，并将计算结果保存到 SC 中，参数要求SA ≥SB 。 其中Int Cpy(buf,SA)是将 SA 拷贝到 buf 中。 大数减法运算的原理与普通的减法计算一样，是从低位单元依次相减，若低位单元不够减则向高位单元借 1 化作 10 个低位单元，并将高位的单元减 1，最后计算的结果存放在 SC 中。 同大数的加法运算一样，也必须自己定义大数的乘法运算。 函数的功能是计算 A×B ，并将计算结果保存到 C 中。 由于大数的存储采用一个单元存储大数的一个十进制位，这与我们日常生活中计算整数的乘法是一样的形式，因此非常容易理解上述的伪代码。大数乘法运算的原理与普通的乘法计算一样，是从乘数 B的低位单元依次与 A 相乘，产生的进位保存在高一位的存储单元内。 同大数的其它运算一样，也必须自己定义大数的除法运算。 函数的功能是计算 A÷B ，并将余数保存在 C 中，商保存在 D 中。 上述大数的除法运算的原理与普通整数的除法计算不太一样，是从被除数 A 的高位单元开始取与除数 B相同长度的单元与 B 循环做减法，直到不够减时再退一位，每次够减时在商 D 中相应的单元中加 1。 RSA.C：源码内容 RSA.H：源码内容 PyCryptodome 是一个包含底层密码原语的 Python 包。 使用非对称密码算法时，Bob 首先要随机生成一对密钥，下面代码是 Python 的 RSA 密钥对生成过程，公钥存储在文件Bob_public_key.pem 中，私钥存储在文件 Bob_private_key.pem 中，程序代码如下： Alice要向Bob发送加密的数据，假设Alice已经获得Bob的公钥，且存储在一个名为Bob_public_key.pem的文件中。因为希望能够加密任意长度的数据，一般使用混合加密方法，即使用 AES 加密消息明文，再用 RSA 加密随机生成的会话密钥，使用 EAX 模式来检测未经授权的修改。过程如下： Bob 首先使用自己的私钥解密，获取会话密钥，然后进行密文解密。具体算法如下： 发送者 Bob使用自己的私钥对消息进行签名,接收者 Alice使用 Bob的公钥对签名信息和完整性进行解密及真实性验证。 假设明文为： 使用 get_random_bytes(16) 随机生成的加密密钥为： AES算法加密后的密文为： 同理，接收方首先使用自己的私钥解密并获得对称密钥 key，然后对密文 Encrypt_text 解密获得明文 Message。 总结不易，看到这那就来个三连吧，肝。。。
2）Bob通过加密算法对消息 m 进行加密，
c
≡
m
e
(
m
o
d
n
)
c≡m^{e}(modn)
c≡me(modn)，其中 m 为明文，c 为密文。；
3）Bob发送 c∈X给 Alice。m1=688，m2=232，m3=687，m4=966，m5=668，m6=003
c1=68879(mod 3337) = 1570
c=1570 2756 2091 2276 2423 158
m1=15701019(mod 3337) = 688
4 RSA实现（C语言）
⭐️4.1 大数的加法运算
Alice 发送消息给 Bob，从 RSA 密钥空间 k={n, p, q, e, d}选择签名所需要的各种参数。
Alice的私有数字签名 Sigk由下式生成：
S
i
g
k
(
m
)
≡
m
d
≡
c
(
m
o
d
n
)
Sig_{k}(m)≡md≡c (mod n)
Sigk(m)≡md≡c(modn)Verk 是它的公共验证算法，然后它发送 (m, c)给 Bob。
Bob 获得 Alice 的公钥及签名信息(e, Verk)，计算
V
e
r
k
(
m
,
c
)
Ver_{k}(m, c)
Verk(m,c)，当
m
≡
c
e
(
m
o
d
n
)
m≡c^{e}(mod n)
m≡ce(modn)时，
V
e
r
k
(
m
,
c
)
Ver_{k}(m, c)
Verk(m,c)正好是 1，在这种情况下，Bob接受签名，否则拒绝它。void Plus(byteint A,byteint B,byteint C)
{
register i;
int X,m,n,valid;
m=Int Valid(A);
n=Int Valid(B);
valid=(m>n)?m+1:n+1;
Set Zero(C);
for(i=Data Length-1;i>=Data Length-valid;i--)
{
X=C[i]+A[i]+B[i];
C[i]=X%10;
if(X>9)
C[i-1]=C[i-1]+X/10;
}
}
void Substract(byteint SA,byteint SB,byteint SC)
{
byteint buf;
register i,j;
Int Cpy(buf,SA);
Set Zero(SC);
for(i=Data Length-1;i>=0;i--)
{
if(buf[i]
void Multiply(byteint A,byteint B,byteint C)
{
register i,j,w;
int X;
int Avalid=0;
int Bvalid=0;
while (A[Avalid]==0 && Avalid=Avalid;i--)
for(j=Data Length-1;j>=Bvalid;j--)
{
w=i+j-(Data Length-1);
X=C[w]+A[i]*B[j];
C[w]=X%10;
C[w-1]=C[w-1]+X/10;
}
}
void Divide(byteint A,byteint B,byteint C,byteint D)
{
register i,j;
int valid_1,valid_2,valid,sbits,cmpval;
byteint buf1,buf2;
Set Zero(D);
Int Cpy(C,A);
valid_2=Int Valid(B);
while((cmpval=Int Cmp(C,B))>0)
{
valid_1=Int Valid(C);
valid=valid_1-valid_2;
if(valid>0)
{
i=Data Length-valid_1;
j=Data Length-valid_2;
sbits=0;
while(j
if(C[i]>B[j])
break;
if(C[i]
#include
#define DATALENGTH 350
signed char R[DATALENGTH],PK[DATALENGTH],RsaKey[DATALENGTH];
signed char SK[DATALENGTH];
unsigned char DesKey[9];
int RsaPrepare(signed char *sk,signed char *pk,signed char *r);
int ReadRsaFile(signed char *r,signed char *pk,signed char *sk);
int WriteRsaFile(signed char *r,signed char *pk,signed char *sk);
//int EncipherDesKey(char *deskey,signed char *r,signed char *pk,signed char *rsakey);
int DecipherDesKey(signed char *rsakey,signed char *r,signed char *sk,char *deskey);
int StrToByt(char *str,signed char *byt);
void BytToStr(signed char *byt,char *str);
5 基于PyCryptodome的RSA设计与实现
⭐️5.2 RSA加密算法设计
5.2.1 生成密钥对
from Cryptodome.PublicKey import RSA
import binascii
key = RSA.generate(2048)
f1= open('Bob_private_key.pem','wb')
f1.write(key.export_key(format='PEM'))
f1.close()
f2=open("Bob_public_key.pem",'wb')
f2.write(key.publickey().export_key(format='PEM'))
f2.close()
5.2.2 RSA数据加密
from Cryptodome.PublicKey import RSA
from Cryptodome.Random import get_random_bytes
from Cryptodome.Cipher import AES,PKCS1_OAEP
from binascii import b2a_hex
message="……".encode("utf-8")
receiver_key=RSA.import_key(open("Bob_public_key.pem").read())
session_key=get_random_bytes(16)
# 使用 RSA 公钥加密会话密钥
cipher_rsa=PKCS1_OAEP.new(receiver_key)
enc_session_key=cipher_rsa.encrypt(session_key)
# 使用 AES算法及会话密钥加密消息
cipher_aes=AES.new(session_key,AES.MODE_EAX)
ciphertext,tag=cipher_aes.encrypt_and_digest(message)
fo=open("encrypted_message.bin","wb")[fo.write(i)foriin(enc_session_key,cipher_aes.nonce,tag,ciphertext)]
#print(b2a_hex(ciphertext))
5.2.3 RSA解密算法
from Cryptodome.PublicKey import RSA
fromCryptodome.Cipher import AES,PKCS1_OAEP
fi=open("encrypted_message.bin","rb")
private_key=RSA.import_key(open("Bob_private_key.pem").read())
enc_session_key,nonce,tag,ciphertext=
[fi.read(i)foriin(private_key.size_in_bytes(),16,16,-
1)]
# Bob使用私钥解密 AES会话密钥
cipher_rsa=PKCS1_OAEP.new(Bob_private_key.pem)
session_key=cipher_rsa.decrypt(enc_session_key)
# 使用 AES会话密钥解密消息
cipher_aes=AES.new(session_key,AES.MODE_EAX,nonce)
message=cipher_aes.decrypt_and_verify(ciphertext,tag)
print(message.decode("utf-8"))
5.2.4 RSA数据签名
from Cryptodome.Hash import SHA256
from Cryptodome.PublicKey import RSA
from Cryptodome.Signature import pkcs1_15
message = "……".encode("utf-8")
key=RSA.import_key(open('Bob_private_key.pem').read())
h = SHA256.new(message)
signature = pkcs1_15.new(key).sign(h)
#接收者可以使用匹配的公钥来验证接收到的消息的真实性
key=RSA.import _ key(open('Bob_public_key.pem').read())
h = SHA256.new(message)
try:
pkcs1_15.new(key).verify(h, signature)
print("The signature is valid.")
except(ValueError, TypeError):
print("The signature is not valid.")
⭐️5.3 消息内容的AES加密与解密
Message="On December 3, 1941, chi bu chau deciphered a secret message intercepted by the Japanese foreign ministry to ambassador nomura in the United States:1. Inform the concerned depositor to transfer the deposit to the neutral country bank as far as possible; 2.The imperial government decided to take drastic action."
key=76b2d1bdfa8548c7937a22bfffa2a452
Encrypt_text="3wz35qGoZe4zY5J6IBPWniTJ9n6m6mkJJdv7ba/uPQMIZh0651yuyZj4BTaBTSA9Dg4HysETKpPDZEqlUaatgmAqczKOJYp5mBviIoL + b + TeiFjXrsi85RYtZXVAruRelql6TiKe2D5A84OkP8AFeD2qmhfKVY + A0oXn5QBS3801mKzqbqxHPVwKFlKqdaUMbEGSoxFJ7SBVxGZmZCIAm5lXhpKIUBl3e3HZzGNGLAfqQC2xBGbrH24MLDwexQJClwqF4yYutStB + fP3T3VsMVdcY191mwKIQzwh/tQkc + itbGUsdEjEzsh1LhyjV4KenOLesyr1ECPHXBrA2hC4MF3sjlm8HEoVH9eQo5xXumX4zCCHxC8uCUCNz8LNhpJ + KyRKGX3PgL0d0dE2y68+0S1vluQEzUCTNf4W5OQQTsM="
总结不易，看到这那就来个三连吧，肝。。。
