2020 2 16 1 第4章公鑰密碼 4 1密碼學(xué)中的一些常用的數(shù)學(xué)知識 自學(xué) 4 2公鑰密碼體制的基本概念4 3RSA算法4 4背包密碼體制4 5Rabin密碼體制4 6NTRU公鑰密碼系統(tǒng)4 7橢圓曲線密碼體制4 8基于身份的密碼體制 2020 2 16 2 4 2公鑰密碼體制的基本概念 4 2 1公鑰密碼體制的原理公鑰體制 Publickeysystem Diffie和Hellman 1976 每個用戶都有一對選定的密鑰 公鑰k1 私鑰k2 公開的密鑰k1可以像電話號碼一樣進行注冊公布 主要特點 加密和解密能力分開多個用戶加密的消息只能由一個用戶解讀 用于公共網(wǎng)絡(luò)中實現(xiàn)保密通信 只能由一個用戶加密消息而使多個用戶可以解讀 可用于認證系統(tǒng)中對消息進行數(shù)字簽字 無需事先分配密鑰 2020 2 16 3 公鑰體制加密 公鑰體制加 解密m D c DSKB EPKB m 安全保障從公開鑰PKB和密文c要推出明文m或解密鑰SKB在計算上是不可行的 由于任一用戶都可用用戶B的公開鑰PKB向他發(fā)送機密消息 因而密文c不具有認證性 圖4 1公鑰體制加密的框圖 2020 2 16 4 公鑰密碼認證體制 用戶A以自己的秘密鑰SkA對消息m進行A的專用變換DSKA A計算密文 c DSKA m 送給用戶B B驗證c m EPKA c EPKA DSKA m 安全性 由于SkA是保密的 其他人都不可能偽造密文c 可用A的公開鑰解密時得到有意義的消息m 因此可以驗證消息m來自A而不是其他人 而實現(xiàn)了對A所發(fā)消息的認證 2020 2 16 5 圖4 2公鑰密碼體制認證框圖 公鑰密碼認證體制 2020 2 16 6 為了同時提供認證功能和保密性 可使用雙重加 解密 圖4 3公鑰密碼體制的認證 保密框圖 公鑰保密和認證體制 2020 2 16 7 公鑰密碼應(yīng)滿足的要求 接收方B產(chǎn)生密鑰對在計算上是容易的發(fā)送方A用收方的公開鑰對消息m加密以產(chǎn)生密文c在計算上是容易的 收方B用自己的秘密鑰對密文c解密在計算上是容易的 敵手由密文c和B的公開密鑰恢復(fù)明文在計算上是不可行的 敵手由密文c和B的公開密鑰恢復(fù)秘密密鑰在計算上是不可行的加解密次序可換 即EPKB DSKB m DSKB EPKB m 不是對任何算法都做此要求 2020 2 16 8 單向函數(shù) 一個可逆函數(shù)f A B 若它滿足 1o對所有x A 易于計算f x 2o對 幾乎所有x A 由f x 求x 極為困難 以至于實際上不可能做到 則稱f為一單向 One way 函數(shù) 定義中的 易于計算 是指函數(shù)值能在其輸入長度的多項式時間內(nèi)求出 即若輸入長度為n 計算函數(shù)的時間是na的倍數(shù) a為一固定的常數(shù) 若計算函數(shù)時間是an的倍數(shù) 則為不可能做到的 2020 2 16 9 限門單向函數(shù) 單向函數(shù)是求逆困難的函數(shù) 而單向陷門函數(shù) Trapdoorone wayfunction 是在不知陷門信息下求逆困難的函數(shù) 當(dāng)知道陷門信息后 求逆是易于實現(xiàn)的 限門單向函數(shù)是一族可逆函數(shù)fk 滿足Y fk X 易于計算 當(dāng)k和X已知 X f 1k Y 易于計算 當(dāng)k和Y已知 X f 1k Y 計算上不可行 Y已知但k未知 研究公鑰密碼算法就是找出合適的單向限門函數(shù) 2020 2 16 10 4 2 3對公鑰密碼體制的攻擊 窮搜索攻擊尋找從公開鑰計算秘密鑰的方法可能字攻擊 2020 2 16 11 RSA算法概況 MIT三位年青數(shù)學(xué)家R L Rivest A Shamir和L Adleman Rivest等1978 1979 發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法 稱作MIT體制 后來被廣泛稱之為RSA體制 它既可用于加密 又可用于數(shù)字簽字 RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性 2020 2 16 12 1 密鑰的產(chǎn)生 選兩個保密的大素數(shù)p和q 計算n p q n p 1 q 1 其中 n 是n的歐拉函數(shù)值 選一整數(shù)e 滿足1 e n 且gcd n e 1 計算d 滿足d e 1mod n 即d是e在模 n 下的乘法逆元 因e與 n 互素 由模運算可知 它的乘法逆元一定存在 以 e n 為公開鑰 d n 為秘密鑰 4 3 1算法描述 2020 2 16 13 算法描述 加密和解密 2 加密加密時首先將明文比特串分組 使得每個分組對應(yīng)的十進制數(shù)小于n 即分組長度小于log2n 然后對每個明文分組m 作加密運算 c memodn3 解密對密文分組的解密運算為 m cdmodn 2020 2 16 14 解密正確性證明 cdmodn medmodn m1modj n modn mkj n 1modnm與n互素 由歐拉定理mj n 1modn mkj n 1modn mkj n 1 mmodngcd m n 1 m是p的倍數(shù)或q的倍數(shù) 設(shè)m cp 此時gcd m q 1 由歐拉定理 mj q 1modq mkj q 1modq mkj q j p 1modqmkj n 1modq 存在一整數(shù)r 使mkj n 1 rq兩邊同乘m cp mkj n 1 m rcpq m rcn 即mkj n 1 mmodn 2020 2 16 15 例4 8選p 7 q 17 求n p q 119 n p 1 q 1 96 取e 5 滿足1 e n 且gcd n e 1 確定滿足d e 1mod96且小于96的d 因為77 5 385 4 96 1 所以d為77 因此公開鑰為 5 119 秘密鑰為 77 119 設(shè)明文m 19 則由加密過程得密文為c 195mod119 2476099mod119 66解密為6677mod119 19 RSA算法例題 2020 2 16 16 4 3 2RSA算法中的計算問題 1 RSA的加密與解密過程加密與解密過程 都為求一個整數(shù)的整數(shù)次冪 再取模 再者考慮如何提高加 解密運算中指數(shù)運算的有效性 2 RSA密鑰的產(chǎn)生產(chǎn)生密鑰時 需要考慮兩個大素數(shù)p q的選取 以及e的選取和d的計算 2020 2 16 17 RSA的安全性 RSA的安全性是基于分解大整數(shù)的困難性假定 尚未證明分解大整數(shù)是NP問題 如果分解n p q 則立即獲得 n p 1 q 1 從而能夠確定e的模 n 乘法逆dRSA 129歷時8個月被于1996年4月被成功分解 RSA 130于1996年4月被成功分解密鑰長度應(yīng)該介于1024bit到2048bit之間由n直接求 n 等價于分解n p q 要大p 1 q 1都應(yīng)有大的素因子 e n且d n1 4 則d能被容易的確定 2020 2 16 18 對RSA的攻擊 共模攻擊 每一用戶有相同的模數(shù)n設(shè)用戶的公開密鑰分別為e1 e2 且e1 e2互素 明文消息為m 密文為因為 e1 e2 1 用歐幾里德算法可求re1 se2 1假定r為負數(shù) 從而可知由Euclidean算法可計算 c1 1 r c2s mmodn 2020 2 16 19 對RSA的攻擊 低指數(shù)攻擊 令網(wǎng)中三用戶的加密鑰e均選3 而有不同的模n1 n2 n3 若有一用戶將消息x傳給三個用戶的密文分別為y1 x3modn1x n1y2 x3modn2x n2y3 x3modn3x n3一般選n1 n2 n3互素 否則 可求出公因子 而降低安全性 利用中國余定理 可從y1 y2 y3求出y x3mod n1n2n3 由x n1 x n2 x n3 可得x3 n1 n2 n3 故有 2020 2 16 20 設(shè)A a1 a2 an 是由n個不同的正整數(shù)構(gòu)成的n元組 s是另一已知的正整數(shù) 背包問題就是從A中求出所有的ai 使其和等于s 其中A稱為背包向量 s是背包的容積 例如 A 43 129 215 473 903 302 561 1165 697 1523 s 3231 由于3231 129 473 903 561 1165所以從A中找出的滿足要求的數(shù)有129 473 903 561 1165 4 4背包密碼體制 2020 2 16 21 定義背包向量A a1 a2 an 稱為超遞增的 如果 4 4背包密碼體制 2020 2 16 22 超遞增背包向量對應(yīng)的背包問題很容易通過以下算法求解 已知s為背包容積 對A從右向左檢查每一元素 以確定是否在解中 若s an 則an在解中 令xn 1 若s an 則an不在解中 令xn 0 下面令對an 1重復(fù)上述過程 一直下去 直到檢查出a1是否在解中 檢查結(jié)束后得x x1x2 xn Bx x1x2 xn T 4 4背包密碼體制 2020 2 16 23 解密為此可用模乘對A進行偽裝 模乘的模數(shù)k和乘數(shù)t皆取為常量 滿足k ai gcd t k 1 即t在模k下有乘法逆元 設(shè)bi t aimodk i 1 2 n得一新的背包向量B b1 b2 bn 記為B t Amodk 用戶以B作為自己的公開鑰 4 4背包密碼體制 2020 2 16 24 例4 10A 1 3 5 11 21 44 87 175 349 701 是一超遞增背包向量 取k 1590 t 43 gcd 43 1590 1 得B 43 129 215 473 903 302 561 1165 697 1523 在得到B后 對明文分組x x1x2 xn 的加密運算為c f x B Bx t A Bxmodk對單向函數(shù)f x t t 1和k可作為其秘密的陷門信息 即解密密鑰 解密時首先由s t 1cmodk 求出s作為超遞增背包向量A的容積 再解背包問題即得x x1x2 xn 這是因為t 1cmodk t 1tABxmodk ABxmodk 而由k ai 知ABx k 所以t 1cmodk ABx 是惟一的 4 4背包密碼體制 2020 2 16 25 背包密碼體制是Diffie和Hellman1976年提出公鑰密碼體制的設(shè)想后的第一個公鑰密碼體制 由Merkle和Hellman1978年提出 然而又過了兩年該體制即被破譯 破譯的基本思想是不必找出正確的模數(shù)k和乘數(shù)t 即陷門信息 只須找出任意模數(shù)k 和乘數(shù)t 使得用k 和t 去乘公開的背包向量B時 能夠產(chǎn)生超遞增的背包向量即可 4 4背包密碼體制 2020 2 16 26 Rabin密碼體制是對RSA的一種修正 它有以下兩個特點 它不是以一一對應(yīng)的單向陷門函數(shù)為基礎(chǔ) 對同一密文 可能有兩個以上對應(yīng)的明文 破譯該體制等價于對大整數(shù)的分解 RSA中選取的公開鑰e滿足1 e n 且gcd e n 1 Rabin密碼體制則取e 2 4 5Rabin密碼體制 2020 2 16 27 4 5Rabin密碼體制 1 密鑰的產(chǎn)生隨機選擇兩個大素數(shù)p q 滿足p q 3mod4 即這兩個素數(shù)形式為4k 3 計算n p q 以n作為公開鑰 p q作為秘密鑰 2 加密c m2modn其中m是明文分組 c是對應(yīng)的密文分組 3 解密解密就是求c模n的平方根 即解x2 cmodn 由中國剩余定理知解該方程等價于解方程組 2020 2 16 28 4 6NTEU公鑰密碼系統(tǒng) NTEU是一種基于環(huán)的公鑰密碼系統(tǒng)特點 密鑰短且容易產(chǎn)生 算法的運行速度快 所需的存儲空間小 1 算法的參數(shù)2 密鑰的產(chǎn)生3 加密4 解密 2020 2 16 29 4 7橢圓曲線 ECC 密碼體制 獲得同樣的安全性 密鑰長度較RSA短得多被IEEE公鑰密碼標(biāo)準P1363采用 2020 2 16 30 橢圓曲線 橢圓曲線的曲線方程是以下形式的三次方程y2 axy by x3 cx2 dx ea b c d e是滿足某些簡單條件的實數(shù) 定義中包含一個稱為無窮遠點的元素 記為O 2020 2 16 31 橢圓曲線加法的定義 如果其上的3個點位于同一直線上 那么它們的和為O O為加法單位元 即對ECC上任一點P 有P O P設(shè)P1 x y 是ECC上一點 加法逆元定義為P2 P1 x y P1 P2連線延長到無窮遠 得到ECC上另一點O 即P1 P2 O三點共線 所以P1 P2 O O P1 P2 O P2 P1O O O O O 2020 2 16 32 橢圓曲線加法的定義 Q R是ECC上x坐標(biāo)不同的兩點 Q R定義為 畫一條通過Q R的直線與ECC交于P1 交點是唯一的 除非做的Q R點的切線 此時分別取P1 Q或P1 R 由Q R P1 O 得Q R P1點Q的倍數(shù)定義如下 在Q點做ECC的一條切線 設(shè)切線與ECC交于S 定義2Q Q Q S 類似可定義3Q Q Q Q 上述加法滿足加法的一般性質(zhì) 如交換律 結(jié)合律等 2020 2 16 33 有限域上的橢圓曲線 曲線方程中的所有系數(shù)都是某一有限域GF p 中的元素 p為一大素數(shù) 最為常用的曲線方程為y2 x3 ax bmod p a b GF p 4a3 27b2 0modp 例 p 23 a b 1 4a3 27b2 8 0 mod23 方程為y2 x3 x 1mod p 圖形為連續(xù)圖形 我們感興趣的是在第一象限的整數(shù)點 設(shè)Ep a b 表示ECC上點集 x y 0 x p 0 y p 且x y均為整數(shù) 并上O 2020 2 16 34 有限域上的橢圓曲線點集產(chǎn)生方法 對每一x 0 x p且x為整數(shù) 計算x3 ax bmodp決定求出的值在模p下是否有平方根 如果沒有則橢圓曲線上沒有與這一x對應(yīng)的點 如果有 則求出兩個平方根 2020 2 16 35 Ep a b 上加法 如果P Q Ep a b P O P如果P x y 則 x y x y OP x1 y1 Q x2 y2 P Q P Q x3 y3 x3 2 x1 x2 modp y3 x1 x3 y1 modp 2020 2 16 36 例 E23 1 1 P 3 10 Q 9 7 2020 2 16 37 4 7 4明文消息到橢圓曲線上的嵌入 取k在30 50之間的值不妨取k 30 x mk j j 0 1 2 30m 30m 1 30m 2 直到x3 ax b modp 是平方根 即得到橢圓曲線上的點 x sqrt x3 ax b 2020 2 16 38 ECC上的密碼 ECC上的離散對數(shù)問題在ECC構(gòu)成的交換群Ep a b 上考慮方程Q kP P Q Ep a b k p 由k和P求Q容易 由P Q求k則是困難的 由ECC上離散對數(shù)問題可以構(gòu)造Diffie Hellman密鑰交換和Elgamal密碼體制 2020 2 16 39 Diffie Hellman密鑰交換 取一素數(shù)p 2180 兩個參數(shù)a b 得到Ep a b 取Ep a b 的一個生成元G x1 y1 要求G的階是一個非常大的素數(shù) 階是滿足nG O的最小正整數(shù)n Ep a b 和G公開 A和B密鑰交換過程如下 A選小于n的整數(shù)nA作為秘密鑰 并有PA nAG作為公鑰B類似選取自己的秘密鑰nB和公開鑰PBA和B分別由K nAPB和K nBPA產(chǎn)生共享的秘密鑰攻擊者如想獲得K 必須由PA和G求出nA或PB和G求出nB 2020 2 16 40 Elgamal密碼體制 密鑰產(chǎn)生