Signature verification operation:
RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)
Input: (n, e) signer's RSA public key
M message whose signature is to be verified, an octet string
S signature to be verified, an octet string of length k, where k is the length in octets of the modulus n
Output: "valid signature" or "invalid signature"
Errors: "message too long"; "modulus too short"

Steps:
1. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to the message M to produce an encoded message EM of length k-1 octets:
EM = EMSA-PKCS1-V1_5-ENCODE (M, k-1).  (SHA1 for SSH!)
If the encoding operation outputs "message too long," then output "message too long" and stop. If the encoding operation outputs "intended encoded message length too short," then output "modulus too short" and stop.
2. If the length of the signature S is not k octets, output "invalid signature" and stop.
3. Convert the signature S to an integer signature representative s: 
s = OS2IP (S) .
4. Apply the RSAVP1 verification primitive (Section 5.2.2) to the public key (n, e) and the signature representative s to produce an integer message representative m:
m = RSAVP1 ((n, e), s) . 
If RSAVP1 outputs "signature representative out of range," then output "invalid signature" and stop.
5. Convert the message representative m to a second encoded message EM of length k-1 octets:
EM' = I2OSP (m, k-1). 
If I2OSP outputs "integer too large," then output "invalid signature" and stop.
6. Compare the encoded message EM and the second encoded message EM'. If they are the same, output "valid signature"; otherwise, output "invalid signature."

Note. Another way to implement the signature verification operation is to apply a "decoding" operation (not specified in this document) to the encoded message to recover the underlying hash value, and then to compare it to a newly computed hash value. This has the advantage that it requires less intermediate storage (two hash values rather than two encoded messages), but the disadvantage that it requires additional code.



RSAVP1:
RSAVP1 ((n, e), s)
Input: (n, e) RSA public key
s signature representative, an integer between 0 and n-1
Output: m message representative, an integer between 0 and n-1
Errors: "signature representative out of range"
Assumptions: public key (n, e) is valid

Steps:
1. If the signature representative s is not between 0 and n-1, output "signature representative out of range" and stop.
2. Let m = s e mod n.
3. Output m.