Question_1

We show that the resulting RSA modulus N=pq 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|<2N^{1/4}\quad (*)$$
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 (*) the quantity $\sqrt{N}$ is very close to $A$. In particular, we show below that:
$$A-\sqrt{N}<1$$

For completeness, let us see why $A-\sqrt{N}<1$. This follows from the following simple calculation.
First observe that$A^2-N=(\frac{p+q}{2})^2-N=(\frac{p-q}{2})^2=(p-q)^2/4$
Now, we obtain $A-\sqrt{N}=\frac{A^2-N}{A+\sqrt{N}}=\frac{(p-q)^2/4}{A+\sqrt{N}}$
Since $\sqrt{N}\le A$ it follows that $A-\sqrt{N}\le\frac{(p-q)^2/4}{2\sqrt{N}}$
By assumption (*) we know that $(p-q)^2<4\sqrt{N}$ and therefore $A-\sqrt{N}\le \frac{4\sqrt{N}}{8\sqrt{N}}=\frac{1}{2}$

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

There is an integer x such that $p=A−x$ and $q=A+x$.
But then $N=pq=(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 !
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.

N = "179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581"


$a=\sqrt{N};$
$A=ceil(a);$
$x=\sqrt{A^2-N};$
$p=A-x,q=A+x;$
$output\quad smaller(p,q);$

Question_2

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

$i=ceil(\sqrt{N});$
$for\quad a\quad in\quad i\quad to\quad i+2^{19}:$
$\quad x=\sqrt{a^2-N};$
$\quad p=(a+x);q=(a-x);$
$\quad test\quad if\quad N=pq\quad break;$
$output\quad p,q;$

Question_3

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

$a=\sqrt{24N};$
$A=ceil(a);$
$x=\sqrt{A^2-24N};$
$p=\frac{A-x}{6},q=\frac{A+x}{4};$
$output\quad smaller(p,q);$

Question_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 $\phi(N)$ from which you can obtain the RSA decryption exponent.

Challenge ciphertext (as a decimal integer):
220964518674103817763065611348834180174100697878928232......

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.

$fi=(p-1)(q-1);$
$d=invert(e)\pmod{fi};$
$PlainText=(CipherText)^d\pmod{N};$
$PlainText_h=dec2hex(PlainText);$
$index=PlainText_h.find(0\times00);$
$output\quad PlainText_h[index:;];$

mpz_get_str(PlainText,16,mpz_t_PT); //转成16为底的字符串


程序源码

Question_1

13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301


Question_2

25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759


Question_3

21909849592475533092273988531583955898982176093344929030099423584127212078126150044721102570957812665127475051465088833555993294644190955293613411658629209


Question_4

Factoring lets us break RSA.


结束语

Week6就要结束了，这门课就完成了，接下来还有Cryptography II，很是期待。