Is it possible to get RSA private key knowing public key and set of "original data=>encrypted data" entries?

Question

Hi, I work on apllication which allows plugins to access different set of functionality, every plugin provides "initialization string" which sets level of access to different features. Developers send me this strings, and I encrypt them using my 1024 bit RSA private key and send encoded data back. When started, my application decodes encoded data(encoded initialisation string) using built-in public key and if "decoded data != initialization string" it fails to start.

So, is it possible to use a database of "initialization string" => "encoded initialization string"(extracted from other plugins) to crack my private key, or make it possible to bruteforce it in reasonable time?

Answer 1

The whole point of the public/private key technology from RSA is that it is very difficult to reverse.

There are known cracks which take advantage of some particular implementation shortcomings, but the basic algorithm is believed to take decades to yield to a brute force attack. See this.

Answer 2

This kind of cryptoanalytic attack is called known plaintext attack and it should be really difficult to apply on RSA1024.

Or at least, trying to break the RSA key with known plaintexts will be as hard as trying to do it without them, the only known kind of attack related to your problem is the timing attack, but it needs to know well the specific implementation of your RSA since it works by measuring time needed for decryption.

The fact is that the safety of RSA is given by two complex mathematical problems, and knowing the plain text and the associated cipher text doesn't give you much help about it.

In any case the known plaintext attacks usually needs a lot of samples to be carried out (like millions or billions for DES) so it's not so easy also for weaker algorithms.

Answer 3

When you say that you "encrypt with a RSA private key" then you are not actually encrypting things. This is an historical bit of confusion. What you are doing is a digital signature which the plugin verifies with the corresponding public key. The confusion comes from the fact that, under an adequate light, RSA signatures can be seen as a kind of "reverse encryption" with the private key acting first. However, it differs in some details (e.g. padding, and involvement of a hash function) which make it quite different when it comes to implementation.

If you are using a proper RSA digital signature scheme (e.g. one of those described in PKCS#1, section 8 "signature schemes with appendix"), with an adequately large RSA key (1024 bits or more) generated through a correctly implemented key generation algorithm, then there is no known, computationally feasible way for an attacker to leverage the signatures you have produce in order to forge new signatures (and, a fortiori, crack the RSA private key). It is in no way proven that your signatures do not help the attacker, but 30 years of public research on the subject have not come up with such a breach.

Note, though, that usage details, in particular padding (the initial part, which transforms the to-be-signed data into a big number that the mathematical core of RSA can process) have been shown to be delicate; many proposed ways to do the padding have been successfully attacked. The PKCS#1 paddings have been under scrutiny for quite some time (two decades for the "v1.5" padding) and have resisted all such attempts so far. The "ISO 9796" family of paddings did not fare that well, many variants having been broken.

If you are not computing your signatures according to a well-established standard (i.e. PKCS#1), then you are looking for trouble. Do not do that. Fortunately, most RSA implementations (in cryptographic libraries and programming languages / environments) follow PKCS#1.