使用Python 模拟RSA 加密与解密

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一、关于

RSA具体原理请移步其他文章，本文主要使用Python 来模拟RSA 算法的实现过程

二、简要分析

在RSA算法中，存在以下几个参数：

1、大素数p、q

2、n = p *q

3、Phi_n = (p-q) * (q-1)

4、E = 0x10001

5、计算得到数d, 使得 e *d % phi_n = 1

6、明文：a

7、密文：b

其中，公钥对（p, e）以及RSA加密算法对公众开放，私钥对（q, d）由加密者自己保留。RSA加密过程为：发送者使用公钥对明文加密得到密文，接收者使用私钥可以解密；RSA签名过程为：发送者使用私钥对明文进行加密（签名），接受者使用公钥可以成功解密，则证明发送者确实是私钥的拥有者。

RSA加密实验基本流程：

一、选取两个大素数p、q，并计算得到n、phi_n

二、选取常用的e = 0x10001，方便将幂运算优化为左移，加快运算速度

三、计算d，使用了扩展欧几里得算法

四、输入明文a，将明文转化为可以用于计算的数字形式

五、对a使用快速幂取模，得到密文b，以16进制显示

RSA解密流程：

六、对b使用快速幂取模，得到明文a，以字符形式显示

三、Python 代码

文件Main.py 为加密解密主程序，methods.py 文件内定义了一些被调用的函数

# RSA Generate By SOOWIN
# 2019/11/26
#import math
import os
from methods import exgcd,quick_algorithm,get_prime# p = get_prime(20)
# q = get_prime(10)p = 10001569
q = 10001567
print("p is : ",end='')
print(p)
print("q is : ",end='')
print(q)
n = p * q
print("n is : ",end='')
print(n)
phi_n = (p-1) * (q-1)
print("phi_n is : ",end='')
print(phi_n)e = 0x10001
d = 0
d = exgcd(e, phi_n)
if(d == 0):
print("Can't generate a proper number d to fit the requirement.")
os.system("pause")
if(d < 0 ):
d += phi_n
print("d is : "+ str(d))mText = "Hpptus"
mHex = mText.encode().hex()
print("mHex is : ",end='')
print(mHex)
mInt = int(mHex,16)
print("mInt is : ",end='')
print(mInt)c = quick_algorithm(mInt, e, n)
print("c is : ",end='')
print(c)
print("The message to be encrypt: "+mText)
print("The encrypted message is: "+ str(bytes.fromhex(hex(c)[2:])))decr = quick_algorithm(c, d, n)# print(bytes.fromhex(hex(decr)[2:]))decrHex = bytes.fromhex(hex(decr)[2:])
# print(decrHex)
print("The message recovered: "+ str(decrHex,encoding="utf-8"))

Main.py

import sys,randomdef exgcd(m, n, x = 0, y = 0):
if n == 0:
x = 1
y = 0
return (m,x,y)
a1 = b = 1
a = b1 = 0
c = m
d = n
q = int(c/d)
r = c%d
while r:
c = d
d = r
t = a1
a1 = a
a = t-q*a
t = b1
b1 = b
b = t-q*b
q = int(c/d)
r = c%d
x = a
y = b
return xdef quick_algorithm(a,b,c):
a=a%c
ans=1
while b!=0:
if b&1:
ans=(ans*a)%c
b>>=1
a=(a*a)%c
return ans