Cryptography Reference
In-Depth Information
Risk 3: Attack Against Small Values of
e
Choosing a small value for exponent
e
in the public key saves computation
time during the encryption, but there are inherent risks. If every user within
a group uses their own modules, but all use a common exponent
e
, then a
message,
m
, encrypted by
e
users, will suffice to reveal
m
. The same is true
when
e(e
+
1
)/
2 linearly dependent messages are encrypted [Hastad].
If there is a risk that this weakness might be practically exploited, then one
can disturb the messages with random bits. The probability that these bits will
prevent linear dependencies is high.
As a sideline, exponent
d
— the private key — shouldn't be too small either, but
this doesn't play an important role in practice.
Risk 4: Attack Against Common Modules
If you now think that all users could use the same module (the keys would then
have to be created centrally) after what was said in the section above, I have
to disappoint you — there are also powerful attacks where even the module can
be factored.
Risk 5: Attack Against the Protocol
At the CRYPTO '98, Daniel Bleichenbacher suggested an attack against a pro-
tocol called
PKCS#1
that is normally used for RSA encryption [BleichRSA].
This attack is practically doable, so it caught some attention, although the threat
is within limited boundaries. I will briefly explain the basic idea.
With the PKCS#1 protocol, an RSA plaintext has the following form:
|
|
|
|
00
02
pad bytes ...
00
plaintext
Bleichenbacher's attack sends a 'ciphertext' to a server that decrypts it. The
server checks whether or not the 'plaintext' created has the described format; if
it doesn't, it returns an error message. And this is the information the attacker
is after. The attacker creates the next 'ciphertext' dependent on the previous
replies and sends it again to have it decrypted. We can easily see that this is
a typical adaptive-chosen-plaintext attack (see Section 3.1). Though the author
does not give an exact figure for the trials required, we can reasonably assume
