## Basic LLL

> Simple crypto is the best crypto.
>
> Author: S1mple
>

basic-lll.sage

def generate():
    p = random_prime(2^1024, lbound=2^1023)
    x=randint(1,2^16)
    y=randint(1,2^256)
    a=randint(2^1023,2^1024)
    q=random_prime(2^1024)
    n=p*q
    return x,a,y,n,p

x,a,y,n,p = generate()
k = x * y + a * p
e=65537
print(f"x = {x}")
print(f"a = {a}")
print(f"n = {n}")
print(f"k = {k}")

m = b'L3AK{<Redacted>}'
flag = int.from_bytes(m, byteorder='big')
c= pow(flag, e, n)
print(f"c = {c}")


'''
x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
'''

* We can solve this challenge without using LLL just by simple mathematics.
* We have:
$$
\begin{aligned}
&x \in {(1, 2^{16})},\ y \in {(1, 2^{256})} \Leftrightarrow
xy \in (1, 2^{272}) \\
& while\ a \in (2^{1023}, 2^{1024}) \\
\Leftrightarrow \ &\frac{xy}{a} < \frac{2^{272}}{2^{1024}} < 1 \Leftrightarrow \left\lfloor \frac{xy}{a} \right\rfloor = 0
\end{aligned}
$$

* From the problem, we have:
$$
\begin{aligned}
&k = xy \ +ap \\
\Leftrightarrow \ &\frac{k}{a} = \frac{xy}{a} + p \ (k,\ a, \ x, \ y \in \mathbb{N}) \\
\Leftrightarrow \ &\left\lfloor \frac{k}{a} \right\rfloor = \left\lfloor \frac{xy}{a} \right\rfloor + p \\
\Leftrightarrow \ &p = \left\lfloor \frac{k}{a} \right\rfloor
\end{aligned}
$$

* Then we can decrypt the message
Code:

from Crypto.Util.number import long_to_bytes

k = ...
a = ...
n = ...
c = ...
e = ...

p = k // a
q = n // p
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))
Flag: L3AK{u_4ctu4lly_pwn3d_LLL_w1th_sh0rt_v3ct0rs_n1c3}

## Lowkey RSA

M = matrix([[x,1,0,0], [a,0,1,0], [-k,0,0,1]])
a = M.LLL()
for i in a:
    if i[-1] == 1:
        y = i[1] 
        p = i[2] 
q = n // p
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = m.to_bytes((m.bit_length() + 7) // 8, byteorder='big')
print(f"flag = {flag.decode()}")

> This RSA might lowkey be insecure, no cap fr fr.
>
> Authors: Black, White, Suvoni

lowkey-rsa.py

from Crypto.Util.number import *

def gen_primes(SIZE):
    p = random_prime(1 << (SIZE - 1), 1 << SIZE)
    while True:
        q = random_prime(1 << (SIZE - 1), 1 << SIZE)
        if p < q: 
            p, q = q, p
            if q < p < 2*q:
                break
    return p, q

nbits = 1024
flag = b"L3AK{<REDACTED>}"

R = RealField(nbits)
p, q = gen_primes(nbits//2)
N = p*q
phi = (p**4-1)*(q**4-1)
N_s = R(N**2)
N_ss = R(N**4)   
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)

while True:
    d = randint(1, round(sqrt(t)) - 1)
    if gcd(phi-d, phi) == 1:
        break

e = inverse_mod(phi-d, phi)
c = pow(bytes_to_long(flag), e, N)
print(f"e = {e}\nN = {N}\nc = {c}")

'''
e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996
'''

* We notice that phi is kinda sus ~ $N^4$, I applied the Wiener's Attack
Code:

from sage.all import *
from Crypto.Util.number import *

def wiener(c, e, n, N):
    # Convert e/n into a continued fraction
    cf = continued_fraction(QQ(e)/QQ(n))
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()

        try:
            if (e * d + 1) % k == 0:
                m = int(pow(c, -d, N))
                temp = long_to_bytes(m)
                if b'L3AK' in temp:
                    print(temp)
        except Exception:
            continue

e = ...
c = ...
N = ...
wiener(c, e, N**4, N)

## Shiro Hero
Welp I managed to find the flag after the contest ended.

ecc.py

#!/usr/bin/env python3
import random
from hashlib import sha3_256, sha256
from Crypto.Util.number import bytes_to_long, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad, pad
from prng import xorshiro256, MASK64     
import hashlib
import os

class ECDSA:
    """ECDSA implementation for secp256k1 curve"""
    # parameters
    p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    a  = 0
    b  = 7
    Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
    Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
    n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
    G  = (Gx, Gy)

    @staticmethod   
    def digest(msg: bytes) -> int:
        """Hash a message and return as integer"""
        return bytes_to_long(sha256(msg).digest())

    @staticmethod
    def point_add(P, Q):
        """Add two points on the elliptic curve"""
        if P == (None, None): 
            return Q
        if Q == (None, None): 
            return P
        (x1, y1), (x2, y2) = P, Q
        if x1 == x2 and (y1 + y2) % ECDSA.p == 0: return (None, None)
        if P == Q:
            l = (3 * x1 * x1) * inverse(2 * y1, ECDSA.p) % ECDSA.p
        else:
            l = (y2 - y1) * inverse(x2 - x1, ECDSA.p) % ECDSA.p
        x3 = (l * l - x1 - x2) % ECDSA.p
        y3 = (l * (x1 - x3) - y1) % ECDSA.p
        return (x3, y3)

    @staticmethod
    def scalar_mult(k, P):
        R = (None, None)
        while k:
            if k & 1: R = ECDSA.point_add(R, P)
            P = ECDSA.point_add(P, P)
            k >>= 1
        return R

    @staticmethod
    def gen_keypair():
        d = random.randint(1, ECDSA.n - 1)         
        Q = ECDSA.scalar_mult(d, ECDSA.G)          
        return d, Q                                 

    @staticmethod
    def ecdsa_sign(h: int, d: int, prng: xorshiro256):
        while True:
            k = prng() % ECDSA.n
            if not k:
                continue
            x, _ = ECDSA.scalar_mult(k, ECDSA.G)
            if x is None:  
                continue
            r = x % ECDSA.n
            if not r:
                continue
            s = (inverse(k, ECDSA.n) * (h + r * d)) % ECDSA.n
            if s:
                return r, s

    @staticmethod
    def ecdsa_verify(h, Q, sig):
        r, s = sig
        if not (1 <= r < ECDSA.n and 1 <= s < ECDSA.n):
            return False
        w  = inverse(s, ECDSA.n)
        u1 = (h * w) % ECDSA.n
        u2 = (r * w) % ECDSA.n
        x, _ = ECDSA.point_add(ECDSA.scalar_mult(u1, ECDSA.G), ECDSA.scalar_mult(u2, Q))
        if x is None:  
            return False
        return (x % ECDSA.n) == r

prng.py

#!/usr/bin/python3
from Crypto.Util.number import bytes_to_long, inverse
MASK64 = (1 << 64) - 1                    

def _rotl(x: int, k: int) -> int:
    return ((x << k) | (x >> (64 - k))) & MASK64

class xorshiro256:
    
    def __init__(self, seed):
        if len(seed) != 4:
            raise ValueError("seed must have four 64-bit words")
        self.s = [w & MASK64 for w in seed]


    @staticmethod
    def _temper(s1: int) -> int:
        return (_rotl((s1 * 5) & MASK64, 7) * 9) & MASK64


    def next_raw(self) -> int:
        s0, s1, s2, s3 = self.s
        t = (s1 << 17) & MASK64

        s2 ^= s0
        s3 ^= s1
        s1 ^= s2
        s0 ^= s3            
        s2 ^= t
        s3  = _rotl(s3, 45)

        self.s = [s0, s1, s2, s3]
        return s1          
    
    def randrange(self, start, stop, inclusive=False):
        if inclusive:
            return start + self.next_raw() % (stop - start + 1)
        return start + self.next_raw() % (stop - start)

    def __call__(self) -> int:
        return self._temper(self.next_raw())

chal.py

from secrets import randbits
from prng import xorshiro256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecc import ECDSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
import hashlib
flag = open("flag.txt", "rb").read()
state = [randbits(64) for _ in range(4)]
prng = xorshiro256(state)
leaks = [prng.next_raw() for _ in range(4)]
print(f"PRNG leaks: {[hex(x) for x in leaks]}")
Apriv, Apub = ECDSA.gen_keypair()
print(f"public_key = {Apub}")
msg = b"My favorite number is 0x69. I'm a hero in your mother's bedroom, I'm a hero in your father's eyes. What am I?"
H = bytes_to_long(msg)
sig = ECDSA.ecdsa_sign(H, Apriv, prng)                  
print(f"Message = {msg}")
print(f"Hash = {H}")
print(f"r, s = {sig}")
key = hashlib.sha256(long_to_bytes(Apriv)).digest()
iv = randbits(128).to_bytes(16, "big")
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = iv.hex() + cipher.encrypt(pad(flag, 16)).hex()
print(f"ciphertext = {ciphertext}")
with open("output.txt", "w") as f:
    f.write(f"PRNG leaks: {[hex(x) for x in leaks]}\n")
    f.write(f"public_key = {Apub}\n")
    f.write(f"Message = {msg}\n")
    f.write(f"Hash = {H}\n")
    f.write(f"r, s = {sig}\n")
    f.write(f"ciphertext = {ciphertext}\n")

* The code is kinda long but let's go through one-by-one, but in the first place, there is an important functions we need to know.
**prng.next_raw()**: This function will "swap" and do many things with the seed (in this problem is **state**), then return **state[1]**
## The flow of the problem
can be divided into two phrases:
1. Create leaks
* We started off with **state** - an array containing 4 int 64 bits. Then **state** go through 4 loops of **next_raw** to create new array **leaks** (and our mission is to recover **state** from **leaks**).
* The following loop use the previous state of **state**

2. Encrypt
* The code generate public and private key, although public key is not gonna do anything. Private key, however, is thrown into signature, with some operation, but the most important two are
$$
\begin{aligned}
&k = prng() \mod(ECDSA.n) \\
&s = k^{-1}(H + rd) \mod(ECDSA.n)
\end{aligned}
$$
this will be the clue to retrieve the private key
**_temper**: Do something with the input (in this problem is s1)
**prng()**: Perform **_temper(next_raw)**, the **next_raw** in here corresponds to loop 5

## Solution
can be divided also into two phrases:
1. Recover **state**
* I used z3 library, which will solve the equation related to bits, then I retrieve the initial **state**
2. Find key
* Once get initial **state**, I perform for loop 5 times and get **state[1]** (which i circle with red pen) this means
$$
\begin{aligned}
&k = \_temper(state[1]) \mod(ECDSA.n) \\
\Leftrightarrow \ &d = \frac{sk - H}{r} \mod(ECDSA.n)
\end{aligned}
$$

Code:

from z3 import BitVec, Solver, RotateLeft, BitVecVal, sat
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

# for bitvec type
def z3_rotl(x, k):
    return RotateLeft(x, k)

def prng_step_z3(s0, s1, s2, s3):
    t = (s1 << 17) & MASK64
    s2 ^= s0
    s3 ^= s1
    s1 ^= s2
    s0 ^= s3
    s2 ^= t
    s3 = z3_rotl(s3, 45)
    return s0 & MASK64, s1 & MASK64, s2 & MASK64, s3 & MASK64

# for int type
def _rotl(x: int, k: int) -> int:
    return ((x << k) | (x >> (64 - k))) & MASK64

def next_raw(state) -> int:
    s0, s1, s2, s3 = state
    t = (s1 << 17) & MASK64
    s2 ^= s0
    s3 ^= s1
    s1 ^= s2
    s0 ^= s3            
    s2 ^= t
    s3  = _rotl(s3, 45)
    state = (s0, s1, s2, s3)
    return state, s1

def _temper(s1: int) -> int:
    return (_rotl((s1 * 5) & MASK64, 7) * 9) & MASK64

def decrypt(ciphertext: bytes, key: bytes, iv) -> bytes:
    cipher = AES.new(key, AES.MODE_CBC, iv)
    return cipher.decrypt(ciphertext)

# 1. Find state using Z3
s0, s1, s2, s3 = [BitVec(f's{i}', 64) for i in range(4)]
solver = Solver()
state = (s0, s1, s2, s3)
for i in range(4):
    state = prng_step_z3(*state)
    solver.add(state[1] == BitVecVal(int(leaks[i], 16), 64))
assert solver.check() == sat, "No solution?"
m = solver.model()
initial_state = [m.eval(v).as_long() for v in [s0, s1, s2, s3]]

# 2. Find key
# 2.1 Find k        
for i in range(5):
    initial_state, s1 = next_raw(initial_state)
    print(f"step {i}: s1 = {hex(s1)}")

k = _temper(s1) % n

# 2.2 Find d
d = ((s * k - H) * pow(r, -1, n)) % n
key = hashlib.sha256(long_to_bytes(d)).digest()

# 2.3 Decrypt the ciphertext
flag = decrypt(ct, key, iv)
flag = unpad(flag, 16)
print(flag)