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