密碼學(xué)中常用數(shù)學(xué)知識(shí)綜述_第1頁
密碼學(xué)中常用數(shù)學(xué)知識(shí)綜述_第2頁
密碼學(xué)中常用數(shù)學(xué)知識(shí)綜述_第3頁
密碼學(xué)中常用數(shù)學(xué)知識(shí)綜述_第4頁
密碼學(xué)中常用數(shù)學(xué)知識(shí)綜述_第5頁
已閱讀5頁,還剩14頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、公鑰密碼 密碼學(xué)中常用的數(shù)學(xué)知識(shí) 公鑰密碼體制的基本概念 RSA算法4.1.1 群、環(huán)、域群、環(huán)、域群群G, 的定義的定義: u 一些數(shù)字組成的集合一些數(shù)字組成的集合 u 一個(gè)二元運(yùn)算,運(yùn)算結(jié)果屬于此集合(封閉性)一個(gè)二元運(yùn)算,運(yùn)算結(jié)果屬于此集合(封閉性)u 服從結(jié)合律。有單位元,逆元服從結(jié)合律。有單位元,逆元 。u 如果是可交換的,則成為如果是可交換的,則成為Abel群群*為乘法時(shí),稱為乘法群為乘法時(shí),稱為乘法群 逆元(逆元(a-1)*為加法時(shí),稱為加法群為加法時(shí),稱為加法群 逆元(逆元(-a)環(huán)環(huán)的定義的定義: u Abel 群,及一個(gè)乘法運(yùn)算:群,及一個(gè)乘法運(yùn)算:u 滿足結(jié)合律與滿足結(jié)合

2、律與加法的分配律加法的分配律 u 如果加法滿足交換律如果加法滿足交換律, 則稱交換環(huán)則稱交換環(huán)u 例:整數(shù)例:整數(shù) mod N (for any N )域域的定義:的定義: u是是Abel加群加群 u環(huán)環(huán) u是是Abel 乘群乘群 u例:例: 整數(shù)整數(shù) mod P ( P 為素?cái)?shù))為素?cái)?shù))Galois 域:域:u 如果如果 n是素?cái)?shù)是素?cái)?shù) p ,則模運(yùn)算,則模運(yùn)算modulo p 形成形成 Galois Field modulo p u 記為:記為: GF(p) 4.1.2 素?cái)?shù)和互素?cái)?shù)素?cái)?shù)和互素?cái)?shù)因子:因子: 對(duì)整數(shù)對(duì)整數(shù) b!=0b!=0 及及 a , 如果存在整數(shù)如果存在整數(shù) mm 使得

3、使得 a=mb,a=mb,稱稱 b b 整除整除 a, a, 也稱也稱b b是是a a的因子。的因子。 記作記作 b|ab|a 例例 1,2,3,4,6,8,12,241,2,3,4,6,8,12,24 整除整除 2424素?cái)?shù):素?cái)?shù): 素?cái)?shù)素?cái)?shù): : 只有因子只有因子 1 1 和自身和自身 1 1 是一個(gè)平凡素?cái)?shù)是一個(gè)平凡素?cái)?shù) 例例 2,3,5,7 2,3,5,7 是素?cái)?shù)是素?cái)?shù), 4,6,8,9,10 , 4,6,8,9,10 不是不是200200以內(nèi)的素?cái)?shù):以內(nèi)的素?cái)?shù): 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

4、 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199素?cái)?shù)分解:素?cái)?shù)分解: 把整數(shù)把整數(shù)n n寫成素?cái)?shù)的乘積寫成素?cái)?shù)的乘積 分解整數(shù)要比乘法困難分解整數(shù)要比乘法困難 整數(shù)整數(shù) n n的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積 eg. 91 = 7 eg. 91 = 7 13 ; 3600 = 2 13 ; 3600 = 24 4 3 32 2 5 52 2 互素?cái)?shù):互素?cái)?shù): 整數(shù)整數(shù) a, ba, b 互素是指互素是指 它們沒有除它們沒有除1之外的其

5、它因子之外的其它因子。8 與與15 互素互素 8的因子的因子1,2,4,8 15的因子的因子 1,3,5,15 1 是唯一的公因子是唯一的公因子 記為:記為:gcd(8,15)=14.1.3 模運(yùn)算模運(yùn)算 設(shè)設(shè)n n是一正整數(shù)是一正整數(shù),a ,a是整數(shù)是整數(shù), ,若若 a=qn+r, 0rn, a=qn+r, 0rd1. Xf;Yd;2. If Y=0 then return X=gcd(f,d)3. R=X mod Y4. X=Y;5. Y=R6. Goto 2假定輸入是兩個(gè)正整數(shù)假定輸入是兩個(gè)正整數(shù)Euclid算法:算法:ngcd(55,22)=gcd(22,11)=gcd(11,0)=1

6、1ngcd(11,10)=gcd(10,1)=1 歐幾里德算法歐幾里德算法-求乘法逆元求乘法逆元 若若gcd(a,b)=1, bgcd(a,b)=1, b在模在模a a下有乘法逆元下有乘法逆元( (設(shè)設(shè)ba)ba)。 即存在即存在xa,bx1 mod axd)1.(X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d);停止,沒有逆元停止,沒有逆元;3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3(整數(shù)除)(整數(shù)除);5. (T1 T

7、2 T3)(X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 2擴(kuò)展歐幾里德算法:擴(kuò)展歐幾里德算法:求求d模模f的逆元的逆元例:求解例:求解 11d (mod51) = 1的步驟。的步驟。 即求即求11-1mod51=?循循環(huán)環(huán)次次數(shù)數(shù)QX1X2X3Y1Y2Y3初初值值-1051 0111Extended Euclid(f,d) (fd)1.(X1 X2 X3)(1,0,f); (Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d); 停止,沒有逆元停止,沒有逆元;3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3(整數(shù)除)(整數(shù)除);5. (T1 T2 T3) (X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 21411-1mod51=14Q=X3 div Y3 = 5

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論