02密码学概论讲解.pptx

南京邮电大学南京邮电大学第第2讲讲 密码学概述密码学概述2024/9/24 周二南京邮电大学2本讲内容本讲内容密码学概述密码学概述1密码学基础密码学基础2传统密码技术传统密码技术3流密码与分组密码流密码与分组密码42024/9/24 周二南京邮电大学31 概述概述u密码学是一门古老而又年轻的学科密码学是一门古老而又年轻的学科u2020世纪世纪4040年代以前，密码只是一门艺术，而不是年代以前，密码只是一门艺术，而不是一门科学一门科学u19491949年年 Claude.E.ShannonClaude.E.Shannon发表发表保密系统的信息保密系统的信息理论理论 nCommunication Theory of Secrecy Systemsn密码学真正成为一名科学u二战以前，只是和军事、机要、间谍工作联系在二战以前，只是和军事、机要、间谍工作联系在一起一起u随着计算机通信技术，特别是随着计算机通信技术，特别是InternetInternet的应用，的应用，促进了密码学的发展促进了密码学的发展2024/9/24 周二南京邮电大学41.1 密码学的发展概况密码学的发展概况u古典密码学古典密码学n隐写术、黑帮行话u近代密码学近代密码学n电报通信建立起来后，采用复杂的机械和电动机设备实现u现代密码学现代密码学n1949年 Shannon 的保密系统的信息理论n1976年 Diffie和Hellman的密码学的新方向n1977年 美国 DESn2000年 美国 AES2024/9/24 周二南京邮电大学5本讲内容本讲内容密码学概述密码学概述1密码学基础密码学基础2传统密码技术传统密码技术3流密码与分组密码流密码与分组密码42024/9/24 周二南京邮电大学62.1 密码学基本概念密码学基本概念u密码学（Cryptology）n研究秘密通信的原理和破译密码的方法的一门学科nThe art and science of making and breaking“secret codes”u密码编码学（Cryptography）n研究对信息进行变换，以保护信息在信道中安全传送研究对信息进行变换，以保护信息在信道中安全传送nmaking“secret codes”u密码分析学（Cryptanalysis）n研究如何分析和破译密码nbreaking“secret codes”2024/9/24 周二南京邮电大学7 其它概念其它概念u明文（明文（PlaintextPlaintext）n需要变换的原消息u密文（密文（CiphertextCiphertext）n明文经过变换成为另一种隐蔽的形式u加密（加密（EncryptionEncryption）n完成变换的过程u解密（解密（DecryptionDecryption）n从密文中恢复出明文u密钥（密钥（KeyKey）n加密密钥（Encryption Key）n解密密钥（Decryption Key）2024/9/24 周二南京邮电大学8密码编制和分析过程图密码编制和分析过程图 明文密钥k密钥k明文密文加密器 Ek解密器 Dk安全信道非法接入者或密码分析员搭线信道（主动攻击或被动攻击）2024/9/24 周二南京邮电大学9密码体制分类密码体制分类u一种完整的密码技术包括一种完整的密码技术包括密钥管理密钥管理和和加密处理加密处理两个方面两个方面n密钥管理包括密钥的产生、分配、保管和销毁等n加密处理包括加密和解密u根据密钥的特点，又可分为：根据密钥的特点，又可分为：n私钥（单钥、对称）密码体制n公钥（双钥、非对称）密码体制2024/9/24 周二南京邮电大学102.2 不可攻破的密码系统不可攻破的密码系统u一个密码系统设计通常的基本要求是一个密码系统设计通常的基本要求是n知道KAB时，EAB容易计算n知道KAB时，DAB容易计算n不知道KAB时，有C=EAB(M)不容易推导出Mu绝对不可破译的密码在理论上是存在的绝对不可破译的密码在理论上是存在的n一次一密u更有实际意义的是计算上不可破译更有实际意义的是计算上不可破译2024/9/24 周二南京邮电大学11“一次一密一次一密”加密加密e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111heilhitler001000010100001010111100000101111101110101111100000101110000110101100001110110111001110101srlhssthsr加密加密:明文 密钥=密文Plaintext:Key:Ciphertext:2024/9/24 周二南京邮电大学12“一次一密一次一密”解密解密e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111srlhssthsr110101100001110110111001110101111101110101111100000101110000001000010100001010111100000101heilhitler解密解密:密文 密钥=明文Ciphertext:Key:Plaintext:2024/9/24 周二南京邮电大学132.3 密码分析密码分析u密码设计与密码分析是共生的密码设计与密码分析是共生的u攻击密码的方法有：攻击密码的方法有：n穷举破译法(Exhaustive Attack Method)n完全试凑法(Complete Trial-and-error Method)n改进试凑法n确定分析法n统计分析法n2024/9/24 周二南京邮电大学14密码分析密码分析u基本的假设基本的假设n敌方完全知道加密算法n只有密钥是敌方不知道的u一般称为一般称为 Kerckhoffs Principlen加密算法不是保密的u为什么这样假设为什么这样假设n过去的经验表明一但加密算法被破解，一切全完了n加密算法无法保证敌方永远不知道n最好提前知道加密方法中的不足2024/9/24 周二南京邮电大学15对密码系统安全性的基本要求对密码系统安全性的基本要求u至少是在实际上不可破的至少是在实际上不可破的u安全性在于密钥，而不是算法安全性在于密钥，而不是算法u密钥空间足够大密钥空间足够大u加解密算法必须是计算上可行的加解密算法必须是计算上可行的2024/9/24 周二南京邮电大学16本讲内容本讲内容密码学概述密码学概述1密码学基础密码学基础2传统密码技术传统密码技术3流密码与分组密码流密码与分组密码42024/9/24 周二南京邮电大学173 传统密码技术传统密码技术u换位密码换位密码n按某种规则把字符秩序打乱重排u代替密码代替密码n明文按照字母表当前字母后移n位加密而产生u转轮机转轮机u电码本电码本2024/9/24 周二南京邮电大学183.1 换位密码换位密码 1 12 23 34 4 3 34 42 21 1密钥 type 44矩阵 栅栏技术明文：明文：canyoubelieveher问题？没有消除字母的使用频率，容易识别1 2 3 4c a n yo u b el i e ve h e rc a n y o u b e l i e v e h e rn y a c b e u o e v i l e r h e密码位置密码位置明文位置明文位置2024/9/24 周二南京邮电大学193.2 简单代替密码简单代替密码u明文明文:fourscoreandsevenyearsagou密钥密钥:a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y yD D E E F F G G H H I I J J K K L L M M N N O O P P Q Q R R S S T T U U V V W W X X Y Y Z Z A A B Bz zC Cu密文密文:IRXUVFRUHDAGVHYHABHDUVDIRu移动移动3 3位就是凯撒密码（位就是凯撒密码（CaesarCaesars ciphers cipher）明文密钥2024/9/24 周二南京邮电大学20凯撒密码的解密凯撒密码的解密u明文明文:spongebobsquarepantsu如何破解？平均需要尝试多少次？如何破解？平均需要尝试多少次？a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y yD D E E F F G G H H I I J J K K L L M M N N O O P P Q Q R R S S T T U U V V W W X X Y Y Z Z A A B Bz zC CPlaintextCiphertextu如果我们知道使用的是凯撒密码如果我们知道使用的是凯撒密码uCiphertext:Ciphertext:VSRQJHEREVTXDUHSDQWU2024/9/24 周二南京邮电大学213.3 改进的代换密码改进的代换密码u不是简单的移位，而是进行随机的排列不是简单的移位，而是进行随机的排列u例如例如u那么存在那么存在26!226!28888 个可能的密钥个可能的密钥a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y yJ J I I C C A A X X S S E E Y Y V V D D K K W W B B Q Q T T Z Z R R H H F F M M P P N N U U L L G Gz zO O明文密文2024/9/24 周二南京邮电大学22多大才算大？多大才算大？u一年中的秒数一年中的秒数3103107 7u太阳系的平均年龄（年）太阳系的平均年龄（年）6106109 9u太阳系的平均年龄（秒）太阳系的平均年龄（秒）2102101717u50M50M计算机一年时钟数计算机一年时钟数1.6101.6101515u6464位数的大小位数的大小1.8101.8101919u128128位数的大小位数的大小3.4103.4103838u256256位数的大小位数的大小1.2101.2107777u宇宙中的电子数目宇宙中的电子数目8.37108.37107777u128bit 2128bit 21281283.4*103.4*1038 38 每秒一亿把钥匙需要每秒一亿把钥匙需要10101414年。年。2024/9/24 周二南京邮电大学23密码分析方法密码分析方法u我们知道采取的是代换密码我们知道采取的是代换密码u并不是通过位移实现并不是通过位移实现u我们能通过下面的密文发现密钥吗？我们能通过下面的密文发现密钥吗？PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCPBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFAFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA2024/9/24 周二南京邮电大学24分析过程分析过程u当然不能尝试当然不能尝试2 28888 个密钥个密钥u我们能更聪明一些吗？我们能更聪明一些吗？u英文字母出现的频率英文字母出现的频率2024/9/24 周二南京邮电大学25分析结果分析结果u密文密文:PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQPBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFAAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFAA AB BC CD DE EF FG GH HI IJ JK KL LM MN NO OP PQ QR RS ST TU UV VW WX XY Y212126266 61010121251511010252510109 93 310100 01 11515282842420 00 027274 42424222228286 6Z Z8 8密文中字母出现的频率:u使用下面的信息解密使用下面的信息解密2024/9/24 周二南京邮电大学26频率图对比2024/9/24 周二南京邮电大学273.4 转轮机转轮机u2020世纪世纪2020年代，人们就发年代，人们就发明了机械加密设备明了机械加密设备u转轮机有一个键盘和一系转轮机有一个键盘和一系列转轮列转轮u当转轮移动后，下一次代当转轮移动后，下一次代替将不同替将不同2024/9/24 周二南京邮电大学28Rotor2024/9/24 周二南京邮电大学293.5 电码本密码电码本密码u传统的电码本密码就像字典一样的书传统的电码本密码就像字典一样的书uZimmermanZimmerman电报通过电码替换电报通过电码替换FebruarFebruar1360513605festfest 13732 13732finanziellefinanzielle 13850 13850folgenderfolgender 13918 13918FriedenFrieden1714217142FriedenschlussFriedenschluss1714917149:u现代的分组密码就如同电码本现代的分组密码就如同电码本2024/9/24 周二南京邮电大学30Zimmerman电报电报2024/9/24 周二南京邮电大学31Zimmerman电报的解密结果电报的解密结果u英国破解了部分的英国破解了部分的电码本电码本2024/9/24 周二南京邮电大学32本讲内容本讲内容密码学概述密码学概述1密码学基础密码学基础2传统密码技术传统密码技术3流密码与分组密码流密码与分组密码42024/9/24 周二南京邮电大学33流密码与分组密码流密码与分组密码u流密码流密码 使用方法与使用方法与“一次一密一次一密”相同相同n密钥相对较短n密钥被“扩展”成二进制的密码流u分组密码分组密码 基于基于电码本电码本的思想的思想n分组密钥确定了“电码本”n每一个密钥确定不同的“电码本”n同时使用了“混淆”和“扩散”2024/9/24 周二南京邮电大学344.1 流密码流密码u密钥流的使用方法与密钥流的使用方法与“一次一密一次一密”相同相同u基本思想：基本思想：n首先利用密钥K产生一个密钥流n然后使用如下规则对明文串x=x0 x1加密 y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)u解密时，使用相同的密钥流与密文做运算解密时，使用相同的密钥流与密文做运算(XOR)(XOR)u已经不如已经不如分组密码分组密码流行了流行了u两个算法两个算法nA5/1nRC42024/9/24 周二南京邮电大学354.6 分组密码分组密码u类似类似“电码本密码电码本密码”u将明文编码后的数字序列划分成长为将明文编码后的数字序列划分成长为m m的明文组的明文组u各明文组在长为各明文组在长为i i的密钥组的控制下变换成长为的密钥组的控制下变换成长为n n的密文组的密文组u通常取通常取n nm mnnm 扩展分组密码nnm 压缩分组密码u典型分析密码结构典型分析密码结构-Feistel-Feistelu美国商用数据加密标准美国商用数据加密标准DESDESn（Data Encryption Standard）南京邮电大学南京邮电大学