數學基礎 on Cryptography.

Presentation on theme: "數學基礎 on Cryptography."— Presentation transcript:

1 數學基礎 on Cryptography

2 Zn (the integers mod n) Zn
Zn (the integers mod n) Zn* (the integers relatively prime to n , mod n)  Although there are many functions that are believed to be one-way, there currently do not exist functions that can be proved to be one-way.  Zm is defined to be the set {0, 1, , m-1}, equipped with two operators, + and *. Addition and multiplication in Zm work exactly like real addition and multiplication, except that the results are reduced modulo m.  相信 f(x) = xb mod n, gcd(x, n)=1 是 one-way function.( Discrete Logarithm Problem; DLP)  These definitions of addition and multiplication in Zm satisfy most of the familiar rules of arithmetic. We will list these properties as follows: (1) addition is closed, i.e., for any a,b  Zm, a+b  Zm (2) addition is commutative , i.e., for any a,b  Zm, a+b = b+a (3) addition is associative, i.e., for any a,b,c  Zm, (a+b)+c = a+(b+c) (4) 0 is an additive identity, i.e., for any a Zm, a+0 = 0+a = a (5) the additive inverse of any a Zm is m-a, i.e., a+(m-a)=(m-a)+a=0 (6) multiplication is closed, i.e., for any a,b  Zm, a*b  Zm (7) multiplication is commutative, i.e., for any a,b  Zm, a*b = b*a (8) multiplication is associative, i.e., for any a,b,c  Zm, (ab)c = a(bc)

3  Properties 1, 3-5 say that Zm forms an algebraic structure called
(9) 1 is a multiplicative identity, i.e., for any a  Zm, a*1 = 1*a = a (10) multiplication distributes over addition, i.e., for any a,b,c  Zm, (a+b)c = (ac)+(bc) and a(b+c) = (ab)+(ac).  Properties 1, 3-5 say that Zm forms an algebraic structure called a group with respect to the addition operation.  If property 2 also holds, the group is said to be Abelian.  Properties 1-10 establish that Zm is, in fact, a ring. Some familiar examples of rings include the integers, Z; the real numbers, R; and the complex numbers, C. {We are interesting in the finite rings, such as Zm}

4  For a (finite) multiplicative group G, define the order of an element gG
to be the smallest positive integer T such that gT = 1 = g0 in Zp.  若 gG 之 order 是 P-1 {P為質數且集合 G 定義於ZP}, 則 g 稱為 mod P 之原根.{當 g 為 mod P 之primitive root, 由 g 所產生之序列(sequence) 具有最大週期, 因此安全上較佳.} 理論上可證: 對所有質數 P, 其原根必 定 存在. 若 g 為 mod P 之 primitive root, 且 a 與 P-1 互質, 則 g a mod P 必為 mod P之原根. mod P 之原根個數等於 (P-1) Euler Totient Function. 例: 若 p=11, 則 (10)={1,3,7,9}, 因此 p=11 時共有 4 個原根; 即 [ 因我們已知 2 是 mod 11 之原根, 故] 21 = = = = 6 2, 8, 7, 6 均是 mod 11 之原根

5 Information Theory Information theory addresses two related problems:
the noisy channel problem and the secrecy problem. Information theory measures the Amount of information in a message by the average number of bits needed to encode all possible messages in an optimal encoding. The amount of information in a message is formally measured by the entropy of the message. The entropy is a function of the probability distribution over the set of all possible messages. Let X1, , Xn be n possible messages occurring with probabilities p(X1), , p(Xn), where I=1n p(Xi) = 1. The entropy of a given message is defined by the weighted average: H(X) = - I=1n p(Xi) log2 p(Xi) = X p(X) log2(1/ p(X) )

6 1: Let n=3, and let the 3 messages be the letters A, B and C, where p(A)=1/2, and p(B)=p(C)=1/4. Then log 2 {1/p(A)} = log 2 2 = 1 log 2 {1/p(B)} = log 2 4 = 2 log 2 {1/p(C)} = log 2 4 = 2, and H(X) = (1/2) log * [(1/4) log 2 4] = = 1.5 此即說明一個最適化編碼方式就是將 A 指定一個 bit , 而 B 和 C 指定兩個 bits. 譬如用: A --- 0, B , C , 則 ABAACABC = , 其 average number of bits per letter = 12/8 = 1. 5  2: Suppose all messages are equally likely; that is, p(Xi) = 1/n for i = 1, , n. Then H(X) = n * [( 1/n ) log 2 n] = [log 2 n].

7 人在福中不知福 觀察 3: Let n = 1 and p(X) = 1. Then H(X) = log 2 1 = 0.
There is no information because there is no choice. 人在福中不知福 若所有messages 之長度均為 N 個 characters , 則 the rate of the language for messages of length N is defined by r = H(X)/N {亦即 每一個 character 所需之平均 bit 數. 觀察 1. H(X) 表示 the amount of information; 亦即 當 messages 之集合 的元素 個數越大 , 其 H(X) 值亦越大 ! 簡單地說 , H(X) 是　要表示集合中所有 元素時　所需之最小　bits 數 . 2. 根據實驗 (對某一字典), 若考慮機率, 英文的 r 值是 介於 1.0 與 1.5 間. 而反過來看 the absolute rate of the language R ; the absolute rate of the language is defined to be the maximum number of bits of information that could be encoded in each character assuming all possible sequences of characters are equally likely. Thus R = log2 26 = 4.7 bits/letter.

8 3. H(X) 何時最大 ? 何時最小 ? 當 all messages are equally likely 時最大 , 而當 the distribution of messages becomes more and more skewed 時, H(X) 值會小下來 . 當 p(Xi) = 1 時, H(X) = 0 達於最小值 .因此 entropy 越大 ,要猜中該訊息越難. { The entropy of a message measures its uncertainty}  Public-key systems used for secrecy only are vulnerable to a ciphertext-only attack if there is not enough uncertainty in the plaintext. WHY ? If M is known to be an integer salary less than $100,000, and EA is known, then 縱然不知 DA 之值,也可以藉著計算 Ci = EA(Mi) , 然後去找所有密文中之 C = Ci 者, 進而對應出 M = Mi . 為了防止此種攻擊,有兩種因應知道: 1. Appending a random bit string to a short message M before enciphering. 2. Mixing the authenticity into the secrecy; i.e., C = EA (DB (M)). The cryptanalyst, lacking DB , cannot search the plaintext space.

9  The uncertainty of messages may be reduced given additional information.
For example, let X be a 32-bit integer such that all values are equally likely; H(X) = 32, if it is learned that X is even, then the entropy is reduced by one bit since the lower order bit must be 0.  再用理論觀點探討之: Given a message Y in the set Y1 , Y2 , , Ym , where m i=1 p(Yi) = 1, let pY(X) be the conditional probability of message X given message Y, and let p(X, Y) be the joint probability of message X and message Y; thus p(X, Y) = pY(X) p(Y). The Equivocation is the conditional entropy of X given Y: Hy(X) = - X,Y p(X,Y) log 2 pY(X) = X,Y p(X,Y) log 2 (1/pY(X)) =  Y p(Y) X pY(X) log2 (1/pY(X))

10 4: Let n = 4 and p(X)=1/4 for each message X; thus H(X) = log 2 4 = 2. Similarly, let m = 4 and p(Y) = 1/4 for each message Y. Now, suppose each message Y narrows the choice of X to two of the four messages as shown next, where both messages are equally likely: Y1 : X1 or X Y2 : X2 or X Y3 : X3 or X Y4 : X4 or X1 Then for each Y, pY(X) = 1/2 for two of the X’s and pY(X) = for the remaining two X’s. Using the formula shown on preceding page, the equivocation is: Hy(X) = X,Y p(X,Y) log 2 (1/pY(X)) =  Y p(Y) X pY(Y) log2 (1/pY(X)) =  Y (1/4) X (1/2) log2 (2) =  Y (1/4) {2 [(1/2) log2 (2)]} = 4 [ (1/4){1}] = 1.

11 Thus knowledge of Y reduces the uncertainty of X to one bit, corresponding to the two remaining choices for X. 質言之, Y 之訊息降低了 X 的entropy: H(X) = 2 降成 H(X) = 1. Shannon's Theory In 1949, Claude Shannon published a paper entitled “Communication Theory of Secrecy Systems” in the Bell Systems Technical Journal. Perfect secrecy requires that the number of keys must be at least as great as the number of possible messages. Cryptosystems 與下述三者有關: 1. Plaintext messages M occurring with prior probability p(M), where  M p(M) = 1.

12 2. Ciphertext messages C occurring with probability p(C),
where  C p(C) = 1. 3. Keys K chosen with probability p(K), where  K p(K) = 1. 設　pC(M) 表示 取得密文 C 而可以解得明文 M 之機率, 則 perfect secrecy 可定義成 : pC(M) = p(M) 即表示 取得密文無關破解 ! (就是 取得也是白取得) Shannon theorized that it is only possible if the number of possible keys is at least as large as the number of possible messages. In other words, the key must be at least as long as the message itself, and no key can be reused. In still other words, this is a one-time pad. The entropy of a cryptosystem is a measure of the size of the keyspace. It is approximated by the base two logarithm of the number of keys: H(K) = log 2 (number of keys)

13 近代密碼學 最好熟悉 Number Theory 、 Information Theory 、 Complexity Theory 、 Combinatoric Theory 、 Probability 、 and Linear Algebra … etc. Number Theory (1) addition is closed, i.e., for any a,b  Zm, a+b  Zm (3) addition is associative, i.e., for any a,b,c  Zm, (a+b)+c = a+(b+c) (4) 0 is an additive identity, i.e., for any a Zm, a+0 = 0+a = a (5) the additive inverse of any a Zm is m-a, i.e., a+(m-a)=(m-a)+a=0  Properties 1, 3-5 say that Zm forms an algebraic structure called a group with respect to the addition operation.  If property 2 also holds, the group is said to be Abelian(交換).

14 一個集合 F, 若定義於“+”與“·”兩運算上, 且具有下列性質, 則F稱為一個場(Field):
Ｆ在運算“+”上是一個交換群(Abelian Group) F之非零元素在“·”上也是交換群(注意有乘法反元素存在) F滿足“· ”對“+”之分配律(Distributed Law); 即 　　a · (b + c) = a · b + a · c Finite Field: 若 F 之元素個數有限,則稱之為 Finite Field 同餘( congruent ): a n b iff (a-b) = k • n for k I a is congruent to b modulo n.

15 The principle of modular arithmetic
對於同餘之運算 有下列定理 Thm1: a =a mod n (反身性) Thm2: If a = b mod n, then b = a mod n (對稱性) Thm3: If a = b mod n and b = c mod n, then a = c mod n ( 遞移性) Thm4: If a = b mod n and c = d mod n, then a + c = b + d mod n, a – c = b – d mod n ac = bd mod n Thm5: (a + b) mod n = [(a mod n)+(b mod n)] mod n, (a - b) mod n = [(a mod n)-(b mod n)] mod n (a * b) mod n = [(a mod n)*(b mod n)] mod n The principle of modular arithmetic

16 Thm 6: If ac = bd mod n and c = d mod n here (c,n)=1,then
a = b mod n Pf: Since ac = bd mod n, so (ac – bd) mod n = 0 = (a – b) c + b (c – d) mod n. Since c = d mod n, so c – d mod n = 0 and b (c - d) mod n =0. Thus (a – b) c mod n = 0. But (c, n) = 1, so (a – b) mod n = 0. QED

17 所有整數用同餘觀點視之, 被分成 n 個 residue classes(剩餘類); 被 n 整除者之一類,被 n 除之餘數為一之一類,
所有整數用同餘觀點視之, 被分成 n 個 residue classes(剩餘類); 被 n 整除者之一類,被 n 除之餘數為一之一類, ,被 n 除之餘數為 n-1 之一類. 若從每一剩餘類中取一數為代表,組成之集合謂之 complete set of residues (完全剩餘系); 表示成 Zn . 最不需要計算成本考量下, Zn = {0, 1, 2, , n-1 } 若對Zn集合再加上一個限制; 即將所有與 n 互質之剩餘類,從中取一數為代表,組成之集合謂之 reduced set of residues (縮剩餘系); 表示成 Zn* . 若 n = 10 , 同樣在最不需要計算成本考量下, Z10* = {1, 3, 7, 9} Why bother to define the “reduced set of residues” ? 因為自Zn*取任一數 a , 則必存在唯一數 b (也是集合Zn*中之元素) 使得 ab = 1 mod n. 譬如:

18 由於 ab = 1 mod n 可知 b 是 a 的乘法反元素( b = a-1 )
b: x x x x x x 9 由於 ab = 1 mod n 可知 b 是 a 的乘法反元素( b = a-1 ) 當 n 是質數,則 Zn* = Zn – { 0 } = { 1, 2, , n-1 } 此時也能滿足 ab = 1 mod n . 茲此, 下一定理誕生焉 Thm7: If (a, n)=1, then there uniquely exists one integer b, 0<b<n, and (b,n) = 1 such that ab = 1 mod n. Def: The Euler totient function (n)即 the reduced set of residues mod n之元素個數.所以當n是質數時, (n) ＝ n-1; 即　{ 1,2, …, n-1}.

19 Thm9: (Euler’s Generalization):
Thm8: Let {r1, r2, ,r(n)} be a reduced set of residues of mod n, and (a,n)=1, then {ar1, ar2,. . . ,ar(n)} is a reduced set of residues of mod n too. Thm9: (Euler’s Generalization): 對每一對 a與 n, gcd(a, n)=1, 則 a(n) mod n = 1. Review Thm7, we realize b should be a(n) –1. 例: 對 mod 8 而言,{1,3,5,7}是一個縮剩餘系, 根據定理8, {3*1, 3*3, 3*5, 3*7}也是一個縮剩餘系, 據此 (3*1)(3*3)(3*5)(3*7) = 1*3*5*7 mod 8 34 (1*3*5*7) = 1*3*5* mod 8 34 =3(8) = mod (定理9)

20 Please take this subject home for fun.
Thm10:( Fermat’s Theorem): Let P be prime, then for every a s.t. (a, P) = 1, aP-1 mod p = 1. 若 (a, n)=1, 如何求 a 的乘法反元素 b 使 ab =1 mod n ? Ans: (法1) 若(n) 已知,則b=a(n)-1 . (法2)不必求(n) ,而是求 b = a –1 mod n = s such that s a + t n = 1; 如何求 s? 請聽細述如下: gcd(a,n) 之求解 可利用輾轉相除法如下得; 但RSA之情況是ed=1 mod (n) 務必知道(n) 才能計算出 d Please take this subject home for fun.

21 Let n ≤ a, r0 = a, r1 = n, thus r0 = r1 g1 + r ≤ r2 < r1 r1 = r2 g2 + r ≤ r3 < r2 . rm-2 = rm-1 gm-1 + rm ≤ rm < rm-1 rm-1 = rm gm 因此 (a,n) = rm 上述 Euclidean Alg. 之主要觀念在於 If c = d g + r, then (c, d) = (d, r).

22 Now (a,n) = (r0 , r1 ) = (r1 , r2 ) = . . . = (rm-1 , rm ) = (rm , 0 ) = rm
存在 一數 s 使得 (a,n) = s a + t n ? (即 找 a, n 之線性組合) By observations , rm = (a,n) = rm-2 - rm-1 gm-1 (看上一頁) = rm-2 – (rm-3 - rm-2 gm-2) gm-1 = (1+ gm-1 gm-2 ) rm-2 – gm-1 rm-3 知 (a, n) 是 rm-2 與 rm-3之線性組合; 反推第一行之式可得 (a,n) = s a + t n . If (a, n) = 1, then 1 = s a + t n , therefore, s a = 1 mod n, thus s = a-1 mod n. rm-2 = rm-1 gm-1 + rm ≤ rm < rm-1

23 RSA 務必知道 (n) 方能從 e 求解 d , 但 (n) 僅CA知道.
若不考慮空間,則法1平均需 1.5 log2n –2 次乘法,而法2則需 ln(n) 次除法. 故法2稍佳 ! (by Knuth) Thm11 (RSA 加解密法乃此定理之一特例) 令 n > 0 且 (e, (n) )=1, 設 d 滿足 e d = 1 mod (n) . 令 E(M) = Me mod n = C 且 D(C) = Cd mod n = M, 則 D(E(M)) = E(D(M))= M mod n. RSA 務必知道 (n) 方能從 e 求解 d , 但 (n) 僅CA知道. 此定理之詳實板請參考次頁

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

25 Def: (linear congruence in one variable)單變數線性同餘式
已知整數 a, b 及 n>0, x 為變數(看成欲求解者),則 a x = b mod n 謂之.(若b=1則是Thm 7矣) Thm12: 令 a, b 及 n 為整數, 且 n>0 及 (a, n) = d; (1) 若 d ∤b , 則 a x = b mod n 無解. (2) 若 d | b , 則 a x = b mod n 恰有d個模n之解 PS: 當 d=1, 則 x 有唯一解 ! 求解此d個解請參考CC著作.

26 by Thm 7 孫子算經: 今有物不知其數,三三數之賸二,五五數之賸三,七七數之賸二,問物幾何?
孫子算經: 今有物不知其數,三三數之賸二,五五數之賸三,七七數之賸二,問物幾何? In other words, to find an integer x such that x = 2 mod 3, and x = 3 mod 5, and x = 2 mod 7. Thm13: (Chinese Remainder Theorem; CRT by Sun Tse) 若 n1, n2, . . ., nt 為 coprimes, 令 N = n1 n nt . 則下列同餘系統中: x = a1 mod n1, x = a2 mod n2, , x = at mod nt, x 在 [0, N-1]中有唯一解. Pf: ( x = ? ) 因 n1, n2, . . ., nt 為 coprimes,故 (ni, N/ni) = 1, 必存在 yi 使得 (N/ni) yi = 1 mod ni.若 (a, n)=1, 如何求 a 的乘法反元素 b 使 ab =1 mod n by Thm 7

27 embedding (N/ni) 是 nj 的倍數
求出 t 個 yi 後, 由於 (N/ni) yi = 0 mod nj. 此處 j ≠ i. 因此 若令 x = (N/n1) y1 a1 + (N/n2) y2 a (N/nt) yt at mod N = ∑i=1t (N/ni) yi ai mod N ∀i , x mod ni = ai , since (N/ni) yi = 1 mod ni.兩邊均乘以 ai 得 (N/ni) yi ai = ai mod ni ( x 之唯一性 ?) 設若 有 x 與 z 兩個解; ∀i , x = z = ai mod ni , 故 ni | (x – z) ∀i , 所以 N | (x – z) ; 此即 x = z mod N. QED embedding

28 find an integer x such that
x = 2 mod 3, and x = 3 mod 5, and x = 2 mod 7 ? Ans: N = 3 * 5 * 7 = 105 因 (N/ni) yi = 1 mod ni.若 (a, n)=1, 如何求 a 的乘法反元素 b 使 ab =1 mod n 故 (105/3) y1 = 1 mod 3, 故 y1 = aΦ(3)-1 = (105/3) 2-1 mod 3 = 2. 同理, y2 = aΦ(5)-1 = (105/5) 4-1 mod 5 = 1 y3 = aΦ(7)-1 = (105/7) 6-1 mod 7 = 1, 最後, x = 35*2*2 + 21*1*3 + 15*1*2 mod 105 = mod 105 = 23.

29 Quadratic Residue(二次剩餘)
Def: 若 a, n 為正整數 , 且 (a, n) = 1, 滿足 x2 = a mod n 有解, 則 稱 a 是模n之二次剩餘(Quadratic Residue of n). 否則, a 稱為模n之非二次剩餘(Quadratic Non-Residue of n). 以QRn 表示所有模n之二次剩餘的集合. 以QNRn 表示所有模n之非二次剩餘的集合. 例: 若 n=7, 則 QR7 = {12 ,22 , ,42 ,52 ,62 } mod 7 = {1, 2, 4} 當然,QNR7 = {3, 5, 6}. to be continued . . .

30 應用實例 (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 non-residue mod p. 方法簡介: 令明文M=m1m2…mk 其中mi是一個位元非0即1。

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