Python实现RSA加密算法

2022年 11月 4日

Python实现RSA加密算法

RSA介绍

RSA加密算法是由美国麻省理工学院的3名密码学者Rivest、Shamir、Adleman提出的一种基于大合数因式分解困难性的公共弄开密钥密码。由于它的安全、易懂，因此已成为目前应用最广的公开密钥密码

加密过程

随机选择两个大素数p和q，p和q都保密
计算n=pq，将n公开
计算 φ(n) =(p-1) * (q-1)，r=φ(n)，r和φ(n)保密
随机选取一个正整数e，1<e<r且e与r互素，正常环境下e取65537,其二进制数表示只有两个1，且为素数，将e公开，（n，e）就构成了用户公钥。
根据ed≡1 mod r ，（≡表示模同余运算），计算出d，将d，保密。（n，d）就构成了用户私钥
加密运算：C=M^e mod n
解密运算：M=C^e mod n

RSA参数选择
为确保RSA密码安全，必须认真选择RSA密码参数

p和q要足够大，n才足够大，才能对抗因式分解
p和q应为强素数
p和q的差要大，即|p-q|要大

以下是用python3.X实习的rsa加密算法，可以参考一下

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

import math
import random


#生成素数数组

def prime_array():
    arraya = []
    for i in range(2,2000):
        x = prime(i,2)
        if x:
            arraya.append(i)
    return arraya


#判断是否为素数
def prime(n,test_divisor):
    if math.sqrt(n) < test_divisor:
        return True
    if n % test_divisor == 0:
        return False
    else:
        return prime(n,test_divisor+1)


#互质e
def co_prime(r):
    while True:
        e = random.choice(range(2000))
        if r < e:
            x =gcd(e,r)
        else:
            x = gcd(r,e)
        if x == 1:
            break
    return e


#最大公约数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a % b)

#ed mod r =1
def find_d(e,r):
    for d in range(10000000):
        x = (e*d) % r
        if x == 1:
            return d

#生成公钥私钥的基本条件
def test():
    a = prime_array()
    print("前2000个素数：",a)
    p = random.choice(a)
    q = random.choice(a)
    print("随机抽取两个素数p&q，p=",p,"q=",q)
    n = p*q
    r = (p-1)*(q-1)#fy
    e = co_prime(r)
    print("根据互质得到e=",e)
    d = find_d(e,r)
    print("求到模逆元d，d=",d)
    pbvk=(n,e,d)
    return pbvk

#生成public key & private key
def generate_pbk_pvk(a,zx):
    pbk = (a[0],a[1])
    pvk = (a[0],a[2])
    print("pbk:",pbk,"pvk；",pvk)
    if zx == 0:
        return pbk
    if zx == 1:
        return pvk

#加密
def encryption(mw,ned):
# 密文b = 明文a的e次方 模 n，ned为公钥
#mw为明文a，ned【1】是e，ned【0】是n
     B = pow(mw,ned[1]) % ned[0]
     return B

#解密
def decode(mw,ned):
    C = pow(mw,ned[1]) % ned[0]
    return C

if __name__=='__main__':
    pbvk = test()
    pbk = generate_pbk_pvk(pbvk, 0) #公钥 if 0 return pbk if 1 return pvk
    A = int(input("请输入明文（需小于%d): " % pbk[0]))
    while A >= pbk[0]:
        A = int(input("明文大于%d,请重新输入:" % pbk[0]))
        if not A >= pbk[0]:
            break
    B = encryption(A,pbk) #加密
    print("生成的密文是: ", B)
    pvk = generate_pbk_pvk(pbvk, 1) #私钥
    C = decode(B,pvk) #解密
    print("解密后的明文是  : ", C)
    if A==C:
        print("加密前的明文和解密后的明文一样")
    else:
        print("加密前的明文和解密后的明文不一样")

这个代码只是最基础的，只能实现一些数字加密与解密，代码参考熊與猫v如果有什么不足还请大佬们指教