Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Public Key Cryptography
77/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
The Key Problem
Symmetric key encryption schemes work well. AES is effectively unbreakable with a “long enough key”.
The problem is how do you get the key in the first place?
78/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Some History
Before cheap powerful computers, unbreakable encryption was almost impossible.
Governments wanted to read the codes of others.
They could control the export of these machines.
When IBM designed DES they could get it weakened
Cipher machines looked like this:
79/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Some History
Cipher machines looked like this:
During 1970-1990 all that changed.
Personal computers could do anything a cipher machine could do.
80/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Some History
During 1970-1990 all that changed.
Personal computers could do anything a cipher machine could do.
University academics worked on encryption with the aim of making it available to everyone
81/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Public Key Encryption
Public key encryption helps (but does not solve) this problem. The idea of public key encryption is that you have two keys:
one for encryption
and another for decryption.
The encryption key is made public, the decryption key is always secret
Can derive public key from private key, but it must be computationally infeasible to derive private key from public key
82/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Diffie-Hellman
Diffie-Hellman is a widely used key agreement protocol. Uses modular arithmetic
The protocol uses two public parameters
generator g (often 160 bits long) prime p (often 1024 bits long)
See spec doc for g and p (http://tools.ietf.org/html/rfc5114, Section 2)
83/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Diffie-Hellman
Alice and Bob pick random numbers rA and rB and find tA =grA modp
tB =grB modp
The protocol just exchanges these numbers:
A →B : tA B →A : tB
Alice calculates trA mod p rB
Bob calculates tAB mod p The shared key is
K=grArB =trA =trB modp BA
84/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Diffie-Hellman
An observer cannot work out rA and rB from tA and tB So we have a good key but know nothing about the
participants.
We did not need to share any keys at the start, therefore this is a very powerful protocol.
In practice: use DH to set up a secure channel, then use something else to authenticate the person at the other end.
85/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Example of DH
86/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Elgamal
Elgamal is Diffie-Hellman turned into public key scheme. It uses a fixed g and p
Alice picks rA as private key
tA = grA mod p is the public key
Encryption of message M: Bob chooses rB, sends (grB modp,M∗trB modp)
Decryption of ciphertext (c1, c2) by Alice: c2 ∗c−rA
Correctness:
A
M∗trB ∗(grB)−rA =M∗(grA)rB ∗(grB)−rA =Mmodp A
1
87/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
RSA
RSA is a public key system invented by (Rivset, Shamir and Adleman).
The scheme carefully generates e,d and n n is a product of two large primes, have
(me)d =mmodn
Public key is (e, n) and the private key is (d, n)
for every m.
88/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
RSA
Because of how e,d and n are generated: To encrypt m as the ciphertext c do:
c = me mod n
To decrypt ciphertext c as a message m do:
m = cd mod n
Security depends on difficulty of finding prime factors of n
For more details see, the crypto module or Schneier: Applied Cryptography
89/91
Codes versus Ciphers
Symmetric Cryptography How Public Key Cryptography works Public Key Cryptography
Using Public Key Crypto
Public key crypto is much slower than symmetric key crypto. So instead of just using public key crypto, systems:
make a new symmetric key
encrypt that with the public key
then encrypt the message with the symmetric key.
90/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Using Public Key Crypto
Public key crypto is much slower than symmetric key crypto. So instead of just using public key crypto, systems:
make a new symmetric key
encrypt that with the public key
then encrypt the message with the symmetric key. Cipher text is
EKP (KS ), {M }KS
where
KP is the public RSA key
KS is the symmetric key (e.g. for AES) EKP ( ) is RSA encryption,
{ }KS is AES-CBC encryption.
90/91
Codes versus Ciphers Symmetric Cryptography Public Key Cryptography
How Public Key Cryptography works
Signatures
Using RSA
Epub(Dpriv(M)) = M This can be used to sign messages.
Sign a message with the private key and this can be verified with the public key.
Any real crypto suite will not use the same key for encryption and signing. as this can be used to trick people into decrypting.
91/91