CANS_Exercise_4

RSA的实现

1.加密算法

其中public_key是一个元组，格式(e, n)，相应的算法是遍历plainText，将其char值转化为ascii，并通过 c = m ** e mod n来进行加密，

def encrypt(public_key, plainText):
    e, n = public_key
    templist = []
    # 取字符的ascii码来进行加密 c = m ** e mod n
    for text in list(plainText):
        templist.append(chr(ord(text)**e % n))
    cipherText = ''.join(templist)
    return cipherText

2.解密算法

类似于加密算法，只是通过 m = ** d mod n 来解密

def decrypt(private_key, cipherText):
    d, n = private_key
    templist = [chr(ord(text)**d % n) for text in cipherText]
    return ''.join(templist)

3.求乘法逆元算法

利用了EGCD算法

def inverse(e, euler):
    d = 0
    x1 = 0
    x2 = 0
    y1 = 0
    temp = euler
    '''
    # 利用欧几里德算法求乘法逆元 (x1, x2, x3) = (1, 0, euler) (y1, y2, y3)=(0, 1, e)
    # 第一步：Q = x3 / y3
    # 第二步：t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
    # 第三步: x1, x2, x3 = y1, y2, y3
    # 第四步：y1, y2, y3 = t1, t2, t3
    # 利用其算法直到 y3 == 1 为止，d = y2
    # 若 y3 == 0 不存在逆元
    '''
    while e > 0:
        temp1 = temp / e
        temp2 = temp - temp1 * e
        temp = e
        e = temp2
        x = x2 - temp1 * x1
        y = d - temp1 * y1
        x2 = x1
        x1 = x
        d = y1
        y1 = y
        if temp == 1:
            return d + euler

4.生成公钥密钥算法

生成的公钥密钥是存储在数组key里面的，其中key[0]是公钥，key[1]是密钥

import random

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


def gen(p, q):
    n = p * q
    euler = (p - 1) * (q - 1)

    # generate (e,n)
    e = random.randrange(1, euler)
    # 确保 e 是在Zn*域中
    while gcd(e, euler) != 1:
        e = random.randrange(1, euler)

    # 求解密密钥d
    d = inverse(e, euler)

    return [(e, n), (d, n)]

5.签名和验签的实现

这里的加密算法使用了RSA中的加密方式，使用了hashlib中的sha256来生成摘要h(m)，然后再通过私钥加密。
验证里面即是通过相同的h(mes)的计算方法来和signed_text通过公钥解密后的h(m)对比是否相同来确定正确与否。
以下是相关实现代码

import hashlib

#使用了自己的私钥对m摘要的 h(m) 进行加密
def sign(text, private_key):
    h = hashlib.sha256()
    hashValue = h.update(text).hexdigest()
    return encrypt(private_key, hashValue)


def checkSign(signed_text, mes, public_key):
    h = hashlib.sha256()
    hashValue = h.update(mes).hexdigest()
    return (hashValue == decrypt(public_key, signed_text))

---

Diffie-Hellman秘钥交换协议

这是一个通过共享的素数p和生成元r来生成交换的公钥的函数

# a prime number: p
# a primitive root of p: r
def diffieHellman(p, r, private_key):
    """
    :type p: int
    :type r: int
    :type private_key: int
    :rtype: int
    """
    return r ** private_key % p

之后就将自身计算得出的公钥发给对方

---

当得到对方的公钥后，再通过自身的私钥来计算sercet_key
公式是sercet_key = public_key ** private_key % p

def genShareKey(p, private_key, public_key):
    """
    :type p: int
    :type private_key: int
    :type public_key: int
    :rtype: int
    """
    return public_key ** private_key % p