Public Key Encryption & Signature in Practice
In practise PK methods are relatively time consuming when compared to a symmetric block cipher like AES.
When encrypting a message m, using RSA for example, m must be less than the 1024-bit modulus n. A larger message could be encrypted by breaking it up into 1024 bit chunks. However it is more efficient to
· 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.
This is much more efficient.
For signature, a large message to be signed could again be broken up into 1024-bit blocks and each signed individually. But the individually signed blocks could be swapped in order by an active attacker, and the message thus changed. So a fixed length (160 bit) Cryptographic Hash of the message H(m) is formed, and only the Hash is signed.
So in practise only one PK operation is required for encryption/decryption/signature or verification.
Identification – the passport of the future?
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?
Proof of identity might be stored on an unforgeable Smart-Card.
Solution: Fiat-Shamir Method
The RSA system can be described simply as
e = m3 mod n
m = e1/3 mod n
Therefore the ability to decrypt is equivalent to the ability to extract cube roots mod n. It is easy to take such roots only if the factors of n are known.
Assume a “trusted centre” which generates n = p.q
Each individual’s identity is represented as an ascii string I, which can be treated as a base-256 number.
The trusted centre then calculates 3ÖI for every user of the system. It then destroys p and q.
Each user is then issued with a Smart Card which contains I, 3ÖI, and n.
The idea is that to prove identity the user reveals I, and then proves that he/she has knowledge of 3ÖI , without actually revealing it.
This is sometimes called a Zero-Knowledge proof, as it proves possession of certain knowledge without revealing anything about it (!?)
The protocol
(all arithmetic mod n)
1. Prover shows I to verifier
2. Prover generates random number R, cubes it, and sends R3 to verifier.
3. Verifier tosses a coin and responds Heads or Tails.
4. The prover then
(a) If heads, then sends R. The verifier cubes this to get R3 and compares it with the number received in step 2.
(b) If tails, then sends R.3ÖI. The verifier cubes this to get I.R3 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 3ÖI. However if tails were luckily predicted, the cheater could send R3/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 3ÖI is only used in the context of R. 3ÖI. Since R is generated randomly, it is acting as a “One-time-pad” on 3ÖI, and therefore no matter how many such values are observed, nothing whatsoever is revealed about the secret 3Ö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=gx 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 = gk mod p
s = (H(m) – x.r).k-1 mod (p-1)
To verify this signature, a possessor of the public key checks that
yr.rs º gH(m) mod p
This can be checked directly by substitution.
There appears to be no way to forge a signature on a given message without first solving the discrete logarithm problem.
The Digital Signature Standard
This is a method for digital signature standardized by the NIST. It is a variant on the El Gamal signature, but more efficient.
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 34 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=gx 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=(gk 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= (ga.yb 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=3a+s mod p B=3b+s mod p
A ®
¬ B
Key=(B/3s)a mod p Key=(A/3s)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=3a+s mod p B=3e mod p
A ®
¬ B
Key=(B/3s)a mod p
Alice sends something encrypted with the Key.
Eve drops the line!
Eve knows that Alice has calculated the key as (3e/3s)a mod p
This is (3a)e-s mod p, which is (A/3s)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=3a4s mod p B=3b4s mod p
A ®
¬ B
Key=(B/4s)a mod p Key=(A/4s)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 Ia, n, g and 3ÖIa mod n. Bob’s smart-card contains his identity Ib, n, g and 3ÖIb mod n.
The key exchange now proceeds as follows (Okamoto’s Method)
Alice Bob
Send Ia to Bob Send Ib to Alice
Generate a random a Generate a random b
Calculate A=3ÖIa . ga mod n Calculate B=3ÖIb . gb mod n
Send A to Bob Send B to Alice
Calculate Key=(B3/Ib)a mod n Calculate Key==(A3/Ia)b mod n
Both keys are the same – g3ab mod n