Cryptography Reference
In-Depth Information
4. Let
a
= 39:
z
= 39
45
≡
78 mod 91, hence,
p
is composite.
Since the numbers 12, 17 and 38 give incorrect statements for the prime candidate
p
= 91, they are called “liars for 91”.
7.7 RSA in Practice: Padding
What we described so far is the so-called “schoolbook RSA” system which has sev-
eral weaknesses. In practice RSA has to be used with a padding scheme. Padding
schemes are extremely important, and if not implemented properly, an RSA imple-
mentation may be insecure. The following properties of schoolbook RSA encryption
are problematic:
RSA encryption is deterministic, i.e., for a specific key, a particular plaintext
is always mapped to a particular ciphertext. An attacker can derive statistical
properties of the plaintext from the ciphertext. Furthermore, given some pairs
of plaintext-ciphertext, partial information can be derived from new ciphertexts
which are encrypted with the same key.
1.
Small public exponents
e
and small plaintexts
x
might be subject to attacks if
no padding or weak padding is used. However, there is no known attack against
small public exponents such as
e
= 3.
Plaintext values
x
= 0,
x
= 1, or
x
=
−
1 produce ciphertexts equal to 0, 1, or
−
RSA has another undesirable property, namely that it is
malleable
. A crypto
scheme is said to be malleable if the attacker Oscar is capable of transforming the ci-
phertext into another ciphertext which leads to a known transformation of the plain-
text. Note that the attacker does not decrypt the ciphertext but is merely capable of
manipulating the plaintext in a predictable manner. This is easily achieved in the
case of RSA if the attacker replaces the ciphertext
y
by
s
e
y
, where
s
is some integer.
If the receiver decrypts the manipulated ciphertext, he computes:
(
s
e
y
)
d
s
ed
x
ed
≡
≡
sx
mod
n
.
Even though Oscar is not able to decrypt the ciphertext, such targeted manipulations
can still do harm. For instance, if
x
were an amount of money which is to be trans-
ferred or the value of a contract, by choosing
s
= 2 Oscar could exactly double the
amount in a way that goes undetected by the receiver.
A possible solution to all these problems is the use of padding, which em-
beds a random structure into the plaintext before encryption and avoids the above
mentioned problems. Modern techniques such as
Optimal Asymmetric Encryption
Padding (OAEP)
for padding RSA messages are specified and standardized in Pub-
lic Key Cryptography Standard #1 (PKCS #1).
Let
M
be the message to be padded, let
k
be the length of the modulus
n
in
bytes, let
|
H
|
be the length of the hash function output in bytes and let
|
M
|
be the
