《高中数学选修5-3(密码学算法基础) 数学与密码学8 课件.ppt》由会员分享，可在线阅读，更多相关《高中数学选修5-3(密码学算法基础) 数学与密码学8 课件.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学与信息安全数学与信息安全怎样设计密码怎样设计密码?第第1阶段古典密码阶段古典密码 密码学还不是科学密码学还不是科学,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现 主要特点：主要特点：数据的安全基于算法的保密数据的安全基于算法的保密数学与密码技术的三个发展阶段数学与密码技术的三个发展阶段数学与密码技术的三个发展阶段数学与密码技术的三个发展阶段古典加密主要技术古典加密主要技术n代替密码：代替密码：明文中的每个字符被替明文中的每个字符被替换成密文中的另
2、一个字符。换成密文中的另一个字符。n置换密码：置换密码：不改变明文字母，只不改变明文字母，只改变了这些字母的出现顺序。改变了这些字母的出现顺序。古典密码用到的数学n变换变换n置换置换n整数的模运算整数的模运算n统计学（破解时）统计学（破解时）用得不多 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 相关技术的发展相关技术的发展19491949年年ShannonShannon（香农）（香农）的的“The Communication The Communication Theory of Secret SystemsTheory of Secret Systems”197
3、1-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst Horst FeistelFeistel等几篇技等几篇技术报告术报告主要特点：主要特点：数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密 第第2阶段阶段 近代密码阶段（近代密码阶段（19491975）l ShannonShannon：美国工程师美国工程师 u 19481948年发表年发表 “A Mathematical A Mathematical Theory of Theory of ommunicationommunication”，标志信息标志信息论的诞生论的诞生u 194
4、91949年发表年发表 “Communication Communication Theory of Secrecy systemTheory of Secrecy system”，以信息以信息论为基础，用概率统计为数学手段对保论为基础，用概率统计为数学手段对保密通信问题进行了分析。密通信问题进行了分析。u由香农提出的保密系统模型目前仍然由香农提出的保密系统模型目前仍然是现代密码学的基本模型是现代密码学的基本模型.Shannon通信系统通信系统模型模型n信源：消息的来源信源：消息的来源n编码器：把消息变换成信号编码器：把消息变换成信号n信道：传递信号的媒介信道：传递信号的媒介,在物在物理线路上
5、划分的逻辑通道。理线路上划分的逻辑通道。n译码器：把信道输出的信号译码器：把信道输出的信号反变换反变换n信宿：信息的接受端信宿：信息的接受端n噪声：信道中的干扰噪声：信道中的干扰ShannonShannon保密通信系统模型保密通信系统模型 公开信道公开信道密钥信道密钥信道香农信息论信信源源熵熵信信道道容容量量无失真信源无失真信源编码定理编码定理率率失失真真函函数数信信源源编编码码信信道道编编码码限限失真信源失真信源编码定理编码定理 信道信道 编码定理编码定理密密码码u概括概括:u信息的测度信息的测度u信道容量信道容量u信源和信道编信源和信道编码理论码理论用到的数学用到的数学概率论与数理概率论与
6、数理统计统计19761976年：年：DiffieDiffie&Hellman&Hellman 的的 “New Directions in New Directions in CryptographyCryptography”提出了公钥密码学思想提出了公钥密码学思想；19771977年年Rivest,ShamirRivest,Shamir&AdlemanAdleman提出了提出了RSARSA公钥算法公钥算法；9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法；主要特点：主要特点：公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能
7、保密通信成为可能第第3阶段阶段 现代密码后期阶段（现代密码后期阶段（1976）q对称密码体制对称密码体制：加密密钥和解密密钥相同加密密钥和解密密钥相同.密钥分发与管理困难。密钥分发与管理困难。q非对称密码体制非对称密码体制(也称公钥密码体制也称公钥密码体制):加密密钥加密密钥（public key）和解密密钥和解密密钥（private key)不相同，不相同，从一个密钥导出另一个密钥是计算上不可行的，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。加密能力和解密能力是分开的，开放性好。密钥密钥分发与管理相对容易分发与管理相对容易.密码体制分类密码体制分类加密与解
8、密的密钥相同，即：加密与解密的密钥相同，即：P=D(K,E(K,P)对称密码体制模型对称密码体制模型加密与解密的密钥不同，则：加密与解密的密钥不同，则：P=D(KD,E(KE,P)非对称密码体制模型非对称密码体制模型如何设计公钥密码u最基本思想:利用数学难解问题.u设计工具:数论、代数数论的游戏之美n数论就是一门研究整数性质的学科数论就是一门研究整数性质的学科 n数论的很多问题最能体现数学之美数论的很多问题最能体现数学之美数学皇冠数学皇冠完美数有多少?物以稀为贵。虽然未找到实际中的特别用途，但优美数的奇异和美丽吸引了许多人2 2 素数素数整数p1被称为素数(质数)，是指p的因子仅有1或它自己。
9、2 3 5 72 3 5 711 13 17 1911 13 17 1923 29 23 29 31 37 31 37 41 43 47 41 43 47 53 59 53 59 61 61 67 67 71 73 79 71 73 79 83 8983 899797n回文素数回文素数13，31，17，71，113，311，347，743，有多少对？有多少对？n孪生素数孪生素数17，19，29，31，41，43，59，61，71，73，,2972546-1,2972546+1,115914298522304-1,115914298522304+1,有多少有多少对？q素数在密码学中占有极其重素数
10、在密码学中占有极其重要的地位。要的地位。q关于素数有如下些问题：关于素数有如下些问题：q如何判定？如何判定？q如何找到？如何找到？q素数的分布？素数的分布？Euclid在探寻完美数的时候发现：完美数可能有公式成立：Mn都是素数加拿大20歲青年 Micheal Cameron 在2001年11月發現了第39個梅森質數 213466917-1，它是個，它是個 4053946 位數位數Micheal AMD TB 800 MHz 電腦，在餘暇時間運作了42日。之后一直未發現有新的梅森質數，直到2006年：q最大的最大的Mersen素数素数2 23258265732582657 -1-1据国际著名数学
11、网站据国际著名数学网站数学世界数学世界20062006年年9 9月月1111日报道，美国密苏里州立日报道，美国密苏里州立中央大学数学家库珀和化学家布恩领导的研究小组发现了已知的最大梅森素数，中央大学数学家库珀和化学家布恩领导的研究小组发现了已知的最大梅森素数，该素数有该素数有98083589808358位数，这一超级素数是目前已知的最大素数，也是位数，这一超级素数是目前已知的最大素数，也是20002000多年来多年来人类发现的第人类发现的第4444个梅森素数。个梅森素数。如果用普通字号将这个数字连续写下如果用普通字号将这个数字连续写下来，它的长度超过来，它的长度超过40公里！公里！为了激励人们
12、寻找梅森素数和促进网格技术发展，设为了激励人们寻找梅森素数和促进网格技术发展，设在美国的电子新领域基金会在美国的电子新领域基金会(EFF)不久前向全世界宣布不久前向全世界宣布:任任何个人或机构通过何个人或机构通过GIMPS项目找到超过项目找到超过1000万位数的梅森万位数的梅森素数，将会获得该基金会颁发的素数，将会获得该基金会颁发的10万美元奖金。但是，绝万美元奖金。但是，绝大多数研究者参与该项目不是为了金钱而是出于乐趣、荣大多数研究者参与该项目不是为了金钱而是出于乐趣、荣誉感和探索精神。誉感和探索精神。目前最大的目前最大的Mersen素素素素德国德国焦点焦点周刊网站日前报道，美国和德国的数学
13、周刊网站日前报道，美国和德国的数学家先后分别于家先后分别于2008年年8月月23日和日和9月月6日计算出了两个新的素日计算出了两个新的素数，这两个数字都超过了数，这两个数字都超过了1100万位，是迄今所知的最大素万位，是迄今所知的最大素数。数。2 243112609-1-12 237156667-1-1美国:超过超过1200万位万位德国:超过超过1100万位万位国际素数搜索项目国际素数搜索项目“互联网梅森素数大搜索互联网梅森素数大搜索”（GIMPS）经过复核验算后证实，这两个数字都是素数。经过复核验算后证实，这两个数字都是素数。3.与几何有关，圆周率与几何有关，圆周率,和和e一样，是无理数一样
14、，是无理数。与素数的前的前2位是回素数位是回素数31,13,前前6位位也是回文素数也是回文素数314159,951413,真真让人让人浮想浮想联翩联翩,还有若干这样奇还有若干这样奇妙的特点妙的特点.4.水仙花数l水仙花数是指一个水仙花数是指一个n(=3)位数字的整数位数字的整数,它等于每个数字的它等于每个数字的n次幂之和。次幂之和。n在在1000以内的水仙花数共有以内的水仙花数共有4个：个：153=13+53+33另外还有另外还有:370、371、407n 四位的水仙花数四位的水仙花数:1634=13+63+33+43另外还有另外还有:8208，9474 中国与数论1986年，陈景润与著名数学
15、家王元、杨乐、张广厚一起研究数论问题。要谈中国要谈中国的数论研的数论研究究,必须必须要说到一要说到一数学家数学家-陈景润。陈景润。n1978年年2月月17日，日，人民日报人民日报、光明日报光明日报同时转载了最初发表于同时转载了最初发表于人民文学人民文学的徐迟的报的徐迟的报告文学告文学哥德巴赫猜想哥德巴赫猜想。这篇报告文学让数亿。这篇报告文学让数亿中国人知道了摘取中国人知道了摘取“数学皇冠上的明珠数学皇冠上的明珠”的陈景的陈景润，陈景润的事迹震撼并激励了国人。润，陈景润的事迹震撼并激励了国人。n陈景润（陈景润（1933年年5月月22日日1996年年3月月19日日），），福建福州福建福州人，人，中
16、国中国著名著名数学家数学家，厦门大学数学厦门大学数学系系毕业。毕业。1953年年-1954年在年在北京四中北京四中任教，因口齿任教，因口齿不清，被拒绝上讲台授课，只可批改作业，后被不清，被拒绝上讲台授课，只可批改作业，后被“停职回乡养病停职回乡养病”。调回。调回厦门大学厦门大学任资料员，同任资料员，同时研究时研究数论数论。1956年年调入调入中国科学院数学研究所中国科学院数学研究所。1980年年当选中科院当选中科院物理学物理学数学部委员。数学部委员。n哥德巴赫猜想的表述极为简单：任何一个大于哥德巴赫猜想的表述极为简单：任何一个大于2的的偶数都可以表示成两个素数之和，例如偶数都可以表示成两个素数
17、之和，例如4=2+2，6=3+3，8=3+5,。n哥德巴赫猜想是德国数学家哥德巴赫（哥德巴赫猜想是德国数学家哥德巴赫（CGoldbach，16901764）1742年年6月月7日给大日给大数学家欧拉的一封信中提出的数学家欧拉的一封信中提出的.n目前不断用计算机进行验证目前不断用计算机进行验证,已到几千万的数字已到几千万的数字,都正确都正确.n陈景润主要研究陈景润主要研究解析数论解析数论，1966年发表年发表表达表达偶数偶数为一个为一个素数素数及一个不超过两个素数的及一个不超过两个素数的乘积乘积之之和和（简称（简称“1+2”），成为），成为哥德巴赫猜想哥德巴赫猜想研究上的里程研究上的里程碑。而他
18、所发表的成果也被称之为碑。而他所发表的成果也被称之为陈氏定理陈氏定理。这项。这项工作还使他与工作还使他与王元王元、潘承洞潘承洞在在1978年共同获得中国年共同获得中国自然科学奖一等奖。他研究哥德巴赫猜想和其他数自然科学奖一等奖。他研究哥德巴赫猜想和其他数论问题的成就，至今，仍然在世界上遥遥领先。论问题的成就，至今，仍然在世界上遥遥领先。n世界级的数学大师、美国学者世界级的数学大师、美国学者安德烈安德烈韦伊韦伊(Andr Weil)曾这样称赞他：曾这样称赞他：“陈景润的每一项工作，都陈景润的每一项工作，都好像是在好像是在喜马拉雅山喜马拉雅山山巅上行走。山巅上行走。”著有著有初等数初等数论论等。等
19、。n1999年年，中国发表纪念陈景润的，中国发表纪念陈景润的邮票邮票。另外亦有。另外亦有小小行星行星以他为名。以他为名。由由哥德巴赫猜想哥德巴赫猜想引出的问题引出的问题n哥德巴赫猜想哥德巴赫猜想的研究有什么用的研究有什么用?n作为数学的基础研究作为数学的基础研究,引出若干新的分支引出若干新的分支.n由于由于哥德巴赫猜想哥德巴赫猜想的描述很简单的描述很简单,让人误以为其让人误以为其证明也会像中小学数学题那么简单，这是为什么证明也会像中小学数学题那么简单，这是为什么有那么多没有受过专业数学训练、甚至只有中小有那么多没有受过专业数学训练、甚至只有中小学文化程度的人都自以为比大数学家更有能耐，学文化程
20、度的人都自以为比大数学家更有能耐，灵机一动破解了这一超级难题。灵机一动破解了这一超级难题。结果导致结果导致n神乎其神神乎其神,有人说美国航天飞机上天有人说美国航天飞机上天,就是用了就是用了陈陈氏定理氏定理,中国自己却不会用中国自己却不会用.n.数论的诱惑n数论中无数的奇妙而易数论中无数的奇妙而易于理解的问题于理解的问题,诱惑了诱惑了无数的数学爱好者无数的数学爱好者.n数论是一个充满诱惑数论是一个充满诱惑,而又是一个充满陷阱和而又是一个充满陷阱和凶险的领域凶险的领域.n不要轻易去碰它不要轻易去碰它.数论有用吗数论有用吗?n几千来几千来,数论是纯粹数学的代表数论是纯粹数学的代表!n几十年前几十年前
21、,竞发现数学论开始有用场竞发现数学论开始有用场:数数值分析、结晶学、理想气体、计算机理值分析、结晶学、理想气体、计算机理论、随机数、密码学；论、随机数、密码学；n连数论都能走出象牙塔，可见其它的分连数论都能走出象牙塔，可见其它的分支应用更广泛；支应用更广泛；n密码学是数论最有成就的应用；密码学是数论最有成就的应用；数论在密码学中的应用举例数论在密码学中的应用举例他們在1977年發表論文，並把 這運算法註冊專利。20年後 RSA Data Security 公司市值超過二億美元。q大整数因子分解问题：大整数因子分解问题：q判判定定给给定定素素数数p,q是是否否为为n的的因因子子容容易易，只只要要
22、计计算算n=pq即可。即可。q给定整数给定整数n,求求n的素因子的素因子p,q使得使得n=pq困难困难.例：例：p=20000000000000002559,q=80000000000000001239,n=16000000000000002295000000000000003170601 验证验证 n=pq容易，但要分解容易，但要分解n困难。困难。RSA公钥密码系统是基于三个难解问题公钥密码系统是基于三个难解问题之一之一-大整数分解困难问题大整数分解困难问题要分解 n=p x q 究竟有多難？n1977年年 Scientific American 雜誌登出雜誌登出了了 RSA-129，獎金是
23、獎金是100美元。美元。n17年後，超過年後，超過600人利用互聯網，聯合人利用互聯網，聯合不同地方的電腦，用了八個月時間，終不同地方的電腦，用了八個月時間，終於破解了於破解了 RSA 129。專家估計，一億台專家估計，一億台100 MHz Pentium 電電腦合起來，分解一個腦合起來，分解一個 308 位數的位數的 n(比比129 位數大了十兆兆兆兆兆兆兆兆兆兆位數大了十兆兆兆兆兆兆兆兆兆兆兆兆兆兆兆倍兆兆兆兆兆倍)，大約需要一千年。，大約需要一千年。RSA的原則是：公開密钥的的原則是：公開密钥的 n 值必須大值必須大得全球電腦聯合起來直至太陽系死亡也得全球電腦聯合起來直至太陽系死亡也不能
24、破解。不能破解。因此必須要找非常大的質數来构造因此必須要找非常大的質數来构造n。产生密钥对产生密钥对选择两个大素数选择两个大素数p,q,p q计算计算n=pq,(n)=(p-1)(q-1)选择整数选择整数e,使得使得gcd(e,(n)=1计算计算d e-1 mod (n)公钥公钥:KU=e,n,私钥私钥:KR=d,n使用使用加密加密:C=Me mod n解密解密:M=Cd mod nRSA加密过程：加密过程：例子：例子：选选p7，q17则则npq119且且(n)(p-1)(q-1)61696取取e5则则d77 (57738549611 mod 96)公钥（公钥（5，119），私钥（），私钥（7
25、7，119）加密加密m19则则cme mod n=195 mod 119=66 mod 119解密解密c66mcd mod n=6677mod 11919 mod 119再例：再例：p=53，q=61，n=pq=3233，(n)52x60=3120令令d=791，则，则e=71令令m=RE NA IS SA NC E即即m=1704 1300 0818 1800 1302 0426170471 mod 3233=3106 mod 3233，C=3106 0100 0931 2691 1984 2927密码技术在信息安全中的地位和作用密码技术在信息安全中的地位和作用 密码技术是保障信息安全的核心
26、技术。密码技术不仅能密码技术是保障信息安全的核心技术。密码技术不仅能够保证机密性信息的加密够保证机密性信息的加密,而且完成数字签名、身份验证、系而且完成数字签名、身份验证、系统安全等功能。所以，使用密码技术不仅可以保证信息的机统安全等功能。所以，使用密码技术不仅可以保证信息的机密性，而且可以保证信息的完整性，防止信息被篡改、伪造密性，而且可以保证信息的完整性，防止信息被篡改、伪造和假冒。和假冒。q防火墙防火墙q安全路由器安全路由器q虚拟专用网（虚拟专用网（VPN）q安全服务器安全服务器q电子认证机构（电子认证机构（CA）和）和PKI产品产品q用户认证产品用户认证产品密码技术的其它数学方法密码技术的其它数学方法n代数：群、环、域、多项式代数：群、环、域、多项式n拉格朗日插值拉格朗日插值n向量几何向量几何n概率统计概率统计n.