EXERCISE 8

RSA CRYPTOSYSTEM

1. One major drawback of public-key algorithms is that they are relatively slow. In Section
7.5.1 we learned that an acceleration technique is to use short exponents e. We study short
exponents in this problem in more detail.
(1) Assume that in an implementation of the RSA cryptosystem one modular squaring
takes 75% of the time of a modular multiplication. How much quicker is one en-
cryption on average if instead of a 2048-bit public key the short exponent e = 216 +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 = 2n + 1. Would it be advantageous to use
exponents of the form 2n + 1? Justify your answer.
(3) Compute the exponentiation x e mod 29 with x = 5 and both variants of e from
Part 2 of this problem with n = 4. Use the square-and-multiply algorithm and show
each step of your computation.

2. One of the most attractive applications of public-key algorithms is the establishment of

a secure session key for a private-key algorithm such as AES over an insecure channel.
Assume Bob has a pair of public/private keys for the RSA cryptosystem. Develop a simple
protocol using RSA which allows the two parties Alice and Bob to agree on a shared secret
key. Who determines the key in this protocol, Alice, Bob, or both?

3. In practice, it is sometimes desirable that both communication parties influence the se-
lection of the session key. For instance, this prevents the other party from choosing a key
which is a weak key for a symmetric algorithm. Some block ciphers such as DES and IDEA
have weak keys. Messages encrypted with weak keys can be recovered relatively easily
from the ciphertext.
Develop a protocol similar to the one above in which both parties influence the key. Assume
that both Alice and Bob have a pair of public/private keys for the RSA cryptosystem. Please
note that there are several valid approaches to this problem. Show just one.

4. In this exercise, you are asked to attack an RSA-encrypted message. You are the attacker
and you obtain the ciphertext y = 1141 by eavesdropping on the channel. The public key
is k pub = (n, e) = (2623, 2111).
(1) Consider the encryption formula. All variables except the plaintext x are known.
Why can’t you simply solve the equation for x?
(2) In order to determine the private key d, you have to calculate d ≡ e−1 mod Φ(n).
There is an efficient expression for calculating Φ(n). Can we use this formula here?
(3) Calculate the plaintext x by computing the private key d through factoring n. (Hint:
Factorization for such small RSA moduli can be done through an exhaustive search
with a list of all small primes and a simple program that checks which prime up
Date: November 13, 2024.
1
Introduction to Information Security Exercise 8
p
to n factors n.) Does this approach remain suitable for numbers with a length of
2048 bits or more?

5. We now show how an attack with chosen ciphertext can be used to break an RSA en-
cryption.
(1) Show that the multiplicative property holds for RSA, i.e., show that the product
of two ciphertexts y1 and y2 is equal to the encryption of the product of the two
respective plaintexts x 1 and x 2 . Under certain circumstances, this property might
be exploited by an attacker.
(2) Assume Oscar eavesdrops and obtains a ciphertext y1 , which is the encrypted ver-
sion of a message x 1 that was sent from Alice to Bob. Oscar would like to know the
plaintext x 1 . Oscar computes an innocent looking message t, which he encrypts.
We assume that he can obtain the decryption of one ciphertext that he sends to
Bob, e.g., by having access to Bob’s computer at a certain point in time. Show how
Oscar can construct a ciphertext y in such a way that he can use its decryption for
computing x 1 .

6. In this exercise, we illustrate the problem of using nonprobabilistic cryptosystems, such

as schoolbook RSA, imprudently. Nonprobabilistic means that the same plaintext maps to
the same ciphertext. This allows traffic analysis (i.e., to draw some conclusion about the
plaintext by merely observing the ciphertext) and in some cases even the total break of
the cryptosystem. The latter holds especially if the number of possible plaintexts is small.
Suppose the following situation:
Alice wants to send a message to Bob encrypted with his public key (n, e). She decides to
use the ASCII table to assign a number to each character (space → 32, ! → 33, . . . , A →
65, B → 66, . . . , ∼ → 126) and to encrypt them separately.
(1) Oscar eavesdrops on the transferred ciphertext. Describe how he can successfully
decrypt the message by exploiting the nonprobabilistic property of RSA.
(2) Bob’s RSA public key is (n, e) = (3763, 11). Decrypt the ciphertext y = 2514, 1125, 333, 3696, 2514
with the attack proposed in 1. For simplification, assume that Alice only chose cap-
ital letters A, . . . , Z during the encryption.
(3) Is the attack still possible if we use OAEP padding? Exactly explain your answer.

7. There is a vulnerability in RSA if the primes are re-used. Assume a certificate server that
generates RSA key pairs kpub = (n, e), kpr = d for users. Of course, to generate the public
keys, the server computes n = pq, where p and q are two large primes. The server does not
disclose the primes to the outside world, not even to the owner of the private key.
Two users, User 1 and User 2, obtain the key pairs kpub1 = (n1 , e1 ), kpr1 = d1 and kpub2 =
(n2 , e2 ), kpr2 = d2 . Due to a faulty true random generator, n1 was computed as n1 = p1 q1
and n2 as n1 = p1 q2 , i.e., p1 was used for both key pairs.
(1) Describe how an attacker can compute both private keys if he has both public keys,
which are, of course, publicly known. (Hint: You have to use the Euclidean algo-
rithm.)
(2) You look up the two public keys kpub1 = (4757, 17) and kpub2 = (2059, 129) in a cer-
tificate database. By wiretapping, you observe that User 1 receives the ciphertext
y1 = (0, 1884, 429) and User 2 receives y2 = (1186, 836, 0, 1114, 137, 46). Your
2
Introduction to Information Security Exercise 8
task is to break the system and to recover the actual letters that form the two plain-
texts x 1 and x 2 . The mapping between letters and plaintext numbers is simple (cf.
also Table 1.3):
A → 0, B → 1, . . . , Z → 25
Each letter is individually encrypted with RSA, i.e., the first plaintext consists of
three letters and the second one of six. (Remark: In this basic form, RSA encrypts
the plaintext value 0 to the ciphertext 0, which is a weakness. In practice, one uses
additional techniques, especially padding, to prevent this.)
8. By coincidence you learn that your colleagues are planning a secret party at somebody’s
house and you are not invited. Not very nice! In order to go to the correct place you
eavesdrop on your colleagues. Luckily, you manage to obtain the email that your dear
colleagues exchange. Unfortunately, this email is RSA encrypted. You have the following
information: kpub = (n, e) = (1271, 11) Ciphertext: [955, 458, 562, 911, 914, 269, 690]
The plaintext is the ASCII encoded name of the host of the party. Each ciphertext contains
one encrypted ASCII symbol. Break RSA through factoring, find the location of the party,
and surprise your colleagues!