[工學(xué)]信息安全技術(shù)chapter6公鑰密碼學(xué)和ras算法(已修改)
2024-10-30 23:46 本頁(yè)面
【正文】 東南大學(xué)信息安全學(xué)科研究生學(xué)位課 網(wǎng)絡(luò)信息安全理論與技術(shù) 黃 杰 信息安全研究中心 第六講 公鑰密碼學(xué)與 RSA 本次課內(nèi)容 ? 數(shù)論入門 –素?cái)?shù) – Fermat定理和 Euler定理 –素性測(cè)試 –離散對(duì)數(shù) ? 公鑰密碼學(xué) ? RSA 數(shù) 論 入 門 素?cái)?shù) ? 任意正整數(shù)可由素?cái)?shù)的乘積來(lái)表示。 ? 整數(shù) 12可用 {a2=2, a3=1}來(lái)表示 ? 整數(shù) 18可用 {a2=1, a3=2}來(lái)表示 ? 兩數(shù)相乘。 ?對(duì)應(yīng)指數(shù)相加。 ? 整除的表示。 ?對(duì)應(yīng)指數(shù)比較大小。 ? 最大公因子的計(jì)算。 ?對(duì)應(yīng)指數(shù)取最小值。 – K=gcd(a,b)對(duì)所有的 p， kp=min(ap,bp) ,0pa ppPa p a????Fermat定理 ? Fermat定理：若 p是素?cái)?shù)， a是正整數(shù)且不能被p整除，則 ? Fermat定理的另一種有用表示：若 p是素?cái)?shù)， a是任意正整數(shù)，則 pa p m o d11 ??paa p m o d?Euler函數(shù) ? Euler函數(shù) Φ(n)，指小于 n且與 n互素的正整數(shù)的個(gè)數(shù)。 ? 對(duì)于素?cái)?shù) p有： Φ(p)=p1 ? 例如， P=7,小于 7且與 7互素的正整數(shù)有： 1， 2， 3， 4， 5， 6，所以 Φ(7)=6 ? 如果 p=15， Φ(15)=?? ? Φ(15)= 8 ? 對(duì)于兩個(gè)素?cái)?shù) p和 q， p≠q，那么對(duì) n=pq，有： Φ(n)= Φ (pq)= Φ (p) Φ (q)=(p1) (q1) Euler定理 ? Euler定理：對(duì)于任意互素的 a和 n，有： ? Euler定理的另一種有用表示： ? 推論：給定兩個(gè)素?cái)?shù) p和 q，整數(shù) n=pq，對(duì)于小于 n的任意正整數(shù) m，有以下關(guān)系式成立： ? 推論的另一種表達(dá)形式： () 1 m odnan? ?( ) 1 m odna a n? ? ?( ) 1 ( 1 ) ( 1 ) 1 m o dn p qm m m n? ? ? ? ???( ) 1 m o dknm m n? ? ?素性測(cè)試 ? MillerRabin算法 –目的：檢驗(yàn)給定的大數(shù) n是否素?cái)?shù)，如 2150+1是否素?cái)?shù)？ – Miller和 Rabin提出的算法較為常用。該算法不能確定一個(gè)大數(shù)是素?cái)?shù)，但是可以確定一個(gè)大數(shù)是合數(shù)。 –奇整數(shù) n=3的表示： n1=2kq, k0,q為奇數(shù) –運(yùn)算時(shí)間 O(log n) MillerRabin算法 ? 性質(zhì) 1：如果 p是素?cái)?shù)， a是小于 p的正整數(shù)，當(dāng)且僅當(dāng) a mod p = 1或 a mod
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1