Summary of Lecture 4

L04 – Plain RSA, Factoring, and Commitment Schemes

2026年3月16日

11821.9K

Security of RSA: Without $sk$, it’s difficult to learn $m$ from $pk, c$

• “Factoring is easy” $\implies$ “Plain RSA is not secure”
• “Plain RSA is secure” $\implies$ “Factoring is hard”
• “Factoring is hard” $\implies$ “Plain RSA is secure”? //not proved, likely true

Commitment Scheme:

• $\mathrm{params}\leftarrow\mathbf{Gen}\left(1^n\right); (\alpha, \beta)\leftarrow\mathbf{Com}(\mathrm{params}, m); \{0,1\}\leftarrow\mathbf{Ver}(\alpha, m, \beta)$
  • hiding:$\alpha\not\to m$
  • binding:$\mathbf{Ver}(\alpha, m, \beta) = \mathbf{Ver}(\alpha, m’, \beta’) = 1$ and $m \ne m’$? Impossible

CONSTRUCTION: based on RSA

• Com:$\alpha = (pk, c) = \left((N, e), c\right); \beta = (p, q, d)$
• Ver:$N = pq; ed \equiv 1 \pmod{(p−1)(q−1)}; \mathrm{RSA}.\mathbf{Dec}(sk, c) = m?$

RSA Implementation:

• choose $p, q$ efficiently? compute $d$ efficiently? compute $c$ / $m$ efficiently?

Addition

Binary Representation of an integer $a$: a 0-1 sequence / binary string $\left(a_{k-1}\dots a_1a_0\right)_2$ such that

• $a = \left(a_{k-1} \dots a_1 a_0\right)_2 \iff a = a_{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0$

Bit Length of Integer $a$: $\ell(a) = \begin{cases} \left\lfloor \log_2\left(\left|a\right|\right) \right\rfloor + 1 & a \neq 0 \\ 1 & a = 0 \end{cases}$

Algorithm for Addition:

• Input:$a = (a_{k-1} \dots a_1 a_0)_2 ,\, b = (b_{k-1} \dots b_1 b_0)_2$ //$0\leq a,b<2^k$
• Output:$c = a + b = (c_k c_{k-1} \dots c_1 c_0)_2$ //$0\leq a+b<2^{k+1}$
  • $carry \leftarrow 0$
  • for $i \leftarrow 0$ to $k-1$ do
    • $t \leftarrow a_i + b_i + carry$ //$t\in\{0,1,2,3\}$
    • set $c_i$and $carry$such that $t = 2 \cdot carry + c_i$ //$carry\in\{0,1\}$
  • $c_k \leftarrow carry$
• Complexity:$O(k)$ bit operations

Big O notation: $O\left(g(n)\right)=\left\{f(n):\,\exists c,n_0>0\text{ such that }0\leq f(n)\leq c\cdot g(n)\text{ for all }n\geq n_0\right\}$

Subtraction

Algorithm for Subtraction:

• Input:$a = \left(a_{k-1} \ldots a_1 a_right\right)_2 ,\, b = \left(b_{k-1} \ldots b_1 b_0\right)_2 ,\, a \geq b$ //$0\leq b\leq a<2^k$
• Output:$c = a – b = \left(c_{k-1} \ldots c_1 c_0\right)_2$ //$0\leq a-b<2^k$
  • $carry \leftarrow 0$
  • for $i \leftarrow 0$ to $k-1$ do
    • $t \leftarrow a_i – b_i + carry$ //$t\in\{-2,-1,0,1\}$
    • set $c_i$and $carry$such that$t = 2 \cdot carry + c_i$ //$carry\in\{-1,0\}$
• Complexity:$O(k)$ bit operations

Multiplication

Algorithm for Multiplication:

• Input: $a = \left(a_{k-1} \cdots a_0\right)_2 ,\, b = \left(b_{k-1} \cdots b_0\right)_2$ //$0\leq a,b<2^k$
• Output: $c = ab = \left(c_{2k-1} \cdots c_0\right)_2$ //$0\leq ab<2^{2k}$
  • $c\leftarrow 0;\,x\leftarrow a$
  • for $i\leftarrow 0$ to $k-1$ do
    • if $b_i = 1$, then $c\leftarrow c + x$;
    • $x\leftarrow x + x$;
• Complexity: $O\left(k^2\right)$ bit operations

Division

Algorithm for Division:

• Input: $a = (a_{k-1} \cdots a_0)_2, b = (b_{l-1} \cdots b_0)_2$ //$0<b\leq a,\,a_{k-1} = b_{l-1} = 1$
• Output: $q = (q_{k-l} \cdots q_0)_2$ and $r = (r_{l-1} \cdots r_0)_2$ //$a = bq + r,0<q<2^{k-l+1} ,0 \le r < b$
  • $(r_k r_{k-1} \cdots r_0)_2 \leftarrow (0 a_{k-1} \cdots a_0)_2$
  • for $i \leftarrow k – l$ down to $0$ do
    • $q_i \leftarrow 2r_{i+l} + r_{i+l-1};$ //$q_i\in\{0,1,2,3\}$
    • If $q_i \ge 2$, then $q_i \leftarrow 1;$ //$\left(r_{i+l},r_{i+l-1}\right)\in\left\{(1,0),(1,1)\right\}$ and $b<\left(r_{i+l}\cdots r_i\right)_2<2b$
    • $(r_{i+l} \cdots r_i)_2 \leftarrow (r_{i+l} \cdots r_i)_2 – q_i \cdot b;$
    • while $(r_{i+l} \cdots r_i)_2 < 0$ do
      • $(r_{i+l} \cdots r_i)_2 \leftarrow (r_{i+l} \cdots r_i)_2 + b;$
      • $q_i \leftarrow q_i – 1;$
  • output $q = (q_{k-l} \cdots q_0)_2$ and $r = (r_{l-1} \cdots r_0);$
• Complexity: $O((k – l + 1) \cdot l)$ bit operations

Example: $(10001)_2=(111)_2(010)_2+(11)_2$

Arithmetic Modulo $N$

THEOREM: Let $a, b \in \{0, 1, …, N – 1\}$. Then

• $(a \pm b) \bmod N$ can be computed in $O(\ell(N))$ bit operations
  • $\ell(a), \ell(b) \leq \ell(N)$
    • $a \pm b$ are computable in $O(\ell(N))$ bit operations
  • $0 \leq |a + b|, |a – b| < 2N$
    • $(a \pm b) \mod N$: computable in $O((\ell(2N) – \ell(N) + 1)\ell(N)) = O(\ell(N))$ bit operations
• $(ab) \bmod N$ can be computed in $O(\ell(N)^2)$ bit operations
  • $\ell(a), \ell(b) \leq \ell(N)$
    • $ab$ is computable in $O(\ell(N)^2)$ bit operations
  • $0 \leq |ab| < N^2$
    • $(ab) \bmod N$: computable in $O((\ell(N^2) – \ell(N) + 1)\ell(N)) = O(\ell(N)^2)$ bit operations.

Modulo exponentiation: For $0 \le a < N, e \in \mathbb{N}, a^e \bmod N = ?$

• Complexity? How to compute efficiently?

EXAMPLE: modulo exponentiation

• $m=$143733911392049898163790620742447116344546040644898141520376037626365007809899615665793895112104794373551079787727363529151277801402630305742433442340983358787394193855033926469913603762712163723160462115649025
• $e=$46310011625494823943446873944318243690297367227688331207962573871391818800156614404181253994785434292576255362553884181998492463297303466464428022018327564723810228367576715525319623371983456905064392494176785
• $N=$245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067
• $\phi(N)=$245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549102628322861627039184220494270313938703906283392288487724394251766892786817697178343799758481228648091667216
• $m^e\bmod{N}=?$

• $xy \bmod N$
  $= ((x \bmod N) \cdot y) \bmod N$
  $= (x \cdot (y \bmod N)) \bmod N$
  $= ((x \bmod N) \cdot (y \bmod N)) \bmod N$
• $a_1 = a = a^1 \bmod N$
• $a_2 = (a_1 \cdot a) \bmod N = a^2 \bmod N$
• $a_3 = (a_2 \cdot a) \bmod N = a^3 \bmod N$
• $\dots$
• $a_e = (a_{e-1} \cdot a) \bmod N = a^e \bmod N$
• Complexity:$O(e)$ multiplications modulo $N$
  • $e = 2^{2048}$?
    –very slow

Square-and-Multiply

ALGORITHM: (200 BC) compute $a^e \bmod N$ in polynomial time

• Input:$a \in \{0, 1, …, N – 1\}$; $e = (e_{k-1} \cdots e_0)_2$// $k = \ell(e)$
  • $e = e_{k-1} \cdot 2^{k-1} + \cdots + e_1 \cdot 2^1 + e_0 \cdot 2^0$
• Output:$a^e \bmod N$
  • Square: this step requires $O(k)$ multiplications modulo $N$
    • $x_0 = a$
    • $x_1 = (x_0^2 \bmod N) = (a^2 \bmod N)$
    • $x_2 = (x_1^2 \bmod N) = (a^{2^2} \bmod N)$
    • $\dots$
    • $x_{k-1} = (x_{k-2}^2 \bmod N) = (a^{2^{k-1}} \bmod N)$
  • Multiply: this step requires $O(k)$ multiplications modulo $N$
    • $(a^e \bmod N) = (x_0^{e_0} \cdot x_1^{e_1} \cdots x_{k-1}^{e_{k-1}} \bmod N)$
• Complexity:$O(k)$ multiplications modulo $N$
  –fast

EXAMPLE: Compute $2^{123} \bmod 35$ using square-and-multiply.

• Input:$a = 2; N = 35; e = 123 = (1\,1\,1\,1\,0\,1\,1)_2; k = 7$
• Square:$k – 1$ multiplications modulo $N$ will be done
  • $x_0 = a = 2;$
  • $x_1 = x_0^2 \bmod N = 4$
  • $x_2 = x_1^2 \bmod N = 16$
  • $x_3 = x_2^2 \bmod N = 11$
  • $x_4 = x_3^2 \bmod N = 16$
  • $x_5 = x_4^2 \bmod N = 11$
  • $x_6 = x_5^2 \bmod N = 16$
• Multiply: at most $k – 1$ multiplications modulo $N$ will be done
  • $a^e = x_0 x_1 x_3 x_4 x_5 x_6 = 2 \times 4 \times 11 \times 16 \times 11 \times 16 \equiv 8 \pmod{35}$
  • $(2^{123} \bmod 35) = 8$

Time-Lock Puzzle

Question: The fastest method of computing $a^{2^t}\bmod{n}$? Square-and-multiply?

MIT LCS35 Time Capsule Crypto Puzzle:

• LCS 35th Celebration (April 12-13, 1999)
• By Ronald L. Rivest, Adi Shamir, and David A. Wagner
• Intrinsically Sequential Computations: Can’t be sped up using parallelism
• Creating the Puzzle:
  • Create $n = pq$ as the product of two primes
  • Choose $t$ as the number of operations required
  • Publish $(n, t)$ as the puzzle description
  • Puzzle: compute $2^{2^t} \bmod n$
  • Method: square-and-multiply (repeated squaring)
    • $a_0 = 2 \bmod n$
    • $a_i = a_{i-1}^2 \bmod n,\,i = 1, 2, \dots, t$
    • Solution is $a_t$

New puzzle: 2019-05-14 Expected to be solved in 2034

Modern applications: blockchain (green consensus)

Encrypting to the future

Question: Encrypt a message $m$ such that it can be decrypted (w/o key) in 35 years?

Encrypting a message $m$ to the future with TLP:

• Create a TLP with the aforementioned scheme. Record the primes $p, q$.
• Compute $a_t$ quickly with the primes
  • $\phi(n) = (p-1)(q-1)$
  • $s = 2^t \bmod \phi(n)$ // $s$ is much smaller that $2^t = 2^{79685186856218}; s < 2^{2048}$
  • Compute $a_t = 2^s \bmod n$ very quickly
• $c = m \oplus a_t$ // Rivest, Shamir, Wagner, 1996

Analysis:

• With $(p, q)$, it is very quick to compute $a_t$ and decrypt $c$ to $m$
• With $(t, n)$, it may take 35 years to compute $a_t$ and then learn $m$
  • Although Bernard Fabrot solved this with 3.5 years of computation