project for RSA

密码学

简单的描述

　　1. 使用随机函数生成一个大整数，介于512bits和1024bits之间。
　　2. 使用米勒拉宾算法进行素性测试
　　3. 使用快速幂来快速的进行加密解密操作，也就是幂运算取模。
　　4. 使用gcd来判断e是否和phin互素
　　5. 使用egcd来求d
　　6. 使用字典来对实现简单字符串和整数之间的映射
　　7. 使用md5来对文件内容进行映射

截图

源代码

import random
import hashlib
# return a^b mod n
def QuickPow(a, b, n):
    t = 1
    tmp = a % n
    while b > 0:
        if (b & 1):
            t = (t * tmp) % n
        tmp = tmp * tmp % n
        b >>= 1
    return t
# 选择一个a来对大整数p的素性测试
def MillerRabin(a, p):
    if (a & 1 == 0):
        return False
    p1 = p - 1
    s2 = p1 & -p1  # 找到最右边的1
    x = QuickPow(a, p1 // s2, p)
    if x == 1 or x == p1:
        return True
    while s2 > 1:
        x = (x * x) % p
        if x == 1:
            return False
        if x == p1:
            return True
        s2 >>= 1
    return False
# 对p进行测试k次
def IsPrime(p, k):
    if p == 2 or p == 3:
        return True
    if p < 2 or (p & 1) == 0:
        return False
    for i in range(k):
        if not MillerRabin(random.randint(2, p - 1), p):
            return False
    return True
# 获得一个介于512比特和1024比特的大素数
def getBigPrime():
    while True:
        tmp = random.randint(2 ** 512, 2 ** 1024)
        if IsPrime(tmp, 3):
            return tmp
# ax + by = d = gcd(a,b), 其中a>b
def Egcd(a, b):
    x1, y1, x2, y2 = 1, 0, 0, 1
    while (b):
        q = a // b
        r = a - b * q
        tmp_x, tmp_y = x2, y2
        x2, y2 = x1 - x2 * q, y1 - y2 * q
        x1, y1 = tmp_x, tmp_y
        a = b
        b = r
    return y1
# gcd(a,b)
def Gcd(a, b):
    while b > 0:
        tmp = a % b
        a, b = b, tmp
    return a
def EnCode(e, n):
    Str = input("请输入明文：")
    m = CharToInt(Str)
    print("相应的密文是：", QuickPow(m, e, n))
def DeCode(d, n):
    c = int(input("请输入密文："))
    m = IntToChar(QuickPow(c, d, n))
    print("相应的明文是：", m)
def CharToInt(string):
    abc_table = dict()
    for i in range(97, 123):
        abc_table[chr(i)] = i - 50
    abc_table[" "] = 10
    abc_table["!"] = 11
    print(abc_table)
    number = ""
    for s in string:
        number += str(abc_table[s])
    return int(number)
def IntToChar(number):
    number_table = dict()
    for i in range(97, 123):
        number_table[i - 50] = chr(i)
    number_table[10] = " "
    number_table[11] = "!"
    i = 0
    Str0 = str(number)
    Str = ""
    while i < len(Str0):
        Str += number_table[int(Str0[i:i + 2])]
        i += 2
    return Str
# 这里对文本进行hash，一个文本对应着唯一的hash值
def Signature(filename, d, n):
    f = open(filename, "r", encoding="utf-8")  # 将文本内容进行hash
    md5 = hashlib.md5()
    md5.update(f.read().encode("utf-8"))
    m = int(md5.hexdigest(), 16)
    print("对应文件的签名是：", QuickPow(m, d, n))
# 对明文进行hash，然后对密文进行解密
# 进行对比，值相同则验证签名成功
def Validation(filename, signature, e, n):
    f = open(filename, "r", encoding="utf-8")
    md5 = hashlib.md5()
    md5.update(f.read().encode("utf-8"))
    m = int(md5.hexdigest(), 16)
    m1 = QuickPow(signature, e, n)
    if m == m1:
        print("验证成功！")
    else:
        print("验证失败！")
def Main():
    p, q = getBigPrime(), getBigPrime()  # 选择两个大素数p，q
    phin = (p - 1) * (q - 1)
    n = p * q
    while True:  # 随机选择一个e
        e = random.randint(0, phin)
        if Gcd(phin, e) == 1:
            break
    d = Egcd(phin, e)  # 根据e来构造d
    if d < 0:
        d += phin
    while True:  # 用户交互界面
        print("请输入相应序号：\n 1. 输入明文加密\n 2. 输入密文解密\n 3.签名 \n 4.验证签名\n 5.离开")
        select = input()
        if select == "1":
            EnCode(e, n)
        elif select == "2":
            DeCode(d, n)
        elif select == "3":
            filename = input("请输入文件名: ")
            Signature(filename, d, n)
        elif select == "4":
            filename = input("请输入文件名: ")
            signature = int(input("请输入签名: "))
            Validation(filename, signature, e, n)
        elif select == "5":
            break
        else:
            print("输入有误，请重新输入！")
if __name__ == '__main__':
    Main()