# N1CTF 2022 Crypto Writeups By tl2cents

91 0 0

In this competition, NeSE solved all the reversing , misc , crypto challenges and won the championship. Here are the detailed writeups of three crypto challenges.

## brandnew check-in

### Solution

By the description : cakectf brand_new_crypto, I went for Google to browse the writeup and found this one : CakeCTF 2022 Writeup. We can use the extended Euclid algorithm to obtain x,y such that : sx+ty=1. Therefore, cx1cy2=mx+yrsx+ty=mx+yr, we can brute force m[0,255] to recover the r0 and use the r0 to verify the original equations : c1=mrs, c2=mrt. By this method, we can recover all the mi and ri if m0.

Now, we have recovered the encrypted flag : encflag=pow(flag,e,n). Notice that ri is generated with getrandbits(1024), we can fully recover MT19937 state and then backtrack to find parameters a or even p,q. Here, parameter a is easy to locate because it is exactly the previous 1024 bits of s. The most important point of recovering MT state is that our recovered ri=getrandbits(1024)modn. Therefore, each ri has 2~3 possible values and we need 20 consecutive parameters ri,..,ri+19 to reconstruct MT state and another 20 consecutive parameters ri+20,..,ri+39 to verify (if not verified, there might be multiple solutions). I found the minimal brute-forcing space is 223.

After we recovered a, tb=samodφ(n)t(1a)+sa=0modφ(n). Therefore, we can obtain kφ(x) and derive the private key to decrypt encflag.

### EXP

MT Cracker (offset = 48, the brute-forcing space is minimal, 12 cores multi-process, time cost : 6 minutes):

## ezdlp

### Solution

Use lattice and gcd to recover the correct modulo N. Since N has a semi-smooth order prime (B1=225,B2=232) , we can use Pollard p-1 algorithm to factorize N and Pohlig-Hellman algorithm to compute the discrete logarithm to obtain flag.

### Recover modulo N

The first step to recover the modulo N. Since the exponent is too large to be computed in Integer Ring, we can construct a lattice to narrow down the exponents. The lattice is as follows:

M=⎡⎣⎢⎢⎢⎢m1m2...m4710...001...0............00...1⎤⎦⎥⎥⎥⎥(1)

Apply LLL algorithm to M: L=M.LLL(). Denoting Li=[ri,ki1,...,ki47] as the ith row of L, we have the following equations :

j=147mjkij=ri,i=1,2,..,47(2)

In (2), if kij<0, place it on the left side; if ri<0, place it on the right side. Now every parameter is positive, and we exponentiate both sides of the equation with base = 0x10001 and then subtract them to get integer multiples of modulo N. We can compute n=gcd(kn1,kn2,..,kn47)and then filter all the small factors to recover the real modulo N (about 1034 bits).

### Semi-Smooth Factorization and Discrete Logarithm

If we simply run Pollard’s p-1 algorithm on N, it costs about 10 hours in sage with time complexity 232. This TCC paper explains the concept of semi-smooth and related factorization attacks. Yafu implements such factorization. Assume the two bounds for semi-smooth order prime are : B1=2a, B2=2b,b>a, the time complexity is O(2a+2b‾‾√). In the challenge, the time complexity is O(225).

For yafu, the max B1 bound is 232 and for B2, the upper bound should be 264. If you find that with correct B1,B2 you can’t obtain the factorization, you can increase the bound B2 a little and run again.

The yafu documentation of pm1:

[pm1]
usage: pm1(expression)

description:
New in version 1.28: uses GMP-ECM exclusively. Stage 1 bound is configurable using
the POLLARD_STG1_MAX parameter. The default is 100000. Stage 2 bound is also
configurable using the POLLARD_STG2_MAX parameter.

To use the default B2 with gmp-ecm, simply do not specify the B2ecm or B2pp1 or B2pm1
flags in the .ini file or in the command line arguments.
Specifying B2 as well will cause the default value to be overridden.

command line flags affecting pm1:

-B1pm1 B1 bound in the pm1 method
-B2pm1 B2 bound in the pm1 method

Crack our modulo in this challenge, a few seconds:

After factorization, just use discrete_log of sage to obtain the flag.

### EXP

Lattice to compute kn

Factorization by yafu , then compute discrete logarithm:

## babyecc

### Solution

First use the point doubling formula to construct an equation (g(m,a,b,y)=0modn) for every set of (n,a,b,y). Combine these polynomials fi(m)=g(m,ai,bi,yi) with CRT to derive a new polynomial F(m)modni. Finally we can get the small root of F (coppersmith method) and recover the flag.

### Construct Polynomial

Point (x,y) doubling formula of Weierstrass normal form ECC :

⎧⎩⎨⎪⎪⎪⎪y2=x3+ax+bλ=3x2+12yxr=λ22xyr=λ(xxr)y(1)

Consider the double point with x-coordinate= m , from (1), xr=(3m2+a2y)22m=(3m2+a)24(m3+am+b)2m, multiply both sides with 4(m3+am+b) :

4(m3+am+b)xr=(3m2+a)28m(m3+am+b)(2)

The ECC polynomial :

y2r=x3r+ax+b(3)

Denote k, c as :

{k=4(m3+am+b)c=(3m2+a)

Combine (2), (3) :

y2r=(ck2m)3+a(ck2m)+bk3y2r[(c2mk)3+a(k2c2mk3)+bk3]=0(4)

Now we have constructed a polynomial f(x) modulo n and f(m)=0.

### SMUPE-problem

In this section, we focus on solving Systems of Modular Univariate Polynomial Equations (SMUPE).

A straight forward method : combine all the polynomials with CRT and we can obtain a new polynomial F(x)modni which coppersmith method can be applied to. Let the max degree of fi is θ and every Ni is about 2nbit, the upper bound of common root xo is 2k×nbits/θ. In this challenge, we have 7 polynomials; the degree of all fi is 12; the bits of Ni is 1024. Therefore, the upper bound of x0 for the above idea is 271024/122597. Our flag length is 344 bits. F(x).small_roots(X=2^400,epsilon= 1/40,beta = 4/7) is enough to extract the small root m.