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=p\,q$
2. Compute $\phi (n)=(p-1)(q-1)$ (Euler's Totient function)
3. Choose random $e$ relatively prime to $\phi (n)$ (i.e. $\mathrm {gcd} (e,\phi (n))=1$)
4. Find $d=e^{-1}{\pmod {\phi (n)}}$
5. Public key: $\left\langle e,n\right\rangle$
   Private key: $\left\langle d,n\right\rangle$
   (All other numbers must be kept private)

Operations

Encryption

$c=m^{e}{\pmod {n}}\quad m<n$

Decryption

$m=c^{d}{\pmod {n}}$

Signing

$s=m^{d}{\pmod {n}}$

Verification

$m=s^{e}{\pmod {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^{d\,e}\equiv m^{1}\equiv m{\pmod {n}}$

This is a side effect of having $d\,e\equiv 1{\pmod {\phi (n)}}$ and $m<n$

Is RSA Secure?

Suppose you could factor $n=p\,q$. Then RSA would be broken:

• compute $\phi (n)=(p-1)(q-1)$
• compute $d=e^{-1}{\pmod {\phi (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 {gcd} (p-1,q-1)$ should be small
4. d should be larger than ${\sqrt[{4}]{n}}$

Attacks

Probable-Message Attack

Using public key $\left\langle e,n\right\rangle$

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}{\pmod {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