First, let's recall Modular Arithmetic!

RSA

RSA cryptosystem -- was developed by Ron Rivest, Adi Shamir and Leonard Adleman in 1977.

Basic formula

(MsgE1)E2 = (MsgE2)E1 = Msg (mod M)

Msg -- Message
E1  -- Exponent 1
E2  -- Exponent 2
M   -- calculation Module

Message encryption

 MsgoExp = eMsg (mod M) -- encryption with a open exponent (Public key)
eMsgsExp =  Msg (mod M) -- decryption with a secret exponent (Private key)

eMsg -- encrypted Message
 M   -- Modulo of the Recipient of the message

Public key encryption encrypts data sent to the owner of the corresponding private key. This function became the primary application.

Signing a message

 MsgsExp = sMsg (mod M) -- signing with a secret exponent (Private key)
sMsgoExp =  Msg (mod M) -- verification with a open exponent (Public key)

sMsg -- message Signature
 M   -- Modulo of the message Sender

A message encrypted with one key of the pair can be decrypted with only the other key of the same pair. If a message is successfully decrypted by the public key, then it was encrypted using an only matching private key. Thus, the ciphertext obtained as a result of using the private key can be considered the digital equivalent of the signature on the decrypted document.

Defining a Basic Module

Use Finding Prime Numbers or . More short numbers you can get at Dumb Primality Test form.

M Modulus

The RSA modulus is non-secret and use for encryption and decryption. Determining the pair of numbers (A, B) that make up a modulus is extremely difficult -- Integer Factorization.

λ Carmichael function

M = A × B -- Product of two prime numbers
λ(M) = lcm(λ(A), λ(B)) -- Carmichael function
λ(x) = φ(x) -- For prime numbers, the Carmichael function coincides with the Euler function.
φ(x) = x − 1 -- The Euler function for prime numbers has a trivial definition.
lcm(p, q) = |p × q| / gcd(p, q) -- Calculating the Least Common Multiple using the Greatest Common Divisor.

oExp Open exponent (Public key)

1 < oExp < λ(M) -- Public Key must be less than the Carmichael function.
gcd(oExp, λ(M)) = 1 -- oExp and λ(M) are coprime

The usual exponent 65537 = 2¹⁶+1 = 100000000000000001₍₂₎ is a prime number. This frees us from checking the greatest common divisor for any λ.

sExp Secret exponent (Private key)

Keys summary

Encryption and decryption the message

(1) Any sender of a message encrypts it using the Public Key (Modulo and Open Exponent) of the message recipient.

(2) The message can only be decrypted using the secret exponent. Only the module's creator can calculate the secret exponent.

Encryption

Decryption

Signing and verifying the message signature

(1) The module owner encrypts the message using a secret key.

(2) Anyone can decrypt this message using the public key.

The ciphertext obtained using the secret key cannot be obtained in any other way. Thus, the result of the encryption operation is unique and can be interpreted as equivalent to a message signature.

Signing

Verifying

One formula

Review the previous four forms. They implement four operations.

1. Encrypting the message sent to the module owner.
2. Decryption of message by module owner.
3. Signing a message by the module owner.
4. Checking message signature.

The same formula is used for all operations -- A^B (mod M). Try checking your previous calculations using the following form.

Let us consider once again the operation of raising to a power by modulo.

Terminology and functionality

Public exponent

Used for encryption and signature verification.

Modulus

Used for encryption and decryption. It is public and can be used as an owner identifier.

Secret exponent

Used for signing and decrypting messages.

Public key

Modulus and Public Exponent.

Private key

Modulus and Secret Exponent.