3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ And PKCS1-v1_5 Signature Scheme has a proof from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately $\endgroup$
    – kelalaka
    Commented Nov 3, 2021 at 18:31
  • $\begingroup$ Thanks for the answer, @kelalaka! $\endgroup$
    – Brongs Gaming
    Commented Nov 3, 2021 at 18:51

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks for the answer! Did I understand correctly that RSASSA-PKCS1-v1_5 can be used only for generating digital signatures? $\endgroup$
    – Brongs Gaming
    Commented Nov 3, 2021 at 15:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – SAI Peregrinus
    Commented Nov 3, 2021 at 16:59
  • 4
    $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Nov 3, 2021 at 17:01
  • 2
    $\begingroup$ 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). $\endgroup$
    – SAI Peregrinus
    Commented Nov 3, 2021 at 17:14
  • 2
    $\begingroup$ @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) $\endgroup$
    – poncho
    Commented Nov 3, 2021 at 18:14
6
$\begingroup$

There is also a more simple but not well-known signature scheme for RSA;

It has existentially unforgeable under adaptive chosen-message attacks in the random oracle model.

Today RSA-FDH is very simple;

  • Sign: $\sigma = Sign(H, m) = (H(m))^d \bmod n$
  • Verify: $\{0,1\} = Verify(H, m, \sigma) = [\sigma^e \bmod n \overset{?}= H(m) \bmod n]$

It was not easy to sign then because of the size requirement; the hash $H$ must have an output size equal to RSA modulus size. Now, the obvious choice is the eXtendible Output Functions (XOF) like SHAKE128/SHAKE256 of SHA-3.

Request output size from SHAKE128(or SHAKE256) equal to RSA modulus size, hash it then sign, that's it!

import hashlib
import rsa

(pubkey, privkey) = rsa.newkeys(2048)


FHD = hashlib.shake_128()
FHD.update(b'Message to Sign')
digestFDH = int.from_bytes(FHD.digest(255),byteorder='little')

#just m^d mod n    
signed = rsa.core.decrypt_int(digestFDH,privkey.d,pubkey.n)

#just m^e mod n
if digestFDH == rsa.core.encrypt_int( signed ,pubkey.e,pubkey.n):
    print("Verified")
else:
    print("!!!Verification failed. Halt!!!")

The exact definition as in 1998 paper (not in quotes)

The signing and verifying algorithm have oracle access to a hash function $H_{FDH} : \{0, 1\}^∗ \to \mathbb{Z}^*_N$. Signature generation and verification are as follows :

$\operatorname{SignFDH}_{N,d}(M) $
$\quad y \leftarrow H_{FDH}(M)$
$\quad \text{return }y^d \bmod N$

$\operatorname{VerifyFDH}_{N,e}(M, x)$
$\quad y \leftarrow x^e \bmod N;$ $\quad y' \leftarrow H_{FDH}(M)$
$\quad\text{if }y = y' \text{ then return }1 \text{ else return } 0$

and note that, at least some of the elements of the $\mathbb{Z}_N^*$ cannot be output by a standard XOFs. The modulus is not an exact power of 2, so one needs to output one bit less than the modulus. The library that I've used for the sample implementation uses bytes for output size, so it cannot cover up to 8-bit.

Also, the all-zero output is excluded!.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the answer! Interesting idea. But where did you request output size from Shake128 to be equal to RSA modulus size in this code snippet? $\endgroup$
    – Brongs Gaming
    Commented Nov 5, 2021 at 8:15
  • 2
    $\begingroup$ digest(255), and note that I don't claim this is secure implementation especially against side-channels, little info. You may need to use a secure one. See the warning of the library $\endgroup$
    – kelalaka
    Commented Nov 5, 2021 at 8:22
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation about the fact that above is an almost FDH signature has been moved to chat. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 5, 2021 at 11:59
  • 1
    $\begingroup$ Aren't the best bounds the ones from "Optimal Security Proofs for Full Domain Hash, Revisited" by Kakvi and Kiltz ? $\endgroup$
    – Ruggero
    Commented Mar 1, 2022 at 14:18
  • $\begingroup$ @Ruggero It seems I've missed that. Thanks, I'll update after read more... $\endgroup$
    – kelalaka
    Commented Mar 1, 2022 at 14:56
2
$\begingroup$

Other answers had given a good overview of RSA signature schemes that has simple paddings that can be used securely.

I'd like to bring the attention of readers to the "RSA-KEM" encryption scheme (since this question is also tagged OAEP) specified in a standard-track RFC (which specifies its use in CMS the Cryptographic Message Syntax environments).

https://datatracker.ietf.org/doc/html/rfc5990#appendix-A

In essence, it's like a encryption counter part to the "full domain hash", where the key material encrypted by the RSA algorithm is "full-domain", that is, it's a value chosen, uniformly random, within the range of $[0,N)$ where $N$ is the public modulus.

It then use a key derivation function to derive a key, which is then used in a key-wrapping encryption.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer! $\endgroup$
    – Brongs Gaming
    Commented Nov 5, 2021 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.