Worked Example

Alice's 1024-bit RSA signing key in hex format:
n=
E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D
12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CF
C6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6
F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F
e=010001
d=
00A403C327477634346CA686B57949014B2E8AD2C862B2C7D748096A8B91F736
F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282D
F439906F34D86E085BD5656AD841F313D72D395EFE33CBFF29E4030B3D05A28F
B7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21
The message to be signed is, of course, M="abc"
that is, the 3 bytes in hex format, PT=616263
The message digest algorithm is SHA-1, so H = Hash("abc") = A9993E364706816ABA3E25717850C26C9CD0D89D
The DigestInfo value for SHA-1 is T=
3021300906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9C
D0D89D
The encoded message block, EB, after encoding but before signing is 0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00302130
0906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9CD0D89D
After RSA signing, the output is 60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F
Weaknesses in RSA

Small encryption exponent If you use a small exponent like e=3 and send the same message to different recipients and just use the RSA algorithm without adding random padding to the message, then an eavedropper could recover the plaintext. Using the same key for encryption and signingGiven that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted message using the same key then she gets the original. Acting as an oracleThere are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. So don't do that. Solutions


  1. Don't use the same RSA key for encryption and signing.
  2. If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
  3. Always format your input before encrypting or signing.
  4. Always add fresh random padding - at least 8 bytes - to your message before encrypting.
  5. When decrypting, check the format of the decrypted block. If it is not as expected, return an error, not the decrypted string.
  6. Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid Signature".

More Advanced Schemes

The underlying RSA computations
c = me mod n, m' = cd mod n; s = md mod n, m' = se mod n
are always the same, but there are many variants of how these can be used inside an encryption or digital signature scheme. Here are some of them.
RSAES-OAEP

The OAEP encoding technique for encryption is described in PKCS#1 version 2 and in IEEE P136. It is more secure than the PKCS#1v1.5 encoding method described above, perhaps provably secure. The encoding technique involves a mask generation function (MGF) based on a hash function and there is no obvious structure in the encoded block, unlike the PKCS#1v1.5 encoding method. Despite being the recommended method for the last decade, it is not used in practice as much as you'd expect. RSASSA-PSS

The PSS encoding method is used to encode before creating a signature. The technique is described in PKCS#1v2.1 and is similar in design to the OAEP encoding used for encryption involving an MGF based on a hash function. However, there are active patents associated with this method, so sensible implementators avoid it like the plague. There are also currently no known weaknesses with the PKCS#1v1.5 signature scheme.