現(xiàn)代密碼學(xué)第6章：公鑰密碼學(xué).ppt

《現(xiàn)代密碼學(xué)第6章：公鑰密碼學(xué).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、公鑰密碼《現(xiàn)代密碼學(xué)》第6章1本章主要內(nèi)容1、數(shù)論簡(jiǎn)介2、公鑰密碼體制的基本概念3、RSA算法4、背包密碼體制5、Rabin密碼體制6、橢圓曲線密碼體制習(xí)題2數(shù)論是密碼學(xué)特別是公鑰密碼學(xué)的基本工具，本章首先介紹密碼學(xué)中常用的一些數(shù)論知識(shí)，然后介紹公鑰密碼體制的基本概念和幾種重要算法。1.數(shù)論簡(jiǎn)介3數(shù)論介紹數(shù)論概念:研究“離散數(shù)字集合”運(yùn)算是“+”,“×”例:整數(shù):5+9=14;5×3=5+5+5=15多項(xiàng)式:x2+1+x=x2+x+1;x×x2+1=x3+x4運(yùn)算概念運(yùn)算:模數(shù)運(yùn)算模多項(xiàng)式運(yùn)算進(jìn)一步運(yùn)算:指數(shù)運(yùn)算,逆運(yùn)算理解公鑰

2、算法的基礎(chǔ)5整除對(duì)整數(shù)b!=0及a,如果存在整數(shù)m使得a=mb,稱b整除a,也稱b是a的因子記作b

3、a例1,2,3,4,6,8,12,24整除2461.因子設(shè)a，b(b≠0)是兩個(gè)整數(shù)，如果存在另一整數(shù)m，使得a=mb，則稱b整除a，記為b

4、a，且稱b是a的因子。1.1素?cái)?shù)和互素?cái)?shù)7整數(shù)具有以下性質(zhì)：①a

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

6、b且b

7、a，則a=±b。③對(duì)任一b(b≠0)，b

8、0。④b

9、g，b

10、h，則對(duì)任意整數(shù)m、n有b

11、(mg+nh)。1.1素?cái)?shù)和互素?cái)?shù)8這里只給出④的證明，其他3個(gè)性質(zhì)的證明都很簡(jiǎn)單。性質(zhì)④的證明：由b

12、g

13、，b

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

15、(mg+nh)。1.1素?cái)?shù)和互素?cái)?shù)92.素?cái)?shù)稱整數(shù)p(p>1)是素?cái)?shù)，如果p的因子只有±1，±p。任一整數(shù)a(a>1)都能惟一地分解為以下形式：其中p1>p2>…pt是素?cái)?shù)，ai>0(i=1,…,t)。例如91=7×11，11011=7×112×131.1素?cái)?shù)和互素?cái)?shù)10這一性質(zhì)稱為整數(shù)分解的惟一性，也可如下陳述：設(shè)P是所有素?cái)?shù)集合，則任意整數(shù)a(a>1)都能惟一地寫成以下形式：其中ap≥0,等號(hào)右邊的乘積

16、項(xiàng)取所有的素?cái)?shù)，然而大多指數(shù)項(xiàng)ap為0。相應(yīng)地，任一正整數(shù)也可由非0指數(shù)列表表示。例如：11011可表示為{a7=1,a11=2,a13=1}。兩數(shù)相乘等價(jià)于對(duì)應(yīng)的指數(shù)相加，即由k=mn可得：對(duì)每一素?cái)?shù)p,kp=mp+np。而由a

17、b可得：對(duì)每一素?cái)?shù)p,ap≤bp。這是因?yàn)閜k只能被pj(j≤k)整除。1.1素?cái)?shù)和互素?cái)?shù)113.互素?cái)?shù)稱c是兩個(gè)整數(shù)a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示為c=gcd(a,b)。1.1素?cái)?shù)和互素?cái)?shù)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整數(shù)能整除0，可得gcd(a,0)=

23、a

24、。如果將a，b都表示為素?cái)?shù)的乘積，則gcd(a,b)極易確定。例如：300=22×31×52；18=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得：對(duì)每一素?cái)?shù)p，cp=min(ap,bp)。1.1素?cái)?shù)和互素?cái)?shù)13由于確定大數(shù)的素因子不很容易，所以這種方法不能直接用于求兩個(gè)大數(shù)的最大公因子，如何求兩個(gè)大數(shù)的最大公

25、因子在下面介紹。如果gcd(a,b)=1，則稱a和b互素。1.1素?cái)?shù)和互素?cái)?shù)14整數(shù)互素整數(shù)a,b互素是指它們沒有除1之外的其它因子8與15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子15素?cái)?shù)與不可約多項(xiàng)式素?cái)?shù):只有因子1和自身1是一個(gè)平凡素?cái)?shù)例2,3,5,7是素?cái)?shù),4,6,8,9,10不是素多項(xiàng)式或不可約多項(xiàng)式irreducible:不可寫成其他因式的乘積x2+x=x×x+1是非不可約多項(xiàng)式;x3+x+1是不可約多項(xiàng)式16一些素?cái)?shù)200以內(nèi)的素?cái)?shù):2357111317192329313741434753

26、59616771737983899710110310710911312713113713914915115716316717317918119119319719917素?cái)?shù)分解把整數(shù)n寫成素?cái)?shù)的成績(jī)分解整數(shù)要比乘法困難整數(shù)n的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積eg.91=7×13;3600=24×32×5218設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，則a=qn+r,0≤r

27、與a模n同余的數(shù)的全體為a的同余類，記為[a]，稱a為這個(gè)同余類的表示元素。注意：如果a≡0(modn)，則n

28、a。1.2模運(yùn)算19同余有以下性質(zhì)：①若n

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