【文档说明】安全与保密.pptx，共(55)页，160.135 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-287903.html

以下为本文档部分文字说明：

2.1信息论2.1.1熵与疑义度2.1.2自然语言率2.1.3密码系统的安全性2.1.4确定性距离2.1.5混乱与扩散2.1.1熵与疑义度◼假设所有的消息都有相等的可能性。◼一条消息中的信息量：要将消息中所有可能的含意

编码所需的最少的比特位数。◼熵：用来形式化地衡量一条消息M中的信息量，记为H(M)。当用比特来衡量时，为log2n，其中n为消息的状态个数，假设所有状态有相等的出现概率。◼例：数据库中表示“星期”的字段宽度不超过3bit的信息◼000星期一◼001星期二◼010星期三

◼011星期四◼100星期五◼101星期六◼110星期日◼111不用◼表示星期的信息的熵H(M)=log2n=log27=2.807◼表示性别的信息的熵H(M)=log2n=log22=1◼表示季节的信息的熵H(M)=log2n=log24=

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

率为r=H(M)/N其中N为消息长度。◼英语的自然语言率：1.0比特/字母～1.5比特/字母◼绝对语言率：每个字符编码的最大比特数，这里假设每个字符序列出现的机会相等。◼若语言中有L个字母，则绝对语言率为：R=log2L为单个字母的最大熵。◼英语的绝对语言率：log2264.7比特/字母◼冗

余度：语言的冗余度记为D，定义为：D=R-r其中，R为绝对语言率，r为自然语言率。英语：r=1.3比特/字母，则D=4.7-1.3=3.4比特/字母。2.1.3密码系统的安全性◼绝对安全的密码系统：一次一密（密钥与消息本身一样长，密钥随机产生且不重复使用）◼密码系统的熵：衡量密钥空间

K的大小的一个标准，通常是密钥数以2为底的对数。H（K）=log2k2.1.4确定性距离◼对于长度为n的消息，能够将一段密文消息解密成与原始明文同种语言的可懂文本的密钥个数为：2H(K)-nD-1◼确定性距离：能够唯一地确定密钥的最短的密文长度的近似值。◼对称密码系统的确定性距离：定义为

密码系统的熵除以语言的冗余度。U=H（K）/D◼理想安全的密码系统：确定性距离无限大的密码系统。2.1.5混乱与扩散◼混乱：在加密变换中，让密钥与密文的关系尽可能复杂的做法。◼实现混乱的方法：代替（恺撒密码）◼扩散：在加密过程中，尽可能将明文的统计特性在密文中消除。◼实现扩散的方

法：换位（钥控序列加密法）2.2复杂性理论2.2.1算法复杂性2.2.2问题复杂性2.2.1算法复杂性◼算法的复杂性通常由两个变量来衡量：T（时间复杂性）和S（空间复杂性，或存储需求）。◼T和S都用n的函数来表示，其

中n为输入的大小。◼数量级法：当n增大时，复杂性函数中增加得最快的一项。◼时间复杂性为4n5+7n+12复杂性的阶为n5,表示为O(n5)◼多项式时间算法：◼O(1)：常数的◼O(n)：线性的◼O(n2)：平方的◼…◼O(nm)：m为常

数◼指数时间算法：O(tf(n))，其中t为大于1的常数，f(n)为n的多项式函数。◼超多项式时间算法：O(cf(n))，其中c为大于1的常数，f(n)大于常数，小于线性。2.2.2问题复杂性◼图灵机：一个有限状态机，具有无限的读写存储磁带，是

一个理想化的计算模型。◼问题：◼易解的问题：可以在多项式时间内求解◼难解的问题：只能在指数时间内求解◼不确定的问题：找不出解决的算法，不考虑算法的时间复杂性◼问题复杂性的划分：◼P问题：可以在多项式时间内求解的问题。◼NP问题：只能在一个非确定性的图灵机（能够进行猜测的一种图

灵机）上在多项式时间内求解的问题。◼NP完全问题：一些特定的NP问题，与其他NP问题同等困难。◼P空间问题：可以在多项式空间内求解，但不能在多项式时间内求解的问题。◼P空间完全问题：与其他P空间问题同等困难。◼指数时间问题：在指数时间内求解

。PNPNP完全的P空间P空间完全的指数时间的2.3初等数论2.3.1模运算2.3.2素数2.3.3最大公因数2.3.4乘法逆元素2.3.5Fermat小定理及欧拉函数2.3.6中国剩余定理2.3.7二次剩余2.

3.8Legendre（勒让得）符号2.3.9Jacobi（雅各比）符号2.3.10生成元2.3.11有限域中的计算2.3.1模运算◼同余：如果a=b+kn，k为整数，则ab（modn）含义：b是a除以n的余数；b为a模n的余数；a与b模n同余。◼amodn

：a模n操作，表示a除以n的余数，为0到n－1之间的整数。例如：(7＋8)mod12=15mod12=3153(mod)12◼模运算（+、－、）满足交换律、结合律和分配律。◼按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。

◼按模指数运算：ammodn◼将指数运算作为一系列乘法运算，每次做一次模运算。◼例：a8modn=((a2modn)2modn)2modn◼当m不是2的乘方时，将m表示成2的乘方和的形式。◼例如：25=(11001)2，即25=24+23+2

0a25modn=(a16a8a)modn=((((a2)2)2)2((a2)2)2a)modn=((((a2a)2)2)2a)modn◼适当存储中间结果，则只需6次乘法：(((((((a2modn)a)modn)2modn)2modn

)2modn)a)modn◼例：◼315mod11=◼57mod13=◼213mod9=◼711mod12=◼415mod7=◼315mod11=1◼57mod13=8◼213mod9=2◼711mod12=7◼415mod7=12

.3.2素数◼素数（质数）：大于1的整数，只能被1和本身整除。◼有无穷多个素数。◼如：2，73，2521，2365347734339，2756839-12.3.3最大公因数◼公因数：两个整数a，b的公因

数定义为能同时整除a，b的所有整数。◼最大公因数：a与b的公因数中能被所有a，b的公因数整除的正整数，记为gcd(a，b)。◼例：gcd(48,36)=12◼互素（互质）：两个整数称为互素的，如果它们除了1以外没有其他的公因数，即g

cd(a,b)=1。◼最大公因数的求法：辗转相除法◼例如：求gcd(15,36)gcd(54,30)36=152+654=30+2415=62+330=24+66=32+024=46+0因此，gcd(15,36)=3gcd(54,30)=6◼原理

：若ab(modc)，则gcd(a,c)=gcd(b,c)◼这里，gcd(36,15)=gcd(6,15)=gcd(6,3)=3◼求最大公因数的Euclid算法p16ab1536361515663302

.3.4乘法逆元素◼求x，满足(a·x)modn=1,即xa-1(modn)◼当a与n互素时,方程xa-1(modn)有唯一解；即：ax-kn=1◼当a与n不互素时,此方程无解。◼一个数关于某一个模的乘法逆元不一定存在

。◼2关于模14的乘法逆元不存在，因为2与14不互素◼a与n互素，a关于模n的乘法逆元才存在◼求乘法逆元：扩展的Euclid算法◼例：求5关于模14的乘法逆元◼辗转相除：14=52+45=4+1◼逆推：1=5-4=5-（

14-52）=53-14◼因此，5关于模14的乘法逆元为3。◼例：求4关于模7的乘法逆元7=41+34=3+11=4-3=4-(7-4)=42-7所以4关于模7的乘法逆元为2练习◼练习：求17关于模26的乘法逆元。答案◼求17关于模26的乘法逆元。◼答案：2326=17+91=9-8

17=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.5Fermat小定理及欧拉函数◼Fermat小定理：如果m为素数，a不能被m整除，则am-11(modm)例：

2101mod116101mod117101mod118101mod11361mod7◼模n的简化剩余集：模n的完全剩余集的一个子集，其中每个元素与n互素。如果n为素数，则模n的简化剩余集为从1~n-1。例：模12的简化剩余集为{1，5，7，11}模7的简化剩余集为{1，2，3，4

，5，6}◼欧拉函数：记为(n)，为模n的简化剩余集中元素的个数。◼如果n是素数，则(n)=n-1◼若n=pq，其中p、q为素数，则(n)=（p-1)(q-1)◼例：n=15,n=35,p=3,q=5◼(n)=24=8◼15的简化剩余集为{1

，2，4，7，8，11，13，14}◼欧拉扩展的Fermat小定理：如果gcd(a,n)=1，则a(n)modn=1。◼a的乘法逆元：x=a(n)-1modn◼例：求5关于模7的乘法逆元解：方法一：7=5+25=22+11=5-22=5-2(

7-5)=35-275关于模7的乘法逆元为3◼方法二：n=7n为素数，gcd(5,7)=1,(n)=n-1=7-1=6x=a(n)-1modn=56-1mod7=55mod7=3◼例：4关于模7的乘法逆元解：(7)=7-1=6n为素数gcd(4,7)=1x=

a(n)-1modn=46-1mod7=45mod7=22.3.6中国剩余定理◼定理：如果n的素数因子分解式为p1p2…pt，则一组方程(xmodpi）=ai，其中i=1,2,…,t，有唯一解x，其中x小于n（其中某些pi可能相等）。◼例：今有物不知其数，三三数之剩二，五

五数之剩三，七七数之剩二，问物几何？xmod3=2xmod5=3xmod7=2◼解法：令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·x1mod3=1,得x1=2

求解21·x2mod5=1,得x2=1求解15·x3mod7=1,得x3=1则x=(M1·x1·a1+M2·x2·a2+M3·x3·a3)modn=(3522+2113+1512)mod105=233mod105=23◼练习：◼今有数不知其数，两两数之剩1，三三

数之剩2，五五数之剩2，求该数。◼解法：令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·x1mo

d2=1,得x1=1求解10·x2mod3=1,得x2=1求解6·x3mod5=1,得x3=1则x=(M1·x1·a1+M2·x2·a2+M3·x3·a3)modn=(1511+1012+612)mod30=47mod30=17◼课后练习：◼今有数不知其数，五五数之剩2，七七数

之剩5，十一十一数之剩3，求该数。2.3.7二次剩余◼定义：设p为素数，a>0且a<p，如果存在某个x，满足x2a(modp)，则称a为模p的二次剩余。否则称a为模p的非二次剩余。◼例1：p=5,a=4x=2224（mod5）◼例

2：p=11,a=5x=4425（mod11）2.3.8Legendre（勒让得）符号◼记为L(a,p)，其中a为任意整数，p为大于2的素数。◼定义：◼L(a,p)=0，如果a能被p整除；◼L(a,p)=1，如果a是模p的二次剩余；◼L(a,p)=-1，如果a是模p的非二次剩余；◼计算

：L(a,p)=a(p-1)/2modp公式验证：L(a,p)=a(p-1)/2modp=(a(p-1)modp)1/2=1½Fermat小定理：am-11(modm)=±1L(a,p)=-1=p-1

Legendre符号的用途◼用Legendre符号来验证a是否是模p的二次剩余◼举例:◼验证：a=5是否是p=11的二次剩余？L(a,p)=a(p-1)/2modp=5(11-1)/2mod11=55mod11=1即L(5,11)=1所以5是模11的二次剩余(7

25mod11)再如：L(6,11)=6(11-1)/2mod11=65mod11=10=p-1所以6不是模11的二次剩余◼224mod5L(4,5)=4(5-1)/2mod5=1425mod11L(5,11)=5(11-1

)/2mod11=12.3.9Jacobi（雅各比）符号◼记为J(a,n)，是Legendre符号的扩展，其中a为任意整数，而n为任意奇数。◼定义：◼J(a,n)只对n为奇数时有意义◼J(0,n)=0◼如果n为素数，且a能被n整除，则J(a,n)=0◼如果n为素数，且a

是模n的二次剩余，则J(a,n)=1(即x2amodn)◼如果n为素数，且a是模n的非二次剩余，则J(a,n)=-1◼如果n是合数，则J(a,n)=J(a,p1)×J(a,p2)×…×J(a,pm)，其中将n因数分解为p1×p

2×…×pm◼Blum整数：◼若p和q为两个素数，且都与3模4同余，则n=pq称为Blum整数。若n为Blum整数，则每个模n的二次剩余恰好有4个平方根，其中一个也是一个二次剩余，称为原平方根。◼例如，139的模437的原平方根为2

4，另三个平方根为185，252和413。n=437=19*23p=19q=23242139（mod437）1852139（mod437）2522139（mod437）4132139（mod437）2.3.10生成元◼定义：如果p为素数，g<p，如果对每个

b从1到p-1，存在a，使gab(modp)，则g为模p的生成元。◼例：p=11，2为模11的生成元g=2p=11b=1~10都可表示成：2amodp1210mod11629mod11221mo

d11727mod11328mod11823mod11422mod11926mod11524mod111025mod11◼生成元的测试◼q=p-1q=q1*q2*……*qn◼对每个qi,若g(p-1)/qimodp=1，则g不是生成元。◼例：p=11q=1

0=2*5g=22(11-1)/2mod11=102(11-1)/5mod11=4所以2是模11的生成元g=33(11-1)/2mod11=13(11-1)/5mod11=9所以3不是模11的生成元◼练习：求模11的生成元一共有几个？2.3.11有限域中的计算

◼有限域：元素个数有限的域。◼在有限域中，非0数的加、减、乘、除都有定义。加法单位元是0，乘法单位元是1，每个非0元素都有一个唯一的乘法逆元。◼有限域中运算满足交换律、结合律和分配律。◼有限域中元素个数为素数或素数的乘方：

设p为素数，则有限域可记为GF(p)或GF(pn)。◼不可约多项式：一个多项式如果除了1和本身外，不能分解成其他多项式的乘积形式，则成为不可约多项式。◼例：x2+1而x3+2x2+x=x(x+1)(x+1)不是不可约多项式◼本原多项式：一个有限域内

的生成元多项式，其系数是互素的。◼在GF(qn)中，所有运算都是模p(x)的运算，其中p(x)是n阶不可约多项式。P(x)=xn+x+12.4因数分解◼对一个数进行因数分解，是指找出这个数的素数因子。6=238=2229=3310=2560=223

5252601=41611012.5素数的产生2.5.1Solovay-Strassen方法2.5.2Lehmann法2.5.3强素数2.5.1Solovay-Strassen方法◼用Jacobi符号来测试p是否为素数：（1）选择一个随机数a，a<

p；（2）如果gcd(a,p)1，则p是合数，停止检测；（3）计算i=a(p-1)/2modp；（4）计算Jacobi符号J(a,p)；（5）如果iJ(a,p)，则p不是素数；（6）如果i=J(a,p)，则p不是素数的概率小于50%。◼对t个不同的随机数a，重复进行这个测试。能通过所有t

个测试的奇数是合数的概率小于1/2t。2.5.2Lehmann法◼测试p是否为素数：（1）选择一个小于p的随机数a；（2）计算a(p-1)/2modp；（3）如果a(p-1)/2modp1或－1(modp)，则p不是素数；（4）如果a(p-1)/2modp＝1或－1(modp

)，则p不是素数的概率小于50%。2.5.3强素数◼强素数p,q：能令乘积n难以用特定的因数分解算法进行因数分解的素数。◼性质：◼p-1和q－1的最大公因数很小◼p-1和q-1都有大素数因子，记为p’，q’；◼p’-1和q’-1都有大素数因子；◼p+1和q+1应该都有大素数因子；◼(p

-1)/2和(q-1)/2都是素数。◼例：n=3337=47*712.6有限域内的离散对数◼求x，使axb(modn)◼当n很大时，这是一个困难的问题◼并非所有的离散对数问题都有解◼密码学中常用的离散对数：◼GF(p)的乘法群◼GF(2

n)的乘法群◼有限域F上的椭园曲线群EC(F)2.7单向哈希函数◼定义：一个单向哈希函数H(M)，操作一个任意长度的消息M，返回一个固定长度的值h。h=H(M)。◼即：函数可以有任意长度的输入，返回一个固

定长度的输出。◼性质：◼给定M，很容易计算h；◼给定h，很难计算M，使H(M)=h；◼给定M，很难找到另一个消息M’，使H(M)=H(M’)。◼课后练习：◼1.求9关于模26的乘法逆元.◼2.求17关于模26的乘

法逆元.◼3.求9关于模29的乘法逆元.◼4.求4关于模35的乘法逆元.◼5.求3关于模26的乘法逆元.◼6.求11于模35的乘法逆元.◼7.求31关于模105的乘法逆元.◼8.求79关于模3220的乘法逆元.◼9.求9关于模10的

乘法逆元.◼10.求3关于模10的乘法逆元.◼11.求4关于模11的乘法逆元.◼12.求11关于模32的乘法逆元.◼答案◼1.37.61◼2.238.1019◼3.139.9◼4.910.7◼5.911.3◼6.1612.3