CSCE 465 Lecture 21

« previous | Tuesday, April 9, 2013 | next »

Public Key Cryptography

Invented and published in 1975

Much slower than Private Key and Hash functions.

Applications

1. message integrity with digital signatures: sign with private key, verify with public key
   • only one person can sign the message: non-repudiation
   • Only achievable with public key cryptography
2. Communicating securely over an insecure channel: encrypt using public key, decrypt with private key
3. Secure storage on an insecure medium (similar to above
4. User Authentication: perform "operation" with private key, verify with public key.
5. Key exchange for secret key cryptography

Algorithms

System	Encryption/Decryption	Digital Signatures	Key Exchange
RSA	Yes	Yes	Yes
Diffie-Hellman	No	No	Yes
DSA	No	Yes	No

Trapdoor One-Way Function

• $y=f_k(x)$ is easy to compute if $k$ and $x$ are known

RSA

(See MATH 470 Lecture 5#RSA→)

(See MATH 470 Lecture 6#RSA Review→)

Invented by Rivest, Shamir, and Adleman

Basis: factorization of large numbers is hard

Variable key length (1024 bits or greater)

Variable plaintext block size

• plaintext block: smaller than key size
• ciphertext block: same as key size

Setup

Find (using Miller-Rabin Algorithm) large primes $p$ and $q$

1. Let $n=pq$
2. Compute $\varphi (n)=(p-1)(q-1)$ (Euler's Totient function)
3. Choose random $e$ relatively prime to $\varphi (n)$ (i.e. $\mathrm{g}\mathrm{c}\mathrm{d}(e,\varphi (n))=1$)
4. Find $d=e^{-1}(\mathrm{mod}\varphi (n))$
5. Public key: $⟨e,n⟩$
   Private key: $⟨d,n⟩$
   (All other numbers must be kept private)

Operations

Encryption

$c=m^e(\mathrm{mod}n)m<n$

Decryption

$m=c^d(\mathrm{mod}n)$

Signing

$s=m^d(\mathrm{mod}n)$

Verification

$m=s^e(\mathrm{mod}n)$

Key Negotiation

$A$ sends random number $R_1$ to $B$, encrypted with $B$'s public key

$B$ sends random number $R_2$ to $A$, encrypted with $A$'s public key

$A$ and $B$ both decrypt received messages using their respective keys

$A$ and $B$ both compute $K=H(R_1\oplus R_2)$ and use that as the shared key.

Proof of Correctness

RSA works because $(m^d{)}^e=m^{de}\equiv m^1\equiv m(\mathrm{mod}n)$

This is a side effect of having $de\equiv 1(\mathrm{mod}\varphi (n))$ and $m<n$

Is RSA Secure?

Suppose you could factor $n=pq$. Then RSA would be broken:

• compute $\varphi (n)=(p-1)(q-1)$
• compute $d=e^{-1}(\mathrm{mod}\varphi (n))$

So to make $n$ difficlut to factor,

1. $p$ and $q$ should be similar length (about 500 bits if key is to be 1024 bits)
2. $(p-1)$ and $(q-1)$ should contain a large prime factor
3. $\mathrm{g}\mathrm{c}\mathrm{d}(p-1,q-1)$ should be small
4. d should be larger than $\sqrt[4]{n}$

Attacks

Probable-Message Attack

Using public key $⟨e,n⟩$

1. Encrypt all possible plaintext messages
2. Try to find a match between the ciphertext and one of the encrypted messages

This only works for small plaintext message sizes

Solution: Pad plaintext message with random text before encryption

• PKCS #1 v1 specifies this padding format.

Timing Attacks

Recovers private key from running time of decryption algorithm.

Computing $m=c^d(\mathrm{mod}n)$ using repeated squaring algorithm:

m = 1
(k-1).downto(1) do |i|
  m = m*m % n
  if d[i] == 1
    m = m*c mod n       # !!! measure timing of this line
  end
end