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