Visual cryptography.sagews

Visual cryptography

In order to make sense of some of the things we mentioned in class, it is useful to see them in action on image files; for we, as humans, are quite good at visually detecting patterns in an array of pixels. This "cloud" interface to Sage is somewhat similar to the regular "notebook" one; use SHIFT+ENTER (or the green "Run" button above) to evaluate a cell.

1) First attempt

Here is a picture of Bletchley Park, where modern computing was born as Alan Turing and thousands of cryptananalysists worked on the breaking of the German codes during WWII:

m = LoadImage("bletchley.jpg")
m # displays it

o = LoadImage("ep109.png")
o

Internally, it's just a $288 \times 460$ matrix of pixels, each of which is colored according to a RGB triple of integers between 0 and 255:

m.size()

(288, 460)

m.data

array([[[126, 157, 186], [200, 231, 255], [169, 199, 233], ..., [ 33, 49, 20], [ 83, 98, 59], [ 72, 88, 43]], [[ 94, 125, 154], [145, 176, 207], [143, 173, 207], ..., [128, 143, 114], [ 19, 34, 0], [140, 155, 112]], [[ 28, 59, 90], [ 18, 49, 80], [ 25, 55, 89], ..., [ 47, 62, 33], [ 70, 84, 48], [202, 217, 176]], ..., [[163, 195, 94], [164, 196, 95], [170, 202, 101], ..., [162, 197, 97], [162, 197, 97], [156, 191, 91]], [[168, 200, 99], [166, 198, 97], [173, 205, 104], ..., [152, 187, 87], [154, 189, 89], [152, 187, 87]], [[154, 186, 85], [152, 184, 83], [164, 196, 95], ..., [161, 196, 96], [162, 197, 97], [159, 194, 94]]], dtype=uint8)

Recall that the goal of encryption would be to reversibly make it look like a random image of the same size just like this one:

RandomImage(288,460)

As a single pixel is encoded on $3 \times 8 = 24$ bits, a $4 \times 4$ block of pixels is encoded on $16 \times 24 = 384$ bits, which give us more than enough room to store a secure symmetric encryption key.

k = RandomImage(4,4)
k.data

array([[[ 48, 150, 155], [ 58, 138, 209], [240, 237, 250], [197, 111, 13]], [[254, 58, 213], [ 22, 124, 28], [ 6, 213, 172], [ 2, 235, 41]], [[ 8, 164, 89], [ 15, 64, 31], [ 56, 29, 207], [ 21, 193, 61]], [[148, 18, 91], [243, 249, 120], [115, 113, 106], [ 72, 161, 65]]], dtype=uint8)

Let's derive from it an encryption mask by repeating this small $4 \times 4$ block:

pad = Image(numpy.tile(k.data, (288/4,460/4,1)))
pad

Et voilà! Here's the picture, encrypted by a 384-bit key:

m + pad      # pixel values are xor-ed together

Discuss the result. Would you say that this cipher provides perfect secrecy?

2) One-time pad

Go through the same process, this time with a genuine randomly generated one-time pad. What's the key-length this time? Verify that the cipher decrypts correctly, i.e. play both the roles of Alice and Bob to see that everything works as it should. Also make sure to take a look at what Eve actually sees on the insecure channel.

A défaut de trouver les bonnes méthodes pour trouver le résultat, voilà le raisonnement que j aurais :

On applique le RPGA sur l'image m

on formate bien le résultat pour obtenir une liste de triplets, ici comme l'exemple k d'avant, un bloc de 4x4 pixels composés chacun de 3 composantes (rgb) de valeurs comprises entre 0 et 255

On applique le XOR (pad + m) pour voir le résultat crypte, il suffit alors d'jaouter m pour retoruver pad ou bien d'ajouter pad pour retoruver m

Bob envoie l'image crypté et Alice pour retrouver l'image de base, applique le même filtre pour retrouver l'image de base

Le méchant Eve quant à lui obtient l'image pad + m

k = os.urandom(16)
load("RC4.sage")
prng = RC4(k)
list = []
tmplist = []
for i in range(4):
    for j in range(4):
        tmplist.append([prng.next() for l in range(3)])

    list.append(tmplist)
    tmplist=[]


pad1 = Image(numpy.tile(list, (288/4,460/4,1)))
#the key
pad1

#encrypted message, this is what eve can see and what Alice send to Bob, Bob just need the pas to discover the real message
m+pad

#here example of what we get with double XOR
m+pad1+pad1

3) Two-time pad

Wow, this works well. In the excitation of the moment, I started encrypting all my images... but forgot to apply one of the most important usage rules of the one-time pad when I encrypted the following two images. Can you find out what they were?

img = LoadImage("c1.tiff")
img2 = LoadImage("c2.tiff")


img + img2

4) Random number generator

After realizing my mistake, I decided to generate pads from a 128-bit key by using it as a seed for a linear congruence generator modulo the following 128-bit prime:

︠0a8f6161-d61c-4a59-a4eb-826e1e1fe34d︠

︠a18e9768-7de3-49d6-823c-d6f4a5cb9dd4︠
p = 340282366920938463463374607431768211507

is_prime(p)

True

Since such a PRNG is characterized by two 128-bit integers $a$ and $b$ which were chosen at random, there should be more than enough entropy to protect my 128-bit key, right? Prove me wrong by finding out what the seed used to produce the first few outputs from the LCG was:

217692597915196650809181220736554072509,

101697276836279744146238049998237762682,

265181937610212296333751058245677871006,

84171444745593992579687306707926595136,

12455596861516498286468598807461112654,

...

Ici on calcule les deux premiers termes Y1 et Y2 qui valent X1-X0 et X2-X1, ensuite on sait que a = Y2*(Y1^-1), enfin b vaut (X1-a*X0)%p

Cependant je n'arrive pas à savoir où se toruve mon problème de syntaxe

Y1 = 101697276836279744146238049998237762682 - 217692597915196650809181220736554072509
Y2 = 2651819376,10212296333751058245677871006 - 101697276836279744146238049998237762682

a = xgcd(Y2,p)
b = ((101697276836279744146238049998237762682 - a*217692597915196650809181220736554072509)%p)

Error in lines 3-3 Traceback (most recent call last): File "/projects/adb30046-5db7-4cd9-8624-c3fe46409858/.sagemathcloud/sage_server.py", line 828, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/usr/local/sage/sage-6.3.beta6/local/lib/python2.7/site-packages/sage/rings/arith.py", line 1916, in xgcd a = ZZ(a) File "parent.pyx", line 1089, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:8902) File "coerce_maps.pyx", line 95, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4203) File "coerce_maps.pyx", line 90, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4110) File "integer.pyx", line 750, in sage.rings.integer.Integer.__init__ (build/cythonized/sage/rings/integer.c:8283) TypeError: unable to coerce <type 'tuple'> to an integer

5) Genuine stream cipher

Ok, now it's time to start doing things properly. We will use the still-standard-albeit-somewhat-deprecated RC4 pseudo-random number generator to generate a key-stream from a 128-bit key.

5) Genuine stream cipher

Ok, now it's time to start doing things properly. We will use the still-standard-albeit-somewhat-deprecated RC4 pseudo-random number generator to generate a key-stream from a 128-bit key. We first aquire 128 bits of "real" random data from the entropy pool of the system.

k = os.urandom(16)      # 16 bytes of entropy coming from /dev/urandom
k.encode('hex')

'2dda36246c779acd0a9a6eb3b9754bea'

k

'-\xda6$lw\x9a\xcd\n\x9an\xb3\xb9uK\xea'

An implementation of the RC4 PRNG is provided. Once initialized with the seed $k$, every invokation of prng.next() will return a new pseudo-random byte derived from $k$.

load("RC4.sage")
prng = RC4(k)

list = [prng.next() for i in range(16) ]

list

[153, 15, 226, 151, 139, 96, 147, 107, 124, 188, 9, 223, 168, 239, 136, 69]

prng.next()

181

Use this to generate of pseudo-random pad from $k$, and then encrypt the Bletchley Park picture with it. Make sure that Bob will be able to decrypt it knowing only $k$.