Notes - Computer Security MT24, RSA cryptosystem

Created: November 03, 2024
Updated: November 04, 2024

Flashcards

Describe the RSA @algorithm by explaining how Alice would send a message to Bob, and how Bob would generate his keys.

Alice wants to send a message to Bob. To do this, Alice encrypts her message using Bob’s public key. Bob can then decrypt the message using his private key.

Key generation:

  • Bob chooses a key length of $b$ bits.
  • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
  • Let $n = pq$, their $b$-bit product.
  • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
  • Choose an integer $e$ which is coprime to $\phi$.
  • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
  • The public key is then the pair: $pk _ B = \langle n, e \rangle$.
  • The private key is then the pair: $sk _ B = \langle n, d \rangle$.

Encryption:

  • Alice has a message $m$.
  • Pad $m$.
  • Calculate $E _ {pk _ B}(m) := m^e \pmod n$.

Decryption:

  • Bob receives ciphertext $c$.
  • Calculate $D _ {sk _ B}(c) := c^d \pmod n$.
  • Discard padding.

What “trapdoor function” does the RSA algorithm make use of?
  • Easy: Given $n$ and $e$, it is easy to compute $m^e \pmod n$ from $m$.
  • Difficult: Find $m$ given $e$ and $m^e \pmod n$.
  • Easy with extra info: Given the factors of $n$, it’s easy to find $m$ given $e$ and $m^e \pmod n$.

The RSA algorithm could be summarised as follows:

  • Key generation:
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key is then the pair: $sk _ B = \langle n, d \rangle$.
  • Encryption:
    • Alice has a message $m$.
    • Pad $m$.
    • Calculate $E _ {pk _ B}(m) := m^e \pmod n$.
  • Decryption:
    • Bob receives ciphertext $c$.
    • Calculate $D _ {sk _ B}(c) := c^d \pmod n$.
    • Discard padding.

What is $\mathcal K$, $\mathcal M$ and $\mathcal C$ in this context?
  • $\mathcal K$ is the set of all $b$ bit numbers $n$ that are the products of two $b/2$ bit primes $p$ and $q$
  • $\mathcal M$ is the set $\{0, 1, \ldots, n - 1\}$
  • $\mathcal C$ is the set $\{0, 1, \ldots, n - 1\}$

The RSA algorithm could be summarised as follows:

  • Key generation:
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key is then the pair: $sk _ B = \langle n, d \rangle$.
  • Encryption:
    • Alice has a message $m$.
    • Pad $m$.
    • Calculate $E _ {pk _ B}(m) := m^e \pmod n$.
  • Decryption:
    • Bob receives ciphertext $c$.
    • Calculate $D _ {sk _ B}(c) := c^d \pmod n$.
    • Discard padding.

@Prove its correctness, i.e. that

\[D _ {sk _ B}(E _ {pk _ B}(m)) = m\]

Since $m$ is smaller than $n$ (by definition, the set of all possible messages is the set of all integers less than $n$) it suffices to check that

\[D _ {sk _ B}(E _ {pk _ B}(m)) \equiv m \pmod n\]

Applying the definitions gives that

\[D_{sk _ B}(E _ {pk _ B}(m)) \equiv m^{ed} \pmod n\]

The key generation algorithm requires that $ed \equiv 1 \pmod \phi$, which implies that

\[ed = 1 + k(p-1)(q-1)\]

for some integer $k$.

Now we calculate $m^{ed} \pmod p$ and $m^{ed} \pmod q$:

\[\begin{aligned} m^{ed} &= m^{1 + k(p-1)(q-1)} \\\\ &= m \cdot m^{k(p-1)(q-1)} \\\\ &= m \cdot (m^{p-1})^{k(q-1)} \\\\ &= \begin{cases} m \cdot 0^{k(q-1)} &\text{if } p \mid m \\\\ m \cdot 1^{k(q-1)} &\text{otherwise} \\\\ \end{cases} \\\\ &\equiv m \pmod p \end{aligned}\]

and

\[\begin{aligned} m^{ed} &= m^{1 + k(p-1)(q-1)} \\\\ &= m \cdot m^{k(p-1)(q-1)} \\\\ &= m \cdot (m^{q-1})^{k(p-1)} \\\\ &= \begin{cases} m \cdot 0^{k(p-1)} &\text{if } q \mid m \\\\ m \cdot 1^{k(p-1)} &\text{otherwise} \\\\ \end{cases} \\\\ &\equiv m \pmod q \end{aligned}\]

So

\[\begin{aligned} &m^{ed} \equiv m \pmod p \\\\ &m^{ed} \equiv m \pmod q \end{aligned}\]

Which together imply that

\[\begin{aligned} &p \mid m^{ed} - m \quad\text{ and,}\\\\ &q \mid m^{ed} - m \end{aligned}\]

Therefore

\[pq \mid m^{ed} - m\]

and so

\[m^{ed} \equiv m \pmod{pq}\]

which is the result we wanted.

The RSA algorithm could be summarised as follows:

  • Key generation:
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key is then the pair: $sk _ B = \langle n, d \rangle$.
  • Encryption:
    • Alice has a message $m$.
    • Pad $m$.
    • Calculate $E _ {pk _ B}(m) := m^e \pmod n$.
  • Decryption:
    • Bob receives ciphertext $c$.
    • Calculate $D _ {sk _ B}(c) := c^d \pmod n$.
    • Discard padding.

What is the time complexity of each step?
  • Key generation: $O(b^3)$
    • (primality testing: $O(b^3)$, Euclid’s algorithm: $O(b)$)
  • Encryption: $O(b^2)$ (when $e$ is fixed)
    • (number of multiplications: $O(1)$, multiplication: $O(b^2)$)
  • Decryption: $O(b^3)$
    • (number of multiplications: $O(b)$, multiplication: $O(b^2)$)

Roughly how many times slower is RSA compared to symmetric key ciphers like DES when implemented on a computer?
\[\approx 10,000\]

@Define the RSA problem.

From the ciphertext $m^e \pmod n$, and given $n$ and $e$, deduce $c$.

What is the relationship between solving the RSA problem and solving the integer factorisation problem?

Solving the RSA problem is at least as easy as solving integer factorisation, but it might be easier.

Why shouldn’t you encrypt $0$ or $1$ using RSA?

Since these messages encrypt to themselves.

Why shouldn’t you encrypt small messages $m$ using RSA?

Because when $m < \sqrt[e]{n}$, $m^e \pmod n$ will just equal $m^e$, which can be reversed easily.

What’s a standard-sized RSA key size today?

2048 bits.

Suppose that Alice wants to send a short password to Bob using RSA. Why would it be a mistake to just encrypt the short password?

Because an attacker could try an offline dictionary attack by encrypting all possible passwords with Bob’s public key.

Describe the same-message attack on RSA.

@todo, once have completed the sheet.

@Define the homomorphic property of RSA, which leads to some weaknesses.
\[E _ {pk _ B}(m_1) \cdot E _ {pk _ B}(m_2) = E _ {pk _ B}(m_1 \cdot m_2)\]

The homomorphic property of RSA is that

\[E _ {pk _ B}(m_1) \cdot E _ {pk _ B}(m_2) = E _ {pk _ B}(m_1 \cdot m_2)\]

Describe a chosen ciphertext attack that exploits this.
  • The attacker intercepts an encrypted message $c = m^e \pmod n$
  • Multiply by the encryption of a random number $r^e \pmod n$
  • Ask the decryption oracle to decrypt $r^e c$, which gives them $rm$
  • Then multiply $rm$ by $r{-1} \pmod n$ to recover $m$

Describe the PKCS#1 v1.5 padding @algorithm for RSA with $e$ fixed as $3$.

Suppose that we want to encrypt some payload using the public key $\langle n, e\rangle$.

  • Compute the maximum number of whole bytes guaranteed to fit within the modulus, $B = \lfloor \log _ 2(n-1)/8 \rfloor$.
  • The payload will be padded to $B$ byes.
  • Suppose that the payload is $p \le B - 11$ bytes long.
  • Construct a plaintext $m$ via the bytestream $00\text{ }02\text{ }\mathbf{Padding}\text{ }00\text{ }\mathbf{Payload}$, where $\mathbf{Padding}$ is a sequence of $B - p - 3$ nonzero bytes.

The PKCS#1 v1.5 padding algorithm for RSA with $e$ fixed as $3$ works as follows: Suppose that the public key is $\langle n, e \rangle$ and we want to encrypt some payload $p$ bytes long. Then:

  • Compute the maximum number of whole bytes guaranteed to fit within the modulus $n$, $B = \lfloor \log _ 2(n-1)/8 \rfloor$.
  • The payload will be padded to $B$ byes.
  • Suppose that the payload is $p \le B - 11$ bytes long. (why, @todo).
  • Construct a plaintext $m$ via the bytestream $m = 00\text{ }02\text{ }\mathbf{Padding}\text{ }00\text{ }\mathbf{Payload}$, where $\mathbf{Padding}$ is a sequence of $B - p - 3$ nonzero bytes.

Some of the simple attacks against RSA are as follows:

  1. $0$ or $1$ will encrypt to themselves, so if these are sent as messages an attacker could work them out.
  2. If the message $m$ is small ($m < \sqrt[3]{n}$) then the $m^e$ will not wrap around and will be easy to invert.
  3. If Alice wants to send messages from a small set, an attacker can use the public key to brute force the plaintext by encrypting every message in the set and seeing which one matches.
  4. If Alice shares the same message with many people then there is a weakness (the same-message attack).
  5. The homomorphic property of RSA can lead to weaknesses.
  6. If an attacker has access to a decryption oracle (a chosen ciphertext attack) then can exploit properties of RSA to decrypt a message from decryptions of other messages.

How does this padding scheme scupper any of these attacks?
  1. $0$ and $1$ are never sent as messages.
  2. The leading bytes ensure that $m > \sqrt[3]{n}$.
  3. The random bytes ensure that the messages don’t come from a small set.
  4. It’s very unlikely that the same message will be sent to different people because of the random bytes.
  5. The padding bytes should confuse attempts to use the homomorphic property.
  6. A decryption oracle should at least refuse to decrypt incorrectly padded messages.

Describe the @algorithm for digital signatures with RSA.

Key generation: (same as for asymmetric encryption case)

  • Bob chooses a key length of $b$ bits.
  • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
  • Let $n = pq$, their $b$-bit product.
  • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
  • Choose an integer $e$ which is coprime to $\phi$.
  • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
  • The public key (verification key) is then the pair: $pk _ B = \langle n, e \rangle$.
  • The private key (signing key) is then the pair: $sk _ B = \langle n, d \rangle$.

Signing a message:

\[\mathsf{SIGN} _ {sk _ A}(m) = m^d \pmod n\]

Verifying a message:

\[\mathsf{VER} _ {pk _ A}(m, x) = (x^e \equiv m \pmod n)\]

The RSA algorithm for signatures could be summarised as so:

  • Key generation: (same as for asymmetric encryption case)
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key (verification key) is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key (signing key) is then the pair: $sk _ B = \langle n, d \rangle$.
  • Signing a message:
    • $\mathsf{SIGN} _ {sk _ A}(m) = m^d \pmod n$
  • Verifying a message:
    • $\mathsf{VER} _ {pk _ A}(m, x) = (x^e \equiv m \pmod n)$

Describe a universal forgery under a chosen message attack.

For any message $m$, the attacker picks a random $r$ coprime to $n$, and asks for the signatures

\[\mathsf{SIGN}(r^{-1}) = (r^{-1})^d \pmod n\]

and

\[\mathsf{SIGN}(mr) = (mr)^d \pmod n\]

But multiplying these two signatures together modulo $n$ gives a signature for $m$:

\[\mathsf{VER}((r^{-1})^d (mr)^d, m) = \mathsf{VER}(m^d, m) = (m^{ed} \equiv m \pmod n)\]

The RSA algorithm for signatures could be summarised as so:

  • Key generation: (same as for asymmetric encryption case)
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key (verification key) is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key (signing key) is then the pair: $sk _ B = \langle n, d \rangle$.
  • Signing a message:
    • $\mathsf{SIGN} _ {sk _ A}(m) = m^d \pmod n$
  • Verifying a message:
    • $\mathsf{VER} _ {pk _ A}(m, x) = (x^e \equiv m \pmod n)$

Describe a existential forgery under the known message attack.

Suppose the attacker knows two signatures

\[\mathsf{SIGN}(m_1) = m_1^d \pmod n\]

and

\[\mathsf{SIGN}(m_2) = m^d_2 \pmod n\]

They can find a signature for $m _ 1 m _ 2$ by multiplying these two messages together, since

\[\mathsf{VER}(m_1 m_2, m_1^d m_2^d) = \mathbf{true}\]

The RSA algorithm for signatures could be summarised as so:

  • Key generation: (same as for asymmetric encryption case)
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key (verification key) is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key (signing key) is then the pair: $sk _ B = \langle n, d \rangle$.
  • Signing a message:
    • $\mathsf{SIGN} _ {sk _ A}(m) = m^d \pmod n$
  • Verifying a message:
    • $\mathsf{VER} _ {pk _ A}(m, x) = (x^e \equiv m \pmod n)$

Describe a existential forgery under a key-only attack.

Pick any number $x$ and compute $x^e !\pmod n$. Then they can sign $x^e !\pmod n$ since

\[\mathsf{VER}(x^e, e) = (x^e \equiv x^e \pmod n) = \mathbf{true}\]

The RSA algorithm for signatures could be summarised as so:

  • Key generation: (same as for asymmetric encryption case)
    • Bob chooses a key length of $b$ bits.
    • He then picks two random prime numbers $p$ and $q$, each $b/2$ bits in size.
    • Let $n = pq$, their $b$-bit product.
    • Let $\phi = \phi(n) = (p-1)(q-1)$, the totient of $n$.
    • Choose an integer $e$ which is coprime to $\phi$.
    • Find an integer $d$ such that $ed \equiv 1 \pmod \phi$.
    • The public key (verification key) is then the pair: $pk _ B = \langle n, e \rangle$.
    • The private key (signing key) is then the pair: $sk _ B = \langle n, d \rangle$.
  • Signing a message:
    • $\mathsf{SIGN} _ {sk _ A}(m) = m^d \pmod n$
  • Verifying a message:
    • $\mathsf{VER} _ {pk _ A}(m, x) = (x^e \equiv m \pmod n)$

One existential forgery key-only attack can be performed like so: pick any number $x$ and compute $x^e !\pmod n$. Then they can sign $x^e !\pmod n$ since

\[\mathsf{VER}(x^e, e) = (x^e \equiv x^e \pmod n) = \mathbf{true}\]

How can you mitigate this particular attack, and for similar attacks against digital signatures in general?

Make the signature recognisable in some way, e.g. by using

\[\mathsf{SIGN} _ {sk_A}(\mathbf{Alice} \parallel m)\]

and asking the verifier to check the prefix, or hashing the message before signing.

Why is hashing a message before signing it not always a good idea?

Because it means hash collisions could translate to the same signature signing multiple messages.



Related posts