A Survey of the Security of RSACryptosystem OUTLINE: 1. Introduction: C = Me mod N 2. Attack N 3. Attack C 4. Attack e 5. Attack Protocol 6. RSA參數限制 7. Conclusions 03:16

1. Introduction It is conjectured that the security of RSA depends on the problem of factoring large numbers. [Schneier 96] C = Me mod N 破解程度: (1) get M (2) get secret key p, q or d 03:16

1. Introduction (cont.) 2. Attack N (1) general: factoring methods (2) condition: [Rivest &Shanir 85, Coppersmith 96] 3. Attack C cycling attack: [Simmon & Norris 77] 4. Attack e (1) e/N: [Wiener 90, Chen et al. 96] (2) e, Ci : Hastad attack (in network) [Hastad 88] (3) e, Ci: random padding[Coppersmith 96] (4) e, Ci:related message[Coppersmith 96] 5. Attack protocol (1) timing attack:[Kocher 96] (2) fault-based attack:[Bonch 97] 6. RSA參數限制 7. conclusions 03:16

2. Attack N (cont.) (digit) Franke 160 63bit subexponential Modern Year Franke 160 2003 Cowie 130 1995 Chen Atkins 129 1993 Buhler Denny 120 GNFS 1990 Lenstra Lenstra 107 Lenstra NFS Silverman Lenstra 1987 100 MPQS 1982 Pomerance (digit) QS 1981 Dixon Monte Carlo 1975 Pollard Morrison 63bit subexponential 1974 Pollard Lehmann P-1 1931 Lehmer Modern Implementation Old 03:16

03:16

03:16

Factorization (cont.) Fastest factoring method -Number Field Sieve Each bit operation was estimated as 10-9 seconds. 03:16

Factorization (cont.) Fermat factorization If N = a*b then N = x2 - y2 , where x= (a+b)/2 and y = (a-b)/2. Therefore, x2 - N will be square. To factor N, we search for a square among the sequence of integers t2 - N, (t+1)2 - N, (t+2)2 - N, …, ((N+1)/2)2 - N where t is the smallest integer greater than N1/2. 03:16

Factorization (cont.) Fermat factorization EX: Let N= 6077. Then t  60771/2  78. 782 - 6077 = 7 792 - 6077 = 164 802 - 6077 = 323 812 - 6077 = 484 = 222 Since 6077 = 812 - 222, we see that 6077 = (81-22)(81+22) = 59*103. Worst case: need to check (N+1)/2 -N1/2 integers 03:16

3. Attack C C0 = Me mod N Ck = Ck-1e mod N If Ck = C0 , then M = Ck-1. 重覆加密攻擊法 cycling attack:[Simmon & Norris 77] C0 = Me mod N Ck = Ck-1e mod N If Ck = C0 , then M = Ck-1. Ck-1 = Mek mod N = M ek = 1 mod O(M), where O(M)| (N) (=l.c.m.(p-1,q-1)) k is small why? (1) the order of e modulo (N) is small (2) O(M) of the message is small 03:16

3. Attack C RSA密碼系統重覆加密攻擊法：已知收方之公開金匙(3, 55), 若有一人送一份機密給收方其密文為C=23,，請問原機密為何？ Ans: M = 12 03:16

4. Attack e (1) e/N: continued fraction method Continued Fraction = [ 2, 3, 2, 3] [2, 3] [2, 3, 2, 3] [2, 3, 2] 2 [2] 03:16

4. Attack e Continued Fraction Continued Fraction = [ 2, 3, 2, 3], = [ 2, 3, 2, 2] [2, 3] [2, 3, 2, 2] [2, 3, 2, 3] [2, 3, 2] 2 [2] 03:16

4. Attack e (1) e/N: continued fraction method ed = 1 mod l.c.m.(p-1,q-1) If d < N1/4, then d can be discovered. [Wiener 90] If (N) - N1/4 < d < (N), then d can be discovered. [Chen et al. 96] 03:16

4. Attack e (cont.) (2) Hastad attack:[Hastad 88] k=3 and e=3 (3, N1) C1 = M3 mod N1 C = C1 mod N1 = C2 mod N2 = C3 mod N3 C2 = M3 mod N2 (3, N2) CRT M C < N1N2N3 C3 = M3 mod N3 (3, N3) M = C1/3 If k > e(e-1)/2 then M can be discovered. [Hastad 88] If k >= e then M can be discovered. [Shimizu 96] Ref. [Joye 97] 03:16

4. Attack e (cont.) (2) Hastad attack:[Hastad 88] 中國餘數定理 Define:令n1,n2,…,nt為兩兩互質之正整數,令 N=n1*n2*…*nt. 則以下同餘系統中,x = a1 mod n1 , x = a2 mod n2 ,…x = at mod nt,會在[0,N-1]中有唯一解. Proof:因為n1,n2,…,nt為兩兩互質之正整數.所以 i=0,1,2,…,t. 所以存在yi,使得(N/ni) yi=1 mod ni. 此外(N/ni) yi=1 mod nj,當 j i, (N/ ni) 為nj的倍數. mod N 03:16

4. Attack e (cont.) (2) Hastad attack:[Hastad 88] 中國餘數定理 EX: To solve the system x 1 (mod 3), x 2 (mod 5), x 3(mod 7) Sol: N=3*5*7=105, N1 =105/3, N2 =105/5=21, N3 =105/7=15. 35y1 1 (mod 3) y1 2 (mod 3) 21y2 1 (mod 3) y2 1 (mod 3) 15y3 1 (mod 3) y3 1 (mod 3) x 1*35*2+2*21*1+3*15*1 157 52 (mod 105) 03:16

4. Attack e (cont.) (2) Hastad attack:[Hastad 88] RSA密碼系統：已知3 users之公開金匙分別為(e1, N1)=(3, 87), (e2, N2)=(3, 115), (e3, N3)=(3, 187), 若有一人送同一份機密給這三個users其密文分別為C1=82, C2=113, C3=156，請問原機密為何？ Ans: M = 7 03:16

4. Attack e (cont.) (3) e, Ci: 附加亂數攻擊法 [Coppersmith 96] 方法: p(x) =0 mod N, degree(p(x))=k If there is a root x0<N1/k , then x0 can be discovered by LLL algorithm from polynomials qij(x)=xi p(x)j mod Nj 應用:RSA with random padding 相同M送兩次 C1 = (2hM+t1)3 mod N = m3 mod N C2 = (2hM+t2)3 mod N = (m+t)3 mod N 則計算 Resultantm (m3 - C1 , (m+t)3 - C2) t9 +(3C1- 3C2)t6 +(3C12+21C1C2+3C22)t3 +(C1- C2)3 = 0 mod N get M If t < N1/9 , get t. 03:16

4. Attack e (cont.) (4) e, Ci: 相關明文攻擊法 [Coppersmith 96] 已知: e, N, k ciphertexts and polynomial relationship among the messages 解出: all messages 特例:[Franklin & Reiter 95] k=2, e=3, M1與M2關係為 M2=AM1+B 已知: e, N, A, B, C1 = M13 mod N, C2 = M23 mod N 則計算 B(C2 + 2A3C1 -B3)/A(C2 - A3C1 + 2B3) =( 3A3BM13+3A2B2M12 +3AB3M1)/ (3A3BM12+3A2B2M1 +3AB3) = M1 03:16

5. Attack Protocol (1)相同模數攻擊法 選定一RSA模數N，給予不同使用者（ei, di），其中eidi = 1 mod (N)，然而使用者並不知道模數N的質因數p和q。 優點是:易於金匙管理且沒有reblocking的問題 缺點是:不安全  相同明文送給系統兩個不同使用者，第三者將可解出該明文 假設相同明文M送給系統兩個不同使用者U1和U2，其對應的密文分別為C1 = Me1 mod N和C2 = Me2 mod N。第三者可從網路上獲得C1和C2以及e1和e2，由於e1和e2互質，則可以利用歐幾里德演算法求出整數x和y滿足xe1+ ye2 = 1，其中有一整數為負數。然後，第三者計算 C1xC2y = Mxe1+ye2 = M mod N， 03:16

5. Attack Protocol (1)相同模數攻擊法  使用者擁有一對加解密金匙，可以因數分解N 假設使用者U1擁有一對加解密金匙（e1, d1），則滿足e1d1 = 1 + k(N)，其中k為一整數。若使用者U1想要求得使用者U2的私密金匙d2，則先計算出g = gcd(e2, e1d1 - 1)，然後得到f = (e1d1 - 1)/g，由於(N)整除(e1d1 - 1)，所以f為(N)的整數倍。最後我們得到私密金匙d2為e2對f的乘法反元素 03:16

5. Attack Protocol (2)時間攻擊法 Timing Attack [Kocher 96] M = Cd mod N /* k: the length of d */ 運算過程: S0 = 1; for i := 0 to k-1 do begin if di = 1 then R = Si*C mod N else R = Si Si = R2 mod N end; Note: If di = 1, needs more time. If di = 0, needs less time. 收集幾組C值猜出正確的d值 03:16

5. Attack Protocol (cont.) 防制之法: <1>all operations have same time <2>error timing measurement randomly add useless operations <3> blinding hard randomness disappears for more C’s find a pair (u, v) such that v =(u-1)e mod N Encryption: C’ = v*Me mod N Decryption: M = u*(C’)d mod N 03:16

5. Attack Protocol (cont.) (3)植基於故障攻擊法 Fault-Based Attack [Boneh 97] 利用random hardware faults攻擊 以CRT方法的RSA signature 已知 a = 1 mod p and b = 0 mod p where N=p*q = 0 mod q = 1 mod q Compute S =(M)d mod N <1> S1 = Md mod p <2> S2 = Md mod q <3> S = a*S1 + b*S2 mod N 此運算比原指數運算S =(M)d mod N快 03:16

5. Attack Protocol (cont.) 破解方法: <1> signature 兩次 運算過程中: S1 or S2 error, say S1 S = a*S1 + b*S2 mod N ----- correct S’ = a*S1’ + b*S2 mod N ----- error S - S’ = a*(S1 - S1’) mod p implies g.c.d.(S-S’, N) = q <2> signature 一次 because (S)e mod N = M g.c.d.(M - (S’)e , N) = q 克服方法: 計算signature 必須驗証無誤後才能釋出 03:16

7. Conclusions It is conjectured that the security of RSA depends on the problem of factoring large numbers. [Schneier 96] Breaking RSA may not be equivalent to factoring [Boneh & Venkatesan] 03:16