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.

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 年.

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))

資訊安全之技術與應用 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 美麗之應用 資訊安全之技術與應用

數論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 例: (135273+261909+522044)mod 9 = (3+0+8)mod 9 = 2 .

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 * 2 mod 7 = 4 [四次方] 4 * 3 mod 7 = 5 [五次方] 鑑於上述計算方式,　計算 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.

如何求得此定理中之 x 值 ? ｛由於事關廣泛,只好先行回顧兩件事} 實例: If n=5, a=3, then 3*0 mod 5 = 0 3*1 mod 5 = 3 3*2 mod 5 = 1 3*3 mod 5 = 4 3*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}.

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 P2e2 ... Ptet . 實例: n = 24 = 2331 (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.

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) + 1 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.

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加密 發方私鑰 收方公鑰

資訊安全之美麗與哀愁 蠻力功擊 RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 = 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533 The encoded message published was 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154 This number came from an RSA encryption of the `secret' message using the public exponent 9007. When decrypted with the `secret' exponent 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095 this becomes 200805001301070903002315180419000118050019172105011309190800151919090618010705 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(挑食的禿鷹 )

資訊安全之美麗與哀愁 珍惜資源 耗費了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). RSA129 VS. RSA170 (170 - 129 = 41; 1041 倍! ) 珍惜資源

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

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 .

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

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

若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 之傳送問題

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是單向函數, 故不易解

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) )

 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

 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的方法是一個密文可以對應到四個可能明文(其中只有一個為真)。因此，在加密時必須加入一些有意義且易於分辨的訊息於明文中，使得解密時能夠明確地還原出原來的明文

方法簡介: 選定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

(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)= 0 if p‌|a {即p是a的因數;a是p的倍數} = 1 if a is a quadratic residue mod p = -1 if a is a quadratic nonresidue mod p. 方法簡介: 令明文M=m1m2…mk 其中mi是一個位元非0即1。

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