Introduction to Public-Key Cryptography - Understanding Cryptography - page 168

Problems

6.1. As we have seen in this chapter, public-key cryptography can be used for en-
cryption and key exchange. Furthermore, it has some properties (such as nonrepu-
diation) which are not offered by secret key cryptography.
So why do we still use symmetric cryptography in current applications?

6.2. In this problem, we want to compare the computational performance of sym-
metric and asymmetric algorithms. Assume a fast public-key library such as
OpenSSL [132] that can decrypt data at a rate of 100 Kbit/sec using the RSA al-
gorithm on a modern PC. On the same machine, AES can decrypt at a rate of
17 Mbit/sec. Assume we want to decrypt a movie stored on a DVD. The movie
requires 1 GByte of storage. How long does decryption take with either algorithm?

6.3. Assume a (small) company with 120 employees. A new security policy de-
mands encrypted message exchange with a symmetric cipher. How many keys are
required, if you are to ensure a secret communication for every possible pair of
communicating parties?

6.4. The level of security in terms of the corresponding bit length directly influ-
ences the performance of the respective algorithm. We now analyze the influence of
increasing the security level on the runtime.
Assume that a commercial Web server for an online shop can use either RSA
or ECC for signature generation. Furthermore, assume that signature generation for
RSA-1024 and ECC-160 takes 15.7 ms and 1.3 ms, respectively.

1. Determine the increase in runtime for signature generation if the security level
from RSA is increased from 1024 bit to 3072 bit.
2. How does the runtime increase from 1024 bit to 15,360 bit?
3. Determine these numbers for the respective security levels of ECC.
4. Describe the difference between RSA and ECC when increasing the security
level.

Hint: Recall that the computational complexity of both RSA and ECC grows with
the cube of bit length. You may want to use Table 6.1 to determine the adequate bit
length for ECC, given the security level of RSA.

6.5. Using the basic form of Euclid's algorithm, compute the greatest common di-
visor of

1. 7469 and 2464
2. 2689 and 4001
For this problem use only a pocket calculator. Show every iteration step of Euclid's
algorithm, i.e., don't write just the answer, which is only a number. Also, for every
gcd, provide the chain of gcd computations, i.e.,

gcd( r 0 , r 1 )=gcd( r 1 , r 2 )= ··· .