RSA Preliminaries Division Algorithm Given integers a and b≠0, there exist unique Integers q and r such that a = bq +r where 0 ≤ r < |b| a is the dividend, b is the divisor, and r is the remainder. b divides a or b is a factor of a if r=0. Greatest Common Divisor The greatest common divisor of two nonzero integers a and b is defined to be the largest positive integer that divides (i.e., is a factor of) both a and b. The greatest common divisor of a and b is denoted by gcd(a,b). We say that a and b are relatively prime if gcd(a,b)=1. The Euclidean Algorithm EUCLID(a,b) if b=0 then return a else return EUCLID(b, a mod b) A useful relation Fact: If d = gcd(a,b), then there exist unique integers x and y such that d = ax + by x and y can be found using the “extended Euclidean algorithm” Euler’s phi function • For any positive integer n, φ(n) (Euler’s phi function) is defined to be the number of positive integers less than n that are relatively prime to n. • φ(n) = nπp|n(1-1/p), (where p runs through all prime factors of n) • Note that if p is prime, then φ(p) = p-1. The Theorems of Euler and Fermat • Euler’s Theorem aφ(n) = 1 mod n for all a in Zn* , where Zn* is the set of all a in Zn such that gcd(a,n)=1 • Fermat’s Theorem If p is prime, then ap = a mod p for all a in Zp and if gcd(a,p)=1, ap-1 = 1 mod p for all a in Zp* The Chinese Remainder Theorem • Suppose n1, n2, …, nk are positive integers which are pairwise relatively prime. Then, for any given integers a1,a2, …, ak, there exists an integer x solving the system of simultaneous congruences x = a1 mod n1 x = a2 mod n2 All solutions are … congruent modulo x = ak mod nk N=n1n2 … nk Public-key Cryptosystems • Each participant has a public key and a secret key. • Every public and secret key is a one-toone function from the set D to D, where D is the set of permissible messages. • Alice: PA, SA Bob: PB,SB Sending a Message Bob uses Alice’s public key to send an encrypted message M to Alice. C = PA(M) M -> PA -----------------------------> SA -> M communication channel Alice uses her secret key to decrypt M Public and Secret keys are Matched Pairs E.g., M=SA(PA(M)) = PA(SA(M)) Digital Signatures Suppose Alice wished to send Bob a digitally signed response M’ 1. Alice computes her digital signature for the message M’: σ = SA(M’) 2. Alice sends the pair (M’, σ) to Bob. 3. When Bob receives (M’, σ) , he can verify that it originated from Alice by verifying that M’ =PA (σ ) The RSA Cryptosystem A participant creates his public and secret keys as follows: 1. Select an random two large primes, p and q 2. Compute n = pq. 3. Compute e that is relatively prime to φ(n)=(p-1)(q-1) 4. Compute the modulo φ(n) inverse d of e. 5. Publish the pair P=(e,n) as RSA public key. 6. Keep secret the pair S=(d,n) as RSA secret key. The domain D of messages is Zn The transformation of a message M associated with a public key P=(e,n) is P(M)=Me and the transformation of a “ciphertext” C associated with a secret key S=(d,n) is S(C)=Cd The Correctness of RSA • SA(PA(M)) = Med=Mde=PA(SA(M)) • We have ed = 1 mod (p-1)(q-1). This means that when ed is divided by (p-1)(q-1), the remainder is 1 and so by the division algorithm, ed = k(p-1)(q-1)+1 for some k. • Thus, Med = M1+k(p-1)(q-1)=M M(p-1)k(q-1) =M(1)k(q-1) mod p (by Fermat’s theorem) =M mod p if gcd(M,p)=1. The Correctness of RSA 2 • Also, Med = M1+k(p-1)(q-1)=M M(q-1)k(p-1) =M(1)k(p-1) mod q (by Fermat’s theorem) =M mod q if gcd(M,q)=1 Thus, Med =M mod p Med =M mod q These two congruences hold even when either p or q is not relatively prime to M and so Med =M mod n (by the Chinese Remainder Theorem) Example (for an extremely simple, breakable code) • Suppose that Alice chooses p=7, q=11 and e=13. Then PA = (13,77) and d=37 since 13*37=1 mod 60 and so her secret key is SA = (37,n). Suppose that Bob wants to send 52 to Alice. What is the encrypted message? Encrypted message • Bob uses Alice’s public key to encrypt his message: • 5213 = 17 mod 77 Decrypted message • Alice receives the encrypted message 17. • Alice uses her secret key (37,77) to decrypt Bob’s message 1737 = 52 mod 77 Verification • Suppose that Alice wants to verify to Bob that she received his message. • She sends encodes the message she received with her secret key and sends it to Bob: 5237 = 24 mod 77 Bob uses Alices’s public key to obtain 2413 = 52 mod 77 Breaking the code • Messages encrypted with RSA can be decrypted by determining primes p and q such that n=pq since in that case a d can be determined such that de = 1 mod φ(n) Asignment • Write an openMP program such that given an integer n, the program determines two primes p and q such that n = pq, if such primes exist.