现代密码学(第一章)

第一章：密码学基础一、信息安全的基本概念二、密码体制的分类三、古典密码四、密码分析2023/2/21一、信息安全的基本概念信息的载体信息的存放地点称为媒质。通信伙伴之间有一条传送信息的通道，称为信道。媒质和信道统称为信息的载体。通常：媒质是开放的，共享的，因而是不安全的；信道也是不安全的公共信道。2023/2/22一、信息安全的基本概念对信息的载体存在两种攻击：（1）被动攻击。攻击者通过各种办法（如搭线窃听，电磁窃听，声音窃听，非法访问等）来非法截收信息。（2）主动攻击。攻击者对载体中的信息进行非法篡改（如删除、增添、重放、伪造等）。2023/2/23一、信息安全的基本概念（为了有效地保护信息，抵抗被动攻击和主动攻击，必须使用密码技术。认识一下名词）密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，密码编码学(Cryptography)，对信息进行编码以保护信息的一门学问。密码分析学(Cryptanalysis)，研究分析破译密码的学问。2023/2/24一、信息安全的基本概念密码技术分为两个部分，第一部分是信息保密，第二部分是信息认证。信息保密用来抵抗被动攻击。信息认证用来抵抗主动攻击。2023/2/25一、信息安全的基本概念信息保密的功能：信息的加密和解密。（使得除通信伙伴以外的其他人无法获取信息。）信息认证的功能：对信息的认证，对发送信息者的身份的认证，对接收信息者的身份的认证。（使得对信息的篡改会被立即发现。）2023/2/26一、信息安全的基本概念信息保密系统信息保密系统又称为加密系统。该系统被描述如下。用户Alice和用户Bob是一对通信伙伴。Eve是攻击者（违法入侵者）。2023/2/27一、信息安全的基本概念Alice欲发送一个消息m给Bob。m称为明文。Alice使用加密密钥z，使用加密算法E，对明文m做以下的变换，称为加密变换：c=E(m,z)c称为密文。Alice将密文c通过不安全的公共信道发送给Bob。Bob使用解密密钥k，使用解密算法D，对密文c做以下的反变换，称为解密变换：m=D(c,k)于是Bob获得了明文m。2023/2/28一、信息安全的基本概念参数与计算的小结明文m，密文c；加密算法E，解密算法D；加密密钥z，解密密钥k；加密变换c=E(m,z)，将明文m变为密文c；解密变换m=D(c,k)，将密文c变为明文m。2023/2/29一、信息安全的基本概念攻击者Eve所拥有的基本资源Eve在不安全的公共信道上截获了密文c。Eve知道加密算法E和解密算法D。攻击者Eve可能拥有的更多资源Eve可能知道密文c所对应的明文m。（此时所进行的攻击称为已知明文攻击）Eve可能拥有强大的计算能力。Eve可能缴获了一台加密机（也称为加密黑盒子），可以任意地输入明文，输出密文。（此时所进行的攻击称为选择明文攻击）2023/2/210一、信息安全的基本概念攻击者Eve不可能拥有的资源Eve不知道加密密钥z和解密密钥k。（事实上，在进行安全性分析时，有时也假设Eve知道了密钥的一部分，但决不能全部知道）攻击者Eve的目的此时Eve是被动攻击者，他的目的是试图获取明文的信息。2023/2/211一、信息安全的基本概念攻击者Eve攻击成功的标志Eve的思路是“不拘一格”。只要Eve以某种方式获取了明文的一定量的信息，就可以算作一种攻击成功。但“攻击成功”的程度有高低之分。比如：能够持续不断地直接获取明文是最高的攻击成功；掌握在未来获取明文的技巧则是低一级的攻击成功；获得明文的某些统计特性是更低一级的攻击成功。2023/2/212一、信息安全的基本概念注解一：关于加密算法E和解密算法D从商用的角度出发，要求加解密算法（E，D）应该是公共的标准算法，是公开的。因此，包括攻击者Eve在内的所有人都知道加解密算法（E，D）。要求安全性不依赖于加解密算法（E，D）是否保密，而仅仅依赖于密钥是否保密。2023/2/213一、信息安全的基本概念注解二：关于已知明文攻击如果每一次加密/解密过程，都要选择一次加解密密钥（z，k），则加解密方式称为一次一密的。一次一密的加解密方式通常具有很好的安全性。但是需要频繁地更换密钥，每次通信之前都需要通信伙伴之间进行协商来确定新的密钥（z，k）。因而一次一密的加解密方式是不实用的。2023/2/214一、信息安全的基本概念如果加解密密钥（z，k）在多次加密/解密过程中反复地重复使用，则加解密方式称为多次一密的。现有的实用加解密方式都是多次一密的。多次一密的加解密方式极大地省却了通信伙伴的工作量。但同时，多次一密的加解密方式使得攻击者增加了几种新的攻击手段。其中包括：已知明文攻击。2023/2/215一、信息安全的基本概念设攻击者Eve截获了密文c，并且知道了密文c所对应的明文m。（这种情况是怎样发生的呢？当明文m是已经过期的消息，可能无法再保密，也可能必须将其公开。因此，这种情况是经常发生的）于是：在解密方程m=D(c,k)中，Eve知道m和c，仅仅不知道解密密钥k。在加密方程c=E(m,z)中，Eve知道m和c，仅仅不知道加密密钥z。2023/2/216一、信息安全的基本概念如果Eve从解密方程m=D(c,k)中计算出解密密钥k，则Eve今后就可以像Bob一样对任何密文c’进行解密：m’=D(c’,k)。如果Eve从加密方程c=E(m,z)中计算出加密密钥z，则Eve今后就可以像Alice一样对任何明文m’进行加密：c’=E(m’,z)。2023/2/217一、信息安全的基本概念还可以给更加宽松的条件。设攻击者Eve获得了以往废弃的n组明文/密文对：（m1，c1），（m2，c2），…，（mn，cn）。于是Eve获得了关于解密密钥k的方程组：m1=D(c1,k)，m2=D(c2,k)，…，mn=D(cn,k)。（n越大，解密密钥k就越容易确定。）2023/2/218一、信息安全的基本概念以上就是已知明文攻击。要抵抗已知明文攻击，必须精心地设计加解密算法（E，D）。（能抵抗已知明文攻击的加解密算法(E,D)并不是很容易构造的。）例1设：加密密钥等于解密密钥：z=k；加密算法为c=m+z；对应的解密算法为m=c-k=c-z。（普通加减法）注意到此时k=c-m。这就是说，只要知道了一组明文/密文对（m，c），就能计算出解密密钥k。2023/2/219一、信息安全的基本概念例2设：加密密钥等于解密密钥，z=(z1,z2)；加密算法为c=z1m+z2

；对应的解密算法为m=(c-z2)/z1。（普通加减乘除法）设攻击者Eve获得了以往废弃的2组明文/密文对：（m1，c1），（m2，c2）。注意到此时c1=z1m1+z2

；

c2=z1m2+z2

。这是一个关于密钥(z1,z2)的二元一次方程组，能计算出(z1,z2)

。2023/2/220一、信息安全的基本概念可以看出，以上两个例子所用的加解密算法都不能抵抗已知明文攻击，因此不能用作多次一密的加解密方式。2023/2/221一、信息安全的基本概念注解三：已知明文攻击的一些弱化形式设攻击者Eve知道了以往的一个密文c以及c所对应的明文m。Eve又截获了一个新的密文c’，Eve试图猜测出c’所对应的明文m’。如果加解密算法设计得“不好”，则密钥对明文的覆盖就可能出现漏洞。此时由{m,c,c’}猜测出c’所对应的明文m’就会变得容易得多。可能出现以下的现象：2023/2/222一、信息安全的基本概念（1）当c’与c的“距离很近”时，m’与m也“距离很近”，而无论密钥是什么值。（2）当c’与c具有某种固定的关系A时，m’与m具有某种固定的关系B，而无论密钥是什么值。（3）当c’与c具有某种固定的关系A时，m’与m“以很大的概率”

具有某种固定的关系B，而无论密钥是什么值。（4）当密钥的可能变化范围（密钥量）太小时，攻击者Eve可以穷举搜索密钥。2023/2/223一、信息安全的基本概念（简单介绍）为了抵抗诸如此类的攻击，以便适用于多次一密，加解密算法应该满足：（1）具有良好的“混淆性”（confusion）和“扩散性”（diffusion）；（2）具有良好的“非线性性”（non-linearity）；（3）具有良好的“差分均匀性”（differencebalance）。（4）密钥的可能变化范围（密钥量）应该大到不可能穷举搜索密钥（bruteforcesearch）。2023/2/224一、信息安全的基本概念2023/2/225二、密码体制的分类密码体制加解密算法的专业术语为”密码体制”。从原理上，密码体制可以分为两大类：（1）单钥密码体制。（又称为对称密码体制）（2）双钥密码体制。（又称为非对称密码体制，也称为公钥密码体制）2023/2/226二、密码体制的分类单钥密码体制单钥密码体制的加密密钥z和解密密钥k能够简单地相互推导出来。换句话说：Alice知道加密密钥z，她当然也就知道解密密钥k；Bob知道解密密钥k，他当然也就知道加密密钥z

。再换句话说，Alice和Bob的地位是对称的，可以双向地发送和接收保密信息。

（其实在一般实用情形之下，总有z=k

）2023/2/227二、密码体制的分类双钥密码体制（公钥密码体制）在双钥密码体制中，要从加密密钥z推导出解密密钥k是很困难的。（虽然，也许加密密钥z唯一地确定了解密密钥k

）具体地说：Bob拥有加密密钥z和解密密钥k。加密密钥z称为Bob的公钥，解密密钥k称为Bob的私钥。Bob的公钥z向大家公布。（像电话号码一样）Bob的私钥k被Bob私藏。2023/2/228二、密码体制的分类因此，大家都知道Bob的公钥z，而只有Bob自己知道他的私钥k。因此，大家都能够用Bob的公钥z将明文消息加密变为密文，并把密文向Bob发送，而只有Bob自己能够解密这些密文。因此，公钥密码体制除了具有信息保密的功能以外，还具有了一种信息认证功能：Alice用Bob的公钥z加密一个消息，谁能把消息正确解密，Alice就认为谁是真正的Bob。2023/2/229二、密码体制的分类公钥密码体制的原理：数学难题例如：大数分解问题；离散对数问题；背包问题；多项式的分解问题；格的最小向量问题；等等。2023/2/230二、密码体制的分类单钥密码体制与双钥密码体制的比较单钥密码体制双钥密码体制一对密钥可供一对通信伙伴双向使用。一对密钥可供多用户向一用户单向使用。无消息认证功能。有消息认证功能。n个用户之间的保密通信，一共需要n(n-1)/2对密钥。n个用户之间的保密通信，一共需要n对密钥。加解密算法简洁快速。加解密算法相对较慢。通信伙伴之间需要协商密钥。通信伙伴之间不用协商密钥。2023/2/231三、古典密码古典密码是密码学的渊源，这些密码大都比较简单，现在已很少采用了。然而，研究这些密码的原理，对于理解、构造和分析现代密码都是十分有益的。2023/2/232三、古典密码明文字母表和密文字母表相同，为：Zq={0,1,

…,q-1}。明文是长为L的字母串，以m表示：m=(m0m1,…,mL-1)，其中每个mlZq，l=0，1，…，L-1。密文是长为L的字母串，以c表示：c=(c0,c1,...,cL-1)，其中每个clZq，l=0，1，…，L-1。2023/2/233三、古典密码单表代换密码单表代换密码是字母表到自身的一个可逆映射f，f：ZqZq。令明文m=m0m1...，则相应密文为c=c0c1...=f(m0)f(m1)...2023/2/234三、古典密码1．移位代换密码(ShiftSubstitutionCipher)加密变换：f

(l)=(l+k)modq，0

l<q。其中k为密钥，0k<q。解密变换：f

-1(l)=(l-k)modq，0

l<q。例如：凯撒(Caeser)密码是对英文26个字母进行移位代换的密码，其q=26。2023/2/235三、古典密码选择密钥k=3，则有下述代换表：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC明文：m=Casearcipherisashiftsubstitution密文：c=FDVHDUFLSKHULVDVKLIWVXEVWLWXWLRQ2023/2/236三、古典密码2.乘数密码(MultiplicativeCipher)：加密变换：f

(l)=lkmodq

，0l<q。其中k为密钥，0k<q。显然，仅当(k,q)=1（即k与q互素）时，f

(l)才是可逆变换。解密变换：f

-1(l)=lk-1modq，0

l<q。2023/2/237三、古典密码我们知道，共有(q)个k满足：0k<q，(k,q)=1。这就是说，乘数密码共有(q)个不同的密钥。对于q=26，(26)=(2×13)=(2)×(13)=12，即共有12个不同的密钥k=1,3,5,7,9,11,15,17,19,21,23和25。此时对应的k-1modq=1,9,21,15,3,19,7,23,11,5,17和25。2023/2/238三、古典密码3.仿射密码(Affinecipher)加密变换：f

(l)=lk1+k0modq，0l<q。其中k1,k2Zq，(k1,q)=1，以[k1,k0]表示密钥。当k0=0时就得到乘数密码，当k1＝1时就得到移位密码。q=26时可能的密钥数为26×(26)＝26×12＝312个。

2023/2/239三、古典密码4.多项式代换密码(PolynomialSubstituteCipher)加密方程为：f

(l)=ktlt＋kt-1lt-1＋…＋k1l+k0modq。其中，kt,...,k0Zq，lZq。前三种密码都可看作是它的特例。2023/2/240三、古典密码5.密钥短语密码选一个英文短语，称其为密钥字(KeyWord)或密钥短语(KeyPhrase)，如HAPPYNEWYEAR，去掉重复字母得HAPYNEWR。将它依次写在明文字母表之下，而后再将字母表中未在短语中出现过的字母依次写于此短语之后，就可构造出一个字母代换表，如下所示：

2023/2/241三、古典密码A：abcdefghijklmnopqrstuvwxyzA’：HAPYNEWRBCDFGIJKLMOQSTUVKZ这是一种易于记忆而又有多种可能选择的密码。用不同的密钥字就可得到不同的代换表。q=26时将可能有26!≈4×1026种。其中绝大多数代换都是好的。是一种灵活变化密钥的代换密码。2023/2/242三、古典密码用现代密码学的眼光观察单表代换密码设单表代换密码用于多次一密的加解密方式，以下对其进行已知明文攻击。Eve截获了一段密文，并获得了该段密文所对应的明文。一、只要密文中含有q个不同的字母（因此对应的明文中也含有q个不同的字母），则加密变换f被确定。2023/2/243三、古典密码二、对于移位代换密码，只要密文中含有1个字母（对应的明文中也含有1个字母），则密钥k被确定。三、对于乘数密码，只要密文中含有1个字母（对应的明文中也含有1个字母），则密钥k被确定。四、对于仿射密码，只要密文中含有2个不同的字母（对应的明文中也含有2个不同的字母），则密钥[k1,k0]被确定。2023/2/244三、古典密码五、对于多项式代换密码，只要密文中含有min{t+1,q}个不同的字母（对应明文中也含有min{t+1,q}个不同的字母），则密钥[kt,...,k0]被确定。综上所述，只要密文中含有至多q个不同的字母，单表代换密码体制就被攻破了。2023/2/245三、古典密码多表代换密码多表代换密码是字母表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)...2023/2/246三、古典密码1.维吉尼亚密码可逆映射f0，f1，...，fd-1都是移位代换密码，分别使用密钥(k0,k1,…,kd-1)。令明文m=m0m1...，则相应密文为c=c0c1...=(m0+k0modq)(m1+k1modq)...(md-1+kd-1modq)(md+k0modq)(md+1+k1modq)...2023/2/247三、古典密码对维吉尼亚密码的讨论设维吉尼亚密码用于多次一密的加解密方式，对其进行已知明文攻击。Eve截获了一段密文，并获得了该段密文所对应的明文。只要密文长度不小于d，密钥(k0,k1,…,kd-1)就被确定。若d充分大，大到不可能截获长度为d的密文（存储量和时间限制），甚至可以设d“接近无穷大”。此时当然可以抵抗已知明文攻击。2023/2/248三、古典密码（注解：当d“接近无穷大”时，维吉尼亚密码变成了现代密码中的一种，我们称之为流密码或序列密码。）但问题是，通信伙伴之间怎样简单快速地协商极长的密钥序列(k0,k1,…,kd-1)？当然不能逐字母地协商密钥。因为，如果攻击者截获长度为d的密文是不可能的（存储量和时间限制），则通信伙伴协商出长度为d的密钥也是不可能的。2023/2/249三、古典密码一种办法是：取(k0,k1,…,kd-1)为一本书，此时通信伙伴只需要相互告知该书的书名和版本号，因此使得密钥协商简单快速。这种办法很容易进行局部破译。设Eve截获了一段长度为l的密文，并获得了该段密文所对应的明文。Eve因此也获得了密钥中长度为l的一段(k0,k1,…,kl-1)。l与d相比当然是微不足道的。2023/2/250三、古典密码如果该段是名书名句，则Eve只需要找到该名书。如果该段并不著名，也可以根据文字推断书名及书目类别，并到书店寻找该书。也可以根据文字的特征，由上下文含义来推测后续密钥。比如(k0,k1,…,kl-1)=informationsecurit，则kl=y

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

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