数学欣赏-06数学之妙-d数学与密码

数学欣赏Mathematics

Appreciation数学欣赏F数学之妙TheConsummateskillof

Mathematics名人说……从十分清楚明白、根本无法怀疑的东西、最简单最容易认识的对象开始，一点一点逐步上升到对复杂对象的认识。

——R.DESCARTES名人说……数学是什么？大致说来，数学和其它科学一样，它的发展基于两个原因：（一）奇怪的现象；（二）数学结果的应用。——陈省身数学之妙出神入化数学，虽然极其抽象，但却被广泛而有效的应用于人类社会的各个领域，其根本原因不仅是其对象为万物之本，更在于其思想方法的深刻性与普适性.由于人类生理的原因，人类能够准确认识的对象只能是有限的、静止的、平直的、离散的，但现实中人们又无法避免无限的、运动的、弯曲的、连续的.数学方法为人类认识这些对象提供了有效的可靠手段，奇妙无比，威力无限.SZUInthisChapter数学归纳法原理1抽屉原理与聚会认友

2七桥问题与图论

3数学与密码4第四节数学与密码

一个数学家儿子

的两部作品丹·布朗(DanBrown)是《数字城堡》、《达·芬奇密码》

的作者。他堪称今日美国最著名畅销书作家。丹·布朗的父亲是一位知名数学教授，母亲则是一位宗教音乐家，成长于这样的特殊环境中，科学与宗教这两种在人类历史上看似如此截然不同却又存在着千丝万缕关联的信仰成为他的创作主题。《数字城堡》

在信息时代，各国间谍、恐怖分子开始通过互联网传递情报，但是为了使电子邮件不被他人截获，他们纷纷给自己的邮件加上了密码。为了从网络上获得重要情报，世界上最为隐秘的情报部门——美国国家安全局(NSA)斥巨资建造了一台可以破解密码的机器——万能解密机……《数字城堡》探讨的主题是一个在美国社会被广泛关注的问题——国家安全与个人隐私的矛盾问题。整部小说跌宕起伏、玄机重重，秘密直到最后才被解开。该书的创作灵感来源于一起真实的事件。其成功要诀就是通过破译一个可以产生国际影响力的密码来结构小说。读者的乐趣之一就是跟随作者进入密码世界，并很快对密码术也略知一二，同时我们还可以一睹运用高科技而进行的政治斗争中的尔虞我诈。《数字城堡》是近年来最精彩同时也是最真实的高科技惊悚小说。丹·布朗以生动的笔触描写了个人自由与国家安全之间的灰色区域，其手法之高超着实令人敬畏，会使读者感到极度震撼，战栗不止。这是一部扣人心弦的最前沿...《达芬奇密码》

凌晨时分，哈佛大学的符号学家罗伯特-兰登突然接到紧急求助电话———巴黎卢浮宫的老馆长在博物馆内惨遭杀害。在尸体旁边，警方发现了一封秘信。后来，兰登和其他解密专家绞尽脑汁，终于弄明白了秘信中的内容。种种迹象显示，破案的线索就藏在达芬奇的诸多名画之中！如果兰登不能破解达芬奇的密码，一个远古时代的重大秘密也将永远不为人知晓。……丹·布朗说，达芬奇是加密术的开路先锋，其艺术作品和手稿中包含着大量令人费解的符号和诡异的代码。他说，《达芬奇密码》中最精彩的内容就是对加密术的探讨，尤其是由达芬奇亲自研究出来的种种加密设计令人忍不住拍案叫绝。在加密术诞生之前，如何把私人信件委托给邮差传递而又不使隐私外泄一直都是个让人头痛的问题。达芬奇发明了第一代“公匙加密术”的雏形———一个可以保证信件安全的便携式“密码箱”。而且一旦有人试图用暴力手段将“密码箱”砸开，里面的信息将立即自行销毁。密码的由来密码，并不是什么奇怪的东西。它只是按照“你知，我知”的原则组成的信号。密码的历史源远流长。据史料记载，在中国，密码的使用可以追溯到三国时期。公元前2000年古埃及墓碑上刻的一些铭文就是用一些奇怪的符号代替当时使用的文字。公元前130年左右，美索不达尼亚的一些碑文上将一些人名改用数字密写。公元4世纪，希腊出现了隐蔽书信内容的初级密码。1200年，罗马教皇政府和意大利世俗政府开始系统地使用密码术。在文艺复兴时期的欧洲，密码被广泛用于政治、军事和外交上。到16世纪末期，多数国家设置了专职的密码秘书，重要文件都采用密码书写。莫尔斯电码与密码通讯1832年10月，美国画家塞缪尔·莫尔斯在乘船从法国返回美国途中，看到一个青年医生在摆弄一块环绕着一圈圈绝缘铜丝的马蹄形铁块，铜丝的通电可以产生对铁丁的吸引力，而一旦断电则吸引力消失。这就是电磁感应现象。受此启发，莫尔斯在1844年5月24日发明了一种被后人称为“莫尔斯电码”的电报码和电报机，开始了无线电通讯。这种编码后来逐步应用到军事、政治、经济等各领域，形成了早期的密码通讯。到第一次世界大战时，密码通讯已十分普遍，许多国家成立专门机构，进一步研制和完备密码，并建立了侦察破译对方密码的机关。目前，信息时代的到来，密码的使用更多、更广，也更加先进了。

在各种各样的通讯传输过程中，人们会通过各种手段截取传输资料，造成传输安全问题。尤其是在科技高度发达的今天，传送过程几乎无法保证安全。于是人们就要在如何对内容加密上进行研究，以保证即使对方截获传送资料，也会由于不了解密码而不知所云。密码联络原理“置换”思想

加密或者用密码联络是自古就有的事情，民间使用较多的所谓“暗号”就是最简单的表现形式。“暗号”只是收发双方对某些具体内容进行的事先约定，其方法只适用于特定时间内的特定内容，不具有一般性。但是“暗号”的基本思想却是一般加密所共有的，这就是“置换”或“代换”的思想——用一种形式取代另外一种形式。

语言→数字，比如英文的莫尔斯电码，中文汉字的电报码等。重要性1.

把各种复杂的文字用10个数字符号来代替，符号的简化便于通讯传递；2.

各种文字转化为数字以后，要进行加密研究，只需要对数字加密进行研究，大大地降低了加密难度。加密传送基本模式

无论何种加密传送，其基本模式都是一样的：把要传递的内容——“明文”，按照“密钥”加密变成“密文”；将密文按照正常方式发送出去；对方接收到密文后，按照密钥解密再还原成原来的明文。

加密方法之一

——代换法加密的方法是人为地产生的，因此也就各种各样。“代换”或“置换”，是自古以来普遍采用的加密思想。所谓“代换”，就是用一种形式取代另外一种形式。这种方法早在罗马帝国时代就已经使用，当时他们把26个字母分别用其后面的第三个字母来代替，用“群”的记号就是如下的“矩阵”：hello

khoor

一种变形：把字母或数字用其它字母或数字代换时没有明显的代换规律。比如把0，1，2，…，9等10个数字分别换成3，5，6，2等等，即有下表：缺欠：在日常书面语言中，每个字母所使用的频率是不相同的，人们可以通过截取大量信息进行统计分析，推测出大体的代换法则，然后再经过检验调整，即可确定正确的代换法则，从而破解出所有信息。密钥可以公开了早期的各种加密方法有一个共同的弱点：他们都是封闭式的制解法，即收发双方都必须同时知道这种密码的构造。这些方法有许多不便之处，而且如果在通讯系统中有一个联络站被间谍渗入，则密码的机密就全盘暴露。20世纪70年代后期，美国几个电机工程师用数论知识创造了一种编码方法，用这种方法制造了密码，可以公开密钥，但他人却无法破解。密码通讯中的加密与解密方法实际上是两个互逆的运算。数学中许多运算是本身容易而逆向困难。比如，乘法容易，除法困难；乘方容易，开方困难等。用两个百位数字相乘得到一个200位数字，利用计算机是轻而易举的。但要把一个200位数分解为两个数的乘积，却极其困难。按照通行的做法：用一个一个较小的数去试除，其工作量是极其巨大的。人们做过估算，要分解一个200位数字，用每秒10亿次的电子计算机，大约需要40亿年，即使分解一个100位数字，所花时间也要以万年计。这就给数学家一种启示：能否利用这种矛盾编制密码，使我方编码、译码轻而易举，而敌方破译却难上加难?1978年，美国三位电机工程师Rivest、Schamir与Adleman利用这个思想创造了一种编码方法，称为RSA方法。其本质是制造密码与破解密码的方法都是公开的，同时又可以公开编制密码所依赖的一个很大的数N，这个N是由我方通过两个大的素数p、q乘积而得到的，而破解密码则必须依靠这两个素数p、q。因此要破解密码则必须首先分解大数N，但这是极端困难的。RSA编码方法与原理RSA方法可以公开用以制造密码与破解密码的方法，它依赖于两个大素数p、q，当然，不同的机构应当使用不同的p、q。下面是其基本方法：制造密码与密钥：1.我方掌握两个大素数p、q，由此可以造出一个大数N=pq；2.选取一个较小的数n，使得n与p-1,q-1均互素；3.再选取m，使得mn-1是(p-1)(q-1)的倍数,即mn=k

(p-1)(q-1)

+1；4.对外公开密钥：N和n。m是我们破解密码的唯一秘诀，绝不可以外传。敌方在不了解p，q的情况下，是难以分解出p，q的，因而也就不可能了解我们的唯一秘诀m.假如我们的朋友要向我们发送信息1.他可以通过查到的我们的密钥N和n，将要发送的信息（数）由明文x转化为密文y:

算出xn，设xn被N除所得的余数y，用数论的记号就是，xn≡y(modN)，y就是要发出的密文。密码通讯2.我方收到密文y后，计算出ym，按照数论的知识，一定有ym≡x(modN),

即ym被N除所得的余数就是对方想发出的明文x。密码通讯收发过程总结：我们把上述过程总结如下：(1)对方要发的明文x转化为密文y:xn≡y(modN)；(2)对方发送密文y；(3)我方收到密文y后转化为明文x:ym≡x(modN)。问题的关键在于为什么能有ym≡x(modN)？这依赖于数论中的一个基本公式：欧拉定理

设a,N

为正整数,如果

(a,N)=1,则有

其中为欧拉函数，它代表在1，2，3，……，N中与N互素的正整数的个数。

其中k是正整数。我们只需证明，对于任意正整数x,有ym≡xnm(modN)（因为xn≡y(modN)

）≡xk(N)+1(modN)≡x(modN)

根据欧拉定理，注意到当N=pq时，而上述选取的m,n满足mn-1是(p-1)(q-1)的倍数，即事实上，由于N=pq,只有四种可能：(x,N)=1、(x,N)=p

、(x,N)=q或(x,N)=N情况1如果(x,N)=1，由欧拉定理，必有xk(N)≡1(modN)，从而xnm≡xk(N)+1(modN)≡x(modN)。

情况2

如果(x,N)=p,即p|x,但q

与x

互素。对x,q应用欧拉定理得

xq-1≡1(modq)，

从而

xk(N)+1=xk(q-1)(p-1)+1≡x(modq)又因p|x,显然有

xk(N)+1=xk(q-1)(p-1)+1≡x(modp)

以上两点表明

xk(N)+1≡x(modpq)≡x(modN).情况3

如果(x,N)=