写给大家看的RSA加密算法

2022-10-28

前段时间看的《王牌特工》帅气的科林叔一把绅士伞在手，天下我有的气势征服了所有观众，凡是特工就没有不和加密解密打交道的，我们经常看到侦探电影的桥段，勇敢又机智的主角，拿着一长串毫无意义的数字苦恼，忽然灵光一闪，翻出一本厚书，将第一个数字对应页码数，第二个数字对应行数，第三个数字对应那一行的某个词。数字变成了一串非常有意义的话：

Eat the beancurd with the peanut. Taste like the ham.

主角喜极而泣……

这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密，而接收信息的人利用相同的密钥，来给信息解密。就好像一个带锁的盒子。发送信息的人将信息放到盒子里，用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥，这种加密称为对称加密（symmetric encryption）。

如果一对一的话，那么两人需要交换一个密钥。一对多的话，比如总部和多个特工的通信，依然可以使用同一套密钥。但这种情况下，对手偷到一个密钥的话，就知道所有交流的信息了。二战中盟军的情报战成果，很多都来自于破获这种对称加密的密钥。

二战中德军的传奇加密机：Enigma

为了更安全，总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构，恐怕很难维护这么多的密钥。在现代社会，每个人的信用卡信息都需要加密。一一设计密钥的话，银行怕是要跪了。

对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁，而总部保有钥匙，那就容易了。特工将信息用锁锁到盒子里，谁也打不开，除非到总部用唯一的一把钥匙打开。只是这样的话，特工每次出门都要带上许多锁，太容易被识破身份了。总部老大想了想，干脆就把造锁的技术公开了。特工，或者任何其它人，可以就地取材，按照图纸造锁，但无法根据图纸造出钥匙。钥匙只有总部的那一把。

上面的关键是锁和钥匙工艺不同。知道了锁，并不能知道钥匙。这样，银行可以将“造锁”的方法公布给所有用户。每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到，也不用担心：只有银行才有钥匙呢！这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。

为了了解RSA加密，请听一个卧底的自白：

RSA加密

我是潜伏在龙凤大酒楼的卧底。想让下面信息以加密的方式发送到总部：

A CHEF HIDE A BED

厨子藏起来了一张床！这是如此的重要，需要立即通知总部。千万重要的是，不能让反革命的厨子知道。

第一步是转码，也就是将英文转换成某个对应的数字。这个对应很容易建立，比如：