Public-Key Cryptosystems and RSA

Public-key Cryptosystems

• Private-key cryptosystems require secure key exchange between parties.
• Public-key cryptosystems utilize a public key, distributed to anyone, and a private key, kept secret.
• Alice sends a message to Bob by using Bob's public key to encrypt the message.
• Bob then decrypts this message using his private key.
• Eve cannot decrypt the message, even if intercepted, without Bob's private key.
• Encryption algorithms need to easily allow Alice to encrypt using Bob's public key and to easily allow Bob to decrypt using his private key.
• Further, they must make it impossible for Eve to decrypt the message, even with Bob's public key.

RSA Cryptosystem: Basic Idea

• Invented in 1977 by Rivest, Shamir, and Adleman, RSA is based on number theory.
• It is easy to find two large prime numbers $p$ and $q$.
• Multiplying $p$ and $q$ to get $n$ is simple
• Factoring $n$ to retrieve $p$ and $q$ is very hard

How RSA Works

• Choose two large prime numbers, $p$ and $q$.
• Compute $n = pq$.
• Select an integer $e$ such that $1 < e < (p-1)(q-1)$ and $\gcd(e, (p-1)(q-1)) = 1$
• Determine $d$ as the inverse of $e$ modulo $(p-1)(q-1)$, meaning $de \equiv 1 \pmod{(p-1)(q-1)}$.
• The public key is $(n, e)$, and the private key is $d$.
• Encryption: $c = m^e \pmod{n}$, where $m$ is the message.
• Decryption: $m = c^d \pmod{n}$, where $c$ is the ciphertext.

RSA Functionality

• We have $de = 1 + k(p-1)(q-1)$ because $de \equiv 1 \pmod{(p-1)(q-1)}$ for some integer $k$.
• $c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k(p-1)(q-1)} \equiv m \cdot (m^{p-1})^{k(q-1)} \pmod{p}$
• $m^{p-1} \equiv 1 \pmod{p}$, according to Fermat's Little Theorem, if $p \nmid m$.
• $c^d \equiv m \cdot (m^{p-1})^{k(q-1)} \equiv m \cdot 1^{k(q-1)} \equiv m \pmod{p}$
• $m \equiv 0 \pmod{p}$ if $p \mid m$, therefore $c^d \equiv 0 \equiv m \pmod{p}$.
• $c^d \equiv m \pmod{p}$
• Similarly, $c^d \equiv m \pmod{q}$.
• $c^d \equiv m \pmod{n}$ because $c^d \equiv m \pmod{p}$ and $c^d \equiv m \pmod{q}$

RSA Example

• Assume $p = 7$ and $q = 11$.
• Thus, $n = pq = 77$ and $(p-1)(q-1) = 6 \cdot 10 = 60$.
• Let $e = 17$, where $\gcd(17, 60) = 1$.
• Find $d$ where $17d \equiv 1 \pmod{60}$, or $17d = 1 + 60k$ for some integer $k$.
• $d = 53$, since $17 \cdot 53 = 901 = 1 + 15 \cdot 60$.
• The public key is $(77, 17).
• The private key is $53$.
• For message $m = 2$, the encrypted message is $c = m^e \pmod{n} = 2^{17} \pmod{77} = 131072 \pmod{77} = 26$.
• Decryption: $m = c^d \pmod{n} = 26^{53} \pmod{77} = 2$.

RSA Security

• RSA's security stems from the difficulty of factoring $n$.
• If $n$ can be factored, $p$ and $q$ can be found, enabling the computation of $(p-1)(q-1)$ and then $d$ from $e$.
• Factoring algorithms have exponential time complexity relative to the number of digits in $n$.
• Large $p$ and $q$ values are required to secure RSA; in practice, primes with several hundred digits are used.

Mechanism Design without Money

Social Choice Function

• A social choice function (SCF) $f: \Theta \rightarrow X$ maps each profile of agent preference types $\theta \in \Theta$ to an outcome $x \in X$.
• Type space and possible outcomes are represented by $\Theta = \Theta_1 \times \ldots \times \Theta_n$ and $X$, respectively.

Mechanism

• A mechanism is a mapping $M: A \rightarrow X$ that goes from agent actions $a \in A = A_1 \times \ldots \times A_n$ to outcomes $x \in X$.
• Agents make actions $a_i \in A_i$ using their type $\theta_i \in \Theta_i$

Dominant Strategy Implementation

• A mechanism $M$ implements the SCF $f$ in dominant strategies if there exists a strategy profile $s^* = (s_1^, \ldots, s_n^)$ such that:
• For all agents $i$, types $\theta_i \in \Theta_i$, and actions of others $a_{-i} \in A_{-i}$, $M(s_i^*(\theta_i), a_{-i}) \succeq_i M(a_i, a_{-i}) \quad \forall a_i \in A_i$
  • Truthful reporting is a dominant strategy
• For all $\theta \in \Theta$, $M(s^*(\theta)) = f(\theta)$
  • The outcome of the mechanism with truthful reporting is the desired outcome

Strategy-Proofness

• A mechanism $M$ is strategy-proof if for all agents $i$, all types $\theta_i \in \Theta_i$, and all possible actions of the other agents $a_{-i} \in A_{-i}$:
  • $M(\theta_i, a_{-i}) \succeq_i M(a_i, a_{-i}) \quad \forall a_i \in A_i$

Gibbard-Satterthwaite Theorem

• This characterizes all SCFs adaptable in dominant strategies.
• This applies to any setting with agents and outcomes.
• Agents have complete preferences over outcomes
• Preferences are independent of each other
• The SCF is onto

Dictatorial SCF

• A SCF $f$ is dictatorial if there exists an agent $i$ such that for all $\theta \in \Theta$, $f(\theta) \succeq_i x \quad \forall x \in X$

Gibbard-Satterthwaite Theorem

• Suppose that:
  • There are at least three possible outcomes ($|X| \geq 3$).
  • The SCF $f$ is onto.
  • Agents have complete preferences over outcomes.
• $f$ is implementable in dominant strategies if and only if it is dictatorial.