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

message integrity with digital signatures: sign with private key, verify with public key
- only one person can sign the message: non-repudiation ^[1]
- Only achievable with public key cryptography
Communicating securely over an insecure channel: encrypt using public key, decrypt with private key
Secure storage on an insecure medium (similar to above
User Authentication: perform "operation" with private key, verify with public key.
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$

Let $n=p\,q$
Compute $\phi (n)=(p-1)(q-1)$ (Euler's Totient function)
Choose random $e$ relatively prime to $\phi (n)$ (i.e. $\mathrm {gcd} (e,\phi (n))=1$ )
Find $d=e^{-1}{\pmod {\phi (n)}}$
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; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} both decrypt received messages using their respective keys; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} both compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K = H(R_1 \oplus R_2)} and use that as the shared key.

Proof of Correctness

RSA works because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (m^d)^e = m^{d\,e} \equiv m^1 \equiv m \pmod{n}}

This is a side effect of having Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\,e \equiv 1 \pmod{\phi(n)}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m < n}

Is RSA Secure?

Suppose you could factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = p \, q} . Then RSA would be broken:

compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n) = (p-1)(q-1)}
compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = e^{-1} \pmod{\phi(n)}}

So to make Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} difficlut to factor,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} should be similar length (about 500 bits if key is to be 1024 bits)
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p-1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (q-1)} should contain a large prime factor
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{gcd}(p-1,q-1)} should be small
d should be larger than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt[4]{n}}

Attacks

Probable-Message Attack

Using public key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle e, n \right\rangle}

Encrypt all possible plaintext messages
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Footnotes

↑ Alice cannot deny that she signed the message

[1] Alice cannot deny that she signed the message

[1]