現代密碼學第6章：公鑰密碼學.ppt

《現代密碼學第6章：公鑰密碼學.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在PPT專區(qū)-天天文庫。

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≡