The ciphertext 5859 was obtained from the RSA algorithm using $n=11413$ and $e=7467$. Using the factorization $11413=101\cdot 113$, find the plaintext.

Bob sets up a budget RSA cryptosystem. He chooses $p=23$ and $q=19$ and computes $n=437=pq$. He chooses the encryption exponent to be $e=397$. Alice sends Bob the ciphertext $c=123$. What is the plaintext? (You know $p$, $q$, and $e$).

Suppose your RSA modulus is $n=55=5\times 11$ and your encryption exponent is $e=3$.

1. Find the decryption exponent $d$.

2. Assume that $gcd(m\text{,}55)=1$. Show that if $c\equiv m^3(\text{mod}55)$ is the ciphertext, then the plaintext is $m\equiv c^d(\text{mod}55)$. Do not quote the fact that RSA decryption works. That is what you are showing in this specific case.

Bob’s RSA modulus is $979=11\times 89$ and his encryption exponent is $e=587$. Alice sends him the ciphertext $c=10$. What is the plaintext?

The ciphertext $62$ was obtained using RSA with $n=667$ and $e=3$. You know that the plaintext is either 9 or 10. Determine which it is without factoring $n$.

Alice and Bob are trying to use RSA, but Bob knows only one large prime, namely $p=1093$. He sends $n=p=1093$ and $e=361$ to Alice. She encrypts her message $m$ as $c\equiv m^e(\text{mod}n)$. Eve intercepts $c$ and decrypts using the congruence $m\equiv c^d(\text{mod}n)$. What value of $d$ should Eve use? Your answer should be an actual number. You may assume that Eve knows $n$ and $e$, and she knows that $n$ is prime.

Suppose you encrypt messages $m$ by computing $c\equiv m^3(\text{mod}101)$. How do you decrypt? (That is, you want a decryption exponent $d$ such that $c^d\equiv m(\text{mod}101)$; note that 101 is prime.)

Bob knows that if an RSA modulus can be factored, then the system has bad security. Therefore, he chooses a modulus that cannot be factored, namely the prime $n=131303$. He chooses his encryption exponent to be $e=13$, and he encrypts a message $m$ as $c\equiv m^{13}(\text{mod}n)$. The decryption method is to compute $m\equiv c^d(\text{mod}n)$ for some $d$. Find $d$. (Hint: Fermat’s theorem)

Let $p$ be a large prime. Suppose you encrypt a message $x$ by computing $y\equiv x^e(\text{mod}p)$ for some (suitably chosen) encryption exponent $e$. How do you find a decryption exponent $d$ such that $y^d\equiv x(\text{mod}p)$?

Bob decides to test his new RSA cryptosystem. He has RSA modulus $n=pq$ and encryption exponent $e$. His message is $m$. He sends $c\equiv m^e(\text{mod}n)$ to himself. Then, just for fun, he also sends $c^{\prime }\equiv (m+q{)}^e(\text{mod}n)$ to himself. Eve knows $n$ and $e$, and intercepts both $c$ and $c^{\prime }$. She guesses what Bob has done. How can she find the factorization of $n$? (Hint: Show that $c\equiv c^{\prime }(\text{mod}q)$ but not mod $p$. What is $gcd(c-c^{\prime }\text{,}n)$?)

Let $n$ be the product of two large primes. Alice wants to send a message $m$ to Bob, where $gcd(m\text{,}n)=1$. Alice and Bob choose integers $a$ and $b$ relatively prime to $\varphi (n)$. Alice computes $c\equiv m^a(\text{mod}n)$ and sends $c$ to Bob. Bob computes $d\equiv c^b(\text{mod}n)$ and sends $d$ back to Alice. Since Alice knows $a$, she finds $a_1$ such that $a{a}_1\equiv 1(\text{mod}\varphi (n))$. Then she computes $e\equiv d^{a_1}(\text{mod}n)$ and sends $e$ to Bob. Explain what Bob must now do to obtain $m$, and show that this works. (Remark: In this protocol, the prime factors of $n$ do not need to be kept secret. Instead, the security depends on keeping $a\text{,}b$ secret. The present protocol is a less efficient version of the three-pass protocol from Section 3.5.)

A bank in Alice Springs (Australia), also known as Alice, wants to send a lot of financial data to the Bank of Baltimore, also known as Bob. They want to use AES, but they do not share a common key. All of their communications will be on public airwaves. Describe how Alice and Bob can accomplish this using RSA.

Naive Nelson uses RSA to receive a single ciphertext $c$, corresponding to the message $m$. His public modulus is $n$ and his public encryption exponent is $e$. Since he feels guilty that his system was used only once, he agrees to decrypt any ciphertext that someone sends him, as long as it is not $c$, and return the answer to that person. Evil Eve sends him the ciphertext $2^{e}c(\text{mod}n)$. Show how this allows Eve to find $m$.

Eve loves to do double encryption. She starts with a message $m$. First, she encrypts it twice with a one-time pad (the same one each time). Then she encrypts the result twice using a Vigenère cipher with key $NANANA$. Finally, she encrypts twice with RSA using modulus $n=pq=7919\times 17389$ and exponent $e=66909025$. It happens that $e^2\equiv 1(\text{mod}(p-1)(q-1))$. Show that the final result of all this encryption is the original plaintext. Explain your answer fully. Simply saying something like “decryption is the same as encryption” is not enough. You must explain why.

In order to increase security, Bob chooses $n$ and two encryption exponents $e_1$, $e_2$. He asks Alice to encrypt her message $m$ to him by first computing $c_1\equiv m^{e_1}(\text{mod}n)$, then encrypting $c_1$ to get $c_2\equiv c_1^{e_2}(\text{mod}n)$. Alice then sends $c_2$ to Bob. Does this double encryption increase security over single encryption? Why or why not?

1. Eve thinks that she has a great strategy for breaking RSA that uses a modulus $n$ that is the product of two 300-digit primes. She decides to make a list of all 300-digit primes and then divide each of them into $n$ until she factors $n$. Why won’t this strategy work?

2. Eve has another strategy. She will make a list of all $m$ with $0\le m<{10}^{600}$, encrypt each $m$, and store them in a database. Suppose Eve has a superfast computer that can encrypt ${10}^{50}$ plaintexts per second (this is, of course, well beyond the speed of any existing technology). How many years will it take Eve to compute all ${10}^{600}$ encryptions? (There are approximately $3\times {10}^7$ seconds in a year.)

The exponents $e=1$ and $e=2$ should not be used in RSA. Why?

Alice is trying to factor $n=57677$. She notices that ${1234}^4\equiv 1(\text{mod}n)$ and that ${1234}^2\equiv 23154(\text{mod}n)$. How does she use this information to factor $n$? Describe the steps but do not actually factor $n$.

Let $p$ and $q$ be distinct odd primes, and let $n=pq$. Suppose that the integer $x$ satisfies $gcd(x\text{,}pq)=1$.

1. Show that $x^{{\displaystyle \frac{1}{2}}\varphi (n)}\equiv 1(\text{mod}p)$ and $x^{{\displaystyle \frac{1}{2}}\varphi (n)}\equiv 1(\text{mod}q)$.

2. Use (a) to show that $x^{{\displaystyle \frac{1}{2}}\varphi (n)}\equiv 1(\text{mod}n)$.

3. Use (b) to show that if $ed\equiv 1(\text{mod}{\displaystyle \frac{1}{2}}\varphi (n))$ then $x^{ed}\equiv x(\text{mod}n)$. (This shows that we could work with ${\displaystyle \frac{1}{2}}\varphi (n)$ instead of $\varphi (n)$ in RSA. In fact, we could also use the least common multiple of $p-1$ and $q-1$ in place of $\varphi (n)$, by similar reasoning.)

Alice uses RSA with $n=27046456501$ and $e=3$. Her ciphertext is $c=1860867$. Eve notices that $c^{14}\equiv 1(\text{mod}n)$.

1. Show that $m^{14}\equiv 1(\text{mod}n)$, where $m$ is the plaintext.

2. Explicitly find an exponent $f$ such that $c^f\equiv m(\text{mod}n)$. (Hint: You do not need to factor $n$ to find $f$. Look at the proof that RSA decryption works. The only property of $\varphi (n)$ that is used is that $m^{\varphi (n)}\equiv 1$.)

Suppose that there are two users on a network. Let their RSA moduli be $n_1$ and $n_2$, with $n_1$ not equal to $n_2$. If you are told that $n_1$ and $n_2$ are not relatively prime, how would you break their systems?

Huey, Dewey, and Louie ask their uncle Donald, “Is $n=19887974881$ prime or composite?” Donald replies, “Yes.” Therefore, they decide to obtain more information on their own.

1. Huey computes ${13}^{(n-1)}\equiv 16739180549(\text{mod}n)$. What does he conclude?

2. Dewey computes $7^{n-1}\equiv 1(\text{mod}n)$, and he does this by computing

   $$\begin{array}{lll}{7}^{(n-1)/32}\hfill & \equiv \hfill & 1992941816(\text{mod}n)\hfill \\ 7^{(n-1)/16}\hfill & \equiv \hfill & 19887730619\hfill \\ 7^{(n-1)/8}\hfill & \equiv \hfill & 1\hfill \\ 7^{(n-1)/4}\hfill & \equiv \hfill & 7^{(n-1)/2}\equiv 7^{(n-1)}\equiv 1.\hfill \end{array}$$

   What information can Dewey obtain from his calculation that Huey does not obtain?

3. Louie notices that ${19857930655}^2\equiv {123}^2(\text{mod}n)$. What information can Louie compute? (In parts (b) and (c), you do not need to do the calculations, but you should indicate what calculations need to be done.)

You are trying to factor $n=642401$. Suppose you discover that

and that

Use this information to factor $n$.

Suppose you know that ${7961}^2\equiv 7^2(\text{mod}8051)$. Use this information to factor $8051$.

Suppose you discover that

How would you use this information to factor 2288233? Explain what steps you would do, but do not perform the numerical calculations.

Suppose you want to factor an integer $n$. You have found some integers $x_1\text{,}{x}_2\text{,}{x}_3\text{,}{x}_4$ such that

Describe how you might be able to use this information to factor $n$? Why might the method fail?

Suppose you have two distinct large primes $p$ and $q$. Explain how you can find an integer $x$ such that

(Hint: Use the Chinese Remainder Theorem to find four solutions to $x^2\equiv 49(\text{mod}pq)$.)

You are told that

Use this information to factor $1891$.

Suppose $n$ is a large odd number. You calculate $2^{(n-1)/2}\equiv k(\text{mod}n)$, where $k$ is some integer with $k\cancel{\equiv }\pm 1(\text{mod}n)$.

1. Suppose $k^2\cancel{\equiv }1(\text{mod}n)$. Explain why this implies that $n$ is not prime.

2. Suppose $k^2\equiv 1(\text{mod}n)$. Explain how you can use this information to factor $n$.

1. Bob is trying to set up an RSA cryptosystem. He chooses $n=pq$ and $e$, as usual. By encrypting messages six times, Eve guesses that $e^6\equiv 1(\text{mod}(p-1)(q-1))$. If this is the case, what is the decryption exponent $d$? (That is, give a formula for $d$ in terms of the parameters $n$ and $e$ that allows Eve to compute $d$.)

2. Bob tries again, with a new $n$ and $e$. Alice computes $c\equiv m^e(\text{mod}n)$. Eve sees no way to guess the decryption exponent $d$ this time. Knowing that if she finds $d$ she will have to do modular exponentiation, Eve starts computing successive squares: $c\text{,}{c}^2\text{,}{c}^4\text{,}{c}^8\text{,}\cdots (\text{mod}n)$. She notices that $c^{32}\equiv 1(\text{mod}n)$ and realizes that this means that $m^{32}\equiv 1(\text{mod}n)$. If $e=53$, what is a value for $d$ that will decrypt the ciphertext? Prove that this value works.

Suppose two users Alice and Bob have the same RSA modulus $n$ and suppose that their encryption exponents $e_A$ and $e_B$ are relatively prime. Charles wants to send the message $m$ to Alice and Bob, so he encrypts to get $c_A\equiv m^{e_A}$ and $c_B\equiv m^{e_B}(\text{mod}n)$. Show how Eve can find $m$ if she intercepts $c_A$ and $c_B$.

Bob finally sets up a very secure RSA system. In fact, it is so secure that he decides to tell Alice one of the prime factors of $n$; call it $p$. Being no dummy, he does not take the message as $p$, but instead uses a shift cipher to hide the prime in the plaintext $m=p+1$, and then does an RSA encryption to obtain $c\equiv m^e(\text{mod}n)$. He then sends $c$ to Alice. Eve intercepts $c$, $n$ and $e$, and she knows that Bob has encrypted $p$ this way. Explain how she obtains $p$ and $q$ quickly. (Hint: How does $c$ differ from the result of encrypting the simple plaintext “1” ?)

Suppose Alice uses the RSA method as follows. She starts with a message consisting of several letters, and assigns $a=1\text{,}b=2\text{,}\dots \text{,}z=26$. She then encrypts each letter separately. For example, if her message is $cat$, she calculates $3^e(\text{mod}n)$, $1^e(\text{mod}n)$, and ${20}^e(\text{mod}n)$. Then she sends the encrypted message to Bob. Explain how Eve can find the message without factoring $n$. In particular, suppose $n=8881$ and $e=13$. Eve intercepts the message

Find the message without factoring 8881.

Let $n=3837523$. Bob Square Messages sends and receives only messages $m$ such that $m$ is a square mod $n$ and $gcd(m\text{,}n)=1$. It can be shown that $m^{958230}\equiv 1(\text{mod}n)$ for such messages (even though $\varphi (n)\ne 958230$). Bob chooses $d$ and $e$ satisfying $de\equiv 1(\text{mod}958230)$. Show that if Alice sends Bob a ciphertext $c\equiv m^e(\text{mod}n)$ (where $m$ is a square mod $n$, and $gcd(m\text{,}n)=1$), then Bob can decrypt by computing $c^d(\text{mod}n)$. Explain your reasoning.

Show that if $x^2\equiv y^2(\text{mod}n)$ and $x\cancel{\equiv }\pm y(\text{mod}n)$, then $gcd(x+y\text{,}n)$ is a nontrivial factor of $n$.

Bob’s RSA system uses $n=2776099$ and $e=421$. Alice encrypts the message $2718$ and sends the ciphertext to Bob. Unfortunately (for Alice), ${2718}^{10}\equiv 1(\text{mod}n)$. Show that Alice’s ciphertext is the same as the plaintext. (Do not factor $n$. Do not compute $m^{421}(\text{mod}n)$ without using the extra information that ${2718}^{10}\equiv 1$. Do not claim that $\varphi (2776099=10$; it doesn’t.)

Let $n=pq$ be the product of two distinct primes.

1. Let $m$ be a multiple of $\varphi (n)$. Show that if $gcd(a\text{,}n)=1$, then $a^m\equiv 1(\text{mod}p)$ and $(\text{mod}q)$.

2. Suppose $m$ is as in part (a), and let $a$ be arbitrary (possibly $gcd(a\text{,}n)\ne 1$). Show that $a^{m+1}\equiv a(\text{mod}p)$ and $(\text{mod}q)$.

3. Let $e$ and $d$ be encryption and decryption exponents for RSA with modulus $n$. Show that $a^{ed}\equiv a(\text{mod}n)$ for all $a$. This shows that we do not need to assume $gcd(a\text{,}n)=1$ in order to use RSA.

4. If $p$ and $q$ are large, why is it likely that $gcd(a\text{,}n)=1$ for a randomly chosen $a$?

Alice and Bob are celebrating Pi Day. Alice calculates ${23039}^2\equiv 314(\text{mod}79927)$ and Bob calculates ${35118}^2\equiv 314(\text{mod}79927)$.

1. Use this information to factor $79927$. (You should show how to use the information. Do not do the calculation. The answer is not “Put the number in the computer and then relax for 10 minutes.”)

2. Given that $79927=257\times 311$ and that ${166}^2\equiv 314(\text{mod}257)$ and ${25}^2\equiv 314(\text{mod}311)$, how would you produce the numbers 23039 and 35118 in part (a)? You do not need to do the calculations, but you should state which congruences are being solved and what theorems are being used.

3. Now that Eve knows that $79927=257\times 311$, she wants to find an $x\cancel{\equiv }\pm 17(\text{mod}79927)$ such that $x^2\equiv {17}^2(\text{mod}79927)$. Explain how to accomplish this. Say what the method is. Do not do the calculation.

Suppose $n=pqr$ is the product of three distinct primes. How would an RSA-type scheme work in this case? In particular, what relation would $e$ and $d$ satisfy?

Note: There does not seem to be any advantage in using three primes instead of two. The running times of some factorization methods depend on the size of the smallest prime factor. Therefore, if three primes are used, the size of $n$ must be increased in order to achieve the same level of security as obtained with two primes.

Suppose Bob’s public key is $n=2181606148950875138077$ and he has $e=7$ as his encryption exponent. Alice encrypts the message hi eve = $080900052205=m$. By chance, the message $m$ satisfies $m^3\equiv 1(\text{mod}n)$. If Eve intercepts the ciphertext, how can Eve read the message without factoring $n$?

Let $p=7919$ and $q=17389$. Let $e=66909025$. A calculation shows that $e^2\equiv 1(\text{mod}(p-1)(q-1))$. Alice decides to encrypt the message $m=12345$ using RSA with modulus $n=pq$ and exponent $e$. Since she wants the encryption to be very secure, she encrypts the ciphertext, again using $n$ and $e$ (so she has double encrypted the original plaintext). What is the final ciphertext that she sends? Justify your answer without using a calculator.

You are told that ${7172}^2\equiv {60}^2(\text{mod}14351)$. Use this information to factor $14351$. You must use this information and you must give all steps of the computation (that is, give the steps you use if you are doing it completely without a calculator).

1. Show that if $gcd(e\text{,}24)=1$, then $e^2\equiv 1(\text{mod}24)$.

2. Show that if $n=35$ is used as an RSA modulus, then the encryption exponent $e$ always equals the decryption exponent $d$.

1. The exponent $e=3$ has sometimes been used for RSA because it makes encryption fast. Suppose that Alice is encrypting two messages, $m_0=m$ and $m_1=m+1$ (for example, these could be two messages that contain a counter variable that increments). Eve does not know $m$ but knows that the two plaintexts differ by 1. Let $c_0\equiv m_0^3$ and $c_1\equiv m_1^3$ mod $n$. Show that if Eve knows $c_0$ and $c_1$, she can recover $m$. (Hint: Compute $(c_1+2c_0-1)/(c_1-c_0+2)$.)

2. Suppose that $m_0=m$ and $m_1=m+b$ for some publicly known $b$. Modify the technique of part (a) so that Eve can recover $m$ from the ciphertexts $c_0$ and $c_1$.

Your opponent uses RSA with $n=pq$ and encryption exponent $e$ and encrypts a message $m$. This yields the ciphertext $c\equiv m^e(\text{mod}n)$. A spy tells you that, for this message, $m^{12345}\equiv 1(\text{mod}n)$. Describe how to determine $m$. Note that you do not know $p$, $q$, $\varphi (n)$, or the secret decryption exponent $d$. However, you should find a decryption exponent that works for this particular ciphertext. Moreover, explain carefully why your decryption works (your explanation must include how the spy’s information is used). For simplicity, assume that $gcd(12345\text{,}e)=1$.

1. Show that if $gcd(b\text{,}1729)=1$ then $b^{1728}\equiv 1(\text{mod}1729)$. You may use the fact that $1729=7\cdot 13\cdot 19$.

2. By part (a), you know that $2^{1728}\equiv 1(\text{mod}1729)$. When checking this result, you compute $2^{54}\equiv 1065(\text{mod}1729)$ and $2^{108}\equiv 1(\text{mod}1729)$. Use this information to find a nontrivial factor of 1729.

Suppose you are using RSA (with modulus $n=pq$ and encrypting exponent $e$), but you decide to restrict your messages to numbers $m$ satisfying $m^{1000}\equiv 1(\text{mod}n)$.

1. Show that if $d$ satisfies $de\equiv 1(\text{mod}1000)$, then $d$ works as a decryption exponent for these messages.

2. Assume that both $p$ and $q$ are congruent to 1 mod 1000. Determine how many messages satisfy $m^{1000}\equiv 1(\text{mod}n)$. You may assume and use the fact that $m^{1000}\equiv 1(\text{mod}r)$ has 1000 solutions when $r$ is a prime congruent to 1 mod 1000.

You may assume the fact that $m^{270300}\equiv 1(\text{mod}1113121)$ for all $m$ with $gcd(m\text{,}1113121)=1$. Let $e$ and $d$ satisfy $ed\equiv 1(\text{mod}270300)$, and suppose that $m$ is a message such that $0<m<1113121$ and $gcd(m\text{,}1113121)=1$. Encrypt $m$ as $c\equiv m^e(\text{mod}1113121)$. Show that $m\equiv c^d(\text{mod}1113121)$. Show explicitly how you use the fact that $ed\equiv 1(\text{mod}270300)$ and the fact that $m^{270300}\equiv 1(\text{mod}1113121)$. (Note: $\varphi (1113121)\ne 270300$, so Euler’s theorem does not apply.)

Suppose Bob’s encryption company produces two machines, A and B, both of which are supposed to be implementations of RSA using the same modulus $n=pq$ for some unknown primes $p$ and $q$. Both machines also use the same encryption exponent $e$. Each machine receives a message $m$ and outputs a ciphertext that is supposed to be $m^e(\text{mod}n)$. Machine A always produces the correct output $c$. However, Machine B, because of implementation and hardware errors, always outputs a ciphertext $c^{\prime }(\text{mod}n)$ such that $c^{\prime }\equiv m^e(\text{mod}p)$ and $c^{\prime }\equiv m^e+1(\text{mod}q)$. How could you use machines A and B to find $p$ and $q$? (See Computer Problem 11 for a discussion of how such a situation could arise.) (Hint: $c\equiv c^{\prime }(\text{mod}p)$ but not mod $q$. What is $gcd(c-c^{\prime }\text{,}n)$?)

Alice and Bob play the following game. They choose a large odd integer $n$ and write $n-1=2^{k}m$ with $m$ odd. Alice then chooses a random integer $r\cancel{\equiv }\pm 1(\text{mod}n)$ with $gcd(r\text{,}n)=1$. Bob computes $x_1\equiv r^m(\text{mod}n)$. Then Alice computes $x_2\equiv x_1^2(\text{mod}n)$. Then Bob computes $x_3\equiv x_2^2(\text{mod}n)$, Alice computes $x_4\equiv x_3^2(\text{mod}n)$, etc. They stop if someone gets $\pm 1(\text{mod}n)$, and the person who gets $\pm 1$ wins.

1. Show that if $n$ is prime, the game eventually stops.

2. Suppose $n$ is the product of two distinct primes and Alice knows this factorization. Show how Alice can choose $r$ so that she wins on her first play. That is, $x_1\cancel{\equiv }\pm 1(\text{mod}n)$ but $x_2\equiv \pm 1(\text{mod}n)$.

1. Suppose Alice wants to send a short message $m$ but wants to prevent the short message attack of Section 9.2. She tells Bob that she is adjoining 100 zeros at the end of her plaintext, so she is using $m_1={10}^{100}m$ as the plaintext and sending $c_1\equiv m_1^e$. If Eve knows that Alice is doing this, how can Eve modify the short plaintext attack and possibly find the plaintext?

2. Suppose Alice realizes that the method of part (a) does not provide security, so instead she makes the plaintext longer by repeating it two times: $m||m$ (where $x||y$ means we write the digits of $x$ followed by the digits of $y$ to obtain a longer number). If Eve knows that Alice is doing this, how can Eve modify the short plaintext attack and possibly find the plaintext? Assume that Eve knows the length of $m$. (Hint: Express $m||m$ as a multiple of $m$.)

This exercise provides some of the details of how the quadratic sieve obtains the relations that are used to factor a large odd integer $n$. Let $s$ be the smallest integer greater than the square root of $n$ and let $f(x)=(x+s{)}^2-n$. Let the factor base $B$ consist of the primes up to some bound $B$. We want to find squares that are congruent mod $n$ to a product of primes in $B$. One way to do this is to find values of $f(x)$ that are products of primes in $B$. We’ll search over a range $0\le x\le A$, for some $A$.

1. Suppose $0\le x<(\sqrt{2}-1)\sqrt{n}-1$. Show that $0\le f(x)<n$, so $f(x)(\text{mod}n)$ is simply $f(x)$. (Hint: Show that $x+s<x+\sqrt{n}+1<\sqrt{2n}$.) Henceforth, we’ll assume that $A<(\sqrt{2}-1)\sqrt{n}-1$, so the values of $x$ that we consider have $f(x)<n$.

2. Let $p$ be a prime in $B$. Show that if there exists an integer $x$ with $f(x)$ divisible by $p$, then $n$ is a square mod $p$. This shows that we may discard those primes in $B$ for which $n$ is not a square mod $p$. Henceforth, we will assume that such primes have been discarded.

3. Let $p\in B$ be such that $n$ is a square mod $p$. Show that if $p$ is odd, and $p\cancel{|}n$, then there are exactly two values of $x$ mod $p$ such that $f(x)\equiv 0(\text{mod}p)$. Call these values $x_{p\text{,}1}$ and $x_{p\text{,}2}$. (Note: In the unlikely case that $p|n$, we have found a factor, which was the goal.)

4. For each $x$ with $0\le x\le A$, initialize a register with value $\log f(x)\text{.}$ For each prime $p\in B$, subtract $logp$ from the registers of those $x$ with $x\equiv x_{p\text{,}1}\text{ or }{x}_{p\text{,}2}(\text{mod}p)$. (Remark: This is the “sieving” part of the quadratic sieve.) Show that if $f(x)$ (with $0\le x\le A$) is a product of distinct primes in $B$, then the register for $x$ becomes 0 at the end of this process.

5. Explain why it is likely that if $f(x)$ (with $0\le x\le A$) is a product of (possibly nondistinct) primes in $B$, then the final result for the register for $x$ is small (compared to the register for an $x$ such that $f(x)$ has a prime factor not in $B$).

6. Why is the procedure of part (d) faster than trial division of each $f(x)$ by each element of $B$, and why does the algorithm subtract $logp$ rather than dividing $f(x)$ by $p$?

In practice, the sieve also takes into account solutions to $f(x)\equiv 0$ mod some powers of small primes in $B$. After the sieving process is complete, the registers with small entries are checked to see which correspond to $f(x)$ being a product of primes from $B$. These give the relations “square $\equiv$ product of primes in $B$ mod $n$” that are used to factor $n$.

Bob chooses $n=pq$ to be the product of two large primes $p\text{,}q$ such that $gcd(pq\text{,}(p-1)(q-1))=1$.

1. Show that $\varphi (n^2)=n\varphi (n)$ (this is true for any positive $n$).

2. Let $k\ge 0$. Show that $(1+n{)}^k\equiv 1+kn(\text{mod}{n}^2)$ (this is true for any positive $n$).

3. Alice has message represented as $m(\text{mod}n)$. She encrypts $m$ by first choosing a random integer $r$ with $gcd(r\text{,}n)=1$. She then computes

   $$\begin{array}{cc}c\equiv {(1+n)}^m{r}^n& (\text{mod }{n}^2)\text{.}\end{array}$$

4. Bob decrypts by computing $m^{\prime }\equiv c^{\varphi (n)}(\text{mod}{n}^2)$. Show that $m^{\prime }\equiv 1+\varphi (n)mn(\text{mod}{n}^2)$. Therefore, Bob can recover the message by computing $(m^{\prime }-1)/n$ and then dividing by $\varphi (n)(\text{mod}n)$.

5. Let $E(m)$ and $D(c)$ denote encryption and decryption via the method in parts (c) and (d). Show that

   $$\begin{array}{cc}D(E(m_1)E(m_2))\equiv D(E(m_1+m_2))& (\text{mod}n)\text{.}\end{array}$$(9.1)

   Note: The encryptions probably use different values of the random number $r$, so there is more than one possible encryption of a message $m$. Part (e) says that, no matter what choices are made for $r$, the decryption of $E(m_1)E(m_2)$ is the same as the decryption of $E(m_1+m_2)$.

The preceding is called the Paillier cryptosystem. (Equation 9.1) says that is is possible to do addition on the encrypted messages without knowing the messages. For many years, a goal was to design a cryptosystem where both addition and multiplication could be done on the encrypted messages. This property is called homomorphic encryption, and the first such system was designed by Gentry in 2009. Current research aims at designing systems that can be used in practice.

One possible application of the Paillier cryptosystem from the previous exercise is to electronic voting (but, as we’ll see, modifications are needed in order to make it secure). Bob, who is the trusted authority, sets up the system. Each voter uses $m=0$ for NO and $m=1$ for YES. The voters encrypt their $m$s and send the ciphertexts to Bob.

1. How does Bob determine how many YES and how many NO votes without decrypting the individual votes?

2. Suppose an overzealous and not very honest voter wants to increase the number of YES votes. How is this accomplished?

3. Suppose someone else wants to increase the number of NO votes. How can this be done?

Here is a 3-person encryption scheme based on the same principles as RSA. A trusted entity chooses two large distinct primes $p$ and $q$ and computes $n=pq$, then chooses three integers $k_1\text{,}{k}_2\text{,}{k}_3$ with $k_1{k}_2{k}_3\equiv 1(\text{mod}(p-1)(q-1))$. Alice, Bob, and Carla are given the following keys:

1. Alice has a message that she wants to send to both Bob and Carla. How can Alice encrypt the message so that both of them can read decrypt it?

2. Alice has a message that she wants to send only to Carla. How can Alice encrypt the message so that Carla can decrypt it but Bob cannot decrypt it?