安全与保密

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+20a25modn=(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以外没有其他的公因数，即gcd(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-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.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·x1mod2=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为素数，a0且ap，如果存在某个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-1Legendre符号的用途用Legendre符号来验证a是否是模p的二次剩余举例:验证：a=5是否是p=11的二次剩余？L(a,p)