Practical Cryptography for Developers
  • Welcome
  • Preface
  • Cryptography - Overview
  • Hash Functions
    • Crypto Hashes and Collisions
    • Hash Functions: Applications
    • Secure Hash Algorithms
    • Hash Functions - Examples
    • Exercises: Calculate Hashes
    • Proof-of-Work Hash Functions
  • MAC and Key Derivation
    • HMAC and Key Derivation
    • HMAC Calculation - Examples
    • Exercises: Calculate HMAC
    • KDF: Deriving Key from Password
    • PBKDF2
    • Modern Key Derivation Functions
    • Scrypt
    • Bcrypt
    • Linux crypt()
    • Argon2
    • Secure Password Storage
    • Exercises: Password Encryption
  • Secure Random Generators
    • Pseudo-Random Numbers - Examples
    • Secure Random Generators (CSPRNG)
    • Exercises: Pseudo-Random Generator
  • Key Exchange and DHKE
    • Diffie–Hellman Key Exchange
    • DHKE - Examples
    • Exercises: DHKE Key Exchange
  • Encryption: Symmetric and Asymmetric
  • Symmetric Key Ciphers
    • Cipher Block Modes
    • Popular Symmetric Algorithms
    • The AES Cipher - Concepts
    • AES Encrypt / Decrypt - Examples
    • Ethereum Wallet Encryption
    • Exercises: AES Encrypt / Decrypt
    • ChaCha20-Poly1305
    • Exercises: ChaCha20-Poly1305
  • Asymmetric Key Ciphers
    • The RSA Cryptosystem - Concepts
    • RSA Encrypt / Decrypt - Examples
    • Exercises: RSA Encrypt / Decrypt
    • Elliptic Curve Cryptography (ECC)
    • ECDH Key Exchange
    • ECDH Key Exchange - Examples
    • Exercises: ECDH Key Exchange
    • ECC Encryption / Decryption
    • ECIES Hybrid Encryption Scheme
    • ECIES Encryption - Example
    • Exercises: ECIES Encrypt / Decrypt
  • Digital Signatures
    • RSA Signatures
    • RSA: Sign / Verify - Examples
    • Exercises: RSA Sign and Verify
    • ECDSA: Elliptic Curve Signatures
    • ECDSA: Sign / Verify - Examples
    • Exercises: ECDSA Sign and Verify
    • EdDSA and Ed25519
    • EdDSA: Sign / Verify - Examples
    • Exercises: EdDSA Sign and Verify
  • Quantum-Safe Cryptography
    • Quantum-Safe Signatures - Example
    • Quantum-Safe Key Exchange - Example
    • Quantum-Safe Asymmetric Encryption - Example
  • More Cryptographic Concepts
    • Digital Certificates - Example
    • TLS - Example
    • One-Time Passwords (OTP) - Example
  • Crypto Libraries for Developers
    • JavaScript Crypto Libraries
    • Python Crypto Libraries
    • C# Crypto Libraries
    • Java Crypto Libraries
  • Conclusion
Powered by GitBook
On this page
  • Key Generation
  • RSA Sign
  • RSA Verify Signature

Was this helpful?

  1. Digital Signatures

RSA Signatures

PreviousDigital SignaturesNextRSA: Sign / Verify - Examples

Last updated 5 years ago

Was this helpful?

The RSA public-key cryptosystem provides a digital signature scheme (sign + verify), based on the math of the modular exponentiations and discrete logarithms and the computational difficulty of (and its related integer factorization problem). The algorithm works as described below.

Key Generation

The RSA algorithm uses keys of size 1024, 2048, 4096, ..., 16384 bits. RSA supports also longer keys (e.g. 65536 bits), but the performance is too slow for practical use (some operations may take several minutes or even hours). For 128-bit security level, a 3072-bit key is required.

The RSA key-pair consists of:

  • public key {n, e}

  • private key {n, d}

The numbers n and d are typically big integers (e.g. 3072 bits), while e is small, typically 65537.

By definition, the RSA key-pairs has the following property:

(me)d≡(md)e≡m(modn)(m^e)^d \equiv (m^d)^e \equiv m \pmod n(me)d≡(md)e≡m(modn) for all m in the range [0...n)

RSA Sign

Signing a message msg with the private key exponent d:

  1. Calculate the message hash: h = hash(msg)

  2. Encrypt h to calculate the signature: s=hd(modn)s = h^d \pmod ns=hd(modn)

The hash h should be in the range [0...n). The obtained signature s is an integer in the range [0...n).

RSA Verify Signature

Verifying a signature s for the message msg with the public key exponent e:

  1. Calculate the message hash: h = hash(msg)

  2. Compare h with h' to find whether the signature is valid or not

If the signature is correct, then the following will be true:

The RSA sign / verify algorithm is pretty simple. Let's implement it with some code.

Decrypt the signature: h′=se(modn)h' = s^e \pmod nh′=se(modn)

h′=se(modn)=(hd)e(modn)=hh' = s^e \pmod n = (h^d)^e \pmod n = hh′=se(modn)=(hd)e(modn)=h

the RSA problem
RSA sign / verify