研究一个难题
1958年的夏天，Michael Rabin 重新回到了IBM在马萨诸塞州哈得孙的Lamb Estate智囊团。John McCarthy正在努力的解决FORTRAN语言里的表处理问题，他交给了Rabin一个难题。下面就是Rabin的回忆。
有两个国家处于战争状态。两个国家分别向对方国家派送间谍。间谍完成任务后就返回自己的国家。当他们试图穿越边界时，有可能被自己方的守卫射杀。
所以，他们需要有一套口令机制。假设间谍的素质都很高，能保守秘密。但边界上的守卫经常去当地酒吧聊天—所以不论你告诉他们什么，敌人都能打听出来。
你是否能设计出一套方案，既能让间谍安全的回来，又不让敌人使用从守卫哪里打听到的信息把他们的间谍混进来？
复杂的乐趣
Rabin 想出来了一个被称作“单向”算法的解决方案。单向算法可以转成成计算过程。从一个方向，你可以很容易的计算，但反过来却很难。我们很熟悉的算法跟这个都不同。例如，使一个数变成三倍大就是一个双向的算法，因为你可以很简单的从y得到3倍的y。同样，你也很容易的从z得到三分之一的z。Rabin 使用的单向算法是由数学家 John von Neumann 开发出来的：
假设你有一个100位的数，X，取它的平方值。这很容易算。如果你有一个200位的数。从这200位中取出中间的100位。现在，如果你知道X，你可以算出Y。但如果你知道Y，让你算出X，这要花费你大量的时间。现在你明白其中的奥秘了吧？
我们可以给守卫一些Y值，而每个间谍都记住一个X值。
[英文原文：In Search of a Tough Problem ]
呵呵，密码学上一般都用这方法。那些著名的加密算法也是基于数学上某一难解问题的，比如说大素数难解问题。
学习了。文章蛮好的。
哈哈，一个典型的例子就是MD5算法
就是丢掉一部分数据导致不可逆的算法么?
准确说,不是不可逆,只是很难可逆…比如RSA,穷举绝对可逆,但是一个256位数穷举要100+年…但是不穷举的话找不到有效的算法进行素数分解…所以称之为不可逆而已…
守卫同样会泄漏f()
非对称加密的优点就在于,即使你知道f(n)你都不一定解得出来…