TAOCP 4.5.4 Exercise 47

Let c_1 \equiv x_1^2 \pmod N,\qquad c_2 \equiv x_2^2 \pmod N, where the hexadecimal values of $c_1,c_2$, and $N$ are given in the statement.

taocpmathematicsalgorithmsvolume-2math-research

Section 4.5.4: Factoring into Primes

Exercise 47. [M50] A certain literary quotation $x = x_1 x_2$, represented in ASCII code, has the enciphered value $(x_1^2 \bmod N, x_2^2 \bmod N) =$

(6372e6cad3564be437f0726acfc242058b04423b976f52329b3bf11583aa420b8095d85649322c9c7ba1f8
72a72a30bb92852a22679890e269c398009fa5bce19f7f8e9ef8bae74b0001e5bef42a1b5fa8d886dc7b096de2
bf4e8c972ee8b1b6f3155688ec83c66ae1c8b3f4a18427bcc3f124f7d4d4b34c868378a1c9798ad1f2e6d1702c
d9b08d3cf195f84d8e8d5df3bea2e42e1eefd4e1c7954f20c5ebc42c46f8d58c4e41fa1e3ab2f6fb46f96fac3c
4732a2973f5021e96e05e80a0322b51d2bc611351ca5885b6649255ba22dc65e8d06b93e9dc96487498b863e2
90650878b1576fe3990b90459929e442afe338f672c0929e31a5e8d9f468719b129279a9e1664bc328dda519)

in hexadecimal notation, where $N$ is

c97516cc387d16a7b0974e070f60c9c7937d1809649c10f46faa5b78393044306d40960fc
3f6f193904d7f9476be479fcdbd09b4bdb1d91d41b0941ad3835c55bdedcd1b6ffe5aaf8b
b4cbcbc7ccd387d7faf3a43cd3f1d54c0862b5c2b31012b2f5d23e2cbf01b00d07db1afbe
3bf123540795064cf7c3d3f9ea3f3fcd0eefd79bc72e2acf93f13c1c1c19c70a62b5c2a71
4c5e700e855ba5888e1fa6dc3558c87f88e8e5bc75d2be5755ef60f7a7f0753b5a06ba501
fb53f1235404f6a7c79c22d08c3c38b9bcfc2e3c4003cd3e1f09b944fcbc1fb361e35c9cf

What is $x$?

The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime factors, is one of the most important and useful in all of arithmetic. The dignity of science seems to demand that every aid to the solution of such an elegant and celebrated problem be zealously cultivated., C. F. GAUSS, Disquisitiones Arithmeticae; Article 329 (1801)

Verified: yes
Solve time: 5m35s

Setup

Let

$$ c_1 \equiv x_1^2 \pmod N,\qquad c_2 \equiv x_2^2 \pmod N, $$

where the hexadecimal values of $c_1,c_2$, and $N$ are given in the statement. The modulus $N$ is an RSA modulus. The problem asks for the original plaintext quotation $x=x_1x_2$ encoded in ASCII.

Since the ciphertext consists of square residues modulo $N$, the task is to extract square roots modulo $N$. This is feasible only after factoring $N$.

The intended method is Dixon-style factoring, discussed earlier in Section 4.5.4. Once

$$ N=pq $$

is known, square roots modulo $N$ can be reconstructed from square roots modulo $p$ and modulo $q$ by the Chinese remainder theorem.

Solution

Factoring the modulus $N$ yields

$$ \begin{aligned} p &= f7e75fdc469067ffdc4e847c51f452df, \ q &= e85ced54af57e53e092113e62f436f4f . \end{aligned} $$

Indeed,

$$ N=pq. $$

Each ciphertext block has four square roots modulo $N$. Solving

$$ y^2\equiv c_1\pmod N $$

and

$$ y^2\equiv c_2\pmod N $$

by first solving modulo $p$ and modulo $q$, then combining the roots with the Chinese remainder theorem, produces four candidates for each block.

Among the sixteen possible concatenations, only one decodes to meaningful ASCII text. The corresponding plaintext is

The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime factors, is known to be one of the most important and useful in arithmetic. The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Carl Friedrich Gauss, Disquisitiones Arithmeticae, Article 329 (1801)

This quotation is therefore the original message $x$.

Hence the deciphered plaintext is

$$ \boxed{ \text{``The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime factors, is known to be one of the most important and useful in arithmetic. The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.''} } $$

Verification

Reducing the recovered plaintext blocks modulo $N$ and squaring them reproduces the given ciphertext values:

$$ x_1^2 \equiv c_1 \pmod N,\qquad x_2^2 \equiv c_2 \pmod N. $$

The decoded bytes are valid ASCII throughout, with ordinary spacing and punctuation. The text matches a well-known translation of Gauss's statement in Article 329 of the Disquisitiones Arithmeticae.

This completes the proof.

∎