Chapter 4 Public key crypto
Problems solved for chapter 4: 5,9,13,14,17,22
A digital signature is better than a
handwritten one because it is more ties to the document itself.

Used for Crypto and signature
Knapsack: The NP complete problem is ideal for a cryptosystem. The Knapsack problem can be stated as a number of weights, numbers that are sett up, like 85 , 13 ,9,7, 47, 27, 99, 88. For a desiered sum S = 172 we need to add 85+13+47+27, this can be set up a 11001100. 
This can be set up in a linear way as well: Superincreasing knapsack: The weights are arranged from least to greatest. Each weight is greater than the sum of all previous weights. 3, 6, 11, 25, 46, 95, 200, 411 Now having a sum S=309, we start with the largest weight and work towards the smallest, giving us 10100110 
This can be used as a better solution:
Converting from super to general: Choose m and n. n needs to be greather than the sum of all elements in the superincreasing knapsack. Both need to be prime numbers. We use 41 and 491 2m = 2*41 = 82mod491=82 3m = 3*41 = 123mod491 = 123 and so on, see page 64 in the book. You will then get the full range. The public key will be 82, 123 and so on and the private key will be the superincreasing knapsack that was made up together with the modular inverse of the conversion factor m:
Private key: 3, 6, 11, 25, 46, 95, 200, 411 and invm modn = inv 41 mod 491 = Do not understand, have to look at this again. 
RSA: relies of the difficulty of factoring
RSA : First algorithm known to be suitable to signing and encryption. Two large prime numbers forming a product N. N=p*q, e (encryption exponent) and d (decryption exponent).
Encrypt: C=MemodN Decrypt: M=CdmodN
p = 11, q = 3 N = 33 (p1)(q1) = 20 e is relatively prime to 20, which means that e = 3
d: ed = 1 mod (p1)(q1) = 20 gives d = 7 Repeat Squaring: Easier to compute large numbers see page 68 in the book Speeding up RSA: Encryption exponent is the same for all users. Poblems with cube root attack since e is chosen to be 3, the mod N operation has no effect. Or to use the Chinese reminder. 
DiffieHellmann: Descrete log problem
DiffieHellman:
DESCRETE LOG PROBLEM Used for establishing a shared secret. Can only be used to establish a shared secret (used as a shared symmetric key) How to avoid a Man In the Middle attack:

Elliptic curve cryptography:
ECC DiffieHellman: Uses elliptic curves, public curve and secret multipliers. Can be harder to break for a given number of bits. But Man In the Middle attacks are the same.

Public key notation
Uses for public key crypto:
Alice orders 100 shares, to ensure integrity she computes a MAC. Then the shares drop and she repudiates the transaction. Bob can not prove that Alice did place the order because he knows the symmetric key also. If Alice used a digital signature, Bob can prove that Alice singed it since she is the only one that knowes the private key.

Public key infrastructure