數(shù)論與信息安全(編輯修改稿)
2024-11-24 21:01 本頁面
【文章內(nèi)容簡介】 53 m o d 1 1xxxx????????? ?? 4. 求解 聯(lián)立的線性同余式 : 歐拉定理和費(fèi)爾瑪定理 模 m的完全剩余集 : (1) 歐拉函數(shù) 設(shè) m0為一正整數(shù) , 記 ? (m)為小于 m且與 m互素的正整數(shù)的個(gè)數(shù) , 并稱其為 m的歐拉函數(shù) . 定理 若 m1， m2互素，則 ? (m1m2)=? (m1) ? (m2) 若kkpppm????2121?, 則 )())(()(kpppmm11111121???? ?? 定理 (2) 歐拉定理 定理 (Euler) 若 a與 m互素，則 a?(m) ?1 mod m 推論 (Fermat) 若 p是素?cái)?shù)， (a, p)=1, 則 ap?1 ?1 mod p 定理 (Fermat) 若 p是素?cái)?shù)，則 ap?a mod p 故當(dāng) p是素?cái)?shù)，則 a?1?ap?2 mod p 例 3 .8 求解 3 102 ? ? mo d 1 1 . 例子： 例 3 .10 若 a , b 是正整數(shù)， p 是素?cái)?shù)，則 pbax m od? 的解是 pbaxpm od2?? 例 求 2?1 mod 11. 同余類方程 mbax m o d? 有解的充分必要條件為 gcd{ a, m } | b ，并且解為 mbax m o d? 其中， a 為 a 模 m 的逆 . (3) 應(yīng)用 例 解方程： 7x?22 mod 31 習(xí)題 1. 解方程： 7x?5 mod 23 2. 求 3?1 mod 13. 3. 7 威爾森定理 定理 (Wilson) 若 p是素?cái)?shù)，則 (p?1)!? ?1 mod p 反之，如果整數(shù) p滿足上式， 則 p是素?cái)?shù) . 平方剩余 例子 設(shè)有下列同余式 : x2?1, x2?2, x2?3, x2?4 mod 5 求解 ? 引理 若 p是奇素?cái)?shù) , p與 a互素 , 則 x2?a mod p 或無解 , 或有兩個(gè)模 p不同余的解 . 并且 , 如果1?x?p是一解 , 則 另一解為 p?x?. 定理 若 p是奇素?cái)?shù) , 則 1, 2, . . ., p?1正好有 (p?1)/2個(gè)是模 p的平方剩余 . 即為： 1, 2, . . ., p?1中模 p與 12, 22, …, [1/2( p?1)]2同余的數(shù) . 例如 ：取 p=11，求模 11的平方剩余 (1?ap). 4. 公鑰密碼 引言 公開密鑰密碼學(xué)是密碼學(xué)歷史上最大的而且也 是唯一真正的革命 . 傳統(tǒng)密碼編碼技術(shù) (包括分組密碼 )建立在替代 和置換基礎(chǔ)之上 . 它們的加密和解密是對(duì)稱的 . 1976年， Diffie 和 Hellman 在這方面取得了驚人的突破：他們開創(chuàng)的公鑰密碼技術(shù)同時(shí)解決了這兩個(gè)問題 . 但常規(guī)的密碼存在兩個(gè)重大問題 : ? 密鑰管理和分配問題 ? 數(shù)字簽名問題 原理 ： 加密密鑰和解密密鑰不同，而且加密密鑰公開，解密密鑰保密 . 例如： ? 甲和乙同時(shí)選用同一個(gè)公鑰密碼系統(tǒng)； ? 乙將公開密鑰傳送給甲； ? 甲用此公鑰加密他的信息并傳送給乙； ? 乙用他自己的私人密鑰解密甲傳來的加密文件 . 需要澄清的問題： ? 不要誤認(rèn)為公鑰密碼加密在防止密碼攻擊方面 更安全可靠（任何加密方案的安全性都依賴于密 鑰的長度和加密算法的計(jì)算復(fù)雜度）； ? 不要誤認(rèn)為公鑰密碼加密使得常規(guī)加密技 術(shù)過時(shí) （ 公鑰密碼加密開銷更大 ， 所以公認(rèn) 為僅用于密鑰管理和數(shù)字簽名 ） ； ? 不要誤認(rèn)為公鑰密碼技術(shù)使得密鑰管理非 常簡單 ， 事實(shí)上 ， 仍需要一個(gè)代理中心 ， 而 且整個(gè)過程既不簡單 ， 也不是更有效 . 采用的技術(shù)的核心： 基于單向陷門函數(shù) : 加密容易 , 但解密卻相當(dāng)難 . 其中 , 陷門就是解密密鑰 . 例如利用求 mod p (素?cái)?shù) ) 的離散對(duì)數(shù)的困難度 : ? 甲和乙在 {1， 2， 3， … ， p?1}各中選取一 數(shù)作為 x甲 和 x乙 并計(jì)算 pbypby xx m o d m o d 乙甲 乙甲 和 ?? ? 乙將 y乙 通知甲 , 而且甲將 y甲 通知乙 。 ? 雙方得到通信密鑰 : pbkxx m o d 乙甲甲乙 ?（ Rivest, Shamir amp。 Adleman） 基于：數(shù)論中的 Euler 定理和因子分解問題是計(jì)算上困難的問題 . RSA公鑰密碼 RSA 加密算法 操作過程： 1. 取兩個(gè)充分大的素?cái)?shù) p, q。 2. 計(jì)算 n=pq (公開 ), 和 ?(n)=(p?1)(q?1) (保密 )； 3. 隨機(jī)選取整數(shù) e (公開 )， 滿足 gcd(e, ?(n))=1； 4. 計(jì)算 d (保密 ), 滿足 de ?1 mod ?(n) RSA 加密算法 對(duì)明文的加密過程： 1. 將明文 (二進(jìn)制數(shù)串 )按長度不大于 log2n分組； 2. 對(duì)每一組 (設(shè)為 mn)加密： 加密算法 : c=E(m) ?me mod n 對(duì)明文的解密過程： 解密算法 : m=D(c) ?cd mod n 例 取 p=43, q=59， 并取 e=13. 則 n=pq=2537， ?(n)=42?58=2436. 解方程： de ?1 mod 2436 得 d=937. 取 m=73, 則 7e =713 =78?74?7 ?2172=c mod 2436 RSA 的安全性 關(guān)鍵： 在于數(shù) n的因子分解 )2(O 222 l o gl o g)( l o g nn 目前最快的因子分解算法的計(jì)算復(fù)雜度為： 即 ， 如果數(shù) n=pq的因子分解被破 ， 則可得 ?(n)=(p?1)(q?1), 從而由加密密鑰 e可由下式解 得解密密鑰： de?1 mod ?(n) 從而 ， RSA建議： 1． p, q為 100位的十進(jìn)制數(shù) (?2332), 從而n=pq為 200位 的十進(jìn)制數(shù)； 2． p, q的差應(yīng)較大 (差幾位 )； 3． p?1, q?1有較大的素因子 。 4． gcd(p?1, q?1)很小 . 這樣的 p, q 稱為 安全素?cái)?shù) . 此外 , 如果 en, 并且 dn1/4, 則 d 很容易確定 . 注： 1. 知道 n與 ?(n) 容易破解 p, q: 2. 如果 p?q=k 較小 , 容易破解 p, q: ?(n)=(p?1)(q?1)=pq?(p+q)+1=n ?(p+q) (
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1