吉林快三走势图表跨度
學霸學習網 這下你爽了
當前位置:吉林快三走势图表跨度 >> >>

吉林快三示意图:無線網絡安全技術2011-8數論與RSA_圖文

吉林快三走势图表跨度 www.dkkczn.com.cn 無線網絡安全技術
秦中元
東南大學信息科學與工程學院 信息安全研究中心 [email protected]

上次課內容
?第七章 用對稱密碼實現保密性 ?7.1 密碼所處的邏輯位置 ?7.2 密鑰分配 ?7.3 隨機數產生

2013-8-19

2

7.1 同時使用鏈路加密和端對端加密 ?主機使用端對端加密來加密用戶數據。 ?整個分組使用鏈路加密。

2013-8-19

3

7.2 典型的密鑰分配過程 ?密鑰分配中心(KDC):負責分發密鑰給需要 的用戶。 ?A與B要建立邏輯連接,需要用一個一次性 的會話密鑰來?;な蕕拇?。 ?假定:
? A擁有一個主密鑰Ka,與KDC共享。 ? B擁有一個主密鑰Kb,與KDC共享。

?該過程要實現:
? 給A和B安全地分配一個會話密鑰。
2013-8-19 4

典型的密鑰分配過程

2013-8-19

5

偽隨機數的產生
?線性擬合發生器 ?密碼編碼學方法產生
? 循環加密 ? DES輸出反饋模式 ? ANSI X9.17 偽隨機數發生器

?BBS發生器

2013-8-19

6

本次課內容
?第八章 數論入門 ?8.1 素數 ?8.2 Fermat定理和Euler定理 ?8.3 素性測試 ?8.4 離散對數

2013-8-19

7

8.1 素數
?素數:除了1和此整數自身外,沒法被其他數整除 的自然數。 ? 素數是無限多的,不存在最大的素數(歐幾里 得)。 ? 已知的最大素數: 232582657-1 ?算術基本定理(素數唯一分解定理): ? 分解的存在性; ? 分解的唯一性:即若不考慮排列的順序,正整 數分解為素數乘積的方式是唯一的。

2013-8-19

8

8.1 素數
?任意正整數可由素數的乘積來表示。

a ? ? p , ap ? 0
ap p?P

? 整數12可用{a2=2, a3=1}來表示 ? 整數18可用{a2=1, a3=2}來表示

?兩數相乘?對應指數相加。 ?整除的表示?對應指數比較大小。 ?最大公因子的計算?對應指數取最小值。
? K=gcd(a,b)-->對所有的p,kp=min(ap,bp)
2013-8-19 9

數論的有趣問題
?哥德巴赫猜想,它是說任何一個大于6的偶數, 都能表示為兩個奇素數之和。 ?孿生素數猜想 ?存在無窮多個素數 p,有p+2也是素數 ?(5, 7), (11, 13), (101, 103), (4967, 4969) ?完美數。

2013-8-19

10

8.2.1 Fermat定理
?Fermat定理:若p是素數,a是正整數且不能被 p整除,則

a

p ?1

?1

mod

p

?Fermat定理的另一種有用表示:若p是素數,a 是任意正整數(不要求不能被p整除?。?,則

a ?a
p

mod

p

2013-8-19

11

8.2.2 Euler函數
?Euler函數?(n),指小于n且與n互素的正整數的個 數。 ??(7)=? ??(8)=? ?性質: (1)?(1) = 1 (2)若p為素數,?(p) = p-1 (3)若有素數m和n,且m≠n,則有: ?(mn) = ?(m)??(n)

2013-8-19

12

8.2.3 Euler定理
?Euler定理:對于任意互素的a和n,有:

a

? (n)

?1

mod n

?Euler定理的另一種有用表示:

a

? ( n ) ?1

?a

mod n

?推論:給定兩個素數p和q,整數n=pq,對于 小于n的任意正整數m,有以下關系式成立:

m
2013-8-19

? ( n ) ?1

?m

( p ?1)( q ?1) ?1

?m

mod n
13

8.3 素性測試 ?目的:檢驗給定的大數n是否素數,如 2150+1是否素數? ?Miller和Rabin提出的算法較為常用。該算 法不能確定一個大數是素數,但是可以確 定一個大數是合數。 ?奇整數n>=3的表示: n-1=2kq, k>0,q為奇數

2013-8-19

14

素數的兩個性質
?如果p是素數,a是小于p的正整數,則a2 mod p=1當且僅當 a mod p = 1或a mod p=-1. ?設p是大于2的素數,有p-1=2kq, k>0,q為奇 數。設a是整數,且1<a<p-1,則下面兩個 條件必有一個成立:
? aq模p和1同余。 q, a2q,….., a2k-1q里存在一個數,模p時 ? 整數a 和-1同余。

2013-8-19

15

素數測試算法
?a test based on Fermat’s Theorem ?The algorithm Test(n) is:
1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq 2. Select a random integer a, 1<a<n–1 3. if aq mod n = 1 then return (―maybe prime"); 4. for j = 0 to k – 1 do 2jq mod n = n-1) 5. if (a then return(" maybe prime ") 6. return ("composite")

2013-8-19

16

8.4 離散對數
? 考慮如下整數:

a mod n, a2 mod n, a3 mod n, … , am mod n, …
? 定義: 令a與n互素,則滿足am ≡ 1 mod n的最小整數m 稱為:
? a模n的階,記為ordna 。 ? 模n下a的指數 ? 由a生成的周期長度

? 若a與n互素,則必有一整數m = ?(n)滿足am ≡ 1 mod n。 ? 本原根 ? 若a是n的本原根,則a的1到Φ(n)次冪是模n各不相 同的,且均與n互素。 ? 當p為素數時, a的1到(p-1)次冪是模n各不相同的
2013-8-19 17

模19的整數冪

2013-8-19

18

離散對數
? 離散對數的定義
? 對于某素數p,p的本原根為a; ? 對于整數b,0 ? b ? p ; ? 存在唯一的整數i, 0 ? i ? p

b ? ai

,使得

mod

p

? i稱為以a為底b的離散對數,記為dloga,p(b)

? 離散對數的性質 ? 離散對數的計算
y≡gx mod p 已知g,x,p,計算y是容易的 已知y,g,p,計算x是困難的

2013-8-19

19

?定理: 令p為一非負整數,其本原根為a,令x 和y與p互素,則有:
(1) (2) (3) (4) dloga,p(1) ≡ 0 (mod ?(p)) dloga,p(a) ≡ 1 (mod ?(p)) dloga,p(xy) ≡ dloga,p(x)+dloga,p(y)(mod ?(p)) dloga,p(yk) ≡ k ? dloga,p(y) (mod ?(p))

2013-8-19

20

引言1 Diffie生平
?Diffie(1944-) ? 1965年,獲得麻省理工學院 數學學士學位 ? 1976年,和Hellman聯合發 表《密碼學新方向》 ? 1991年,任職于Sun公司 ? 1992年,瑞士聯邦理工學院 授予博士頭銜。
2013-8-19 21

引言2 Diffie的問題
? Diffie考慮的問題: 1.加密過程中密鑰分發問題 – 手工分發不符合實際情況,而KDC的 存在意味著通信雙方的隱私會被第三 方監視。 2.“數字簽名”問題: – 尋找一個正確判斷消息來源的方法, 即象手寫簽名一樣,以保證消息卻是 出自特定的人。
2013-8-19 22

引言3 雙重加密方案
? 雙重加密方案 1. Alice把消息放到箱子里,用自己的鎖鎖上發送給Bob 2. Bob收到箱子后加上自己的鎖,在把箱子返回給Alice 3. Alice除掉自己的鎖,再把箱子寄給Bob 4. Bob除掉自己的鎖,讀取消息

2013-8-19

23

2013-8-19

24

2013-8-19

25

2013-8-19

26

? 雙重加密方案的數學描述:
1. Alice發送EA(P)給Bob 2. Bob發送EB(EA(P))給Alice 3. Alice發送DA(EB(EA(P)))=DA(EA(EB(P)))=EB(P)給Bob 4. Bob解密DB(EB(P)=P

? 雙重加密方案的分析
? 要求構造一個函數,滿足:
? EB(EA(P ))=EA(EB(P))

? 無法驗證Alice或Bob的身份

– Diffie的解決方法:
? 使用單向函數
2013-8-19 27

引言4 單向函數
?現實生活中的例子
? 單向路:只允許沿著一個方向走(加密),但 你不能沿著反方向走(解密)。 ? 電話號碼本:很容易根據人名找到電話號碼 (加密),但是根據號碼找對應的人很難(解 密)。

?單向函數的其它例子:黃色顏料+藍色顏料 得到綠色顏料,但是反過來??

2013-8-19

28

?單向函數:
? 函數值計算很容易 ? 逆計算是不可行的。

?單向陷門函數:
? 函數值計算很容易 ? 若知道某種附加的信息,則逆計算是可行的,否則不 可行。

2013-8-19

29

公鑰密碼學
?公鑰密碼學和其之前的對稱密碼的區別
? ? ? ? 對稱密碼采用替換和置換; 公鑰算法采用數學函數; 對稱密碼只使用一個密鑰; 公鑰算法使用兩個獨立的密鑰

?關于公鑰密碼的誤解
? 公鑰密碼比對稱密碼安全 ? 公鑰密碼可以取代傳統密碼 ? 公鑰密碼可以很容易的實現密鑰分配

2013-8-19

30

公鑰密碼體制的組成部分
?六個組成部分
? ? ? ? ? ? 明文 加密算法 公鑰 私鑰 密文 解密算法

2013-8-19

31

公鑰密碼體制(加密過程)

Bob
2013-8-19

Alice
32

9.2 RSA算法
?作者
? 1977年,R, S, A
? Ron Rivest ? Adi Shamir ? Len Adleman

S、R、A
2013-8-19 33

RSA算法
? 1977年Rivest, Shamir和Adleman共同提出,是最早提出 的滿足要求的公鑰算法之一,是被廣泛接受且被實現的通 用公鑰加密方法。 ? RSA是一種分組密碼。明文和密文均為0到n-1的整數,通 常n的大小為1024位二進制數或309位十進制數。 ? 對于明文分組M,密文分組C,選取兩個素數p、q,計算 n=pq,ed mod Φ(n) =1. ? 加密過程:C=Me mod n ? 解密過程: Cd mod n =(Me)d mod n=Med mod n = M ? 公鑰用于加密KU={e,n} ? 私鑰用于解密KR={d,n} ? 如何滿足條件:M=Med mod n?

2013-8-19

34

2013-8-19

35

加密和解密過程

2013-8-19

36

RSA加解密舉例 ?p=17 ?q=11 ?n=187 ?Φ(n)=? ?e選為7 ?d=23 ?公鑰為?私鑰為? ?輸入明文M=88.密文為?

2013-8-19

37

Principles of PKC

9.1.3 對公鑰密碼的要求

Diffie and Hellman(1976)
1. 密鑰對的生成在計算上是容易的 2. 加密在計算上是容易的 3. 解密在計算上是容易的 4. 已知公鑰的情況下,攻擊者想要確定私鑰 在計算上是不可行的 5. 已知公鑰和密文的情況下,攻擊者想要恢 復明文在計算上是不可行的 6. 加密和解密的順序可以交換:

? M = DPUb[EPRb(M)] = DPRb[EPUb(M)]

Principles of PKC

?單向函數 ? Y = f(X) 容易 ? X = f-1(Y) 不可行 ?單向陷門函數 ? Y = fk(X) 給定k和X,容易 ? X = fk-1(Y) 給定k和Y,容易 ? X = fk-1(Y) 給定Y但k未知,不可 行

RSA算法的基本特征
? 基于大數(100到200位十進制素數)分 解難題 ? 分組密碼算法:要求分組的二進制值小 于n,分組長度即為log2(n): ? 基于整數乘法 ? 明/密文分組以及公/私鑰被看作小于n的 整數 ? 加/解密是模乘運算 ? 明文、密文是0到n-1之間的整數,通常n 的大小為1024位或309位十進制數

公鑰密碼體制(認證過程)

Bob
2013-8-19

Alice
41

既實現加密又實現認證的方法

2013-8-19

42

對公鑰密碼的要求
?公鑰和私鑰的產生在計算上是容易的; ?已知公鑰和明文,產生密文在計算上是容 易的; ?已知私鑰和密文,恢復出明文在計算上是 容易的; ?已知公鑰,確定私鑰在計算上是不可行的; ?已知公鑰和密文,恢復明文在計算上是不 可行的; ?加密和解密的順序可以交換
2013-8-19 43

算法復雜性
?算法時間復雜性是衡量算法有效性的常用標準。 一般有以下幾種:
? 線性的:若運行時間為O(n); ? 多項式的:存在常量t,使得運行時間為O(nt); ? 指數的:存在某常量t和多項式h(n),使得運行時間為O(th(n))

?在多項式時間內可解的問題,稱為易處理問題。 易處理問題的全體稱為確定性多項式時間可解類, 記為P。 ?不能在多項式時間可解的問題,稱為非確定性多 項式時間可解問題,簡稱NP問題。

2013-8-19

44

如何計算ab mod n
?先計算冪,再取?!屑浣峁淺4??解決方法: ?利用模算術的性質
(a×b) mod n =[(a mod n) × (b mod n)]mod n

?重復計算中間結果的平方
a2 a4 a8 a16,只需四次乘法

2013-8-19

45

如何計算ab mod n
a ?a
m (
bi ?0

? 2i )

??a
bi ? 0

( 2i )

a mod n ? ( ? a
b bi ?0

( 2i )

) mod n ? ( ? [a
bi ?0

( 2i )

mod n]) mod n

計算ab mod n的算法:

2013-8-19

46

公鑰密碼分析
?窮舉攻擊——使用長密鑰 ?從給定的公鑰計算私鑰 ?窮舉消息攻擊

2013-8-19

47


吉林快三走势图表跨度 | 網站地圖 | 學霸百科 | 吉林快三走势图表跨度
All rights reserved Powered by 吉林快三走势图表跨度 吉林快三走势图表跨度 www.dkkczn.com.cn
copyright ©right 2010-2021。
文檔資料庫內容來自網絡,如有侵犯請聯系客服。[email protected]