Cryptography
Is there an easy way to make textbook RSA secure enough so it can be used in real life?
I have written a raw (textbook) RSA implementation (just for fun) and I wonder is there an easy way to make it secure enough so it can be used in real life (without implementing OAEP+ and RSASSA-PSS)? Are there any simple algorithms for padding and generating secure digital signatures?
Solution
Actually, RSASSA-PKCS1-v1_5 signature padding is quite simple, and has no known weaknesses (the similarly named RSAES-PKCS1-v1_5 padding is broken for encryption unless implemented in a very very careful way; don't use that).
The padding format is:
00 01 FF FF FF ... FF FF 00 <DER of Hash Type> <Hash>
where DER of Hash Type is a byte string that depends on the type of hash you used, and Hash is the output of the hash function. For SHA-256, the DER is the byte string:
30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
So, you take your hash, prepend it with a fixed string, and you're done.
If you want to make things a bit simpler, you could omit the DER of Hash Type (which would mean that you're not precisely PKCS #1.5, however it does not introduce any known weaknesses.
Comments (5)
- +0 – Thanks for the answer! Did I understand correctly that RSASSA-PKCS1-v1_5 can be used only for generating digital signatures? — Nov 03, 2021 at 15:39
- +1 – Yes, that's only for signatures. RSA encryption is mostly useful as a building-block for other constructs (eg homomorphic encryption). The simple alternative would be RSA-KEM, which isn't exactly encryption (it exchanges a random number which is used to derive an encryption key for use with a symmetric AEAD) but is simple and secure. — Nov 03, 2021 at 16:59
- +4 – @BrongsGaming: well, yes, however the question did ask 'Are there any simple algorithms for padding and generating secure digital signatures?' - you didn't ask for simple algorithms for encryption. For that, the simplest might be "don't do padding at all; instead, have the encryptor pick a random value between 2 and $n-2$, and textbook RSA encrypt that; use the original random number you picked to generate a symmetric key and use that symmetric key to encrypt the message you want to send. — Nov 03, 2021 at 17:01
- +2 – Of note, RSA-KEM is essentially a more-formal version of that (it specifies how to use the random number to generate a symmetric key and a few other bits about the format). — Nov 03, 2021 at 17:14
- +2 – @BrongsGaming: the reason textbook RSA is considered insecure is a) because it's determenistic; the attacker can guess plaintexts and encrypt them - if they guess correctly, he knows the plaintext, and b) RSA's homomorphic properties; if the value being encrypted is a smooth number, that is, a product of small primes, then the attacker can recover that plaintext surprisingly quickly. Neither of these apply to RSA-KEM (where you pick a random n-bit number) — Nov 03, 2021 at 18:14