Public-Key Cryptography: RSA (Rivest, Shamir, Adleman)
Sender uses a public key
» Advertised to everyone
Receiver uses a private key
Plaintext Plaintext
Encrypt with Internet Decrypt with
public key private key
Ciphertext
Asymmetric Encryption
Gives 'one-way' security.
Two keys generated, one used with decryption
algorithm (private key) and one with encryption
algorithm (public key).
Generation of private key, given public key is
computationally hard.
Does not need secure key transmission
mechanism for key distribution.
The RSA Algorithm
Based on the idea that factorization of integers
into their prime factors is hard.
★ n=p . q, where p and q are distinct primes
Proposed by Rivest, Shamir, and Adleman
in 1977 and a paper was published in The
Communications of ACM in 1978
A public-key cryptosystem
RSA Algorithm
Bob chooses two primes p,q and compute
n=pq
Bob chooses e with gcd(e,(p-1)(q-1))=
gcd(e, ψ(n))=1
Bob solves de≡1 (mod ψ(n))
Bob makes (e,n) public and (p,q,d) secret
Alice encrypts M as C≡Me (mod n)
Bob decrypts by computing M≡Cd (mod n)
RSA Algorithm
Generating the private and public key
requires four steps:
Choose two very large prime numbers, p and q
Compute n = p x q and z = (p – 1) x (q – 1)
Choose a number d that is relatively prime to z
Compute the number e such that e x d = 1 mod z
Generating Public and Private Keys
Public key consist of pair (n, e)
Private key consists of pair (n, d)
RSA Encryption and Decryption
Encryption of message block m:
» c = me mod n
Decryption of ciphertext c:
» m = cd mod n
Example (1/2)
Choose p = 7 and q = 11 n = p*q = 77
Compute encryption key e: (p-1)*(q-1) = 6*10
= 60 chose e = 13 (13 and 60 are
relatively prime numbers)
Compute decryption key d such that 13*d = 1
mod 60 d = 37 (37*13 = 481)
Example (2/2)
n = 77; e = 13; d = 37
Send message block m = 7
Encryption: c = me mod n = 713 mod 77 = 35
Decryption: m = cd mod n = 3537 mod 77 = 7
Properties
Confidentiality
A receiver B computes n, e, d, and sends out (n, e)
» Everyone who wants to send a message to A uses (n,
e) to encrypt it
How difficult is to recover d ? (Someone that can do
this can decrypt any message sent to B!)
Recall that
d is relatively prime to (p-1)*(q-1)
So to find d, you need to find prime factors p and q
» This is provably very difficult
Example
Perform encryption and decryption using the RSA
algorithm, for the following:
a) p=3; q=11; e=7; M=5
b) p=5; q=11; e=3; M=9
c) p=7; q=11; e=17; M=8