Creating this blogpost almost entirely to share one writeup :P.

I saw UMassCTF on ctftime one fine day and decided to delve into the cryptography challenges.

Due to my mountains of homework I opted only to attempt the RSA challenge and I solved it! … after the CTF ended.

Nevertheless I think that my writeup will be of help to my learning and of utility to future CTF players.

WeirdRSA (500 pts)

Wanna take a look at this challenge? 

I tried the normal decryption for RSA but for some reason it isn't working.

http://static.ctf.umasscybersec.org/crypto/3e057374-8731-4bf5-be5c-c436a8dab580/chall.py

Created by Soul#8230

Reconnaissance

We are greeted by this interesting snippet:

import random
from Crypto.Util.number import isPrime

m, Q = """REDACTED""", 1 

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 4)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 4)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

def pow(m, e, n):     
    return v(e)

def v(n):
    if n == 0:
        return 2
    if n == 1:
        return m
    return (m*v(n-1) - Q*v(n-2)) % N

p, q = genPrimes(1024)

N = p * q
e = 0x10001

print("N:", N)
print("c:", pow(m, e, N))

"""
N: 18378141703504870053256589621469911325593449136456168833252297256858537217774550712713558376586907139191035169090694633962713086351032581652760861668116820553602617805166170038411635411122411322217633088733925562474573155702958062785336418656834129389796123636312497589092777440651253803216182746548802100609496930688436148522617770670087143010376380205698834648595913982981670535389045333406092868158446779681106756879563374434867509327405933798082589697167457848396375382835193219251999626538126258606572805220878283429607438382521692951006432650132816122705167004219371235964716616826653226062550260270958038670427
c: 14470740653145070679700019966554818534890999807830802232451906444910279478539396448114592242906623394239703347815141824698585119347592990685923384931479024856262941313458084648914561375377956072245149926143782368239175037299219241806241533201175001088200209202522586119648246842120571566051381821899459346757935757111233323915022287370687524912870425787594648397524189694991735372527387329346198018567010117587531474035014342584491831714256980975368294579192077738910916486139823489975038981139084864837358039928972730135031064241393391678984872799573965150169368237298603189344477806873779325227557835790957023000991
"""

Those familiar with RSA should instantly spot the strange exponentiation function pow(m,e,N). It seems to be some kind of recurrence relation (precisely, a Lucas sequence) of the form

and we are to somehow invert it.

Also, the genPrimes() function indicates that the two primes only differ in their 256 least significant bits. This reeks of Fermat’s Factorization Method, which can quickly factorize composite numbers with prime factors close together.

Some quick google-fu brings us to this paper that talks about the use of Lucas sequences to substitute for modular exponentiation in RSA.

This cryptosystem, for the sake of namedropping, is called Lucas RSA or LUCRSA, whatever have you.

Reading the Paper

Everything is very similar to RSA. Similar decryption framework, similar assumptions (Large Pseudoprime Factorization is hard), etc.

The Cryptosystem

Heres a bad summary of how the LUCRSA cryptosystem works:

Thus we define \(N=pq\) where p,q are primes, a public exponent \(e\), and a plaintext (converted into integers) \(m\).

Our substitute for the exponentiation function is the recurrence relation \(v_{e}(n) = mv_{e}(n-1)-v_{e}(n-2)\) with \(v_{e}(0)=2, v_{e}(1)=m\).

Encryption

To encrypt, we simply look up the \(e^{th}\) term in the recurrence relation \(v_{e}\). This gives us our ciphertext \(c\).

Decryption

Decryption in LUCRSA is also rather similar.

Instead of Euler’s totient function \(\phi(N)\) we instead consider Lehmer’s totient function \(t(N) = (p-\left(\frac{D}{p}\right))(q-\left(\frac{D}{q}\right))\), as referenced from the paper.

There also exists an analogue of the Carmichael’s lambda function \(\lambda(N)\), which is often used in place of \(\phi(N)\). It is defined as \(s(N)=lcm((p-\left(\frac{D}{p}\right)),(q-\left(\frac{D}{q}\right)))\).

Instead of computing \(d\) where \(ed \equiv 1 \pmod{\phi(N)}\) in regular RSA, we compute \(ed \equiv 1 \pmod{t(N)}\).

Lastly, we define a new recurrence relation for decryption, \(v_{d}(n) = cv_{d}(n-1)-v_{d}(n-2)\) with \(v_{d}(0)=2, v_{d}(1)=c\).

We then look up the \(d^{th}\) term in the recurrence relation \(v_{d}\) to recover \(m\).

That seems pretty easy.

And you’d be right, if it were not for recursion. D:

Realise that even if you implemented the naive recursive algorithm for \(v_{d}\), you would have about 2**2046 recursion calls.

(By naive, I mean you simply abused the properties of \(v_{d}\) provided in the paper.)

For being such a fan of recursion, Python3 would reward you with:

RecursionError: maximum recursion depth exceeded in comparison

(Yes, this will happen even if you sys.setrecursionlimit(2**32-1), the maximum allowable recursion limit in Python).

So instead, I present you 3 smarter approaches, my own, that of the challenge setter, Soul#8230, and another solution done by Rey#7813.

Smart(er) Solution No 1: Matrix Exponentiation (N00bcak)

It is commonly known that the Fibonacci numbers can be efficiently calculated if we consider the following equation:

starting with \(\begin{bmatrix}F_{1} \\ F_{0}\end{bmatrix} = \begin{bmatrix}1 \\ 1 \end{bmatrix} \pmod N\)

Essentially, we are iteratively doing the following steps:

• Compute \(F(n+1)=F(n)+F(n-1)\)
• Move \(F(n)\) in the upper row of the matrix \(\begin{bmatrix}F_{n+1} \\ F_{n}\end{bmatrix} \pmod N\) to the lower row.
• Move \(F(n+1)\) to the upper row of the same matrix

Generalizing this idea, we can do something similar for \(v_{d}\).

We instead construct the equation

starting with \(\begin{bmatrix}v_{d,1} \\ v_{d,0}\end{bmatrix} = \begin{bmatrix}c \\ 2 \end{bmatrix} \pmod N\).

Ok but I am not convinced that this won’t take seventy trillion centuries

It won’t if you have a GPU >:)))

Jokes aside, repeated matrix multiplication is fast, but look at this:

d: 100952607126688026903464794905613135743376133926243507941633382859591885475 362592986814791882009957277702254617584724174536165999151192904694964832087 554440992064672015194793991610674092559440865440101193893727245538342250226 054024485727310015110343475084372325136932298905959666058125473516117441408 193176669955827209622251066457076784585371373964277798061865411821246530561 383535103167981845269581107478839208362184363684861933751977628913990071405 958328582095998026994488924875397572666822615094574032473410127350687926799 7897021195578431451783598575024934925665773924302367241787422460973592399521285519201923073

Indeed, the source of this method’s speed actually lies in the square-and-multiply exponentiation algorithm.

The core idea of this algorithm is to reconstruct the binary representation of m in exponentiating, allowing exponentiation to be carried out quickly and efficiently.

Basically for any exponent m:

1. Keep a copy of the original item you wish to exponentiate \(P_{original}\) and store your exponentiation result under \(R\).

2. Define two operations, square and multiply.

   1a. square - Assign \(R \leftarrow R^2\)

   1b. multiply - Assign \(R \leftarrow R \cdot P_{original}\)

3. Convert m into binary representation.

4. For every bit b in m’s binary representation (left-to-right),

   3a. If b is 1, square and multiply.

   3b. If b is 0, square.

Thus we can perform large exponentiations in \(\approx log_{2}m\) operations. (ngl taking the \((2^{10^{9}})^{th})\) power in one second-ish is pretty cool.)

Script 1

And thus, here is my script:

from Crypto.Util.number import long_to_bytes

N=1837814170350487005325658962146991132559344913645616883325229725685853721
777455071271355837658690713919103516909069463396271308635103258165276086166
811682055360261780516617003841163541112241132221763308873392556247457315570
295806278533641865683412938979612363631249758909277744065125380321618274654
880210060949693068843614852261777067008714301037638020569883464859591398298
167053538904533340609286815844677968110675687956337443486750932740593379808
258969716745784839637538283519321925199962653812625860657280522087828342960
743838252169295100643265013281612270516700421937123596471661682665322606255
0260270958038670427
C=1447074065314507067970001996655481853489099980783080223245190644491027947
853939644811459224290662339423970334781514182469858511934759299068592338493
147902485626294131345808464891456137537795607224514992614378236823917503729
921924180624153320117500108820020920252258611964824684212057156605138182189
945934675793575711123332391502228737068752491287042578759464839752418969499
173537252738732934619801856701011758753147403501434258449183171425698097536
829457919207773891091648613982348997503898113908486483735803992897273013503
106424139339167898487279957396515016936823729860318934447780687377932522755
7835790957023000991

def ffm(num): # Fermat's Factorization Method.
    if num%2==0: return (2,num/2)
    a=ceil(sqrt(num))
    c=a**2-num
    while is_square(c)==0: a+=1
    b=sqrt(c)
    return (a-b,a+b)

def matpow(mat,power): # Matrix Square-And-Multiply Exponentiation.
    power_rep=bin(power)[3:]
    result=mat
    pcnt=1
    for i in power_rep:     
        result=result*result
        pcnt*=2
        if i=='1':
            result=mat*result
            pcnt+=1
    print(pcnt)
    return result

def decrypt(d): # Decryption.
    Mat=Matrix(Zmod(N),[[C,-1],[1,0]])
    ori=vector(Zmod(N),[C,2])
    return matpow(Mat,d-1)*ori

p,q=ffm(N) 
assert p*q==N
D=(C**2-4)%N
p_leg,q_leg=int((p-kronecker(D,p))%N),int((q-kronecker(D,q))%N)
tn=lcm((p_leg),(q_leg))
d=inverse_mod(0x10001,tn)
assert (0x10001*d)%tn==1
decc,_=decrypt(d)
print(long_to_bytes(decc))

Smart(er) Solution No 2: Memoization (Soul#8203)

This is the intended solution by the challenge setter.

One can not only exploit these properties of \(v_{d}\):

But also keep track of all \(v_{d}\) values computed so far in a dictionary.

This will keep recursion calls down while also speeding up the algorithm significantly.

Script 2

def v(n):
    if n == 0: return 2
    if n == 1: return c
    if n in v_dict.keys(): return v_dict[n]
    if(n % 2 == 0): ret = (pow(v(n // 2), 2, N) - 2) % N
    else: ret = (c * pow(v(n // 2), 2, N) -  v(n // 2) * v((n // 2) - 1) - c) % N
    v_dict[n] = ret
    return ret

Smart(er) Solution No 3: (Rey#7813)

This solution uses William’s p+1 algorithm to optimize \(v_{d}\).

I do not claim (as of yet) to understand what it does, so I will just link you to this writeup and show you the script:

Script 3

# Williams's p + 1 algorithm
def LUC(c, d, N):
	x = c
	y = (c**2 - 2) % N
	for bit in bin(d)[3:]:
		if bit == '1':
			x = (x*y - c) % N
			y = (y**2 - 2) % N
		else:
			y = (x*y - c) % N
			x = (x**2 - 2) % N
	return x

WHERES THE FLAG? (WTF)

Here!

b'UMASS\\{who_said_we_had_to_multiply_117a1b8a68814dc478ad78bc67d7d7d4\\}'

N00bcak Outtakes

My first instinct was, bizarrely, to derive the closed form solution of the sequence.

This, I would not have realized on my 11pm brain, would involve surds and is rather dumb.

In case you are curious, we can rewrite the recurrence relation in its characteristic equation to obtain:

which simplifies to

Solving, we obtain

Notice that \(\pmod N\) was missing from these workings the whole time. I will stop here because… man this was dumb.