Cryptography Reference
In-Depth Information
2. This property can under certain circumstances lead to an attack. Assume that
Bob first receives an encrypted message
y
1
from Alice which Oscar obtains by
eavesdropping. At a later point in time, we assume that Oscar can send an inno-
cent looking ciphertext
y
2
to Bob, and that Oscar can obtain the decryption of
y
2
.
In practice this could, for instance, happen if Oscar manages to hack into Bob's
system such that he can get access to decrypted plaintext for a limited period of
time.
7.13.
In this exercise, we illustrate the problem of using nonprobabilistic cryptosys-
tems, such as schoolbook RSA, imprudently. Nonprobabilistic means that the same
sequence of plaintext letters maps to the same ciphertext. This allows traffic analysis
(i.e., to draw some conclusion about the cleartext by merely observing the cipher-
text) and in some cases even to the total break of the cryptoystem. The latter holds
especially if the number of possible plaintexts is small. Suppose the following situ-
ation:
Alice wants to send a message to Bob encrypted with his public key pair (
n
,
e
).
Therefore, 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
,
2929
,
3368
,
2514
with the attack proposed in 1. For simplification, assume that Alice only chose
capital letters A-Z during the encryption.
3. Is the attack still possible if we use the OAEP padding? Exactly explain your
answer.
7.14.
The modulus of RSA has been enlarged over the years in order to thwart im-
proved attacks. As one would assume, public-key algorithms become slower as the
modulus length increases. We study the relation between modulus length and perfor-
mance in this problem. The performance of RSA, and of almost any other public-key
algorithm, is dependent on how fast modulo exponentiation with large numbers can
be performed.
1. Assume that one modulo multiplication or squaring with
k
-bit numbers takes
c
k
2
clock cycles, where
c
is a constant. How much slower is RSA encryp-
tion/decryption with 1024 bits compared to RSA with 512 bits on average? Only
consider the encryption/decryption itself with an exponent of full length and the
square-and-multiply algorithm.
2. In practice, the Karatsuba algorithm, which has an asymptotical complexity that
is proportional to
k
log
2
3
, is often used for long number multiplication in cryptog-
raphy. Assume that this more advanced technique requires
c
·
·
k
log
2
3
=
c
·
k
1
.
585
clock cycles for multiplication or squaring where
c
is a constant. What is the
