In the book "Cryptography engineering" (2010, Ferguson), I found, page 209/210, these 3 functions: MsgToRSANumber, SignWithRSA, VerifyRSASignature (see below).
I can't understand how the last function VerifyRSASignature works. It seems that it checks if "the given signature $\sigma$ raised to exponent $e$ mod $n$" (this part is ok) is equal to $s$, which is the result of MsgToRSANumber, i.e. the result of a random choice!
How can this work? Isn't there a mistake here?
The pseudocode shown is correct.
It works because $\mathsf{MsgToRSANumber}$ is a function in the mathematical sense; and in particular, always returns the same result for the same arguments $(n,m)$. This is possible because it internally uses a Pseudo Random Number Generator (PRNG), rather than a True RNG (which indeed would make the signature verification fail).
The rationale for using a (P)RNG to transform the message $m$ into the message representative $s$ is that the (conjecturally hard) RSA problem is to invert the public key function $s\to s^e\bmod n$ for a random $s$ in interval $[0,n)$. If we used $s=m$, or a simple transformations (e.g. $s\ =\ (a\;m+b)\bmod n$ for some public constants $a$, $b$ ), an attack would often be tractable. The signature system proposed has some level of reducibility to the RSA problem.
This signature scheme is known as Full Domain Hash. See this question for references.
RSASSA-PSS of PKCS#1v2, and RSA per ISO/IEC 9796-2 scheme 2, are signature systems which combine a PRNG and a TRNG in preparing the message representative $s$. The TRNG insures that an adversary can not predict or choose which $s$ the legitimate signer will use, even if given the opportunity to choose the messages signed. This allows stronger/simpler security reduction.
MsgToRSANumber always returns the same result for the same arguments, because the PRNG only uses SHA(m) as seed, and no other source of entropy? Is that correct? [I was thinking the PRNG uses this seed, but also other sources of entropy, and that was my misunderstanding... how would it be called in this case? Not a PRNG, would this be a TRNG?]
$\endgroup$
MsgToRSANumberalways returns the same result for the same arguments. A PRNG that's fed true entropy, even partially, is no longer a PRNG. It remains an RNG, and arguably becomes a TRNG; but the definition of the later is ambiguous (some use True as meaning straight from an entropy source), thus I would call what you describe a TRNG mixing seed and entropy with some post-conditioning, or just a RNG.
$\endgroup$