Return to Answer

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.
 $(e, n)$ is the public key, $(d, n)$ the private one.

• To encrypt a message $m$, compute $c\equiv m^e\mod n$.
• To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65537 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\varphi(n))=1$ (where $\varphi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\bmod{\varphi(n)}$. In other words, $d$ is the modular inverse of $e$, ($d\equiv e^{-1}\bmod{\varphi(n)}$).

$(e, n)$ is the public key, $(d, n)$ the private one.

• To encrypt a message $m$, compute $c\equiv m^e\mod n$.
• To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65537 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.
$(e, n)$ is the public key, $(d, n)$ the private one.

• To encrypt a message $m$, compute $c\equiv m^e\mod n$.
• To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65567 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.
$(e, n)$ is the public key, $(d, n)$ the private one.

• To encrypt a message $m$, compute $c\equiv m^e\mod n$.
• To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65537 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.

To encrypt a message $m$ compute $c\equiv m^e\mod n$. To decrypt a ciphertext $c$, compute $c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$.

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems
3. $e$ is often statically set to $65567$ for speed (since there are only two set bits in that number)
4. Side-channel attack mitigations can be put in place for deployed systems too

In no way is my list comprehensive, but hopefully this helps.

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.
$(e, n)$ is the public key, $(d, n)$ the private one.

• To encrypt a message $m$, compute $c\equiv m^e\mod n$.
• To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

1. It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
2. It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65567 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.