| 实 验 目 的 | 1. 熟悉RSA算法，理解其原理 2.网上找相关资料实现RSA算法 |
| 实 验 环 境 |
Python2+pycharm |
| 实 验 步 骤 | 算法基本思路： 1.公钥与私钥的生成： (1)随机挑选两个大质数 p 和 q，构造N = p*q； (2)计算欧拉函数φ(N) = (p-1) * (q-1)； (3)随机挑选e，使得gcd(e, φ(N)) = 1，即 e 与 φ(N) 互素； (4)计算d，使得 e*d ≡ 1 (mod φ(N))，即d 是e 的乘法逆元。 此时，公钥为（e, N），私钥为（d, N），公钥公开，私钥自己保管。 2.加密信息： (1)待加密信息（明文）为 M，M < N；（因为要做模运算，若M大于N，则后面的运算不会成立，因此当信息比N要大时，应该分块加密） (2)密文C = Me mod N (3)解密Cd mod N = (Me)d mod N = Md*e mod N ； 要理解为什么能解密？要用到欧拉定理aφ(n) ≡ 1 (mod n)，再推广：aφ(n)*k ≡ 1 (mod n)，得：aφ(n)*k+1 ≡ a (mod n) 注意到 e*d ≡ 1 mod φ(N)，即：e*d = 1 + k*φ(N)。 因此，Md*e mod N = M1 + k*φ(N) mod N = M 我的理解就是：服务器用客户的公钥加密信息发给我，然后客户用私钥解密。 3.数字签名： (1)密文C = Md mod N (2)解密M = Ce mod N = (Md)e mod N = Md*e mod N = M ；（原理同上） 我的理解就是：我用自己的密钥加密签名，别人用我的公钥解密可以看到这是我的签名。注意，这个不具有隐私性，即任何人都可以解密此签名。
|
| 实 验 结 果 |
PlainText: 10855225086173939930078735827643414599362568936 5889113498649228757882549939690 Encryption of plainText: 9643670328277461591386781304632351444421180914158605020517 8025562797860283631742532185008096175459168035060137521984 5956515264084827140511733851353574504602300562727743205958 6030439105507942610235389151100878860062259683721684449352 6995565035371405430097017917181968434081359786502175905113 26578152573016111 Decryption of cipherText: 1085522508617393993007873582764341459936256893658891134986 49228757882549939690 The algorithm is correct: True |
| 实 验 总 结 |
本实验可用老师MixCS软件生成素数p，q，从而生成公钥和私钥，鉴于网上有相关介绍，本人还是坚持用python试一试。
加载python强大的第三方库实现RSA算法，如：RSA模块，Pycrypto模块等，这些模块都能自动生成极大素数p，q，进而生成公钥，私钥，因此与老师的所给的参考文件中的公钥,私钥不同，我还是希望一直用python做完实验的
|
附录
import random def 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 result def 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<<halfkeyLength) if n % 2 != 0: found = True #If n satisfy primeTest 10 times, then n should be a prime number for i in range(0, 10): if primeTest(n) == "composite": found = False break if found: return n def extendedGCD(a, b): #a*xi + b*yi = ri if b == 0: return (1, 0, a) #a*x1 + b*y1 = a x1 = 1 y1 = 0 #a*x2 + b*y2 = b x2 = 0 y2 = 1 while b != 0: q = a / b #ri = r(i-2) % r(i-1) r = a % b a = b b = r #xi = x(i-2) - q*x(i-1) x = x1 - q*x2 x1 = x2 x2 = x #yi = y(i-2) - q*y(i-1) y = y1 - q*y2 y1 = y2 y2 = y return(x1, y1, a) def selectE(fn, halfkeyLength): while True: #e and fn are relatively prime e = random.randint(0, 1<<halfkeyLength) (x, y, r) = extendedGCD(e, fn) if r == 1: return e def computeD(fn, e): (x, y, r) = extendedGCD(fn, e) #y maybe < 0, so convert it if y < 0: return fn + y return y def keyGeneration(keyLength): #generate public key and private key p = findPrime(keyLength/2) q = findPrime(keyLength/2) n = p * q fn = (p-1) * (q-1) e = selectE(fn, keyLength/2) d = computeD(fn, e) return (n, e, d) def encryption(M, e, n): #RSA C = M^e mod n return fastExpMod(M, e, n) def decryption(C, d, n): #RSA M = C^d mod n return fastExpMod(C, d, n) #Unit Testing (n, e, d) = keyGeneration(1024) #AES keyLength = 256 X = random.randint(0, 1<<256) C = encryption(X, e, n) M = decryption(C, d, n) print "PlainText:", X print "Encryption of plainText:", C print "Decryption of cipherText:", M print "The algorithm is correct:", X == M