密码学第五章公钥密码试卷.ppt

第五章 公钥密码 公钥密码 数论简介 公钥密码体制的基本概念 RSA算法 椭圆曲线密码体制 数论简介 素数和互素数 因子 整数a,b,如果存在m，使a=mb，称为b整除a，记为b|a，称b是a的因子。 性质 a|1，则a=±1 a|b且b|a，则a=b 对任意b,b≠0，则b|0 b|g,b|h,对任意整数m,n,有b|(mg+nh) (证明留给大家) 素数和互素数 素数 整数p(p1)为素数，如果p的因子只有±1,±p 整数分解的唯一性 任一整数a(a1)可唯一的分解为 其中p1p2…pt是素数，ai0 例：91=7×11，11011=7×112×13 素数和互素数 整数分解唯一性的另一表示 P是所有素数的集合，任一a(a1)可表示为 ap≥0,大多数指数项ap为0，任一整数可由非0指数列表表示。例如11011可以表示为{a7=1, a11=2, a13=1} 两数相乘等价于对应的指数相加 由a|b可得，对每一素数p， ap ≤bp 素数和互素数 c是a和b的最大公因子，c=gcd(a,b) c是a的因子也是b的因子 a和b的任一公因子也是c的因子 gcd(a,b)=1,称为a,b互素 模运算 设n是一正整数,a是整数,若 a=qn+r, 0≤rn, 则a mod n=r 若(a mod n)=(b mod n),称为a,b模n同余，记为a≡b mod n 称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素 模运算 同余的性质 若n|(a-b)，则a≡b mod n (a mod n) ≡(b mod n),则a≡b mod n a≡b mod n，则b≡a mod n a≡b mod n， b≡c mod n，则a≡c mod n 求余运算a mod n将a映射到集合{0,1,…,n-1},求余运算称为模运算 模运算 模运算的性质 [(a mod n)+(b mod n)] mod n=(a+b) mod n [(a mod n)-(b mod n)] mod n=(a-b) mod n [(a mod n)×(b mod n)] mod n=(a×b) mod n 模运算 例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法 模运算 若x+y=0 mod n, y为x的加法逆元。每一元素都有加法逆元 若对x，有xy=1 mod n，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元 定义Zn={0,1,..,n-1}为模n的同余类集合。 模运算 Zn上模运算的性质 交换律 （x+w) mod n=(w+x) mod n (x×w) mod n=(w×x) mod n 结合律 [(x+w)+y] mod n=[x+(w+y)] mod n [(x×w) ×y] mod n=[x×(w×y)] mod n 分配律 [w×(x+y)] mod n=[w×x+w×y)] mod n 模运算 单位元 (0+w) mod n=w mod n (1×w) mod n=w mod n 加法逆元：对w∈Zn,有z∈Zn，满足w+z=0 mod n, z为w的加法逆元，记为z=-w。 加法的可约律 (a+b)≡(a+c) mod n, 则b≡c mod n 对乘法不一定成立，因为乘法逆元不一定存在。 模运算 定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元 证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1 mod n 设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律 (a×b)=(a×c) mod n, b=c mod n 费尔玛定理和欧拉定理 费尔玛定理 若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1 mod p 证明： gcd(a,p)=1,则a×Zp=Zp, a×(Zp-{0})=Zp-{0} {a mod p,2a mod p,…,(n-1)a mod p} ={0,1,…,p-1} (a mod p) ×(2a mod p) ×…×(n-1)a mod p=(p-1)! mod p (p-1)! ×ap-1=(p-1)! mod p (p-1)!与p互素，所以乘法可约律，ap-1=1 mod p 费尔玛定理和欧拉定理 欧拉函数 设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为j(n) 定理：若n是两个素数p和q的乘积，则j(n)＝ j(p) j(q)=(p-1)(q-1) 欧拉定理 若a和