. 6
( 36 .)


Proposition 2.5 (properties of Shamir protocol)
in transmitting the
= m, i.e. realisation of the protocol succeeds
(1) 24
message m from A to B;
(2) adversary cannot figure out what a message was transmitted (if p is
Notice first that any integer e 2 0 can be represented as e =
k(p - 1) r where r = e mod (p - 1). Therefore, by Fermat's theorem

. xr mod p
xe mod p = X ˜ ( P - ' ) + ˜ mod p = (xP-')˜

( I k. xT) mod p = x e mod ( P - 1 ) modp. (2.23)

By the protocol construction

modp = ( x i A ) d Bmodp = (xEB)dAdE modp
2 4 = x?
= ( m c A ) C E d A d E mod = mcAdAcBdB mod p .

Taking into account Eq. (2.23) and then Eqs. (2.17) and (2.18)) we may
x 4 = m ( c ˜ d ˜ c s mod )( ˜ - 1 )

- m(cAdA mod ( P - l ) ) ( c E d E mod ( P - 1 ) ) mod = ml'l mod =

which proves the first statement of the proposition.
Basics of Contemporary Cryptography f o r IT Practitioners

The proof of the second statement is based on the assumption that for
an adversary trying to recover m, there is no strategy more effective than
the following. She computes CB from (2.20), then finds d B and computes
5 4 = m by (2.22). But to implement this strategy the adversary has to
solve discrete logarithm problem which is impossible if p is large.
Let us discuss a method of selecting pairs C A , d A and C B ,d B satisfying
(2.17) and (2.18). It suffices only to consider the actions of user A because
user B acts the same way. The number C A is chosen randomly but must be
coprime to p - 1 (by searching through odd numbers since p - 1 is even).
Then d A may be computed by use of extended Euclidean algorithm as was
explained in Sec. 2.3.
Example 2.15 If A wants to send B the message rn = 10, A chooses p =
23 and sends it to B. Then A selects C A = 7 (gcd(7,22) = 1) and computes
d A = 19. Similarly, B selects CB = 5 (coprime to 22) and computes d B = 9.

The Shamir protocol begins.

- B : 2 1 = lo7 mod 23 = 14.
(Step 1) A

- B : 5 2 = 145 mod 23 = 15.
(Step 2) A
B : z = 1519 mod 23 = 19.
(Step 3) A 3
(Step 4) B computes 5 4 = 19™ mod 23 = 10.

We can see that B has received the message m 10.

ElGamal Encryption

Let there be users A, B , C, . . . , who wish to communicate each other secret
messages but have no secure communications channels. In this section,
we consider a cipher suggested by Taher ElGamal [ElGamal (1985)l which
solves the problem and uses only one message pass in contrast to three-pass
protocol by Shamir. In fact, the ElGamal scheme is based on Diffie-Hellman
key-agreement protocol which is used for a pair of users to obtain a common
secret key. The message is then encrypted by multiplication with that key.
For any subsequent messages the secret key is computed anew. Proceed to
the details of the method.
For the whole group of users a large prime p and integer g are chosen
so that distinct powers of g be distinct numbers modulo p (cf. Sec. 2.2).
Numbers p and g are transmitted to users in clear and may be used by all
users of a network.
Public Key Cryptosystems 25

Then every user selects his/her own secret number ci (private key),
1 < ci < p - 1, and computes the corresponding public number di (public
di = gci mod p . (2.24)
This results in Table 2.3.
Table 2.3 User keys in ElGamaI system.

Public key
User Private key

Let's show now how A transmits a message m to B. We shall assume,
a in the case of Shamir cipher, that the message is represented as a number
m < p.
Step 1 A generates a random number k, 1 5 k 5 p - 2, computes

r = g k modp, (2.25)

e=m.dg modp (2.26)

and transmits the pair of numbers (r,e) to user B.
Step 2 B , upon the receipt of (r,e ) , computes
m' = e . T P - I - ˜ B mod p . (2.27)

Proposition 2.6 (properties of ElGamal cipher)
(1) User B has received the message, i.e. m' = m;
(2) An adversary who knows p, g , d g , r , and el cannot compute m.
Proof. Substitute the value of e from (2.26) into (2.27):
. TP-'-'B mod p .
m' = m . d B k
Now substitute (2.25) in place of r and (2.24) in place of d g :

m = m . (gCB)" (gk)P-l-CB mod p
= m . g c ˜ k + k ( p - l ) - k c mod p = m - gk(p-l) mod p .
˜ (2.28)
Basics of Contemporary Cryptography f o r IT Practitioners

By Fermat™s theorem

mod p = 1k mod p = 1

and thus we obtain the first statement of the proposition.
To prove the second statement notice that the adversary cannot com-
pute k in (2.25) since it is the discrete logarithm problem. Hence, she
cannot compute m in (2.26) since m was multiplied by an unknown factor.
The adversary also cannot reproduce the actions of the legitimate receiver
(user B ) because she does not know the secret number CB (computation of
CB based on (2.24) is again the discrete logarithm problem).

Example 2.16 Transmit the message m = 15 from A to B. Choose the
parameters in the same way as in Example 2.2 on page 15. Let p = 23,
g = 5. Let user B choose his secret number CB = 13 and compute by (2.24)

dg = 513 mod 23 = 21.

User A generates random number k , say k = 7, and computes by (2.25),

= 5™ mod 23 = 17, e = 15 .21™ mod 23 = 1 5 . 1 0 mod 23 = 1 2 .

Then A sends B the encrypted message as a pair of numbers (17,12).
B computes by (2.27)

m/ = 12.1723-1-13 mod 23 = 12.17™ mod 23 = 1 2 . 7 m o d 23 = 1 5 .

We can see that B has been able to decrypt the message transmitted.

It is clear that the same scheme may be used by all the users in a
network. Note that any user who knows the public key of user B ( d g ) can
send B messages encrypted using dg. But it is only user B , and nobody
else, who is able to decrypt those messages since decryption is done by
utilising the private key cg which is known only to B. Note also that the
length of the ciphertext is twice the length of the plaintext but only one
pass in needed (provided the table with public keys was delivered to all
users in advance).
Public Key Cryptosystems 27

2.6 RSA Encryption and Trapdoor Functions

Named after its developers Ron Rivest, Adi Shamir, and Leonard Adleman,
this cipher proposed in [Rivest et al. (1978)] is so far one of most widely
We have seen that Shamir™s cipher completely solves the problem of se-
cure message exchange in the case when only open channels are available.
But as a disadvantage, the message is passed three times from one user to
another. The ElGamal cipher allows to solve the same problem in only one
pass, but also has a disadvantage of expanding the message: the cipher-
text is twice as long as the plaintext. The RSA encryption is free of such
disadvantages. It is interesting that this system is based on other one-way
function different from discrete logarithm. Moreover, we meet here one
more invention of contemporary cryptography - trapdoor function.
The RSA system is based on the following two facts from number theory:

Fact 1 testing numbers for primdity (and finding primes) is relatively easy
(see, e.g. [Menezes et al. (1996)l);
Fact 2 the problem of factoring numbers of the form n = pq, where p and
q are primes of roughly the same size, i.e. finding p and q given n, is
very hard (or computationally infeasible) when p and q are sufficiently
large (see also [Menezes et al. (1996)l).

Let again there be users A, B , C , . . . . Each user chooses randomly two
large primes P and Q and computes

N=PQ. (2.29)

Then the user computes the number 4 = ( P - l ) ( Q - 1) and selects a
number d < 4 relatively prime to 4 after which finds using the extended
Euclidean algorithm a number c such that

4 = 1. (2.30)

The user keeps secret the number c (as well as P, Q, and 4, but these
will not be needed any more) and publishes the numbers N and d . The
number c is the private key of the user and the pair of numbers N , d is
the corresponding public key. All information associated with the users is
shown in Table 2.4.
Proceed to the description of RSA protocol. If Alice wants to send a
message m to Bob, she will treat the message m as a number satisfying the
Basics of Contemporary Cryptography for IT Practitioners

User keys in RSA system.
Table 2.4

User Private key Public key

inequality m < N B (further on subscript B indicates that the corresponding
parameters belong to Bob).

Step 1 Alice encrypts the message as follows

e = mdBmod NB (2.31)

using Bob's public keys and transmits e over an open channel.
Step 2 Bob, having received the encrypted message, computes

NB .
= ecB mod (2.32)

Proposition 2.7 For the described protocol, m' = m, i.e. user B receives
the message sent by A .
Proof. By the protocol construction

m' = ecB mod NB = mdBcB N B .

Equation (2.30) means that for some k

CBdB = k$hB -k 1 .
By Proposition 2.4

4˜ = (PB- ˜ ) ( Q B 1) = ˜ NB)


. 6
( 36 .)