现代密码学第6章：公钥密码学.ppt

《现代密码学第6章：公钥密码学.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、公钥密码《现代密码学》第6章1本章主要内容1、数论简介2、公钥密码体制的基本概念3、RSA算法4、背包密码体制5、Rabin密码体制6、椭圆曲线密码体制习题2数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。1.数论简介3数论介绍数论概念:研究“离散数字集合”运算是“+”,“×”例:整数:5+9=14;5×3=5+5+5=15多项式:x2+1+x=x2+x+1;x×x2+1=x3+x4运算概念运算:模数运算模多项式运算进一步运算:指数运算,逆运算理解公钥

2、算法的基础5整除对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子记作b

3、a例1,2,3,4,6,8,12,24整除2461.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b

4、a，且称b是a的因子。1.1素数和互素数7整数具有以下性质：①a

5、1，那么a=±1。②a

6、b且b

7、a，则a=±b。③对任一b(b≠0)，b

8、0。④b

9、g，b

10、h，则对任意整数m、n有b

11、(mg+nh)。1.1素数和互素数8这里只给出④的证明，其他3个性质的证明都很简单。性质④的证明：由b

12、g

13、，b

14、h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b

15、(mg+nh)。1.1素数和互素数92.素数称整数p(p>1)是素数，如果p的因子只有±1，±p。任一整数a(a>1)都能惟一地分解为以下形式：其中p1>p2>…pt是素数，ai>0(i=1,…,t)。例如91=7×11，11011=7×112×131.1素数和互素数10这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a>1)都能惟一地写成以下形式：其中ap≥0,等号右边的乘积

16、项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为{a7=1,a11=2,a13=1}。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=mp+np。而由a

17、b可得：对每一素数p,ap≤bp。这是因为pk只能被pj(j≤k)整除。1.1素数和互素数113.互素数称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。1.1素数和互素数12由于要求最大公因子为正，

18、所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(

19、a

20、,

21、b

22、)。由任一非0整数能整除0，可得gcd(a,0)=

23、a

24、。如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如：300=22×31×52；18=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。1.1素数和互素数13由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公

25、因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。1.1素数和互素数14整数互素整数a,b互素是指它们没有除1之外的其它因子8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子15素数与不可约多项式素数:只有因子1和自身1是一个平凡素数例2,3,5,7是素数,4,6,8,9,10不是素多项式或不可约多项式irreducible:不可写成其他因式的乘积x2+x=x×x+1是非不可约多项式;x3+x+1是不可约多项式16一些素数200以内的素数:2357111317192329313741434753

26、59616771737983899710110310710911312713113713914915115716316717317918119119319719917素数分解把整数n写成素数的成绩分解整数要比乘法困难整数n的素数分解是把它写素数的乘积eg.91=7×13;3600=24×32×5218设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤r

27、与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。注意：如果a≡0(modn)，则n

28、a。1.2模运算19同余有以下性质：①若n

29、(a-b)，则a≡bmodn。②(amodn)≡(bmodn)，则a≡bmodn。③a≡bmodn,则b≡