他凭什么得了图灵奖---我所认识的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   天河一号超级计算机（10¹⁵次/秒）用穷举法分解200位大素数估计时间。
  通常的算法是
  n=m^(1/2)
   For (q=2；q<n; q++)，
  If (q能整除m)
  { p=m/q;
    printf(“m分解为%d 和%d)rn”,p,q)
  }
   If (q==n) printf(“m本身是素数,不能分解rn”)
 
  当m是一个200位的10进制整数时，for循环次数的数量级是10¹⁰⁰，
  用天河一号，每秒千万亿（10¹⁵）次，还需要10⁸⁵秒，
  假定一个聪明人找到一个好算法，把速度再提高十亿亿亿倍（10²⁵），还需要10⁶⁰秒，
  一年不到10⁹秒，至少要10⁵¹年。
  （ 一年365x24x60x60=31536000秒 < 10⁹秒）
   
附录2  陷门单向函数（鸳鸯剑函数）的制作
  下面的科普牺牲了严格性，希能使中学数学兴趣小组的朋友也看懂思路。
  (a)双向函数  two-way function
　　三角函数y=Sin(x)的反函数是x=ArcSin(y)，对于基本三角函数，给定原来的函数f(x),不难找到

反函数 f^-1（y）, 因为正反都容易，映射来去自由，所以称为双向函数。

  (b) 单向函数  one-way function
　　单向函数y=f(x)有下列性质,如果给定x₁,求y₁=f(x₁)容易；反过来给定y₂,    解方程y₂=f(x) 求x₂很难。（作为科普，就不费力地描述这个“很难”到底有多难）。
  乘法X与逆向运算因子分解InvX就是一对这样的冤家。 给定两个100位的大素数p,q ，做乘法容易，对200位的合数做因子分解是一件难事（若干年）。
     附录1给了一个粗略的估计，如果用笨笨的穷举法，用高级计算机分解200位的大数，需要10^u年，如果某聪明人吧方法加快了十亿亿亿（10²⁵）倍，只不过用v=u^-25取代了u，还要10^v年。不解决根本问题。

  ( 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三剑客就是那个铸剑师；而那个秘籍，又称为陷门（或窍门），是一对大素数。为了做一对鸳鸯剑，需秘密地选一对数量级为10¹⁰⁰的大素数p,q ，做乘法 n=pq；
　　利用的整除性技术构造两个依赖于p和q的整数e 和 d ，(技术细节,参见[5])， e 和 d 所藏身区间的大小的数量级是10¹⁰⁰（穷举法搜索就死心了吧）。
　　有了n,e, d,造出这一对互逆的鸳鸯剑（函数），一个做私钥，一个作公钥，如下：
                     y = x^e mod n   , （做私钥）
                     x = y^d mod n     （作公钥）
　　教科书上，利用e,d的具体细节，可验证：x=（ x^e mod n）d mod n= x ，即 明文x 用鸳剑函数加密，而用鸯剑函数脱密，最后还原为明文，不失真。
　　构造不是很复杂，计算起来也不慢；
　　如只得到了鸳鸯剑之一，想造出另外一个，很难。因为关键是在数量级为10¹⁰⁰的区间中找出 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加密演算法

关于 Leonard . Adleman的系列博文
　　1一位狂热科学家的工作照  

       2 图灵奖得主是怎样炼成的-----侧应钱学森之问   

      3 他凭什么得到图灵奖？ （在RSA中的贡献，+RSA科普）

      4  一不小心，成了计算机病毒的教父 (科普）  

     5  奇思妙想，客串艾滋病免疫研究      (科普）  

     6  沧海横流，谁开辟了DNA计算?  （DNA计算简介，科普）

                其它系列博文的入口    唐常杰博客主页      科学博客主页