作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！
加密和解密是自古就有技术了。经常看到侦探电影的桥段，勇敢又机智的主角，拿着一长串毫无意义的数字苦恼，忽然灵光一闪，翻出一本厚书，将第一个数字对应页码数，第二个数字对应行数，第三个数字对应那一行的某个词。数字变成了一串非常有意义的话：
主角喜极而泣……
这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密，而接收信息的人利用相同的密钥，来给信息解密。就好像一个带锁的盒子。发送信息的人将信息放到盒子里，用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥，这种加密称为对称加密（symmetric encryption）。
如果一对一的话，那么两人需要交换一个密钥。一对多的话，比如总部和多个特工的通信，依然可以使用同一套密钥。但这种情况下，对手偷到一个密钥的话，就知道所有交流的信息了。二战中盟军的情报战成果，很多都来自于破获这种对称加密的密钥。
二战中德军的传奇加密机：Enigma
为了更安全，总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构，恐怕很难维护这么多的密钥。在现代社会，每个人的信用卡信息都需要加密。一一设计密钥的话，银行怕是要跪了。
对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁，而总部保有钥匙， 那就容易了。特工将信息用锁锁到盒子里，谁也打不开，除非到总部用唯一的一把钥匙打开。只是这样的话，特工每次出门都要带上许多锁，太容易被识破身份了。 总部老大想了想，干脆就把造锁的技术公开了。特工，或者任何其它人，可以就地取材，按照图纸造锁，但无法根据图纸造出钥匙。钥匙只有总部的那一把。
上面的关键是锁和钥匙工艺不同。知道了锁，并不能知道钥匙。这样，银行可以将“造锁”的方法公布给所有用户。每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到，也不用担心：只有银行才有钥匙呢！这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。
为了了解RSA加密，请听一个卧底的自白：
RSA加密我是潜伏在龙凤大酒楼的卧底。想让下面信息以加密的方式发送到总部：
厨子藏起来了一张床！这是如此的重要，需要立即通知总部。千万重要的是，不能让反革命的厨子知道。
第一步是转码，也就是将英文转换成某个对应的数字。这个对应很容易建立，比如：
将上面的信息转码，获得下面的数字序列： 这串数字完全没有什么秘密可言。厨子发现了这串数字之后，很容易根据数字顺序，对应字母表猜出来。
为了和狡猾的厨子斗智斗勇，我们需要对这串数字进一步加密。使用总部发给我们的锁，两个数字：3和10。我们分为两步处理。 第一步是求乘方。第一个数字是3，也就是说，总部指示我们，求上面数字串的3次方： 原字符串: 1 3 8 5 6 8 9 4 5 1 2 5 4 三次乘方: 1 27 512 125 216 512 729 64 125 1 8 125 64 第二步是求余数。第二个上锁的数字是10，将上面每个三次乘方除以10，获得其余数： 余数： 1 7 2 5 6 2 9 4 5 1 8 5 4
将这串数字发回总部。中途被厨子偷看到，但一时不能了解其中的意思。如果还是像刚才一样对应字母表的话，信息是： AGBEFBIDEAHED 这串字母完全不包含正常的单词。
信息到了总部。总部开始用神奇的钥匙来解读。这个钥匙是3。(偷偷告诉你的，别告诉厨子。) （这里钥匙不小心和之前锁中的一个数字相同。这只是巧合。） 解锁过程也是两步。第一步求钥匙次的乘方，即3次方。第二步求它们除以10（锁之一）的余数。 加密信息：1 7 2 5 6 2 9 4 5 1 8 5 4 三次乘方：1 343 8 125 216 8 729 64 125 1 512 125 64 (这里用的是钥匙的“3”) 除十得余：1 3 8 5 6 8 9 4 5 1 2 5 4 正是我们发送的信息。对应字母表，总部可以立即知道原来的信息。
特工练习再次强调，为了演示方便，选用了简单的锁和钥匙。锁和钥匙只是凑巧相同。为此，我们做一个小练习。 练习：总部新公布出来的锁是2987(次乘方)和3937(为除数)。 1) 作为特工，用上面的算法为信息加密(你可能需要一些编程来计算，尝试用Python的数学计算功能？)。 猜到钥匙是什么了呢？不是上面两个数字中的任何一个，而是143！ 2) 作为值班人员，验证143是钥匙，可以解密信息。 为了简便，你可以只检验一个简单的信息，比如“IE”。
下面是我根据这个练习写的一个Python小程序。这里的转码用的是ASCII编码标准，而不是上面的A对应1，B对应2。  # By Vamei
#==== Agent ========
# coding covert: string to number
# By ASCII convention
def convert(original):
return map(ord, original)
# the input is a list of integers
def encrypt(input_list):
f = lambda x: (x**2987)%3937
return map(f, input_list)
#==== Headquarter =====
# the input is the result of the encrypt function
def decrypt(encrypted_list):
f = lambda x: (x**143)%3937
return map(f, encrypted_list)
# convert numbers back to a string
def inv_convert(decrypt_list):
f = lambda x: str(unichr(x))
result = map(f, decrypt_list)
return "".join(result)
# Test
message = "Go to hell!"
secret = encrypt(convert(message))
print(secret)
public = inv_convert(decrypt(secret))
print(public)
|
