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!.
