RSA

In 1978, Rivest, Shamir, and Adelman introduced some of the first techniques for public-key cryptography, based on the computational difficulty of factoring large numbers. There is no known efficient algorithm for factoring huge numbers (at least, not on classical computers). Along with the Diffie-Hellman-based techniques that we have already seen, RSA techniques are some of the most commonly used throughout cryptography.

15.1. Arithmetic modulo a composite

Earlier in section 3.4 we discussed the idea of multiplicative inverses. We say that $X$ is a multiplicative inverse of $A$ mod $\nmod$ if $AX \equiv_\nmod 1$. We also saw that when $\nmod$ is prime, all numbers in $\{1,\ldots,\nmod-1\}$ have a multiplicative inverse mod $\nmod$.

When $\nmod$ is not a prime, not all numbers have multiplicative inverses mod $\nmod$. But there is an easy way to characterize the numbers that do:

The proof of this theorem uses a fact from number theory called Bezout's theorem, which we will not prove.

Now the proof of theorem 15.1.1:

15.1.1. Computing inverses

Suppose you want to compute the multiplicative inverse of $A$ mod $\nmod$. You will probably first compute $\gcd(A,\nmod)$ to ensure that the inverse of $A$ indeed exists. GCDs can be computed using Euclid's algorithm (section A.3). By making a small modification to this algorithm, we can also compute the corresponding Bezout coefficients—and hence, the multiplicative inverse—along the way.

To compute the multiplicative inverse of $A$ mod $\nmod$, first run $(d,s,t) := \subname{extgcd}(A,\nmod)$. If $d=1$, then $s$ is the multiplicative inverse of $A$; otherwise, $A$ has no multiplicative inverse.

15.1.2. Algebraic properties

Previously, in definition 13.1.3, we defined multiplicative groups for prime moduli $\nmod$. We now extend the definition to composite moduli as well.

It is convenient to have formulas for $\phi(\nmod)$, for different kinds of $\nmod$. It is easy to see that when $\nmod$ is prime, $\phi(\nmod) = \nmod-1$. RSA-based cryptography uses $\nmod$ which is the product of two distinct primes $\nmod = \pmod\qmod$:

You might wonder about the significance of the totient function $\phi(\nmod)$. Why is it so important to know the number of elements in $\Z^*_\nmod$? The answer is the following useful theorem, usually called Euler's theorem (as if that would narrow things down), which we will not prove here:

15.2. The RSA function and RSA assumption

Another way to think about Euler's theorem is the following:

Euler's theorem motivates the following RSA functions:

15.2.1. Security and $e$th roots

Suppose $\nmod$, $e$, and $d$ have the relationship described above: $\nmod$ is the product of two distinct primes and $e,d$ are multiplicative inverses mod $\phi(\nmod)$. The main idea behind RSA is that if you know $\nmod$ and $e$ (but not $d$), then you can efficiently compute the function $X \mapsto X^e \pct \nmod$, but there is no known efficient method to invert it.

Sometimes we refer to the act of inverting $X \mapsto X^e$ as computing $e$-th roots mod $\nmod$.

Formalizing this intuition starts with specifying how the relevant values $\nmod$, $e$, and $d$ are chosen:

We formalize the idea that “computing $e$-th roots mod $\nmod$ is hard” using the following definition:

15.3. Building a KEM from RSA

The RSA assumption gives us a function that anyone can compute but only someone with the secret information $d$ can invert. Doesn't this sound a lot like PKE? Can we use RSA for encryption, where encryption is $X \mapsto X^e$ and decryption is its inverse $Y \mapsto Y^d$?

Textbook RSA encryption is not secure! The main reason is quite obvious: It's deterministic! An adversary who has a guess of the plaintext value can check whether that guess is true, by re-encrypting it. So, NEVER use textbook RSA for encryption.

However, there is a simple modification to textbook RSA that results in a secure KEM: Simply hash the plaintext under a random oracle. The resulting construction even achieves CCA security!

15.4. ☆ Chinese remainder theorem

In RSA-based cryptography, one user knows the factorization of the modulus. This section introduces a technique that allows for faster modular arithmetic when the factors of the modulus are known.

History. In the Sunzi Suanjing, written some time around the fourth century ce, the Chinese mathematician Sunzi posed an interesting puzzle involving remainders:

Sunzi's puzzle is the first known instance of a system of simultaneous equations involving modular arithmetic: In our notation, he is asking us to solve for $X$ in the following system of congruences:

We can solve such systems of equations using what is called (in the West) the Chinese remainder theorem (CRT). Below is one of the simpler formations of the CRT, involving only two moduli (unlike the example above, which involves three moduli):

15.4.1. Using CRT for modular arithmetic

Another way to think about the Chinese remainder theorem is:

This observation leads to a different approach for doing arithmetic mod $\pmod\qmod$:

15.4.2. Applications to RSA

You may have gotten the impression that the “CRT recipe” for modular arithmetic is convoluted and wasteful. That's true when we're evaluating simple expressions like addition and multiplication, as in our examples. But remember, RSA-based cryptography involves modular exponentiations with huge exponents. The CRT method is significantly faster for these exponentiations.

To understand why the CRT method is faster, it's enough to know that the cost of standard modular exponentiation over a $k$-bit modulus is $O(k^3)$. For simplicity, let's pretend that exponentiation takes exactly $k^3$ steps.

With the CRT method, we perform an exponentiation mod $\pmod$ and another mod $\qmod$. But $\pmod$ and $\qmod$ are each only $k/2$ bits long. So the overall cost is $(k/2)^3 + (k/2)^3 = 2(k^3/8) = k^3/4$. By this rough analysis, it is four times faster than the standard method. In reality, there are other costs slowing down the CRT method, which this analysis doesn't account for, like the cost of solving for the answer mod $\pmod\qmod$. Still, the CRT method is indeed noticeably faster in practice.

Remember, in order to take advantage of the CRT speedup, you must know $\pmod$ and $\qmod$. In RSA-KEM (construction 15.3.2), for example, only the private key holder will know this factorization. Thus, decapsulation can be sped up, but encapsulation cannot.

Exercises

1. Using induction, prove that the extended Euclidean algorithm correctly returns $(d,s,t)$ such that $\gcd(X,Y) = d = sX + dY$. You can use the fact that the standard Euclidean algorithm correctly computes the GCD.

2. Euclid's GCD algorithm involves modular reductions $X \pct Y$. Below is a variant called the binary GCD algorithm that avoids them:

   $\subname{bgcd}(X,Y)$:

   if $Y=0$: return $X$

   if $X$ is even and $Y$ is even: return $2 \cdot \subname{bgcd}(X/2, Y/2)$

   if $X$ is even and $Y$ is odd: return $\subname{bgcd}(X/2,Y)$

   if $X$ is odd and $Y$ is even: return $\subname{bgcd}(X,Y/2)$

   if $X$ is odd and $Y$ is odd: return $\subname{bgcd}(X, Y-X)$

   Augment this algorithm to also compute Bezout coefficients, and use induction to prove its correctness. Your modified algorithm should return $(d,s,t)$ such that $d = \gcd(X,Y) = sX + tY$.

3. Prove that if $g^a \equiv_\nmod 1$ and $g^b \equiv_\nmod 1$ then $g^{\gcd(a,b)} \equiv_\nmod 1$.

4. You have a jug that can hold exactly $A$ liters, and another jug that can hold exactly $B$ liters. $A$ and $B$ are integers, and the jugs are labeled with their capacities. You also have two swimming pools with infinite capacity: One is empty and the other is full. Describe how to put exactly $\gcd(A,B)$ liters of water into the empty pool.

5. Find a formula for $\phi(\pmod^k)$ where $\pmod$ is a prime.

6. As a function of $\nmod$, how many fractions $a/b$ in lowest terms are there, where $0 < a/b < 1$ and $b \le \nmod$? For example, the answer for $\nmod=5$ is 9, corresponding to the following fractions:

   $\frac15, \frac14, \frac13, \frac25, \frac12, \frac35, \frac23, \frac34, \frac45.$

7. h Suppose $\nmod$ is an integer such that $\Z^*_\nmod$ is a cyclic group. Prove that $\Z^*_\nmod$ has exactly $\phi(\phi(\nmod))$ generators.

   Fix one generator $g$, and prove that $g^a$ is also a generator if and only if $a \in \Z^*_{\phi(\nmod)}$.

8. An $e$-th root of $X$ mod $\nmod$ is a value $R$ such that $R^e \equiv_\nmod X$. Suppose you know an $a$-th root of $X$ and a $b$-th root of $X$, where $\gcd(a,b)=1$.

   1. Explain how you can compute an $ab$-th root of $X$.

   2. Find the 427th root of $X$ mod $\nmod$:

   $\begin{aligned} \nmod &= \longnum{3529989702930195629837009938006115078412418112416496826209336627007785798371354161537610954925266878624256967940099671370545330372624851667963106134013952353285024059460266308121063631688798419320109443074482643642387689894031811306984721157101102112383731318101907304584195929712979594815857713411733} \\ X &= \longnum{889018519543927479097362565779068834659989771720267013867018149333933495527677049331353560717868474063961815531930719441237789675885741315096660865749437389525137759715499975708673295314569980020922381778690146463616246585437793158189100154453974921912379499701923652309545085782884916005436240837783} \\ \text{7th root of } X &= \longnum{2169174066236503845875432071010839356613596767060116769730772089449051156095014115213553238718903180171973793093601005007491328019047263693997712100328105113084319857423206418326645537386805722975143273782767557303303437851736507613764825100987568094399011261059081525194625549119202765764649756707587} \\ \text{61st root of } X &= \longnum{2828794670179084993266033755315338950066620307508352572766758892602982204835141232834843070815203542188387418055437464055168991761620966394079143233909356293523508717678281283608998199908043284537107503687626649723751604756530884329600883958305046615870295996132009177082547360022487017331837376643048}\end{aligned}$

9. True or false (prove or disprove): If $X^2 \equiv_\nmod 1$ then $X \in \Z_\nmod^*$.

10. Let $\nmod$ be an RSA modulus.

    1. Suppose you are given integers $X, Y$ such that $X^2 \equiv_\nmod Y^2$ but $X \not\equiv_\nmod \pm Y$. Show how to easily factor $\nmod$.

    2. Factor $\nmod$ below:

       $\begin{aligned} \nmod &= \longnum{5654762149685703354214693790848031657029658489174195095045308201171689244196382582693706951357995049006563040502366709138881656445631366795989012256182108569696793495347122425942615655071824204668643956490221216375437564525811249968746811896772606187045241925267058898354751028926702272628497786711523} \\ X &= \longnum{3580978208095998360659158965217310337620161478555975541101429421391816908728748749836340003033464866459980530061292884027697340913699570449072079862023912325165250698494363120775497939325143231400443629383563412067001065144016339332838870762061630265368146471427565774014995981435733156376738708930} \\ Y &= \longnum{28559790939461549743990406025231168349469120861042991216761797196853816843035360892647550121750966921890117551993466387033365039377265816392316616052346915640086645278964479178653154301009174051109632449970687601282569979655593959247505832952745931531151902384563552297126774532544521663924927782216}\end{aligned}$

11. h Compute the following:

    • What is the last digit of $7^{12345}$?

    • What is $2^{2^{7654321}} \pct 23$?

    • What is $2^{2^{2^{7654321}}} \pct 47$?

    The last digit of $X$ is $X \pct 10$.

12. Provide the missing RSA parameters:

    $\begin{aligned} \pmod &= \longnum{2508155518612074411603483456053649492488128985989731823725285662913699958052730556491454817701843193235338530836280820397638580621580235357783239815254789} \\ \qmod &= \longnum{???} \\ \nmod &= \longnum{19780696365941038115808653814673581857568952327247226929990191572804292421135237238851869823521485898243284297974668758633421942655172386349407895354658437244009007312769136626560794840725353484955232772081654611792212477376066620814539486454983549904691798818130805033095638478772213822148316899475916866257} \\ e &= \longnum{65537} \\ d &= \longnum{???} \\ X &= \longnum{???} \\ X^e &= \longnum{18408592046547703375756701318112875027982329348260670087800300490698116060116543310952149339594433836470057966708020426387564225898802947405602885979947192219631365547861906826876402264886245542542447315050523282544713007050303049540775190384755815453703370619461544416372853881371966527791821549427879560631}\end{aligned}$

13. Why must the RSA exponents $e$ and $d$ always be odd?

14. Why must $\pmod$ and $\qmod$ be distinct primes in RSA key generation? Why is it a bad idea to let $\pmod=\qmod$?

15. h Let $\nmod$ be an RSA modulus (product of distinct primes).

    1. Show that if you know $\nmod$ and $\phi(\nmod)$, then you can easily factor $\nmod$.

    2. Factor the following number $\nmod$:

       $\begin{aligned} \nmod &= \longnum{7927903415944936893588926763257010951562575183247774861367794801073233465922131018985321427787108175649840345485926879427445468578502246636114687852132041280655902666516260662516557830442228724702236120120527414726759176225329927782428088467364112170494813909836389383578652518325688048789844550683089}\\ \phi(\nmod) &= \longnum{7927903415944936893588926763257010951562575183247774861367794801073233465922131018985321427787108175649840345485926879427445468578502246636114687852126398436485259034841337888771241319431218512411726521588987966248136988004824546343685449003768609489343983835425185252299788706733893727226165143878500}\end{aligned}$

    There are two unknowns, $\pmod$ and $\qmod$; each of $\nmod$ and $\phi(\nmod)$ give you one equation on those unknowns.

16. h It's unwise to choose RSA primes $\pmod$ and $\qmod$ too close.

    1. Let $\nmod = \pmod\qmod$ be an RSA modulus. Show that if you know $\delta = |\pmod-\qmod|$ then you can easily factor $\nmod$.

    2. Factor the following number $\nmod$, whose factors are too close together.

       $\begin{aligned} \nmod = \longnum{222411814771269308827925512286318744055323682722912332852543706394589455527980618133528085951421013581679876758661948320578072381194530067735588426797943666875381066783263890133417095098180501268061546468664335659433927300108695187488992795843450761559627026755300386022159004496474996644842429948807}\end{aligned}$

    There are two unknowns, $\pmod$ and $\qmod$; each of $\nmod$ and $\delta$ give you one equation on those unknowns.

17. Continuing the theme of the previous problem, let $\nmod=\pmod\qmod$ be an RSA modulus.

    1. Define the value $t = (\pmod+\qmod)/2$. Note that when $\pmod$ and $\qmod$ are close, $T$ is not much larger than $\sqrt{\nmod}$. Show that $t^2 - \nmod$ is a perfect square, and show how to efficiently factor $\nmod$ if you are given $t$.

    2. Factor the following number $\nmod$, whose factors are too close together. You may find Sage's is_square function useful.

       $\begin{aligned} \nmod = \longnum{7813061858079685590220707750205644391045060422286896240625920430554886629534646829765557148132519988891972365860880312260351263459139332908185459745419812323708477546241889242960051897350686420104041122458840446021423628488635011059054138158312275066147565788230943202082756277867898949394745428918743}\end{aligned}$

    3. How long did it take you to factor $\nmod$ using this method? How long would it have taken using the method from exercise 15.16?

18. Formalize the attack against textbook RSA encryption, showing that it is not a CPA-secure PKE.

19. h Bob and Charlie are such good friends that their RSA public keys have the same $\nmod$ value, although they have different $e$-values. Bob's public key is $(\nmod,e_1)$ and Charlie's is $(\nmod,e_2)$. Furthermore, $\gcd(e_1,e_2) = 1$.

    Alice encrypts the same plaintext $\ptxt$ for both Bob and Charlie using textbook RSA encryption, resulting in $\ctxt_1 = \ptxt^{e_1} \pct \nmod$ and $\ctxt_2 = \ptxt^{e_2} \pct \nmod$. Explain how to efficiently recover $\ptxt$, given $\ctxt_1, \ctxt_2$, and the two public keys.

    Think about Bezout's theorem with respect to $e_1$ and $e_2$.

20. Consider the following PKE scheme:

    $\Enc\bigl( (\nmod,e), \ptxt \bigr)$:

    $r \gets \Z_\nmod$

    $\ctxt_1 := \ptxt^{r+e} \pct \nmod$

    $\ctxt_2 := \ptxt^{re} \pct \nmod$

    return $(\ctxt_1, \ctxt_2)$

    $\KeyGen = \RSA.\KeyGen$

    $\Dec\bigl( (\nmod,d), (\ctxt_1, \ctxt_2) \bigr)$:

    $\ptxt := (\ctxt_1)^d \cdot (\ctxt_2)^{-d^2} \pct \nmod$

    return $\ptxt$

    1. Show that the scheme satisfies correctness (decryption is the inverse of encryption).

    2. Show that the scheme is not CPA-secure.

21. Below is an attempt to build a PKE from RSA, using CBC mode:

    $\Enc\bigl( (\nmod,e), \ptxt_1 \| \cdots \| \ptxt_\ell \bigr)$:

    // each $\ptxt_i$ is $\secpar$ bits.

    $\ctxt_0 \gets \Z_\nmod$

    for $i = 1$ to $\ell$:

    $\ctxt_i = (\ctxt_{i-1} + \ptxt_i)^e \pct \nmod$

    return $\ctxt_0 \| \cdots \| \ctxt_\ell$

    $\KeyGen = \RSA.\KeyGen$

    $\Dec\bigl( (\nmod,d), \ctxt_0 \| \cdots \| \ctxt_\ell \bigr)$:

    for $i = 1$ to $\ell$:

    $\ptxt_i = (\ctxt_i)^d - \ctxt_{i-1} \pct \nmod$

    return $\ptxt_1 \| \cdots \| \ptxt_\ell$

    Show that the scheme is not a CPA-secure PKE.

22. h Consider the following symmetric-key encryption scheme. The key $\key$ is a large integer. To encrypt a plaintext $\ptxt$, first “pad” it into a prime number as follows: Append $\secpar$ uniformly chosen bits to $\ptxt$ until the result is the binary representation of a prime number. After the plaintext has been converted to a prime number in this way, encrypt by multiplying with the private key. The idea is that recovering the private key should be as hard as factoring.

    Despite this intuition, show that the scheme is not CPA-secure.

    $\begin{aligned} \K &= \{ n\text{-bit primes} \} \\ \M &= \bits^n \\ \C &= \bits^{2n+\secpar} \end{aligned}$

    $\Enc(\key,\ptxt)$:

    do:

    $R \gets \bits^\secpar$

    $X := \ptxt \| R$

    until $X$ is binary encoding of a prime number

    return $\key \cdot X$ // integer multiplication

    $\Dec(\key,\ctxt)$:

    $X := \ctxt / \key$

    return first $n$ bits of $X$

    Request any two ciphertexts.

23. Generalize the Chinese Remainder Theorem to more than two moduli. Suppose $\nmod_1, \ldots, \nmod_k$ are relatively prime, so for all $i \ne j$ we have $\gcd(\nmod_i,\nmod_j) = 1$. For any collection of integers $U_i \in \Z_{\nmod_i}$, describe how to compute an integer $X$ such that $X \equiv_{\nmod_i} U_i$ for all $i$.

24. h Consider a rectangular grid of points, with width $w$ and height $h$. Starting in the lower-left of the grid, start walking diagonally northeast. When you fall off end the grid, wrap around to the opposite side (i.e., Pac-Man topology). Below is an example of the first few steps you take on a grid with $w=3$ and $h=5$:

    

    Show that if $\gcd(w,h) = 1$, then you will eventually visit every point in the grid.

    What is the formula for your position after $n$ steps?

25. h Let $\nmod$ be an RSA modulus and $e,d$ be appropriate RSA exponents. The proof of claim 15.2.3 showed that $X^{ed} \equiv_\nmod 1$ for all $X \in \Z_\nmod^*$. Complete the proof by showing that the same is true for all $X \in \Z_\nmod$, not just those in $\Z_\nmod^*$.

    Use CRT.

26. h Let $\nmod=\pmod\qmod$ be an RSA modulus. Usually we choose the exponents $e$ and $d$ to satisfy $ed \equiv_{\phi(\nmod)} 1$.

    Define the value $L = \text{lcm}(\pmod-1,\qmod-1)$, and show that RSA still works—that is, exponentiation by $e$ and exponentiation by $d$ are inverses mod $\nmod$—if the exponents are chosen to satisfy $ed \hl{\equiv_L} 1$.

    Use CRT.

27. Suppose $X \in \Z_{rs}$ is the solution to

    $\begin{aligned} X &\equiv_r U, \\ X &\equiv_s V.\end{aligned}$

    Prove that $X \in \Z_{rs}^*$ if and only if $U \in \Z_r^*$ and $V \in \Z_s^*$. As a result of this fact, it must be the case that $\phi(rs) = \phi(r) \phi(s)$, whenever $\gcd(r,s)=1$.

28. h Let $\nmod$ be an RSA modulus and $e$ be a suitable RSA exponent. In this exercise we consider values $X \in \Z_\nmod$ that satisfy $X^2 \equiv_\nmod 1$.

    1. $X = 1$ and $X = -1$ (by which we mean $X=\nmod-1$) satisfy the equation. But there are two other nontrivial solutions; show how to compute them if you know the factorization of $\nmod$.

    2. Explain how you can easily factor $\nmod$ if you are given either of the two nontrivial solutions.

    Use CRT.

29. Suppose $\G$ is a cyclic group of composite order $\nmod = \pmod\qmod$, with generator $g$. Every element of $\G$ can be written as a power of $g$, and arithmetic in the exponent happens mod $\nmod$.

    1. Prove that for any $X \in \G$, there exist integers $a$ and $b$ such that $X = g^{a\pmod + b\qmod}$.

    2. Prove that there is an exponent $c$ such that, for all $a$ and $b$, we have $(g^{a\pmod + b\qmod})^c = g^{a\pmod}$. In other words, for all $X \in \G$, we know that $X^c$ is always in the order-$\qmod$ subgroup (generated by $g^\pmod$), and if $X$ was already in the order-$\qmod$ subgroup (the case of $b=0$ above), then $X^c = X$.