RSA I

\( \def\ZZ{\mathbb{Z}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \)

Public-Key Encryption: Setting

In the setting of private-key encryption, two parties agree on a secret key \( K \) which can be used (by either party) for both encryption and decryption. Public-key encryption is asymmetric in both these respects. In the setting of public-key encryption, one party (the receiver) generates a pair of keys \( (pk,sk) \), called the public key and the private key, respectively. The public key can be used by a sender to encrypt a message for the receiver; the receiver can then use the private key to decrypt the resulting ciphertext.

Since the goal is to avoid the need for two parties to meet in advance to agree on any information, how does the sender learn \( pk \)? At an abstract level, there are essentially two ways this can occur. Let us call the receiver Alice and the sender Bob. If Bob knows that Alice wants to communicate with him, he can at that point generate \( (pk,sk) \) (assuming he hasn't done so already) and then send \( pk \) in the clear to Alice; Alice can then use \( pk \) to encrypt her message. We emphasize that the channel from Alice to Bob may be public, but is assumed to be authenticated . That is, if adversary modifies data transferred over the channel, Alice and Bob should be able to detect it. This can be ensured by the public-key infrastructure (PKI), which we will learn later in more detail.

Fig 1. Setting of public-key encryption (Scenario 1)

An alternate way to picture the situation is that Bob generates her keys \((pk,sk)\) in advance, independent of any particular sender. (In fact, at the time of key generation Bob need not even be aware that Alice wants to talk to her or even that Alice exists!) Then Bob widely disseminates his public key \( pk \), say, by publishing it on his webpage, putting it on his business cards, publishing it in a newspaper, or placing it in a public directory. Now, anyone who wishes to communicate privately with Bob can look up his public key and proceed as above. Note that multiple senders can communicate multiple times with Bob using the same public key \( pk \) for all communication.

Fig2. Setting of public key encryption (Scenario 2)

Private-Key Cryptography vs. Public-Key Cryptography

Disadvantages of private-key cryptography

Key sharing: As we know already, securely sharing keys is sometimes difficult.
Key management: Even if key-sharing is possible, it is difficult to manage keys in a large organization. If a central server manages all keys, the server should manage \( {n \choose 2} = O(n^2) \) different keys.
Inapplicable to open systems: Private-key cryptography cannot be applied to open, dynamic systems such as e-commerce. Together with the disadvantages above, private-key cryptography requires you to know in advance the parties with whom you will communicate and share the keys. However, in an open system, you don't know who will communicate in the future.

Advantages of private-key cryptography or disadvantages of public-key cryptography

Speed: Private-key cryptography is about 1000 times faster then public-key cryptography.
Private-key cryptography still has domains of applicability such as military settings and disk encryption, where bidirectional, "one-to-one" communication is considered.
Public-key cryptography is harder to get right and has a large attack space simply because some keys are purely public.
Public-key cryptography needs to rely on the common belief such as hardness of discrete logarithm. However, it is known to be broken if we have quantum computers in the future.

Formal Definition of a Public-Key Encryption Scheme

A public-key encryption scheme \( \cal PE \) is defined by specifying a message space \( \cal M \) along with three algorithms \( ({\sf Gen}, {\sf Enc}, {\sf Dec}) \): a procedure for generating keys, a procedure for encrypting, a procedure for decrypting. The message space defines the set of "legal" messages, i.e., those supported by the scheme. The algorithms have the following functionality:

The key-generation algorithm \( \sf Gen \) is a randomized algorithm that takes the security parameter \( n \) and outputs a pair of keys \( (pk, sk) \). We refer to the first of these as the public key and the second as the private key. We denote this process by \( (pk, sk) \leftarrow {\sf Gen}(n) \) .
The encryption algorithm \( \sf Enc \) takes as input a public key \( pk \) and a message \( M \) and outputs a ciphertext \( C \) . We denote this process by \( C \leftarrow {\sf Enc}_{pk}(M) \).
The decryption algorithm \( \sf Dec \) takes as input a private key \( sk \) and a ciphertext \( C \) and outputs a plaintext \( M \) . We denote this process by \( M \leftarrow {\sf Dec}_{sk}(C) \).

The scheme \( \cal PE \) is said to provide correct decryption if for any key pair \( (pk, sk) \leftarrow {\sf Gen}(n) \) (we may allow negligible probability of generating a flawed pair), and for any message \( M \in {\cal M} \), it holds that

\( {\sf Dec}_{sk} ( {\sf Enc}_{pk} ( M ) ) = M \).

Security of PKE: IND-CPA and IND-CCA

Contrary to the private-key setting, the minimum threat model for the attacker is the chosen plaintext attack because the encryption key is public. Why?

The adversary also has the public key. So, it can freely encrypt any message it wants.

IND-CPA

A PKE encryption scheme \(({\sf Gen}, {\sf Enc}, {\sf Dec})\) is IND-CPA secure if considering the above game, for any polynomial time adversary \(A\) and for any large integer \(n\), the adverary \(A\) can make a correct guess with probability 1/2 + negl(n).

IND-CCA

Stronger security requirement is IND-CCA. The adversary has additionally a decryption box.

A PKE encryption scheme \(({\sf Gen}, {\sf Enc}, {\sf Dec})\) is IND-CCA secure if considering the above game, for any polynomial time adversary \(A\) and for any large integer \(n\), the adverary \(A\) can make a correct guess with probability 1/2 + negl(n).

Number Theory

For a prime number \( p \), we have \( \phi(p) = p - 1 \). For two prime numbers \( p, q \), we have \( \phi(p \cdot q ) = (p-1) (q-1) \).

For any positive integer \(n\), and for any \(a \in \ZZ_n^*\), it holds \(\) a^{\phi(n)} \bmod n = 1 .\(\)

The above can be extended as follows:

For any positive integer \(n\), for any \(a \in \ZZ_n^*\), and for any integer \(x\), it holds \(\) a^x \bmod n = a^{r} \bmod n,\(\) where \(r = x \bmod{\phi(n)}\).

Proof

Since \(r = x \bmod {\phi(n)}\), we have \(\)x = q \cdot \phi(n) + r.\(\) Here, \(q\) is the quotient obtain from dividing \(x\) by \(\phi(n)\). Therefore, we have \(\)a^x \bmod n = a^{\phi(n) \cdot q + r} \bmod n = (a^{\phi(n)})^q \cdot a^{r} \bmod n = 1 \cdot a^{r} \bmod n = a^r \bmod n.\(\)

Example

Let \(n = 15\). Then, we have \(4^{81} \bmod 15 = 4^1 \bmod 15 = 4.\)


>>> pow(4, 81, 15)
4

RSA Encryption Scheme

Rivest, Shamir, and Adleman published a paper that describes the first public-key encryption scheme in 1978.

Main Idea

The RSA encryption scheme considers \(n = p q\) for primes \(p\) and \(q\). More importantly, it considers the case in which \(r = 1\).

For example, consider \(n = 11 \cdot 13 = 143\).

Consider \(x = 721\). Note that \(r = x \bmod{ \phi(n) } = 721 \bmod 120 = 1.\)
Since \(r = 1\), we have \[a^x = a^r = a \pmod{n}\]


>>> for a in range(12, 20):
...   print("a=", a, ", pow(a, 721, 143)=", pow(a, 721, 143))
...
a= 12 , pow(a, 721, 143)= 12
a= 13 , pow(a, 721, 143)= 13
a= 14 , pow(a, 721, 143)= 14
a= 15 , pow(a, 721, 143)= 15
a= 16 , pow(a, 721, 143)= 16
a= 17 , pow(a, 721, 143)= 17
a= 18 , pow(a, 721, 143)= 18
a= 19 , pow(a, 721, 143)= 19

Consider \(x = 841\). Note that \(r = x \bmod{ \phi(n) } = 841 \bmod 120 = 1.\)
Since \(r = 1\), we have \[ a^x = a^r = a \pmod{n} \]


>>> for a in range(12, 20):
...   print("a=", a, ", pow(a, 841, 143)=", pow(a, 841, 143))
...
a= 12 , pow(a, 841, 143)= 12
a= 13 , pow(a, 841, 143)= 13
a= 14 , pow(a, 841, 143)= 14
a= 15 , pow(a, 841, 143)= 15
a= 16 , pow(a, 841, 143)= 16
a= 17 , pow(a, 841, 143)= 17
a= 18 , pow(a, 841, 143)= 18
a= 19 , pow(a, 841, 143)= 19

How is this related to the encryption/decryption though?

Recall that the correctness of the encryption scheme means that decrypted message should be the same as the message that was encrypted. In a sense, the condition of "being the same" is somehow captured in the exponent \(x\).
There are many different \(x\)'s such that \(x \bmod{\phi(n)}\) equals 1.
Main conceptual ideas: We will talk about the details in the next lecture.
- Split \(x\) into two factors \(e\) and \(d\). That is, \(e \cdot d = x\).
- Use \(e\) for encryption and \(d\) decryption.
- Encryption of \(m\) is \(m^e\).
- Decryption of \(c\) is \(c^d\).
- \({\sf Dec}( {\sf Enc} (m)) = (m^e)^d = m^{ed} = m^x = m\).

Examples

Split \(x = 721\) into \(e = 7\) and \(d = 103\).

Consider a message \(m = 71\).

Encryption of message (m = 71, e = 7):
```
>>> pow(71, 7, 143)
124
```


Decryption of the ciphertext (c=143, d=103):
>>> pow(124, 103, 143)
71

Consider a message \(m = 34\).

Encryption of message (m=34, e = 7):
```
>>> pow(34, 7, 143)
122
```


Decryption of the ciphertext (c=122, d=103):
>>> pow(122, 103, 143)
34