公钥密码系统
soliton
Ok,具有挑战性的内容来了，如果下面的内容读懂了，那也算是个密码系统的业余专家了。
首先，看看RSA的密码系统是怎样工作的，最好我们自己设计一个。
1, 找出两个质数，例如p=11和q=19，
算出他们的乘积N=p*q=209.
2，算出f(N)=(p-1)*(q-1)=(11-1)*(19-1)=180.
3, 找出一个数字与f(N)=180互质,假如我们让它等于7，c=7.
4, 算出d, 使得c*d=1(取180的模），我们发现d=103.
好，有了这些。RSA公钥系统所有需要的东西都知道了。看看它是怎样工作的。
我们知道公钥系统有两个钥匙，一个公钥，一个私钥。那么，在上面的数字里，需要让
大家知道的是（N,
c).这里c是公钥。有了这些，就可以编制密码了。一般我们还是用
下面的对应：空格，a,b,...,y,z=00, 01, 02, ..., 25,
26.假如要送的字母是
i=09, 用公钥编制的密码是9的c次方，并取N的模,
即9的7次方取209的模为04。那么，
04就是编制成功的密码。收到密码后，怎样解码呢？那就要用私钥了，这是不能让别人知道的。私钥也是一对（N,d).解密码的办法和编密码的办法是相同的，只是把公钥变成私钥就行了。那么我们将04解码为，4的103次方取209的模，不出意外得到9！
ok,显然，我们已经发现问题了，好像与字母对应没什么区别？即i对应为04，再将04解码变为i.而我们知道英语中字母的出现有一定的几率，敌人多收到几次就可解码。这个原因主要是因为我们的例子举的太简单，
即一个字母一个字母的编码和解码。而一般的编码可以几十个字母同时编码和解码。
再看看，共钥密码系统不能让敌人知道的是那些，显然d不能让敌人知道。另外，
f(N),p,q不能让敌人知道。敌人和公众需要知道那些？1，2，3，4的步骤是知道的，N是知道的。
怎样来破解密码，从N算出p,q,在算出f(N), 再算出d。
这个密码系统难以破解的核心在那里？知道N，但是就是算不出来p,q。也就不知道f(N),
也就算不出来d。
不信，好，我们把前面悬赏的问题再来完整的叙述一遍。
大家知道的一对公钥是：
c=9007,
N=1143816257578888676692357799761466
1201021829672124236256184293570693524
57338978305971235639597050589890751475
99290026879543541.
这个N就是RSA129码。知道这对公钥，我们就可以送出密码。送出的密码是
968696137546220614771409222543
558829054599911245743198746951
209308162962251457083569314766
228839696280133919900551829945
157815154
请问是什么意思？
我们前面有个估计因数分解的速度，那是最直接的办法，专家用比较先进的办法估算，破解这个密码需要10的16次方年，而我们说过地球的年龄还不到10的10次方年。破解的关键就是知道N是那两个质数的乘积。1995年，互联网上多台计算机用了8个月的时间，估计微处理器5000MIPS年（MIPS指每秒百万指令），终于破解了这个密码，当然关键是知道N是怎样得到的：
34905295108476509491478496199038981334177646384
93387843990820577*
32769132993266709549961988190834461413177642967
992942539798288533
于是便有了，那是个神经质的秃鹰。
现在的银行系统大概用1000个数字左右的N。个人要破解恐怕不太可能。
好，几个问题！设计RSA要求找出两个质数p,q.那么，过两年所有的质数都被用了怎么办？
答，质数是无穷多的，例如100到200个数字的质数（10的100次方到10的200次方）大概有质数10的90次方，天文数字！地球上每个人10亿才用掉10的20次方个（随便算算）。
所以，前几年看到有报道说有人想卖大质数，大概没人愿买。
既然，N越大越安全，那我们用一万个数字的好了，为什么现在才用1000的。答，第一没必要，第二，
N越大，编制密码和解码便需要更多的计算机资源，浪费！
什么密码是安全的，答：美国有个标准，大概是说，假如世界顶尖的解码组10年破解不了的密码就被认为是安全的。
终于，RSA的公钥密码系统介绍完了，不过这是非专业的介绍，真要知道详细情况，需要查阅专业书籍。
中国最近出了个世界闻名的密码专家，王小云女士，一举破解了好几个密码系统，令人佩服。
所以， 引出下文，
RSA公钥系统的安全性是建立在大数分解上，如果有个聪敏人突然能找出一种简单的分解办法，其安全性便被破解。那么，我们能否找到一种不可能被破解的密码系统呢？有，那就是量子密码！