Summary of Lecture 3

L03 – Division of residue classes, Euler’s phi function, Euler’s theorem, Fermat’s little theorem, and RSA

2026年3月11日

608.8K

The set$\mathbb{Z}_n^* = \{[a]_n \in \mathbb{Z}_n \colon \gcd(a, n) = 1\}$

• Euler’s Phi Function:$\phi(n) = |\mathbb{Z}_n^*|$
• $n = p_1^{e_1} \cdots p_r^{e_r} \Rightarrow \phi(n) = n(1 – p_1^{-1}) \cdots (1 – p_r^{-1})$

Euler’s theorem Let $n \ge 1$ and $\alpha \in \mathbb{Z}_n^*$. Then $\alpha^{\phi(n)} = 1$.

• Fermat’s Little Theorem: If $p$ is a prime, then $\alpha^p = \alpha, \forall \alpha \in \mathbb{Z}_p$.

RSA:$\Pi = (\mathbf{Gen, Enc, Dec}) + \mathcal{M}, \,\mathcal{M} = \{m \colon 0 \le m < N, \gcd(m, N) = 1\}$

• $(pk, sk) \leftarrow \mathbf{Gen}(1^n)$
  • $N = pq; \phi(N) = (p – 1)(q – 1)$
  • $0 \le e, d < \phi(N), de \equiv 1 \pmod{\phi(N)}$
  • $pk = (N, e), sk = (N, d)$
• $c \leftarrow \mathbf{Enc}(pk, m):$
  • $c = m^e \bmod N$
• $m \leftarrow \mathbf{Dec}(sk, c):$
  • $m = c^d \bmod N$

Example

EXAMPLE: this is a toy example; all numbers are very small

RSA Security

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

• At least, it should be difficult to learn $d$ from $pk$

Plain RSA and Integer Factoring (given $N$, find $p,q$):

• “Factoring is easy”$\implies$“Plain RSA is not secure”
  • $N \to (p, q) \to \phi(N) \to d$: computable with EEA
• “Plain RSA is secure”$\implies$“Factoring is hard”
• “Factoring is hard” $\nRightarrow$ “Plain RSA is secure” //not proved
• It is likely that “Factoring is hard”$\implies$“Plain RSA is secure”
  • The best known method of computing $d$ is via factoring $N$

How Large is the $N$ in practice?

• $\left|N\right|=2048$ is recommended from present to 2030
• $\left|N\right|=3072$ is recommended after 2030

Example

EXAMPLE: A sample execution of the RSA public-key encryption.

• $p=$179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624225795083
• $q=$179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227077847
• $N=$32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123931212190742861198666048560131098081430518774846347259215332611759149330725252437276424147817808729273755165527379964561074264587032664709511346018327798373715290148129504141795132314929388992688247440232727539575514688633282447719228530664706520939357878528540284184156513405575872085703420500969966917951381310826301
• $\phi(N)=$32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123931212190383322571693585378585237043272713828122751863426871297212289168409787085665422221552391774628940093485139736801331477871715085171882512773342103512436341899373968354945401344376784553485755251993821373671344677095606146354543604901758694718276224054213583162787340809095977593826461068360296205292132857953372
• $e=$15
• $d=$4308934142841467640095316891822660261392547022628731204284046057003287351849052119092960188203055128491829061456253069265882607886732122812678420318193104416084116982306799478900026366718620280906141018451209009103572295819015967488245079245130156062744219446938174005718343452205475441147673653216524161625384443009559144717144698272436361843749700248456916172961638555787971611422056296206985569950525345798018631573510863716228678022917668369778947134991512253249862447326053512583571273798100700265842849822845956946080819513939147320234492629103496540561811088371645441212797012510194809114706160705617714393783
• $m=$10604921754758721445761654694144853008952777608280437615045472365621528740679915569270051503191522500036448557172487959011926112038398359402756573149541644330968641767630622070720630061130259783825355948223371330949158036812742187057045604934546811790948975878200144189048344249873200320299277234465689039409989622319232683984241843711183212001991457793528752812978134072787404790207031482099444968252108690296363773578594703102617386738297675080295774091447240197521221546035459030086538114428516078644733180655540109133778241607260273655335661777894173665137928787960365220712025120785257907244561721692764755210375
• $c=$10526389958138962919595594093411158893099743508465902347128478139908774614311778097354795345791726768384252751637693995592403757856185437083738829836072472243389583367910268799453378039419721345566549516730187308436864460088396611726670050723242080139176080334720294195304048915003805656341816548307249886049027910488249318660062714335703057576576016988513484148308512574950252535463185824865665499749033598201370342142901944632549253564037639312442875039735826909329356840665993783695101447610485922726915969967968584661240430425982194189504400469889762574275824269475495394920107921066723277769226199475558068627049

Commitment Scheme (for SI120)

DEFINITION: A non-interactive commitment scheme$(\mathbf{Gen},\mathbf{Com},\mathbf{Ver})$ consists of three algorithms as follows

• $\mathrm{params}\leftarrow\mathbf{Gen}\left(1^n\right)$: Takes a security parameter $n$ as input, outputs the public parameters $\mathrm{params}$ of the system;
• $(\alpha,\beta)\leftarrow\mathbf{Com}(\mathrm{params},m)$: Takes a message $m$ as input, outputs a commitment $\alpha$ and an opening value $\beta$;
• $\{0,1\}\leftarrow\mathbf{Ver}(\alpha, m, \beta)$: Takes the commitment $\alpha$, the message $m$, and an opening value $\beta$ as input, and outputs 1 (accept) or 0 (reject).

and satisfies the following properties:

• hiding: the commitment $\alpha$ reveals nothing about $m$.
• binding: it is hard for the committer to output a commitment $\alpha$ and later output two pairs $(m,\beta)$ and $\left(m’,\beta’\right)$ such that $\mathbf{Ver}(\alpha,m,\beta)=\mathbf{Ver}\left(\alpha,m’,\beta’\right)=1$ but $m \neq m’$.

CONSTRUCTION: a commitment scheme based on RSA encryption

• $\mathrm{params}\leftarrow\mathbf{Gen}\left(1^n\right)$: Do nothing; the $\mathrm{params}$ is empty.
• $(\alpha,\beta)\leftarrow\mathbf{Com}(\mathrm{params},m)$:
  • Choose $p,q,N,e,d$ as per $\mathrm{RSA}.\mathbf{Gen}\left(1^n\right)$;
  • Compute $c=\mathrm{RSA}.\mathbf{Enc}\left(pk,m\right)$;
  • Output $\alpha=(pk,c)=\left((N,e),c\right)$ and $\beta=(p,q,d)$
• $\{0,1\}\leftarrow\mathbf{Ver}(\alpha, m, \beta)$: Outputs 1 iff the following equalities are all true:
  • $N=pq$;
  • $ed\equiv 1\pmod{(p-1)(q-1)}$;
  • $\mathrm{RSA}.\mathbf{Dec}\left(sk,c\right)=m$

Security Analysis:

• hiding: Given $\alpha = (pk, c)$, it is hard to learn $m$//this is ensured by RSA’s security
• binding: $(m,\beta)=\left(m,(p,q,d)\right),\,\left(m’,\beta’\right)=\left(m’,\left(p’,q’,d’\right)\right)$. Is it possible that $\mathbf{Ver}(\alpha,m,\beta)=\mathbf{Ver}\left(\alpha,m’,\beta’\right)=1$ but $m \neq m’$?
  • $\mathbf{Ver}(\alpha,m,\beta)=1:\,N = pq,\,ed \equiv 1 \pmod{(p-1)(q-1)},\, m = c^{d} \bmod{N}$
  • $\mathbf{Ver}\left(\alpha,m’,\beta’\right)=1:\,N = p’q’,\,ed’ \equiv 1 \pmod{\left(p’-1\right)\left(q’-1\right)}, m’ = c^{d’} \bmod{N}$
  • The above equalities imply that $m = m’$

RSA Implementation

CONSTRUCTION: $\Pi = \left(\mathbf{Gen}, \mathbf{Enc}, \mathbf{Dec}\right) + \mathcal{M}$, the message space is $\mathcal{M} = \left\{m :\, 0 \leq m < N,\,\gcd(m, N) = 1\right\}$

• $(pk, sk) \leftarrow \mathbf{Gen}\left(1^n\right)$
  • choose two $n$-bit primes $p \neq q$
  • $N = pq;\,\phi(N) = (p-1)(q-1)$
  • choose $e, d$ s.t. $0 \leq e, d < \phi(N)$,
    • $\gcd\left(e, \phi(N)\right) = 1$
    • $d = e^{-1} \bmod \phi(N)$
  • output $pk = (N, e),\,sk = (N, d)$
• $c \leftarrow \mathbf{Enc}(pk, m)$:
  • output $c = m^e \bmod N$
    • $0 \leq c < N$
• $m \leftarrow \mathbf{Dec}(sk, c)$:
  • output $m = c^d \bmod N$
    • $0 \leq m < N$

Questions

• Choose $p, q$ efficiently?
  • Prime Number Generation
• Compute $d$ efficiently?
  • Extended Euclidean Algorithm
• Compute $c$/$m$ efficiently?
  • Square-and-Multiply

1977, Rivest, Shamir and Adleman: A method for obtaining digital signatures and public-key cryptosystems. MIT/LCS/TM-82. (Turing Award 2002)

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$
• Output:$c = a + b = (c_k c_{k-1} \dots c_1 c_0)_2$
  • $carry \leftarrow 0$
  • for $i \leftarrow 0$ to $k-1$ do
    • $t \leftarrow a_i + b_i + carry$
    • set $c_i$ and $carry$ such that $t = 2 \cdot carry + c_i$
  • $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\}$