LCS35 Challenge [SOLVED - April 2019]

LCS35 IS SOLVED. It had been confirmed that Bernard Fabrot solved the challenge using a Core i7-6700, the GNU Multiple Precision Arithmetic Library and 3,5 years of time.

The LCS35 challenge (see also Scienceblogs) is a neat little and still unsolved challenge posed by Ron Rivest, one of the inventors of the famous RSA cryptosystem, back in the year 1999. It consists of a single task: Given 2048-bit RSA integer $n$ and an exponent $t$, compute the following value $W$: $$W \equiv 2^{(2^t)}  \pmod{N}$$ The actual values for the challenge are:

n = 631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681

t = 79685186856218

Additionally, there is an integer $z$, which has to be xor'ed with $W$ to reveal the actual 'plaintext', i.e.: $$\text{Plaintext} \leftarrow z \otimes W $$ The given value for $z$ is:

z = 427338526681239414707099486152541907807623930474842759553127
    699575212802021361367225451651600353733949495680760238284875
    258690199022379638588291839885522498545851997481849074579523
    880422628363751913235562086585480775061024927773968205036369
    669785002263076319003533000450157772067087172252728016627835
    400463807389033342175518988780339070669313124967596962087173
    533318107116757443584187074039849389081123568362582652760250
    029401090870231288509578454981440888629750522601069337564316
    940360631375375394366442662022050529545706707758321979377282
    989361374561414204719371297211725179287931039547753581030226
    7611143659071382

As written in [1], the plaintext consists of two parts. One is a secret message and the second part is a hint towards the factorisation of $n$, i.e., the exponent $E$, such that $\text{nextPrime}(5^E \text{ mod }2^{1024})$ is a divisor of $n$. They designed the challenge such that, even when considering Moore's Law, it will probably first be solved around the year 2035. The reason that this might probably be true is, that this problem is non parallelizable. It is a linear operation that only involves squaring the previous output. $$ (2^{2^0})^2 = 2^{(2^1)} \rightarrow (2^{(2^1)})^2 = 2^{(2^2)} \rightarrow (2^{(2^2)})^2 = 2^{(2^3)}\rightarrow \ldots \rightarrow (2^{(2^{t-1})})^2 = 2^{(2^t)}$$ It is compareable to the Proof-Of-Work method, modern crypto currency use to mine their coins. If the factorisation of $n$ is known, than this task would be very easy, even if $t$ would be much larger, say around the size of $n$. One simply computes $$2^t \equiv e \pmod{\varphi(n)}$$ and afterward $2^e \equiv W\pmod{N}$. Since $e < \varphi(n) < n$, this is of complexity $\mathcal{O}(\text{log}_2 n)$ and thus can be computed in milliseconds on modern PCs.

-- Some ideas --

⬛ Some remarkable fact is, that $2^{({2^t})}$ is nearly a Fermat number. The $n$-th Fermat number is defined as: $$F_n = 2^{({2^n})}+1$$ So the challenge could be rephrased to:

LCS35 (rephrased): Compute the t-th Fermat number modulo n.

Fermat numbers have some nice recursive properties. For example $$F_n = 2 + \prod^{n-1}_{i=1} F_i$$ or $$F_n = (F_{n-k} - 1)^{2^k} + 1 $$ Fermat numbers are an example for double exponential functions. And being double exponential seems to be the problem that denies a fast algorithm if the order of the group (here the multiplicative group generated by $2$ in the ring $\mathbb{Z}^*_n$) is unknown.

You can also bring Fermat number into the exponent if you write the challenge in the following way: $$t = 2^{e_m} + 2^{e_{m-1}} + \ldots + 2^{e_0}$$ then
$$2^{(2^t)} = 2^{(2^{2^{e_m} + 2^{e_{m-1}} + \ldots + 2^{e_0}})} = 2^{(2^{2^{e_m}}\cdot 2^{ 2^{e_{m-1}}}\cdot \ldots \cdot 2^{2^{e_0}})} = 2^{(F_{e_m}-1)(F_{e_{m-1}}-1)\ldots(F_{e_0}-1)}$$ Since the actual binary representation of $t$ is: $$t = 10010000111100100100111010000011010010100011010$$ the exponent becomes:
\begin{align*}
&(F_{46}-1)(F_{43}-1)(F_{38}-1)(F_{37}-1)(F_{36}-1)(F_{35}-1)(F_{32}-1)(F_{29}-1) \\
&(F_{26}-1)(F_{25}-1)(F_{24}-1)(F_{22}-1)(F_{16}-1)(F_{15}-1)(F_{13}-1)(F_{10}-1) \\
&(F_{8}-1)(F_{4}-1)(F_{3}-1)(F_{1}-1)
\end{align*} Since $$(F_n-1) = \sum^{2^d}_{i=0}\binom{2^d}{i}\left( \prod^{n-d-1}_{j=0} F_j\right)^i$$ and further $$\prod^{n-d-1}_{j=0} F_j = F_{n-d}-2$$ this can be written in a recursive way. For example, a three-step recursion for the largest exponent factor can be written as:
\begin{align*}
& (F_{46}-1)= \sum^{2^d}_{i=0}\binom{2^d}{i}\left( \prod^{n-d-1}_{j=0} F_j\right)^i \\ & = \sum^{2^d}_{i=0} \binom{2^d}{i}\left( F_{n-d} - 2 \right)^i \\
& = \sum^{2^d}_{i=0}\binom{2^d}{i}\left( -1 + \sum^{2^e}_{k=0}\binom{2^e}{k}\left( \prod^{n-d-e-1}_{l=0} F_l\right)^k \right)^i  \\
& = \sum^{2^d}_{i=0}\binom{2^d}{i}\left( -1 + \sum^{2^e}_{k=0}\binom{2^e}{k}\left( F_{n-d-e} - 2\right)^k \right)^i  \\
& = \sum^{2^d}_{i=0}\binom{2^d}{i}\left( -1 + \sum^{2^e}_{k=0}\binom{2^e}{k}\left( -1 + \sum^{2^f}_{m=0}\binom{2^f}{m}\left( \prod^{n-d-e-f-1}_{g=0} F_g\right)^m \right)^k \right)^i  \\
\end{align*} Let us assume that, e.g., $\prod^{16}_{g=0} F_g$ is the maximum product that can be computed reasonable fast (whatever this means). So we could chose $d=e=10$ and $f=9$ which leads to $$  \prod^{n-d-e-f-1}_{g=0} F_g = \prod^{46-10-10-9-1}_{g=0} F_g  = \prod^{16}_{g=0} F_g$$ The advantage is, that the binomial coefficients stay small compared to one large one-step with $\binom{2^{29}}{i}$. Using this values, we get:
\begin{align*}
& (F_{46}-1)=  \sum^{1024}_{i=0}\binom{1024}{i}\left( -1 + \sum^{1024}_{k=0}\binom{1024}{k}\left( -1 + \sum^{512}_{m=0}\binom{512}{m}\left( \prod^{16}_{g=0} F_g\right)^m \right)^k \right)^i
\end{align*}
Just for test purposes, so far i computed $$2^{(F_{29}-1)(F_{26}-1)(F_{25}-1)(F_{24}-1)(F_{22}-1)(F_{16}-1)(F_{15}-1)(F_{13}-1)(F_{10}-1)(F_{8}-1)(F_{4}-1)(F_{3}-1)(F_{1}-1)} \equiv I \pmod{n} $$, hence it is left $$I^{(F_{46}-1)(F_{43}-1)(F_{38}-1)(F_{37}-1)(F_{36}-1)(F_{35}-1)(F_{32}-1)}\pmod{n}$$ which is obviously the way bigger part.

⬛ There are cases, even when the factorization of $n$ is unknown, it is possible to generate groups with known order, e.g., if one steps over to $n^2$. In this case one can compute efficiently $$(1+n\lambda)^{2^t} \pmod{n^2}$$ for any $\lambda \in \mathbb{Z}_n$ using the Binomial theorem. A fact which is also used by Paillier cryptosystem. But this does not bring anyone further to a computation of $$(2+n\lambda)^{2^t} \pmod{n^2}$$ but it may be a starting point for further ideas.

⬛ Another approach might be to use the computation of inverse elements in $\mathbb{Z}_n$. Note that when you compute the inverse of e.g., $2$ then this is $$2^{-1} \equiv 2^{\lambda\varphi(n)-1} \equiv 2^{B+x}\pmod{n}$$  with known $B$ and $B > x$ and any $\lambda \in \mathbb{Z}$. The $B$ comes from the inequalities $$2^{B} < \varphi(n) < n < 2^{B+1}$$
However, since $\varphi(n)$ is unknown, this might not lead to anything useful. And further, the computation of an inverse element is also of complexity $\mathcal{O}(\log_2 n)$, which is the same complexity as to compute $2^{B}$ itself, albeit it seems to be much more efficient in practice to compute the former than the later (so maybe the hidden constants differ).

⬛ According to the binomial theorem one could easily turn $2^t$ into a sum, since $$2^t = (1+1)^t = \sum^t_{i=0} \binom{t}{i} $$ So the challenge is equivalent to compute $$2^{\sum^t_{i=0} \binom{t}{i}} \equiv W \pmod{n}$$ This seems to look like a trivial way to parallize the problem, but the computational task to compute individual terms is almost as computational expensive than to compute the entire sum. Support may come from Ramus' Theorem, which is about arithmetic progressions of binomial coefficients.

Ramus' Theorem (1834).  Let $S(m,n,q) := \sum^{\lfloor m/n \rfloor}_{k=0} \binom{m}{nk+q}$ with $0 \leq q \leq n$ , then it is $$S(m,n,q) = \sum^n_{i=1}\omega^{-qi}(1+\omega^i)^m $$ where $\omega$ is the $n$-th root of unity.

Suppose you have $H$ computing units, than for each integer$0 \leq q < H$ the associated unit computes $$2^{\sum^{\lfloor t/H\rfloor}_k \binom{t}{Hk+q}} \equiv 2^{\sum^H_{k=1}\omega^{-qk}(1+\omega^k)^t} \pmod{n}$$ The problem is the exponent $t$ from $(1+\omega^k)^t$, where in this case $\omega$ is the $H$-th root of unity. For example, the $H$-th term in the sum $$\sum^H_{k=1}\omega^{-qk}(1+\omega^k)^t$$ is $$\omega^{-qH}(1+\omega^H)^t = \omega^{-qH}(1+\omega^H)^t = 2^t$$ which is already equal to the original problem. Note that is possible because $\omega$ is a complex value hence some previous terms can be negative.


[1] http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt