RSA-256bit Digital Circuit Lab TA: Po-Chen Wu

Outline Introduction to Cryptography RSA Algorithm Montgomery Algorithm for RSA-256 bit

Introduction to Cryptography

Communication Is Insecure Alice Bob Paparazzi

Secure Approach: Cryptosystems Alice Bob Paparazzi

Cryptosystems Encryption Scheme Decryption Scheme Alice Bob Encryption Key Decryption Key

Encryption vs. Decryption Only Bob knows the decryption key. Encryption Key Only Alice and Bob know the encryption key: PRIVATE cryptosystem Everyone knows the encryption key: PUBLIC cryptosystem RSA is a public cryptosystem.

RSA Algorithm

RSA Cryptosystem If Bob wants to use RSA, he needs to select a key pair, and announce the encryption key. If Alice wants to communicate with Bob, she needs to use the encryption key announced by Bob. If Bob wants to receive messages from the others, he needs to use the decryption key he selected.

How to Select a key pair Key pair selection scheme: Bob (randomly) selects 2 prime numbers p and q. For security reason, p = 2p' + 1 and q = 2q' + 1, where p' and q' are also prime numbers. Bob evaluates n = pq and Ф(n) = (p −1)(q − 1) Bob chooses e such that gcd(e, Ф(n)) = 1 Bob finds the integer d (0 < d < Ф(n)) such that ed − kФ(n) = 1 Finally, Bob announces the number pair (n, e) and keeps (d, p, q, Ф(n)) in secret. Euler's totient or phi function, Ф(n) counts the integers between 1 and n that are coprime to n. Ф(p) = p − 1, Ф(q) = q − 1 Ф(pq) = (p − 1)(q − 1)

How to Encrypt Encryption Scheme: Whenever Alice wants to tell Bob m which is less than n, she evaluate c = me mod n, where n and e are the numbers Bob announced. Then Alice sends c to Bob.

How to Decrypt Decryption Scheme: Why the decryption scheme work? Whenever Bob receives an encrypted message c, he evaluate m' = cd mod n Fact: m' = m Why the decryption scheme work? Euler's theorem: if gcd(a, n)=1, aФ(n) mod n = 1 cd mod n = (me mod n) d mod n =(me)d mod n = med mod n = mkФ(n)+1 mod n =(mk)Ф(n)m mod n = m Hard to calculate! 這裡的a (a.k.a. mk) 也有可能使得gcd(a, n)!=1 但機率實在是低得離譜，大概是(2^128+2^128-1)/2^255 也就是1/2^127 左右 而駭客只要把d找出來就可以得到m 要找d就要解出ed − kФ(n) = 1 要解上述式子就得知道Ф(n)長怎樣 而要知道Ф(n)必須將n拆成p&q 所以只要能將n拆成p&q，就能破解RSA了 所以p&q要夠大夠複雜，n才不好拆，d才難求

Montgomery Algorithm for RSA-256 bit

Inverse (1/4) For real number, x and y are the inverse of each other if We write y = x−1, and vice versa. When we say a divided by b, or a / b, we mean that a multiplied by b−1. In the “world” of “modulo N,” we want to define the inverse (and then the division operator / ) such that the exponential laws hold. xy = 1

Inverse (2/4) For a positive integer x (< N), We define the inverse of in the “world” of “modulo N” is the positive integer y (< N) such that We write y = x−1, and vice versa. We define the “division” in the “world” of “modulo N” as xy mod N = 1 在mod的世界裡，正整數x的inverse，是一個正整數叫做y 這個y能夠使得xy mod N = 1 我們可以寫做y = x−1(所以x−1是一個正整數!) 而所有的division我們都要看成是 x / y mod N = xy−1 mod N 而y−1是一個正整數 (這樣就不會有分數的情況出現了) x / y mod N = xy−1 mod N

Inverse (3/4) Theorem: If b = an, then b / a mod N = n. Example: a = 2, N = 35, then a−1 = 18 b = 12 = 2 * 6, b / a mod N = ba−1 mod N = 12 * 18 mod 35 = 216 mod 35 = 6

Inverse (4/4) Another example: a = 2, N = 35, then a−1 = 18 b = 13 b / a mod N = ba−1 mod N = 13 * 18 mod 35 = 234 mod 35 = 24 or b / a mod N = (b + N) / a mod N = (13 + 35 ) / 2 mod 35 = 24 所以計算b / a mod N 有兩種方法 ba−1 mod N (b直接成a−1) (b + kN) / a mod N , k ∈ integer (把b + kN弄成是a的倍數直接除，不用真的做mod)

MSB-Based Modular Multiplication We want to evaluate V ≡ AB (mod N), where A = 2n-1an-1+2n-2an-2+…+2a1+a0 We can find that V ≡ {2[…(2(2an-1B + an-2B) + an-3B) + …+ a1B] + a0B} The Algorithm for MSB-Based Modular Multiplication Vn ← 0 for i = n − 1, …,1,0 Vi ← (2Vi+1 + ai．B) mod N 2Vi+1 + aiB < 3N

Square and Multiplication Algorithms for Modular Exponentiation Evaluate S = Me mod N where exponent e=(1ek-2…e1e0) No need to be k bit MSB-ME( Me mod N) S ← M for i = k − 2, …,1,0 S ← (S．S) mod N if (ei = 1) S ← (S．M) mod N LSB-ME(Me mod N) S ← 1, T ← M for i = 0,1,…, k − 1 if (ei = 1) S ← (S．T) mod N T ← (T．T) mod N LSB是比較直覺的想法，T是temp的意思，每次T是M^1, M^2, M^4, 然後看S要不要乘(如果e_i = 1就乘T) MSB比較潮，因為一開始一定是1，所以可以省一次，S一開始就是M，然後會變成M^2, M^4,…，中間如果遇到e_i = 1就乘個M (所以之後可能變成M^3這樣) (A·B) mod N is still hard to implement

Montgomery Algorithm Idea: Trying to compare Vi with N costs a lot. Idea: How about LSB first to evaluate the multiplication? mod不是那麼好計算的

Montgomery Algorithm: Phase 1 Evaluate Vn=(A·B·2-n) mod N A．B．2-n = B．2-n．(2n-1an-1+2n-2an-2+…+2a1+a0 ) = B．(2-1an-1+2-2an-2+…+2-(n-1)a1+2-na0 ) = 2-1(an-1B +2-1(an-2B+…+2-1(a1B+2-1a0B)…)) V0 ← 0 for i = 0,1,…, n−1 Vi+1 ← Vi + aiB 2 mod N Vi+ aiB 2 mod N = Vi+ aiB+qiN 2 , qi = LSB of (Vi+ aiB) 在mod的世界裡，/2不是真的除2 因為 Vi +aiB 2 一定會小於N，所以 1. 若是Vi+ aiB為2的倍數，那 Vi+aiB 2 mod N 就是 Vi+aiB 2 2. 但若Vi+ aiB不是2的倍數，怎麼辦? 其實就是直接把Vi+ aiB再加N後一起除2就好 因為有沒有加N，最後做mod時結果應該是要一樣的，但是由於Vi+aiB+N會是2的倍數，所以好處理很多 可是 Vi+ aiB+qiN 2 可能會大於N，就不是真的 Vi+ aiB 2 mod N 的解，怎辦? 其實就是最後再檢查就好 (接下頁) LSB modular reduction Vi + aiB 2 mod N is easy!

Montgomery Algorithm: Phase 2 When to substitute? V0 ← 0 for i = 0,1,…, n−1 qi ← (Vi +aiB) mod 2 Vi+1 ← Vi + aiB +qiN 2 if (Vn ≥ N) V ← Vn − N A=(an-1an-2…a1a0)2 , A,B<N V0=0<2N, Vi+1 ≤ Vi + aiB + N 2 < 2N, i=0,1,…,n-1

Montgomery Algorithm: Modified Version (1/2) A．B．2-n = B．2-n．(2n-1an-1+2n-2an-2+…+2a1+a0 ) = B．(2-1an-1+2-2an-2+…+2-(n-1)a1+2-na0 ) = 2-2((2an-1+an-2)B +2-2((2an-3+an-4)B+… + 2-2((2a3+a2)B + 2-2(2a1+a0)B)…)) V0 ← 0 for i = 0,2,…, n−2 Vi+2 ← Vi + 2ai+1B + aiB 4 mod N 另外由於N是p*q = (2p’+1)*(2q’+1) 所以N mod 4 = (4p’ q’+2p’+2q’+1) mod 4 因為p’ mod 4 = 1or3, so 2p’ mod 4 =2 (2p’+2q’) mod 4 = 0 => (4p’ q’+2p’+2q’+1) mod 4 = 1 Vi + 2ai+1B + aiB 4 mod N = Vi + 2ai+1B + aiB + qiN 4 , qi = (ki = 0)? 0: (4−ki), ki = (Vi + 2ai+1B + aiB) mod 4

Montgomery Algorithm: Modified Version (2/2) for i = 0,2,…, n−2 ki = (Vi + 2ai+1B + aiB) mod 4 qi = (ki = 0)? 0: (4−ki); Vi+2 ← Vi + 2ai+1B + aiB + qiN 4 if (Vn ≥ N) V ← Vn − N 因為V_i<2N儲存 所以Vi + 2ai+1B + aiB < 5N -> 要用259bit去存 Vi + 2ai+1B + aiB + (4−ki)N < 8N -> 也是用259bit去存 A=(an-1an-2…a1a0)2 , A,B<N V0=0<2N, Vi+2 ≤ Vi + 2ai+1B+aiB+3N 4 < 2N, i=0,1,…,n-1

Modular Exponentiation Using Montgomery Algorithm (1/2) Observation on Vn = MA(A, B) = (A·B·2-n) mod N Define A' = 2nA mod N (A “packed”) Fact: If V = AB mod N, then V = MA(A', B) Fact: If V = AB mod N, then V' = MA(A', B') Idea: “Pack” the integers we want to evaluate, and use Montgomery Algorithm instead of direct modular multiplication.

Modular Exponentiation Using Montgomery Algorithm (2/2) Evaluate S = Me mod N Constant C = 22n mod N MSB-ME( Me mod N) M ' ← MA(C．M) (pre-processing) S ← M ' for i = k − 2, …,1,0 S ← MA(S．S) if (ei = 1) S ← MA(S．M ') S ← MA(S．1) (post-processing) LSB-ME( Me mod N) T ← MA(C．M) (pre-processing) S ← 1 for i = 0,1,…, k − 1 if (ei = 1) S ← MA(S．T) T ← MA(T．T) 把原本的(A·B) mod N的部份都變成MA()，這樣會好計算許多 另外pre-processing的部份，不用真的實作MA，只要作2nM mod N就可以 (M乘二，檢查是否要減N<-循環) MSB-ME( Me mod N) S ← M for i = k − 2, …,1,0 S ← (S．S) mod N if (ei = 1) S ← (S．M) mod N LSB-ME(Me mod N) S ← 1, T ← M for i = 0,1,…, k − 1 if (ei = 1) S ← (S．T) mod N T ← (T．T) mod N

The End. Any question?

Reference [1] P.L. Montgomery, “Modular multiplication without trial division,”Mathematics of Computation, vol.44, pp.519-521, April 1985.