课件第2章密码学基础

不 学 都追不破 追到心 ~喜 的人认真解解看~看到最后 笑 最近和一个心仪的 会。可是我用尽了所有方法都解不开这个 ****-/*----/----*/****-/****-/*----/---**/*----/****- /-****/***--/****----/----*/**---/-****/**---/**---/***--/--***/**** 她唯一给我的提5层加密 ..也就是说 5 才是答案..好郁闷阿..救救我吧 6首先要把摩斯 给解开来.应该是. 2374.然后呢?然后我再想 12楼（LZ同学 经过昨天一晚的奋斗。我还是 不了。不过今天我死磨她，叫她给提示的后，她说途中有一 表则是我们人类每天都可能用到的东西.我会再套多点讯息的..希望大大帮忙解答阿..毕竟我也希望不要她亲口说出来这个 38楼 数字有偶数个，且注意到41组合出现数次。于是分组：41944181416341926223 意个位数总是1~4于是颠倒：14491418143614292632 翻成英文字母，前26大写后小写：NwNRNjNcZfu然后卡住了„„按大小写分别穷举换位也没看出结果„ 83楼：（注意，此公就是后来破 的大神 38楼给我的提示。还是 到 出来分组后的数字分是，4194418141634192622374并且每个组合个位数都不超过4。 数是和这两个数字后面有以外其他的都没有。 的键盘上和的字母也是个的，其他的都不超过4个字母。那么，按照上面的组合 可得。GZGTGOGXNCS 我们发现每一组数字都能解释出来。目前我只能 到这里的。虽然很不通顺，但我相信这里 93楼（我觉得这位仁兄找到了突破点，虽然不对但是帮了大忙，让别人想到键盘带入 2374 207楼（大神啊，你成就了美满姻缘 步骤。如下。 4194418141634192622374 4 特别是除了十位数是7和9这两个数字后面有4以外其他的都没有4 看图 的键盘7和9的字母也是4个的，其他的都不超过4个字母 那么，按照上面的组 得 GZGTGOGXNC 后我们发现每一组数字都能解释出来 目前我只 这里的。虽然很不通顺，但我相信这里应该是个突破点。93楼的键盘代入也给了我很大的提示。包括楼主的“她说途中有一个步骤是"替代"而表则是我们人类每天都可能用到的东西”那么很可能就是电脑键盘。因为QWE的格式是被世人所认可的，也就有可能成为的码表。码表QWE=ABC依次类推。那 GZGTGOGXNC 就G=OZ=TG=OT=EG=OO=IG=OX=UN=YC=V 翻译过来就是OTOEOIOUYVL其实这里就已经大概知道答案是什么了。按照逻辑来整理，只要你重组这些字母的时候你就看到了虽然重组有很多种例如，LVIOUETOOO可是这些没有语言性质。因为楼 最终答案是语。所以唯一一个符合逻辑的答案应该是ILOVEYOUTOO. 可是我还不确定。因为这里我才解 所以我决定用OTOEOIOUYVL 。我用了很 方法。凯撒，乘法等等。。最后我发现了只有栅栏才能读得通。分成两排OTOEOIOUYVL重组后，OOTUOYEVOLI。然后倒序ILOVEYOUTOO.ILOVEYOUTOO.就自然而然的出来了。最后我才肯 就是ILOVEYOU 笔记本或者你经常接触电脑。另外楼主和楼主的女人关系应该是认识很久的那种，而不是一见钟情。而且楼主告白的时候应该有用到ILOVEYOU或者我爱你之类的字眼。对不对阿？ 好累啊 祝楼 咯.因为她是爱你的学基础古典替对称密公开密消息学新学基础知引解决数据 性、完整性、不可否认性以 识别等 技术是保 基础 学(Cryptography)包 编码学 分析学两部分 变化的客观规律应用于编 用来保守通 的，称为码编码学 研 变化客观规律中的固有缺陷，并应用于破 以获取通的，称 分析学历 宋代的曾公亮、丁度等编 卡西斯基所著 和破译技术 香 了 体制的通信理论趣 “黑话北宋曾公亮——军 《美丽的心灵 ·福布斯·纳英格玛(ENIGMA)——第一部机 体消息 学中被称为明文 inText） 消息以隐藏它的内容的过程称为加密被加密的消息称为密文(Cipher把密文转变为明文的过程称 (Decrypt)

体完 体制要包括如下五个要 M是可能明文的有限集称为明文空间 C是可能密文的有限集称为密文空 可能密钥构成的有限集称为密钥空间 E为加密算法，对于任一密钥，都能够有效地计算； D 算法，对于任一密钥，都能够有效地计算 体系必须满足如下 加密算法(Ek：M->C) 算法(Dk：C->M)满足Dk(Ek(x))=x,这里 破译者不能在有效的时间 出密钥k或明文x丝男：发送方、加密女神：接收方方麻麻接收告白：原告白->马甲：加马甲->告白 的分依 体制分类 古典加密体制、现代加密体依据密钥特点分 对称密钥加密、公开密钥加依据对明文数据处理的 分 (blockcipher)、序 (stream依 的内容分 基于算法、基于 分析也称 分 主要包括 唯密 、已知明 、选择明 、自适应选择明、选择密 、选择密Doyou量子研究的内容，就是如何利用量子技术在量子信道上安全可靠地分配密钥。在信息中，密钥的地位是举足轻重的。但是，如何安全可靠、迅速高效地分配密钥，一直是学领域的题。与传统学不同，量子学利用物理学原理保护 通常把以量子为信息载体，经由量子信道传送，在合法用户之间建立共享的密钥的方法，量钥分(QKD)，“海森堡测 原理”及“单量子不可 定理”保证。“森堡测不准原理”是量子力的基本原它，在时同的精度测定量子的位置与动量是不可能的，只能精确测定两者之一。“单量子不 定理”是“海森堡 原理”的推论，它表明在不知道量子状态的情况 单个量子是不可能的，因为单个量子就只能先作测量，而测量必然改变量子的状态，所以说不统信息论的束缚，设计出无条件安全的。古典替简单代简单代 指将明文字母表M中的每个字母用密文字母表C代替 例如：移 、乘 、仿 等移 具体算法是将字母表的字母右移k运算。 每一个字母具有两个属性，本身代表的含义，可计算序列 加密函数：Ek(mm+k)mod 函数：Dk(c)=(c–k)mod数论整除：a=mb+k其中a、b、m、k都是整数如果k=0，则a能被b整greatestcommonleastcommon素数：只能被自己和1互素 模：k=amod凯撒凯 体系的数学表示M=C={有序字母表}，q26，k3 其中q为有序字母表的元素个数，本例采用英文字母q=26使用凯 对明文字符串逐位加密结果如下 明文信息Mmeetmeafterthetoga 密文信息C=phhwphdiwhowkhwrjd字母对照abcdefghij0123456789klmnopqrstuvwxyz乘乘将明文字母串逐位乘以密钥k并进行模运算数学表达式:Ek(m)=k*mmod (k,q)=1 (k,q)=1表示k与q的最大公因子为1算法描述 K={k∈整数集|0<k<26， Ekm)=kmmodq Dk-1(c)=k-1cmodq，其中k-1为k在模q下的乘法逆密钥取值与乘法乘 的密钥k与26互素时，加密变换才是一一映射的k的选择有11种：3、5、7、9、11、15、17、19、21、23、k-1为k在模q其定义为k-1*kmodq可采用扩展的欧几里德算法。欧几里德算法又称辗转相除法用于计算两个整数a和b的最大公约数仿仿可以看作是移 和乘 的结合 体制描K={k1,k2∈Z|0< Ek(m)=(k1m+k2)modDk(c)=k1-1c-k2)modq，其中k1-1为k1在模q下的乘法逆密钥情况，k1和k2仿 事设k＝（5，3），注意到5-加密函数 Ek(x)=5x+3(mod 函数

mod Dk(y)=21(y-3)mod26=21y–11(mod26加密明文“yes”的加密 过程如下

s

=5

3

=

-

= = Mod

Mod加密过 过基于统计 分简单代 的加密是从明文字母到密文字母的一映1412.70128.167864

4.25

6.996.094

7.506.744.02

9.056.3275.982.78

2.40

1.

2.758

2.

1.974 1.4920

0.7720.153

0.09

0.978

0.

0.07 多表代 是以一系列代替表依次对明文消息的字母进代替的加密方多表代 使用从明文字母到密文字母的多个映射来隐单字母出现的频率分每个映射是简单代 中的一对一映 若映射系列是非周期的无限序列，则相应 称为非周期表代 非周期多表代 对每个明文字母都采用不同的代替表(或密钥)进行加密，称一次一 维吉尼亚经典的多表代 有 Vigenère、Beaufort、RunningKey、Vernam和轮转机 维吉尼亚 是以移位代替为基础的周期多表代 加密时每一个密钥被用来加密一个明文字母，当所完后，密钥又重新循环使维吉尼亚 算法如下 Ek(m)=C1C2Cn，其中Ci=（miki）mod 密钥K可以通过周期性反复使用对称密者发送 接收 密 密

对称密 加密模 分 原理 明文消息分成若干固定长度的组，进行加密 亦然 BLOCKLLLL„L

„D

D

D

BLOCKD

LLLL„L

BLOCK序 （ 通过伪随机数发生器产生性能优良的伪随机序列(密钥流)，该序列加密明文消息流，得到密文序列 亦然 „„„„

+„„„ 数据加密标准1973 局NBS公开征集国 标准方案 算法必须提供高度的安全 算法必须有详细的说明，并易于理解 算法的安全性取决于密钥，不依赖于算 算法适用于所有 算法适用于不同应用场 算法必须高效、经济 算法必须能被证实有 算法必须是可出1974年NBS开始第二次征集时，IBM公司提交了算法LUCIFER 准FIPSPUB46”发布，简称为DESS-S-DES是由 EdwardSchaeffer教授 输入为一个8位的二进制明文组和 与加密基本一) 加密:IP-1(fk2(SW(fk1(IP(明文) :IP-1(fk1(SW(fk2(IP文

加密过IPIP-8位密

10位密 S-DES的体

过8位明IPIP-8位密S-DES循环左移函数585LS-LS-5585LS-LS-585LS-LS-5S-DES

S-DES

884E/P844E/P84F448fS0S12244SW4E/P84F448fS0S12244P4IPP4IP-++IP-+“⊕”:按位异或运算+ +S盒函查 S0和S1为两个盒子函数，将输入作为索查输出+SW:将左4位和右4位交换+88SDES012 012S盒函

S0=

103321

S1=

01213313

3210S盒函数按下述规输入的第1位和第4位二进制数合并为一个两位二进为S盒的行号索引将第2位和第3位同样合并为一个两位二进制数，作为S盒列号索引确定S盒矩阵中的一个系数（i，j）此系数以两位二进制数形式作为S盒的输出例如 L’=（l0,l1,l2,l3）=（0，1，0，0）， 在S0中确定系数3，则S0的输出为11BDES

64 置换循环左移置换循环左移置换循环左移置换IPIP-1DESDES的安全1977年，耗资两千 建成一个专门计算机用于DES破译，需要12个小时 1994年世 大会，M.Matsui提出线性分析方法，利243个已知明文，成功破译1997年首届“向 天时 了用DES加密的一段信息 年月日，电 组织25 机以22.5小时成 DES加密算法后，DES将不再作 加密标准分 的工作模电子编码本模式 „„„„„„密文分组密文分组„密文分组密文分组„密文分组+++„ 密文分组密文分组密文分组密文分组密文分组 CBC移位寄存S移位寄存S64-加加明文分组密 密明文明文分组顺S码序明文分组S（（明文分组明文明文分组明文分组„序 明文分组序S

丢丢选择SSS加密文分组移位密文分组移位寄S64-加加丢丢选择S+移位寄存S64移位寄存S64-加加明文分组 丢选择丢选择S明文分组输顺明文分组S序 明文分组S序密文分组馈密文分组馈S64-S64-加移位寄加移位寄存式丢选择S明文丢选择S明文分组明文分组（序明文明文分组 2.14OFB其他对 简三重AES算1AddRoundKey骤——XOR运2SubBytes骤——非线性的替换3ShiftRows骤——横列进行循环式移4MixColumns骤——线性转换来公开密公开密 又称非对称密 或双密加密密钥 密钥为两个独立密钥公开密 的通信安全性取决于私钥 性Bob

Alice

Alice

密 密公开密 的模公开密钥理公开密 思公开密 是1976年由WhitfieldDiffie和man在其 学新方向”一文 单向陷门函数f(x)，必须满足以下三个条件x，计算y=f(x)是容易②给定y,计算x使y=f(x) 的（所谓计算x=f- 是计算上相当复杂已无实际意义在δ，已知δ时对给定的任何y，若相应的x存在，则计算xy=f(x)是容易公开密钥的应Bob

Alice

Alice

密 密

公开密 的加密模公开密钥的应AliceBob

Bob

密 公共信 密

公开密 的认证模公 体制基于数学难NP= 数学 素数p的原根（primitiveroot）的定义：如果a是素数p的原根，则数amodpa2modp,„,ap-1modp是不同意的整数b，可以找到唯一的幂i，满足b≡aimodp，且注：“b≡amodp”等价于“bmodpap”，称为“b与a模p同余离散对 若a是素数p的一个原根，则相对于任意整数b（bmodb≡aimodp，i称为b的以a为基数且模p的幂指数，即离 对于函数y≡gxmodp，其中，g为素数p的原根，y与x均 注：离散对数的求解为数学界公认 问题 man密钥交换算Alice和Bob协商好一个大素数p，和大的整数g，1<g<p，g是 Alice选取大的随机数x<p，并计算Y=gx(mod②Bob选取大的随机数x<p，并计算Y=gx(modAlice将Y传送给Bob，Bob将Y传送给④Alice计算K=(Y)X(modP)，Bob计算K＝(YX(mod显而易见K=K=gxx(modP)，即Alice和Bob已获得了相同值K Thesimplestandtheoriginalimplementationoftheprotocolusesthemultiplicativegroupofintegersmodulop,wherepisprime,andaprimitiverootmodulop.Hereisanexampleoftheprotocol,withnon-secretvaluesinblue,andsecretvaluesin AliceandBobagreetouseaprimenumber=23andbaseg=5(whichisaprimitivemodulo Alicechoosesasecretintegera=6,sendsBobA=gamod A=56mod23= Bobchoosesasecretintegerb=15,sendsAliceB=gbmod B=515mod23= Alicecomputess=Bamod s=196mod23= Bobcomputess=Abmod s=815mod23= AliceandBobnowshareasecret(thenumber2).RSA公开密钥欧拉欧拉函数是欧拉定理的 被称为n的完全余数集合。Zn包含的元素个数记做φ(n)，称为欧拉函数，其中φ(1)被定义为1，但是并没有任何实质的如果两个素数p和q，且np×qφ(np-1)(q-欧拉定理的具体表述：正整数a与