Cryptography Reference
In-Depth Information
Problems
7.1.
Let the two primes
p
= 41 and
q
= 17 be given as set-up parameters for RSA.
1. Which of the parameters
e
1
= 32
,
e
2
= 49 is a valid RSA exponent? Justify your
choice.
2. Compute the corresponding private key
K
pr
=(
p
,
q
,
d
). Use the extended Eu-
clidean algorithm for the inversion and point out every calculation step.
7.2.
Computing modular exponentiation efficiently is inevitable for the practicabil-
ity of RSA. Compute the following exponentiations
x
e
mod
m
applying the square-
and-multiply algorithm:
1.
x
= 2,
e
= 79,
m
= 101
2.
x
= 3,
e
= 197,
m
= 101
After every iteration step
, show the exponent of the intermediate result in binary
notation.
7.3.
Encrypt and decrypt by means of the RSA algorithm with the following system
parameters:
1.
p
= 3
,
q
= 11
,
d
= 7
,
x
= 5
2.
p
= 5
,
q
= 11
,
e
= 3
,
x
= 9
Only use a pocket calculator at this stage.
7.4.
One major drawback of public-key algorithms is that they are relatively slow.
In Sect. 7.5.1 we learned that an acceleration technique is to use short exponents
e
.
Now we study short exponents in this problem in more detail.
1. Assume that in an implementation of the RSA cryptosystem one modular squar-
ing takes 75% of the time of a modular multiplication. How much quicker is
one encryption on average if instead of a 2048-bit public key the short exponent
e
= 2
16
+ 1 is used? Assume that the square-and-multiply algorithm is being used
in both cases.
2. Most short exponents are of the form
e
= 2
n
+ 1. Would it be advantageous to
use exponents of the form 2
n
1? Justify your answer.
3. Compute the exponentiation
x
e
mod 29 of
x
= 5 with both variants of
e
from
above for
n
= 4. Use the square-and-multiply algorithm and show each step of
your computation.
−
7.5.
In practice the short exponents
e
= 3, 17 and 2
16
+ 1 are widely used.
1. Why can't we use these three short exponents as values for the exponent
d
in
applications where we want to accelerate decryption?
2. Suggest a minimum bit length for the exponent
d
and explain your answer.
7.6.
Verify the RSA with CRT example in the chapter by computing
y
d
= 15
103
mod
143 using the square-and-multiply algorithm.
