# Author: Carl Löndahl

# Polictf 2017 – Lucky Consecutive Guessing

This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem to . This problem is quite easy to solve.

The basic idea is to view the problem as the latter and correct the discrepancies (). So, for instance, if we sample

then these values contain the implicit discrepancies. By performing correction of the values (subtracting from the corresponding we obtain a corrected value).

So, now we can use LLL to solve the simpler problem. Once a solution is found, we use the discrepancies to correct it to the case .

import random class LinearCongruentialGenerator: def __init__(self, a, b, nbits): self.a = a self.b = b self.nbits = nbits self.state = random.randint(0, 1 << nbits) def nextint(self): self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) return self.state >> (self.nbits - 32) def break_lcg(a,b,p,i,j,outputs): deltas = [b % p, (a*b + b) % p, (a^2*b + a*b + b) % p, (a^3*b + a^2*b + a*b + b) % p] Y = [((val << (i - j)) ) for val, delta in zip(outputs, deltas)] L = matrix([ [ p, 0, 0, 0 ], [a^1, -1, 0, 0 ], [a^2, 0, -1, 0 ], [a^3, 0, 0, -1] ]) B = L.LLL() Y = vector([x - y for x, y in zip(Y, deltas)]) target = vector([ round(RR(w) / p) * p - w for w in B * vector(Y) ]) states = list(B.solve_right(target)) return [x + y + z for x, y, z in zip(Y, states, deltas)] # parameters p = 2^85 a = 0x66e158441b6995 b = 0xb n = 85 r = 32 sequence = [1310585136, 1634517111, 2548394614, 745784911] # break the LCG start_seed = break_lcg(a,b,p,n,r,sequence) # run it to sample required values lcg = LinearCongruentialGenerator(a, b, n) lcg.state = start_seed[0] for i in range(0, 104): print lcg.nextint()

# Generating wallpaper-consistent terminal colors with K-means++

## K-means algorithm

Assume that we have to following image:

We can represent the image in 3D-space as follows:

Suppose that we want to find eight dominant colors in the image. We could create a histogram and take the eight most common values. This would be fine, but often, very similar colors would repeat. Instead, we can try to find eight centroids in the image and find clusters of points beloning to each centroid (say, a point belongs to a centroid if for some radius ). All points not belonging to a centroid will be penalized using some heuristic. This is basically the K-means clustering algorithm.

## Usage

The algorithm can be used to generate set of dominant colors to be used for instance in the terminal. Running the above algorithm on the image, we get

or as list

`['#321331', '#e1a070', '#621d39', '#e05a40', '#9ed8aa', '#8b3860', '#f7d188', '#ab3031']`

with some minor adjustment

{ "color": [ "#ab3031","#621d39","#e05a40","#e1a070","#9ed8aa","#521f50","#8b3860","#f7d188","#ab5a5b","#623b4b","#e08c7b","#e1b99c","#c4d8c8","#715171","#8b5770","#f7e4c0" ], "foreground": "#c5c8c6", "background": "#282a2e" }

In iTerm, it might look like this

This can be achieved using the following code:

#!/usr/bin/env python import sys, os from sklearn.cluster import KMeans from PIL import Image nbrcentroids = 10 # Constant increase in colors beta = 10 # Multplicative factor in background gamma = 0.4 rgb2hex = lambda rgb: '#%s' % ''.join(('%02x' % min(p + beta, 255) for p in rgb)) darken = lambda rgb : (p * gamma for p in rgb) def getcentroids(filename, n=8): img = Image.open(filename) img.thumbnail((100, 100)) # Run K-means algorithm on image kmeans = KMeans(init='k-means++', n_clusters=n) kmeans.fit(list(img.getdata())) # Get centroids from solution rgbs = [map(int, c) for c in kmeans.cluster_centers_] return rgbs def set_colors_gnome(centroids): centroids = sorted(centroids, key=lambda rgb: sum(c**2 for c in rgb)) prefix = 'gsettings set org.pantheon.terminal.settings ' # Set background and foreground os.system(prefix + 'background \"%s\"' % rgb2hex(darken(centroids[0]))) os.system(prefix + 'foreground \"%s\"' % rgb2hex(centroids[-1])) # Set ANSI colors colors = ':'.join(rgb2hex(centroid) for centroid in centroids[1:-1]) os.system(prefix + 'palette \"' + colors + ':' + colors + '\"') def bar(mode): write = sys.stdout.write for i in range(0, nbrcentroids): write('\033[0;3%dmBAR ' % i) write('\n') centroids = getcentroids(sys.argv[1], n=nbrcentroids) set_colors_gnome(centroids) bar(0);

It is on Github too!

# PlaidCTF’17 – Multicast

We are given a challenge which contains a Sage script, which holds the following lines of code

nbits = 1024 e = 5 flag = open("flag.txt").read().strip() assert len(flag) <= 64 m = Integer(int(flag.encode('hex'),16)) out = open("data.txt","w") for i in range(e): while True: p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False) q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False) ni = p*q phi = (p-1)*(q-1) if gcd(phi, e) == 1: break while True: ai = randint(1,ni-1) if gcd(ai, ni) == 1: break bi = randint(1,ni-1) mi = ai*m + bi ci = pow(mi, e, ni) out.write(str(ai)+'\n') out.write(str(bi)+'\n') out.write(str(ci)+'\n') out.write(str(ni)+'\n')

…along with a text file containing the encrypted flag. Let us first parse the file and put in a JSON structure

data = {'n' : [n0, n1, ...], 'a' : [a0, a1, ...], ...}

We see that the flag is encrypted several times, up to affine transformation. If we define a polynomial , this has a root . We could try to find this root using Coppersmith, but it turns out it not possible since the size of is larger than . However, due to a publication by Håstad, we can construct the following:

where

It is easy to construct as

using the Chinese Remainder Theorem. Clearly, also has a root (this is easy to check!). Since is strictly smaller than , the polynomial roots of can be found using Coppersmith!

p = data['n'][0] * data['n'][1] * data['n'][2] * data['n'][3] * data['n'][4] PR. = PolynomialRing(Zmod(p)) f = 0 # compute the target polynomial for i in range(0, 5): q = p / data['n'][i] qinv = inverse_mod(q, data['n'][i]) f = f + q * qinv * ((data['a'][i]*x + data['b'][i])^5 - data['c'][i]) # make f monic f = f * inverse_mod(f[5], p) print f.small_roots(X=2^512, beta=1)[0]

The code outputs the long integer representation of

PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}

# ASIS CTF’17

## F4 Phantom

With F-4 Phantom II, we want to break the encryption! Please help us!!

nc 66.172.27.77 54979

We get a key-generation function, as seen below.

def gen_pubkey(e, p): assert gmpy.is_prime(p) != 0 B = bin(p).strip('0b') k = random.randrange(len(B)) k, l = min(k, len(B) - k), max(k, len(B) - k) assert k != l BB = B[:k] + str(int(B[k]) ^ 1) + B[k+1:l] + str(int(B[l]) ^ 1) + B[l+1:] q = gmpy.next_prime(int(BB, 2)) assert p != q n = p*q key = RSA.construct((long(n), long(e))) pubkey = key.publickey().exportKey("PEM") return n, p, q, pubkey

So, , where . The density of primes (well, asymptotically) is , so we expect to be quite small.

We define . Now, we solve the following equation

Now, we know that the roots should be numerically close to and . So, we may simply call on them and check if they divide . Note that we need to do this for different hypotheses (different ).

import gmpy, base64 from Crypto.PublicKey import RSA def solve(a): a2 = a ** 2/4 L = gmpy.sqrt(a2 + N) # L > a/2 C_1 = gmpy.next_prime(-a/2 + L) if N % C_1 == 0: return C_1 C_2 = gmpy.next_prime(a/2 + L) if N % C_2 == 0: return C_2 return False # just some public key pem_data1 = ''' MIGmMA0GCSqGSIb3DQEBAQUAA4GUADCBkAKBhyW0uQDhy7/eShVn6VQWQisC8sda zl8xJmCe8eEPGNfDVMFgN7Ll4WdRLYE4T8dOvoMb99Cmjhym7Orb/qfP5q/BpTQy 5hr1w5RZVtYMqQ5I+M4qg7E8kkVhGJh/13bNwqEYvV6VNSCK+bgFWVGMelTQam31 Fiq6wsTLbIBCrLie52Cil1584QIEC8rPFw== ''' pub = RSA.importKey(base64.b64decode(pem_data1)) N = pub.n m = (len(bin(N))+1)/2-2 print '[ ] Solving equations...' for mm in range(m, m+3): for j in range(2, m/2+1): k = mm - j l = j retval = solve(2**(k-1) + 2**(l-1)) if retval: q = retval break retval = solve(2**(k-1) - 2**(l-1)) if retval: q = retval break p = N / q print '[+] Found p = {}... and q = {}...'.format(str(p)[:40], str(q)[:40])

λ python solve.py [ ] Solving equations... [+] Found p = 1381282812140256921334162381757305071089... and q = 1381282811302268925712750063033928508701...

Now, it turns out that . We cannot decrypt the message! If we look closely, we see that . Hmm… so, we can decrypt the message . And the message is the flag, which is constant. What if we sample two ciphertexts encrypting the same message but under different keys? Yes… so, basically, we have and . Then, we can combine it using CRT! This is easy!

import gmpy from Crypto.Util.number import long_to_bytes enc1 = 63188108518214820361083256140053967663112132356420859206347143811869148973386950682507343981284848159232100220605963292020722612854139075311063776086523677522160515093598202087755508512714885329251980275085813640578839753523295579661559881983237388178475574713319340090857313275483787001349560782781513895950569634984688753665 q1 = 33452043035349425454164058954054458228134102234436666511159820871022348004023966976017694615018111901825497223286811050478588079083387098695346723120647425399335947 p1 = 33452043035349425454164058954054813129854949698738692548175391185736387867969615080539316436404430573352896343366560167202569408949342999951142479436993639588965567 e1 = 3562731839 enc2 = 162331112890791758781057932826106636167735138703054666826574266304486608255768782351247144197937186145526374008317633308191215438756014724244242639042178681790803086016105986729819920057318114565244866632716401408212076926367974085730803964312385570202673351687846963322223962280999264618753873289802828995706526584379102468 q2 = 1381282812140256921334162381757305071089685391539884775199049048751523002134390007428038278188586333291047282664366863789424963612326970767160301759006158962675449 p2 = 1381282811302268925712750063033928508701820008572424411412024462643800411901779755548441592138469189655615818433739872652769585433967353091413641137354055362924329 e2 = 197840663 d1 = gmpy.invert(e1, p1-1) d2 = gmpy.invert(e2, p2-1) assert(gmpy.gcd(e1, p1-1) == 1) assert(gmpy.gcd(e2, p2-1) == 1) m = (pow(enc1, d1, p1) * p2 * gmpy.invert(p2, p1) + pow(enc2, d2, p2) * p1 * gmpy.invert(p1, p2)) % (p1*p2) print long_to_bytes(m)

…prints:

********** great job! the flag is: ASIS{Still____We_Can_Solve_Bad_F4!}

Alright!

## A fine OTP server

Connect to OTP generator server, and try to find one OTP.

nc 66.172.27.77 35156

We get the code for generating OTPs:

def gen_otps(): template_phrase = 'Welcome, dear customer, the secret passphrase for today is: ' OTP_1 = template_phrase + gen_passphrase(18) OTP_2 = template_phrase + gen_passphrase(18) otp_1 = bytes_to_long(OTP_1) otp_2 = bytes_to_long(OTP_2) nbit, e = 2048, 3 privkey = RSA.generate(nbit, e = e) pubkey = privkey.publickey().exportKey() n = getattr(privkey.key, 'n') r = otp_2 - otp_1 if r < 0: r = -r IMP = n - r**(e**2) if IMP > 0: c_1 = pow(otp_1, e, n) c_2 = pow(otp_2, e, n) return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2

We note that . Because of this, the task is really trivial. We can simply compute the cubic root without taking any modulus into consideration. can solve this efficiently! This gives us:

ASIS{0f4ae19fefbb44b37f9012b561698d19}

## Secured OTP server

Connect to OTP generator server, and try to find one OTP.

This is secure than first server 🙂nc 66.172.33.77 12431

This is almost identical to the previous, but the OTP is chosen such that it will overflow the modulus when cubed.

template_phrase = '*************** Welcome, dear customer, the secret passphrase for today is: ' A = bytes_to_long(template_phrase + '00' * 18)

Note that we can write an OTP as , where . So, we have . The observant reader have noticed that if we remove , it will not wrap around . Now, we can mod out the terms containing , i.e., find . Now we are back in the scenario of previous challenge… so, we can use the method from before! Hence, . Finally, we get

ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter’s_attack_CongratZ_ZZzZ!_!!!}

## DLP

You should solve a DLP challenge, but how? Of course , you don’t expect us to give you a regular and boring DLP problem!

nc 146.185.143.84 28416

The ciphertext is generated using the following function:

def encrypt(nbit, msg): msg = bytes_to_long(msg) p = getPrime(nbit) q = getPrime(nbit) n = p*q s = getPrime(4) enc = pow(n+1, msg, n**(s+1)) return n, enc

We have that . We can write this as . Now, we can eliminate the ordo term by taking . Assuming that , we can determine by simple division. So, . In Python, we have that

Turns out this is the case, and, hence, we obtain

ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

## unsecure ASIS sub-d

ASIS has many insecure sub-domains, but we think they are over HTTPS and attackers can’t leak the private data, what do you think?

So, we get a PCAP. The first thing we do is to extract data `binwalk -e a.pcap`

. This generates a folder with all the certificates used.

Then, we look at the moduli.

#!/bin/bash FILES=*.crt for f in $FILES do openssl x509 -inform der -in $f -noout -text -modulus done

This generates a file with all moduli. Let us try something simple! Common moduli! For each pair, we check if . If so, we have found a factor. Turns out two moduli have a common factor, so we can factor each of them and decrypt their traffic:

p1 = 146249784329547545035308340930254364245288876297216562424333141770088412298746469906286182066615379476873056564980833858661100965014105001127214232254190717336849507023311015581633824409415804327604469563409224081177802788427063672849867055266789932844073948974256061777120104371422363305077674127139401263621 q1 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791 p2 = 159072931658024851342797833315280546154939430450467231353206540935062751955081790412036356161220775514065486129401808837362613958280183385111112210138741783544387138997362535026057272682680165251507521692992632284864412443528183142162915484975972665950649788745756668511286191684172614506875951907023988325767 q2 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791

We can now generate two PEM-keys

d1 = gmpy.invert(e, (p1 - 1)*(q1 - 1)) key = RSA.construct((long(p1*q1), long(e), long(d1))) f = open('privkey.pem','w') f.write(key.exportKey('PEM')) f.close()

Putting it into Wireshark, we obtain two images:

I totally agree.

## Alice, Bob and Rob

We have developed a miniature of a crypto-system. Can you break it?

We only want to break it, don’t get so hard on our system!

This is McElice PKC. The ciphertexts are generated by splitting each byte in blocks of four bits. The following matrix is used as public key:

The ciphertext is generated as , which is a function from 4 bits to a byte. is an error (or pertubation) vector with only one bit set. This defines a map . So, each plaintext byte is two ciphertext bytes.

We can first create a set of codewords

P = numpy.matrix([[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 0, 1, 1, 0, 0],[0, 1, 1, 1, 0, 0, 1, 0]]) image = {} # set of codewords for i in range(0, 2**4): C = (numpy.array([int(b) for b in (bin(i))[2:].zfill(4)]) * P % 2).tolist()[0] image[int(''.join([str(c) for c in C]), 2)] = i

Then, go through each symbol in the ciphertext, flip all possible bits (corresponding to zeroing out ) and perform lookup in the set of codewords (compute the intersection between the Hamming ball of the ciperhext block and ).

f = open('flag.enc','r') out = '' for i in xrange(18730/2): blocks = f.read(2) j = ord(blocks[0]) C1 = 0 C2 = 0 for i in range(0, 8): if j ^ 2**i in image: C1 = image[j ^ 2**i] << 4 j = ord(blocks[1]) for i in range(0, 8): if j ^ 2**i in image: C2 = image[j ^ 2**i] out += chr(C1+C2) f=open('decrypted','w') f.write(out)

Turns out it is a PNG:

# Confidence DS CTF ’17 – Public Key Infrastructure

Log in as admin to get the flag.

nc pki.hackable.software 1337

This was a fun challenge, because it required many steps to complete. The first thing we notice is that MD5 is being used:

def h(x): return int(hashlib.md5(x).hexdigest(), 16) def makeMsg(name, n): return 'MSG = {n: ' + n + ', name: ' + name + '}' def makeK(name, n): return 'K = {n: ' + n + ', name: ' + name + ', secret: ' + SECRET + '}' def sign(name, n): k = h(makeK(name, n)) r = pow(G, k, P) % Q s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q return (r*Q + s)

Naturally, we cannot register as . An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the account. What if we can create a collision in while keeping distinct?

from coll import Collider, md5pad, filter_disallow_binstrings import os def nullpad(payload): return payload + b'\x00' * (64 - len(payload) % 64) def left_randpad(payload): random_string = os.urandom(64) return random_string[:len(payload) % 64] + payload # nullpad the prefix so that it does not interfere # with the two collision blocks prefix = nullpad(b'K = {n: ') suffix = b', name: groci, secret:' collider = Collider() collider.bincat(prefix) collider.safe_diverge() c1, c2 = collider.get_last_coll() collider.bincat(suffix) cols = collider.get_collisions() # here are our collisions! A = next(cols) B = next(cols)

The above code creates a collision such that `k = h(makeK(name, n))`

generates the same value. The problem is that the server does not return the signature, but `str(pow(sign(name, n), 65537, int(n.encode('hex'), 16)))`

.

To get the signature, which is computed as , we need to perform some additional computations. Obviously, we could factor the modulus and compute and then obtain the signature as easy as … but factoring…

The probability that it is smooth enough is not very high. Also, the number is around digits so not a good candidate for msieve or other factoring software… so what then?

Well… what if and both are prime? Then, we can easily recover the signature as ! No need for time-consuming factoring! Embodied in Python, it could look like this:

import hashlib from Crypto.Util.number import isPrime def num2b(i): c = hex(i).strip('L') c = (len(c) % 2) * '0' + c[2:] return c.decode('hex') # get the payloads A = int(A[64:64*3].encode('hex'), 16) B = int(B[64:64*3].encode('hex'), 16) # PURE BRUTEFORCE, NOTHING FANCY HERE! # append the same data to both payload until # they resulting numbers are BOTH prime mul = 2 ** 96 for i in range(1, 2**20, 2): if isPrime(AA + i) and isPrime(BB + i): print AA+i print BB+i break

As an example, we obtain

and

Putting this into action, we might do something like:

def connect(name, n): name_encoded = base64.b64encode(name) n_encoded = base64.b64encode(n) server = remote('pki.hackable.software', 1337) payload = 'register:' + name_encoded + ',' + n_encoded server.send(payload + '\n') return pow(int(server.recvline()), modinv(65537, n1-1), n1) payload1 = nullpad('K = {n: ') + num2b(n1) payload2 = nullpad('K = {n: ') + num2b(n2) name = 'groci' PORT = 1331 assert(h(makeK(name, payload1)) == h(makeK(name, payload2))) assert(h(makeMsg(name, payload1)) != h(makeMsg(name, payload2))) # Get first signature sig = connect(name, payload1) r1, s1 = sig / Q, sig % Q z1 = h(makeMsg(name, payload1)) # Get second signature connect(name, payload2) sig = pow(int(server.recvline()), modinv(65537, n2-1), n2) r2, s2 = sig / Q, sig % Q z2 = h(makeMsg(name, payload2)) # Make sure we got a nonce re-use assert(r1 == r2) # OK, use standard nonce re-use technique... delta = modinv(((s1 - s2) % Q), Q) k = ( ((z1 - z2) % Q) * delta) % Q r_inv = modinv(r1, Q) PRIVATE = (((((s1 * k) % Q) - z1) % Q) * r_inv) % Q # Now that we know the private key, # lets forge/sign the admin account! name = 'admin' n = 'snelhest' k = h(makeK(name, n)) r = pow(G, k, P) % Q s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q sig = r*Q + s # connect and login name_encoded = base64.b64encode(name) n_encoded = base64.b64encode(n) server = remote('pki.hackable.software', 1337) payload = 'login:' + name_encoded + ',' + n_encoded + ',' + base64.b64encode(num2b(sig)) server.send(payload + '\n') print server.recvline()

We obtain the following signatures:

Now, with our forced nonce re-use, we can use standard techniques to obtain the private key and sign our account, which gives the flag

`DrgnS{ThisFlagIsNotInterestingJustPasteItIntoTheScoreboard}`

!

Note to reader: I apologize for the excessive use of memes.

# 0ctf’17 – All crypto tasks

## Integrity

Just a simple scheme.

nc 202.120.7.217 8221

The `encrypt`

function in the scheme takes the username as input. It hashes the username with MD5, appends the name to the hash and encrypts with a secret key , i.e. . Then, the secret becomes . Notably, the first block contains the hash, but encrypted.

Recall how the decryption is defined:

So, what would happen if we input as username? Then, we have encrypted , but we want only . As mentioned before, the hash fits perfectly into a single block. So, by removing the , becomes the new (which has no visible effect on the plaintext anymore!). Then, we have , which is all what we need.

The flag is `flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}`

.

## OTP1

I swear that the safest cryptosystem is used to encrypt the secret!

We start off analyzing the code. Seeing `process(m, k)`

function, we note that this is actually something performed in with the mapping that, for instance, an integer is in binary, which corresponds to a polynomial . The code is doing in .

The `keygen`

function repeatedly calls ` key = process(key, seed)`

. The first value for `key`

is random, but the remaining ones does not. `seed`

remains the same. Define to be the key and the seed. Note that all elements are in . The first stream value is unknown.

So, we can compute the seed and key as and . The individual square roots exist and are unique.

def num2poly(num): poly = R(0) for i, v in enumerate(bin(num)[2:][::-1]): if (int(v)): poly += x ** i return poly def poly2num(poly): bin = ''.join([str(i) for i in poly.list()]) return int(bin[::-1], 2) def gf2num(ele): return ele.polynomial().change_ring(ZZ)(2) P = 0x10000000000000000000000000000000000000000000000000000000000000425L fake_secret1 = "I_am_not_a_secret_so_you_know_me" fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe" secret = str2num(urandom(32)) R = PolynomialRing(GF(2), 'x') x = R.gen() GF2f = GF(2**256, name='a', modulus=num2poly(P)) f = open('ciphertext', 'r') A = GF2f(num2poly(int(f.readline(), 16))) B = GF2f(num2poly(int(f.readline(), 16))) C = GF2f(num2poly(int(f.readline(), 16))) b = GF2f(num2poly(str2num(fake_secret1))) c = GF2f(num2poly(str2num(fake_secret2))) # Retrieve partial key stream using known plaintexts Y = B + b Z = C + c Q = (Z + Y**2) K = (Y + Q).sqrt() print 'flag{%s}' % hex(gf2num(A + K)).decode('hex')

This gives the flag `flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}`

.

## OTP2

Well, maybe the previous one is too simple. So I designed the ultimate one to protect the top secret!

There are some key insights:

- The
`process1(m, k)`

function is basically the same as in previous challenge, but it computes the multiplication with the exception that elements are in this time. We omitt the multiplication symbol from now on. - The
`process2(m, k)`

function might look involved, but all that it does is to compute the matrix multplication between two matrices (with elements in ), i.e., - We start with matrices and .
- Raising to a power yields has a closed form formula: .
- The
`nextrand(rand)`

function takes the integral value of , we call this and computes via a square-and-multiply type algorithm. In python, it would bedef proc2(key): AN = A**gf2num(N) return key*AN+(AN+1)/(A+1)*B

Let us look at the `nextrand(rand)`

function a little more. Let be the random value fed to the function. Once is computed, it returns

Define . Adding this to the above yields

.

So, . Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) to find . And once we have , we also have . Then, all secrets have been revealed!

From the plaintext, we can immediately get the key by XORing the first part of the plaintext with the corresponding part of the ciphertext. This gives .

R = PolynomialRing(GF(2), 'x') x = R.gen() GF2f = GF(2**128, name='a', modulus=num2poly(0x100000000000000000000000000000087)) A = GF2f(num2poly(0xc6a5777f4dc639d7d1a50d6521e79bfd)) B = GF2f(num2poly(0x2e18716441db24baf79ff92393735345)) G1 = GF2f(num2poly(G[1])) G0 = GF2f(num2poly(0x2fe7878d67cdbb206a58dc100ad980ef)) U = B/(A+1) Z = (G1+U)/(G0+U) N = discrete_log(Z, A, K.order()-1)

We can then run the encryption (the default code) with the parameters fixed to obtain the flag `flag{LCG1sN3ver5aFe!!}`

.