小白人工简单的RSA算法的代码化，用学了一天的python呈现屎山

一.RSA算法及极简介

信息对称加密的算法，RSA算法中，两个大质数（记作p和q）是核心秘密，它们相乘得到模数n（公开）。公钥e通常取固定值如65537，且必须与(p-1)(q-1)互质；私钥d是e关于(p-1)(q-1)的模逆元，满足e·d ≡ 1 mod (p-1)(q-1)。加密时用公钥(e, n)，解密时用私钥(d, n)。该算法广泛用于安全通信（如HTTPS）、数字签名（确保身份和完整性）以及密钥交换。其安全性基于大整数n难以分解回p和q。而在d的求取处理上，我们在已知p,q,e的情况下十分易于求解。

二.简单情景下的人工计算法——辗转相除 （已知p,q,e)

1.数学原理基础

欧拉函数，欧拉定理，模运算，费马小定理

2.步骤

步骤一：选择两个大素数 p 和 q

步骤二：计算模数 n=p×q

步骤三：计算欧拉函数 φ(n)=(p-1)×(q-1),令其为r

步骤四：选择公钥指数 e    0<e<φ(n)=(p-1)×(q-1),且互质

步骤五：计算私钥指数 d     

e,d满足: e*d-r*k=1（基于模运算理解）,k为整数

3.辗转相除法的“步骤5”核心–模运算与回代

以题目为例：p=5,q=11,e=7,d=???

易得r=(p-1)*(q-1)=40,则得到：7*d – 40*k = 1(i)

7<40=>>>        40 % 7 = 5        =>>>7*d – 5*k = 1(ii)

7>5=>>>        7 % 5 = 2        =>>>2*d – 5k = 1(iii)

2<5=>>>        5 % 2 = 1        =>>>2*d – 1k =1(iv)

此时r处先归1，令d=1(若e先则令k=0)  

辗转开始：

将d=1带入(iv)求得k=1,将k=1带入(iii),求得d=3,将d=3带入(ii)，求得k=4，将k=4带入(i)得到d=23即为最终答案

三.代码初学者的落实

纵观人工入门计算，可以得到以下思路：

p,q,e的质数性，e与r的相对比较大小，质数输入不符的自动迭代换数处理；

又涉及到辗转相除，必须有储存所谓列出的方程式的对象，由于对python并未做深入了解，此处采用列表形式。

import math
#输入端
num1 = int(input("第一个质数："))
num2 = int(input("第二个质数："))
num3 = int(input("输入初步公钥："))
###输入端质数验证函数———————————-111111111111111111111
def is_prime(n):

# 1. 处理特殊情况：小于2的数不是质数
if n <= 1:
return False
# 2. 2是唯一的偶质数
if n == 2:
return True
# 3. 大于2的偶数不是质数
if n % 2 == 0:
return False
# 4. 检查从3到√n的所有奇数（核心逻辑）
# 取平方根并向上取整，避免浮点误差
max_divisor = int(math.isqrt(n)) + 1
# 步长设为2，只检查奇数
for i in range(3, max_divisor, 2):
if n % i == 0:
return False
# 5. 所有检查通过，是质数
return True
#输入端参数质数验证
def numsdeal(numlist):
for i in range (3):
while not is_prime(numlist[i]):
numlist[i] = numlist[i] + 1
return numlist
numin = [num1,num2,num3]
numin = numsdeal(numin)
#保障e < r且质数
r = (num1-1) * (num2-1)
if numin[2] > r:
for i in range(2):
numin[i] = numin[i] + 1
while not is_prime(numin[i]):
numin[i] = numin[i] + 1
else:
print("正确参数列(质数1,质数2,最终公钥)为:",numin)
else:
print("正确参数列(质数1,质数2,最终公钥)为:",numin)
liste = [numin[2]]
listr = [r]
listE = [numin[2]]
listR = [r]
def elists(liste,listr,listE,listR):
if listr[-1] != 1:
liste.append(liste[-1] % listr[-1])
listr.append(listr[-1])
listE.append(liste[-1])
return rlists(liste,listr,listE,listR)
else:
return [liste,listr,listE,listR]
def rlists(liste,listr,listE,listR):#########必定先执行这一步，与elists交互

if liste[-1] != 1:
listr.append(listr[-1] % liste[-1])
liste.append(liste[-1])
listR.append(listr[-1])
return elists(liste,listr,listE,listR)
else:
return [liste,listr,listE,listR]

endlist = rlists(liste,listr,listE,listR)
liste = endlist[0]
listr = endlist[1]
listE = endlist[2]
listR = endlist[3]
listD = []
listK = []
personal_key = 0
##辗转相除核心 e * d – r * k = 1
def RSA_to_K(liste,listr,listE,listR,listD,listK,i):
if i >= -len(liste):
listK.append((liste[i] * listD[-1] – 1) /listr[i])############################
i = i – 1
return RSA_to_D(liste,listr,listE,listR,listD,listK,i)
else:
personal_key = listD[-1]
return personal_key
##
def RSA_to_D(liste,listr,listE,listR,listD,listK,i):
if i >= -len(liste):
listD.append((listr[i] * listK[-1] + 1) / liste[i])
i = i – 1
return RSA_to_K(liste,listr,listE,listR,listD,listK,i)
else:
personal_key = listD[-1]
return personal_key
##初始化分流
def RSA(liste,listr,listE,listR,listD,listK,i=-1):
if listR[-1] == 1:
listD.append(1)
listK.append(liste[i] – 1)
i = i – 1
return RSA_to_D(liste,listr,listE,listR,listD,listK,i)
elif listE[-1] == 1:
listK.append(0)
listD.append(liste[i] ** -1)
i = i – 1
return RSA_to_K(liste,listr,listE,listR,listD,listK,i)
else:
return False
personal_key = RSA(liste,listr,listE,listR,listD,listK,i=-1)

print(int(personal_key))

虽然说是屎山，但是也不咋滴。。。

#############

其中有两个列表是记录辗转的有效轨迹的，用于复盘测试。

四.复盘

缺点十分多，对算法的本质理解还不够深，造成的代码冗余量十分大，见笑也望见谅与鼓励。

奋斗，共同成长，不断学习中。。。。。。