网络安全教程 教学课件 田园 第8章 计算机密码学概要.pptVIP

第8章 计算机密码学概要 ;8.1 一些必要的数论知识 ;8.1.1 Euclid定理及线性同余式; 存在多项式算法A，任给整数a和b，由A计算出整数q和r满足a=bq+r及0≤rb，且A的计算复杂度不超过max（|a|3,|b|3）。 尽管看似平凡，但实际上Euclid定理的几个等价形式有着广泛的应用。第一个等价形式是以下定理。 任给整数a和b，总存在整数x和y（但不唯一）满足 ax+by=（a,b）。 Euclid定理的第二个等价形式正是关于线性同余式可解性的命题。 任给整数N、a和b，线性同余式ax=b mod N存在整数解x当且仅当（a,N）|b，且这时恰有（a,N）个解x且0≤xN。 特别地，若a、N互素则ax=b mod N总存在且有唯一的整数解x且0≤xN。;8.1.2 中国剩余定理; 中国剩余定理断言，以上问题的解存在而且在区间[0,M-1]上唯一，不仅如此，这一定理实际上还给出了对x的精确的求解公式： X= 其中Mi=m1…mi-1mi+1…mn, MiNi=1 mod mi。;8.1.3 Fermat 定理和Euler定理; 对任何正整数N，Euler函数有以下规律 φ(N1N2)=φ(N1)φ(N2)，其中N1、N2互素； φ(pm)=pm?pm?1，其中p是素数、m是正整数。 回到Euler定理，它陈述的事实是。 若整数a、N互素，则必有aφ(N)=1 mod N。 ;8.1.4 交换群的概念和密码学中常见的例子; x*y=y*x，称为交换性。 (x*y) *z=x* (y*z)，称为结合性。 存在一个元素e使x*e=e*x=x对任何x都成立，这称为单位性，元素e称做单位元素。 对任何x都存在一个元素，记做x?1，满足x*x?1=x?1*x=e，这称为可逆性。 G的元素个数称做群的阶，记号为|G|。下面是密码学中常用的群。; （1）N是正整数，Z*N≡{1≤a≤N?1：a与N互素}，+和*分别表示Z*N上的模N加法和模N乘法，于是（Z*N, *）是群（为什么？），单位元素是1，群的阶是Euler函数φ(N)，特别地，若p是素数则（Z*p,*）是p?1阶群。。 （2）N是正整数，QRN≡{1≤a≤N?1：二次同余式x2= a mod N有解}，*表示QRN上模N乘法，（QR*N, *）是群，群的单位元素是1。; （3）p是素数，Fp≡{0,1,…,p?1}、F* p≡Fp\{0}，在Fp上定义模p的加法运算+，在F*p上定义模p的乘法运算*，于是（F*p,*）和（Fp,+）都是群，阶分别为p?1和p（为什么？）。 （4）设Fq是有限域、阶为q，A、B∈Fq是给定的常数，Fq上的椭圆曲线E/Fq是集合{(x,y): y2=x3+Ax+B}，在E/Fq上可以定义点的一种运算“+”使(x1,y1)+(x2,y2)=(x3,y3)。; 设G是一个有限群，N是G的阶，e是G的单位元素，Lagrange定理断言，对G的任何元素a必有aN=e。 设G是一个有限群，N是G的阶，e是G的单位元素。 对G的任何元素a，a的阶定义为使ad=e的最小正整数d。 d一定整除N。 群有许多具体类型，在密码学中至今应用最多的都是最简单的一类，即循环群。 G定义为循环群，如果存在元素g0使任何非单位元素g∈G，都存在整数m使g=g0m，g0称为G的生成子。; 关于群的另一重要概念是子群：H是G的子集，如果G上的群运算应用于H的元素恰使H也是一个群，则H定义为G的子群。 关于子群的一个重要规律也是Lagrange发现的，也称为Lagrange定理：子群H的阶必整除G的阶。;.1.5* 二次剩余及二次同余式x2=a mod p在特殊情况下的解; 二次剩余理论中最深刻的结论之一是Gauss-Euler-Legend互反律。首先定义Legend符号：对素数p及与之互素的整数a，（a/p）=+1表示a是p的二次剩余，即存在x满足方程x2=a mod p；（a/p）= ?1表示a是p的非二次剩余，即方程x2=a mod p无解；对p|a的情形，约定（a/p）=0。Legend符号有以下性质。 ;（1）（ab/p）=（a/p）（b/p） （2）（2/p），a为奇数则（a/p）=a(p?1)/2 mod p （3）（p/q）（q/p）=(?1)(p?1)(q?1)/4（Gauss-Euler-Legend互反律）;;;;8.2 消息认证与数字签名方案; 消息认证方案（Message Authentication Scheme）用于保证数据一