第二章 预备知识(精品).ppt

《第二章 预备知识(精品).ppt》由会员分享，可在线阅读，更多相关《第二章 预备知识(精品).ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章 预备知识 密码学的数学知识2.1 数论基础 2.1.1 整数算法1、整数除法n定理1(带余数除法)设a,b是两个整数，其中b0。则存在两个整数使得a=bq+r成立，其中q和r是唯一确定的,0r|b|。n思考：C语言中用什么方式求商和余数？n两种限制：在密码学中，要求除数是正数（b0），要求余数是非负数（r0）。n如果a是负数，r和q就可能是负数，如何满足r必须是正数这个限制呢？n解决方法：q的值减1，然后再把b和r的值相加。2、整除性n定义1d|n表示d整除n，d称做n的因数。n称做d的倍n性质：l如果a|1，那么a=1l如果a|b，且b|a，那么a=bl如果a|b，且b|c，那么a|

2、cl如果a|b，且a|c，那么a|(mb+nc)n定义2整数p(1),除了1和它本身外没有任何其他因数，则它为素数。3、最大公约数 gcd(a,b)表示a和b的最大公因数，lcm(a,b)表示a和b的最小公倍数，则gcd(a,b)lcm(a,b)=ab互素：如果两个数a和b除了1以外没有其他的公因数，则两个数称为互素，记为：gcd(a,b)=1性质：gcd(a,0)=agcd(a,b)=gcd(b,r)，r是a除以b所得的余数。4、算数基本定理 定理3(算术基本定理)任何一个正整数m都存在唯一的因数分解形式:其中,是素数且这个分解形式也称为m的标准分解形式。利用算数基本定理求最大公约数和最小公

3、倍数n设a，b是两个正整数，且有标准分解形式：则：5、Euclid算法 利用Euclid算法求a和b的最大公因数:最后一个不等于0的余数就是我们要求的a,b的最大公因数gcd(a,b)。r1=a,r2=b（初始化）当r20时q=r1/r2;r=r1-qr2;r1=r2;r2=r;gcda,b=r1算法r1=a r2=br1 r2r1 r2r1 0rr0过程gcd(a,b)=r1n例：计算gcd1694,9171694=1917+777917=1777+140777=5140+77140=177+6377=163+1463=414+714=27+0所以gcd1694,917=7练习：计算2740

4、和1760的最大公约数计算25和60的最大公约数qr1r2r12740176098011760980780198078020037802001801200180209180200200qr1r2r0256025260251022510521050506、扩展Euclid算法 定理2设a,bN，则存在两个整数s和t，使得sa+tb=gcd(a,b)r1=ar2=br1r2r1r2r10rr0gcd(a,b)=r1s1=1s2=0s1s2s1s2s1s2sss过程t1=0t2=1t1t2t1t2t1t2ttts=s1t=t1s=s1-qs2t=t1-qt2r1=a;r2=bs1=0;s2=1（初始

5、化）t1=0;t2=1当r20时q=r1/r2;r=r1-qr2;r1=r2;r2=r;s=s1-qs2;s1=s2;s2=st=t1-qt2;t1=t2;t2=tgcd(a,b)=r1,s=s1t=t1例：设a=161,b=28,求gcd(161,28)以及s和t的值。思考：若a和b其中一个数为0，则s和t的值为多少？qr1r2rs1s2st1t2t5161282110101-512821701-11-56321701-14-56-2370-14623 2.1.2 模运算 1、模算符 amodn=r(n称为模数，r称为余数，n0，r0）例：求以下运算的结果：27mod536mod12-18m

6、od14-7mod10201032、余集：Zn 模数n运算的结果总是一个在0n-1之间的整数，则模运算创建了一个集，这个集在模运算中称为最小余数集Zn。集合Zn=0,1,2,3，(n-1)Z2=0,1Z6=0,1,2,3,4,5Z12=0,1,2,3,4,5,6,7,8,9,10,113、同余 从Z到Zn的映射不是一一对应的。Z的无穷多个元素可以向Zn的一个元素映射。即：a1modn=ra2modn=r则称a1和a2为同余模n，记为：a1a2(modn)212(mod10)1323(mod10)-812(mod10)38(mod5)2333(mod5)-82(mod5)假设a和b是两个整数，m

7、是一个正整数，如果m|b-a，则称a与b对模m同余。记作ab(modm)。定理4同余的性质设a,b,c是整数，则有1)aa(modm)2)若ab(modm)，则ba(modm)。3)若ab(modm),bc(modm),则ac(modm)。解释（1）同余算符与等号是有区别的。n首先，等号是把集合Z的一个元素向它本身映射，而同余符号是把Z集合的一个元素向集合Zn映射。n等号是一对一的，同余算符是多对一的。（2）插在同余算符右侧的段（modn）只表示目标集合（Zn），加这个符号是为了表明模是用作映射的。Z=-821222mod10mod10mod10mod10Z10=0,1,2,3,4,5,6,7

8、,8,9-821222(mod10)4、在集合Zn中的运算Z或Zn+modZn=1,2,3（n-1）nc(a+b)modn=c(a-b)modn=c(ab)modn=c运算例：执行下列运算（输入来自集合Zn）n在集合Z15中把7和14相加。n在集合Z13中7减去11。n在集合Z20中11减7。（14+7）mod15(7-11)mod13(711)mod2021mod15=6-4mod13=977mod20=17性质：n(a+b)modn=(amodn)+(bmodn)modnn(ab)modn=(amodn)(bmodn)modnn(ab)modn=(amodn)(bmodn)modnZ或Zn

9、+modZn=1,2,3（n-1）ncZ或Zn+modZn=1,2,3（n-1）ncmodnmodna mod nb mod nab应用(1)(1723345+2124945)mod11=(8+9)mod11=6(2)(1723345-2124945)mod11=(8-9)mod11=10(3)(17233452124945)mod11=(89)mod11=6在算法中，我们经常要求10的幂除以整数时的余数，如10mod3，102mod3等。10nmodx=(10modx)n计算：10nmod310nmod910nmod75、逆运算 （1）加法逆在Zn中，如果a+b0(modn)成立，则a和b互

10、为加法逆。如果在集合Zn中，a和b的加法逆可以按b=n-a计算，那么在集合Zn中，a和b互为加法逆。在模算法中，每一个整数都有一个加法逆。一个整数与其加法逆的和与0modn同余。注意：在模运算中，每个数都有一个加法逆且这个逆是唯一的；每个数都有且仅有一个加法逆。数的逆也可能是数本身。（2）乘法逆 在集合Zn中，如果ab1(modn)成立，则a和b互为乘法逆。在模运算中，一个整数也许有乘法逆也许没有乘法逆。如果有乘法逆，整数与其乘法逆的乘积与1modn同余。可以证明，在集合Zn中当且仅当gcd(n,a)=1时，a具有一个乘法逆。例1：求集合Z10中8的乘法逆。例2：求集合Z10中的乘法逆。例3：

11、求集合Z11中的乘法逆。求乘法逆的方法 在扩展的Euclid算法中，如果给定n和b且b在Zn中有逆，就可以求出b在集合Zn中的乘法逆。sa+tb=gcd(a,b)sn+tb=gcd(n,b)sn+tb=1（sn+tb）modn=1modn(sn)modn+(tb)modnmodn=1modn(tb)modn=1在Zn中t是b的乘法逆当且仅当gcd(n,b)=1时，b具有一个乘法逆。运用Euclid算法求乘法逆t=t1-qr2r1=ar2=br1r2r1r2r10rr0过程gcd(n,b)=r1t1=0t2=1t1t2t1t2t1t2ttt过程如果r1=1，b-1=t1r1=n;r2=bt1=0

12、;t2=1（初始化）当r20时q=r1/r2;r=r1-qr2;r1=r2;r2=r;t=t1-qt2;t1=t2;t2=t如果r1=1，那么b-1=t1算法例：求Z26中11的乘法逆。qr1r2rt1t2t22611401-2211431-251431-25-733105-72610-726t1=-7，乘法逆是（-7）mod26=19所以11在Z26中的乘法逆是19。练习n求Z100中23的乘法逆。n求Z26中12的乘法逆。6、加法表和乘法表0123456789123456789023456789013456789012456789012356789012346789012345789012

13、345689012345679012345678 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 90000000000012345678902468024680369258147048260482605050505050628406284074180296308642086420987654321 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9Z10的加法表Z10的乘法表7、加法集和乘法集的不同 如果发送方使用一个整数作为加密密钥，接受方用该整数的逆作为解密密钥。u如果这种算法是加法，Zn当作可能密钥的集。u如果这种算法是乘法，Zn

14、就不能称为可能密钥的集。u新集合Zn*:仅包含Zn中具有乘法逆的整数。u集合Zn的每一个元素都有一个加法逆，但只有部分元素具有乘法逆。集合Zn*的每一个元素具有一个乘法逆，但只有部分元素具有加法逆。要求加法逆，就用集合Zn；要求乘法逆，就用集合Zn*。Z6 0，1，2，3，4，5Z70，1，2，3，4，5,6Z100，1，2，3，4，5,6,7,8,9Z6*1，5Z7*1，2，3，4，5，6Z10*1，3，7，98、另外两个集合n密码学经常使用两个集合：Zp和Zp*，这两个集合中的模是一个素数。n除了n是素数外，Zn和Zp是相同的。Zp包含从0到p-1的所有整数。在Zp中每个数都有一个加法逆，

15、除了0以外每个元素都有一个乘法逆。n除了n是素数外，Zn*和Zp*是相同的。Zp*包含从1到p-1的所有整数。在Zp*中每个数都有一个加法逆和一个乘法逆。nZ130，1，2，3，4，5，6，7，8，9，10，11，12nZ13*1，2，3，4，5，6，7，8，9，10，11，122.1.4Euler定理1、Euler函数 定义：Euler函数是定义在正整数上的函数，它在正整数m的值等于1，2，m-1中与m互素的数的个数，记作(m)。定理：设正整数m的标准分解形式为则计算：2、Fermat（费马小定理）（3）应用快速求幂例1：求610mod11解：利用Fermat定理的第一种形式，p=11,得6

16、10mod11=1例2:求312mod11的结果解：312mod11=(3113)mod11=(311mod11)(3mod11)mod11=(33)mod11=93、Euler定理能否证明第二种形式？（1）如果a既不是p的倍数也不是q的倍数，那么a和n互素。（2）如果a是p的倍数(a=ip)，但a不是q的倍数。证明：2.1.5二次剩余定义：设gcd(a,m)=1，若同余式x2a(modm)有解，则a称作模m的二次剩余，否则称为模m的二次非剩余。定理：若gcd(a,p)=1，则a是模p的二次剩余的充要条件为1(modp),a是模p的二次非剩余的充要条件是-1(modp)。2.2信息论基础2.2

17、.1熵的概念熵是信息的数学测度或不确定性。定义1离散随机变量x的熵定义为其中，p(x)表示随机变量x的概率分布。定义2两个离散随机变量(x,y)的联合熵定义为其中，P(xy)表示离散随机变量(x,y)的联合概率分布。定义3两个离散随机变量(x,y)的条件熵定义为其中，P(xy)表示离散随机变量(x,y)的联合概率分布，P(x|y)表示两离散随机变量的条件分布。例：对某一地区进行15年的观察，发现6月份下雨的概率为0.4，晴天的概率为0.6，而10月份下雨的概率为0.65，下雪的概率为0.15，晴天的概率为0.2，分别求6月份和10月份的天气的熵。解：令x为6月份的天气，y为10月份的天气，那么

18、H(x)=-0.4log20.4-0.6log20.6=0.9694H(y)=-0.65log20.65-0.15log20.15-0.2log20.2=1.2772所以，H(x)H(y),即六月份天气的不确定性小于十月份天气的不确定性。2.2.2互信息 互信息是一个事件含有另外一个事件的信息的度量，或者是已知另外一事件的情况下，此事件不确定性的减少。定义:两个离散随机变量x和y，它们具有概率分布P(x)和P(y)和联合概率分布P(xy)，则互信息定义为：若随机变量x和y统计独立，即y不含x的任何信息，则I(x;y)=0 2.3计算复杂性简介 算法复杂性是理论计算机科学的分支科学，使用数学方法

19、对计算中所需要的各种资源的耗费做定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。复杂性理论提供了对不同的密码技术和算法的计算复杂性进行分析的方法。它对各种密码算法和技术进行比较，并确定其安全性。信息论指出，除了一次一密算法外，其他所有的算法都是可破译的。对于攻击的复杂性，可采用以下方式来衡量：（1）数据复杂性：完成攻击所需要输入的数据量 （2）时间复杂性：完成攻击所需要的时间 （3）空间复杂性：完成攻击所需要的存储空间。2.3.1算法复杂性 算法复杂性用符号“o”表示，当n变大时，增长最快的函数，所有常数和较低阶形式的函数忽略不计，只看最高阶形式的函数

20、。如，一个所给的算法复杂度为5n2+8n+10，那么计算复杂性表示为o(n2)，7n3+8n2+6n+5计算复杂性表示为o(n3)。计算复杂性常数级的：如o(1)。复杂性随n线性增长的称为它是“线性的”。如上述算法称为多项式的。2.3.2问题的分类 定义1P类问题：在多项式时间内可以解决的问题。NP类问题：在多项式时间内可以验证的问题。在NP类问题中有些特殊的问题能够被证明与此类中的任何问题一样困难，这类问题称之为NP-完全类问题。这一类问题的困难程度相当，其中只要有一个问题有多项式时间算法，则整个NP类问题都属于P类问题。2.3.2问题的分类典型的NP完全类问题：1）整数分解问题2）背包问题

21、3）哈米尔顿回路问题4）离散对数问题5）解平方剩余问题整数分解问题 根据算术基本定理，任何一个正整数都可以分解成标准形式当m较大时，这个问题很困难，属于NP完全类问题。背包问题 已知长度为k的圆形背包及长度分别为a1,a2,an的n各圆形物品。假设这些物品的半径和背包半径相同，要求从n个物品中选出若干个正好装满这个背包。数学模型：设有长度为n的向量A=(a1,a2,an)任意给定一个正整数k，寻找有没有一些ai的和恰好等于k，即求方程：的解向量x=(x1,x2,xn)，其中xi=0或1。当背包向量A的长度n比较小时，可以用穷举搜索的方法求得解向量；但当n比较大时，此问题是难解的。经证明，背包问

22、题是NP完全问题。离散对数问题 设x,r,n是正整数。已知x,r,n，可以很快求得yxr(modn)反过来，如果已知y,x和n，求r使得yxr(modn)成立，这便是离散对数问题。经过证明，离散对数问题是NP完全类问题。2.4单向哈希函数 一个单向哈希函数H(M)，操作一个任意长度的消息M，返回一个固定长度的值h。h=H(M)，其中h的长度为m。许多函数可以有任意长的输入，返回一个固定长度的输出，但单向哈希函数还有另外一些单向的性质：(1)给定M，很容易计算h；(2)给定h，很难计算M，使H(M)=h；(3)给定M，很难找到另一个消息M，使H(M)=H(M)。(4)h的每一比特都与M的每一比特

23、相关，并有高度的敏感性。即每改变M的一比特，都将对h产生明显的影响。单向哈希函数的长度：64位的哈希函数太小，多数实用的单向哈希函数产生128位的哈希值。这样，要找到两个有相同值的随机消息，就要试次。美国国家标准与技术委员会在其安全哈希函数标准中，使用了一个160位的哈希值。在实际中，以压缩函数的思想来建立单向哈希函数。这个单向函数当给定一个长度为m的输入时，输出一个长度为n的值（n比m小）。压缩函数的输入为一个消息块和前一个文本的输出。输出为所有块的哈希值。即块 的哈希值为 这个哈希值和下一个消息块一起，成为压缩函数的下一个输入。整个消息的哈希值为最后一块的哈希值。单向函数输入输出 消息带有前像，前像可以包含整条消息的长度的某种二进制表示。这个技术避免了因相同长度的消息可能有相同的哈希值带来的潜在的安全问题。许多研究者认为如果压缩函数是安全的，则这种对任意长度的前像进行散列的方法是安全的。hi 2.4 单向哈希函数 几种类型的哈希函数：N-hash：使用128位的消息块和一个复杂的随机化函数，产生一个128位的哈希值。MD2：128位的单向哈希函数，运行速度最慢。MD4：产生一个128位的哈希值。MD5：MD4算法的增强，设计上类似于MD4，也产生一个128位的值，但比MD4复杂。安全哈希算法SHA：用于数字签名标准。产生一个160位的哈希值，比MD5的长。