tldr

RSA works by exploiting the fact we can’t easily factor 2 large prime numbers and group theory to make a trapdoor permutation, aka a function that turns x into y but y can’t easily be turned into x without a secret. However, implementing RSA gets tricky because there’s lots of subtle attacks.

RSA takes advantage of the group Z^*_{n} (multiplicative group of integers modulo n). This is the non-negative integers less than n that have an inverse modulo n. 1 x 1 mod n = 1. 0 x int = 0 so it’s not in the group. Elements in this group are all co-prime with n. Euler’s totient function can give use the number of elements in this group:

if n = prime1 x prime2 … primem, there are (prime1 - 1) x (prime2 - 1) x … (primem -1) elements. -- This is called the order of the group.

For RSA, n = pq. So there are (p-1)x(q-1)=n+1-q-p elements. (n numbers from 1 to n - q numbers that are multiples of p - p numbers that are multiples of q + 1 bc n is a multiple of qp and pq so it got subtracted twice).

The trapdoor permutation is what transforms a secret key into a public key.

For RSA, we generate large primes p,q, and a number from Z*_n e. Then we find d such that ed mod (pq+1-p-q) = 1. This allows us to generate y = x^e mod n. And then we can get x back by raising y^d mod n = x^(de) mod n = x^1 mod n.

In this scheme, the public key is n and e (public exponent) and the secret key is d (secret exponent). p,q, and the order of Z*_n should be kept secret.      If you know p you can compute gcd(n, p) = q easily (and vice versa if you have q to find p). You then can pq+1-p-q to find the order. With the order and e, you can easily find d and find the secret.

There are 2 hard problems that protect RSA. The first, is that it is hard to factor n into p and q. The second, is that it is hard to find the eth root of x^e mod n. We think these problems are about equally hard but don’t know for sure.

RSA can be used to both encrypt/decrypt and sign/verify. Generally, it’s used in tandem with symmetric schemes. RSA allows 2 parties to securely create a symmetric key and then that key is used.

Using RSA as exactly described with math above is called “textbook RSA” and SHOULD NEVER be used. It has vulnerabilities for both encrypting and signing that will be discussed below.

It’s also worth pointing out the for both encrypting and signing, the security level depends on the size of n and the choice of p&q. If n is too small the key can be brute forced. A minimum of 2048 bits should be used (about 90 bits of security aka 2^90 operations) and 4096 bits is ideal (about 128 bits of security). p & q should be random primes that are of similar size, not too small, and not too close together. And of those reasons make it easier to figure out p/q from n.

Failings of textbook RSA

The simple version of RSA just using the above math has issues. The first is that it is deterministic, i.e., encrypting the same plaintext results in the same ciphertext. The second and bigger issue is that it is malleable: given 2 ciphertexts you can create a new, valid ciphertext and learn information about the plaintext.

y1 = x1^e mod n & y2 = x2^e mod n → y1 y2 mod n=(x1 x2)^e mod n, which is the ciphertext of the plaintext x1 times x2.     (I’m not exactly sure what information an attacker would learn from x1x2^e mod n but I imagine there’s ways to correlate data).

How to encrypt with OEAP

RSA should be used in conjunction with Optimal Asymmetric Encryption Padding (RSA-OAEP). This works by padding the message with random bytes. The randomness makes RSA non-deterministic and non-malleable.

To do RSA-OAEP, we need a message (say a symmetric key K), a PRNG, and 2 hash functions. RSA-OAEP is secure as long as the PRNG is secure and the hash functions aren’t too weak (not sure what is considered toooo weak).

RSA-OAEP then works like this for modulus n of m bytes:

• Create M = H || 00…0 || 01 || K, where H is a h-byte constant defined by OAEP and enough 0s to make the message the desired size. (K is m-2h-2 bytes & M is m-h-1 bytes)

• Generate a h-byte random string R

• Set M = M xor Hash1(R) -- note Hash1(R) is m-h-1 bytes

• Set R = R xor Hash2(M) -- note Hash2(M) is h bytes

• Create P = 00 || M || R, where P is m-bytes

• Convert P to an integer less than n and use that value as x

• Use RSA to generate x^e mod n

To decrypt:

• Compute x = y^d mod n

• Convert x to P and get back M and R

• Calculate M = M xor Hash1(R xor Hash2(M))

• Verify M = H || 00…0 || 01 || k

In practice, m is usually 256 bytes (for 2048 RSA) and h is 32 bytes (for SHA-256 as Hash2).

Hash1 has to has to have a length of m-h-1=223 bytes, which is an unusual length. Typically a mask generating hash function technique is used.

Signing with RSA is kinda the opposite of encrypting.

x^d mod n is the signature and you raise that to the e to get x^ed mod n = x mod n.      Note that while x is public you wouldn’t produce the signature of x but rather Hash(x). Because Hash(x) is a set size, this makes RSA signing much more efficient than encrypting. So while public/private key encryption is limited to smaller messages (mainly a symmetric key), public/private signing can be used with arbitrary sizes. (I think part of the reason for the inefficiency is the size of the key but I’m not sure).

Another interesting difference between signing and encrypting is that signing is still secure, even if it is deterministic. Signing only needs to protect from forgery where encryption needs to preserve confidentiality. So knowing that the same message was signed twice doesn’t compromise the goals of a signature scheme.

Failings of textbook RSA

Like with encryption, the math above signing isn’t secure. It can also be made secure via random padding like OAEP or other methods (discussed below).

One way RSA signing isn’t secure is that anyone can forge certain messages. 0^d mod n = 0, 1^d mod n = 1, and (n-1)^d mod n = n -1 for all private key ds.

The more significant way RSA signing is broken is through a blinding attack. Basically an adversary gets a victim into signing a message and then the adversary can manipulate that signature to create a new, valid signature. This works as follows:

• The adversary finds a R such that R^eM mod n is a message the victim would sign (note the adversary would know e)

• The adversary gets the victim to sign the message to create (R^eM)^d mod n = RM^d mod n

• The adversary divides the signature by R to create the valid signature M^d mod n

PSS

Similar to RSA with OAEP, we can use randomized padding to help fix the problems with textbook RSA. The standard is called Probabilistic Signature Scheme (PSS). We have to use PSS instead of OAEP because OAEP has only been proven secure of encryption.      PSS works by signing the Hash(message) and this is secure as long as the hash function is collision resistant. This allows us to sign messages of any length and normally SHA-256 is used.

PSS requires: a PRNG, Hash1 with h-bytes (usually SHA-256), and Hash2 with a wide output range. The process for signing message M with a modulus of length m-bytes is this:

• Prick an r-byte random string R using PRNG (R is called the salt and r-bytes is usually equal to h-bytes)

• Form M’ = 00 00 00 00 00 00 00 00 || Hash1(M) || R, which is 8 + h + r bytes

• Computes H = Hash1(M’) -- h-bytes

• Set L = 00…00 || 01 || R -- with enough 00 bytes such that L has length m-h-1

• Set L = L xor Hash2(H)

• Set P = L || H || BC -- with BC being a fixed value and P being m-bytes

• Convert P into a number x, which is lower than n

• Use x to compute x^d mod n

To verify a signature:

• Get x from (x^d)^e mod n

• Use x to get P to get L and H

• Get R from L and use it with Hash1(M) to compute M’ and Hash1(M’)

• Make sure that the padding and values all equal each other

PSS is standardize and secure. It is complicated and this can lead to implementation errors. Below is another method that is less complex and doesn’t need a PRNG.

Full Doman Hash Signatures (FDH)

FDH is very simple, convert Hash(M) into x less than n and sign that. Then you can verify a signature by turning the signature into x and recomputing Hash(H) → x.

When FDH is simple why deal with PSS?

PSS was released after FDH (in 1996) and has a security proof that offers slightly higher security guarantees (a lot of that coming from randomness).

Despite the stronger guarantees, most applications using PSS could switch to FDH without a meaningful security loss. However, there are some attacks that PSS does protect from the FDH is vulnerable to.

I’m not going to write too much here. Don’t try to implement RSA yourself. Current implementations are fast, secure, and as bug free as modern software can be.

However, there are some neat tricks worth highlighting.

RSA requires numbers to be raised to exponents (x^e). The naive way to do this takes e-1 operations. I.e.,

for i=1 to e-1:
  x = x * x

A faster way to do this would be through repeated squaring. To get x^8 we can do x=x^2. x=x^2. x=x^2. This takes 3 operations now instead of 7.

Now there are clever bit tricks to speed this up even more. You can scan the exponents value from left to right, square the number, and, if the bit is 1, multiple it by the original number.

This means the square and multiply method takes O(m) instead of O(2^m) time. You can get even faster optimizations with other tricks, such as a sliding window (see expNN() in go).

Unfortunately, these speed ups come a slight security cost. The time it takes to exponentiate will vary based on what the exponent is. This leads to a side-channel timing attack where an attacker could track how long it takes compute the RSA operations and figure out what the secret exponent is. This can also be done via hardware by monitoring the power consumption (more operations means both slower and the hardware has to use more power).      Only a minority of crypto libraries implement defenses against timing attacks and a smaller number still for the hardware power analysis.

Part of RSA is picking the public exponent e. If e is small, then x^e mod n is faster to computer. e is allowed to be any number between 3 and order(n) -1. Generally, e=65537 it is small with only two 1 bits and it is large enough to avoid low exponent attacks.      Because n is unique, e can be reused because d will be unique and unpredictable. d tends to be about as large as n, which makes decryptions much slower than encryption.
     I.e, the value of e=65537 ≈ 2^16 where d ≈ 2^2048 if n is 2048 bits. so raising a number to the e takes 17 operations when d would take about 3000.      This idea can be expanded to also think about signing taking much longer than verifying.

The Chinese remainder theorem lets us take an equation that has mod n and solve it in terms of n1, n2 … ni as long as ni,nj are co-prime. This can be applied to RSA because n=pq where p and q are different prime numbers.      I’m not going to write down the math. It will just me copying down latex in non-latex. You can look it up. Note, there are more optimizations in practice to speed this up further:

https://crypto.stackexchange.com/questions/2575/chinese-remainder-theorem-and-rsa

There is an attack on non-probabilistic RSA signature schemes (aka FHD not PSS) that use the Chinese Remainder Theorem. It is a type of fault attack, a type of attack where the system is forced to temporarily behave incorrectly. E.g., altering the voltage supply to change x to x’.      If you do this to a value in CRT and get the computer to use a wrong value during CRT (say during the mod q portion), the math ends up being vulnerable. A valid signature x minus invalid signature x is a multiple of p, which in turn can be used with n to find p, which finds q, which finds the order, and then d.

You can modify the attack to not even need a correct signature. Rather, you’d only need to know the message had been signed.

If your public key has the same n as someone else (or reused), the private keys aren’t safe. At a high level, it makes sense that the private key d shouldn’t be shared, so why share the public key?

To show why, imagine I know my own private key pair (n, d1), you have your private + public key pair (n, d2) & (n, e2), and I don’t know p or q.

We know that ed = const order(n) +1 [because x^ed mod n = x^1 mod n so ed mod order(n) = 1]. So we can compute const order(n) from ed -1. [note e1d1 mod order(n) = e2d2 mod order(n) = 1]

Using Euler’s Theorem we know a co-prime n, a^order(n) = 1 mod n.      a^const order(n) = 1^const mod n = 1 mod n.

We also know cost order(n) is even [feels right but I’m not 100% sure why]. This means we can write const order(n) = (2^s)t for some s and t. [somehow] we can use this to turn a^const order(n) = 1 mod n into x^2=1 for some easily computable x from const order(n) -- where x is the root of unity.

We then get x^2-1 = 0 mod n → (x+1)(x-1) = 0 mod n → either x+1 or x-1 has a common factor with n.

Look into:

• Bleichenbacher’s padding oracle attack on OAEP’s predessor

• Wiener’s attack on low private exponents

• Coppershmith’s method on RSA for small exponents with bad padding

• Side channel attacks

  https://ches.iacr.org/2021/program.php

https://ches.iacr.org/2022/affiliated.php

• “Twenty Years of Attacks on the RSA Cryptosystem”

• “Remote Timing Attacks Are Practical”

• Fault attacks see “On the Importance of Eliminating Errors in Cryptographic Computations”

• Checkout implementations in OpenSSL, NSS, Crypto++, or other.

BAM. Finally done.

Lucas

tldr

RSA works by exploiting the fact we can’t easily factor 2 large prime numbers and group theory to make a trapdoor permutation, aka a function that turns x into y but y can’t easily be turned into x without a secret. However, implementing RSA gets tricky because there’s lots of subtle attacks.

RSA takes advantage of the group Z^*_{n} (multiplicative group of integers modulo n). This is the non-negative integers less than n that have an inverse modulo n. 1 x 1 mod n = 1. 0 x int = 0 so it’s not in the group. Elements in this group are all co-prime with n. Euler’s totient function can give use the number of elements in this group:

if n = prime1 x prime2 … primem, there are (prime1 - 1) x (prime2 - 1) x … (primem -1) elements. -- This is called the order of the group.

For RSA, n = pq. So there are (p-1)x(q-1)=n+1-q-p elements. (n numbers from 1 to n - q numbers that are multiples of p - p numbers that are multiples of q + 1 bc n is a multiple of qp and pq so it got subtracted twice).

The trapdoor permutation is what transforms a secret key into a public key.

For RSA, we generate large primes p,q, and a number from Z*_n e. Then we find d such that ed mod (pq+1-p-q) = 1. This allows us to generate y = x^e mod n. And then we can get x back by raising y^d mod n = x^(de) mod n = x^1 mod n.

In this scheme, the public key is n and e (public exponent) and the secret key is d (secret exponent). p,q, and the order of Z*_n should be kept secret.      If you know p you can compute gcd(n, p) = q easily (and vice versa if you have q to find p). You then can pq+1-p-q to find the order. With the order and e, you can easily find d and find the secret.

There are 2 hard problems that protect RSA. The first, is that it is hard to factor n into p and q. The second, is that it is hard to find the eth root of x^e mod n. We think these problems are about equally hard but don’t know for sure.

RSA can be used to both encrypt/decrypt and sign/verify. Generally, it’s used in tandem with symmetric schemes. RSA allows 2 parties to securely create a symmetric key and then that key is used.

Using RSA as exactly described with math above is called “textbook RSA” and SHOULD NEVER be used. It has vulnerabilities for both encrypting and signing that will be discussed below.

It’s also worth pointing out the for both encrypting and signing, the security level depends on the size of n and the choice of p&q. If n is too small the key can be brute forced. A minimum of 2048 bits should be used (about 90 bits of security aka 2^90 operations) and 4096 bits is ideal (about 128 bits of security). p & q should be random primes that are of similar size, not too small, and not too close together. And of those reasons make it easier to figure out p/q from n.

Failings of textbook RSA

The simple version of RSA just using the above math has issues. The first is that it is deterministic, i.e., encrypting the same plaintext results in the same ciphertext. The second and bigger issue is that it is malleable: given 2 ciphertexts you can create a new, valid ciphertext and learn information about the plaintext.

y1 = x1^e mod n & y2 = x2^e mod n → y1 y2 mod n=(x1 x2)^e mod n, which is the ciphertext of the plaintext x1 times x2.     (I’m not exactly sure what information an attacker would learn from x1x2^e mod n but I imagine there’s ways to correlate data).

How to encrypt with OEAP

RSA should be used in conjunction with Optimal Asymmetric Encryption Padding (RSA-OAEP). This works by padding the message with random bytes. The randomness makes RSA non-deterministic and non-malleable.

To do RSA-OAEP, we need a message (say a symmetric key K), a PRNG, and 2 hash functions. RSA-OAEP is secure as long as the PRNG is secure and the hash functions aren’t too weak (not sure what is considered toooo weak).

RSA-OAEP then works like this for modulus n of m bytes:

• Create M = H || 00…0 || 01 || K, where H is a h-byte constant defined by OAEP and enough 0s to make the message the desired size. (K is m-2h-2 bytes & M is m-h-1 bytes)

• Generate a h-byte random string R

• Set M = M xor Hash1(R) -- note Hash1(R) is m-h-1 bytes

• Set R = R xor Hash2(M) -- note Hash2(M) is h bytes

• Create P = 00 || M || R, where P is m-bytes

• Convert P to an integer less than n and use that value as x

• Use RSA to generate x^e mod n

To decrypt:

• Compute x = y^d mod n

• Convert x to P and get back M and R

• Calculate M = M xor Hash1(R xor Hash2(M))

• Verify M = H || 00…0 || 01 || k

In practice, m is usually 256 bytes (for 2048 RSA) and h is 32 bytes (for SHA-256 as Hash2).

Hash1 has to has to have a length of m-h-1=223 bytes, which is an unusual length. Typically a mask generating hash function technique is used.

Signing with RSA is kinda the opposite of encrypting.

x^d mod n is the signature and you raise that to the e to get x^ed mod n = x mod n.      Note that while x is public you wouldn’t produce the signature of x but rather Hash(x). Because Hash(x) is a set size, this makes RSA signing much more efficient than encrypting. So while public/private key encryption is limited to smaller messages (mainly a symmetric key), public/private signing can be used with arbitrary sizes. (I think part of the reason for the inefficiency is the size of the key but I’m not sure).

Another interesting difference between signing and encrypting is that signing is still secure, even if it is deterministic. Signing only needs to protect from forgery where encryption needs to preserve confidentiality. So knowing that the same message was signed twice doesn’t compromise the goals of a signature scheme.

Failings of textbook RSA

Like with encryption, the math above signing isn’t secure. It can also be made secure via random padding like OAEP or other methods (discussed below).

One way RSA signing isn’t secure is that anyone can forge certain messages. 0^d mod n = 0, 1^d mod n = 1, and (n-1)^d mod n = n -1 for all private key ds.

The more significant way RSA signing is broken is through a blinding attack. Basically an adversary gets a victim into signing a message and then the adversary can manipulate that signature to create a new, valid signature. This works as follows:

• The adversary finds a R such that R^eM mod n is a message the victim would sign (note the adversary would know e)

• The adversary gets the victim to sign the message to create (R^eM)^d mod n = RM^d mod n

• The adversary divides the signature by R to create the valid signature M^d mod n

PSS

Similar to RSA with OAEP, we can use randomized padding to help fix the problems with textbook RSA. The standard is called Probabilistic Signature Scheme (PSS). We have to use PSS instead of OAEP because OAEP has only been proven secure of encryption.      PSS works by signing the Hash(message) and this is secure as long as the hash function is collision resistant. This allows us to sign messages of any length and normally SHA-256 is used.

PSS requires: a PRNG, Hash1 with h-bytes (usually SHA-256), and Hash2 with a wide output range. The process for signing message M with a modulus of length m-bytes is this:

• Prick an r-byte random string R using PRNG (R is called the salt and r-bytes is usually equal to h-bytes)

• Form M’ = 00 00 00 00 00 00 00 00 || Hash1(M) || R, which is 8 + h + r bytes

• Computes H = Hash1(M’) -- h-bytes

• Set L = 00…00 || 01 || R -- with enough 00 bytes such that L has length m-h-1

• Set L = L xor Hash2(H)

• Set P = L || H || BC -- with BC being a fixed value and P being m-bytes

• Convert P into a number x, which is lower than n

• Use x to compute x^d mod n

To verify a signature:

• Get x from (x^d)^e mod n

• Use x to get P to get L and H

• Get R from L and use it with Hash1(M) to compute M’ and Hash1(M’)

• Make sure that the padding and values all equal each other

PSS is standardize and secure. It is complicated and this can lead to implementation errors. Below is another method that is less complex and doesn’t need a PRNG.

Full Doman Hash Signatures (FDH)

FDH is very simple, convert Hash(M) into x less than n and sign that. Then you can verify a signature by turning the signature into x and recomputing Hash(H) → x.

When FDH is simple why deal with PSS?

PSS was released after FDH (in 1996) and has a security proof that offers slightly higher security guarantees (a lot of that coming from randomness).

Despite the stronger guarantees, most applications using PSS could switch to FDH without a meaningful security loss. However, there are some attacks that PSS does protect from the FDH is vulnerable to.

I’m not going to write too much here. Don’t try to implement RSA yourself. Current implementations are fast, secure, and as bug free as modern software can be.

However, there are some neat tricks worth highlighting.

RSA requires numbers to be raised to exponents (x^e). The naive way to do this takes e-1 operations. I.e.,

for i=1 to e-1:
  x = x * x

A faster way to do this would be through repeated squaring. To get x^8 we can do x=x^2. x=x^2. x=x^2. This takes 3 operations now instead of 7.

Now there are clever bit tricks to speed this up even more. You can scan the exponents value from left to right, square the number, and, if the bit is 1, multiple it by the original number.

This means the square and multiply method takes O(m) instead of O(2^m) time. You can get even faster optimizations with other tricks, such as a sliding window (see expNN() in go).

Unfortunately, these speed ups come a slight security cost. The time it takes to exponentiate will vary based on what the exponent is. This leads to a side-channel timing attack where an attacker could track how long it takes compute the RSA operations and figure out what the secret exponent is. This can also be done via hardware by monitoring the power consumption (more operations means both slower and the hardware has to use more power).      Only a minority of crypto libraries implement defenses against timing attacks and a smaller number still for the hardware power analysis.

Part of RSA is picking the public exponent e. If e is small, then x^e mod n is faster to computer. e is allowed to be any number between 3 and order(n) -1. Generally, e=65537 it is small with only two 1 bits and it is large enough to avoid low exponent attacks.      Because n is unique, e can be reused because d will be unique and unpredictable. d tends to be about as large as n, which makes decryptions much slower than encryption.
     I.e, the value of e=65537 ≈ 2^16 where d ≈ 2^2048 if n is 2048 bits. so raising a number to the e takes 17 operations when d would take about 3000.      This idea can be expanded to also think about signing taking much longer than verifying.

The Chinese remainder theorem lets us take an equation that has mod n and solve it in terms of n1, n2 … ni as long as ni,nj are co-prime. This can be applied to RSA because n=pq where p and q are different prime numbers.      I’m not going to write down the math. It will just me copying down latex in non-latex. You can look it up. Note, there are more optimizations in practice to speed this up further:

https://crypto.stackexchange.com/questions/2575/chinese-remainder-theorem-and-rsa

There is an attack on non-probabilistic RSA signature schemes (aka FHD not PSS) that use the Chinese Remainder Theorem. It is a type of fault attack, a type of attack where the system is forced to temporarily behave incorrectly. E.g., altering the voltage supply to change x to x’.      If you do this to a value in CRT and get the computer to use a wrong value during CRT (say during the mod q portion), the math ends up being vulnerable. A valid signature x minus invalid signature x is a multiple of p, which in turn can be used with n to find p, which finds q, which finds the order, and then d.

You can modify the attack to not even need a correct signature. Rather, you’d only need to know the message had been signed.

If your public key has the same n as someone else (or reused), the private keys aren’t safe. At a high level, it makes sense that the private key d shouldn’t be shared, so why share the public key?

To show why, imagine I know my own private key pair (n, d1), you have your private + public key pair (n, d2) & (n, e2), and I don’t know p or q.

We know that ed = const order(n) +1 [because x^ed mod n = x^1 mod n so ed mod order(n) = 1]. So we can compute const order(n) from ed -1. [note e1d1 mod order(n) = e2d2 mod order(n) = 1]

Using Euler’s Theorem we know a co-prime n, a^order(n) = 1 mod n.      a^const order(n) = 1^const mod n = 1 mod n.

We also know cost order(n) is even [feels right but I’m not 100% sure why]. This means we can write const order(n) = (2^s)t for some s and t. [somehow] we can use this to turn a^const order(n) = 1 mod n into x^2=1 for some easily computable x from const order(n) -- where x is the root of unity.

We then get x^2-1 = 0 mod n → (x+1)(x-1) = 0 mod n → either x+1 or x-1 has a common factor with n.

Look into:

• Bleichenbacher’s padding oracle attack on OAEP’s predessor

• Wiener’s attack on low private exponents

• Coppershmith’s method on RSA for small exponents with bad padding

• Side channel attacks

  https://ches.iacr.org/2021/program.php

https://ches.iacr.org/2022/affiliated.php

• “Twenty Years of Attacks on the RSA Cryptosystem”

• “Remote Timing Attacks Are Practical”

• Fault attacks see “On the Importance of Eliminating Errors in Cryptographic Computations”

• Checkout implementations in OpenSSL, NSS, Crypto++, or other.

BAM. Finally done.

Lucas