RSA or RNG

I did not manage to solve this. Have to search on Github for some solution (very shameless to admit). I made some mistakes in solving the problem, which will be mentioned below. The challenge is similar to the so easy rsa challenge in HITCON 2021, in which maple3142 has a good blog entry about.

Denote the Linear Congruential Generator (LCG) function as $f(x)=ax+b$$f(x) = ax + b$, we have $q=f^x(p)$$q = f^x(p)$ for some unknown $x\in [2,1000]$$x \in [2, 1000]$. The range is from running the LCG for a bit, and due to the distribution of primes.

We also have $n=pq$$n = pq$, or substituting the above: $n=p{f}^x(p)$$n = p f^x(p)$. $f^x(p)$$f^x(p)$ is some function of degree 1 in terms of $p$$p$. Indeed, for instance, $f^2(p)=a(ap+b)+b=a^{2}p+ab+b$$f^2(p) = a(ap + b) + b = a ^ 2 p + ab + b$, and obviously it is of degree 1. Hence, $p{f}^x(p)-n$$p f^x(p) - n$ is some quadratic equation in terms of $p$$p$.

I made the mistake of not looking at the problem in this manner, seeing the $a^2$$a ^ 2$ and $a^3$$a ^ 3$ makes me think that the polynomial is of very high degree, which is very wrong. Also I did not think of this in the idea of $p,q$$p, q$ being related to each other, and the fact that the $x$$x$ can be brute forced. These are all new ideas and I am glad I actually looked at the solution to figure this out.

To solve the quadratic in modulo $2^{5}12$$2 ^ 512$, one can use the Hensel's lemma, or work in 2-adic. Both I have no idea how the math works, but the 2-adic idea looks just like solving normal equations. The following is the Sage implementation of the latter idea:

xxxxxxxxxx
from Crypto.Util.number import * 

e = 65537 
N = 95397281288258216755316271056659083720936495881607543513157781967036077217126208404659771258947379945753682123292571745366296203141706097270264349094699269750027004474368460080047355551701945683982169993697848309121093922048644700959026693232147815437610773496512273648666620162998099244184694543039944346061
ct = "04fee34327a820a5fb72e71b8b1b789d22085630b1b5747f38f791c55573571d22e454bfebe0180631cbab9075efa80796edb11540404c58f481f03d12bb5f3655616df95fb7a005904785b86451d870722cc6a0ff8d622d5cb1bce15d28fee0a72ba67ba95567dc5062dfc2ac40fe76bc56c311b1c3335115e9b6ecf6282cca"

MOD = 2**512
A = 2287734286973265697461282233387562018856392913150345266314910637176078653625724467256102550998312362508228015051719939419898647553300561119192412962471189
B = 4179258870716283142348328372614541634061596292364078137966699610370755625435095397634562220121158928642693078147104418972353427207082297056885055545010537

def factor():    
    R.<p> = PolynomialRing(Zp(2, 512))
    q = p 

    for i in range(1000):
        print("Interval:", i)
        q = A * q + B 

        f = p * q - N 

        possible_sols = [ZZ(p) for p, e in f.roots()]

        for sol in possible_sols:
            if N % sol == 0:
                return int(sol)
    

p = factor()
q = N // p

d = pow(e, -1, (p - 1) * (q - 1))
m = pow(int(ct, 16), d, N)
print(long_to_bytes(m))

The Hansel lifting solution (and the one I search on Github) is at this link. Some good resource: Youtube video on how to solve the problem when modulo prime, and blog post about solving quadratic congruences.

For prime modulus, we can also do factoring (which is the same as calculating the roots). See the implementation at this HITCON 2021 writeup