现代密码学(第一章)

1、2020/9/9,1,第一章：密码学基础,一、信息安全的基本概念 二、密码体制的分类 三、古典密码 四、密码分析,2020/9/9,2,一、信息安全的基本概念,信息的载体 信息的存放地点称为媒质。 通信伙伴之间有一条传送信息的通道，称为信道。 媒质和信道统称为信息的载体。 通常：媒质是开放的，共享的，因而是不安全的；信道也是不安全的公共信道。,2020/9/9,3,一、信息安全的基本概念,对信息的载体存在两种攻击： （1）被动攻击。攻击者通过各种办法（如搭线窃听，电磁窃听，声音窃听，非法访问等）来非法截收信息。 （2）主动攻击。攻击者对载体中的信息进行非法篡改（如删除、增添、重放、伪造等）。,

2、2020/9/9,4,一、信息安全的基本概念,（为了有效地保护信息，抵抗被动攻击和主动攻击，必须使用密码技术。认识一下名词） 密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支， 密码编码学(Cryptography)，对信息进行编码以保护信息的一门学问。 密码分析学(Cryptanalysis)，研究分析破译密码的学问。,2020/9/9,5,一、信息安全的基本概念,密码技术分为两个部分，第一部分是信息保密，第二部分是信息认证。 信息保密用来抵抗被动攻击。 信息认证用来抵抗主动攻击。,2020/9/9,6,一、信息安全的基本概念,信息保密的功能：信息的加密和解密。（使

3、得除通信伙伴以外的其他人无法获取信息。） 信息认证的功能：对信息的认证，对发送信息者的身份的认证，对接收信息者的身份的认证 。（使得对信息的篡改会被立即发现。）,2020/9/9,7,一、信息安全的基本概念,信息保密系统 信息保密系统又称为加密系统。该系统被描述如下。 用户Alice和用户Bob是一对通信伙伴。 Eve是攻击者（违法入侵者）。,2020/9/9,8,一、信息安全的基本概念,Alice欲发送一个消息m给Bob。 m称为明文。 Alice使用加密密钥z，使用加密算法E，对明文m做以下的变换，称为加密变换： c=E(m, z) c称为密文。 Alice将密文c通过不安全的公共信道发送

4、给Bob。 Bob使用解密密钥k，使用解密算法D，对密文c做以下的反变换，称为解密变换： m=D(c, k) 于是Bob获得了明文m 。,2020/9/9,9,一、信息安全的基本概念,参数与计算的小结 明文m ，密文c； 加密算法E，解密算法D； 加密密钥z，解密密钥k； 加密变换c=E(m, z)，将明文m 变为密文c； 解密变换m=D(c, k) ，将密文c变为明文m 。,2020/9/9,10,一、信息安全的基本概念,攻击者Eve所拥有的基本资源 Eve在不安全的公共信道上截获了密文c。 Eve知道加密算法E和解密算法D。 攻击者Eve可能拥有的更多资源 Eve可能知道密文c所对应的明文

5、m 。（此时所进行的攻击称为已知明文攻击） Eve可能拥有强大的计算能力。 Eve可能缴获了一台加密机（也称为加密黑盒子），可以任意地输入明文，输出密文。（此时所进行的攻击称为选择明文攻击）,2020/9/9,11,一、信息安全的基本概念,攻击者Eve不可能拥有的资源 Eve不知道加密密钥z和解密密钥k。 （事实上，在进行安全性分析时，有时也假设Eve 知道了密钥的一部分，但决不能全部知道） 攻击者Eve的目的 此时Eve是被动攻击者，他的目的是试图获取明文的信息。,2020/9/9,12,一、信息安全的基本概念,攻击者Eve攻击成功的标志 Eve的思路是“不拘一格”。只要Eve以某种方式获取

6、了明文的一定量的信息，就可以算作一种攻击成功。但“攻击成功”的程度有高低之分。比如：能够持续不断地直接获取明文是最高的攻击成功；掌握在未来获取明文的技巧则是低一级的攻击成功；获得明文的某些统计特性是更低一级的攻击成功。,2020/9/9,13,一、信息安全的基本概念,注解一：关于加密算法E和解密算法D 从商用的角度出发，要求加解密算法（E，D）应该是公共的标准算法，是公开的。因此，包括攻击者Eve在内的所有人都知道加解密算法（E，D）。 要求安全性不依赖于加解密算法（E，D）是否保密，而仅仅依赖于密钥是否保密。,2020/9/9,14,一、信息安全的基本概念,注解二：关于已知明文攻击 如果每一

7、次加密/解密过程，都要选择一次加解密密钥（z，k），则加解密方式称为一次一密的。 一次一密的加解密方式通常具有很好的安全性。但是需要频繁地更换密钥，每次通信之前都需要通信伙伴之间进行协商来确定新的密钥（z，k） 。因而一次一密的加解密方式是不实用的。,2020/9/9,15,一、信息安全的基本概念,如果加解密密钥（z，k）在多次加密/解密过程中反复地重复使用，则加解密方式称为多次一密的。 现有的实用加解密方式都是多次一密的。 多次一密的加解密方式极大地省却了通信伙伴的工作量。 但同时，多次一密的加解密方式使得攻击者增加了几种新的攻击手段。其中包括：已知明文攻击。,2020/9/9,16,一、信

8、息安全的基本概念,设攻击者Eve截获了密文c，并且知道了密文c所对应的明文m 。（这种情况是怎样发生的呢？当明文m 是已经过期的消息，可能无法再保密，也可能必须将其公开。因此，这种情况是经常发生的）于是： 在解密方程m=D(c, k)中，Eve知道m 和c，仅仅不知道解密密钥k。 在加密方程c=E(m, z)中，Eve知道m 和c，仅仅不知道加密密钥z。,2020/9/9,17,一、信息安全的基本概念,如果Eve从解密方程 m=D(c, k) 中计算出解密密钥k ，则Eve今后就可以像Bob一样对任何密文c进行解密： m=D(c, k)。 如果Eve从加密方程 c=E(m, z) 中计算出加密

9、密钥z ，则Eve今后就可以像Alice一样对任何明文m进行加密： c=E(m, z)。,2020/9/9,18,一、信息安全的基本概念,还可以给更加宽松的条件。设攻击者Eve获得了以往废弃的n组明文/密文对：（m1，c1），（m2，c2）， （mn，cn）。 于是Eve获得了关于解密密钥k 的方程组： m1=D(c1, k) ， m2=D(c2, k) ， ， mn=D(cn, k) 。 （n越大，解密密钥k 就越容易确定。）,2020/9/9,19,一、信息安全的基本概念,以上就是已知明文攻击。 要抵抗已知明文攻击，必须精心地设计加解密算法（E，D）。（能抵抗已知明文攻击的加解密算法(E,

10、D)并不是很容易构造的。） 例1 设：加密密钥等于解密密钥：z=k；加密算法为c= m+z；对应的解密算法为m=c-k=c-z。（普通加减法） 注意到此时k=c-m。这就是说，只要知道了一组明文/密文对（m，c），就能计算出解密密钥k。,2020/9/9,20,一、信息安全的基本概念,例2 设：加密密钥等于解密密钥，z=(z1, z2)； 加密算法为c=z1m+z2 ；对应的解密算法为m=(c-z2)/z1。（普通加减乘除法） 设攻击者Eve获得了以往废弃的2组明文/密文对：（m1，c1），（m2，c2）。注意到此时 c1=z1m1+z2 ； c2=z1m2+z2 。 这是一个关于密钥(z1,

11、 z2)的 二元一次方程组，能计算出(z1, z2) 。,2020/9/9,21,一、信息安全的基本概念,可以看出，以上两个例子所用的加解密算法都不能抵抗已知明文攻击，因此不能用作多次一密的加解密方式。,2020/9/9,22,一、信息安全的基本概念,注解三：已知明文攻击的一些弱化形式 设攻击者Eve知道了以往的一个密文c以及c所对应的明文m 。 Eve又截获了一个新的密文c， Eve试图猜测出c所对应的明文m。 如果加解密算法设计得“不好”，则密钥对明文的覆盖就可能出现漏洞。此时由m ,c, c猜测出c所对应的明文m就会变得容易得多。可能出现以下的现象：,2020/9/9,23,一、信息安全

12、的基本概念,（1）当c与c 的“距离很近”时， m与m 也“距离很近”，而无论密钥是什么值。 （2）当c与c 具有某种固定的关系A时， m与m 具有某种固定的关系B ，而无论密钥是什么值。 （3）当c与c 具有某种固定的关系A时， m与m “以很大的概率” 具有某种固定的关系B ，而无论密钥是什么值。 （4）当密钥的可能变化范围（密钥量）太小时，攻击者Eve可以穷举搜索密钥。,2020/9/9,24,一、信息安全的基本概念,（简单介绍）为了抵抗诸如此类的攻击，以便适用于多次一密，加解密算法应该满足： （1）具有良好的“混淆性”（confusion）和“扩散性”（diffusion）； （2）具

13、有良好的“非线性性”（non-linearity）； （3）具有良好的“差分均匀性”（difference balance）。 （4）密钥的可能变化范围（密钥量）应该大到不可能穷举搜索密钥（brute force search）。,2020/9/9,25,一、信息安全的基本概念,2020/9/9,26,二、密码体制的分类,密码体制 加解密算法的专业术语为”密码体制”。从原理上，密码体制可以分为两大类： （1）单钥密码体制。（又称为对称密码体制） （2）双钥密码体制。（又称为非对称密码体制，也称为公钥密码体制）,2020/9/9,27,二、密码体制的分类,单钥密码体制 单钥密码体制的加密密钥z和

14、解密密钥k能够简单地相互推导出来。 换句话说： Alice知道加密密钥z，她当然也就知道解密密钥k； Bob知道解密密钥k，他当然也就知道加密密钥z 。 再换句话说， Alice和Bob的地位是对称的，可以双向地发送和接收保密信息。 （其实在一般实用情形之下，总有z=k ）,2020/9/9,28,二、密码体制的分类,双钥密码体制（公钥密码体制） 在双钥密码体制中，要从加密密钥z推导出解密密钥k是很困难的。（虽然，也许加密密钥z唯一地确定了解密密钥k ） 具体地说： Bob拥有加密密钥z和解密密钥k。加密密钥z称为Bob的公钥，解密密钥k称为Bob的私钥。 Bob的公钥z向大家公布。（像电话号

15、码一样） Bob的私钥k被Bob私藏。,2020/9/9,29,二、密码体制的分类,因此，大家都知道Bob的公钥z，而只有Bob自己知道他的私钥k。 因此，大家都能够用Bob的公钥z将明文消息加密变为密文，并把密文向Bob发送，而只有Bob自己能够解密这些密文。 因此，公钥密码体制除了具有信息保密的功能以外，还具有了一种信息认证功能：Alice用Bob的公钥z加密一个消息，谁能把消息正确解密， Alice就认为谁是真正的Bob。,2020/9/9,30,二、密码体制的分类,公钥密码体制的原理：数学难题 例如： 大数分解问题； 离散对数问题； 背包问题； 多项式的分解问题； 格的最小向量问题；等

16、等。,2020/9/9,31,二、密码体制的分类,单钥密码体制与双钥密码体制的比较,2020/9/9,32,三、古典密码,古典密码是密码学的渊源，这些密码大都比较简单，现在已很少采用了。然而，研究这些密码的原理，对于理解、构造和分析现代密码都是十分有益的。,2020/9/9,33,三、古典密码,明文字母表和密文字母表相同，为： Zq=0, 1, , q-1。 明文是长为L的字母串，以m表示： m=(m0 m1, mL-1)， 其中每个mlZq，l=0，1，L-1。 密文是长为L的字母串，以c表示： c=(c0, c1, ., cL-1)， 其中每个clZq，l=0，1，L-1。,2020/9/

17、9,34,三、古典密码,单表代换密码 单表代换密码是字母表到自身的一个可逆映射f， f：ZqZq。 令明文m=m0m1.，则相应密文为 c=c0c1.=f(m0)f(m1).,2020/9/9,35,三、古典密码,1移位代换密码 (Shift Substitution Cipher) 加密变换：f (l)=(l+k)mod q，0 l q。 其中k为密钥， 0kq。 解密变换： f -1(l)=(l-k)mod q，0 l q。 例如：凯撒(Caeser)密码是对英文26个字母进行移位代换的密码，其q=26。,2020/9/9,36,三、古典密码,选择密钥k=3，则有下述代换表： abcdef

18、g hijklmn opqrst uvwxyz DEFGHIJ KLMNOPQ RSTUVW XYZABC 明文：m =Casear cipher is a shift substitution 密文：c=FDVHDU FLSKHU LV D VKLIW VXEVWLWXWLRQ,2020/9/9,37,三、古典密码,2. 乘数密码(Multiplicative Cipher)： 加密变换：f (l)=lk mod q ，0lq。 其中k为密钥，0kq。显然，仅当(k, q)=1（即k与q互素）时， f (l)才是可逆变换。 解密变换： f -1(l)=lk-1mod q，0 l q。,202

19、0/9/9,38,三、古典密码,我们知道，共有(q)个k满足： 0kq， (k, q)=1。这就是说，乘数密码共有(q)个不同的密钥。 对于q=26， (26)=(213)=(2)(13)=12， 即共有12个不同的密钥k=1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23和25。 此时对应的k-1mod q=1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17和25。,2020/9/9,39,三、古典密码,3. 仿射密码(Affine cipher) 加密变换： f (l)=lk1+k0 mod q，0lq。 其中k1, k2Zq，(k1 , q

20、)=1，以k1 , k0表示密钥。当k0=0时就得到乘数密码，当k11时就得到移位密码。 q=26时可能的密钥数为26(26)2612312个。,2020/9/9,40,三、古典密码,4. 多项式代换密码(Polynomial Substitute Cipher) 加密方程为： f (l)=ktl tkt-1l t-1k1l +k0 mod q。 其中，kt, ., k0Zq，lZq。 前三种密码都可看作是它的特例。,2020/9/9,41,三、古典密码,5. 密钥短语密码 选一个英文短语，称其为密钥字(Key Word)或密钥短语(Key Phrase)，如HAPPY NEW YEAR，去掉

21、重复字母得HAPYNEWR。将它依次写在明文字母表之下，而后再将字母表中未在短语中出现过的字母依次写于此短语之后，就可构造出一个字母代换表，如下所示：,2020/9/9,42,三、古典密码,A：abcdefg hijklmn opqrst uvwxyz A：HAPYNEWRBCDFGIJKLMOQSTUVKZ 这是一种易于记忆而又有多种可能选择的密码。用不同的密钥字就可得到不同的代换表。q=26时将可能有26!41026种。其中绝大多数代换都是好的。是一种灵活变化密钥的代换密码。,2020/9/9,43,三、古典密码,用现代密码学的眼光观察单表代换密码 设单表代换密码用于多次一密的加解密方式，

22、以下对其进行已知明文攻击。Eve截获了一段密文，并获得了该段密文所对应的明文。 一、只要密文中含有q个不同的字母（因此对应的明文中也含有q个不同的字母），则加密变换f被确定。,2020/9/9,44,三、古典密码,二、对于移位代换密码 ，只要密文中含有1个字母（对应的明文中也含有1个字母），则密钥k被确定。 三、对于乘数密码 ，只要密文中含有1个字母（对应的明文中也含有1个字母），则密钥k被确定。 四、对于仿射密码 ，只要密文中含有2个不同的字母（对应的明文中也含有2个不同的字母），则密钥k1 , k0被确定。,2020/9/9,45,三、古典密码,五、对于多项式代换密码 ，只要密文中含有mi

23、nt+1, q个不同的字母（对应明文中也含有mint+1, q个不同的字母），则密钥kt, ., k0被确定。 综上所述，只要密文中含有至多q个不同的字母，单表代换密码体制就被攻破了。,2020/9/9,46,三、古典密码,多表代换密码 多表代换密码是字母表Zq=0, 1, , q-1到自身的d个可逆映射f0，f1，. ，fd-1，在加密时循环排列使用。 令明文m=m0m1.，则相应密文为 c=c0c1.=f0(m0)f1(m1).fd-1(md-1)f0(md) f1(md+1).,2020/9/9,47,三、古典密码,1. 维吉尼亚密码 可逆映射f0，f1，. ，fd-1都是移位代换密码，

24、分别使用密钥(k0, k1, , kd-1 )。令明文m=m0m1.，则相应密文为 c=c0c1.=(m0+k0modq)(m1+k1modq). (md-1+kd-1modq) (md+k0modq)(md+1+k1modq).,2020/9/9,48,三、古典密码,对维吉尼亚密码的讨论 设维吉尼亚密码用于多次一密的加解密方式，对其进行已知明文攻击。Eve截获了一段密文，并获得了该段密文所对应的明文。只要密文长度不小于d，密钥(k0, k1, , kd-1 )就被确定。 若d充分大，大到不可能截获长度为d的密文（存储量和时间限制），甚至可以设d “接近无穷大”。此时当然可以抵抗已知明文攻击。

25、,2020/9/9,49,三、古典密码,（注解：当d “接近无穷大” 时，维吉尼亚密码变成了现代密码中的一种，我们称之为流密码或序列密码。） 但问题是，通信伙伴之间怎样简单快速地协商极长的密钥序列(k0, k1, , kd-1 )？ 当然不能逐字母地协商密钥。因为，如果攻击者截获长度为d的密文是不可能的（存储量和时间限制） ，则通信伙伴协商出长度为d的密钥也是不可能的。,2020/9/9,50,三、古典密码,一种办法是： 取(k0, k1, , kd-1 )为一本书，此时通信伙伴只需要相互告知该书的书名和版本号，因此使得密钥协商简单快速。 这种办法很容易进行局部破译。 设Eve截获了一段长度为

26、l的密文，并获得了该段密文所对应的明文。 Eve因此也获得了密钥中长度为l的一段(k0, k1, , kl-1 )。 l与d相比当然是微不足道的。,2020/9/9,51,三、古典密码,如果该段是名书名句，则Eve只需要找到该名书。 如果该段并不著名，也可以根据文字推断书名及书目类别，并到书店寻找该书。 也可以根据文字的特征，由上下文含义来推测后续密钥。比如(k0, k1, , kl-1 )=information securit，则kl=y ； (k0, k1, , kl-1 )=计算机病，则kl=毒；等等。,2020/9/9,52,三、古典密码,另一种办法是： 取(k0, k1, , kd

27、-1 )为某个周期序列的一个周期，周期d极大，而用一个长度大约为ln(d)的“密钥种子”，采用公开算法来递归生成这个周期序列。 此时通信伙伴只需要相互告知“密钥种子”的值。 这是现代流密码的一般构造，存在着大量有待解决的工程实践问题、学术理论问题。,2020/9/9,53,三、古典密码,2. 多字母代换密码 多字母代换密码是字母L维向量空间到自身的一个可逆映射f：ZqLZqL；即 f(m0m1.mL-1)=c0c1.cL-1。 令明文m=m0m1.，则相应密文为 c=c0c1. =f(m0m1.mL-1)f(mLmL+1.m2L-1).,2020/9/9,54,三、古典密码,对多字母代换密码的

28、讨论 我们知道，字母L维向量空间ZqL一共有qL个向量。换句话说，多字母代换密码f 实际上是一个单表代换密码，只不过“字母表”是ZqL，有qL个“字母”。这里的一个“字母”就是ZqL中的一个L维向量。 如果f 设计得好，则需要qL个“密文字母”和其对应的“明文字母”才能确定f 。（取q=2，L=128，则qL=2128是一个极庞大的数字。）,2020/9/9,55,三、古典密码,因此，设计得好的多字母代换密码f 能够极大地扩大已知明文攻击所需要的明文/密文的长度。 但问题是，多字母代换密码f 怎样做到设计得好并且简单快速？（达到设计要求的密码是一种现代密码，称之为分组密码。） 显然不能使用真实的代换表，因为一个代换表需要q