资源描述：
《数论在密码上的应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数论在密码上的应用杨重骏;杨照昆一、前言二、因子、质数、同余式与费马、尤拉定理三、狄飞、赫尔曼、麦克儿(Diffie,Hellmon,Merkle)法四、瑞未斯特、希米尔、爱得曼（Rivest,Shamir,Adleman）法五、如何寻找大质数六、结尾的话一、前言数论，顾名思义，是一门研究数字性质的学问。一般所谓的数论，特指正整数(即自然数)的许多性质，像质数的分布，方程式的正整数解，韩信点兵，及进位法都包括在数论里面，我们在小学时候学的分解因子，最大公约数也是数论的一部分，可惜因为数论在日常生活中没有什幺直接的用处，在中学数学里很少提到数
2、论，一般被认为是一种「纯数学」，深而无用。可是「无用之用，真乃大用」，终于在一九七0年代后期，几个电机工程师用数论的一些基本定理，制成了一种新的密码。这种由数论所作成的密码与以前人们所用的密码，有着根本性质上的不同，可说是密码史上一个空前的革新。密码通讯在军事上的用途是大家都知道的，但由于交通的发达，在分秒必争的工商业社会里，商业上的情报也已成为商业盈利的主要依靠。譬如说，有人早几个小时知道什幺公司有了一种新的发明，或某两个公司计划合作，或某地区有物价的大波动，就可以在股票上上下其手，转瞬之间收进大笔的财富。因此公司本身内部及公司与公司之间
3、的通讯都希望能对外严守机密。但由于现在通讯无论是有线或无线都很容易被敌方窃听，因此公司必须对情报加锁，即所谓密码通讯。以往人们在军事上所用的密码其基本的形式在于「代换」与「置换」。譬如说，我要发出下面一个消息给你，「我有一个秘密对你说」我就先把这几个字换成数字，即一般电码本上的代码，假定「我」字的代码是3314,「有」字的代码是1432，「一」字代码是0001，等等，则上面那句话就成了331414320001…代换密码是把0,1,2,⋯,9十个数字互换，譬如我们可以把0换成2，1换成3，等等，若用群论的符号表示，上面的代换可写成这个表示法是
4、上行为0，1，2，…，9，而下行是他们代换成的新数字，即02,13，25,…。因此刚才的电码若用G法代换，则成了这时一个不知道这个代换规则的人看到了上面的信号，他就不能从电码本子里找出它的原意了。置换法在于把密码排成一种双方都知道的形式，如下图则发出的信号为755772433216623，同样的，不知道这种特定图案的人，很难解开原来的信息。以代换法为例，像G这类的转换可以有10!=3,628,800种不同的变化，假定我们可以在一分钟内试一种代换，又假定我们的运气中等，在试到一半时即10!/2=1,814,400时可以成功，则在不吃、不睡、不
5、错的情形下，我们要试3年零165天，等迷解出来的时候，仗早已打完了。但这只是最基本的密码而已，在生死关头，更难解的密码必然出笼，例如在代换法中，若两位两位的代换(即005779,0185,⋯)则其变化可达100!=9.32x10种之多，如果我们再用硬试的方48法，则一百万人同心协力也得用6x10年才能试出谜底，可是地球的年龄不过9只有5x10年而已。因此解密码，都不用硬试的方法去解。一般可用统计的方法根据名字(或字母)出现的频率及发生的事件加以分析，例如在英语中，各字母出现的频率按多少排列是因此一个出现次数最多的符号就很可能代表e，出现次多
6、的符号就很可能代表a，并以此类推，但道高一尺，魔高一丈，如果不断地变化代换的方法，譬如说前一百个字用代换法G1，第二个一百个字用代换法G2，则频率方法亦失去功效。但是魔高一丈，恶魔又高一丈，重赏之下，天下尚没有绝对解不开的密码。二次大战时，美国密码兼统计学家弗立得门(W.F.Friedman)，在一年半的时间完全破获了日军的密码。在中途岛一战，美国海军以劣势的军力，大胜日本皇家海军(读过参加该战役的日本军官渊田美津雄及奥宫正武所着的《中途岛》一书吗?)。另外英国也几乎在同时解开了德军的密码，做到了知己知彼的优势地位(知己知彼并不一定百战百胜
7、，但总比不知彼要好得多。)过去这类密码的特质(也可以说是缺点)在于它们是关闭式的制解法，即收发双方都必须同时知道这种密码的构造。因此如果在一通讯系统中有一个联络站被间谍渗入或被敌人占领，则密码的机密可能全盘暴露。而现在用数论的密码却是公开式的(Public-KeyCryptography)，即是只有收方知道密码的解法，发方只需要知道做法而已，而且这种制法可以公开。因此即使发方被捕，敌人仍榨不出解密码的机密来，其程序是这样的：1.收方先告诉发方如何用把情报做成密码(敌人也听到了这个做法)2.发方依法发出情报的密码(敌人也听到了这个信号)3.收
8、方解开此密码为原信息(但敌人却解不开此密码)当然把收发互换，就可以互通信息了。刚才说过这种方法最大的好处就是只有一方知道译码的秘诀，比以前收发双方都知道秘诀的保密性高多了，自从这
