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:
bulletGenerate a superincreasing knapack
bulletConvert the superincreasing knapsack into a general knapsack
bulletThe public key is the general knapsack
bulletThe private key is the superincreasing knapsack together with the conversion factors.

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).


bulletChoose two large numbers p and q and form their product N = pq
bulletChoose e relatively prime to (p-1)(q-1) and find the multiplicative inverse of e mudulo (p-1)(q-1)
bulletinv of e mudulo (p-1)(q-1) = d
bulletN = modulus  e = encryption exponent  d = decryption exponent




    Public key: (N, e) 



   Private key: d


    Encrypt: C=MemodN

    Decrypt: M=CdmodN


  p = 11, q = 3  N = 33

  (p-1)(q-1) = 20

  e is relatively prime to 20, which means that e = 3


 d:  ed = 1 mod (p-1)(q-1) = 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.

Diffie-Hellmann: Descrete log problem

Diffie-Hellman:  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:

bulletecrypt the DH exchange with a shared symmetric key
bulletencrypt the DH exchange with public keys and
bulletsign with private keys



Elliptic curve cryptography:

bulletWay of making cryptosystems
bulletFewer bits are needed for the same level of security
bulletComputational advantage
bulletUsed in handheld devices
bullety2 = x3 + ax + b

   ECC Diffie-Hellman:  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:
bulletSignatures and Non-repudiation

  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.

bulletConfidentiality and Non-repudiation


Public key infrastructure