1、高中数学选修课程专题研究3-2 信息安全与密码1PPT课件前 言密码的历史极为久远,其起源可以追溯到几千年以前,人类有记载的通信密码始于公元前405年。2PPT课件3PPT课件前 言第一次世界大战是化学家的战争,第二次世界大战是物理学家的战争,如果未来发生战争将是数学家的战争,其核心是信息战中的军事密码学问题。4PPT课件生活中常见的密码5PPT课件早期生活中的密码 6PPT课件文学作品中的密码7PPT课件8PPT课件信息安全、密 码v防止信息被非授权地访问、使用、泄露、分解、修改和毁坏,以求保证信息的保密性、完整性、可用性和可追责性,使信息保障能正确实施、信息系统能如意运行、信息服务能满足要
2、求。v按特定法则编成,用以对通信双方的信息进行明密变换的符号。目前新出现的定义又增加信息有效性和占有性之类的概念目前新出现的定义又增加信息有效性和占有性之类的概念(后者与偷窃、欺诈和舞弊相对应)网络经济当然增加了(后者与偷窃、欺诈和舞弊相对应)网络经济当然增加了电子交易信用和责任的需要。电子交易信用和责任的需要。9PPT课件课程标准系列3-2:信息安全与密码 内容与要求初等数论的有关知识 v了解整除和同余,模的完全同余系和简化剩余系,欧拉定理和费马小定理,大数分解问题。v了解欧拉函数的定义和计算公式,威尔逊定理及在素数判别中的应用,原根与指数,模的原根存在性,离散对数问题。10PPT课件课程标
3、准系列3-2:信息安全与密码 内容与要求数论在信息安全中的应用v了解通讯安全中的有关概念(如明文、密文、密钥)和通讯安全中的基本问题(如保密、数字签名、密钥管理、分配和共享)。v了解古典密码的一个例子:流密码(利用模同余方式)。v理解公钥体制(单项函数概念),以及加密和数字签名的方法(基于大数分解的RSA方案)。v理解离散对数在密钥交换和分配中的应用棣弗-赫尔曼方案。v理解离散对数在加密和数字签名中的应用盖莫尔算法。v了解拉格朗日插值公式在密钥共享中的应用。11PPT课件知识框架图凯撒密码体制维吉尼亚密码体制流密码体制M序列公钥密码体制的思想RSA公钥方案离散对数方案保密通讯的基本常识公公钥钥
4、密密码码体体制制古古典典密密码码体体制制密码管理密码管理12PPT课件保密通讯的基本常识人类使用密码的历史,从今天已知的,最早可以一直追溯到古巴比伦人的泥板文字。古埃及人,古罗马人,古阿拉伯人几乎世界历史上所有文明都使用过密码。和 一直是密码应用的最重要的领域。军事外交13PPT课件保密通讯的基本常识密码体制发展简史原始的原始的密码体制密码体制古典古典密码体制密码体制近代近代密码体制密码体制14PPT课件保密通讯的基本常识明文与密文在通讯过程中,当甲方通过公共通道向乙方传递信息时,为了不被窃取或修改,往往可将信息改变为秘密形式,这时将原信息称为明文明文,明文的秘密形式称为密文密文。明文明文密文
5、密文加加 密密解解 密密15PPT课件保密通讯的基本常识保密通讯的基本模型兄妹好朋友小明小虹小强16PPT课件保密通讯的基本常识保密通讯的基本模型甲方甲方乙方乙方密文解密密文解密明文加密明文加密第三方第三方密文密文17PPT课件保密通讯的基本常识密码体制评价标准v敌方难于破译收发双方使用的密钥v有足够多的密钥供收发双方选择使用v加密解密的运算较为容易操作,不会误译 18PPT课件古典密码体制古典密码学是现代密码学的渊源,这些密码大多比较简单,用手工或机械操作即可实现。加密和解密的方式千差万别,但任何密码体制本质上都是采用了不同的数学模型。19PPT课件换位加密术栅栏加密法 明文 MEET ME
6、 TONIGHT ZQHIOETEXTGNTMEMEOIHQZMEMTNGTXET20PPT课件替换加密术猪圈加密法 21PPT课件原文CRYPTOGRAPHY 22PPT课件古典密码体制恺撒密码体制加密方法:取一个整数 ,然后将明文中每个英文字母改用在它 位之后的那个字母来代替。例如,取k=10,而明文为“battle”。这时,字母b改成它10位之后的字母l。251kkk思思 考考k k为何不能取为何不能取0 023PPT课件abcdefghijklmnopqrstuvwxyz12345678910注意英文中最后一个字母注意英文中最后一个字母z向后向后又回到字母又回到字母a25battle2
7、4PPT课件古典密码体制恺撒密码体制经过这个字母代换方式,上述明文就成为密文“”。其中k=10即是加密密钥。lkddvo25PPT课件古典密码体制恺撒密码体制采用同余符号,则上述密码体制的加密运算为 26mod10 xxEy明文battleontuesdayXYx+10mod26密文1019191141413 19 20 4 18 3 0 24111033211424 23 3 4 14 2 13 10 8 L K D D V O Y X D E O C N K I?字母数字对应表字母数字对应表26PPT课件古典密码体制恺撒密码体制为方便起见,我们用英文来介绍这种密码体制即将a,b,c,y,z
8、依次用数字0,1,24,25表示a0b1c2d3e4f5g6h7i8j9k10l11m12n13o14p15q16r17s18t19u20v21w22x23y24z2527PPT课件补充同余的概念设m和n都是整数,如果有一个整数k,使得n=km,就说n是m的倍数,也说m是n的因数,也说m整除n,记作设m是正整数,a和b是整数,如果就说a和b同余模m,记作如果不成立,就说nmbammbamod)(modmba 28PPT课件古典密码体制恺撒密码体制课堂练习取k=6,试将明文math进行加密。sgznabcdefghijklm0123456789101112nopqrstuvwxyz1314151
9、617181920212223242529PPT课件古典密码体制恺撒密码体制解密运算 26mod16yyDx密文LKDDVOYXDEOCNKIYY+16XY+16mod26明文 11 10 3 3 21 14 24 23 3 4 14 2 13 10 8 27 26 19 19 37 30 40 39 19 20 30 18 29 26 24 101919114 14 13 19 10 4 18 3 0 24 b a t t l e o n t u e s d a y加密规则与解密规则互为逆运算,由于事先约定好运算规则,并且加密规则与解密规则互为逆运算,由于事先约定好运算规则,并且高度保密,所
10、以这一对运算分别被称为加密密钥、解密密钥,高度保密,所以这一对运算分别被称为加密密钥、解密密钥,统称为密钥。统称为密钥。26mod10yyDx30PPT课件古典密码体制恺撒密码体制课堂练习取k=6,试将密文sgznksgzoiy进行解密 mathematicsabcdefghijklm0123456789101112nopqrstuvwxyz1314151617181920212223242531PPT课件古典密码体制恺撒密码体制缺点:是密钥量太小,只有25个。如果知道密码体制,可以逐个试k的值,很容易就恢复成明文。这种体制在公元9世纪才被阿拉伯人找到破译方法,在阿拉伯科学家阿尔金迪关于破译加
11、密信息的手稿中有详细的描述。破译的方法是频率统计分析频率统计分析。思思 考考恺撒密码体制恺撒密码体制的不足之处的不足之处32PPT课件古典密码体制恺撒密码体制33PPT课件思 考恺撒密码体制中是用“+”进行加密,是否能够对其进行改造,用“”进行加密?如果可行,解密的过程应该如何?34PPT课件深入探究恺撒密码体制恺撒密码体制加密方法:取一个整数 ,然后将明文中每个英文字母改用在它k位之后的那个字母来代替。251 kk26modkxy35PPT课件深入探究思思 考考能否用乘法运算来能否用乘法运算来“改造改造”恺撒密码体制呢恺撒密码体制呢26modkxy 36PPT课件深入探究比如:取k=3(1k
12、25)明明 文文math对应数字对应数字1201973xy3x(mod26)密密 文文 36 0 57 21100521 k a f v 37PPT课件深入探究如何将密文“kafv”还原为明文“math”呢?恺撒密码体制恺撒密码体制加密钥匙加密钥匙8解密钥匙解密钥匙18同余意义下的互为相反数同余意义下的互为相反数)26(mod0188“改造改造”后的体制后的体制加密钥匙加密钥匙3解密钥匙解密钥匙?同余意义下的互为倒数同余意义下的互为倒数)26(mod13 k38PPT课件深入探究寻找k=3在模26意义下的倒数!3?(正整数)?(正整数)1(mod26)9 9?31?2?139PPT课件深入探究
13、密密 文文kafv对应数字对应数字1005219yx9y(mod26)明明 文文 90 0 45 189120197 m a t h解密钥匙:解密钥匙:k=9;解密运算应该是解密运算应该是9y还是还是y/9呢?呢?40PPT课件深入探究课堂练习课堂练习自行选择下列中一个自行选择下列中一个k k值,将单词值,将单词mathmath进行加密和解密。进行加密和解密。k=4k=5k=6k=741PPT课件深入探究取k=4时,找不到正整数k,使得4k(正整数)(正整数)1(mod26)?4整数偶数,而整数偶数,而被被26除余数为除余数为1的数必为奇数,故的数必为奇数,故k不能取偶数不能取偶数42PPT课
14、件深入探究aa-1模模26的倒数表的倒数表1139521715931119157172319112152317252543PPT课件)26(modbkxy深入探究恺撒密码体制恺撒密码体制方法一方法一方法二方法二改造后的体制改造后的体制+Hill密码体制密码体制)26(modkxy)26(modkxy 44PPT课件补充同余的性质同余的性质mabmbamaamod,mod;mod那么如果mcamcbmbamod,modmod那么和如果那么和如果,modmodmdcmbambdacmdbcamdbcamodmod,mod和mbamnmnbnamod,mod互素,那么与而如果将同余性质将同余性质与等
15、式性质与等式性质对比记忆对比记忆abbaaa那么如果,;cacbba那么和如果,那么和如果,dcbabdacdcbadbca和,45PPT课件维吉尼亚密码体制1586年,法国外交家维吉尼亚把恺撒密码的模型作另一种改进。恺撒密码的密钥是用同一个数字k=10简单地重复成序列10,10,10,与明文逐位模26相加。维吉尼亚则增加密钥的长度。对于维吉尼亚密码,密钥是一个字序 ,其中m为任意正整数。因此,在原理上存在无限多个密钥。mkkkk,2146PPT课件维吉尼亚密码体制以finger作为密钥,对“battleonTuesday”加密过程可表示如下:明文battleontuesdayx1019191
16、14141319204183024密钥序列58136417581364175813Y=E(x)686251521192160898811密文GIGZPVTVGAIJIIL47PPT课件维吉尼亚密码体制这种密码体制克服了恺撒体制的缺点,明文中前两个字母t被加密成不同的字母G和Z,而密文中前两个G也来自明文中不同的字母b和t,所以加密性能比恺撒体制要好。48PPT课件维吉尼亚密码体制课堂练习以finger作为密钥,试将明文Mathematics进行加密rignidfbviw49PPT课件维吉尼亚密码体制解密过程密文gigzpvtvgaijiilY686251521192160898811密钥序列-
17、5-8-13-6-4-17X=D(y)明文21 16132022921 18 13 20 22 921 18 1310191911414 13 19 20 4 183 0 24b a t t l e o n t u e s d a y50PPT课件维吉尼亚密码体制课堂练习以finger作为密钥,试将密文rignidfbviw进行解密mathematics51PPT课件维吉尼亚密码体制维吉尼亚密码直到二百年后才找到破译方法,破译者是英国人巴比奇(1854年)和德国人卡西斯基(1863年)。破译手段是采用更精细的数学统计方法,关键是首先设法决定密钥的周期长度。密文出现周期性变化,敌方找到密文出现周
18、期性变化,敌方找到k值,便容易破译值,便容易破译 52PPT课件Hill密码体制假设甲方要将信息“HELP”(明文)发送给乙方,则发送者事先与接受者约定某个二维函数,假如设()2122115233xxyxxy53PPT课件然后将HELP分为两组(H,E)和(L,P),按上面的编码方法得:H7 L11 E4 P15用前面的函数()作用后,得Hill密码体制1x2x1x2x21133xxy33437326mod721252xxy34457226mod8思考思考为什么要将为什么要将HELP分成两组?分成两组?54PPT课件Hill密码体制从而将明文转化为密文“HIAT”,这一过程称为加密。IyHy8
19、26mod834726mod73321TyAy1926mod1997026mod07821思考思考解密过程又如何进解密过程又如何进行呢?行呢?55PPT课件Hill密码体制然后甲方将“HIAT”发送给乙方,乙方得到密文之后,仍将密文分成两组并由()解出2187yIyH21190yTyA2122119201715yyxyyx思 考如何由解出下式56PPT课件Hill密码体制如何用Hill密码体制进行解密?2122115233xxyxxy21221131923195yyxyyx57PPT课件Hill密码体制补充知识对于一个n阶方阵A,若存在一个n阶方阵B,使得AB=BA=E(mod m),称A为模
20、m可逆,B为A的逆矩阵,记为B=A-1(mod m)。可验证:26mod11acbdbcadA58PPT课件Hill密码体制模26的倒数表a1357911 15 17 19 21 23 25a-11921 15319723 11517 2559PPT课件上述例子也可用矩阵运算表示如下:明文HELP的加密过程为:Hill密码体制9201715,5233DyEx26mod733437326mod1997155112(密文)HAITTIAHExPELH19807154117523315411760PPT课件Hill密码体制反过来,解密过程可计算如下:什么是矩阵?)(15411719807920171
21、519807明文HELPPELHDyTIAH61PPT课件Hill密码体制2122115233xxyxxy212211329359yyxyyx211915273yyx21296273yyx26mod9926mod17926mod151526mod1272122119201715yyxyyx62PPT课件Hill密码体制练 习试将HIAT进行解密2111715yyx24181771526mod7212920yyx2128972026mod42111715yyx323191701526mod11212920yyx17119902026mod1563PPT课件Hill密码体制再将 代入得到从而得到明
22、文“HELP”,这一过程称为解密。21,yyExHx4721PxLx151121思 考当明文字母个数不是偶数时,怎样进行加密运算?64PPT课件简单的机械加密普通的打字机可以提供多种简单的替换加密方法。例如,不要击打表示正确字母的那个键,而是击打它上头偏左的键;也可以选择击打它的右旁键,或击打上头偏右的键。如果你选择击打上头偏左键的方案,那么I LOVE YOU打字后成了:8 O9F3 697而如果选择击打右旁键的方案,那又成了O :PBR UPI65PPT课件流密码体制M序列密码体制在第一次世界大战后又有了新的突破,这种新体制被称为流密码,在技术上依托于一种新的基本元件,称为移位寄存器。66
23、PPT课件流密码体制M序列一个n级的移位寄存器由两部分组成:移位寄存部分计算反馈部分67PPT课件流密码体制M序列移位寄存部分:可存放n个数字 ,这n个数字组成一个状态,其中每个字母取值可为0或1。naaa,2168PPT课件流密码体制M序列计算反馈部分:位移寄存器的工作过程可用下图表示,21aaa1a2 an-1an输出x1x2x n-1x na1a2 an-1an反馈69PPT课件流密码体制M序列例如:在一个3元移位寄存器中,取当取初始状态为 时,32213211,xxxxxxxf1,1,1,321aaa3214,aaafa0,1,1,432aaa0,1,0,654aaa411112mod
24、011a1,1,1将 输出,初始状态 变成1,0,1,543aaa如此类推,下一个状态70PPT课件流密码体制M序列它会产生以下8个连续的状态(可自行验证)且继续输出的 是一个周期长度为8的两元序列可以证明:n级移位寄存器产生的二元序列必定是周期序列,且这个序列的最大周期长度为进一步还可证明:n级移位寄存器生成的周期长度为 的二元序列 表示此序列连续的 个状态。且连续的状态一定对应原二元序列。011,001,000,100,010,101,110,111,21naaa1010001110100011,21naaan2n2,221naaan271PPT课件流密码体制M序列M序列中1和0的位置排列
25、非常平衡。数学上称作是“伪随机性”,它很像是随机产生的序列,但实际上有内在规律,它是由给定的布尔函数及初始状态产生的,所以是“伪”随机。72PPT课件流密码体制M序列流密码体制:发方用完全随机的二元序列作为密钥,收方无法重新得到此序列进行去密运算、现在M序列是由移位寄存器生成的,发方将明文(二元序列)加上M序列密钥(模2加法)得到密文,收方用同一个移位寄存器生成同一个M序列密钥再加到密文上便恢复成明文。73PPT课件流密码体制M序列例如,甲方发送信息“HEAD”给乙方。则甲方采用如上 加密11101000A 000B 001C 010D 011E 100F 101G 110H 111明文HEAD二进制111100000011111110101010密文00001010100174PPT课件流密码体制M序列目前使用的移位寄存器,级数n均在30以上。n级的M序列共有 个。这是一个很大的数目,用来作密钥很理想,不仅数量多,而且它们的伪随机性能不易破译。用M序列的流密码体制目前仍是无线电保密通信的基本手段之一。nn12275PPT课件小 结v保密通讯的基本常识v古典密码体制 凯撒密码体制 维吉尼亚密码体制 Hill密码体制 流密码体制76PPT课件作 业v课本P50习题1、2、3、4、5。77PPT课件