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 **the RSA problem** (and its related integer factorization problem). The **RSA sign / verify** algorithm works as described below.

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

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

â€‹$(m^e)^d \equiv (m^d)^e \equiv m \pmod n$ for all ** m** in the range [0...

**Signing** a message ** msg** with the private key exponent

Calculate the message hash:

= hash(*h*)*msg*Encrypt

to calculate the signature: $s = h^d \pmod n$â€‹*h*

The hash ** h** should be in the range [0...

**Verifying** a signature ** s** for the message

Calculate the message hash:

= hash(*h*)*msg*Decrypt the signature: $h' = s^e \pmod n$â€‹

Compare

with*h*to find whether the signature is valid or not*h'*

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

â€‹$h' = s^e \pmod n = (h^d)^e \pmod n = h$â€‹

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