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 
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!
, 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:
as![\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}](https://s0.wp.com/latex.php?latex=%5Cphi_i+%3D+%5Cfrac%7B1%7D%7BN_i%7D%5Ccdot+%5Cprod_k+N_k+%5Ccdot+%5B%5Cprod_k+N_k+%2F+N_i%5D%5E%7B-1%7D_%7BN_i%7D&bg=ffffff&fg=000000&s=0 "\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}")
also has a root 
(this is easy to check!). Since 
is strictly smaller than 
, the polynomial roots of 
, where 
. The density of primes (well, asymptotically) is 
, so we expect 
to be quite small.
. Now, we solve the following equation
. So, we may simply call 
on them and check if they divide 
. Note that we need to do this for different hypotheses (different 
).
. 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!
. 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:
, where 
. So, we have 
. The observant reader have noticed that if we remove 
, it will not wrap around 
, 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
. 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
. 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:
, 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.
(compute the intersection between the Hamming ball of the ciperhext block and 
. An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the 
while keeping 
distinct?
, 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…
digits so not a good candidate for msieve or other factoring software… so what then? 
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:
. Then, the secret becomes 
. Notably, the first block 
contains the hash, but encrypted.
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 
, 
, which is all what we need.![\mathbb F_2[x]/P(x)](https://s0.wp.com/latex.php?latex=%5Cmathbb+F_2%5Bx%5D%2FP%28x%29&bg=ffffff&fg=000000&s=0 "\mathbb F_2[x]/P(x)")
with the mapping that, for instance, an integer 
is 
in binary, which corresponds to a polynomial 
. The code is doing 
in 
.
to be the key and 
the seed. Note that all elements are in 
is unknown.
and 
. The individual square roots exist and are unique.
with the exception that elements are in 
this time. We omitt the multiplication symbol from now on.
matrices (with elements in 
and 
.
.
via a square-and-multiply type algorithm. In python, it would be
is computed, it returns
. Adding this to the above yields
.
. Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) 
to find 
.
fixed to obtain the flag 
. Let us reorder the function as follows:
, since we can control 
. Equivalently, we can encrypt for different values of 
, where the trailing six bits will be the trailing six bits of 
.
time and space. This is done by putting about 
values of the encryption (or decryption) in a table. Then, we generate the decryptions (or encryptions, respectively) and look in the table.
. 
, 
. (This is not true, thanks to hellman for pointing that out in the comments).
. Having a look at the Wikipedia page, I found that this is how AES-CFB/(CBC) would behave (image from Wikipedia):
, we can inject some data into the decrypted ciphertext! Assume that we want 
. Then, we can set 
, since then 
. Embodying the above in Python, we might get something like