4

All attacks on RSA seem to require knowledge of at least the ciphertext and the public key.

However, has there ever been any evidence of an attack which simply uses a sufficiently large number of ciphertext to calculate the public and / or private key, and if so what is the recommended way to mitigate this?

Improve this question
6
  • 2
    What makes you think such an attack would be possible? Also public keys are generally something you already have. They're called "public" for a reason.
    – Ben
    Commented May 23, 2018 at 15:38
  • I remember how the attack on WEP worked, in that it was collect as much ciphertext as possible to discover the initialisation vector. That and my limited knowledge in this area leads me to believe such an attack on RSA may have been attempted before. I'd love to find out that it's somehow (verifiably) impossible though.
    – m.edmondson
    Commented May 23, 2018 at 16:02
  • In theory weak key generation could be exploited using cipher texts only. Never done it myself but the NSA probably have :)
    – paj28
    Commented May 23, 2018 at 16:11
  • 1
    Think about it. RSA encryption is c ≡ m^e (mod n) and RSA decryption is m ≡ c^d (mod n). The public key contains e and n, and the private key contains d and n (with d being the modular inverse of e). An attack against RSA would require factoring n, which makes it possible to calculate d. Even if you can factor large semiprimes, how would you get d without n? Also, see this answer.
    – forest
    Commented May 24, 2018 at 0:54
  • @forest - From that answer Therefore, an attacker able to break the cryptosystem with the public key can obtain it under the usual assumption of a few known plaintext/ciphertext pairs, then break the cryptosystem.. This would tell me it is possible?
    – m.edmondson
    Commented May 24, 2018 at 13:30

1 Answer 1

Reset to default
1

I don't think anyone has ever demonstrated finding the entire public key—all (say) 2048 bits of n—but cryptographers demonstrated distinguishing public keys (popular exposition) by solving the German tank problem on ciphertexts to break the privacy claims of PLAID, the Protocol for Lightweight Authentication of IDentity developed by the Australian Department of Human Services.

The basic idea of PLAID is an identification protocol for smart cards: When you put your smart card into a legitimate hospital terminal, the terminal proves to the smart card that it represents legitimate hospital, and the smart card identifies you to the terminal, and then the terminal dispenses health care at you like a vending machine.

PLAID is intended to provide privacy from malicious terminals: If you put your smart card into a malicious terminal which cannot prove to your smart card that it represents a legitimate hospital, the terminal should be unable to distinguish your card from any other card.

However, in the protocol, the smart card sometimes reveals RSA ciphertexts under a public key n stored on the smart card—even to illegitimate terminals. Every ciphertext under the key n is a nonnegative integer c < n, but since n is different for each key, the upper bound on ciphertexts is different for each key.

Specifically, a malicious terminal can use the same methods used by British statisticians during World War II to estimate the number of German tanks by examining the serial numbers c of captured tanks which are all less than the total number n of tanks. The granularity of this estimate turns out to be enough to distinguish two smart cards' public keys simply by examining a sufficient number of ciphertexts made by them.

Not all public-key cryptosystems have this property—for example, most public-key encryption and signature schemes that rely on the difficulty of computing discrete logs in a single standard group, like X25519 or Ed25519, tend to naturally provide the various related notions of key privacy for public-key encryption, anonymous signatures, or key indistinguishability for signatures (paywall-free).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .