rsa算法及安全性分析(編輯修改稿)
2025-02-05 02:14 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 … ,(n1)a mod p} ={0,1,… ,p1} (a mod p) (2a mod p) … (n1)a mod p=(p1)! mod p (p1)! ap1=(p1)! mod p (p1)!與 p互素，所以乘法可約律， ap1=1 mod p 費(fèi)爾瑪定理和歐拉定理 ?歐拉函數(shù) ?設(shè) n為一正整數(shù)，小于 n且與 n互素的正整數(shù)的個(gè)數(shù)稱為 n的歐拉函數(shù)，記為 φ (n) ?定理：若 n是兩個(gè)素?cái)?shù) p和 q的乘積，則φ (n)＝ φ (p) φ (q)=(p1)(q1) ?歐拉定理 ?若 a和 n互素 ,則 aφ (n)= 1 mod n 離散對(duì)數(shù) ?求模下的整數(shù)冪 ?根據(jù)歐拉定理，若 gcd(a,n)=1,則 af(n) ≡1 mod n。 考慮一般 am ≡1 mod n, 如果 a,n互素，至少有一個(gè)整數(shù) m滿足這一方程。稱滿足這一方程的最小正整數(shù) m為模 n下 a的 階 。 ?例： a=7,n=19. 71 ≡7 mod 19, 72 ≡11 mod 19, 73 ≡1 mod 19,所以 7模 19的階為 3。從冪次為 4開始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同 RSA算法的實(shí)現(xiàn) ? 實(shí)現(xiàn)的步驟如下： Bob為實(shí)現(xiàn)者 (1) Bob尋找出兩個(gè)大素?cái)?shù) p和 q (2) Bob計(jì)算出 n=pq 和 φ (n)=(p1)(q1) (3) Bob選擇一個(gè)隨機(jī)數(shù) e (0e φ (n))，滿足 (e,φ (n))=1 (4) Bob使用輾轉(zhuǎn)相除法計(jì)算 d=e1(modφ (n)) (5) Bob在目錄中公開 n和 e作為公鑰 ? 密碼分析者攻擊 RSA體制的關(guān)鍵點(diǎn)在于如何分解 n。 若分 解成功使 n=pq，則可以算出 φ(n)＝（ p1)(q1)，然后由公 開的 e，解出秘密的 d RSA算法編制 ? 參數(shù) T={N}； ? 私鑰 SK=D； ? 公鑰 PK=E； 設(shè)：明文 M， 密文 C， 那么： 用公鑰作業(yè)： ME mod N = C 用私鑰作業(yè)： CD mod N = M 解密正確性證明 ? cd mod n ≡med mod n ≡m1 modj(n) mod n ≡ mkj(n)+1 mod n ? m與 n互素 ， 由歐拉定理 mj(n)≡1 mod n, mkj(n)≡1 mod n, mkj(n)+1≡m mod n ? gcd(m,n) ≠1,m是 p的倍數(shù)或 q的倍數(shù) ， 設(shè) m=cp， 此時(shí)gcd(m,q)=1,由歐拉定理 ，
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1