Cryptography Reference
In-Depth Information
x
values, we can retrieve
K
. (Note that this is not that simple in practice since many
technical problems must be solved.)
There is yet another example of side channel attack which is due to Daniel
Bleichenbacher, from Bell Labs (see Ref. [34]). It is an attack against PKCS#1v1.5. In
this scenario, the cleartext is first transformed into a plaintext according to a specific
format prior to encryption.
8
After decryption, the format is checked before the clear-
text is recovered. The problem is: what about invalid formats? In the first version of
PKCS#1v1.5, an invalid format was indicated as an error to the sender of the cipher-
text, and this information was useful for adversaries. Actually, adversaries could use the
receiver as an oracle which checked the correctness of the format, and the decryption
problem would become easy with the help of this oracle by successive approximations.
9.3.6
Bit Security of RSA
So far we wondered how hard recovering the whole plaintext was. Assuming that it is
hard, one can however wonder if recovering a part of it is also hard. As an example,
we can ask ourselves what is the security of the least significant bit: how hard is it to
recover the least significant bit of the plaintext?
We can prove that recovering this bit is as hard as the decryption problem, by using
the notion of Turing reduction. Let us assume that we have an oracle lsbdec which,
given a ciphertext
y
, returns the least significant bit of
x
y
d
mod
N
. First of all, we
notice that we can use it to implement an oracle which returns the most significant bit
msbdec(
y
)
=
=
msb(
x
) by observing the following identity.
msb(
x
)
=
lsb(2
x
mod
N
)
.
Hence
lsbdec(2
e
y
mod
N
)
msbdec(
y
)
=
.
We can decrypt a given ciphertext
y
by using the following algorithm.
1:
a
←
0,
b
←
N
2:
for
i
=
0to
log
2
N
do
if
msbdec(2
ie
y
mod
N
)
3:
=
0
then
4:
a
←
(
a
+
b
)
/
2
5:
else
6:
b
←
(
a
+
b
)
/
2
7:
end if
8:
end for
9: yield
a
8
We recall that the cleartext is the message in clear and the plaintext is the input of the encryption algorithm.
Search WWH ::
Custom Search