Digital Signature Algorithm - Signing

Signing

Let be the hashing function and the message:

• Generate a random per-message value where
• Calculate
• In the unlikely case that, start again with a different random
• Calculate
• In the unlikely case that, start again with a different random
• The signature is

The first two steps amount to creating a new per-message key. The modular exponentiation here is the most computationally expensive part of the signing operation, and it may be computed before the message hash is known. The modular inverse is the second most expensive part, and it may also be computed before the message hash is known. It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as .