RSA-python编程简单实现

RSA-python简单实现

狙个栗子

15814人浏览 · 2022-04-20 20:21:59

狙个栗子 · 2022-04-20 20:21:59 发布

RSA_python简单编程实现

一.RSA算法简述

rsa算法是一种非对称加密算法，其安全性是建立在大素数难以分解的基础上的，即将两个大素数相乘十分容易，但想对其乘积进行分解却很困难，所以可以将其乘积公开作为加密密钥

二. 密钥生成过程

1.选择两个大素数p和q

2.计算两素数的乘积 n =p*q,和Φ(n)=(p-1)(q-1)

3.选择大于1并且小于Φ(n)的随机整数e，使得gcd(e,Φ(n))=1

4.计算e在modΦ(n)下的乘法逆元d

5.最后得出公钥为（e，n），私钥为（d，n）

三. RSA加解密过程

1. 加密

对于明文M，则有密文C=M^e mod n

2. 对于密文C，则有明文M=C^d mod n

声明：以上理论来自该处

四.python实现简易RSA算法

- 在了解了RSA算法的基本的工作流程，那么就可以编写代码了

- 话不多说看代码

from math import sqrt

def Cnotrol():
    d = 0
    x = int(input('请输入你的选择的功能::RSA加密为0，RSA解密为1，分解查找P与Q为2,退出请按9:'))
    qt = 1
    while qt:
        if x == 0:
            print('----------------加密----------------')
            print('---------请输入P,Q,E,M(明文)---------')
            p = int(input('输入P:'))
            q = int(input('输入Q:'))
            e = int(input('输入E:'))
            Flag = apnjudg(p, q, e)
            if Flag == 0:
                m = int(input('请输入M:'))
                encryption(m, e, p * q)
                Cnotrol()
            else:
                break

        elif x == 1:
            print('----------------解密----------------')
            print('---------请输入P,Q,E,C(密文)---------')
            p = int(input('输入P:'))
            q = int(input('输入Q:'))
            e = int(input('输入E:'))
            fi = (p - 1) * (q - 1)
            for i in range(fi):  # 求逆元d
                if e * i % fi == 1:
                    d = i
                    break
            print("逆元d的值为：", d)
            apnjudg(p, q, d)
            c = int(input('请输入C:'))
            decode(c, d, p * q)
            Cnotrol()

        elif x == 2:
            print('----------------拆解素数乘积----------------')
            n = int(input('输入乘积N:'))
            broken(n)
            Cnotrol()

        else:
            print("感谢您的使用")
            break
        qt = 0



def encryption(m, e, n):
    s = m % n
    for i in range(1, e):
        s = (s * (m % n)) % n
    print('你所加密的密文是：', s)


# 解密
def decode(c, d, n):
    s = c % n
    for i in range(1, d):
        s = (s * (c % n)) % n
    print('你所解密的明文是：', s)


# p,q,e质数判断
def apnjudg(p, q, e):
    Li = [p, q, e]
    flag = 0
    for x in range(0, 3):
        if int(Li[x]) > 2:
            # 查看因子
            # sqrt()平方根函数减小计算周期
            for i in range(2, int(sqrt(Li[x]))+1):
                if (int(Li[x]) % i) == 0:
                    print(int(Li[x]), "不是质数")
                    print(i, "乘于", int(Li[x]) // i, "是", int(Li[x]))
                    flag += 1
                    break
                else:
                    continue
            if flag == 0:
                print(int(Li[x]), "是质数")
            else:
                print("QAQ您的输入有误(存在非质数)，程序退出QAQ")
                break
        # 如果输入的数字小于或等于 2，不是质数
        else:
            print(int(Li[x]), "不是质数")
            flag += 1
            continue
    return flag


# 拆解获得素数p,q
def broken(n):
    if n < 10000000:
        for i in range(1, 10000):
            for t in range(1, 10000):
                if n == i * t:
                    print(i, t)
                    break

if __name__ == '__main__':
    Cnotrol()