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 1024bit 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 128bit 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 1024bit 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 SmartCard.
Solution: FiatShamir Method
The RSA system can be described simply as
e = m^{3} mod n
m = e^{1/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 base256 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 ZeroKnowledge proof, as it proves possession of certain knowledge without revealing anything about it (!?)
The protocol
(all arithmetic mod n)

Prover shows I to verifier

Prover generates random number R, cubes it, and sends R^{3} to verifier.

Verifier tosses a coin and responds Heads or Tails.

The prover then

If heads, then sends R. The verifier cubes this to get R^{3} and compares it with the number received in step 2.

If tails, then sends R.^{3}I. The verifier cubes this to get I.R^{3} 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 R^{3}/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 “Onetimepad” 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=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 (p1)
To verify this signature, a possessor of the public key checks that
y^{r}.r^{s} g^{H(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

Generate a random 160bit prime number q.

Generate a random prime p such that p1 is a multiple of q.

Find a generator g of the prime order subgroup of order q.
Recall from the notes this example:
Fact If for a prime p, p1 has a prime factor q, then a generator g of the subgroup of size q can be found by generating random r < p1 until g=r^{(p1)/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, p1 has a prime factor 7, then a generator of the subgroup of size 7 can be found as follows:
Generate r=3 at random. Then 3^{4} mod 29 = 81 mod 29 = 23. So g =23 is a generator of the subgroup 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

Generate a random value of k and calculate r=(g^{k} mod p) mod q. Note that this can be done offline before the message to be signed is available.

Get the message to be signed and calculate its hash h=H(M)

Calculate s=(h+x*r)/k mod q.

The signature is {r,s}. Note that r and s are each only 160 bits in length, so the signature is quite short.
This requires y, g, p and q

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.

Calculate a=h/s mod q and b=r/s mod q.

Calculate v= (g^{a}.y^{b} mod p) mod q

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 ManintheMiddle – 1
… or how to restore authentication to keyexchange.
Q. Why would you want to have a secure conversation with someone 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})^{es} mod p, which is (A/3^{s})^{es} 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 offline 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^{a}4^{s} mod p B=3^{b}4^{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 offline 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 ManintheMiddle – 2
Assume that a trusted thirdparty exists known to both Alice & Bob. Just like in FiatShamir 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 Smartcard contains her identity I_{a}, n, g and ^{3}I_{a} mod n. Bob’s smartcard contains his identity I_{b}, n, g and ^{3}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=^{3}I_{a} . g^{a} mod n Calculate B=^{3}I_{b} . g^{b} mod n
Send A to Bob Send B to Alice
Calculate Key=(B^{3}/I_{b})^{a} mod n Calculate Key==(A^{3}/I_{a})^{b} mod n
Both keys are the same – g^{3}^{ab} mod n
Share with your friends: 