Raw RSA
Leichter, Jerry
leichter_jerrold at emc.com
Sun Sep 10 09:51:56 EDT 2006
| > | It is known, that given such an oracle, the attacker can ask for
| > | "decryption" of all primes less than B, and then he will be able to
| > | sign PKCS-1 encoded messages if the representative number is B-smooth,
| > | but is there any way to actually recover d itself?
|
| > RSA is multiplicative, so, yes, this follows easily unless the encoding
| > used prevents it.
|
| Could you describe this attack in more detail. I do not see a scenario where
| it would be useful.
|
| The attacker can encrypt a subset of numbers - those that encrypt to a B
| smooth number, but for this to be useful to him, he has to find a number in
| the subset set that corresponds to what he desires to encrypt, which looks
| like a very long brute force search.
Let R(x) = x^k mod n - where k might be the public key - for encryption -
or the private key - for signing. R(xy) = R(x)R(y) mod n. For
encryption, this means little - since the encryption exponent is
public, anyone can compute R(xy) directly anyway. But for signing,
it means that if I have my hands on signed copies of x and y, I can
forge a signature on xy. Thus, if I am able to get signatures on a
good collection of primes, I can sign many messages easily. Yet
another reason to sign hashes of messages, not raw messages - and
that the signer module should compute the hash itself, not rely on
the caller to do it.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list