RSA

Asymmetric Keys

 Two related keys, a public key and a private key, that are used to perform
complementary operations, such as encryption and decryption or
signature generation and signature verification.
Private-Key Cryptography

 traditional private/secret/single key cryptography uses one key

 shared by both sender and receiver
 if this key is disclosed communications are compromised
 also is symmetric, parties are equal
 hence does not protect sender from receiver forging a message &
claiming is sent by sender
Public-Key Cryptography

 probably most significant advance in the 3000 year history of

cryptography
 uses two keys – a public & a private key
 asymmetric since parties are not equal
 uses clever application of number theoretic concepts to function
 complements rather than replaces private key crypto
Why Public-Key Cryptography?

 developed to address two key issues:

 key distribution – how to have secure communications in general without having to
trust a KDC (Key Distribution Center) with your key
 digital signatures – how to verify a message comes intact from the claimed sender
 public invention due to Whitfield Diffie & Martin Hellman at Stanford Uni in 1976
 known earlier in classified community
Public-Key Cryptography

 public-key/two-key/asymmetric cryptography
involves the use of two keys:
 a public-key, which may be known by anybody, and can
be used to encrypt messages, and verify signatures
 a private-key, known only to the recipient, used to
decrypt messages, and sign (create) signatures
 is asymmetric because
 those who encrypt messages or verify signatures cannot
decrypt messages or create signatures
Public-Key Cryptography

 public-key/two-key/asymmetric cryptography involves the use of two

keys:
 a public-key, which may be known by anybody, and can be used to encrypt
messages, and verify signatures
 a private-key, known only to the recipient, used to decrypt messages, and sign
(create) signatures
 is asymmetric because
 those who encrypt messages or verify signatures cannot decrypt messages or
create signatures
Public-Key Cryptography
Public-Key Cryptography
Public-Key Characteristics

 Public-Key algorithms rely on two keys where:

 it is computationally infeasible to find decryption key
knowing only algorithm & encryption key
 it is computationally easy to en/decrypt messages
when the relevant (en/decrypt) key is known
 either of the two related keys can be used for
encryption, with the other used for decryption (for
some algorithms)
Public-Key Characteristics

 Public-Key algorithms rely on two keys where:

 it is computationally infeasible to find decryption key knowing only algorithm &
encryption key
 it is computationally easy to en/decrypt messages when the relevant
(en/decrypt) key is known
 either of the two related keys can be used for encryption, with the other used
for decryption (for some algorithms)
Public-Key Cryptosystems
Public-Key Applications

 can classify uses into 3 categories:

 encryption/decryption (provide secrecy)
 digital signatures (provide authentication)
 key exchange (of session keys)
 some algorithms are suitable for all uses, others are specific to one
Security of Public Key Schemes

 like private key schemes brute force exhaustive search attack is always
theoretically possible
 but keys used are too large (>512bits)
 security relies on a large enough difference in difficulty between easy
(en/decrypt) and hard (cryptanalyse) problems
 more generally the hard problem is known, but is made hard enough to be
impractical to break
 requires the use of very large numbers
 hence is slow compared to private key schemes
RSA

 by Rivest, Shamir & Adleman of MIT in 1977

 best known & widely used public-key scheme
 based on exponentiation in a finite (Galois) field over integers modulo a
prime
 nb. exponentiation takes O((log n)3) operations (easy)
 uses large integers (eg. 1024 bits or 309 decimal digits)
 security due to cost of factoring large numbers
 nb. factorization takes O(e log n log log n) operations (hard)
RSA Algorithm

 It uses expressions with exponentials.

 Plaintext is encrypted in blocks, where block size 𝑃 is less than or equal to
log 2 𝑛 + 1
 If block size 𝑃 < 𝑛 = 𝑖 then 2𝑖 < 𝑛 ≤ 2𝑖+1
 Encryption: 𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑛
 Decryption: 𝑀 = 𝐶 𝑑 𝑚𝑜𝑑 𝑛 = 𝑀𝑒 𝑑
𝑚𝑜𝑑 𝑛 = 𝑀𝑒𝑑 𝑚𝑜𝑑 𝑛
 Public key 𝑃𝑈 = 𝑒, 𝑛
 Private key 𝑃𝑅 = 𝒅, 𝑛
Finding e and d

 𝑀𝑒𝑑 mod 𝑛 = 𝑀 can be realized if 𝑒 and 𝑑 are multiplicative inverses

modulo 𝜙 𝑛 where
 𝜙 𝑛 is the Euler totient function
 𝜙 𝑛 = 𝑝𝑞 = 𝑝 − 1 𝑞 − 1
 𝑝 and 𝑞 are primes
 𝑒𝑑 mod 𝜙 𝑛 = 1
 𝑒𝑑 ≡ 1 mod 𝜙 𝑛 = 1 These are true only if 𝑒 and 𝑑 are relatively prime to 𝜙 𝑛
 𝑑 = 𝑒 −1 mod 𝜙 𝑛 = 1
RSA | Ingredients

 𝑝, 𝑞, two prime numbers (Private, chosen)

 𝑛 = 𝑝𝑞 (Public, calculated)
 𝑒 such that gcd 𝜙 𝑛 , 𝑒 = 1 where 1 < 𝑒 < 𝜙(𝑛) (Public, chosen)
 𝑑 = 𝑒 −1 (𝑚𝑜𝑑 𝜙 𝑛 ) (Private, calculated)
RSA Example - Key Setup

1. Select primes: 𝑝 = 17 & 𝑞 = 11

2. Compute 𝑛 = 𝑝𝑞 = 17 × 11 = 187
3. Compute 𝜙 𝑛 = 𝑝– 1 𝑞 − 1 = 16 × 10 = 160
4. Select 𝑒: gcd 𝑒, 160 = 1; choose 𝑒 = 7
5. Determine 𝑑: 𝑑𝑒 = 1 mod 160 and 𝑑 < 160
1. The Value is 𝑑 = 23 since 23 × 7 = 161 = 10 × 160 + 1
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}
RSA Example - En/Decryption

 sample RSA encryption/decryption is:

 given message 𝑀 = 88 (note that 88<187)
 encryption:
𝐶 = 887 mod 187 = 11 882 mod 187 = 77
884 mod 187 = 132
887 mod 187 = 884 mod 187 882 mod 187 881 mod 187 mod 187
887 mod 187 = 132 × 77 × 88 mod 187 = 11
 decryption:

𝑀 = 1123 mod 187 = 88

Exponentiation in Modular Arithmetic

 We know that 𝑎𝑏 mod 𝑛 = 𝑎 mod 𝑛 𝑏 mod 𝑛 mod 𝑛

 So, 𝑎2 mod 𝑛 = 𝑎 mod 𝑛 𝑎 mod 𝑛 mod 𝑛
 What about 𝑎16 mod 𝑛
 Can be calculated by successively forming 𝑎2 , 𝑎4 , 𝑎8 , 𝑎16 ,
 More generally, we can find 𝑎𝑏 mod 𝑛 as follows
 If 𝑏 = 𝑏𝑘 𝑏𝑘−1 … . . 𝑏0 2 in binary then 𝑏 = σ𝑏𝑖 ≠0 2𝑖
𝑖
∴ 𝑎𝑏 mod 𝑛 = ෑ 𝑎2 mod 𝑛 mod 𝑛
𝑏𝑖 ≠0
Exponentiation in Modular Arithmetic

 More generally, we can find 𝑎𝑏 mod 𝑛 as follows

 If 𝑏 = 𝑏𝑘 𝑏𝑘−1 … . . 𝑏0 2 in binary then 𝑏 = σ𝑏𝑖 ≠0 2𝑖
𝑖
∴ 𝑎𝑏 mod 𝑛 = ෑ 𝑎2 mod 𝑛 mod 𝑛
𝑏𝑖 ≠0
Efficient Encryption

 encryption uses exponentiation to power e

 hence if e small, this will be faster
 often choose 𝑒 = 65537 (216 + 1)
 also see choices of e=3 or e=17
 but if 𝑒 too small (eg 𝑒 = 3), it is then vulnerable to attack
 using Chinese remainder theorem & 3 messages with different modulii
 if 𝑒 fixed must ensure gcd 𝑒, 𝜙 𝑛 =1
 ie reject any 𝑝 or 𝑞 not relatively prime to 𝑒
Efficient Decryption

 decryption uses exponentiation to power 𝑑 (ie 𝑀 = 𝐶 𝑑 mod 𝑛)

 this is likely large, insecure if not
 can use the Chinese Remainder Theorem (CRT) to compute mod p & q
separately. then combine to get desired answer
𝑀 = 𝐶 𝑑 mod 𝑛 = 𝑉𝑝 𝑋𝑝 + 𝑉𝑞 𝑋𝑞 𝑚𝑜𝑑 𝑛
𝑤ℎ𝑒𝑟𝑒 𝑋𝑝 = 𝑝 𝑝−1 mod 𝑝 , 𝑋𝑞 = 𝑞 𝑞 −1 mod 𝑞 , 𝑉𝑝 = 𝐶 𝑑 mod 𝑝, 𝑉𝑞 = 𝐶 𝑑 mod 𝑞
𝑉𝑝 and 𝑉𝑞 calculation can be simplified using Fermat’s theorem:
𝑉𝑝 = 𝐶 𝑑 mod (𝑝−1) 𝑚𝑜𝑑 𝑝, 𝑉𝑞 = 𝐶 𝑑 mod (𝑞−1) 𝑚𝑜𝑑 𝑞
 approx 4 times faster than doing directly (ie 𝑀 = 𝐶 𝑑 mod 𝑛)
 only owner of private key who knows values of p & q can use this
technique
RSA Key Generation

 users of RSA must:

 determine two primes at random 𝑝, 𝑞
 select either 𝑒 or 𝑑 and compute the other
 primes 𝑝, 𝑞 must not be easily derived from modulus 𝑛 = 𝑝𝑞
 means must be sufficiently large
 typically guess and use probabilistic test
 exponents 𝑒, 𝑑 are inverses, so use Inverse algorithm to compute the other
RSA Security

 possible approaches to attacking RSA are:

 brute force key search (infeasible given size of numbers)
 mathematical attacks (based on difficulty of computing 𝜙 𝑛 , by factoring
modulus 𝑛)
 timing attacks (on running of decryption)
 chosen ciphertext attacks (given properties of RSA)
Factoring Problem

 mathematical approach takes 3 forms:

 factor n=p.q, hence compute ø(n) and then d
 determine ø(n) directly and compute d
 find d directly
 currently believe all equivalent to factoring
 have seen slow improvements over the years
 as of May-05 best is 200 decimal digits (663) bit with LS
 biggest improvement comes from improved algorithm
 cf QS to GHFS to LS
 currently assume 1024-2048 bit RSA is secure
 ensure p, q of similar size and matching other constraints
Timing Attacks

 developed by Paul Kocher in mid-1990’s

 exploit timing variations in operations
 eg. multiplying by small vs large number
 or IF's varying which instructions executed
 infer operand size based on time taken
 RSA exploits time taken in exponentiation
 countermeasures
 use constant exponentiation time
 add random delays
 blind values used in calculations
Chosen Ciphertext Attacks

 RSA is vulnerable to a Chosen Ciphertext Attack (CCA)

 attackers chooses ciphertexts & gets decrypted plaintext back
 choose ciphertext to exploit properties of RSA to provide info to help
cryptanalysis
 can counter with random pad of plaintext
 or use Optimal Asymmetric Encryption Padding (OASP)