Rivest-Shamir-Adleman Algorithm

Definition

Rivest-Shamir-Adleman Algorithm

The Rivest-Shamir-Adleman algorithm (RSA) is an asymmetric encryption scheme whose security relies on the hardness of the integer factorisation problem.

Algorithm

Let be the modulus consisting of two large prime numbers , with:

• Public key where is the public exponent
• Private key where is the private exponent

Cryptographic Hardness

Security depends on the size :

• Primes are typically between and bits long
  The larger, the better (but also slower)

Key Generation

Key Generation: Generate two large prime numbers and compute the modulus . Choose a public exponent coprime to . The private exponent is the multiplicative inverse of modulo :

• If the inverse exists,

• The extended Euclidean algorithm can be used for this purpose.

Speedup

To speed-up encryption, is typically a small number (e.g., ).

Generation of Large Prime Numbers

1. Randomly generate an odd number of the desired bit length.
2. Test if small prime numbers (e.g. those smaller than 1000) divide the generated number.
3. Iterate the Miller-Rabin test on the generated number to ensure primality.

• If the test says that the number is not prime, the answer is always correct.
• If the test says that the number is prime, the answer might be wrong (probability )
• Iterating the test times reduces the probability of mistakes to .

Encryption Scheme

RSA can be used as an asymmetric encryption scheme. Encryption uses the public key; decryption uses the private key.

Encryption

Let be the plaintext and be the corresponding ciphertext, then:

Decryption

Let be the plaintext and be the corresponding ciphertext, then:

Signature Scheme

RSA can also be used as an asymmetric signature scheme. The roles of the keys are reversed compared to encryption.

Malleability

The malleability of RSA can be used to generate valid signatures for new messages from signatures of other messages. If and are valid signatures, then

is a valid signature for the message .

Furthermore, if the private key’s owner is willing to sign only some messages, an attacker can obtain arbitrary signatures. To sign a message , the attacker chooses with , asks for a signature on , and computes

This is a valid signature for , since

Signing

Let be the message and be the signature, then:

Verification

Let be the message and be the signature, then:

Correctness

Theorem

For all positive integer messages , it holds that

Proof

By construction of , we have for some . Then

Case : By Euler’s theorem, , so

Case : Since , either or . Assume (the other case is symmetric). Then for some .

Since , Euler’s theorem gives . Hence

Therefore for some , and

Issues

Determinism

If the same message is encrypted multiple times with the same public key, the produced ciphertexts are the same. Textbook RSA is deterministic.

Small Messages and Public Exponents

Given a ciphertext , it holds that for some . When both and are small, is not much larger than , and the plaintext can be reconstructed by brute-forcing the possible values of and computing the \textsuperscript{th} root:

Padding

The plaintext is extended with randomly generated components to bring it to the size of the modulus . The padded plaintext is then encrypted as usual. Usage of padding prevents both previous attacks (determinism and small messages).

PKCS#1 v. 1.5

Simple, but vulnerabilities are known.

Definition

Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding (OAEP) is a padding algorithm for RSA encryption. It is recommended for new applications.

Link to original