CYS406 · Annotated Slides · Chapter 4 — Public-Key Cryptography and RSA

Exam weight Low

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

Exam weight Low

Exam weight Low

Slide 4: Symmetric Cipher: Confidentiality

Exam weight Low

Slide 5: Symmetric Cipher: Authentication

Exam weight Low

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

Exam weight High

Public-key: encrypt with the receiver’s PUBLIC key for confidentiality; sign with your PRIVATE key for authentication.

Exam trapConfidentiality: encrypt with the RECEIVER’s public key. Signature: encrypt (sign) with the SENDER’s private key.

🎯 How this can come up · 2 questions

MCQ

To send Bob a confidential message, Alice encrypts with:

MCQ

A digital signature is created with:

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 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
- It was revealed in 1997 that James H. Ellis, Clifford Cocks, and Malcolm J. Williamson of GCHQ, the British signals intelligence agency, had previously shown in 1969 how public-key cryptography could be achieved.

Exam weight Low

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 related private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures
infeasible to determine private key from public
is asymmetric because
- those who encrypt messages or verify signatures cannot decrypt messages or create signatures

Exam weight Low

Exam weight Low

Symmetric vs Public-Key

Exam weight Low

Exam weight Low

Exam weight Low

Applications: encryption/decryption, digital signatures, key exchange.

Public-Key Requirements

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)
these are formidable requirements which only a few algorithms have satisfied

Exam weight Low

Public-Key Requirements

need a trapdoor one-way function
one-way function has
- Y = f(X) easy
- X = f
  - 1 (Y) infeasible
a trap-door one-way function has
- Y = f (X) easy, if k and X are known k
- X = f
  - 1 (Y) easy, if k and Y are known k
- X = f
  - 1 (Y) infeasible, if Y known but k not known k
a practical public-key scheme depends on a suitable trap-door one-way function

Exam weight Low

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

Exam weight Low

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)

operations (easy)

uses large integers (eg. 1024 bits)
security due to cost of factoring large numbers
- nb. factorization takes O(e log n log log n) operations (hard)

Exam weight Low

RSA (Rivest–Shamir–Adleman): security rests on the difficulty of factoring large n = pq.

Exam weight Low

Exam weight Low

Exam weight High

Key setup: pick primes p, q; n = pq; φ(n) = (p−1)(q−1); choose e with gcd(e, φ) = 1; d = e⁻¹ mod φ. Public (e, n), private (d, n).

Why RSA Works

because of Euler's Theorem:
- a ø(n) mod n = 1 where gcd(a,n)=1
in RSA have:
- n=p.q
- ø(n)=(p-1)(q-1)
- carefully chose e & d to be inverses mod ø(n)
- hence e.d=1+k.ø(n) for some k
hence: C d = M = M e.d 1+k.ø(n) = M .(M) 1 ø(n) k = M 1 .(1) k = M 1 = M mod n

Exam weight Low

Exam weight High

Example: p = 17, q = 11 → n = 187, φ = 160, e = 7, d = 23 (7·23 = 161 ≡ 1 mod 160).

🎯 How this can come up · 1 question

Written

p = 5, q = 11, e = 3. Find n, φ(n) and d.

RSA Example - En/Decryption

sample RSA encryption/decryption is:
given message M = 88 (nb. 88<187)
Publish public key PU={7,187}
Private key PR={23,187}
encryption: 7 mod 187 = 11 C = 88
decryption: M = 11 23 mod 187 = 88

Exam weight High

Encrypt C = Mᵉ mod n; decrypt M = Cᵈ mod n. With the example, M = 88 → C = 88⁷ mod 187 = 11.

🎯 How this can come up · 1 question

MCQ

In RSA, decryption computes:

Exam weight Low

Square-and-multiply makes huge exponents fast.

Exam weight Low

Exam weight Low

Efficient Encryption

encryption uses exponentiation to power e
hence if e small, this will be faster
- often choose e=65537 (2 16 +1)
- also see choices of e=3 or e=17
but if e too small (eg e=3) can attack
- using Chinese remainder theorem & 3 messages with different moduli
if e fixed must ensure gcd(e,ø(n))=1
- ie reject any p or q not relatively prime to e

Exam weight Low

Efficient Decryption

decryption uses exponentiation to power d
- 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
- approx 4 times faster than doing directly
only owner of private key who knows values of p & q can use this technique

Exam weight Low

RSA Key Generation

users of RSA must:
- determine two primes at random - p, q
- select either or and compute the other e d
primes p,q must not be easily derived from modulus n=p.q
- means must be sufficiently large
- typically guess and use probabilistic test
exponents, are inverses, so use Inverse e d algorithm to compute the other

Exam weight Low

RSA Security

possible approaches to attacking RSA are:
- brute force key search - infeasible given size of numbers
- mathematical attacks - based on difficulty of computing ø(n), by factoring modulus n
- timing attacks - on running of decryption
- chosen ciphertext attacks - given properties of RSA

Exam weight Low

Exam weight Low

Attacks: brute force on d, factoring n (keys ≥ 2048 bits), timing attacks (constant-time code, blinding), chosen-ciphertext attacks (OAEP padding).

Exam weight Low

Exam weight Low

Exam weight Low

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)

Exam weight Low

Summary

have considered:
- principles of public-key cryptography
- RSA algorithm, implementation, security

Exam weight Low