RSA Cryptosystem Theorem 1.3: For n = p * q p,q 均是質數

Presentation on theme: "RSA Cryptosystem Theorem 1.3: For n = p * q p,q 均是質數"— Presentation transcript:

1 RSA Cryptosystem Theorem 1.3: For n = p * q p,q 均是質數
The Euler totient function (n)即 the reduced set of residues mod n之元素個數.所以當n是質數時, (n) ＝ n-1; 即　{ 1,2, …, n-1}. Theorem 1.4 ( Fermat’s Theorem): Let P be prime, then for every a s.t. gcd(a, P) = 1, aP-1 mod p = 1. Theorem 1.5(Euler’s Generalization): 對每一對 a與 n, gcd(a, n)=1, 則 a(n) mod n = 1.

2 Given e and d satisfying e*d mod (n) = 1, and a message M[0, n-1]
Theorem: Given e and d satisfying e*d mod (n) = 1, and a message M[0, n-1] such that gcd(M, n)=1, (Me mod n)d mod n = M. 1. 對任意一明文 M需滿足 gcd(M, n) = 1, 此處 n=p*q; p與q為兩大質數. 2. 如何求 e 與 d兩數? 可取一與(n)互質之數 e,根據 e*d mod (n)=1之條件,可求解 d . 3. 若 e 與 n 公開, 而 d 與 (n) 保密, 則安全可保. 4. 若有人欲分解 n= p*q,若n 是200位數,而電腦可處理 106 指令/秒(即1 MIPS)則破解 需106 年.

3 Public-key Cryptosystem
Proposed by Rivest, Shamir and Adleman in 1978 Public-key Cryptosystem RSA 每一使用者擁有兩把keys C = E(M) = MeB mod nB 明文M 明文M 密文 C A B D(C)=CdB mod nB = M constraints 此妙法之理論根據 ? 1. nB = p . q {約略大於 340位數} 2. gcd( eB , (p-1)(q-1)) = 1 3. 0 < M < nB (M, Ф(nB))=1 ) 4. eB . dB  1 (mod (p-1)(q-1))

4 資訊安全之技術與應用 RSA數位簽章 Alice Bob Alice 送出 C = (MdA mod mA)eB mod mB 簽章 加密
1. 本法乃為了確定送方身份而存在. 2. 所謂簽章,就RSA而言只不過送方先用唯獨自己知道的私鑰(private key) 加一次密之謂. Alice Bob Alice 送出 C = (MdA mod mA)eB mod mB 簽章 加密 Bob 解得 M = (CdB mod mB)eA mod mA 美麗之應用 資訊安全之技術與應用

5 數論review  同餘( congruent ): a n b iff (a-b) = k • n for k I
a is congruent to b modulo n. 數論review 例: 17與7對 mod 5 同餘,寫成 17 5 7 Def: 集合Zn是一個“complete set of residues modulo n” iff 有一集合Zn={r1,r2, …,rn},對任一整數a, 恰好有一個ri Zn, s.t. a n ri . 由於用n去除任意數,其餘數可能有n種值(即0,1,…,n-1),所以明顯地,S={0,1,…,n-1} Commutative Ring (交換環) 1. 整數是一個交換環 ,因為整數對 “+” 與 “*”兩運算,具有 (a) 交換律 (b) 結合律 與 (c) 乘法對加法之分配律. 2. 由於“整數”與“mod n整數”兩者同構(homomorphism), 因此 mod n整數是 交換環. 下述 The principle of modular arithmetic值得熟悉: Theorem: 若 a1 與 a2是整數, op 是二元運算子“+”,“-” 或 “*”, 則 (a1 op a2) mod n = [(a1 mod n) op (a2 mod n)] mod n 例: ( )mod 9 = (3+0+8)mod 9 = 2 .

6 Computing Inverse Lemma 1.1:
上一頁之Theorem可以推廣應用至指數;但僅止於 et ,n-1 t  0情況方可用. 亦即 et mod n = [ ti=1(e mod n)] mod n 為了計算效率上之考量,可以更快速執行此計算: 35 mod 7 =？　　　　3 * 3 mod 7 = [平方] 2 * 2 mod 7 = [四次方] 4 * 3 mod 7 = [五次方] 鑑於上述計算方式,　計算 az mod n 之　Time Complexity  1.5 log2z ,此法可應用於RSA之運算. Computing Inverse 當a, n是兩互質數;　a  [0, n-1], 則存在唯一整數x  [0, n-1], s.t. a x mod n = 1. Lemma 1.1: 若 gcd(a, n) = 1, 則 a i mod n  a j mod n for each i, j s.t. n > j > i  0. 此引理引申為: 每一個　a i mod n, i = 0, 1, …, n-1　是相異的整數. 而{ a i mod n }i = 0, 1, …,n-1是”a complete set of residues {0, 1, …, n-1}之一permutation.

7 如何求得此定理中之 x 值 ? ｛由於事關廣泛,只好先行回顧兩件事}
實例: If n=5, a=3, then 3*0 mod 5 = *1 mod 5 = *2 mod 5 = 1 3*3 mod 5 = *4 mod 5 = 2 [Notice: gcd(3,5)=1] Theorem 1.2: If gcd(a, n)=1, then there exists an integer x, 0 < x < n s.t. a x mod n = 1. 如何求得此定理中之　x 值 ? ｛由於事關廣泛,只好先行回顧兩件事} (1) Congruences related to reduced residues. (2) Euler totient function. 然後再定義一algorithm以求解　x 值. DEF: The reduced set of residues mod n 是 the subset of residues { 0, 1, …, n-1} relatively prime to n. 例: The reduced set of residues mod 10 是 {1, 3, 7, 9} The reduced set of residues mod 16 是 {1,3,5,7,9,11,13,15} 所以當n是質數,則The reduced set of residues mod n 是{1,2,…,n-1}, 即 the complete set of residues mod n - {0}.

8 DEF: The Euler totient function (n)　即 the reduced set of residues mod n之元素個數. 所以當n是質數時, (n) ＝ n-1; 即　{ 1,2, …, n-1}. 例: The reduced set of residues modulo 10 = {1, 3, 5, 7} = S ={r1, r2, r 3 ,r(10)} Theorem 1.3: For n = p * q p,q 均是質數 則 (n) = (p)* (q) = (p-1)*(q-1). 更一般化來看: 對任意整數 n, (n) =  ti=1Piei-1(Pi-1) where n = P1e1 P2e Ptet . 實例: n = 24 = (24) = 22(2-1)30(3-1) = 4*1*1*2 = 8 即 {1, 5, 7, 11, 13, 17, 19, 23} Theorem 1.4 ( Fermat’s Theorem): Let P be prime, then for every a s.t. Gcd(a, P) = 1, aP-1 mod p = 1. 此定理可自下一定理( Euler’s Theorem)穫得證明; Theorem 1.5(Euler’s Generalization): 對每一對 a與 n, gcd(a, n)=1, 則 a(n) mod n = 1.

9 RSA之理念呼之欲出 @ 只需將 x 設為 x = a(n)-1 mod n 即可! 閣下想通了嗎? 若(n)已知,則x之值易得.
現在可回答先前之疑; If gcd(a,n)=1, then how to compute x s.t. a*x mod n = 1? @ 只需將 x 設為 x = a(n)-1 mod n 即可! 閣下想通了嗎? 譬如說: a=3, n=7, 則　x = an-2 mod n = 35 mod 7 = 5 ; a*x mod n = 3 * 5 mod 7 = 1. 若(n)已知,則x之值易得. RSA之理念呼之欲出 Theorem: Given e and d satisfying e*d mod (n) = 1, and a message M[0, n-1] such that gcd(M, n)=1, (Me mod n)d mod n = M. Pf: (Me mod n)d mod n = Med mod n = M Why ?  e d mod (n) = 1 implies e d = t* (n) for some integer t.  Med mod n = Mt(n)+1 mod n = MMt(n) mod n = M(Mt(n) mod n) mod n = M*1 mod n = M. Mt(n) mod n = (M(n) mod n)t mod n = 1t mod n = 1.

10 Observations 明文 1. 對任意一明文 M需滿足 gcd(M, n) = 1, 此處 n=p*q; p與q為兩大質數.
2. 如何求 e 與 d兩數? 可取一與(n)互質之數 e, 根據 e*d mod (n) = 1之條件,可求解 d (refer to上一頁) 3. 若 e 與 n 公開, 而 d 與 (n) 保密, 則安全可保. 4. 若有人欲分解 n = p*q,若 n 是200位數,而電腦可處理 106 指令/秒(即1 MIPS)則破解 需106 年.( ?) 5. 公開金鑰與對稱金鑰兩者之系統整合現況: Encrypted session key 密文 明文 收方私鑰 產製亂數 RSA解密 DES解密 DES加密 通訊基碼 session key RSA解密 發方公鑰 通訊基碼 session key RSA加密 Encrypted session key 密文 PKDB RSA加密 發方私鑰 收方公鑰

11

12 資訊安全之美麗與哀愁 蠻力功擊 RSA-129 = = * The encoded message published was This number came from an RSA encryption of the `secret' message using the public exponent When decrypted with the `secret' exponent this becomes Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between words, the decoded message reads THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE(挑食的禿鷹 )

13 資訊安全之美麗與哀愁 珍惜資源 耗費了600個志願者8個月的計算(來自20個國家).
( conducted by Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland with the multiple polynomial quadratic sieve factoring method ) 幾乎是蠻力功擊方式(brute force attack). RSA VS. RSA170 ( = 41; 1041 倍! ) 珍惜資源

14 Reblocking problem RSA之見 圖示密度變化
RSA 加解密法 一旦要同時做到secrecy 與 authenticity , 則稍有麻煩發生; 因為此時需要用到不同的 moduli 做 successive transformations. For instance, in order for A to send a signed, secret message M to B, A must transmit: C = EB (DA (M)) If nA > nB , the blocks comprising DA (M) might not be in the range [ 0, nB-1 ] of B’s transformation. Reducing them to modulo nB does not solve the problem, because it would then be impossible to recover the original message M.(since the mapping is many-to-one type) One solution is to reblock DA(M). (i.e., changing the transformation of DA ) RSA三人 showed that reblocking can be avoided using a threshold value h (e.g., h = 1099). Each user has two sets of transformations: (EA1 , DA1) for signatures and (EA2 , DA2) for secrecy, where nA1 < h < nA2 .(即簽小密大) To send a signed, secret message to B, A transmits C = EB2 (DA1 (M)), which is computable because nA1 < h < nB2 (由於 h 之門檻值使然). User B recovers M and checks A’s signature by computing EA1 (DB2 (C)) = EA1 (DB2 (EB2 (DA1 (M)))) = EA1 (DA1 (M)) = M . RSA之見 圖示密度變化 EB2 DB2 DA1 EA1

15 Kohnfelder scheme K points: 第一個函數將M之空間一對一轉換, 保持在 nA1
第二個函數將nA1 之空間放大到nA2 , 但由於輸入端之空間僅有nA1 , 故有稀疏之感 第三個函數是第二個函之反函數,故雖其空間在nA2 , 但事實上已經還原回nA1 ,不 再有稀疏之感 第四個函數 則將第一個函數還原回來nA1 . 只有想函數之moduli 而不思考資料之流動現況,對此solution不易clear. Kohnfelder scheme 此法基本理念乃在 由於送收雙方均知道 nA 及 nB 之大小, 且RSA法滿足交換律, 因此 if C = EB (DA (M)) is not computable because nA > nB , then C’ = DA (EB (M)) is computable, user B can recover M by computing DB (EA (C’)) = DB (EA (DA (EB (M)))) = DB (EB (M)) = M . 同樣推理,亦可處理 nA < nB .

16 應該是收方簽署而非原加密者簽署 ! xd = (re)d = r1

17 有點牽強 e1 與 e2 跟 (n) 互質 ! 假如

18 若session key 不是用第九頁之方法傳 送,而是每兩人約定一把session key,
A cryptosystem is a five-tuple (P, C, K, E, D) , where the following conditions are satisfied: 1. P is a finite set of possible plaintexts 2. C is a finite set of possible ciphertexts 3. K, the keyspace, is a finite set of possible keys 4. For each kK, there is an encryption rule e k E and a corresponding decryption rule d k D. Each e k : PC and d k :C P are functions such that d k (e k (x)) = x for every plaintext x P. 1976年, Diffie與Hellman提出 Public Key Cryptosystem 概念,建議應用數論之特性解決 Key Distribution Problem. 從此公開金鑰之加密系統問世. 若session key 不是用第九頁之方法傳 送,而是每兩人約定一把session key, 則人數一多,key 之管理難矣! 對稱加密法session key 之傳送問題

19 Key agreement denotes a protocol whereby two (or more) parties jointly establish a secret key by communicating over a public channel. Diffie-Hellman在1976年有一佳作: 目標: Alice 與 Bob 兩人共同建構一把密鑰 KAB 方法: 給定一個大質數P,求出 GF(P)之原根g (所謂 primitive root 即是當 g 與 P 互 質, g>0, 若 g(p) = 1 mod P時,則稱 g 是 mod P 之原根). 如今, A 與 B 均已知 P 與 g, 再經 (1) A 任選一密鑰 XA, 算出 YA = gXA mod P { YA即謂公開金鑰} 送給 B. (2) B 任選一密鑰 XB, 算出 YB = gXB mod P { YB即謂公開金鑰} 送給 A. 而 KAB = gXAXB mod P = (YA) XB mod P = (YB) XA mod P 對入侵者而言,只可能知道YA ,YB, g 及 P,由這些資料 推求 KAB,一般相信等於解離散對數問題( Discrete Logarithm Problem; DLP); 因DLP是單向函數, 故不易解

20 ElGamal's PKC [ 與 Diffie-Hellman Key Agreement 部份相同者] 設 g 為 GF(P)之原根, P 為一大質數, XB 是 B 選取之密鑰, YB = gXB mod P 是 B 的 公鑰(準備送給A的). 現在,若 A 欲送明文M, 0 <= M <= P-1, 給 B, 則 A 任選一亂數r, (0 <= r <= P-2), 且計算送出密文 C (根據下述定義): A: C = (C1 ,C2) C1= g r mod P C2 = M(YB)r mod P B 收到 C 后計算下式 B: C1XB = (g r ) XB = YBr (mod P ) C2*(C1XB) -1 = M(YBr) (YBr) -1 = M (mod P ) ® 若 r 不重覆使用,則 ElGamal 之 PKC 安全性等於 Diffie-Hellman之 KDS. ® 每一明文M在不同的 r之下,可對應到不同的C密文,此即是所謂的 Probabilistic Public Key Cryptosystem. 此法之缺點: 傳輸效率祇有 1/2 ( 因為 C = (C1 ,C2) )

21  Something you should know: 若是秘密金匙密碼系統, 則
{ E: Encryption fun, D: Decryption fun, M: Plaintext C: Ciphertext, K: Key, e: encryption key, d: decryption key} C = EK(M) M= DK(C ) M= DK(EK(M)) M= EK(DK(M)) Not always true. 若是公開金匙密碼系統, 則 C=Ee(M) M=Dd( C) M=Dd(Ee(M)) M=Ee(Dd(M)) 具有 交換性 之PKC

22  Something you should know: Probabilistic encryption systems:
機率式公開金匙加密系統: PKC中，如Knapsack，RSA，Diffie-Hellman等均 是確定式的 (明密文一對一固定方式)，所以Intruder可以從截收到的密文C=E(M)中，針對數個最有可能的明文，如M’，進行加密而得C’=E(M’)。然後再將C與C’比對，若C=C’ 則可知M=M’。質言之,確定式的保密系統對Intruder而言，其破密資訊是可以累積的。 機率式加密系統對每一個明文使用不同的亂數(當然是在加密時)，因此一個明文可以 對應到很多不同的密文。而解密時卻是解得唯一的明文。 (1) Rabin Public Key Cryptosystem(1979) Rabin的方法是一個密文可以對應到四個可能明文(其中只有一個為真)。因此，在加密時必須加入一些有意義且易於分辨的訊息於明文中，使得解密時能夠明確地還原出原來的明文

23 方法簡介: 選定n=p*q; 其中p與q是大質數。令明文為M，密文為C，公開加密金匙為 (b,n)，秘密解密金匙為(p,q)。 [加密程序]: C = M * (M + b) mod n， 其中b是亂數。 [解密程序]: 根據上式可知M2 + M*b - C = 0 mod n. 故明文可由下述四者之一算出: M = -b/2 (b/2)2+C mod p M = -b/2 (b/2)2+C mod q

24 (2)另一種機率式加密法 ----- Goldwasser-Micali Public-Key Cryptosystem  背景知識 設a為大於1之整數,且 (a,p)=1, 若x 2  a (mod p) 可解,則a謂 之二次剩餘,對mod p. 例如: 1,2,4為7(即mod 7)之二次剩餘, 3,5,6為二次非剩餘. 因x=1,6時 x 2  1 (mod 7),同理x=3,4時x 2  2 (mod 7), x=2,5時, x 2  4 (mod 7). Jacobi symbol: J(a/p)= if p‌|a {即p是a的因數;a是p的倍數} = if a is a quadratic residue mod p = if a is a quadratic nonresidue mod p. 方法簡介: 令明文M=m1m2…mk 其中mi是一個位元非0即1。

25 首先任選n=p*q，此p與q是大質數。其次任選一數 y，但是必需滿足J(y/p) =
J(y/q) = -1; 也就是y是p與q之二次非餘數。 公開加密金匙為 (y, n)，秘密解密金匙為 (p, q)。