## Content

### Factoring challenge #1:

Your goal in this project is to break RSA when the public modulus $N$ is generated incorrectly. This should serve as yet another reminder not to implement crypto primitives yourself.

Normally, the primes that comprise an RSA modulus are generated independently of one another. But suppose a developer decides to generate the first prime $p$ by choosing a random number $R$ and scanning for a prime close by. The second prime $q$ is generated by scanning for some other random prime also close to $R$.
We show that the resulting RSA modulus $N=p q$ can be easily factored.

Suppose you are given a composite(合数) $N$ and are told that $N$ is a product of two relatively close primes $p$ and $q$, namely $p$ and $q$ satisfy

$|p-q|<2 N^{1 / 4}$

Your goal is to factor $N$.
Let $A$ be the arithmetic(算数) average of the two primes, that is $A=\frac{p+q}{2}$. Since $p$ and $q$ are odd(奇数), we know that $p+q$ is even and therefore $A$ is an integer(整数).

To factor $N$ you first observe that under condition $\left.{ }^*\right)$ the quantity $\sqrt{N}$ is very close to $A$. In particular, we show below that:

${A-\sqrt{N}<1}*$

But since $A$ is an integer, rounding $\sqrt{N}$ up to the closest integer reveals the value of $A$. In code, $A=$ ceil $(\operatorname{sqrt}(N))$ where “ceil” is the ceiling function.
Visually, the numbers $p, q, \sqrt{N}$ and $A$ are ordered as follows:

Since $A$ is the exact mid-point between $p$ and $q$ there is an integer $x$ such that $p=A-x$ and $q=A+x$. But then $N=p q=(A-x)(A+x)=A^2-x^2$ and therefore $x=\sqrt{A^2-N}$.

Now, given $x$ and $A$ you can find the factors $p$ and $q$ of $N$ since $p=A-x$ and $q=A+x$. You have now factored $N$ !

$\because A是p,q的中点$

$\therefore$ $p=A-x$ $q=A+x$$\implies N=p q=(A-x)(A+x)=A^2-x^2$

$\therefore x=\sqrt{A^2-N}$

Further reading: the method described above is a greatly simplified version of a much more general result on factoring when the high order bits of the prime factor are known.

In the following challenges, you will factor the given moduli using the method outlined above. To solve this assignment it is best to use an environment that supports multi-precision arithmetic and square roots. In Python you could use the gmpy2 module. In C you can use GMP.

The following modulus $N$ is a products of two primes $p$ and $q$ where $|p-q|<2 N^{1 / 4}*$. Find the smaller of the two factors and enter it as a decimal integer in the box below.

For completeness, let us see why $A-\sqrt{N}<1$. This follows from the following simple calculation.
First observe that $A^2-N=\left(\frac{p+q}{2}\right)^2-N=\frac{p^2+2 N+q^2}{4}-N=\frac{p^2-2 N+q^2}{4}=(p-q)^2 / 4$.
Now, since for all $x, y: \quad(x-y)(x+y)=x^2-y^2$ we obtain $A-\sqrt{N}=(A-\sqrt{N}) \frac{A+\sqrt{N}}{A+\sqrt{N}}=$ $\frac{A^2-N}{A+\sqrt{N}}=\frac{(p-q)^2 / 4}{A+\sqrt{N}}$
Since $\sqrt{N} \leq A$ it follows that $A-\sqrt{N} \leq \frac{(p-q)^2 / 4}{2 \sqrt{N}}=\frac{(p-q)^2}{8 \sqrt{N}}$.
By assumption (*) we know that $(p-q)^2<4 \sqrt{N}$ and therefore $A-\sqrt{N} \leq \frac{4 \sqrt{N}}{8 \sqrt{N}}=1 / 2$ as required.

$0$\implies A<\sqrt{N}+1$

$\text{proof:}$

${A}=\frac{p+q}{2}, {~N}={pq}$ $A为整数$

$0<{A}-\sqrt{N}$ :

$A-\sqrt{N}<1$,有:

$\mathrm{A}^2-\mathrm{N}=\left(\frac{\mathrm{p}+\mathrm{q}}{2}\right)^2-\mathrm{N}=\frac{\mathrm{p}^2+2 \mathrm{~N}+\mathrm{q}^2}{4}-\mathrm{N}=\frac{\mathrm{p}^2-2 \mathrm{~N}+\mathrm{q}^2}{4}=\frac{(\mathrm{p}-\mathrm{q})^2}{4}\tag{1}$

$A-\sqrt{N}=\frac{(A-\sqrt{N})(A+\sqrt{N})}{A+\sqrt{N}}=\frac{A^2-N}{A+\sqrt{N}}={A+\sqrt{N}}=\frac{\frac{(p-q)^2}{4}}{A+\sqrt{N}} \tag{1}$

$A-\sqrt{\mathrm{N}}=\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\mathrm{~A}+\sqrt{\mathrm{N}}}<\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\sqrt{\mathrm{N}}+\sqrt{\mathrm{N}}}=\frac{(\mathrm{p}-\mathrm{q})^2}{8 \sqrt{\mathrm{N}}} \tag{3}$

$\mathrm{A}-\sqrt{\mathrm{N}}=\frac{(\mathrm{p}-\mathrm{q})^2}{8 \sqrt{\mathrm{N}}}<\frac{4 \sqrt{\mathrm{N}}}{8 \sqrt{\mathrm{N}}}=1 / 2<1 \tag{4}$

Enter the answer for factoring challenge #1 in the box below:

code:

### Factoring challenge #2:

The following modulus $N$ is a products of two primes $p$ and $q$ where $|p-q|<2^{11} N^{1 / 4}$. Find the smaller of the two factors and enter it as a decimal integer.

Hint: in this case $A-\sqrt{N}<2^{20}$ so try scanning for $A$ from $\sqrt{N}$ upwards, until you succeed in factoring $N$.

$\text{Proof:}$

${A}=\frac{p+q}{2}, {~N}={pq}$ $A$为整数

$|p-q|<2^{11} N^{1 / 4}$$\implies$$(p-q)^2<2^{22}\sqrt{N}$

$0

Enter the answer for factoring challenge #2 in the box below:

Code

### Factoring challenge #3:

The following modulus $N$ is a product of two primes $p$ and $q$ where $|3 p-2 q|. Find the smaller of the two factors and enter it as a decimal integer.
Hint: first show that $\sqrt{6 N}$ is close to $\frac{3 p+2 q}{2}$ and then adapt the method in challenge #1 to factor $N$.

$A-\sqrt{6N}<\frac{1}{8\sqrt{6}}$

$\text{Proof:}$

$\because$$\text{A是3p,2q的中点}$

$\therefore$ $p=\frac{A-x}{3}$ $q=\frac{A+x}{2}$$\implies N=p q=\frac{(A-x)(A+x)}{6}=\frac{A^2-x^2}{6}$(这里其实$\frac{A-x}{3}$有可能为p或者q,还要根据$A-x$是否被3除尽就可确定)

$\therefore x=\sqrt{A^2-6N}$

$\sqrt{ab}<=\frac{a+b}{2}$

$\therefore{\sqrt{6pq}<\frac{3p+2q}{2}}$$\implies \sqrt{6N}

$A-\sqrt{6N}=\frac{A^2-6N}{A+\sqrt{6N}}=\frac{\frac{(3p-2q)^2}{4}}{A+\sqrt{6N}}<\frac{\frac{(3p-2q)^2}{4}}{\sqrt{6N}+\sqrt{6N}}=\frac{\frac{(3p-2q)^2}{4}}{2\sqrt{6N}} \tag {6}$

$A-\sqrt{6N}<\frac{\frac{(3p-2q)^2}{4}}{2\sqrt{6N}}<\frac{1}{8\sqrt{6}}$

Enter the answer for factoring challenge #3 in the box below:

code

### 4.

The challenge ciphertext provided below is the result of encrypting a short secret ASCII plaintext using the RSA modulus given in the first factorization challenge.

The encryption exponent used is $e=65537$ The ASCII plaintext was encoded using PKCS v1.5 before the RSA function was applied, as described in PKCS.

Use the factorization you obtained for this RSA modulus to decrypt this challenge ciphertext and enter the resulting English plaintext in the box below. Recall that the factorization of $N$ enables you to compute $\varphi(N)$from which you can obtain the RSA decryption exponent.

After you use the decryption exponent to decrypt the challenge ciphertext you will obtain a PKCS1 encoded plaintext.To undo the encoding it is best to write the decrypted value in hex.You will observe that the number starts with a ‘0x02’ followed by many random non-zero digits.Look for the ‘0x00’ separator and the digits following this separator are the ASCII letters of the plaintext.

(note: the separator used here is ‘0x00’, not ‘0xFF’ as stated in the lecture)