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

Question

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

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.