hello,everybody!
来一个迟到的七夕祝福!
场景:
假设李雷和韩梅梅生活在1984一样的一个极权世界,七夕到了,李雷想向韩梅梅表达爱意.但是他又不能以明文给韩梅梅传递这个信息.要不big brother就会打爆他的头.因为法律这玩意儿可怕哟!
问题:
如何通过加密传递' I love you!' 或者 '我爱你' 或者'520'这样的信息?
同时敌人如big brother截获密文以后不能将其翻译为原始信息
解决方案:加密信息
一.low方案:凯撒密码
原理:
1.我们假设26个英文字母用一些数字来代替
比如a对应97,b对应98.....依次得出x对应120,y对应121,z对应122
我们可以把这种对应关系写在一张表中,就是明文密文对照表
就像这样
2.将要发送的英文字母翻译为对应的数字如'i love you'翻译为(暂且不管空格)
105
108
111
118
101
121
111
117
3.将这一串数字发给韩梅梅,如果韩梅梅也了解这种字母和数字的对应关系或者她也有一张上面的明文密文替换表.她就能明白你的意思啦.
这就是简单的替代密码技术,不需要密钥,只要传递消息的双方了解转换规则(加密算法)即可以完成消息传递.当然这还不是凯撒密码
而所谓的凯撒密码,其实就是上面的方法的一个加强版,增加一个钥匙key,在转换一个字符的时候,不以在对照表中查到的对应数字作为密文,而是将对应的数字加上一个key所对应的字符作为密文.
如:
假设选取钥匙key = 3
那么'i love you'加密后的密文就变成了'l oryh brx'
等韩梅梅收到这条消息,再按照相反的顺序解密(用对应的数字减key再翻译)即可得到原来的消息.
凯撒密码的代码请参看
(1条消息) python密码学凯撒密码_凯撒密码在Python_culing2941的博客-CSDN博客
def encrypt(string, shift):cipher = ''for char in string:if char == ' ':cipher = cipher + charelif char.isupper():cipher = cipher + chr((ord(char) + shift - 65) % 26 + 65)else:cipher = cipher + chr((ord(char) + shift - 97) % 26 + 97)return ciphertext = input("enter string: ")
s = int(input("enter shift number: "))
print("original string: ", text)
print("after encryption: ", encrypt(text, s))结果:
enter string: i love you
enter shift number: 3
original string: i love you
after encryption: l oryh brx
凯撒密码比开始的简单替换密码,多了密钥这个环节.所以即使敌人知道你用了替换这种把戏,不知道你的key的情况下要想破解你的密文还是有一定的难度(不是不能破解,如:可以通过假设key为1,key为2,key为3...通过穷举来暴力破解)
通过在加密时,每加密一个字符就修改一次key,可以有效增加解密的难度.相关的发展,大家可以搜索弗吉尼亚密码,而弗吉尼亚密码可以通过统计规律性来破解.著名小说家爱伦坡的作品《金甲虫》详细解释了破译过程。更复杂的密码可以参看二战时德军的密码机恩尼格玛，而对恩尼格玛的破译直接指向了伟大的阿伦.图灵。相关电影《模仿游戏》。
这些故事在一本叫《码书：编码和解码的战争》有详尽的描述。
回到本文：
现在我们假设李雷用凯撒密码给韩梅梅传递消息，同时假设big brother也知道凯撒密码算法。那么问题就来了，李雷要如何把key告诉韩梅梅呢？
为解决这个问题，出现了迪菲.赫尔曼公钥加密算法.而我们接下来要说的RSA非对称加密技术就是这种在迪菲.赫尔曼公钥加密思想上发展而来的.
二.high方案:RSA公钥加密
先来解释两个术语:
1.对称加密:加密和解密使用的是同一个钥匙key
2.非对称加密:加密和解密使用的不是同一个钥匙key,加密使用的是公钥,而解密使用私钥
RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的.RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制
算法思想
1.选取两个素数p.q (保密) 2.计算r = p*q (公开) 3.计算欧拉函数 φ(r) = (p-1)*(q-1) (保密) 4.产生公钥e 选取随机整数,满足gcd(e,φ(r)) = 1,即e和φ(r)互质 5.计算私钥d,满足d*e (mod φ(r)) = 1 6.将明文x(值在0-(r-1))自乘e次幂mod r 得到密文y 7.将密文y自乘d 次幂 mod r 还原文明文x
代码实现(python)
先看需要用到的几个函数
1.判断质数
def isPrimeNumber(n):'''判断质数'''for i in range(2,int(n**0.5+1)):if n % i == 0:return Falseelse:return True2.求最大公约数(欧几里得算法)
def gcd(n1,n2):'''最大公约数'''if n1 < n2:n1,n2 = n2,n1if n1 % n2 == 0:return n2else:return gcd(n2,n1%n2)3.生成公钥和私钥
def keysBuilder():'''生成公钥和私钥:return:'''# 步骤1p = random.choice(list(filter(isPrimeNumber,range(300,400))))q = random.choice(list(filter(isPrimeNumber,range(300,400))))while p == q:q = random.choice(list(filter(isPrimeNumber,range(300,400))))print('选取的两个素数分别为{}和{},请不要泄露这两个数字'.format(p,q))# 步骤2r = p * q# 步骤3fai_r = (p-1) * (q-1)print('欧拉函数的值为:',fai_r)# 步骤4e = 0found_e = Falsewhile not found_e:e = random.randint(2,fai_r)if isPrimePair(e,fai_r):found_e = True# 步骤5d = 0i = 2while i < fai_r:if i * e % fai_r == 1 and i != e:d = ibreaki += 1# 返回公钥对和私钥对public_key = (e,r)print('为您生成的公钥对为',public_key,'您可以将其公开')private_key = (d,r)print('为您生成的私钥对为', private_key, '请妥善保管,后续将用于解密!')return public_key,private_key4.加密/解密函数
def numEncryption(num,pb_key):'''数字加密'''cypher_num = num**pb_key[0] % pb_key[1]return cypher_numdef numDecryption(cypherNum,pv_key):'''数字解密'''return cypherNum**pv_key[0] % pv_key[1]到这里就基本完成了RSA的主要工作,但是还只能处理待发送信息为数字的情况.如何发送字符信息呢?其实很简单,只需要借助python的ord()和chr()函数先完成字符串和数字之间的转换.代码如下:
def txtEncryption(astring,pb_key):'''文本加密'''res = ' 'for c in astring:c_num = ord(c)res +=' '+ chr(numEncryption(c_num,pb_key))print('加密结果为:',res)return resdef txtDecryption(cyphertext,pv_key):res =''cypherNum_list =[ord(x) for x in cyphertext.split()]for cy_num in cypherNum_list:c = chr(numDecryption(cy_num,pv_key))res += creturn res最后是完整代码及测试
# RSA公钥加密算法
'''步骤:1.选取两个素数p.q (保密)2.计算r = p*q (公开)3.计算欧拉函数 φ(r) = (p-1)*(q-1) (保密)4.产生公钥e 选取随机整数,满足gcd(e,φ(r)) = 1,即e和φ(r)互质5.计算私钥d,满足d*e (mod φ(r)) = 16.将明文x(值在0-(r-1))自乘e次幂mod r 得到密文y7.将密文y自乘d 次幂 mod r 还原文明文x
'''import random# def powerMod(base_num,power_num,mod_num):
# '''
# 计算次幂取模的函数,参数全部为正整数
# :param base_num: 底数
# :param power_num: 幂指数
# :param mod_num: 模数
# :return:
# '''
# if power_num == 1:
# return base_num % mod_num
# else:
# return powerMod(base_num,power_num-1,mod_num)*base_num % mod_numdef isPrimeNumber(n):'''判断质数'''for i in range(2,int(n**0.5+1)):if n % i == 0:return Falseelse:return Truedef gcd(n1,n2):'''最大公约数'''if n1 < n2:n1,n2 = n2,n1if n1 % n2 == 0:return n2else:return gcd(n2,n1%n2)def isPrimePair(n1,n2):'''判断两个数字是否互质'''if gcd(n1,n2) == 1:return Trueelse:return Falsedef keysBuilder():'''生成公钥和私钥:return:'''# 步骤1p = random.choice(list(filter(isPrimeNumber,range(300,400))))q = random.choice(list(filter(isPrimeNumber,range(300,400))))while p == q:q = random.choice(list(filter(isPrimeNumber,range(300,400))))print('选取的两个素数分别为{}和{},请不要泄露这两个数字'.format(p,q))# 步骤2r = p * q# 步骤3fai_r = (p-1) * (q-1)print('欧拉函数的值为:',fai_r)# 步骤4e = 0found_e = Falsewhile not found_e:e = random.randint(2,fai_r)if isPrimePair(e,fai_r):found_e = True# 步骤5d = 0i = 2while i < fai_r:if i * e % fai_r == 1 and i != e:d = ibreaki += 1# 返回公钥对和私钥对public_key = (e,r)print('为您生成的公钥对为',public_key,'您可以将其公开')private_key = (d,r)print('为您生成的私钥对为', private_key, '请妥善保管,后续将用于解密!')return public_key,private_keydef numEncryption(num,pb_key):'''数字加密'''cypher_num = num**pb_key[0] % pb_key[1]return cypher_numdef numDecryption(cypherNum,pv_key):'''数字解密'''return cypherNum**pv_key[0] % pv_key[1]def txtEncryption(astring,pb_key):'''文本加密'''res = ' 'for c in astring:c_num = ord(c)res +=' '+ chr(numEncryption(c_num,pb_key))print('加密结果为:',res)return resdef txtDecryption(cyphertext,pv_key):res =''cypherNum_list =[ord(x) for x in cyphertext.split()]for cy_num in cypherNum_list:c = chr(numDecryption(cy_num,pv_key))res += creturn resif __name__ == '__main__':# for i in range(1,11):# print(powerMod(2,i,11))# print('==============')# for i in range(1, 11):# print(powerMod(3,i,11))# print('==============')# for i in range(1, 11):# print(powerMod(6,i,11))# print('==============')# print(isPrimeNumber(6))# print(isPrimePair(11,22))pb_key,pv_key = keysBuilder()print(pb_key,pv_key)# origin = 520# cyphertxt = numEncryption(origin,pb_key)# print('加密的结果为:',cyphertxt)# print('解密的结果为:',numDecryption(cyphertxt,pv_key))origin = 'I love you !'cyphertxt = txtEncryption(origin,pb_key)print('加密的结果为:',cyphertxt)print('解密的结果为:',txtDecryption(cyphertxt,pv_key))
其中一个结果:
选取的两个素数分别为331和389,请不要泄露这两个数字
欧拉函数的值为: 128040
为您生成的公钥对为 (8567, 128759) 您可以将其公开
为您生成的私钥对为 (72143, 128759) 请妥善保管,后续将用于解密!
(8567, 128759) (72143, 128759)
加密结果为: 𖧲 듥 씰 노 큌 𗻠 듥 눘 노 듥
加密的结果为: 𖧲 듥 씰 노 큌 𗻠 듥 눘 노 듥
解密的结果为: I love you !
李磊.韩梅梅的信息传递过程为:
1.韩梅梅生成自己的公钥对(8567,128759)并公开，所有人都能得到，所以不需要单独传递key
2.李雷利用韩梅梅的公钥对加密原始消息'I love you',得到密文 '𖧲 듥 씰 노 큌 𗻠 듥 눘 노 듥 '
3.李雷将密文发送给韩梅梅
4.韩梅梅利用自己的私钥对(72143,128759)解密密文得到原文'I love you'
5.假设老大哥截获了密文,但是他只直到韩梅梅的公钥对,无法计算出韩梅梅的私钥,所以无法解密
当然故事还远没有结束.
可能情况1:
RSA算法的安全性来源于对大质数的因式分解问题在数学上是一个很难计算的问题.如果老大哥能在合理的时间内将公钥中的128759因式分解得到331和389.那么他就能计算出私钥72143进而解密密文.一种高科技东东'量子计算机'可能会成为老大哥的秘密武器
可能情况2:
韩梅梅喜欢的其实是老大哥.所以她在公开了公钥对(8567, 128759)后,将p.q的值(选取的两个素数分别为331和389)直接告诉了老大哥.目的是检验有多少个李雷对自己心怀不轨,那么老大哥也能轻松破译李雷的密文,这个故事告诉我们安全系统中最不安全的因素其实是人.这个悲伤的故事的结局是:李雷卒!老大哥的名字叫Jim Green!!!
ref:
1.西蒙.辛格《码书：编码和解码的战争》
2.约翰.麦考密克《改变未来的九大算法》
3.蔡龙飞，许喜斌《计算机网络基础》
4.引用
百度百科：RSA算法_百度百科 (baidu.com)
(1条消息) python密码学凯撒密码_凯撒密码在Python_culing2941的博客-CSDN博客
35岁学python，也不知道为了啥？
