IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises IV.
1. Let C be a cryptosystem with plaintext space P = {x, y, z}, key space K =
{k1, k2, k3} and cryptotext space C = {a, b, c}.
The probability distributions pP and pK are defined as
pP (x) =
3
8
, pP (y) =
1
8
, pP (z) =
1
2
;
pK(k1) =
1
3
, pK(k2) =
1
6
, pK(k1) =
1
2
.
The encryption function is given by the following table:
x y z
k1 a b c
k2 b c a
k3 c a b
(a) Determine the probability distribution pC.
(b) Is C perfectly secure? Explain your reasoning.
2. Decrypt the following ciphertexts.
(a) AABCCEEHHIILLOPPPRTY
(b) TEGUN LRNCS XXXIJ GJCPV CYMOA QUSKL UWMCJ
CWKIN NGNPZ JIIML MGVCS ZRJIX UCRRR ROWSY
WKSJA YNLRC AMTSB OQAEM WIIIJ SAFGS XXEUW
VPEQV PUNXR TMKKL UEILG YHYGE FYZPA TEWYM
XFQDU CEYHX RZRYY EJBEF DCJEI DWVLR RJUFO
UWVPE QVGQY WNTAN GLULX UGAFV WQLOR AGXAY
INXUG JJKXU LSSVF JMMWY RRTCP VCJBE GYYXL
WUXJB TRMRX SIPHO LZJMD AQRVF TUWIC QVNYW
KSJBS FGSXV HJIFE GYPKL UWERU YWTMF BIEVF
JCIJN IEUGS KLUWM CJCWK INNGN PZJUM IWSIG
PJU
(c) ABABB ABABA ABAAB AAAAA ABBAB
BABAA BBBBB ABAA
(d) JZDGCVVOVITZJV
3. You have found an old cryptotext encrypted with the Vigenere cryptosystem.
You have observed that the cryptotext contains three occurrences of the sequence
CGIRTFGH. These occurrences start at positions 37, 1283 and 2354.
What can you deduce about length of the key?
4. Let C be a product cryptosystem which consists of two transposition cryptosystems
whose block sizes are m and n. Determine the block size of C. Explain
your reasoning.
5. Let C = (P, C, K, e, d) be a cryptosystem.
(a) Suppose that C is perfectly secure. Show that for any m  P and c  C it
holds that Pr(C = c|P = m) = Pr(C = c).
(b) Suppose that for any m, m  P and c  C it holds that
Pr(P = m|C = c) = Pr(P = m |C = c).
Show that C is perfectly secure.
6. Let S be an endomorphic cryptosystem. Let S2
= S×S. Which of the following
simple cryptosystems ­ the Shift, Vigenere, Hill or Affine cryptosystem ­ would
you prefer to use as S2
. Explain your reasoning.
7. What is the number of keys one can use in the Hill cryptosystem with matrices
of degree 2 over Z26?