Cryptography & Data Security - Comp 547

Assignment 3
Maxime CHAMBREUIL
maxime.chambreuil@mail.mcgill.ca

Contents
1 Exercises from Stinson’s book 1
1.1 Latin Square Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Ciphertext equally probable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Entropy calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Vigenere cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Visual One-Time Pad 3

2.1 Superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Blum-Blum and Shub generator 3

3.1 Distinguishing the Blum Blum and Shub generator . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1 Exercises from Stinson’s book

1.1 Latin Square Cryptosystem
A cryptosystem has a perfect secrecy if

∀p ∈ P, c ∈ C, P rP,C (p/c) = P rP (p)

P r(p).P r(c/p)
∀p ∈ P, c ∈ C, P rP,C (p/c) =
P r(c)
Each key is used with equal probability, so knowing j, there is only one key that encrypt j to
a L(i,j) among the n keys (Each number appears once in a column). Concerning P r(c), each L(i,j)
appears n times in the square among the n2 possible cases.

P r(p). n1
P r(p/c) = n = P r(p)
n2

In conclusion, the Latin Square Cryptosystem achieves perfect secrecy provided that every key
is used with equal probability.

October 26, 2003 http://www.maxime-chambreuil.fr.st 1

 Cryptography & Data Security - Comp 547

1.2 Ciphertext equally probable

If the cryptosystm has perfect secrecy, then we have :

∀p ∈ P, c ∈ C, P rP,C (p/c) = P rP (p)

So, we can deduce with the Bayes Theorem that :

P r(p).P r(c/p) P r(p).P r(c/p)

∀c ∈ C, P r(c) = = = P r(c/p)
P r(p/c) P r(p)
As |P | = |C| = |K|, we know that there is only one key among n that encrypts p to c. So

1
∀c ∈ C, P r(c/p) =
n
We can conclude that every ciphertext is equally probable.

1.3 Entropy calculi

H[P ] = −P r(p = a)lgP r(p = a) − P r(p = b)lgP r(p = b) − P r(p = c)lgP r(p = c)
1 1 1 1 1 1
= − lg − lg − lg
2 2 3 3 6 6
= 1, 4591
H[K] = −P r(k = K1 )lgP r(k = K1 ) − P r(k = K2 )lgP r(k = K2 ) − P r(k = K3 )lgP r(k = K3 )
1 1 1 1 1 1
= − lg − lg − lg
3 3 3 3 3 3
= 1, 5850
H[C] = −P r(c = 1)lgP r(c = 1) − P r(c = 2)lgP r(c = 2) − P r(c = 3)lgP r(c = 3) − P r(c = 4)lgP r(c = 4)
2 2 2 2 1 1 2 2
= − lg − lg − lg − lg
9 9 9 9 3 3 9 9
= 1, 9749
H[K/C] = P r(c = 1)H[K/c = 1] + P r(c = 2)H[K/c = 2] + P r(c = 3)H[K/c = 3] + P r(c = 4)H[K/c = 4]
2
= [−P r(K = K1 /c = 1)lgP r(K = K1 /c = 1) − P r(K = K2 /c = 1)lgP r(K = K2 /c = 1)
9
−P r(K = K3 /c = 1)lgP r(K = K3 /c = 1)] + · · ·
2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
= [− lg − 0lg0 − lg ] + [− lg − lg − 0lg0] + [− lg − lg − lg ] + · · ·
9 2 2 2 2 9 2 2 2 2 3 3 3 3 3 3 3
= 1, 1950
H[P/C] = P r(c = 1)H[P/c = 1] + P r(c = 2)H[P/c = 2] + P r(c = 3)H[P/c = 3] + P r(c = 4)H[P/c = 4]
2
= [−P r(P = a/c = 1)lgP r(P = a/c = 1) − P r(P = b/c = 1)lgP r(P = b/c = 1)
9
−P r(P = c/c = 1)lgP r(P = c/c = 1)] + · · ·
2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
= [− lg − 0lg0 − lg ] + [− lg − lg − 0lg0] + [− lg − lg − lg ] + · · ·
9 2 2 2 2 9 2 2 2 2 3 3 3 3 3 3 3
= 1, 1950

1.4 Vigenere cipher

We know that:

lg|K|
n≥
RL .lg|P |

October 26, 2003 http://www.maxime-chambreuil.fr.st 2

 Cryptography & Data Security - Comp 547

In our case:

lg|K| lg(26)m 1
= =
RL .lg|P | RL .lg(26)m RL
1
So we can conclude that unicity distance for a vigenere cipher is RL .

2 Visual One-Time Pad

2.1 Superposition
In a message, let us consider a pixel which can be black or white (1 or 0). We can construct the
following truth tables:

M K M⊕K=c C K C ∨ K = M’ M M’
0 0 0 0 0 0 0 0
1 0 1 1 0 1 ⇒ 1 1
0 1 1 1 1 1 0 1
1 1 0 0 1 1 1 1

M and M’ are pretty much the same, instead of having a white background, we have a black
one though. Therefore we can distinguish the message M.

2.2 Redundancy
When we consider a letter, we can admit that it is represented inside a rectangle of approxi-
mately 20 × 20 pixels, so one letter of our alphabet is encoded on 400 bits. In fact we only need
5 bits for our 26 letters, so we have 400 - 5 = 395 useless bits. This amount of redundancy in the
message allows Oscar to find it and break the cryptosystem.

If there is no redundancy in the plaintext, there is no chance for Oscar to retrieve the message.
In our example, a letter would be represented by 5 pixels, so it is not enough to find out which
letter is behind those pixels.

3 Blum-Blum and Shub generator

3.1 Distinguishing the Blum Blum and Shub generator
Knowing the algorithm of the generator, I will first take N = 1 and check if the second block of
N bits is the square of the first block mod N. If it is not the case, I will increment N, until I find N
(or N hit half the length of the string).

Knowing N, I would generate all the keystream and compare it with the output of the Blum
Blum and Shub generator to be sure that’s the right N. If they match, the string has been generated
with the Blum-Blum and Shub Generator. If they do not match, I increment N and I look for
another N, until I hit half the length of the original string.

3.2 Maple
isBBSG := proc(string)

local lg,M,N,tmp,Next,generated,s,i;
lg := length(string):

October 26, 2003 http://www.maxime-chambreuil.fr.st 3

 Cryptography & Data Security - Comp 547

M := 2;

# Loop on N that match s = sˆ2 mod N, but does not generate the right string
while (M < 1+(lg/2)) do:

N:=M:
tmp := convert(string[1..N],decimal,10):
Next := convert(string[N+1..2*N],decimal,10):

# Look for an N that match the formulae

while ((not (tmpˆ2=Next mod N)) and N < 1+(lg/2) ) do:

N := N+1:
tmp := convert(string[1..N],decimal,10):
Next := convert(string[N+1..2*N],decimal,10):

end do:

# Test this N
if (N < 1+(lg/2)) then:

s := convert(string[1..N],decimal,10):
generated := s:

# Generate a string thanks to the found N

for i from 1 to lg/N do:
s := sˆ2 mod N:
tmp := convert(s,binary):
generated := cat(generated,tmp):
end do:

# Compare the generated string to the original

if (generated[1..lg] = string) then:

M := 2+(lg/2): # To stop the general loop

print("This string has been generated with the Blum-Blum and Shub Generator."):

else:

# To do another step of the general loop

# from the found N + 1 (Useless to begin at N=0)
N := N+1:
M := N:
end if:

else

# We arrive to the middle of the original string, so no N was found

M :=N:
print("This string has NOT been generated with the
Blum-Blum and Shub Generator."):

end if:

October 26, 2003 http://www.maxime-chambreuil.fr.st 4

 Cryptography & Data Security - Comp 547

end do:
return N:

end proc:

isBBSG(W0):
This string has NOT been generated with the Blum-Blum and Shub Generator.

isBBSG(W1):
This string has NOT been generated with the Blum-Blum and Shub Generator.

October 26, 2003 http://www.maxime-chambreuil.fr.st 5