他凭什么得了图灵奖---我所认识的L . Adleman （3） （唐常杰）
1 幸运之星照耀有准备的头脑
1976年，MIT的Rivest and Shamir 正在研究基于数论计算复杂性的新型密码技术；他们缺少扮演蓝军的研究者，Leonard .Adleman下列条件使得其他竞争者败下阵去：
(a) UC Berkely的 EECS博士学位（文化底蕴与资质）；
(b) 1975 -1976的三篇关于数论计算复杂性的论文[1,2,3]（课题组急需的内功）；
(c) 做过银行程序员，而且是编程高手（针对性极强的硬功）。
黑白照片时代的RSA三剑客 彩色照片时代的RSA三剑客
隐隐透出工作的疲惫 笑意写在脸上，洋溢着丰收的喜悦
Adleman本人在多年后（1996年8月）对NetWorker记者说，“我是在正确的地方，正确的时间，碰巧有正确知识的人”（ I was in the right place at the right time and, accidentally, had the right knowledge.）
阳光好、土地肥、种子壮；基础、机遇、勤奋和经验，构成一个难能可贵的组合。
舍他其谁也？
他顺利地以讲师职称进入了Rivest and Shamir的密码技术研究团队,扮演蓝军，负责攻击。
2 RSA研究中的蓝军
他们的攻防演习做了43 次 ，前42次蓝军胜，Adleman说，有些方案几分钟就破解了，有的用了几天。第43次，Rivest and Shamir，利用素数与整除性，构造了世界上第一个陷门单向函数，这个陷门之盾（详见本文科普部分），终于挡住了Adleman的才华之矛；用当时的计算机,要 long long time,成千上万年,才能破解。
“红”方终于胜利了，这是红蓝双方的成功。
他们先申请了专利，命名为 RSA公钥密码技术，在加州成立了RSA 数据安全公司，后来这个专利转到了MIT （猜测：因为这是职务发明，专利权归属学MIT学校）；1978年在顶级杂志CACM上发表了开创性的论文[4]，于2002年三人共获图灵奖。
RSA最奇妙之点在于，互不相识的双方在不安全信道上，也能进行安全通信.其思想启发了今天的CA认证服务。因科普内容放在后面，这里暂用淘宝购物来比喻（实际上内涵不同），在淘宝上用支付宝购物，互不相识的买卖双方，通过第三方支付宝实现安全交易。
说到这里，笔者想再次推荐在“基础、机遇、勤奋和成功”中 中的哪个的积分公式，Leonard . Adleman正是这样一位基础好、路线对，勤奋而又有机遇的人，他成功了。
3 RSA公钥密码的用户感受
先从用户感受来看这一发明的轮廓，把更深的原理放在附录2中，供有兴趣的朋友参考（其实，静下心来，用中学数学知识也能了解附录2的大概思想）。
( a) 铸剑秘籍和鸳鸯剑 传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点：
* 如果用y=f(x)加密，则可以用 x=g(y)解密，反之亦然；
* 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑；
* 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N万年。
天下有这样的铸剑师，有这样的铸剑秘籍吗？
有，而且办了公司，RSA公司就是这样的鸳鸯剑函数公司，批量生产（其生产流程参见附录2），对社会销售。一般人只能买鸳鸯剑函数，而买不到秘籍(正规名称：陷门、可理解为造钥匙的窍门，即一对秘密的大素数，参见附录2)。下面假定我们已经买回三对鸳鸯剑函数。
(b)公钥体制的大致思路。
设x是明文，y是密文,有a,b,c三个户，他们从鸳鸯剑公司那里买回了自己的鸳鸯剑函数，鸳剑作公钥函数(让地球人都知道），鸯剑作私钥函数（妥善保管），用大写字母表示如下
公钥函数 私钥函数
y=A(x), x=A-1(y)
y=B(x) , x=B-1(y) ,
y=C(x), x=C-1(y)
(c ) 用途1：举报罪犯。 a通过网络 发信息x 给b，举报罪犯c；a当然不希望c知道，操作如下：
a 把密文y=B(x)送给 B，
b 收到密文y后，用x= B-1(y)解密，即接受者用自己的私钥解密,得到明文x。
即使c截获了y=B(x),也无法理解，因为要构造出函数B-1，相当于做因子分解，需要若干年。好像两位客家人用家乡话聊天，旁边的东北人即便听见了，也懂不起。
(d) 问题：举报后怎样领奖？如果是有奖举报，a凭什么领奖呢？ b说，的确收到了举报信息y=B(x)， 凭什么说是a举报的呢？
(e) 增加发信者指纹，要点如下：
* 为留下领奖凭据，a做了改进，把举报信息用改成 y=A-1(B(x))，这好像在信封外再加一层信封;
* b收到后，先用a的公钥y=A(x)函数脱去A-1这层信封；注意，只有A自己才知道私钥函数A-1(.. )，具有A-1(…)这层信封的信息只能是A送来的，因此公钥密码体制还有防诬告，防抵赖的作用。
* b然后用自己的私钥B-1解密。
以上就是公钥密码机制的思想，不需要微积分，需要若干数论中的关于整除性的定理；高三学生静下心来，也能理解思路框架，更多的技术细节的通俗解释在附录中，为通俗，有不到位的地方，请专家指正。
4《红灯记》要与时俱进 传统的密码电报的密钥是密码本，需要单独的安全通道传送。截获与保卫密码本的斗争演绎出了许多可歌可泣的故事。现代京剧《红灯记》描写了抗日战争中，李玉和一家三代为保护密码本的故事，他们不怕牺牲、前赴后继，激励了几代人的革命激情。
在公钥密码体制中，通信双方干脆公开自己的公钥，不怕敌人听到，而私钥静放囊中，不存在长途运送；所以，用人来传送密码本的故事，在未来战争中可能不会有了。
爱国主义的主题是永存的，它将以新的形式存在和表达。在此意义上，《红灯记》也将与时俱进。
附录1 天河一号超级计算机（1015次/秒）用穷举法分解200位大素数估计时间。
通常的算法是
n=m(1/2)
For (q=2；q
If (q能整除m)
{ p=m/q;
printf(“m分解为%d 和%d)\r\n”,p,q)
}
If (q==n) printf(“m本身是素数,不能分解\r\n”)
当m是一个200位的10进制整数时，for循环次数的数量级是10100，
用天河一号，每秒千万亿（1015）次，还需要1085秒，
假定一个聪明人找到一个好算法，把速度再提高十亿亿亿倍（1025），还需要1060秒，
一年不到109秒，至少要1051年。
（ 一年365x24x60x60=31536000秒
附录2 陷门单向函数（鸳鸯剑函数）的制作
下面的科普牺牲了严格性，希能使中学数学兴趣小组的朋友也看懂思路。
(a)双向函数 two-way function
三角函数y=Sin(x)的反函数是x=ArcSin(y)，对于基本三角函数，给定原来的函数f(x),不难找到
反函数 f-1（y）, 因为正反都容易，映射来去自由，所以称为双向函数。
(b) 单向函数 one-way function
单向函数y=f(x)有下列性质,如果给定x1,求y1=f(x1)容易；反过来给定y2, 解方程y2=f(x) 求x2很难。（作为科普，就不费力地描述这个“很难”到底有多难）。
乘法X与逆向运算因子分解InvX就是一对这样的冤家。 给定两个100位的大素数p,q ，做乘法容易，对200位的合数做因子分解是一件难事（若干年）。
附录1给了一个粗略的估计，如果用笨笨的穷举法，用高级计算机分解200位的大数，需要10u年，如果某聪明人吧方法加快了十亿亿亿（1025）倍，只不过用v=u-25取代了u，还要10v年。不解决根本问题。
( c) 铸剑秘籍和鸳鸯剑 传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点：
* 如果用y=f(x)加密，则可以用 x=g(y)解密；
* 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑；
* 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N年。
(d) 陷门单向函数 one-way function
RSA三剑客就是那个铸剑师；而那个秘籍，又称为陷门（或窍门），是一对大素数。为了做一对鸳鸯剑，需秘密地选一对数量级为10100的大素数p,q ，做乘法 n=pq；
利用的整除性技术构造两个依赖于p和q的整数e 和 d ，(技术细节,参见[5])， e 和 d 所藏身区间的大小的数量级是10100（穷举法搜索就死心了吧）。
有了n,e, d,造出这一对互逆的鸳鸯剑（函数），一个做私钥，一个作公钥，如下：
y = xe mod n , （做私钥）
x = yd mod n （作公钥）
教科书上，利用e,d的具体细节，可验证：x=（ xe mod n）d mod n= x ，即 明文x 用鸳剑函数加密，而用鸯剑函数脱密，最后还原为明文，不失真。
构造不是很复杂，计算起来也不慢；
如只得到了鸳鸯剑之一，想造出另外一个，很难。因为关键是在数量级为10100的区间中找出 d或e, 但这需要把n分解为素数p,q, 如附录1的估计，这是难计算问题，现在的技术，要若干年。
利用RSA原理，可开展鸳鸯函数租售业务，一般人只买鸳鸯函数，而不买秘籍(或陷门、即那一对素数)，这样，自己都不知道破解法，破解法被窃取的隐患就少一个。
买回的鸳鸯剑，一个做私钥，自己保管好；一个作公钥，让地球人都知道。
参考文献
[1] Leonard M. Adleman, Kenneth L. Manders: Computational Complexity of Decision Procedures for Polynomials (Extended Abstract) FOCS 1975: 169-177
[2] Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials STOC 1976: 23-29
[3] Leonard M. Adleman, Kenneth L. Manders: Diophantine Complexity FOCS 1976: 81-88
[4]. R. Rivest ， A. Shamir L.Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, 21(2):120-126,(February) 1978.
[5]博友dailiangren（评论4）推荐的参考资料ttp://zh.wikipedia.org/zh/RSA加密演算法