Public Key Encryption & Signature in Practice

In practise PK methods are relatively time consuming when compared to a symmetric block cipher like AES.

• 
  Generate a random 128-bit AES key K.
  
• 
  Encrypt the entire message using the AES in CBC mode
  
• 
  Use the Public key of the recipient to encrypt K
  
• 
  Send the encrypted message and the encrypted “session key” to the recipient
  

The intended receiver then first finds the session key using his private key, and then decrypts the message.

How can person A identify themselves to person B, whilst not revealing any information which would enable either B or an eavesdropper to subsequently masquerade as A?

The RSA system can be described simply as

e = m³ mod n

m = e^1/3 mod n

(all arithmetic mod n)

1. 
   Prover shows I to verifier
   
2. 
   Prover generates random number R, cubes it, and sends R³ to verifier.
   
3. 
   Verifier tosses a coin and responds Heads or Tails.
   

4. 
   The prover then
   

1. 
   If heads, then sends R. The verifier cubes this to get R³ and compares it with the number received in step 2.
   
2. 
   If tails, then sends R.³I. The verifier cubes this to get I.R³ and compares it with the number sent in step 2, times the I sent in step 1.
   

If comparisons work, the verifier is satisfied (for now!). However a cheater has a one in two chance of success, so go back to step 2., and do it again, and again until satisfied.

In step 4a the prover is being tested on whether or not it actually knows the cube root of the number sent. If not, it will sooner or later be caught out. However anyone can respond correctly if heads were received every time, as anyone can generate a random number mod n and cube it.
In step 4b however the cheater has a bit of a problem, not knowing ³I. However if tails were luckily predicted, the cheater could send R³/I in step 2 (a number whose cube root she doesn’t know – gulp), followed by R in step 4b. This passes the comparison check.
But a cheater must be very lucky! In step 2 a commitment is made which cannot be backed away from. A single wrong guess and the game is up!
Observe that ³I is only used in the context of R. ³I. Since R is generated randomly, it is acting as a “One-time-pad” on ³I, and therefore no matter how many such values are observed, nothing whatsoever is revealed about the secret ³I.

El Gamal Signature

The El Gamal public key method can also be used for Signature. A variant of this method constitutes the popular International Digital Signature Standard.

A prime p, and suitable generator g are made known to all.
The Signer has a secret key x and a public key y related by

y=g^x mod p

To sign a message m, first produce a fixed length digest of it using a hash function such as SHA. Then generate a random number k < p.

The signature consists of
r = g^k mod p

s = (H(m) – x.r).k^-1 mod (p-1)

To verify this signature, a possessor of the public key checks that

Parameter Generation

1. 
   Generate a random 160-bit prime number q.
   
2. 
   Generate a random prime p such that p-1 is a multiple of q.
   
3. 
   Find a generator g of the prime order sub-group of order q.
   

Recall from the notes this example:

Fact If for a prime p, p-1 has a prime factor q, then a generator g of the sub-group of size q can be found by generating random r < p-1 until g=r^(p-1)/q mod p is not equal to 1. (It is easy to see that such a number raised to the power of q mod p will be 1).
Example
For p=29, p-1 has a prime factor 7, then a generator of the sub-group of size 7 can be found as follows:-
Generate r=3 at random. Then 3⁴ mod 29 = 81 mod 29 = 23. So g =23 is a generator of the sub-group of order 7.

Generating a Public/Private Key pair

This is easy:-

Generate a random x and calculate y=g^x mod p

Here x is the private key, y is the public key

Digital Signature

This requires x, g, p and q

1. 
   Generate a random value of k and calculate r=(g^k mod p) mod q. Note that this can be done off-line before the message to be signed is available.
   
2. 
   Get the message to be signed and calculate its hash h=H(M)
   
3. 
   Calculate s=(h+x*r)/k mod q.
   
4. 
   The signature is {r,s}. Note that r and s are each only 160 bits in length, so the signature is quite short.
   

Signature Verification

This requires y, g, p and q

1. 
   Hash the message again yourself to find h=H(M), and retrieve the signature {r,s}. If r or s is greater than or equal to q, abort and do NOT verify the signature.
   
2. 
   Calculate a=h/s mod q and b=r/s mod q.
   
3. 
   Calculate v= (g^a.y^b mod p) mod q
   
4. 
   If v=r then the signature is verified. Otherwise its not.
   

Note that signature is much faster than verification. This is in stark contrast with RSA where verification is much faster than signature.

Beating Man-in-the-Middle – 1

… or how to restore authentication to key-exchange.

Q. Why would you want to have a secure conversation with some-one you have never met before.

A. You wouldn’t.

So how can Alice & Bob use a small easily memorized mutual secret – like “Sparky” to lock out MITM?
First idea – include the mutual secret s in the key exchange.

Alice Bob
Generate private a Generate private b
A=3^a+s mod p B=3^b+s mod p
A 

 B
Key=(B/3^s)^a mod p Key=(A/3^s)^b mod p

Consider now a MITM called Eve. Eve carries out the following exchange with Alice.

Alice Eve
Generate private a Generate private e
A=3^a+s mod p B=3^e mod p
A 

 B

Key=(B/3^s)^a mod p
Alice sends something encrypted with the Key.

Eve drops the line!

Eve knows that Alice has calculated the key as (3^e/3^s)^a mod p

This is (3^a)^e-s mod p, which is (A/3^s)^e-s mod p. Eve now refers to her database of common passwords and tries every feasible s until the piece of ciphertext decrypts to something sensible. This is called an off-line dictionary attack. Thus she finds “Sparky”, and can play MITM against Alice & Bob.

Solution – use two independent generators, for example 3 & 4.

Alice Bob
Generate private a Generate private b
A=3^a4^s mod p B=3^b4^s mod p
A 

 B
Key=(B/4^s)^a mod p Key=(A/4^s)^b mod p

Using two different generators prevents an off-line dictionary attack.
… and we are done! We now have a method which features

• 
  Small easily remembered secret
  
• 
  Forward secrecy
  
• 
  Use of Strong Cryptography
  

Note that Eve can try to connect to Alice, masquerading as Bob, guessing one password at a time. Each such bad connection eliminates one password for Eve from her list. Nothing can be done about this, but passwords might be considered to “erode” slightly with each bad connection, and eventually might have to be replaced.

Beating Man-in-the-Middle – 2

Assume that a trusted third-party exists known to both Alice & Bob. Just like in Fiat-Shamir both Alice & Bob go to the TTP and are issued with smart cards. The TTP has a public value n=p.q where p and q are the TTPs secret. There is also a generator g of suitable order. Alice’s Smart-card contains her identity I_a, n, g and ³I_a mod n. Bob’s smart-card contains his identity I_b, n, g and ³I_b mod n.

The key exchange now proceeds as follows (Okamoto’s Method)

Alice Bob

Send I_a to Bob Send I_b to Alice

Generate a random a Generate a random b

Calculate A=³I_a . g^a mod n Calculate B=³I_b . g^b mod n

Send A to Bob Send B to Alice
Calculate Key=(B³/I_b)^a mod n Calculate Key==(A³/I_a)^b mod n
Both keys are the same – g^3ab mod n

Download 28.95 Kb.

Share with your friends: