计算机安全保密第二讲

计算机安全保密第二讲

密码学数学基础唐明武汉大学计算机学院本次课的内容2.1信息论2.2复杂性理论2.3初等数论2.4因数分解2.5素数的产生2.6有限域内的离散对数2.7单向哈希函数2.1信息论2.1.1熵与疑义度2.1.2自然语言率2.1.3密码系统的安全性2.1.4确定性距离2.1.5混乱与扩散2.1.1熵与疑义度1949年，Shannon发表“CommunicationTheoryofSecrecySystems”

一条消息中的信息量，形式上由该消息的熵来度量。

一、自信息和熵1、自信息

文字、图象、声音是消息，信息是消息的有价值内容。①给定一离散事件集X，它含有N个事件x1,x2,…,xN，事件xi出现的概率记作pi，1≥pi≥0且

②自信息定义定义事件xi的自信息，记作I(xi),定义为

注意：自信息的定义没有规定对数的底！对数底为2时，自信息单位为比特（bit）；对数底取为e时，自信息单位为奈特（nat）；对数底为10时，自信息单位为哈特（hart）。

离散随机事件概率对数值的绝对值。

③自信息的含义自信息度量了一个随机事件xi未出现时所呈现的不确定性，也度量了该事件xi出现后所给出的信息量。

事件的不确定性越大，则一旦出现给出的信息量也就越大。④举例例计算从英文字母表中任选一个字母时所给出的自信息量。因为从26个字母中任取一个字母的概率为，所以任选一个字母所给出的信息量为

一、自信息和熵2、熵自信息描述了事件集X中一个事件出现给出的信息量，整个集X的平均信息量是该集所有事件自信息的统计平均值（数学期望），称作集X的熵。

定义2.2集X的熵，记作H(X)，定义为定义中，规定0log0=0。H（X）度量了集X中各个事件未出现时所呈现的平均不确定性(疑义度)，也度量了集X中一个事件出现时所给出的平均信息量。

疑义度：消息的熵同时也可衡量其不确定性（疑义度），即将消息隐藏在密文中时，要破译它所需的明文比特数（即当消息被加密成密文时，为了获取明文需要解密的明文的位数）。

一、自信息和熵2、熵举例例给出集按定义有:I(x1)=-log21/2=log22=1比特，I（x2）=I（x3）=-log21/4=log24=2比特。于是一个事件集的熵越大，其不确定性越高。。比特。关于熵的实际例子例：X可能在下周某天去钓鱼。星期一，……，星期日共有七种可能（x1，…，x7），假设各种可能性出现概率相等，则：P（Xi）=1/7，H（x）=－7·(1/7)·log21/7=－log21/7=log27同时，H（x）也指出了X中的信息量将消息中所有可能的值进行编码时所需的最少比特数。2<H(x)=log27<3b1b2b3可以表示一周的7个状态：000星期日001星期一……110

星期六保留

关于熵熵的实实际例例子甲任意意取一一个不不超过过15的整数数，由由乙来来猜，，但允允许乙乙提K个问题题，甲甲只回回答““是””或者者“非非”，，问K多大时时可以以确定定猜到到该数数。解：若若令乙乙猜想想作为为事件件V，V可能有有16种结果果，假假定这这16种结果果是等等概率率的，，V的熵为为：H（V）=log216令事件件Ak=U1U2U3…Uk为提问问k个问题题，但但Ui的熵不不超过过log22=1，（因为只只有““是””或者者“非非”）），故故Ak的熵为为不超超过k比特，，则：：log216k·log22=k，k4故k=4继续前前面的的例子子0到15之之间的的数可可以由由4比比特信信息来来表示示。即即—————————————而上面面的问问题实实际上上可以以转化化为如如何获获得这这4个个比特特信息息。因因为每每个问问题的的答案案只有有两种种，故故每个个问题题的答答案最最多只只能提提供1比特特的信信息。。因而如如果要要确保保得到到正确确结果果，则则至少少需要要4次次。那如何何保证证每次次可以以获得得1位位的信信息呢呢？最直接接的四四个问问题：：这个数数被表表示为为四位位二进进制后后，第第一位位是0吗？？这个数数被表表示为为四位位二进进制后后，第第二位位是0吗？？……这样，，我们们可以以确保保每次次都可可以得得到一一位信信息。。思考？？假设乙乙的第第一个个问题题是““这个个数字字是a吗？””其中a是0-15之间间的任任意一一个确确定的的数。。如果乙乙得到到“是是”的的回答答，请请问该该事件件提供供的信信息量量是多多少？？如果果乙乙得得到到““否否””的的回回答答，，请请问问乙乙是是否否还还能能够够确确保保在在规规定定次次数数之之内内得得到到正正确确结结果果？？为为什什么么？？思考考？？假设设乙乙的的第第一一个个问问题题是是““这这个个数数字字大大于于11吗吗？？””如果果乙乙得得到到““是是””的的回回答答，，请请问问该该事事件件提提供供的的信信息息量量是是多多少少？？如果果乙乙得得到到““否否””的的回回答答，，请请问问乙乙是是否否还还能能够够确确保保在在规规定定次次数数之之内内得得到到正正确确结结果果？？为为什什么么？？关于于熵熵的的实实际际例例子子有25个外外表表完完全全相相同同的的硬硬币币，，其其中中24个重重量量完完全全一一样样，，有有一一个个较较轻轻的的伪伪币币，，用用无无砝砝码码的的天天平平，，试试问问要要做做多多少少次次的的比比较较，，可可以以找找到到这这枚枚伪伪币币？？继续续前前面面的的例例子子解：：事事件件V为找找出出伪伪币币，，可可能能有有25个个结结论论，，他他们们是是等等概概率率，，故故：：H（（V））=log225，，事件件U为天天平平称称的的结结果果，，可可能能有有3种种情情况况：：1.左左右右平平衡衡；；2.左左边边重重；；3.右右边边重重；；故故：：H（（U））=log23令Ak=U1U2U3…Uk为连连续续用用k次天天平平的的事事件件，，k··log23log225k（log225））/log23=2.93故k最少少为为3次次继续续前前面面的的例例子子一种种解解决决方方案案：：25=8+8+9（（第第一一次次））天平平两两端端各各放放8个个，，如如果果平平衡衡，，则则伪伪币币在在剩剩余余的的9个个之之中中，，跳跳到到ii；；如果果不不平平衡衡，，则则伪伪币币在在较较轻轻的的8个个之之中中，，跳跳到到iii。。9=3+3+3（（第第二二次次））天平平两两端端各各放放3个个，，如如果果平平衡衡，，则则从从剩剩下下3个个中中寻寻找找伪伪币币。。否否则则，，从从较较轻轻的的3个个中中寻寻找找伪伪币币。。8=3+3+2（（第第二二次次））天平平两两端端各各放放3个个，，如如果果平平衡衡，，则则从从剩剩下下2个个中中寻寻找找伪伪币币。。否否则则，，从从较较轻轻的的3个个中中寻寻找找伪伪币币。。思考考？？有25个个外外表表完完全全相相同同的的硬硬币币，，其其中中24个个重重量量完完全全一一样样，，伪伪币币重重量量不不一一样样，，但但不不知知是是轻轻还还是是重重，，用用无无砝砝码码的的天天平平，，试试问问要要做做多多少少次次的的比比较较，，可可以以找找到到这这枚枚伪伪币币？？2.1.2自自然然语语言言率率自然然语语言言率率：：对对于于给给定定的的一一种种语语言言，，其其自自然然语语言言率率为为r=H(M)/N其中N为消息长长度。英语的自自然语言言率：1.0比比特/字字母～1.5比比特/字字母它是一个个语言系系统的实实际表现现力，实实际上是是一个语语言系统统的实际际熵。绝对语言言率绝对语言言率：每每个字符符编码的的最大比比特数，，这里假假设每个个字符序序列出现现的机会会相等。。若语言中中有L个字母，，则绝对对语言率率为：R=log2L为单个字字母的最最大熵。。英语的绝绝对语言言率：log2264.7比特/字字母它是一个个语言系系统理论论上的最最大表现现力。当当每个字字符出现现的概率率相同时时，其具具有最大大表现力力。实际际上是语语言系统统的最大大熵。冗余度：：语言的的冗余度度记为D，定义为：：D=R-r其中，R为绝对语语言率，，r为自然语语言率。。英语：r=1.3比特/字字母，则则D=3.4比特/字字母。2.1.3密密码系统统的安全全性绝对安全全的密码码系统：：M：明文空间间；K：密钥空间间；C：密文空间间；c=E(m,k)。E：：M→→C。。H(M),H(K)绝对保密密的密码码系统的的必要条条件：H(K)>H(M)卢开澄，，计算机机密码学学，清华华大学出出版社。。即：一次次一密（（密钥与与消息本本身一样样长，且且密钥不不重复使使用）系系统。密码系统统的熵：：衡量密密钥空间间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增大时，，复杂性性函数中中增加得得最快的的一项。。多项式时时间算法法：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为整数数，则则ab（modn）amodn：a模n操作，，表示示a除以n的余数数，为为0到n－1之间的的整数数。例如：：(7＋9)mod12=16mod12=4模运算算（+、－－、）满足足交换换律、、结合合律和和分配配律。。(a+b)modn=((amodn)+(bmodn))modn(a-b)modn=((amodn)-(bmodn))modn(a*b)modn=((amodn)*(bmodn))modn(a*(b+c))modn=((a*bmodn)+(a*cmodn))modn按模计计算原原理：：对中中间结结果作作模运运算与与做完完了全全部运运算后后再做做模运运算结结果相相同。。求:1711mod26=?按模指指数运运算：：ammodn将指数数运算算作为为一系系列乘乘法运运算，，每次次做一一次模模运算算。例：a8modn=((a2modn)2modn)2modn当m不是2的乘乘方时时，将将m表示成成2的的乘方方和的的形式式。例如：：25=(11001)2，即25=24+23+20a25modn=(a16a8a)modn=((((a2)2)2)2((a2)2)2a)modn=((((a2a)2)2)2a)modn适当存存储中中间结结果，，则只只需6次乘乘法：：(((((((a2modn)a)modn)2modn)2modn)2modn)a)modn求1711mod26=?2.3.2素素数素数（（质数数）：：大于于1的的整数数，只只能被被1和和本身身整除除。有无穷穷多个个素数数。如：2，73，，2521，2365347734339，2756839-12.3.3最最大公公因数数公因数数：两两个整整数a，b的公因因数定定义为为能同同时整整除a，b的所有有整数数。最大公公因数数：a与b的公因因数中中能被被所有有a，b的公因因数整整除的的正整整数，，记为为gcd(a，b)。互素（（互质质）：：两个个整数数称为为互素素的，，如果果它们们除了了1以以外没没有其其他的的公因因数，，即gcd(a,b)=1。最大公公因数数的求求法：：辗转转相除除法即即Euclid算法例如：：求gcd(15,36)36=152+615=62+36=32+0因此，，gcd(15,36)=3原理：：若ab(modc)，则gcd(a,c)=gcd(b,c)这里，，gcd(15,36)=gcd(15,6)=gcd(6,3)=3理论基基础:若a=b·q+r，则gcd（a,b）=gcd（（b,r））定理：：若a=b·q+r，则gcd（a,b）=gcd（（b,r））那么：：gcd（a,b）=gcd(b,amodb)untilamodb=0thenbistheresult.证明：：d=（（a,b）），d’=（b,r）d|(a––bq)d|r，d为b,r的公因因数；；d|d’d’=h··dd’|(b·q+r)d’|a，，d’’为a,b的公因因数；；d’|dd=k·d’所以k·h=1,由于d,d’都为正正整数数，所所以k和h也都为为正整整数，，故：：k=h=1；2.3.4乘乘法逆逆元素素定理：：axbmodn有解的的充要要条件件是d|b，其中d=gcd（a，n）。。我们关关心下下列同同余式式：（（b=1时）当b=1时，d=1，即可得得：如果gcd(a,n)=1，，则ax1modn有解。。如果ax1modn有解，，则gcd(a,n)=1。。2.3.4乘乘法逆逆元素素求x，满足(a·x)modn=1,即xa-1(modn)当a与n互素时时,方方程程xa-1(modn)有唯一一解；；当a与n不互素素时,此此方程程无解。如果n为素数，则则从1到n-1的任意整数数都与n互素，即在在1到n-1之间都恰好好有一个关关于模n的乘法逆元元。求乘法逆元元：扩展的的Euclid算法例：求5关关于模14的乘法逆逆元素辗转相除：：14=52+45=4+1逆推：1=5-4=5-（14-52）=53-14因此，5关关于模14的乘法逆逆元为3。。练习练习：求17关于模模26的乘乘法逆元素素。答案：2326=17+91=9-817=9+8=9-(17-9)9=8+1=92-17=(26-17)2-17=262-173=17(-3)+262(1723-2615)2.3.5Fermat小小定理及欧欧拉函数Fermat小定理：如如果m为素数，a不能被m整除，则am-11(modm)n为正整数，，Zn={0，1，2，……，n-1}为模n的集合，Zn为模n的完全剩余余集。Zn*={aZn|gcd(a,n)=1}称为模n的简化剩余余集。（n）=|Zn*|,表示Zn*元素的个数数。称为欧拉函函数,（n）为n的欧拉函数数值。如果n是素数，则则(n)=n-1设n=p1r1p2r2…pmrm,其中p1,p2,…,pm是n的素数因子子,则(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)=(n/(p1p2…pm))(p1-1)(p2-1)……(pm-1)(8)=？？如果果n=pq，其中中p和q为素素数数，，则则Φ(n)=(p––1)(q––1)。例：：n=15,求(15).解：：Zn={0，，1，，2，，3，，4，，……，，14}Zn*={1，，2，，4，，7，，8，，11，，13，，14}，，因此此(15)=8[15=3*5（15）=(3-1)*(5-1)=8]欧拉拉扩扩展展的的Fermat小小定定理理欧拉拉扩扩展展的的Fermat小定定理理：：如果果gcd(a,n)=1，，则a(n)modn=1。。即：：如果果gcd(a,n)=1，，则a*a(n)-1modn=1即a关于于modn的乘乘法法逆逆元元素素为为a(n)-1再求求：：17关关于于模模26的的乘乘法法逆逆元元素素？？中国国剩剩余余定定理理--韩韩信信点点兵兵秦朝朝末末年年，，楚楚汉汉相相争争。。一一次次，，韩韩信信将将1500名名将将士士与与楚楚王王大大将将李李锋锋交交战战。。苦苦战战一一场场，，楚楚军军不不敌敌，，败败退退回回营营，，汉汉军军也也死死伤伤四四五五百百人人，，于于是是韩韩信信整整顿顿兵兵马马也也返返回回大大本本营营。。当当行行至至一一山山坡坡，，忽忽有有后后军军来来报报，，说说有有楚楚军军骑骑兵兵追追来来。。只只见见远远方方尘尘土土飞飞扬扬，，杀杀声声震震天天。。汉汉军军本本来来已已十十分分疲疲惫惫，，这这时时队队伍伍大大哗哗。。韩韩信信兵兵马马到到坡坡顶顶，，见见来来敌敌不不足足五五百百骑骑，，便便急急速速点点兵兵迎迎敌敌。。他他命命令令士士兵兵3人人一一排排，，结结果果多多出出2名名；；接接着着命命令令士士兵兵5人人一一排排，，结结果果多多出出3名名；；他他又又命命令令士士兵兵7人人一一排排，，结结果果又又多多出出2名名。。韩韩信信马马上上向向将将士士们们宣宣布布：：我我军军有有1073名名勇勇士士，，敌敌人人不不足足五五百百，，我我们们居居高高临临下下，，以以众众击击寡寡，，一一定定能能打打败败敌敌人人。。汉汉军军本本来来就就信信服服自自己己的的统统帅帅，，这这一一来来更更相相信信韩韩信信是是““神神仙仙下下凡凡””、、““神神机机妙妙算算””。。于于是是士士气气大大振振。。一一时时间间旌旌旗旗摇摇动动，，鼓鼓声声喧喧天天，，汉汉军军步步步步进进逼逼，，楚楚军军乱乱作作一一团团。。交交战战不不久久，，楚楚军军大大败败而而逃逃。。我国古代数学学名著《孙子子算经》中，，提出了闻名名于世的“物物不知数”问问题。原文是是：“今有物不知知其数，三三三数之剩二，，五五数之剩剩三，七七数数之剩二。问问物几何？””这个问题的解解法(Ⅰ)“笨”算法原来的问题题题意是：求一一数，三除余余二，五除余余三，七除余余二。因为以3除余2，以7除余2的数，所以以以21除也余2而23是以3，7除余2的最小数，它它刚好又是以以5除余3的数。(Ⅱ)古代的口诀解解法程大位著的《《算法统宗》》，对“物不不知其数”的的问题的解答答方法用下面面的口诀标出出：“三人同行七七十稀，五树树梅花廿一枝枝，七子团圆正半半月，除百零零五便得知。。”“三人同行七七十稀，五树树梅花廿一枝枝，七子团圆正半半月，除百零零五便得知。。”它的意义是：：以70乘用3除的余数2，21乘用5除的余数3，15乘用7除的余数2，然后总加起起来。如果它它大于105，则减105，若仍大再减减，……最后后得出来的正正整数就是答答案了。它的形式是：：2×70＋3×21＋2×15=233，两次减去105，得23，这就是答案案了。70，21，，15的性质质70是用3除除余1，5与与7都除得尽尽的数，所以以70a是一个用3除除余a而5与7除都都除得尽的数数。21是用5除除余1，3与与7除得尽的的数，所以21b是用5除余b，而3与7除得得尽的数。同理，15c是用7除余c而3与5除得得尽的数。因而：70a＋21b＋＋15c是一个3除余a，5除余b，7除余c的数，也就是是可能的解答答之一，但可可能不是最小小的。这数加加减105后都仍然有同同样的性质，，所以可以多多次减去105而得到答案。。“三人同行七七十稀，五树树梅花廿一枝枝，七子团圆圆正半月，除除百零五便得得知”。用现现代术语翻译译，其口诀实实际上是：N=70r1＋21r2＋15r3-105p，，其中ri(i=1，2，3)分别是余数，，p是使N＞0的任一整数。。推广开来若某数N分别被称为定定母的d1，d2，d3，…，dn除得的余数为为r1，r2，r3，…，rn，则N=k1r1＋k2r2＋k3r3＋…＋knrn-pq，其中k1是d2，d3，d4，…，dn的公倍数，且且被d1除余1；k2是d1，d3，d4，…，dn的公倍数，且且被d2除余1；…kn是d1，d2，d3，…，dn-1的公倍数，且且被dn除余1．p是任意整数，，q是d1，d2，d3，…，dn的最小公倍数数。上式的关键在在于“求一””，即求“一一个数的多少少倍除以另一一数，所得余余数为1”的的方法，也即即求出公式中中的“ki”．这个方法的研研究，是由我我国宋代著名名数学家秦九九韶(约1202～1261)在其其名著《数书书九章》一书书中完满解决决的。他把它它称作“大衍衍求一术”。。类似的理论成成果，在欧洲洲直到18，，19世纪才才由著名数学学家欧拉和高高斯获得，最最早出现在高高斯1801年出版的《《算术研究》》一书里。而而这，已是秦秦九韶之后500多年的的事了。因而，上述成成果被称为““中国剩余定定理”，或““孙子定理””。思考?“今有物不知知其数，三三三数之剩二，，五五数之剩剩三，七七数数之剩四。问问物几何？””（70*2+21*3+15*4））mod3*5*7=?=532.3.6中中国剩余定定理定理：如果n的素数因子分分解式为p1p2…pt，则一组方程(xmodpi）=ai，其中i=1,2,…,t，有唯一解x，其中x小于n（其中某些pi可能相等）。。例：今有物不不知其数，三三三数之剩二二，五五数之之剩三，七七七数之剩二，，问物几何？？xmod3=2xmod5=3xmod7=2定理：令d1，d2，…,dt为两两互素，，并令n=d1d2…dt，则xmoddixi(I=1,……,t)在[0，n-1]范围内有公共共解x：x=modn其中：mi=n/di，yi=mi-1moddi解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1p2p3=105，M1=n/p1=35,M2=n/p2=21,M3=n/p3=15求解35·x1mod3=1,得x1=2求解21·x2mod5=1,得x2=1求解15·x3mod3=1,得x3=1则x=(M1·x1·a1+M2·x2·a2+M3·x3·a3)modn=(3522+2113+1512)mod105=233mod105=232.3.7二二次剩余定义：：设整整数n>1。对于aZn*，如果存存在xZn，满足足x2≡a（modn）有解，，则称称a为模n的二次次剩余余（或或平方方剩余余）；；否否则，，称a为模n二次非非剩余余（或或平方方非剩剩余））。用QRn表示模模n的二次次剩余余集合合，用用QNRn表示模模n的二次次非剩剩余集集合。。例如：：32≡2（mod7），则2QR7求QR7=？QNR7=？2.3.8Legendre（（勒让让德））符号号记为L(a,p)，叫做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(1,7)=？？L(2,7)=？？L(3,7)=？？L(4,7)=？？L(5,7)=？？L(6,7)=？？2.3.9Jacobi（（雅各各比））符号号记为J(a,n)，是Legendre符号的的扩展展，其其中a为任意意整数数，而而n为任意意奇数数。定义：：J(a,n)只对n为奇数数时有有意义义J(0,n)=0如果n为素数数，且且n|a，则J(a,n)=0如果n为素数数，且且a是模n的二次次剩余余，则则J(a,n)=1如果n为素数数，且且a是模n的非二二次剩剩余，，则J(a,n)=-1如果n是合数数，则则J(a,n)=J(a,p1)×J(a,p2)×……×J(a,pm)，其中将将n因数分分解为为p1×p2×…×pmJacobi符号的的计算算（P19）Blum整数：：若p和q为两个个素数数，且且都与与3模模4同同余，，则n=pq称为Blum整数。。若n为Blum整数，，则每每个模模n的二次次剩余余恰好好有4个平平方根根，其其中一一个也也是一一个二二次剩剩余，，称为为原平平方根根。例如，，139的的模437的原原平方方根为为24，另另三个个平方方根为为185，，252和和413。。2.3.10生生成成元定义：：如果果p为素数数，g小于p，如果对对每个个b从1到到p-1，，存在a，使gab(modp)，则g为模p的生成成元。。或者说说g是关于于模p的原根。例：p=11，2为模11的的生成成元P20生成元元的测测试测试一一个数数是否否为生生成元元不太容容易。。如果果知道道p––1的因数数分解解式，，就很很容易易。令q1，q2，…，，qn为p––1的素数数因子子，且且q1，q2，…，，qn两两不不同，，则测测试给给定数数g是否为为p的生成成元时时，对对所有有的q=q1，q2，…，，qn计算g（p-1）/qmodp若对某某个q值，g（p-1）/qmodp为1，则g不是生生成元元。反反之，，则是是生成成元。。生成元元的测测试测试3是否否为模模11的生生成元元.测试如如下：：即p=11，，则p-1=10=2*5g（p-1）/qmodp=？3（11-1）/2mod11=13（11-1）/5mod11=9所以3不是是模11的的生成成元。。伽罗瓦瓦Galois,Evariste（（1811--1832））Galois（伽罗瓦瓦）一一共参参加了了2次次EcolePolytechnique（巴黎理工大大学）的考考试第一次，由由于口试的的时候不愿愿意做解释释，并且显显得无理，，结果被据据了。他当当时大概十十七八岁，，年轻气盛盛，大部分分东西的论论证都是马马马虎虎，，一般懒的的写清楚,并且拒绝绝采取考官官给的建议议。第二次口试试的时候，，逻辑上的的跳跃使考考官Dinet感到困惑，，后来Galois感觉很不好好，一怒之之下，把黑黑板擦掷向向Dinet,并且直接命命中。最后和Galois决斗的那个个人，是当当时法国最最好的枪手手，Galois的勇气令人人钦佩。两两个人决斗斗的时候，，相距25步，Galois被击中了腹腹部。伽罗瓦(EvaristeGalois)1811年10月25日生于于巴黎附近近的一个小小城。1829年年他两次投投考巴黎理理工大学，，却因思想想激进，两两次被拒绝绝录取，最最后只好进进入高等师师范学校学学习。1829年年5月，17岁的他他写出了关关于五次方方程的代数数解法的论论文，论文文中首次引引入“群””的概念。。他把论文文寄给柯西西，请他交交给法兰西西科学院审审查。柯西西对此根本本不屑一顾顾，把这个个中学生的的文章给弄弄丢了。1830年年2月伽罗罗瓦再次将将他的研究究成果写成成一篇详细细的论文，，寄给科学学院秘书傅傅立叶，希希望能得到到数学大奖奖，不料当当年5月傅傅立叶病死死，伽罗瓦瓦的文稿再再次被丢失失。1831年年伽罗瓦第第三次将论论文送交法法国科学院院。泊松院院士看了4个月，最最后在论文文上批道：：“完全无无法理解””。泊松的的不公正评评价，使他他受到很大大打击。这些大数学学家的傲慢慢和自大，，使得伽罗罗瓦的理论论被埋没了了将近50年。伽罗瓦因为为政治激进进，被阴谋谋的政客们们用一件小小事怂恿和和一个军官官决斗。在在决斗前一一个晚上，，他急切地地写着他的的遗言。想在死亡来来临之前尽尽快把他的的思想中那那些有意义义的东西写写出来。他他不时中断断，在纸边边空白处写写上“我没没有时间，，我没有时时间。”接着伽罗瓦瓦又写下一一个潦草的的大纲。他在天亮之之前那最后后几个小时时写出的东东西，一劳劳永逸地给给一个折磨磨了数学家家几个世纪纪的难题找找到了真正正的答案，，开创了数数学上的一一个重要的的分支――――群论。。伽罗瓦在决决斗中被打打成重伤，，死在家里里，年仅21岁。１８４６年年，也就是是伽罗瓦死死后１４年年，他的遗遗稿才得以以发表。随随着数学的的发展和时时间的推移移，伽罗瓦瓦研究成果果的重要意意义愈来愈愈为人们所所认识。他的最主要要成就是提提出了群的的概念，用用群论彻底底解决了根根式求解代代数方程的的问题，而而且由此发发展了一整整套关于群群和域的理理论，为了了纪念他，，人们称之之为伽罗瓦瓦理论。伽伽罗瓦理论论对近代数数学的发展展产生了深深远影响，，它已渗透透到数学的的很多分支支中。2.3.11有限限域中的计计算有限域：元元素个数有有限的域，，也叫伽罗罗瓦（Galois）域。在有限域中中，非0数数的加、减减、乘、除除都有定义义。加法单单位元是0，乘法单单位元是1，每个非非0元素都都有一个唯唯一的乘法法逆元。有限域中运运算满足交交换律、结结合律和分分配律。有限域中元元素个数为为素数或素素数的乘方方：设p为素数，则则有限域可可记为GF(p)或GF(pn)。不可约多项项式：一个个多项式如如果除了1和本身外外，不能分分解成其他他多项式的的乘积形式式，则成为为不可约多多项式。本原多项式式：一个有有限域内的的生成元多多项式，其其系数是互互素的。在GF(qn)中，所有运运算都是模模p(x)的运算，其其中p(x)是n阶不可约多多项式。一般研究GF（2n），如GF（25）：a(x)=x4+x3+1表示11001。若p（x）不能分解为为次数小于于n的多项式之之积，则p（x）称既约多项项式。二元多项式式系数的运运算：（U+V））mod2=UVU－V=UVU·V=UV例：GF（25）：a(x)=x4+x2+1,b(x)=x3+x2a＋b=10101+01100=11001例：a=101，p（x）=x³³+x+1，GF（（2³），，求（aa）modp（x）aa=10001，p（x）=x³+x+1=1011（aa）modp（x）=10001mod1011=111=x²²+x+12.4因因数分解对一个数进进行因数分分解，是指指找出这个个数的素数数因子。60=2*2*3*5252601=41*61*1012113-1=3391*23279*……现代因数分分解的一些些算法P212.5素素数的产生生2.5.1Solovay-Strassen方法2.5.2Lehmann法2.5.3Rabin-Miller法2.5.4实际应应用2.5.5强素数数2.5.1Solovay-Strassen方法用Jacobi符号来测试试p是否为素数数：（1）选择择一个随机机数a，a<p；（2）如果gcd(a,p)1，则p是合数，停停止检测；；（3）计算算i=a(p-1)/2modp；=L(a,p)?（4）计算Jacobi符号J(a,p)；（5）如果iJ(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)/2modp1或－1(modp)，则p不是素数；；（4）如果果a(p-1)/2modp＝1或－1(modp)，则p不是素数的的概率小于于50%。。2.5.3Rabin-Miller法选择一个随随机数p，进行测试。。计算b，其中b是能整除p-1的2的次方方数（即2b是指整除p-1的最大的2的幂），，然后计算算m，使得p=1+2b*m。（1）选择一个随随机数a，使a小于p；（2）令i=0，Z=ammodp；（3）如果Z=1，或Z=p-1，则p可能是素数数，通过了了检测；（4）如如果i>0，且Z=1，则p不是素数数；（5）令令i=i+1，如果i<b且Zp-1，令Z=Z2modp，返回第（（4）步步。如果果Z=p-1，则p通过检测测，可能能是素数数；（6）如如果i=b且Zp-1，则p不是素数。一个奇合数通通过t次测试的概率率小于1/4t。2.5.4实实际应用（1）产生一一个n位随机数p（n位二进制）；；（2）将最高高位和最低位位置为1；（3）检查p是否能被小素素数整除：3，5，7，，11，等等等。许多实际际应用中都用用小于256地所有素数数去除p；（4）对于随机数a，进行Rabin-Miller测试，如果p通过了，则产产生另一个随随机数a，再进行测试。。选择值小一一些的a可以令计算更更快。做5次次测试，如果果p没通过其中的的一次，则产产生另一个p再测试。2.5.5强强素数强素数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都是素数。2.6有限限域内的离散散对数求x，使axb(modn)当n很大时，这是是一个困难的的问题并非所有的离离散对数问题题都有解密码学中常用用的离散对数数：GF(p)的乘法群GF(2n)的乘法群EC(F)2.7单向向哈希函数定义：一个单单向哈希函数数H(M)，操作一个任意意长度的消息息M，返回一个固定定长度的值h。h=H(M)。性质：给定M，很容易计算h；给定h，很难计算M，使H(M)=h；给定M，很难找到另一一个消息M’，使H(M)=H(M’)。MD5算法(P27)输入：将明文文分成512位的块,再再将其分成16个32位位的子块M0…M15输出：4个32位的块（（a,b,c,d），将这四个32位分组级联联后将生成一一个128位位散列值。消息填充在md5算法中，首先先需要对信息息进行填充，，使其字节长长度对512求余的结果果等于448。因此，信息的的字节长度（（bitslength）将被扩展至n*512+448，即n*64+56个字节（bytes）），n为一个正整数数。填充方法：在在信息的后面面填充一个1和无数个0，直到满足足上面的条件件时才停止用用0对信息的的填充。然后后，在在这个个结果后面附附加一个以64位二进制制表示的填充充前信息长度度。经过这两步的的处理，现在在的信息字节节长度=n*512+448+64=(n+1)*512，即长度恰好是是512的整整数倍。这样做的原因因是为满足后后面处理中对对信息长度的的要求。md5中有四个32位被称作链链接变量（chainingvariable）的整数参数，，他们分别为为：A=0x01234567，B=0x89abcdef，，C=0xfedcba98，D=0x76543210。当设置好这四四个链接变量量后，就开始始进入算法的的四轮循环运运算。循环的的次数是信息息中512位位信息分组的的数目。将将上上面四个链接接变量复制到到另外四个变变量中：A到a，B到b，C到c，D到d。主循环有四轮轮（md4只有三轮），，每轮循环都都很相似。每每轮进行16次操作。每次操作对a、b、c和d中的其中三个个作一次非线线性函数运算算，然后将所所得结果加上上第四个变量量，文本的一一个子分组和和一个常数。。再将所得结结果向右环移移一个不定的的数，并加上上a、b、c或d中之一。最后后用该结果取取代a、b、c或d中之一。以下是每次操操作中用到的的四个非线性性函数（每轮轮一个）。f(x,y,z)=(x&y)|((~x)&z)g(x,y,z)=(x&z)|(y&(~z))h(x,y,z)=x^y^zi(x,y,z)=y^(x|(~z))（&是与，|是或或，~是非，，^是异或））每圈的操作函函数假设mj表示消息的第第j个子分组（从从0到15）），ff(a,b,c,d,mj,s,ti)用于第一圈表示a=b+(a+f(b,c,d)+mj+ti)<<s)gg(a,b,c,d,mj,s,ti)用于第二圈圈表示a=b+(a+g(b,c,d)+mj+ti)<<s)hh(a,b,c,d,mj,s,ti)用于第三圈圈表示a=b+(a+h(b,c,d)+mj+ti)<<s)ii(a,b,c,d,mj,s,ti)用于第四圈圈表示a=b+(a+i(b,c,d)+mj+ti)<<s)每圈的具体体操作P29其中在第i步中，ti是4294967296*abs(sin(i))的整数部分分，i的单位是弧弧度。(4294967296等于2的32次次方)如何计算？？1弧度=多少度？？T1=?T16=?T24=?T32=?我们把长度度等于半径径的弧所对对的圆心角角叫做1弧度的角。所有这些完完成之后，，将a、b、c、d分别加上a、b、c、d。然后用下一一分组数据据继续运行行算法，最最后的输出出是a、b、c和d的级联。参考P28图2.6验证自己的的函数正确确性md5("")=d41d8cd98f00b204e9800998ecf8427emd5("a")=0cc175b9c0f1b6a831c399e269772661

md5("abc")=900150983cd24fb0d6963f7d28e17f72md5("messagedigest")=f96b697d7cb7