第四次实践性作业

1、用Python或Sage实现RSA算法的加密、解密、签名/验证签名

基本思路：
1.随机选两个大素数p和q，构造N = p * q
2.计算欧拉函数fn = (p - 1) * (q - 1)
3.随机选e，e与fn互素，gcd(fn, e) = 1
4.计算d，d是e的乘法逆元，e * d ≡ 1 (mod fn)

重点难点：
扩展欧几里德，素性测试，快速幂模
参考博客：7hat, Estimator

import math
import random


def gcd(p, q):
    while  q != 0:
        p, q = q, p % q
    return p


def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)  # q = GCD(a, b) = GCD(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

# 筛出素数表
def primeList(n):
    l = list(range(1, n + 1))
    l[0] = 0
    for i in range(2, n + 1):
        if l[i - 1] != 0:
            for j in range(i * 2, n + 1, i):
                l[j - 1] = 0
    prime = [x for x in l if x != 0]
    return prime


def selectE(fn, halfKeyLen):
    while True:
        e = random.randint(0, 1 << int(halfKeyLen))
        x, y ,q = ext_euclid(e, fn)
        if q == 1:
            return e


def calD(fn, e):
    x, y, q = ext_euclid(fn, e)
    if y < 0:
        return fn + y
    return y


def encryption(m, e, n):
    # c = m ** e % n
    return QuickPow(m, e, n)


def decryption(c, d, n):
    # m = c ** d % n
    return QuickPow(c, d, n)

# 快速幂模运算，把b拆分为二进制，遍历b的二进制，当二进制位为0时不计入计算
def QuickPow(a, b, MOD):
    ret = 1
    a = a % MOD
    # 这里我们不需要考虑b<0，因为分数没有取模运算
    while b > 0:
        if b & 1:
            # 不能写成ret = (ret % MOD) * (a % MOD),因为可能最后一次相乘的时候返回一个未除尽的数
            ret = (ret * a) % MOD
        # A(n) == A(n-1)^2，% c可以提高效率
        a = (a * a) % MOD
        #  相当于遍历二进制的b
        b >>= 1
    return ret


# ''' Miller-Rabin素性测试算法，测试k次
def Miller_Rabin(a, p): # a^(p-1) = 1 (mod p)
    p1 = p - 1
    s2 = p1 & -p1 # fetch the last 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


def IsPrime(p, k):
    if p == 2 or p == 3:
        return True
    if p < 2 or p % 2 == 0:
        return False
    for i in range(k):
        if not Miller_Rabin(random.randint(2, p-1), p):
            return False
    return True


def findPrime(halfKeyLen):
    while True:
        n = random.randint(0, 1 << int(halfKeyLen))
        if IsPrime(n, 10) == True:
            return n
# '''


def keyGen(keyLen):
    p = findPrime(keyLen // 2)
    q = findPrime(keyLen // 2)
    # print(p, q)
    n = p * q
    fn = (p - 1) * (q - 1)
    e = selectE(fn, keyLen // 2)
    d = calD(fn, e)
    return n, e, d

# '''
n, e, d = keyGen(1024)
x = random.randint(0, 1 << 256) # m
c = encryption(x, e, n)
m = decryption(c, d, n)

print("\nnum: ", x, "\nencryption: ", c, "\ndecryption: ", m, "\nx == m: ", x == m)
# '''

输出：

num: 36879361432602253382899580346501552994785005676258166868531621291871578004919
encryption: 57401526896249059529691420188536996411946422482135688383144190440230497001057124849270479044974871465309409970212549510443893961985443785908904163284178933167360971802234614408437297190590770074305706433714680735169222334777470388611463130267333702702163498909645560289607748808763845495632289826831248761137
decryption: 36879361432602253382899580346501552994785005676258166868531621291871578004919
x == m: True

2、用Python或Sage实现DH秘钥交换协议的。

p = 71      # prime
g = 7       # primitive root
xa = 5  # only Alice knows
xb = 12  # only Bob know

# Alice sends
ya = (g ** xa) % p
print("\nAlice sends: ", ya)

# Bob sends
yb = (g ** xb) % p
print("\nBob sends: ", yb)

# Alice calculates the shared secret key
ka = (yb ** xa) % p
print("\nAlice shared secret: ", ka)

# Bob calculates the shared secret key
kb = (ya ** xb) % p
print("\nBob shared secret: ", kb)

输出：

Alice sends: 51
Bob sends: 4
Alice shared secret: 30
Bob shared secret: 30