<<

. 7
( 36 .)



>>

where cp(.) is the Euler function. Hence by Theorem 2.4
m' = m k p ( N B ) + l mod NB =m,
0
Proposition 2.8 (properties of RSA protocol)
(1) The protocol encrypts and decrypts data correctly;
(2) A n adversary who overhears all transmitted messages and knows all
public information cannot recover the plaintext message i f P and Q are
large.
Public Key Cryptosystems 29


Proof. The first property follows from Proposition 2.7. To prove the
second property notice that the adversary knows only public parameters N
and d. In order to find c she must know the value q5 = ( P - l)(Q - 1) for
which, in turn, P and Q must be known. Generally speaking, P and Q can
be found by factoring N but it is a hard problem (Fact 2). Note, however,
that the choice of large random primes P and Q can be done in acceptable
0
time (Fact 1).

The one-way function y = xd mod N employed in RSA has a so-.called
“trapdoor” which allows for easy computation of the inverse function x =
$ mod N if the factorisation of N is known. (Indeed, it is easy to compute
j
q5 = ( P - 1)(Q - 1) and then c = d-™ mod q5.) If P and Q are unknown
then to compute the inverse function is practically impossible because to
find P and Q given N is very hard (Fact 2), i.e. the knowledge of P and Q
is a “trapdoor”. The trapdoor functions are employed in other branches of
cryptography, as well.
Notice that it is important for the RSA system that each user chooses
his own pair of primes P and Q, i.e. that all moduli N A , N g , N c , . . . b e
different (otherwise one user would be able to read encrypted messages
destined to another user). But it is not required for the second public
parameter d. The parameter d can be the same for all users. It is often
recommended to choose d = 3 (for correspondingly chosen P and Q), see
e.g. [Menezes et al. (1996)l. In this case encryption is maximally fast (it
requires only 2 modular multiplications).

Example 2.17 Suppose Alice wants to send Bob the message m = 15.
Let Bob™s parameters be

PB = 3, 11, N B = 33, d B = 3
QB =

(3 is coprime to ( ˜ ( 3 3= 20). Find cg using the extended Euclidean algo-
)
rithm: C B = 7 (check it: 3 . 7 mod 20 = 1). Encrypt m using Eq. (2.31):

mod 33 = 152.15 mod 33 = 27.15 mod 33 = 9 .
e=

Alice sends the number 9 to Bob over an open channel. Only Bob knows
cg = 7 so he decrypts by (2.32):
2
m = g7 mod 33 = (g2) .9™ . 9 mod 33 = 152 .15 ™ 9 mod 33 = 15.
˜

We can see that Bob has deciphered the message.
Basics of Contemporary Cryptography for IT Practitioners
30


The considered system is unbreakable if P and Q are large but has the
following imperfection: A sends a message to B by utilising B™s public
information (the numbers NB and d B ) . Adversary E cannot read the mes-
sages destined for B but she is able to send a message to B on behalf of
A, i.e. E can impersonate A. Surely, we need more complex protocols to
avoid this. It is interesting that one of the possible solutions may be based
entirely on the RSA scheme, as the following.
A wants to send B message m. First A computes the number e =
mCAmod N A . E cannot do that since C A is secret. Then A computes the
number f = e d B mod N B and sends f to B. B receives f and computes
sequentially u = f“” mod NB and w = udA mod NA.
As a result, B obtains the message w = m. As in the conventional
RSA system, E cannot recover the message but, in contrast to RSA, she
also cannot send a message on behalf of A (because she does not know the
secret C A ) .
Here we meet a new situation. B knows that the message was originated
by A as if it were signed by A. A virtually signs the message by encrypting it
with the use of her secret parameter C A . This is an example of the so-called
digital signature. The digital signature is one of the widely used inventions
of modern cryptography. It will be systematically studied in Chap. 4.


Problems and Exercises

+ 8, 3 - 8, 3 . 8 ,
2.1 Reduce the results of expressions 5, 16, 27, -4, -13, 3
3.8.5
(a) modulo 10,
(b) modulo 11.
2.2 Compute using fast modular exponentiation algorithms 28 mod 10,
37 mod 10, 7™™ mod 100, 757 mod 100.
2.3 Factor numbers 108, 77, 65, 30, 159.
2.4 Determine what pairs of numbers (25,12), (25,15), (13,39), (40,27)
are relatively prime.
2.5 Find values of Euler function ( ˜ ( 1 4 )(,˜ ( 2 0 ) .
2.6 Compute using the properties of Euler function ( ˜ ( 5 3 ) ,
(p(21), ( ˜ ( 1 5 9 ) .
2.7 Compute the quantities 313 mod 13, 524 mod 11, 317 mod 5 using the
Fermat theorem.
2.8 Compute the quantities 3™ mod 20, 214 mod 21, 21°7 mod 159 using
the Euler theorem.
Public Key Cryptosystems 31


2.9 Find using the Euclidean algorithm gcd(21,12), gcd(30,12),
gcd(24,40), gcd(33,16).
2.10 Using the extended Euclidean algorithm, find 2 and y in equations
+ 12y = gcd(21,12),
212
(a)
+ 12y = gcd(30,12),
(b) 302
+ 40y = gcd(24,40),
(c) 242
+ 163 = gcd(33,16).
(d) 332
2.11 Compute 3-l mod 7, 5-™ mod 8, 3-1 mod 53, 10-1 mod 53.
2.12 Write out all primes less than 100. Which of them are of the form
+
p = 2q 1, where q is also prime?
2.13 Find all relevant values for the parameter g in the Diffie-Hellman
system with p = 11.
2.14 Compute secret keys YA,YB and a corresponding common key ZAg
in the Diffie-Hellman system with parameters
X A = 5 , X B = 7;
(a) p = 23, g = 5 ,
X A = 5 , X B = 7;
= 19, g = 2,
(b) p
X A = 3, Xg = 4;
= 23, g = 7,
p
(c)
= 17, g = 3, X A = 10, Xg = 5;
(d) p
= 19, g = 10, X A = 4, X g = 8.
(e) p
2.15 For Shamir™s cipher with specified parameters p , C A , CB find missing
parameters and describe the process of transmitting message m from
A to B
(a) 19, C A = 5, CB = 7, m = 4;
p =
= 23, C A = 15, CB = 7, m = 6;
(b) p
= 19, CA = 11, cg = 5, m = 10;
(c) p
(d) = 23, CA = 9, cg = 3, m = 17;
p
= 17, C A = 3, CB = 13, m = 9.
(e) p
2.16 For EIGamal™s cipher with specified parameters p , g, cg, k find miss-
ing parameters and describe the process of transmitting message m
to user B
(a) p = 19, g = 2, C B = 5 , k = 7, m = 5 ;
(b) p = 23, g = 5, cg = 8, k = 10, m = 10;
(c) p = 19, g = 2, cg = 11, k = 4, m = 10;
(d) p = 23, g = 7, cg = 3, k = 15, m = 5;
(e) p = 17, g = 3, CB = 10, k = 5, m = 10.
2.17 For the RSA system with specified parameters PA, QA, dA find miss-
ing parameters and describe the process of transmitting message m
Basics of Contemporary Cryptography for I T Practitioners
32


to user A
(a) PA = 5, Q A = 11, d A = 3, m = 12;
(b) PA = 5, Q A = 13, d A = 5, m = 20;
(C) PA = 7, Q A = 11, d A = 7, m = 17;
(d) PA = 7, QA = 13, d A = 5, m = 30;
(e) PA = 3, QA = 11, d A = 3, m = 15.
2.18 The encrypted message e = 100 is sent to the RSA user with param-
eters N = 187, d = 3. Decrypt the message by breaking the RSA
system of the user.


Themes for Labs

2.19 Write and debug the set of program functions implementing the ba-
sic algorithms used in the cryptosystems studied: modular exponen-
tiation (azmod m), greatest common divisor (gcd(a, b ) ) , inversion
(x-' mod m).
2.20 Write a program implementing the Diffie-Hellman key agreement.
The following parameter values are recommended: p = 30803, g = 2.
Secret keys are to be randomly generated.
2.21 Write a program implementing the Shamir cipher. The number p =
30803 may be taken as a prime modulus. The other parameters are
to be randomly generated.
2.22 Write a program implementing the ElGamal cipher. The following
parameter values are recommended: p = 30803, g = 2. Private keys
and the other parameters are to be randomly generated.
2.23 Write a program implementing the RSA cipher for transmitting mes-
sages to users A or B. The following parameter values are recom-
mended: PA = 131, Q A = 227, PB = 113, Q B = 281, d A = d B = 3.
Chapter 3

Solving Discrete Logarithm Problem



Problem Setting
3.1

In order to construct a reliable cryptosystem one should take into account
the methods of disclosure the adversary can employ. This allows one to
choose cryptosystem parameters (e.g. the length of numbers) so that the
adversary™s methods become infeasible. In the present section, we shall
consider two such methods to give the reader some insight into this LLmys-
terious” field.
We have seen that many of the public-key ciphers are based on the
one-way function

y = a x modp (3.1)
and we know that given a and x the value of y can be computed with not
more than 2logz operations (Proposition 2.1). But finding x given a and
y, i.e. computing the discrete logarithm, is assumed to be a much more
complex problem.
As it was shown in the justification of Shamir cipher (see (2.23)), by
Fermat™s theorem, when exponentiating modulo a prime p exponents are
reduced modulo p - 1. Therefore it suffices to deal with only the exponents
x satisfying the inequality 0 _< x _< p - 1.
Denote by t, the number of multiplications needed for computation of y
in (3.1) given a and x and, for brevity, we shall call ty time of computation.
Time of exponentiation with the algorithms of Sec. 2.1 is not more than
2 log x and x < p. Hence

I210gp (34
ty

for any exponent x.

33
Basics of Contemporary Cryptography for IT Practitioners
34


Now proceed to the problem of finding 2 in (3.1) given u and y. First
estimate the complexity of the exhaustive search. In the exhaustive search,
we begin with u1 and check whether u1 = y. If it is not the case, check
whether u2 = y, u3 = y, and so on until ui = y is found (then z = i). On
average, it will require to multiply by u and check for equality ( p - 1)/2
times. So the time of exhaustive search




With the “baby-step giant-step” algorithm described below the time of
finding z is noticeably smaller:




and with the index calculus algorithm also described below this time is even
substantially smaller:




where c1, c2 are some positive constants.
To make the comparison more illustrative, express the time of compu-
tation through the bitlength of the numbers in (3.1). Denote the bitlength
of p by n. When making computations modulo p we have n x logp. There-
fore the order of complexity (time of computation) for the above mentioned
algorithms will be the following:




where M loosely denotes “proportional”.

<<

. 7
( 36 .)



>>