转发注明出处:
1976 年以前,所有的加密方法都是同一种模式:
(1)甲方选择某一种加密规则,对信息进行加密;
(2)乙方使用同一种规则,对信息进行解密。
由于加密和解密使用同样规则(简称 "密钥"),这被称为(Symmetric-key algorithm)。
这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。保存和传递密钥,就成了最头疼的问题。
1976 年,两位美国计算机学家 Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。
这种新的加密模式被称为 "非对称加密算法"。
(1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
(2)甲方获取乙方的公钥,然后用它对信息加密。
(3)乙方得到加密后的信息,用私钥解密。
如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。
1977 年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做。从那时直到现在,RSA 算法一直是最广为使用的 "非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有 RSA 算法。
这种算法非常,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长 RSA 密钥是 768 个二进制位。也就是说,长度超过 768 位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024 位的 RSA 密钥基本安全,2048 位的密钥极其安全。
RSA 算法需要一些数学知识,不过别怂,不难的。我总结了一下,大概需要以下三部分的知识:
接下来说下每个部分的内容:
1、互质关系: 如果两个正整数,除了 1 以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15 和 32 没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。
2、先说下 欧拉函数:φ(n) 为比 n 小但与 n 互素的正整数个数,称为 n 的欧拉函数。对任一素数 p, 有φ(n)=p-1,而对于两个不同的素数 p 和 q,则对 n=pq,可以证明φ(n)=φ(pq)=(p-1)(q-1)=φ(p)*φ(q)
3、模反元素: 如何求模反元素 (逆元),用辗转相除法,我在上一篇博客<> 有说,看了一定会懂的!
上面 3 点一定要 GET,不然不用往下看了~~
RSA 算法可归纳如下:
上面过程很重要!!! 刚开始看会有点懵逼,看下面的例子,一定会懂!
我们通过一个例子,来理解 RSA 算法。假设 Alice 想发送明文 9726 给 Bob,这之间的过程是怎样的?又是怎样生成公钥和私钥呢?
(1)Bob 生成密钥
Bob 选择两个互异素数 p=101 和 q=113,计算: n=pq=101*113=11413, φ(n)=(p-1)(q-1)=100*112=11200
由于加密密钥 e 必须与φ(n) 没有公因子,假设 Bob 随机选择了 e=3533,则用辗转相除法可求得: d=e-1=3533-1 mod 11200=6597
于是 Bob 公布他的公钥 KU={3533, 11413}, 将私钥 KR={6597, 11413} 保密。
(2)Alice 加密信息
由于 Bob 的公钥是公开的,任何人都可得到,因此 Alice 使用 Bob 的公钥来加密即将发送给 Bob 的明文信息。
Alice 计算: 97263533 mod 11413=5761, 然后在一个信道上发送密文 5761.
(3)Bob 解密密文
当 Bob 接收到密文 5761 时,他用他的私钥进行解密。
Bob 计算: 57616597 mod 11413=9726, 这样 Bob 就得到 Alice 发给他的明文信息了!!!
流程图
我画的流程图网址:
ReadMe:
源代码
View Code
- 1#RSA加密算法2 3 import random 4#p,
- q是两个不同的素数n = pq,
- 按理说应该随机产生,这里我用p = 101,
- q = 103为例5 6 P = 101 7 Q = 113 8 N = P * Q 9 global _E#把逆元定义为全局变量,才能在解密模块调用10 _E = 0#初始为0 11 12#欧拉公式: 如果n是质数,则φ (n) = n - 1。因为质数与小于它的每一个数,都构成互质关系13 F = (P - 1) * (Q - 1) 14 15 16#求最大公约数,若最大公约数是1,且m,
- n > 1,
- m与n不等,则说明m,
- n互质17 def comm_div(m, n) : #m > n 18 temp = m % n 19
- while (temp != 0) : 20 m = n 21 n = temp 22 temp = m % n 23
- if n == 1 : #说明互质,返回True 24
- return True 25 26 27#在1 - 9999之间随机选择一个整数e,条件是1 < e < F,且e与F互质28#互质即说明e,
- F的公因子有且仅有1 29 def e_product() : 30
- while True: 31 rand = random.randrange(2, F) 32
- if comm_div(F, rand) : 33 e = rand 34
- return e 35 36 37#用辗转相除法求质数e关于欧拉公式F的逆元38 def _e_product(e, F) : 39 a_list = [] 40 m = F 41 n = e 42 temp = m % n 43 44
- while (temp != 0) : 45 a = (m - temp) / n 46 a_list.append(a) 47 m = n 48 n = temp 49 temp = m % n 50 print("a_list:", a_list) 51 a_list.reverse()#逆序52 print("a_list_reverse:", a_list) 53 b_list = [] 54 b_list.append(1) 55 b_list.append(a_list[0]) 56 print("(最初插入的两个1及a_list[0])b_list:", b_list) 57
- for i in range(len(a_list) - 1) : 58 b = b_list[ - 1] * a_list[i + 1] + b_list[ - 2] 59 b_list.append(b) 60 61 print("b_list", b_list) 62#a_list存放的是商数,如果商数个数是偶数b_list[ - 1]即为所求逆元63#若为奇数,F - b_list[ - 1]为所求的逆元64
- if len(a_list) % 2 == 0 : #偶数65
- return b_list[ - 1] 66
- else: 67
- return F - b_list[ - 1] 68 69 70#传入明文 (数字)和公钥,进行加密,
- 返回密文71 def core_encryption(clear_text, e, N) : 72 clear = clear_text 73
- for i in range(e - 1) : 74 clear_text = clear_text * clear 75 cipher_text = clear_text % N 76
- return cipher_text 77 78 79 def encryption(clear_text) : 80 clear_text = int(clear_text) 81 e = e_product() 82 print("随机产生的e:%s" % e) 83 global _E#对全局变量进行重新赋值,需要global 84 _E = _e_product(e, F) 85#print("逆元_e:", _E) 86#print("逆元类型:", type(_E)) 87 print("公钥KU:%d,%d\n私钥KR:%d,%d" % (e, N, _E, N)) 88 cipher_text = core_encryption(clear_text, e, N) 89
- return cipher_text 90 91 92#根据之前加密生成的私钥进行解密,所以必须先有加密才行的93 def decryption(cipher_text, _e, N) : 94 cipher_text = int(cipher_text) 95 cipher = cipher_text 96#print(_e) 97#print("逆元_e类型:", type(_e)) 98
- for i in range(_e - 1) : 99 cipher_text = cipher_text * cipher 100 clear_text = cipher_text % N 101
- return clear_text 102 103 104
- if __name__ == "__main__": 105
- while True: 106 print("必须先加密后解密!".center(50, "-")) 107 choice = input("Input E for encryption or D for decryption:") 108
- if choice == "E": 109 clear_text = input("请输入明文(只允许数字):") 110
- if clear_text.strip().isalnum() : 111 print("加密成功!密文为:%d" % encryption(clear_text)) 112
- if choice == "D": 113 cipher_text = input("请输入密文:") 114
- if cipher_text.strip().isalnum() : 115 print("解密成功!明文为:%d" % decryption(cipher_text, _E, N))
问题
在测试时我遇到了下面这个问题
- 1 C: \Python34\python3.exe C: /Users/Administrator / PycharmProjects / xingxi / playfair / RSA.py 2--------------------必须先加密后解密!---------------------3 Input E
- for encryption or D
- for decryption: E 4请输入明文 (只允许数字) : 9726 5随机产生的e: 2147 6 a_list: [5.0, 4.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 1.0, 1.0, 1.0] 7 a_list_reverse: [1.0, 1.0, 1.0, 2.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 4.0, 5.0] 8(最初插入的两个1及a_list[0]) b_list: [1, 1.0] 9 b_list[1, 1.0, 2.0, 3.0, 8.0, 11.0, 19.0, 30.0, 49.0, 79.0, 128.0, 591.0, 3083.0] 10公钥KU: 2147,
- 11413 11私钥KR: 3083,
- 11413 12加密成功!密文为: 5200 13--------------------必须先加密后解密!---------------------14 Input E
- for encryption or D
- for decryption: D 15请输入密文: 5200 16 Traceback(most recent call last) : 17 File "C:/Users/Administrator/PycharmProjects/xingxi/playfair/RSA.py",
- line 116,
- in18 print("解密成功!明文为:%d" % decryption(cipher_text, _E, N)) 19 File "C:/Users/Administrator/PycharmProjects/xingxi/playfair/RSA.py",
- line 99,
- indecryption 20
- for i in range(_e - 1) : 21 TypeError: 'float'object cannot be interpreted as an integer 22 23 Process finished with exit code 1
现在已经解决了,问题出在了下面第 6 行代码,rang() 函数里面不能是 float 型,只需要 int(_e-1) 转型即可解决!
- 1 def decryption(cipher_text, _e, N) : 2 cipher_text = int(cipher_text) 3 cipher = cipher_text 4#print(_e) 5#print("逆元_e类型:", type(_e)) 6
- for i in range(_e - 1) : 7 cipher_text = cipher_text * cipher 8 clear_text = cipher_text % N 9
- return clear_text
你可能会说,毛线,这么简单的坑你都跳 (鄙视脸)。
好吧,这都怪我在这之前输出了一条测试 print("_e:%d" % _e),然后我运行时看到输出的是整型,就蒙比了,心想: 明明是 int 型,怎么会爆错说 float 型!!!这大概就是所谓的被自己挖的坑坑到怀疑人生吧~~
测试 (为了方便我日后再来看,一些打印测试我没有去除)
View Code
- 1 C: \Python34\python3.exe C: /Users/Administrator / PycharmProjects / xingxi / playfair / RSA.py 2--------------------必须先加密后解密!---------------------3 Input E
- for encryption or D
- for decryption: E 4请输入明文 (只允许数字) : 9726 5随机产生的e: 4031 6 a_list: [2.0, 1.0, 3.0, 1.0, 1.0, 17.0, 2.0, 1.0, 3.0] 7 a_list_reverse: [3.0, 1.0, 2.0, 17.0, 1.0, 1.0, 3.0, 1.0, 2.0] 8(最初插入的两个1及a_list[0]) b_list: [1, 3.0] 9 b_list[1, 3.0, 4.0, 11.0, 191.0, 202.0, 393.0, 1381.0, 1774.0, 4929.0] 10公钥KU: 4031,
- 11413 11私钥KR: 6271,
- 11413 12加密成功!密文为: 325 13--------------------必须先加密后解密!---------------------14 Input E
- for encryption or D
- for decryption: D 15请输入密文: 325 16解密成功!明文为: 9726 17--------------------必须先加密后解密!---------------------18 Input E
- for encryption or D
- for decryption: E 19请输入明文 (只允许数字) : 25 20随机产生的e: 6403 21 a_list: [1.0, 1.0, 2.0, 1.0, 75.0, 2.0] 22 a_list_reverse: [2.0, 75.0, 1.0, 2.0, 1.0, 1.0] 23(最初插入的两个1及a_list[0]) b_list: [1, 2.0] 24 b_list[1, 2.0, 151.0, 153.0, 457.0, 610.0, 1067.0] 25公钥KU: 6403,
- 11413 26私钥KR: 1067,
- 11413 27加密成功!密文为: 10272 28--------------------必须先加密后解密!---------------------29 Input E
- for encryption or D
- for decryption: D 30请输入密文: 10272 31解密成功!明文为: 25 32--------------------必须先加密后解密!---------------------33 Input E
- for encryption or D
- for decryption:
注: RSA 算法背景参考自
博客参考书籍: 信息安全概论 (凌捷 谢赞福 编著)
接下来一个月信息安全方面可能最多会再写一篇博客, 重心会放在人工智能和操作系统! fight!
来源: http://www.cnblogs.com/0zcl/p/6120389.html