Encryption

Public-key cryptography
- Encryption
- Digital signatures
- Key establishment
Key escrow
Chaffing and winnowing
- Confidentiality without encryption

Problems with symmetric algorithms

Distribution of keys becomes a problem.
- Keys must be distributed with utmost security
- Can be a complex task
- Often keys has to be delivered by hand
- Keys often change
The number of keys increases with the square of the number of people exchanging secrets: n*(n-1)/2
Provides authentication as long as the keys are secure

Public key cryptography

Invented by Whitfield Diffie, Martin Hellman and Ralph Merkle (ca 1976)
- Secretely discovered before that by GCHQ (Goverment Communications Headquarters)
Many algorithms since 1976
- Only a few of those are both secure and practical
- Some are only suitable for key distribution
Only three work well for both key distribution and encryption
- RSA, ElGamal and Rabin
Slow: 100-1000 times slower than symmetric algorithms (RSA/DES)
Hybrid systems are used instead: distribution of symmetric keys using public key cryptography

Public key cryptography

Public key or asymmetric encryption system
Each user have two keys: a public and a private, secret key
For n users, we only need 2*n keys instead of n*(n-1)/2 keys as with symmetric encryption
D_Kpublic(E_Kprivate(M)) = M
Sometimes we also want
- D_Kprivate(E_Kpublic(M)) = M

Public key cryptography

Security of Public key cryptography

A cryptoanalyst always has the public key
If he have a cipher-text C = E_Kpublic(M) he can guess the value of M and easily check his guess
Add random bits to all messages (sort of like IV)

Modulo arithmetics

Restricts results to a certain range
Reminder after division
11 mod 3 = 2 since 11/3 = 3, 11 - 3*3 = 2
a mod n = b iff a = c*n + b for some integer c
Common operation: a^b mod b

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

*	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
0	4	3	2	1

Primes

Prime number: a number that can only be divided with itself and 1
- 2, 3, 5, 7, 11, 2365347734339
Two numbers are relatively prime when they share no factors in common other than 1
A prime number is relatively prime to all numbers except its multiples

Hard problems

Algorithmic complexity
n: input size of the problem
Linear: trivial
- O(n)
Polynomial: often possible
- O(n²), O(n⁵⁰⁰⁰ + n² + n )
Exponential: hard, infeasible for large n
- O(2ⁿ)
In cryptography: n is often the key size or the modulus

NP-complete problems

A class of problems
Every problem have a exponential solution
If one of the problems have a polynomial solution, then every NP-complete problem have a polynomial solution
- Nobody believes this is the case, but nobody have been able to prove or disprove it
Parallel solutions is possible: hardware advances might be a problem in the future

Number theory problems

Not NP-complete problems
Much research but no fast algorithms
- Advances can still be made
Example: factoring large numbers
- Given n, find primes p and q such that n = p * q

Diffie-Hellman

First public-key algorithm ever invented
Relies on the difficulty of calculating discrete logarithms in a finite field
Can not be used to encrypt messages
Instead used to agree on a secret key
Alice and Bob agree on a large prime n, and g such that g is primitive mod n
n and g can be public

Alice chooses a random large integer x and sends Bob
X = g^x mod n
Bob chooses a random large integer y and sends Alice
Y = g^y mod n
Alice computes
k1 = Y^x mod n
Bob computes
k2 = X^y mod n
k1 = k2 = g^xy mod n

Protocols for 3 and more people
US Patent expired in 1997
Problem: both parties have to be active in the same time

Knapsacks

First algorithm for public-key encryption
Ralph Merkle and Martin Hellman
Knapsack-problem: NP-complete
Knapsack problem:
- Given a pile of items, each with different weights, is it possible to put some of the items in knapsack so that the knapsack weighs a given amount?
- Given a set of values M₁, M₂, ..., M_n, compute the values of b_i such that
  S = b₁ M₁ + b₂ M₂ + ... b₃ M_n
  b_i: 1 or 0
Example:
- Items: 1, 5, 6, 11, 14, 20
- Knapsack of 22: 5, 6, 11
- Knapsack of 24: impossible

Knapsack

Plain-text bits corresponds to the b values
Cipher-text: the resulting sum

Example:

Plain-text:    1 1 1 0  0  1   0 1 0 1  1  0   0 0 0 0  0  0
Knapsack:      1 5 6 11 14 20  1 5 6 11 14 20  1 5 6 11 14 20
Cipher-text:   1+5+6= 32       4+11+14= 30     0

Knapsack problem: hard to solve
- Public key
One easier knapsack problem: super-increasing knapsacks
- Private key
- We need to be able to create a hard knapsack problem from an easy one

Easy knapsack problem

If the list of weights is a super-increasing sequence, the knapsack problem is easy to solve
Super-increasing sequence
- Every term is greater than the sum of all the previous term.
- {1, 3, 6, 13, 27, 52} - super-increasing
- {1, 3, 4, 9, 15, 25} - not super-increasing
Example:
- Knapsack weight: 70
- Items: {2, 3, 6, 13, 27, 52}
- W = 70
- 52 <= 70
  - 52 is in the knapsack
- W = 70 - 52 = 18
- 27 > 18
  - 27 is not in the knapsack
- 13 <= 18
  - 13 is in the knapsack
- W = 18 - 13 = 5
- 6 > 5
  - 6 is not in the knapsack
- 3 <= 5
  - 3 is in the knapsack
- W = 5 - 3 = 2
- 2 <= 2
  - 2 is in the knapsack
- W = 2 - 2 = 0
  - W = 0, we have a solution: {2, 3, 13, 52 }

Creating the public key from the private key

Take a super-increasing knapsack sequence ({2, 3, 6, 13, 27, 52}) and multiply all values by a number n, mod m.
The modulus m should be a number greater than the sum of all the number in the sequence: for example 105.
The multiplier should have no factors in common with the modulus: for example 31
Normal knapsack: {62, 93, 81, 88, 102, 37}
Public key: {62, 93, 81, 88, 102, 37}
Private key: {2, 3, 6, 13, 27, 52}

Encryption

Message: 011000 110101
011000: 93 + 81 = 174
110101: 62 + 93 + 88 + 37 = 280
Cipher-text: 174, 280

Decryption

Multiply each of the cipher-text values with n^-1 mod m
Then partition it with the private key
- 174 * 61 mod 105 = 9 = 3 + 6 = 011000
- 280 * 61 mod 105 = 70 = 2 + 3 + 13 + 52 = 110101

Practical implementation

At least 250 items
Value of each term in the easy knapsack: 200 - 400 bits
Modulus: 100 - 200 bits
1000, 000 tries a second: more than 10⁴⁶ years

Security of knapsacks

Shamir and Zippel found a way to reconstruct the super-increasing knapsack from the normal knapsack
Demonstrated with an Apple II...

RSA

RSA - Ron Rivest, Adi Shamir, Leonard Adelman
Bases its security on the difficulty of factoring large numbers
n = p * q, p and q are primes
Conjectured to be as hard to break as factoring n, that is from only n finding the primes p and q
Security depends on n: larger n more secure

Key generation

Generate two random large primes p and q
n = pq
Choose e such that e and (p - 1)(q - 1) are relatively prime
Compute d = e^-1 mod ((p - 1)(q - 1))
e and n is the public key, d and n the private key
Discard and never reveal p and q
Common choices of e: 3, 17 , 65537
Small e improves performance

Encryption and decryption

c_i = m_i^e mod n
m_i = c_i^d mod n

RSA

Conjectured to be as hard to break as factoring n
- Nobody proved it yet
If there is a way to get d, i.e. the private key, then this method can also be used to factor large numbers
- Not impossible but unlikely
De facto standard in much of the world
No US public key standard due to pressure from NSA and patent issues
U.S. Patent expired on September 20, 2000. No patents in other countries

Digital Signatures

Similar to MACs
Difference: only the originator should be able to create the signature
Public-key cryptography much easier: signature = E_Kprivate(M)
Everyone with the public key and the message M can verify the signature
Only a hash of the message is usually signed due to efficiency
Dedicated digital signature algorithms exist

Digital Signatures using RSA

A message hash M of up to n bits is generated
Then, to save space and time, the message hash is signed with sender's private key
The signature is S = M^d mod n
Send M (possible encrypted) and S
The receiver unsigns the message hash using the senders public key: M = S^e mod n
The receiver generates a message hash and compares it to M to confirm to the integrity and authentication of the message

ElGamal

Can be used for both encryption and digital signatures
Relies on the difficulty of calculating discrete logarithms in a finite field
No patents (expired 1997)
Similar to RSA

DSA

DSA - Digital Signature Algorithm
Used in DSS - Digital Signature Standard by NIST
Lot of criticism, especially from RSA Data Security Inc.
- DSA cannot be used for encryption or key distribution
  - (Almost) true, but not the point of DSS
- DSA was developed by NSA
- DSA is slower than RSA
- RSA is a de facto standard
  - But not royalty free
- DSA has not been analyzed enough
- DSA may infringe on other patents
- The key size is too small
  - Key size has been increased from 512 to 512-1024 bits
  - "Not great, but better"

DSA

Variant of the Schnorr and ElGamal signature algorithms
Uses a hash value (default is SHA) instead of the full message
Have a subliminal channel
- Implementors of DSA can leak key bits
- Don't use implementations you can't trust
Can actually be used to do ElGamal and RSA encryption

Public-key key length

Factoring is not proven to be hard
Factoring algorithms are improving faster than mathematicians expected
Mips-year: one year for a one mips (million instructions per second) computer
A 1-Mips machine is equivalent to a DEC VAX 11/780
100 MHz Pentium: 50 mips

Factoring algorithms

General number field sieve		Special number field sieve
# of bits	Mips-years	# of bits	Mips-years
512	30,000	512	< 200
768	2*10⁸	768	100,000
1024	3*10¹¹	1024	3*10⁷
1280	1*10¹⁴	1280	3*10⁹
1536	3*10¹⁶	1536	2*10¹¹
2048	3*10¹⁶	2048	4*10¹⁴

Note: Special number field sieve can not yet be used on numbers that are generally used in public key cryptography

Public-key key length

Year	vs. Individual	vs. Corporation	vs. Goverment
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Recommended (1995, Bruce Schneier) public-key key lengths in bits

Key-escrow

The purpose: to develop a cryptosystem that both protects individual privacy but at the same time allows for court-authorized wiretaps
No real advantages to the users
Complete or partial keys are stored at some escrow-agency

Clipper

One of two chips that implement the US government's Escrowed Encryption Standard
For encryption phone-conversations
Implements the Skipjack algorithm, an NSA designed secret key algorithm in OFB mode.
Each key was split into two halves, both necessary to decrypt messages
Each half would be held by different agencies

Chaffing and Winnowing

Two techniques for achieving confidentiality:
- Encryption
- Steganography (lecture 13)
New technique from 1998: Chaffing and Winnowing
Ron Rivest
to winnow is to separate out or eliminate
- the process of separating grain from chaff. (Att skilja agnarna fr�n vetet.)
There are two parts to sending a message:
- authenticating (adding MACs), and
- adding chaff.
The recipient removes the chaff to obtain the original message

Message transfer

Split the message into small packets
Add a message authentication code, MAC and a serial number:
- packet --> n, packet, MAC
Use a secret MAC-key
Adding chaff: adding fake packets with bogus MACs

Example:

Message:

        (1,Hi Bob,465231)
        (2,Meet me at,782290)
        (3,7PM,344287)
        (4,Love-Alice,312265)

Message transfer

After we added chaff:

        (1,Hi Larry,532105)
        (1,Hi Bob,465231)
        (2,Meet me at,782290)
        (2,I'll call you at,793122)
        (3,6PM,891231)
        (3,7PM,344287)
        (4,Yours-Susan,553419)
        (4,Love-Alice,312265)

Message transfer

After we added chaff:
Recovering the message: discard all packets where the MAC is incorrect
Sort the packets in the order of the serial numbers

More secure: use bits

        (1,0,351216)
        (1,1,895634)
        (2,0,452412)
        (2,1,534981)
        (3,0,639723)
        (3,1,905344)
        (4,0,321329)
        (4,1,978823)

Summary

The security of public key cryptography is based on "hard" problems
- Some problems can possibly be solved faster in the future
- NP-complete problems is probably secure though
Can be used for encryption, but is often too slow
- Use it to establish symmetric secret keys
Can be used for digital signatures
Use key length larger than 2048
RSA and ElGamal is the most used algorithms
More about encryption:
- Applied Cryptography, Bruce Schneier
  Good if you need to implement encryption schemes
- Handbook of Applied Cryptography, Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone.
  Available online. A lot of math.

Next time

Using encryption, Protocols
Digital watermarking