密码学的数学基础

1、2.1 密码学的数学基础2.1.1 熵与疑义度熵与疑义度2.1.2 自然语言率自然语言率2.1.3 密码系统的安全性密码系统的安全性2.1.4 确定性距离确定性距离2.1.5 混乱与扩散混乱与扩散2.1.1 熵与疑义度n假设所有的消息都有相等的可能性。假设所有的消息都有相等的可能性。n一条消息中的信息量：要将消息中所有可能的含一条消息中的信息量：要将消息中所有可能的含意编码所需的最少的比特位数。意编码所需的最少的比特位数。n熵：用来形式化地衡量一条消息熵：用来形式化地衡量一条消息M中的信息量，中的信息量，记为记为H(M)。当用比特来衡量时，为。当用比特来衡量时，为log2n，其中，其中n为消息

2、的状态个数，假设所有状态有相等的出现为消息的状态个数，假设所有状态有相等的出现概率。概率。n例：数据库中表示例：数据库中表示“星期星期”的字段宽度不超过的字段宽度不超过3bit的信息的信息n 000 星期一星期一n 001 星期二星期二n 010 星期三星期三n 011 星期四星期四n 100 星期五星期五n 101 星期六星期六n 110 星期日星期日n 111 不不 用用n表示星期的信息的熵表示星期的信息的熵 H(M)= log2n= log27=2.807n表示性别的信息的熵表示性别的信息的熵 H(M)= log2n= log22=1n表示季节的信息的熵表示季节的信息的熵 H(M)= l

3、og2n= log24=2n表示月份的信息的熵表示月份的信息的熵 H(M)= log2n= log212=3.585nn疑义度：消息的熵同时也可衡量其不确定性（疑疑义度：消息的熵同时也可衡量其不确定性（疑义度），即将消息隐藏在密文中时，要破译它所义度），即将消息隐藏在密文中时，要破译它所需的明文比特数。需的明文比特数。n例：性别的疑义度为例：性别的疑义度为12.1.2 自然语言率n自然语言率：对于给定的一种语言，其自然语言自然语言率：对于给定的一种语言，其自然语言率为率为r = H(M)/ N其中其中N为消息长度。为消息长度。n英语的自然语言率：英语的自然语言率：1.0比特比特/字母字母1.5

4、比特比特/字母字母n绝对语言率：每个字符编码的最大比特数，这里绝对语言率：每个字符编码的最大比特数，这里假设每个字符序列出现的机会相等。假设每个字符序列出现的机会相等。n若语言中有若语言中有L个字母，则绝对语言率为：个字母，则绝对语言率为：R = log2L 为单个字母的最大熵。为单个字母的最大熵。n英语的绝对语言率：英语的绝对语言率：log226 4.7比特比特/字母字母n冗余度：语言的冗余度记为冗余度：语言的冗余度记为D，定义为：，定义为：D = R - r其中，其中，R为绝对语言率，为绝对语言率，r为自然语言率。为自然语言率。英语：英语：r = 1.3比特比特/字母，则字母，则 D =

5、4.7 -1.3=3.4比特比特/字母。字母。2.1.3 密码系统的安全性n绝对安全的密码系统：一次一密（密钥与消息本绝对安全的密码系统：一次一密（密钥与消息本身一样长，密钥随机产生且不重复使用）身一样长，密钥随机产生且不重复使用）n密码系统的熵：衡量密钥空间密码系统的熵：衡量密钥空间K的大小的一个标准，的大小的一个标准，通常是密钥数以通常是密钥数以2为底的对数。为底的对数。H（K） = log2k2.1.4 确定性距离n对于长度为对于长度为n的消息，能够将一段密文消息解密成的消息，能够将一段密文消息解密成与原始明文同种语言的可懂文本的密钥个数为：与原始明文同种语言的可懂文本的密钥个数为：2H

6、(K)- nD - 1n确定性距离：能够唯一地确定密钥的最短的密文确定性距离：能够唯一地确定密钥的最短的密文长度的近似值。长度的近似值。n对称密码系统的确定性距离：定义为密码系统的熵除对称密码系统的确定性距离：定义为密码系统的熵除以语言的冗余度。以语言的冗余度。U = H（K）/ Dn理想安全的密码系统：确定性距离无限大的密码理想安全的密码系统：确定性距离无限大的密码系统。系统。2.1.5 混乱与扩散n混乱：在加密变换中，让密钥与密文的关系尽可混乱：在加密变换中，让密钥与密文的关系尽可能复杂的做法。能复杂的做法。n实现混乱的方法：代替（恺撒密码）实现混乱的方法：代替（恺撒密码）n扩散：在加密过

7、程中，尽可能将明文的统计特性扩散：在加密过程中，尽可能将明文的统计特性在密文中消除。在密文中消除。n实现扩散的方法：换位（钥控序列加密法）实现扩散的方法：换位（钥控序列加密法）2.2 复杂性理论2.2.1 算法复杂性算法复杂性2.2.2 问题复杂性问题复杂性2.2.1 算法复杂性n算法的复杂性通常由两个变量来衡量：算法的复杂性通常由两个变量来衡量：T（时间复（时间复杂性）和杂性）和S（空间复杂性，或存储需求）。（空间复杂性，或存储需求）。nT和和S都用都用n的函数来表示，其中的函数来表示，其中n为输入的大小。为输入的大小。n数量级法：当数量级法：当n增大时，复杂性函数中增加得最快增大时，复杂性

8、函数中增加得最快的一项。的一项。n时间复杂性为时间复杂性为4n5+7n+12复杂性的阶为复杂性的阶为n5 , 表示为表示为O(n5)n多项式时间算法：多项式时间算法：nO(1)：常数的：常数的nO(n)：线性的：线性的nO(n2)：平方的：平方的nnO(nm)：m为常数为常数n指数时间算法：指数时间算法：O(tf(n)，其中，其中t为大于为大于1的常数，的常数，f(n)为为n的多项式函数。的多项式函数。n超多项式时间算法：超多项式时间算法：O(cf(n)，其中，其中c为大于为大于1的常数，的常数，f(n)大于常数，小于线性。大于常数，小于线性。2.2.2 问题复杂性n图灵机：一个有限状态机，具

9、有无限的读写存储图灵机：一个有限状态机，具有无限的读写存储磁带，是一个理想化的计算模型。磁带，是一个理想化的计算模型。n问题：问题：n易解的问题：可以在多项式时间内求解易解的问题：可以在多项式时间内求解n难解的问题：只能在指数时间内求解难解的问题：只能在指数时间内求解n不确定的问题：找不出解决的算法，不考虑算法的时不确定的问题：找不出解决的算法，不考虑算法的时间复杂性间复杂性n问题复杂性的划分：问题复杂性的划分：nP问题：可以在多项式时间内求解的问题。问题：可以在多项式时间内求解的问题。nNP问题：只能在一个非确定性的图灵机（能够进行猜问题：只能在一个非确定性的图灵机（能够进行猜测的一种图灵机

10、）上在多项式时间内求解的问题。测的一种图灵机）上在多项式时间内求解的问题。nNP完全问题：一些特定的完全问题：一些特定的NP问题，与其他问题，与其他NP问题同等困难。问题同等困难。nP空间问题：可以在多项式空间内求解，但不能在多项空间问题：可以在多项式空间内求解，但不能在多项式时间内求解的问题。式时间内求解的问题。nP空间完全问题：与其他空间完全问题：与其他P空间问题同等困难。空间问题同等困难。n指数时间问题：在指数时间内求解。指数时间问题：在指数时间内求解。PNPNP完全的P空间P空间完全的指数时间的2.3 初等数论2.3.1 模运算模运算2.3.2 素数素数2.3.3 最大公因数最大公因数

11、2.3.4 乘法逆元素乘法逆元素2.3.5 Fermat小定理及欧拉函数小定理及欧拉函数2.3.6 中国剩余定理中国剩余定理2.3.7 二次剩余二次剩余2.3.8 Legendre（勒让得）符号（勒让得）符号2.3.9 Jacobi（雅各比）符号（雅各比）符号2.3.10 生成元生成元2.3.11 有限域中的计算有限域中的计算2.3.1 模运算n同余：如果同余：如果a = b + kn，k为整数，则为整数，则a b（mod n）含义：含义：b是是a除以除以n的余数；的余数； b为为a模模n的余数；的余数； a与与b模模n同余。同余。na mod n ：a模模n操作，表示操作，表示a除以除以n的

12、余数，为的余数，为 0到到n 1之间的整数。之间的整数。例如：例如：(78) mod 12 = 15 mod 12 = 3 15 3(mod)12 n模运算（模运算（+、 ）满足交换律、结合律和分配律。）满足交换律、结合律和分配律。n按模计算原理：对中间结果作模运算与做完了全部运算按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。后再做模运算结果相同。n按模指数运算：按模指数运算：am mod nn将指数运算作为一系列乘法运算，每次做一次模运算。将指数运算作为一系列乘法运算，每次做一次模运算。n例：例：a8 mod n = (a2 mod n)2 mod n)2 mod n

13、n当当m不是不是2的乘方时，将的乘方时，将m表示成表示成2的乘方和的形式。的乘方和的形式。n例如：例如：25=(11001)2，即，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod nn适当存储中间结果，则只需适当存储中间结果，则只需6次乘法：次乘法：(a2mod n) a)mod n)2mod n)2mod n)2mod n) a)mod nn例：例：n315 mod 11=n57 mod 13= n213 mod 9=n711 mod 12=n415 mod

14、 7 =n315 mod 11=1n57 mod 13= 8n213 mod 9=2n711 mod 12= 7n415 mod 7 =12.3.2 素数n素数（质数）：大于素数（质数）：大于1的整数，只能被的整数，只能被1和本身整和本身整除。除。n有无穷多个素数。有无穷多个素数。n如：如：2，73，2521，2365347734339，2756839-12.3.3 最大公因数n公因数：两个整数公因数：两个整数a，b的公因数定义为能同时整的公因数定义为能同时整除除a，b的所有整数。的所有整数。n最大公因数：最大公因数：a与与b的公因数中能被所有的公因数中能被所有a，b的公的公因数整除的正整数，

15、记为因数整除的正整数，记为gcd(a，b)。n 例：例：gcd(48,36)=12n互素（互质）：两个整数称为互素的，如果它们互素（互质）：两个整数称为互素的，如果它们除了除了1以外没有其他的公因数，即以外没有其他的公因数，即 gcd(a,b)=1。n最大公因数的求法：辗转相除法最大公因数的求法：辗转相除法n例如：求例如：求gcd(15,36) gcd(54,30) 36=15 2+6 54=30+24 15=6 2+3 30=24+6 6=3 2+0 24=4 6+0因此，因此，gcd(15,36)=3 gcd(54,30)=6n原理：若原理：若a b (mod c)，则，则 gcd(a,c

16、) = gcd(b,c)n这里，这里，gcd(36,15) = gcd(6,15) = gcd(6,3) = 3n求最大公因数的求最大公因数的Euclid算法算法 p16 a b 15 36 36 15 15 6 6 3 3 0 2.3.4 乘法逆元素n求求x，满足，满足 (a x) mod n = 1, 即即 x a-1(mod n)n当当a与与n互素时互素时, 方程方程 x a-1(mod n) 有唯一解；有唯一解；即：即：ax-kn=1n当当a与与n不互素时不互素时, 此方程无此方程无解。解。n一个数关于某一个模的乘法逆元不一定存在。一个数关于某一个模的乘法逆元不一定存在。n2关于模关于

17、模14的乘法逆元不存在，因为的乘法逆元不存在，因为2与与14不互素不互素na与与n互素，互素，a关于模关于模n的乘法逆元才存在的乘法逆元才存在n求乘法逆元：扩展的求乘法逆元：扩展的Euclid算法算法n例：求例：求5关于模关于模14的乘法逆元的乘法逆元n辗转相除：辗转相除：14 = 5 2 + 4 5 = 4 + 1n逆推：逆推：1 = 5 - 4 = 5 - （14 - 5 2）= 5 3 - 14 n因此，因此，5关于模关于模14的乘法逆元为的乘法逆元为3。n例：求例：求4关于模关于模7的乘法逆元的乘法逆元 7=4 1+3 4=3+1 1=4-3 =4-(7-4) =4 2-7 所以所以4

18、关于模关于模7的乘法逆元为的乘法逆元为2练习n练习：求练习：求17关于模关于模26的乘法逆元。的乘法逆元。答案n求求17关于模关于模26的乘法逆元。的乘法逆元。n答案：答案：2326 = 17 + 9 1 = 9 - 817 = 9 + 8 = 9 - (17 - 9)9 = 8 + 1 = 9 2 - 17 = (26 - 17) 2 - 17 = 26 2 - 17 3 = 17 (-3) + 26 2+17 26- 17 26 = 17 23 - 26 152.3.5 Fermat小定理及欧拉函数nFermat小定理：如果小定理：如果m为素数，为素数，a不能被不能被m整除，整除，则则 a

19、m-1 1 (mod m)例：例：210 1 mod 11 610 1 mod 11 710 1 mod 11 810 1 mod 11 36 1 mod 7 n模模n的简化剩余集：模的简化剩余集：模n的完全剩余集的一个子集，其中每个元素的完全剩余集的一个子集，其中每个元素与与n互素。如果互素。如果n为素数，则模为素数，则模n的简化剩余集为从的简化剩余集为从1 n-1。例：模例：模12的简化剩余集为的简化剩余集为1，5，7，11 模模7的简化剩余集为的简化剩余集为1，2，3，4，5，6 n欧拉函数：记为欧拉函数：记为 (n)，为模，为模n的简化剩余集中元素的个数。的简化剩余集中元素的个数。n如

20、果如果n是素数，则是素数，则 (n) = n-1n若若n=pq，其中，其中p、q为素数，则为素数，则 (n)=（p-1)(q-1)n例：例：n=15 , n=3 5 , p=3, q=5n (n)=2 4=8n 15的简化剩余集为的简化剩余集为1，2，4，7，8，11，13，14n欧拉扩展的欧拉扩展的Fermat小定理：如果小定理：如果gcd(a,n) = 1，则，则 a (n) mod n = 1。na的乘法逆元：的乘法逆元：x=a (n)-1 mod nn例：求例：求5关于模关于模7的乘法逆元的乘法逆元解：方法一：解：方法一：7=5+2 5=2 2+1 1=5-2 2 =5-2 (7-5)

21、 =3 5-2 7 5关于模关于模7的乘法逆元为的乘法逆元为3n方法二：方法二： n=7 n为素数，为素数，gcd(5,7)=1, (n)=n-1=7-1=6x= a (n)-1 mod n =5 6-1 mod 7=55mod 7=3n例：例：4关于模关于模7的乘法逆元的乘法逆元解：解： (7)=7-1=6 n为素数为素数 gcd(4,7)=1 x= a (n)-1 mod n =46-1 mod 7=45mod 7=22.3.6 中国剩余定理n定理：如果定理：如果n的素数因子分解式为的素数因子分解式为p1 p2 pt，则一组方程则一组方程 (x mod pi）= ai，其中，其中i = 1

22、,2,t，有，有唯一解唯一解x，其中，其中x小于小于n（其中某些（其中某些pi可能相等）。可能相等）。n例：今有物不知其数，三三数之剩二，五五数之例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？剩三，七七数之剩二，问物几何？x mod 3 = 2x mod 5 = 3x mod 7 = 2n解法：解法：令令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=3 5 7=105，M1=n/p1=35, M2=n/p2=21, M3=n/p3=15求解求解 35 x1 mod 3=1, 得得x1=2求解求解 21 x2 mod 5=1, 得得x

23、2=1求解求解 15 x3 mod 7=1, 得得x3=1则则 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3+15 1 2) mod 105 = 233 mod 105 = 23n练习：练习：n今有数不知其数，两两数之剩今有数不知其数，两两数之剩1，三三数之剩，三三数之剩2，五五，五五数之剩数之剩2，求该数。，求该数。n解法：解法：令令a1=1，a2=2，a3=2，p1=2，p2=3，p3=5，n=p1 p2 p3=2 3 5=30M1=n/p1=15, M2=n/p2=10, M3=n/p3=6求解求解 15 x1 mod

24、2=1, 得得x1=1求解求解 10 x2 mod 3=1, 得得x2=1求解求解 6 x3 mod 5=1, 得得x3=1则则 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (15 1 1+10 1 2+6 1 2) mod 30 = 47 mod 30 = 17n课后练习：课后练习：n今有数不知其数，五五数之剩今有数不知其数，五五数之剩2，七七数之剩，七七数之剩5，十一，十一十一数之剩十一数之剩3，求该数。，求该数。2.3.7 二次剩余n定义：设定义：设p为素数，为素数，a0且且ap，如果存在某个，如果存在某个x，满足满足x2 a (mod p)，则称

25、，则称a为模为模p的二次剩余。否的二次剩余。否则称则称a为模为模p的非二次剩余。的非二次剩余。n例例1：p=5, a=4 x=2 22 4 （mod 5）n例例2：p=11, a=5 x=4 42 5 （mod 11）2.3.8 Legendre（勒让得）符号n记为记为L(a,p)，其中，其中a为任意整数，为任意整数，p为大于为大于2的素数。的素数。n定义：定义：nL(a,p) = 0，如果，如果a能被能被p整除；整除；nL(a,p) = 1，如果，如果a是模是模p的二次剩余；的二次剩余；nL(a,p) = -1，如果，如果a是模是模p的非二次剩余；的非二次剩余；n计算：计算：L(a,p) =

26、 a(p-1)/2 mod p公式验证：公式验证：L(a,p) = a(p-1)/2 mod p = (a(p-1) mod p)1/2 = 1 Fermat小定理：小定理： am-1 1 (mod m) = 1 L(a,p) = -1=p-1Legendre符号的用途n用用Legendre符号来验证符号来验证a是否是模是否是模p的二次剩余的二次剩余n举例举例:n验证：验证：a=5是否是是否是p=11的二次剩余？的二次剩余？L(a,p) = a(p-1)/2 mod p=5(11-1)/2 mod 11=55 mod 11=1 即即 L(5,11) =1 所以所以5是模是模11的二次剩余的二次

27、剩余 (72 5 mod 11) 再如：再如： L(6,11)= 6(11-1)/2 mod 11=65 mod 11=10=p-1 所以所以6不是模不是模11的二次剩余的二次剩余n22 4 mod 5 L(4,5)=4(5-1)/2 mod 5 =1 42 5 mod 11 L(5,11)=5(11-1)/2 mod 11 =12.3.9 Jacobi（雅各比）符号n记为记为J(a,n)，是，是Legendre符号的扩展，其中符号的扩展，其中a为任意整数，为任意整数，而而n为任意奇数。为任意奇数。n定义：定义：nJ(a,n)只对只对n为奇数时有意义为奇数时有意义nJ(0,n)=0n如果如果n

28、为素数，且为素数，且a能被能被n整除，则整除，则J(a,n)=0n如果如果n为素数，且为素数，且a是模是模n的二次剩余，则的二次剩余，则J(a,n) = 1(即即x2 a mod n)n如果如果n为素数，且为素数，且a是模是模n的非二次剩余，则的非二次剩余，则J(a,n) = -1n如果如果n是合数，则是合数，则J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中将，其中将n因数分解为因数分解为p1p2pmnJacobi符号的计算（略）符号的计算（略）P19nBlum整数：整数：n若若p和和q为两个素数，且都与为两个素数，且都与3模模4同余，则同余，则n = pq称为称为Blum整数

29、。若整数。若n为为Blum整数，则每个模整数，则每个模n的二次剩余的二次剩余恰好有恰好有4个平方根，其中一个也是一个二次剩余，称为个平方根，其中一个也是一个二次剩余，称为原平方根。原平方根。n例如，例如，139的模的模437的原平方根为的原平方根为24，另三个平方根为，另三个平方根为185，252和和413。n=437=19*23 p=19 q=23242 139 （mod 437） 1852 139 （mod 437）2522 139 （mod 437） 4132 139 （mod 437）2.3.10 生成元n定义：如果定义：如果p为素数，为素数，gp，如果对每个，如果对每个b从从1到到p

30、-1，存在存在a，使，使ga b (mod p)，则，则g为模为模p的生成元。的生成元。n例：例：p=11，2为模为模11的生成元的生成元g=2 p=11 b=110 都可表示成：都可表示成：2a mod p1 210 mod 11 6 29 mod 11 2 21 mod 11 7 27 mod 11 3 28 mod 11 8 23 mod 11 4 22 mod 11 9 26 mod 11 5 24 mod 11 10 25 mod 11n生成元的测试生成元的测试nq=p-1 q=q1*q2*qnn对每个对每个qi, 若若 g (p-1)/qimod p=1，则，则g不是生成元。不是生

31、成元。n例：例：p=11 q=10=2*5 g=2 2 (11-1)/2 mod 11= 10 2 (11-1)/5 mod 11= 4 所以所以 2是模是模11的生成元的生成元 g=3 3 (11-1)/2 mod 11= 1 3 (11-1)/5 mod 11= 9 所以所以 3不是模不是模11的生成元的生成元n练习：求模练习：求模11的生成元一共有几个？的生成元一共有几个？2.3.11 有限域中的计算n有限域：元素个数有限的域，也叫伽罗瓦有限域：元素个数有限的域，也叫伽罗瓦（Galois）域。）域。n在有限域中，非在有限域中，非0数的加、减、乘、除都有定义。数的加、减、乘、除都有定义。加

32、法单位元是加法单位元是0，乘法单位元是，乘法单位元是1，每个非，每个非0元素都元素都有一个唯一的乘法逆元。有一个唯一的乘法逆元。n有限域中运算满足交换律、结合律和分配律。有限域中运算满足交换律、结合律和分配律。n有限域中元素个数为素数或素数的乘方：设有限域中元素个数为素数或素数的乘方：设p为素为素数，则有限域可记为数，则有限域可记为GF(p)或或GF(pn)。n不可约多项式：一个多项式如果除了不可约多项式：一个多项式如果除了1和本身外，和本身外，不能分解成其他多项式的乘积形式，则成为不可不能分解成其他多项式的乘积形式，则成为不可约多项式。约多项式。n 例：例：x2+1 而而x3+ 2x2+x

33、= x(x+1)(x+1) 不是不可约多项式不是不可约多项式n本原多项式：一个有限域内的生成元多项式，其本原多项式：一个有限域内的生成元多项式，其系数是互素的。系数是互素的。n在在GF(qn)中，所有运算都是模中，所有运算都是模p(x)的运算，其中的运算，其中p(x)是是n阶不可约多项式。阶不可约多项式。P(x)=xn+x+12.4 因数分解n对一个数进行因数分解，是指找出这个数的素数对一个数进行因数分解，是指找出这个数的素数因子。因子。6=2 38=2 2 29=3 310=2 560=2 2 3 5252601=41 61 1012.5 素数的产生2.5.1 Solovay-Strasse

34、n方法方法2.5.2 Lehmann法法2.5.3 强素数强素数2.5.1 Solovay-Strassen方法n用用Jacobi符号来测试符号来测试p是否为素数：是否为素数：（1）选择一个随机数）选择一个随机数a，ap；（2）如果）如果gcd(a,p) 1，则，则p是合数，停止检测；是合数，停止检测；（3）计算）计算i=a(p-1)/2 mod p；（4）计算）计算Jacobi符号符号J(a,p)；（5）如果）如果i J(a,p)，则，则p不是素数；不是素数；（6）如果）如果i= J(a,p)，则，则p不是素数的概率小于不是素数的概率小于50%。n对对t个不同的随机数个不同的随机数a，重复进行这个测试。能