本文共 1769 字，大约阅读时间需要 5 分钟。

【题目】

实现 RSA 公钥密码算法，具体要求：

    A. 随机选择两个长度不小于 64 比特的整数批 p,q，并选择合适的素检测算 法检测其素性, 计算模 n=pq。     B. 随机选择一个长度不小于 16 比特的整数 e，判断其是否适合作为公钥， 直至找到合适的公钥，利用欧几里得算法计算私钥 d。     C. 任选一个长度不小于 64 比特的整数进行加密，然后使用私钥解密。

【实现代码】

# -*- coding: utf-8 -*-"""Created on Wed Jan 10 19:33:44 2018@author: HP"""import randomfrom time import clockdef fastExpMod(b, e, m):    """    e = e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n)    b^e = b^(e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n))        = b^(e0*(2^0)) * b^(e1*(2^1)) * b^(e2*(2^2)) * ... * b^(en*(2^n))     b^e mod m = ((b^(e0*(2^0)) mod m) * (b^(e1*(2^1)) mod m) * (b^(e2*(2^2)) mod m) * ... * (b^(en*(2^n)) mod m) mod m    """    result = 1    while e != 0:        if (e&1) == 1:            # ei = 1, then mul            result = (result * b) % m        e >>= 1        # b, b^2, b^4, b^8, ... , b^(2^n)        b = (b*b) % m    return resultdef primeTest(n):    q = n - 1    k = 0    #Find k, q, satisfied 2^k * q = n - 1    while q % 2 == 0:        k += 1;        q //= 2    a = random.randint(2, n-2);    #If a^q mod n= 1, n maybe is a prime number    if fastExpMod(a, q, n) == 1:        return "inconclusive"    #If there exists j satisfy a ^ ((2 ^ j) * q) mod n == n-1, n maybe is a prime number    for j in range(0, k):        if fastExpMod(a, (2**j)*q, n) == n - 1:            return "inconclusive"    #a is not a prime number    return "composite"def findPrime(halfkeyLength):    while True:        #Select a random number n         n = random.randint(0, 1<
   
       a*xi + b*yi = a*yi+1 + b*(xi+1 - [a/b]*yi+1)    xi = yi+1    yi = xi+1 - [a/b]*yi+1    """    tmp = x    x = y    y = tmp - (a//b) * y    return (x, y, r)def selectE(fn, halfkeyLength):    while True:        #e and fn are relatively prime        e = random.randint(0, 1<
   

转载地址：http://xhaii.baihongyu.com/