Signature generation operation:
RSASSA-PKCS1-V1_5-SIGN (K, M)
Input: K signer’s RSA private key
M message to be signed, an octet string
Output: S signature, an octet string of length k, where k is the length in octets of the modulus n
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. Convert the encoded message EM to an integer message representative m:
m = OS2IP (EM) .
3. Apply the RSASP1 signature primitive (Section 5.2.1) to the private key K and the message representative m to produce an integer signature representative s:
s = RSASP1 (K, m) .
4. Convert the signature representative s to a signature S of length k octets:
S = I2OSP (s, k).
5. Output the signature S.


RSASP1:
RSASP1 (K, m)
Input: K RSA private key, where K has one of the following forms: a quintuple (p, q, dP, dQ, qInv) 
m message representative, an integer between 0 and n–1
Output: s signature representative, an integer between 0 and n–1
Errors: “message representative out of range”
Assumptions: private key K is valid

Steps:
1. If the message representative m is not between 0 and n–1, output “message representative out of range” and stop.
2. Let s1 = m dP mod p.
3. Let s2 = m dQ mod q.
4. Let h = (s1 – s2) · qInv mod p.
5. Let s = s2 + q · h.
6. Output s.