密码与隐藏技术.ppt

《密码与隐藏技术.ppt》由会员分享，可在线阅读，更多相关《密码与隐藏技术.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第2 2章章 密码与隐藏技术密码与隐藏技术 -1-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 第第2 2章章 密码与隐藏技术密码与隐藏技术 2.1 2.1 密码技术概述密码技术概述2.2 2.2 古典加密方法古典加密方法2.3 2.3 数据加密标准数据加密标准DESDES2.4 2.4 高级加密标准高级加密标准AESAES2.5 2.5 公开密钥体制公开密钥体制2.6 RSA2.6 RSA算法算法2.7 NTRU2.7 NTRU公开密钥体制公开密钥体制2.8 2.8 对称加密体制与公开密钥体制比较对称加密体制与公开密钥体制比较2.9 2.9

2、信息隐藏技术信息隐藏技术2.10 2.10 数字水印数字水印1第第2 2章章 密码与隐藏技术密码与隐藏技术 -2-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.1 密码技术概述密码技术概述密码技术是防止信息泄露的技术，是信息安全技术中最重要和最基本的安全技术。密码技术中常用的一些术语：1明文P（Plaintext）：可以理解的信息原文。2.加密E（Encryption）：用某种方法伪装明文以隐藏它的内容的过程。3密文C（Ciphertext）：经过加密后将明文变换成不容易理解的信息。4解密D（Decryption）：将密文恢复成明文的过程。2

3、第第2 2章章 密码与隐藏技术密码与隐藏技术 -3-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 5算法（algorithm）：就是用于加密或解密的方法，在现代密码学中算法就是一个用于加密和解密的数学函数。6密钥K（key）：是用来控制加密和解密算法的实现。典型的加密和解密过程可以用图2.1来描述。如果将加密过程看成是一个数学函数F的话，则密文C可以表示为：C=F（P，K）3第第2 2章章 密码与隐藏技术密码与隐藏技术 -4-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 这个函数具有两个自变量P和K

4、，在函数F的作用下得到密文。在已知密钥K1、K2、加密算法E和解密算法D时，则加密和解密过程可以表示如下：EK1（P）=CDK2（C）=P显然为使明文加密后能被解密必须有：P=DK2（EK1（P）=P在实际加密和解密时，根据加密算法的特点，K1与K2的值可以不同，也可以相同。4第第2 2章章 密码与隐藏技术密码与隐藏技术 -5-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 例：设明文是一串二进制序列，加密和解密算法都采用模2运算，即异或运算，加密密钥和解密密钥也相同。若明文P=11001100加密和解密密钥K=11000111则加密后的密文C=P

5、K=00001011解密后的密文P=CK=11001100如字符串“HYIT”的ASCII码为48594954H，密钥用05H，密文为4D5C4C51H，对应的ASCII码为“MLQ”5第第2 2章章 密码与隐藏技术密码与隐藏技术 -6-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 现代密码学已发展成两个重要的研究分支：（1）对称加密方法，其典型代表是数据加密标准DES（数据加密标准）、IDEA（国际数据加密算法）、AES（高级加密标准）等算法。（2）公开密钥算法(也称非对称算法)，其典型代表是RSA、椭圆曲线加密、NTRU算法等。6第第2 2章

6、章 密码与隐藏技术密码与隐藏技术 -7-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.2 古典加密方法古典加密方法2.2.1 代替密码代替密码代替密码又称替换密码，就是按照一定要求，将明文中的每个字符替换成另一个字符，明文中字符的位置保持不变，但其本身改变了。分为单表代换和多表代换。（1）单表代换：同一个字符具有一个密文字符。（2）多表代换：同一个字符具有不同的密文字符。如：移位密码：C=P+K(mod26),M=C-K(mod26)仿射变换：C=aP+b(mod26),M=a-1(C-b)(mod26)，a与26互素7第第2 2章章 密码与

7、隐藏技术密码与隐藏技术 -8-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 多表代换：密钥由多个字母组成，依次用来对明文进行加密。2.2.2 换位密码换位密码换位密码也可称为置换密码，它是改变明文中字母的位置，明文中的字母不变。也就是明文中的字母保持不变，但顺序被打乱了。例如可以将明文the变换成het。8第第2 2章章 密码与隐藏技术密码与隐藏技术 -9-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.3 对称加密体制对称加密体制对称加密算法，有时又叫传统密码算法，它的典型特点是：1采用的解密算

8、法就是加密算法的逆运算，或者解密算法与加密算法完全相同；2加密密钥和解密密钥相同，或者加密密钥能够从解密密钥中推算出来，反过来也成立。对称算法要求发送者和接收者在安全通信之前，商定一个密钥。它的安全性依赖于密钥的保密性。9第第2 2章章 密码与隐藏技术密码与隐藏技术 -10-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 对称算法可分为两类：分组密码和序列密码或流密码。1分组密码是将明文分成固定长度的组或块（如64比特为一组），然后用同一密钥和算法对每一块进行加密，输出密文的长度也是固定的，如图2.3所示。教材P192序列密码（streamciph

9、er）的主要原理是通过伪随机序列发生器产生性能优良的随机序列，使用该序列与明文序列叠加来输出密文序列。解密时，再用同一个随机序列与密文序列进行叠加来恢复明文，如图2.4所示。教材P1910第第2 2章章 密码与隐藏技术密码与隐藏技术 -11-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.3.1 DES算法算法DES（数据加密标准，DataEncryptionAlgorithm）算法：IBM提出，美国标准，世界首例标准。DES是分组加密算法，它以64位（二进制）为一组，对称数据加密，64位明文输入，64位密文输出。密钥长度为56位，但密钥通常表

10、示为64位，并分为8组，每组第8位作为奇偶校验位，以确保密钥的正确性，这样对用户来说每组密钥仍是56位。利用密钥，通过传统的换位、替换和异或等变换，实现二进制明文的加密与解密。11第第2 2章章 密码与隐藏技术密码与隐藏技术 -12-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 DES算法概要：1对输入的明文从右向左按顺序每64位分为一组（不足64位时，在高位补0），并按组进行加密或解密。2进行初始换位。3将换位后的明文分成左、右两个部分，每部分为32位长。4进行16轮相同的变换，包括密钥变换。5将变换后左右两部分合并在一起。6逆初始变换，输出6

11、4位密文。12第第2 2章章 密码与隐藏技术密码与隐藏技术 -13-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 p=p1p2p64p=p58p50p7c=c1c2c64c=c40c8c2513第第2 2章章 密码与隐藏技术密码与隐藏技术 -14-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 加加密密变变换换：将明文p初始置换后得到p分为两部分（L0,R0），首轮变换后得到新的64位数据，还分为左右两部分（L1,R1），再用（L1,R1）进行同样变换，从而先后得到（L2,R2）（L16,R16）。（

12、L16,R16）即为c。一轮变换过程图示：一轮变换过程图示：14第第2 2章章 密码与隐藏技术密码与隐藏技术 -15-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 15第第2 2章章 密码与隐藏技术密码与隐藏技术 -16-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 置换相当于重新排队置换相当于重新排队队列：123626364p1p2p3p64p62p63p58p50p42p23p15p716第第2 2章章 密码与隐藏技术密码与隐藏技术 -17-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算

13、机工程学院计算机工程学院计算机工程学院 17第第2 2章章 密码与隐藏技术密码与隐藏技术 -18-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 18第第2 2章章 密码与隐藏技术密码与隐藏技术 -19-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 19第第2 2章章 密码与隐藏技术密码与隐藏技术 -20-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 20第第2 2章章 密码与隐藏技术密码与隐藏技术 -21-为中华之崛起而读书为中华之崛起而读书计算机工程

14、学院计算机工程学院计算机工程学院计算机工程学院 对应S盒的（3，5）元素为9，将9转换为二进制数1001。所以，当S盒的输入为101011时，S盒的输出为1001。S盒代替是DES算法的核心部分，整个变换过程是非线性的（而DES算法的其他变换都是线性的），提供很好的混乱数据效果，比DES算法的其他步骤都提供了更好的安全性。9.P盒置换：将S盒输出的32位二进制数据按P盒置换表2.7进行置换。21第第2 2章章 密码与隐藏技术密码与隐藏技术 -22-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 22第第2 2章章 密码与隐藏技术密码与隐藏技术 -2

15、3-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 可利用课后时间，编程实现DES算法23第第2 2章章 密码与隐藏技术密码与隐藏技术 -24-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 DES算法的安全性：算法的安全性：（1）安全性比较高，目前只有一种方法可以破解该算法,那就是穷举法。（2）采用64位密钥技术,实际只有56位有效，8位用来校验的。一台PC机器,它能每秒计算一百万次（约220），那么它要穷举的时间为2285年，所以这种算法还是比较安全的一种算法。但破译但破译DES不是不可能不是不可能

16、:(1)1997年DESCHALL小组经过4个月，通过Internet搜索了31016个密钥，找出了DES密钥，恢复了明文。（2）1998年美国EFF（electronics frontier foundation)宣布，他们用一台20万美元的计算机改装的专用解密机，花56小时破译了56位密钥的DES。2000年有了高级加密标准年有了高级加密标准AES-Rijndael算法。算法。24第第2 2章章 密码与隐藏技术密码与隐藏技术 -25-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.4 高级加密标准高级加密标准AESRijndael算法也是一

17、种分组密码体制，其明文分组长度、密钥长度可以是128比特、192比特、256比特中的任意一个。按照密钥长度，分别记为AES-128，AES-192，AES-256。AES比DES支持更长的密钥，AES-128密钥个数比DES的56位密钥个数要多1021倍，对AES的攻击仍然是穷举密钥攻击。如果用一台每秒钟能够找出255个DES密钥的机器，用它来找AES-128的密钥，大约需要149万年。25第第2 2章章 密码与隐藏技术密码与隐藏技术 -26-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.4 高级加密标准高级加密标准AES26第第2 2章章

18、密码与隐藏技术密码与隐藏技术 -27-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 即即57 83=D427第第2 2章章 密码与隐藏技术密码与隐藏技术 -28-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 11B即即0001 0001 1011对应多项式对应多项式x8+x4+x3+x+1即即57 83=C1（先相乘，再相除，得到的余数先相乘，再相除，得到的余数）28第第2 2章章 密码与隐藏技术密码与隐藏技术 -29-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计

19、算机工程学院 29第第2 2章章 密码与隐藏技术密码与隐藏技术 -30-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 注意：注意：系数系数a3,a1,b3,b1 是一个字节是一个字节8位二进制位二进制数，不是一位二进制数数，不是一位二进制数1或或0把复杂的乘法运算转把复杂的乘法运算转换为移位和加法运算。换为移位和加法运算。30第第2 2章章 密码与隐藏技术密码与隐藏技术 -31-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 31第第2 2章章 密码与隐藏技术密码与隐藏技术 -32-为中华之崛起而读书

20、为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 该矩阵是一个循环矩阵，x b(x)=b2x3+b1x2+b0 x+b3，即左循环移了一位（a0=a2=a3=00,a1=01，系数为一个字节），可见x或x的幂模乘多项式，相当于对字节构成的向量进行字节循环移位。32第第2 2章章 密码与隐藏技术密码与隐藏技术 -33-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 33第第2 2章章 密码与隐藏技术密码与隐藏技术 -34-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.4.2

21、 AES算法概述算法概述 AES算法是一种可变数据块长Nb和可变密钥长Nk的迭代分组加密算法，其数据块长和密钥长度可分别为128、192和256比特。AES算法以字节（8比特）和字（32比特）为处理单位，将明文分成Nb个字，密钥分成Nk个字，每个字为4个字节32比特。Nb、Nk可分别取4、6、8，两者不一定相同。令变换轮数Nr max Nb，Nk+6，则算法共进行一个初始轮（初始化），Nr-1轮变换及最后一轮变换，即AES算法共进行Nr+1轮变换。34第第2 2章章 密码与隐藏技术密码与隐藏技术 -35-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学

22、院 当AES的输入明文分组长度为128位时，经AES加密或解密处理后，得到的输出也是128位。基基本本处处理理单单位位：在AES中，各种运算是以字节为基本单位进行处理的。在一个字节中，最右边的位是字节低位，最左边的位是字节高位。状态：状态：对明文数据块加密或解密时，要经过多次的数据变换操作，每一次变换操作都产生一个中间结果，我们将这个中间结果称为状态（state）。怎么表示状态？怎么表示状态？状态可以用二维字节数组表示，它有4行Nb列，其中数组中元素单位为字节，Nb列的单位为字。35第第2 2章章 密码与隐藏技术密码与隐藏技术 -36-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工

23、程学院计算机工程学院计算机工程学院 36第第2 2章章 密码与隐藏技术密码与隐藏技术 -37-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 状态数组：状态数组：37第第2 2章章 密码与隐藏技术密码与隐藏技术 -38-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 轮数轮数Nr的取值的取值：Nr max Nb，Nk+6教材P31表2.9，与Nb和Nk的值有关。38第第2 2章章 密码与隐藏技术密码与隐藏技术 -39-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工

24、程学院 39第第2 2章章 密码与隐藏技术密码与隐藏技术 -40-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 40第第2 2章章 密码与隐藏技术密码与隐藏技术 -41-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 41第第2 2章章 密码与隐藏技术密码与隐藏技术 -42-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 42第第2 2章章 密码与隐藏技术密码与隐藏技术 -43-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院

25、计算机工程学院 一个字节总共就256种可能，可以把字节代替变换SubBytes（）对各种可能字节的变换结果排成一个表，如表2.10所示，该表称为AES的S盒。可以通过查表直接得到Subbytes（）的输出。这样可以加快程序执行速度。如果状态中的一个字节为xy，则S盒中第x行第y列的字节就是SubBytes（）的输出。例：设有状态中的一个字节为C4H，则SubBytes（）的输出为S盒中第C行第4列的字节值为1CH。可以看出AES的S盒具有一定的代数结构，而DES中S盒是人为构造的。43第第2 2章章 密码与隐藏技术密码与隐藏技术 -44-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机

26、工程学院计算机工程学院计算机工程学院 共共4行，每行以字节为单行，每行以字节为单位循环移位位循环移位共共Nb列，每列与一个固定的多项式列，每列与一个固定的多项式a(x)进行模进行模x4+1乘法，乘法，a(x)是模是模x4+1可逆的。可逆的。44第第2 2章章 密码与隐藏技术密码与隐藏技术 -45-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 4圈密钥加法变换AddRoundKey（）圈密钥也称轮密钥，圈密钥加法变换AddRoundKey（）是将一个圈密钥按位异或到一个状态上，如图2.10所示，圈密钥的长度为Nb个字。圈密钥按顺序取自扩展密钥Exp

27、andedKey，扩展密钥是由原始密钥经过扩展后得到的，扩展密钥的长度为Nb(Nr十1)个字。例：（S0j,S1j,S2j,S3j）=（S0j,S1j,S2j,S3j）（k0j,k1j,k2j,k3j），0j3。其中（k0j,k1j,k2j,k3j）表示扩展密钥中的第rNb+j个字，0rNr。45第第2 2章章 密码与隐藏技术密码与隐藏技术 -46-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 圈密钥按列S00,S10,S20,S30,S03,S13,S23,S33顺序与状态上各元素进行异或运算。在AES加密过程中，r=0时，是第一轮变换之前的初

28、始圈密钥加法变换；r=Nr时，是输出之前的最后一轮密钥加法变换。Nb与Nk不同如何进行加法变换呢？他们以字为单位，而且是以Nb个字同时进行加法变换。Nr十1轮需要Nr十1次Nb个字的加法变换，即需要Nb(Nr十1)个字密钥。由Nk个字的密钥，如何扩展成长度为Nb(Nr十1)个字的扩展密钥呢？46第第2 2章章 密码与隐藏技术密码与隐藏技术 -47-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 5扩展密钥（密钥编排规则）AES算法利用外部输入字数为Nk的密钥串K，通过扩展密钥程序得到共Nb(Nr+l)字的扩展密钥串。对扩展密钥按每组为Nb个字分组，

29、将每组的密钥称为圈密钥(或轮密钥)。这样就可以产生Nr+1个圈密钥，每个圈密钥由Nb个字组成。每个字用wi表示，其中i=0，1，2，Nb(Nr1)-1。扩展密钥算法见教材p35-36。一一次次生生成成所所有有密钥，不像密钥，不像DES算法，在每轮变换密钥。算法，在每轮变换密钥。扩展密钥程序涉及三个RotWord（）、SubWord（）和Rcon模块。它们的工作方式如下：47第第2 2章章 密码与隐藏技术密码与隐藏技术 -48-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院（l）位置变换RotWord（）：把一个四个字节的输入序列（a0，al，a2，

30、a3）循环左移一个字节后输出。如将（a0，al，a2，a3）循环左移一个字节后输出为（al，a2，a3，a0）。（2）SubWord（）：把一个四字节的输入序列（a0，al，a2，a3）的每一个字节进行S盒变换，然后作为输出。（3）变换Rcon：Rcon是一个10个字的常常值数组值数组，Rconi是一个32比特字符串（xi-1，00，00，00）。这里x（02），xi-1是x（02）的（i-1）次幂的十六进制表示，即：48第第2 2章章 密码与隐藏技术密码与隐藏技术 -49-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 x0（01），x（02），

31、xi=02xi-1这里表示有限域GF（28）中的乘法。扩展密钥扩展前Nk个字就是外部密钥CipherKey，以后的字wi等于它前一个字wi-1与前第Nk个字wi-Nk的异或，即 wiwi-1wi-Nk但是若i=Nk的倍数，则 wiwiNkSubWord(RotWord(wi-1)Rconi/Nk49第第2 2章章 密码与隐藏技术密码与隐藏技术 -50-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 50第第2 2章章 密码与隐藏技术密码与隐藏技术 -51-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院

32、51第第2 2章章 密码与隐藏技术密码与隐藏技术 -52-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 1逆行移位变换InvShiftRows（）InvShiftRows（）是ShiftRows（）的逆变换，是对一个状态的每一行循环右移不同的位移量。第0行不移位，保持不变，第1行移动C1个字节，第2行移动C2个字节，第3行移动C3个字节。C1，C2，C3值依赖于分组长度Nb的大小，见2.11表所示。2.逆S盒变换InvSubBytes（）InvSubBytes（）是SubBytes（）的逆变换，它将状态中的每一个字节非线性地变换为另一个字节。52

33、第第2 2章章 密码与隐藏技术密码与隐藏技术 -53-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 同样，可以将逆S盒变换对各种可能结果排成一个表，如表2.12所示。表2.12称为AES的逆S盒变换表或逆字节代替表。如果状态中的一个字节为xy，则逆S盒中第x行，第y列的字节就是InvSubBytes（）的返回值。3逆列混合变换InvMixColumns（）InvMixColumns（）是MixColumns（）的逆变换。InvMixColumns（）对一个状态逐列进行变换，它将一个状态的每一列视为有限域GF（28）上的一个多项式，InvMixCo

34、lumns（）将状态的每一列所对应的GF（28）上的多项式模x4+1乘以多项式。53第第2 2章章 密码与隐藏技术密码与隐藏技术 -54-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 4圈密钥的使用AES解密时的扩展密钥程序与加密时的扩展密钥程序相同，但解密时圈密钥的使用顺序与加密过程相反。同时，除第一个和最后一个圈密钥外，其其余余圈圈密密钥钥需需要要进行逆混合列变换。进行逆混合列变换。例：如果加密时圈密钥为：k0，k1，kNr，那么，解密时密钥为：kNr，InvMixColumns（kNr-1），InvMixColumns（k2），k0。54第

35、第2 2章章 密码与隐藏技术密码与隐藏技术 -55-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.5 公开密钥体制公开密钥体制公开密钥算法的典型特点是：1在公开密钥算法中，有一对密钥（pk，sk），其中pk（public-key）是公开的，即公开密钥，简称公钥。另一个密钥sk（privatekey）是保密的，这个保密密钥称为私人密钥，简称私钥。2在公开密钥算法中，进行加密和解密时，使用不同的加密密钥和解密密钥。而且不能从加密密钥或解密密钥相互推导出来，或者很难推导出来。也就是说已知加密密钥和加密算法，求解密密钥在计算上是不可行的。55第第2

36、2章章 密码与隐藏技术密码与隐藏技术 -56-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 3在公开密钥算法中，公开密钥和私人密钥必须配对使用。也就是说如果使用公开密钥加密时，就必须使用相应的私人密钥解密；如果使用私人密钥加密时，也必须使用相应的公开密钥解密。4一般来说，公开密钥算法都是建立在严格的数学基础上，公开密钥和私人密钥的产生也是通过数学方法来产生的。公开密钥算法的安全性是依赖于某个数学问题很难解决的基础上。公公开开密密钥钥加加密密一一般般是是为为了了保保密密，私私人人密密钥钥加加密密一一般般是是为为了认证。了认证。公公开开密密钥钥算算法

37、法的的基基本本工工具具不不再再是是代代换换和和置置换换，而而是是数数学学函数。函数。56第第2 2章章 密码与隐藏技术密码与隐藏技术 -57-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 57第第2 2章章 密码与隐藏技术密码与隐藏技术 -58-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 58第第2 2章章 密码与隐藏技术密码与隐藏技术 -59-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 59第第2 2章章 密码与隐藏技术密码与隐藏技术 -60-为

38、中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 60第第2 2章章 密码与隐藏技术密码与隐藏技术 -61-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 因此，研究公钥密码算法就是要找出合适的陷门单向函数。因此，研究公钥密码算法就是要找出合适的陷门单向函数。61第第2 2章章 密码与隐藏技术密码与隐藏技术 -62-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.6 RSA算法算法RSA算法是公开密钥密码体制中最著名、使用最广泛的一种算法是公开密钥密码体制中

39、最著名、使用最广泛的一种。2.6.1 RSA算法数学基础算法数学基础定义1：对一个自然数P，如果P只能被1和自身除尽时，则称P为素数（或质数），否则为合数。定义2：如果整数a与整数b的最大公约数是1，则称a与b是互为质数。例如：2和3，7和11等都是互为质数。定义3：欧拉函数定义为：设设r是一正整数，小于是一正整数，小于r且与且与r互素的正整数互素的正整数的个数称为的个数称为r的欧拉函数。的欧拉函数。(r)=r（11/P1）（11/P2）（11/Pn）P1、P2Pn是r的质因子，即公约数。若r是素数，则(r)=r-1。若r是两个素数p和q的乘积，则(r)=(p)(q)=(p-1)(q-1)若r

40、和a互素，则a(r)=1modr62第第2 2章章 密码与隐藏技术密码与隐藏技术 -63-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 欧拉函数是用来计算1、2、3、r中有多少个数与r互为质数的。例如：当r=20时，由于r=225，即20的公约数是2和5所以：=20（1-1/2）（1-1/5）=8即在120个整数中有8个与20互质的数，它们是1，3，7，9，11，13，17，19。定义4：两个整数a、b分别被m除，如果所得余数相同，则称a与b对模m是同余的，记作：ab（modm）63第第2 2章章 密码与隐藏技术密码与隐藏技术 -64-为中华之崛

41、起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.6.2 RSA算法基础算法基础1产生素数产生素数的方法很多，这里介绍的方法是：（1）凡素数n必不能被2（实际上一个数的最大公约数小于或等于）之间的所有素数整除。（2）除2以外所有素数为奇数，由素数的定义决定算法。判断1N个数中的n是否为素数时具体算法是：（1）令n从3开始（3是素数）；（2）每次增加2，n=n+2（排除了偶数）；64第第2 2章章 密码与隐藏技术密码与隐藏技术 -65-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院（3）n被所有小于等于的素数整除

42、（4）若不存在被整除的数，则n为素数2求最大公约数算法设b、c为整数，b0，c0，bc（使用这个条件不影响算法，但可避免符号问题），b、c的最大公约数记为gcd（b，c）。我们可以利用欧几里德算法，即重复使用带余数除法求最大公约数。欧几里德算法：每次的余数为除数，除上一次的除数，直到余数为为0时时为止，则上次余数为最大公约数。65第第2 2章章 密码与隐藏技术密码与隐藏技术 -66-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 可以先设b为上次的除数，c为余数，按欧几里德算法求出gcd（b、c）3求乘逆算法设已知a，求b，称求a对于模r的乘逆b，

43、并称a与b对r互为乘逆。也可以写成:b=a-1modr乘法逆元不是倒数。乘法逆元不是倒数。求乘逆时也可以利用欧几里德算法，即重复使用带余数除法。但与求最大公约数不同，即每次的余数为除数，除上次除数，直到余数为为1时时为止。如果gcd(r,a)=1，则a在modr下必有乘法逆元b。并非每个数都有乘法逆元。66第第2 2章章 密码与隐藏技术密码与隐藏技术 -67-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 a=3:r=14,b=5；r=17,b=6；r=15,不存在b67第第2 2章章 密码与隐藏技术密码与隐藏技术 -68-为中华之崛起而读书为中华

44、之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 68第第2 2章章 密码与隐藏技术密码与隐藏技术 -69-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 sk和pk互为乘逆。69第第2 2章章 密码与隐藏技术密码与隐藏技术 -70-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 70第第2 2章章 密码与隐藏技术密码与隐藏技术 -71-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 71第第2 2章章 密码与隐藏技术密码与隐藏技术 -7

45、2-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 72第第2 2章章 密码与隐藏技术密码与隐藏技术 -73-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 73第第2 2章章 密码与隐藏技术密码与隐藏技术 -74-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2.6.4 RSA算法安全性算法安全性RSA算算法法的的安安全全性性取取决决于于p、q的的保保密密性性，以及分解大数的难度，即：已知r=pq，分解出p、q的困难性，所以在计算出r后要立即彻底删除p、

46、q值。随着硬件资源的发展和因数分解算法的不断改进，为保证RSA分开密钥密码体制的安全性，最实际的做法是不断提高r的位数(个人768bit、公司1024bit、甚至2048bit以上)。为了提高分解大数难度，在选p、q时，还要注意如下几点：1要使p、q是强素数；2p与q的值必须相差很大，有人建议至少要在10倍左右；3p-1与q-1的最大公因子应很小。不对称密钥密码体制与对称密钥密码体制相比较，确实有其不可取代的优点，但它的运算量远大于后者，超过后者几百倍，几千倍甚至几万倍。74第第2 2章章 密码与隐藏技术密码与隐藏技术 -75-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计

47、算机工程学院计算机工程学院 75第第2 2章章 密码与隐藏技术密码与隐藏技术 -76-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 76第第2 2章章 密码与隐藏技术密码与隐藏技术 -77-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 77第第2 2章章 密码与隐藏技术密码与隐藏技术 -78-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 78第第2 2章章 密码与隐藏技术密码与隐藏技术 -79-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工

48、程学院计算机工程学院计算机工程学院 2.8 对称加密体制与公开密钥体制比较对称加密体制与公开密钥体制比较1对称算法（1）在对称算法体制中，如果有N个成员，就需要N（N-1）/2个密钥，这巨大的密钥量给密钥的分配和安全管理带来了困难。（2）在对称算法体制中，知道了加密过程可以很容易推导出解密过程，知道了加密密钥就等于知道了解密密钥，可以用简单的方法随机产生密钥。（3）多数对称算法不是建立在严格意义的数学问题上，而是基于多种“规则”和可“选择”假设上。79第第2 2章章 密码与隐藏技术密码与隐藏技术 -80-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学

49、院（4）用对称算法传送信息时，通信双方在开始通信之前必须约定使用同一密钥，这就带来密钥在传递过程中的安全问题，所以必须建立受保护的通道来传递密钥。（5）对称算法不能提供法律证据，不具备数字签名功能。（6）对称算法加密速度快，这也是对称算法唯一的重要优点，通常用对称算法加密大量的明文。80第第2 2章章 密码与隐藏技术密码与隐藏技术 -81-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院 2公开密钥算法（1）在公开密钥体制中，每个成员都有一对密钥（pk、sk）。如果有N个成员，只需要2N个密钥，需要的密钥少，密钥的分配和安全管理相对要容易一些。（2）

50、知道加密过程不能推导出解密过程，不能从pk推导出sk，或从sk推导出pk。或者说如果能推导出来也是很难的，要花很长的时间和代价。（3）容易用数学语言描述，算法的安全性建立在已知数学问题求解困难的假设上。81第第2 2章章 密码与隐藏技术密码与隐藏技术 -82-为中华之崛起而读书为中华之崛起而读书计算机工程学院计算机工程学院计算机工程学院计算机工程学院（4）需要一个有效的计算方法求解一对密钥pk、sk，以确保不能从pk、sk中相互推导。（5）用公开密钥算法传送信息时，无需在通信双方传递密钥。也就不需要建立受保护的信息通道。这是公开密钥算法最大的优势，使得数字签名和数字认证成为可能。公开密钥算法有