> For the complete documentation index, see [llms.txt](https://kos0ng.gitbook.io/ctfs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kos0ng.gitbook.io/ctfs/write-up/2023/bsides-indore/cryptography.md).

# Cryptography

| Challenge                         | Link                                  |
| --------------------------------- | ------------------------------------- |
| My\_beloved\_LCG.py (3 solves) 🥈 | [Here](#my_beloved_lcg.py-495-points) |

## My\_beloved\_LCG.py (3 solves)

### Description

Given challenge as below

```python
from Crypto.Util.number import long_to_bytes ,getPrime
from random import randint,shuffle
import json
# from banner import banner

class LCG:
    def __init__(self,m, seed):
        self.a = randint(1,m)
        self.b = randint(1,m)
        self.m = m
        self.state = seed
        self.refresh()

    def refresh(self):
        self.state = (self.get_random_bits()*self.get_random_bits())%self.m

    def next_state(self):
        self.state = (self.a * self.state + self.b) % self.m

    def get_random_bits(self):
        self.next_state()
        return (self.state)>>100

    def encrypt(self,msg):
        tmp = self.get_random_bits()
        return long_to_bytes(tmp^int(msg,16)).hex()

banner()

m=8232312959811687665793375850697161475128245885498087244865661043365300427355910967177802992671927606112967162365226385902985055038600150891334303906988843
seed=randint(1,m)
L=LCG(m,seed)
FLAG=open("flag.txt",'rb').read()

for i in range(50):
    try:
        choice=json.loads(input("give a message to encrypt\n"))

        if("option" not in choice):
            print("give me an option")
        else:

            if(choice["option"]=="parameters"):
                print(json.dumps({"M":L.m,"a":L.a,"b":L.b}))
                continue

            if(choice["option"]=="get_flag"):
                print(json.dumps({"enc_flag":L.encrypt(FLAG.hex())}))
                continue

            if choice["option"]=="encrypt" and "msgs" in choice:
                msgs=choice["msgs"]
                if(len(msgs)==20):
                    encyrpted_msgs=[]
                    for i in msgs:
                        encyrpted_msgs.append(L.encrypt(i)) 
                    shuffle(encyrpted_msgs) # swix :)

                    print(json.dumps({"encrypted_msgs":encyrpted_msgs}))
                else:
                    print("give me 64 msgs to encrypt")
                continue

            print("give a valid option")

    except:
        # print("dont try something stupid")
        exit()
```

### Solution

The idea is cracking partial lcg value with minimum known value because there is 20 values generated and shuffled. In this case i can crack lcg using two latest values generated. Here is solver i used during competition

```python
from sage.all import QQ
from sage.all import ZZ
from sage.all import matrix
from sage.all import vector
from pwn import *
import json
from Crypto.Util.number import *
from itertools import permutations

class LCG:
    def __init__(self, seed, a, c, m):
        self.seed = seed
        self.a = a
        self.c = c
        self.m = m

    def next(self):
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

def attack(y, k, s, m, a, c):
    """
    Recovers the states associated with the outputs from a truncated linear congruential generator.
    More information: Frieze, A. et al., "Reconstructing Truncated Integer Variables Satisfying Linear Congruences"
    :param y: the sequential output values obtained from the truncated LCG (the states truncated to s most significant bits)
    :param k: the bit length of the states
    :param s: the bit length of the outputs
    :param m: the modulus of the LCG
    :param a: the multiplier of the LCG
    :param c: the increment of the LCG
    :return: a list containing the states associated with the provided outputs
    """
    diff_bit_length = k - s

    # Preparing for the lattice reduction.
    delta = c % m
    y = vector(ZZ, y)
    for i in range(len(y)):
        # Shift output value to the MSBs and remove the increment.
        y[i] = (y[i] << diff_bit_length) - delta
        delta = (a * delta + c) % m

    # This lattice only works for increment = 0.
    B = matrix(ZZ, len(y), len(y))
    B[0, 0] = m
    for i in range(1, len(y)):
        B[i, 0] = a ** i
        B[i, i] = -1

    B = B.LLL()

    # Finding the target value to solve the equation for the states.
    b = B * y
    for i in range(len(b)):
        b[i] = round(QQ(b[i]) / m) * m - b[i]

    # Recovering the states
    delta = c % m
    x = list(B.solve_right(b))
    for i, state in enumerate(x):
        # Adding the MSBs and the increment back again.
        x[i] = int(y[i] + state + delta)
        delta = (a * delta + c) % m

    return x

def get_param():
	payload = {"option" : "parameters"}
	r.recvuntil(b"to encrypt")
	r.sendline(json.dumps(payload).encode())
	r.recvline()
	return json.loads(r.recvline().strip().decode())

def get_flag():
	payload = {"option" : "get_flag"}
	r.recvuntil(b"to encrypt")
	r.sendline(json.dumps(payload).encode())
	r.recvline()
	return json.loads(r.recvline().strip().decode())

def encrypt(payload):
	payload = {"option" : "encrypt", "msgs" : payload}
	r.recvuntil(b"to encrypt")
	r.sendline(json.dumps(payload).encode())
	r.recvline()
	return json.loads(r.recvline().strip().decode())

def solve(arr, m, a, c, ct):
	for bit_length in range(411,413):
		res = attack(arr, m.bit_length(), bit_length, m, a, c)
		lcg = LCG(int(res[-1]),a,c,m)
		pt = (lcg.next()>>100) ^^ ct
		pt = long_to_bytes(pt)
		if(b"BSidesIndore" in pt): 
			print(arr, bit_length, pt)

# r = process(["python3","My_beloved_LCG.py"])
r = remote("34.30.232.46", int(1111))
resp = get_param()
m = resp['M']
a = resp['a']
c = resp['b']

data = encrypt("A"*20)
print(data)
arr = []
for i in data['encrypted_msgs']:
	arr.append(bytes_to_long(bytes.fromhex(i))^^10)
ct = bytes_to_long(bytes.fromhex(get_flag()['enc_flag']))
r.close()

for i in permutations(arr, int(2)):
	tmp = list(i)
	# print(tmp)
	solve(tmp, m, a, c, ct)
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://kos0ng.gitbook.io/ctfs/write-up/2023/bsides-indore/cryptography.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.