ITN581 – Semester 1 2002

Cryptographic Fundamentals and Applications

Assignment 1 (100 marks)

Gavin Longmuir - Answers in Red

1. (2 marks)

Calculate

(i) 621⁵¹ mod 131 56

(ii) φ(172872) 7³(7-1)x2²(2-1)x3¹(3-1)=49392

(iii) gcd(59801,2911867) 7

(iv) (95231)^-1 mod 131187 let a=95231, n=131187

0 < a < n, gcd(95231,131187)=1

via Euler’s theorem a^-1=a^f(131187)-1

φ(131187) = φ(3x7x6247)

= (3-1)(7-1)(6247-1) = 74952

a^-1 = 95231^(74952-1) mod 131187

= 95231^{(1+2+4+64+128+1024+8192+65536)} mod 131187

= 95231 x 117238 x 24280 x 12331 x 7828

x 11638 x 45628 x 82282 (mod 131187)

= 34424 mod 131187

2. (2 marks)

(i) Give the binary representation of 523. 1+2+8+512

1000001011 (as binary vector)

1101000001 (base2)

(ii) Find the reduced residue class of modulo 27. f(27)=3²(3-1)=18

shouldn’t have anything divisible by 3

find all gcd(i,27)=1,i=1..26

{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26}

3. (2 marks)

Find f(n) for all integers between 120 and 130 inclusive.

f(120)=2²(2-1)x3⁰(3-1)x5⁰(5-1)=32

f(121)=11¹(11-1)=110

f(122)=(2-1)(61-1)=60

f(123)=(3-1)(41-1)=80

f(124)=2¹(2-1)x31⁰(31-1)=60

f(125)=5²(5-1)=100

f(126)=3¹(3-1)x7⁰(7-1)x2⁰(2-1)=36

f(127)=127-1=126

f(128)=2⁶(2-1)=64

f(129)=(3-1)(43-1)=84

f(130)=(13-1)(5-1)(2-1)=48

4. (2 marks)

Find A^-1 for:

(i) A = é 0 1 ù mod 2

ë 1 1 û

A^-1 = é 1 1 ù mod 2

ë 1 0 û

(ii) A = é 13 17 ù mod 27

ë 5 26 û

A^-1 = é 8 1 ù mod 27

ë 13 4 û

5. (6 marks)

Solve for x:

(i) x º 17 mod 55 and x º 19 mod 49

use CRT via Gauss’s Algorithm, 55 and 49 are relatively prime – ie. gcd(55,49)=1

let c₁=17, c₂=19, d₁=55, d₂=49, and n=Πd_i where i=1..2, n=2695

x = Σ[ ( n / d_i ) (( n / d_i )^-1 mod d_i) x c_i ] mod n

= { [(2695/55) ((2695/55)^-1 mod 55) 17]

+ [(2695/49) ((2695/49)^-1 mod 49) 19] } mod 2695

= { [(49) ((49)^-1 mod 55) 17] + [(55) ((55)^-1 mod 49) 19] } mod 2695

= { [(49) (9) 17] + [(55) (41) 19] } mod 2695

= 1832 mod 2695

(ii) 7001x º 8941 mod 31465

a=7001, b=8941, gcd(a,b)=1, factors of 31465 are: 31, 29, 7, 5

x = 8941/7001 mod 31465 exists if 7001^-1 mod 31465 exists

= 8941 * 23101 mod 31465

= 9781 mod 31465

**************************************************************************************************

Note: In the following questions the text alphabet consists of

ABCDEFGHIJKLMNOPQRSTUVWXYZ_ unless otherwise specified.

Where a numerical equivalent is required, map A to 0, B to 1, ... , Z to 25, _ to 26.

Note that the _ character represents the <space> character.

**************************************************************************************************

6. (1 mark)

Decrypt the following cryptogram given that a Caesar cipher was used with a key shift of 17. (Refer to Appendix 1)

JYVQMZDUIQRHVQHZIZDXQZDQJYVQVRIJ

THE_WINDS_ARE_RISING_IN_THE_EAST

7. (4 marks)

Each of the following cryptograms are formed from a different Caesar cipher. Decrypt the cryptogram in each case.

(a) RFCYIGLBYMDYNCPQMLYUCYZPCYBCRCPKGLCQYRFCYIGLBYMDYDSRSPCYUCYDZAC

THE_KIND_OF_PERSON_WE_ARE_DETERMINES_THE_KIND_OF_FUTURE_WE_FACE

(b) XLYIK_PBCZYCKCDBTFPKQZBKSTRSKTOPLWCKLYOKPFPBIGSPBPKWTQPKTCKQEWWKZQKSPBZTCX

MANY_PERSONS_STRIVE_FOR_HIGH_IDEALS_AND_EVERYWHERE_LIFE_IS_FULL_OF_HEROISM

8. (6 marks)

Decode the following cryptograms given that each was formed by a transposition cipher (d £ 6). (Refer to Appendix 2)

(1) AREDAKL_OF_EHIS_NGINATW_S_REAL_IYSAWAYS_OOG_NI_DT_HG

1234/1234/1234/1234/1234/1234/1234/1234/1234/1234/1234/1234/1234

ARED/AKL_/OF_E/HIS_/NGIN/ATW_/S_RE/AL_I/YSAW/AYS_/OOG_/NI_D/T_HG

Transformation f^-1 = (4 3 1 2)

DEAR/_LAK/E_OF/_SHI/NING/_WAT/ERS_/I_AL/WAYS/_SAY/_GOO/D_NI/GHT_

(2) TWAA_HA_EYVHI_A_NRVW__EE_HDNIAE_HN_TTIHM_GMAAS___ADILI_DYHWD

HE_RENQ_NIUISREA_ITBUB_OKRAAFEHS_DAT

123456/123456/123456/123456/123456/

TWAA_H/A_EYVH/I_A_NR/VW__EE/_HDNIA/E_HN_T/TIHM_G/MAAS__/_ADILI/_DYHWD/HE_REN/Q_NIUI
/SREA_I/TBUB_O/KRAAFE/HS_DAT

Transformation f^-1 = (2 6 3 1 5 4)

WHAT_A/_HEAVY/_RAIN_/WE_VE_/HAD_IN/_THE_N/IGHT_M/A_AM_S/AID_LI/DDY_WH/EN_HER/_INQUI
/RIES_A/BOUT_B/REAKFA/ST_HAD

(3) ENI__H_EVR_DAEROCFO_YNPMANIG_OMO_GHTI_EW_TOHUS_ETAOMEH_DERU

ND_O_H_AAINOYOD_PU_US_EOPS_

Clue: this one starts with a <space> character.

12345/12345/12345/12345/

ENI__/H_EVR/_DAER/OCFO_/YNPMA/NIG_O/MO_GH/TI_EW/_TOHU/S_ETA/OMEH_/DERUN/D_O_H/_AAIN
/OYOD_/PU_US/_EOPS/_

Transformation f^-1 = (4 3 5 2 1)

_I_NE/VER_H/EARD_/OF_CO/MPANY/_GOIN/G_HOM/E_WIT/HOUT_/TEA_S/HE_MO/URNED/_OH_D/IANA_
/DO_YO/U_SUP/POSE_/?

9. (3 marks)

The following cryptogram was formed using the operation

c º (8p + 15) mod 27

where p and c denote the numerical equivalent character of a plaintext and ciphertext character. (Refer to Appendix 3) Use this information to decrypt the message:

FRZYHUKAUQZULEUHPWYTHFPNJRFHDUHPLTFRUQ

THIS_EXPERIENCE_ALSO_TAUGHT_ME_ANOTHER

10. (3 marks)

Suppose that it is known that plaintext letters (p denotes numerical equivalence of plaintext letter) are encrypted using the formula

c º (ap + b) mod 27.

It is also known that the encryption of letter T is letter K and the encryption of letter I is letter D.

(i) Use this information to find the encryption keys a and b.

c º (ap + b) mod 27

ap º c – b mod 27

a º p^-1 (c – b) mod 27

p₁=T=19, c₁=K=10, p₂=I=8, c₂=D=3

p₁^-1=10, p₂^-1=17

a º 10 (10 – b) mod 27 and a º 17 (3 – b) mod 27

100 – 10b mod 27 º 51 – 17b mod 27

19 – 10b mod 27 º 24 – 17b mod 27

19 + 7b mod 27 º 24 mod 27

7b mod 27 º 5 mod 27

b = 20, a = 8

(ii) Find the decryption keys x and y, where

p º (xc + y) mod 27.

c º (ap + b) mod 27

ap º c – b mod 27

p º a^-1 (c – b) mod 27

b = 20, a = 8, a^-1 = 17

xc + y mod 27 º 17(c – 20) mod 27

xc + y mod 27 º 17c – 16 mod 27

x = 17, y = 11

11. (3 marks)

Encrypt the message HAPPY_BIRTHDAY using a Hill cipher (Refer to Appendix 4) with the encryption matrix of

é 5 11 ù

ë 19 17û

HA\PP\Y_\BI\RT\HD\AY

IZ\YA\BH\MU\YZ\OW\VD

12. (6 marks)

The cryptogram below is formed using a Hill cipher with a 2 by 2 encryption matrix. It is known that the plaintext begins with the characters AS_YOU. Use this information to find the encryption matrix. What is the decryption matrix? Use this information to decrypt the cryptogram:

AJXVFH_QZJCXUROBCTY_WOITNIWOQHJK

AJ/XV/FH/_Q/ZJ/CX/UR/OB/CT/Y_/WO/IT/NI/WO/QH/JK

AS/_Y/OU/

[ 0 9 ] . é a b ù = [ 0 18 ]

ë c d û

[ 23 21 ] . é a b ù = [ 26 24 ]

ë c d û

[ 5 7 ] . é a b ù = [ 14 20 ]

ë c d û

using pairs 1 and 2 let

é 0 9 ù = é 0 18 ù . é a b ù

ë 23 21 û ë 26 24 û ë c d û

é 0 18 ù ^-1 = not invertible

ë 26 24 û

try using pairs 2 and 3

é 23 21 ù = é 26 24 ù . é a b ù

ë 5 7 û ë 14 20 û ë c d û

é 26 24 ù ^-1 = é 23 21 ù mod 27

ë 14 20 û ë 19 11 û

thus via C = A . P mod 27 è C . P^-1 = A mod 27

é 26 24 ù . é 17 3 ù = é 25 9 ù

ë 14 20 û ë 11 25 û ë 15 8 û

A = é 25 9 ù

ë 15 8 û

P = C . A

AJ/XV/FH/_Q/ZJ/CX/UR/OB/CT/Y_/WO/IT/NI/WO/QH/JK

AS/_Y/OU/_L/EA/RN/_T/O_/LI/ST/EN/_I/NT/EN/TL/Y_

13. (3 marks)

Decode the cryptogram below given that ciphertext characters are encrypted in blocks of length 2 using the operation

C º AP mod 27

where A denotes the 2 by 2 matrix given below

A = é19 8 ù

ë2 20û

DILTVXWGXRCSOVRHSZWNQHJZQBBX

P = A^-1 . C mod 27

A^-1 = é 14 16 ù

ë 4 16 û

DI/LT/VX/WG/XR/CS/OV/RH/SZ/WN/QH/JZ/QB/BX

IF/_Y/OU/_W/AN/T_/TO/_S/EN/D_/MO/NE/Y_/EV

14. (1 mark)

Suppose that the cryptogram 011101101101100100100010 is intercepted.

Suppose that it is known that this cryptogram was formed by a stream cipher and

that the first eight bits of plaintext are 10111110.

Use the above information to derive the first eight bits of the keystream.

Ci = (Pi + Ki) mod 2

10111110

11001000 ç keystream

01110110

15. (4 marks)

Let a(t) be a binary sequence produced by a LFSR whose characteristic polynomial is x⁵ + x³ + 1.

(i) Find the first period of the sequence if the initial state vector 00011 is used.

f(x) = x⁵ + x³ + x⁰

let initial state vector a(u₀, u₁, u₂, u₃, u₄) be 00011

u₅ will be u₃ + u₀ mod 2, u₆ = u₄ + u₁ mod 2 and so on..

00011 ç initial vector (u₀,u₁,u₂,u₃,u₄)

+ +

00111

+ +

01111

+ +

11111

+ +

11110

+ +

11100 ç 2^nd vector (u₅,u₆,u₇,u₈,u₉)

+ +

11001

+ +

10011

+ +

00110

+ +

01101

+ +

11010 ç 3^rd vector (u₁₀,u₁₁,u₁₂,u₁₃,u₁₄)

+ +

10100

+ +

01001

+ +

10010

+ +

00100

+ +

01000 ç 4^th vector (u₁₅,u₁₆,u₁₇,u₁₈,u₁₉)

+ +

10000

+ +

00001

+ +

00010

+ +

00101

+ +

01010 ç 5^th vector (u₂₀,u₂₁,u₂₂,u₂₃,u₂₄)

+ +

10101

+ +

01011

+ +

10111

+ +

01110

+ +

11101 ç 6^th vector (u₂₅,u₂₆,u₂₇,u₂₈,u₂₉)

+ +

11011

+ +

10110

+ +

01100

+ +

11000

+ +

10001 ç 7^th vector (u₃₀,u₃₁,u₃₂,u₃₃,u₃₄)

+ +

00011 ç is the same as initial vector

thus period is one bit over 6

(ii) Find the first period of the sequence b(t) = a(2t).

b(0) = a(2*0), b(1) = a(2*1), ..b(4)=a(2*4)

initial state vector b(u₀, u₂, u₄, u₆, u₈) is 00110

2^nd state vector b(u₁₀, u₁₂, u₁₄, u₁₆, u₁₈) is 10010

3^rd state vector b(u₂₀, u₂₂, u₂₄, u₂₆, u₂₈) is 00010

from above, u₃₁ is the same as u₀ ie mod 31.

4^th state vector b(u₃₀, u₁, u₃, u₅, u₇) is 10111

5^th state vector b(u₉, u₁₁, u₁₃, u₁₅, u₁₇) is 01100

6^th state vector b(u₁₉, u₂₁, u₂₃, u₂₅, u₂₇) is 01111

7^th state vector b(u₂₉, u₀, u₂, u₄, u₆) is 10011

thus period is one bit over 6

16. (4 marks)

Let z be a Boolean function produced by Boolean variables x₁,x₂,....,x_n. Suppose that

z = f(x₁,x₂,...,x_n-1) + x_n

where f is a Boolean function of x₁,x₂,...,x_n-1. If the probability that x_n = 0 is ½

show that the probability that z = 0 is ½.

Show that XOR-ing gives a ‘0’ 50% percent of the time

Let P(f(x₁,x₂,...,x_n-1)=0) be p, thus P(f(x₁,x₂,...,x_n-1)=1) is 1-p

Now P(x_n=0) is ½ and P(x_n=1) is ½

P(z=0) = P(x_n=0) . P(f(x₁,x₂,...,x_n-1)=0) + P(x_n=1) . P(f(x₁,x₂,...,x_n-1)=1)

= ½ . p + ½ (1-p)

= ½ (p+1-p)

= ½

17. (12 marks)

Suppose that F is a symmetric block cipher with block size eight. Suppose that F is a two round Feistel cipher. Suppose that for a certain key K this cipher results in the following substitution table for each round:

Round 1:

0000®1101 0001®1000 0010®1011 0011®0001

0100®0111 0101®1010 0110®1111 0111®0000

1000®0100 1001®1110 1010®0110 1011®1100

1100®1001 1101®0010 1110®0011 1111®0101

Round 2:

0000®1111 0001®1011 0010®0100 0011®0101

0100®1010 0101®0000 0110®0011 0111®1110

1000®0001 1001®1100 1010®1000 1011®1101

1100®0110 1101®1001 1110®0111 1111®0010

We want to encrypt a 24 bit message M given below:

M = 111000111110010011100011

(i) Find the cryptogram which results from encrypting M when block cipher is used

in ECB mode. (2 marks)

n=8, let P=(x₀,x₁), C=(x₂,x₃), two rounds h=2

where x_i+1 = x_i-1 + F_i(x_i) mod 2

M = (1110,0011)(1110,0100)(1110,0011)

R1 (1110,0011) è (0011,(1110+0001)) è (0011,1111)

R2 (0011,1111) è (1111,(0011+0010)) è (1111,0001)

R1 (1110,0100) è (0100,(1110+0111)) è (0100,1001)

R2 (0100,1001) è (1001,(0100+1100)) è (1001,1000)

R1 (1110,0011) è (0011,(1110+0001)) è (0011,1111)

R2 (0011,1111) è (1111,(0011+0010)) è (1111,0001)

C = (1111,0001)(1001,1000)(1111,0001)

(ii) Find the cryptogram which results from encrypting M when block cipher is used

in CBC mode with initialisation vector IV = 10101010. (2 marks)

n=8, let P=(x₀,x₁), C=(x₂,x₃), two rounds h=2

where x_i+1 = x_i-1 + F_i(x_i) mod 2

IV = (1010,1010)

M = (1110,0011)(1110,0100)(1110,0011)

M = (M₁)(M₂)(M₃)

permute M₁ by IV è (1110,0011)+(1010,1010) è (0100,1001)

R1 (0100,1001) è (1001,(0100+1110)) è (1001,1010)

R2 (1001,1010) è (1010,(1001+1000)) è (1010,0001)

permute M₂ by C₁ è (1110,0100)+(1010,0001) è (0100,0101)

R1 (0100,0101) è (0101,(0100+1010)) è (0101,1110)

R2 (0101,1110) è (1110,(0101+0111)) è (1110,0010)

permute M₂ by C₂ è (1110,0011)+(1110,0010) è (0000,0001)

R1 (0000,0001) è (0001,(0000+1000)) è (0001,1000)

R2 (0001,1000) è (1000,(0001+0001)) è (1000,0000)

C = (1010,0001)(1110,0010)(1000,0000)

(iii) Find the cryptogram which results from encrypting M when block cipher is used

in OFB mode with four bits of feedback and the same initialisation vector as in

(ii). (2 marks)

n=8, let X_t=(x₀,x₁), Y_t=(x₂,x₃), two rounds h=2,

L=n/2=4 and that Z_t=lower 4 bits of Y_t

where x_i+1 = x_i-1 + F_i(x_i) mod 2

IV = (1010,1010) = X₁

M = (1110)(0011)(1110)(0100)(1110)(0011)

M = (M₁)(M₂)(M₃)(M₄)(M₅)(M₆)

R1 (1010,1010) è (1010,(1010+0110)) è (1010,1100)

R2 (1010,1100) è (1100,(1010+0110)) è (1100,1100) = Y₁

permute M₁ with lower 4 bits of Y₁ (Z₁) è (1110)+(1100) è (0010) = C₁

X₂ is lower 4 bits of X₁ concatenated with Z₁ è (1010,1100)

R1 (1010,1100) è (1100,(1010+1001)) è (1100,0011)

R2 (1100,0011) è (0011,(1100+0101)) è (0011,1001) = Y₂

permute M₂ with lower 4 bits of Y₂ (Z₂) è (0011)+(1001) è (1010) = C₂

X₃ is lower 4 bits of X₂ concatenated with Z₂ è (1100,1001)

R1 (1100,1001) è (1001,(1100+1110)) è (1001,0010)

R2 (1001,0010) è (0010,(1001+0100)) è (0010,1101) = Y₃

permute M₃ with lower 4 bits of Y₃ (Z₃) è (1110)+(1101) è (0011) = C₃

X₄ is lower 4 bits of X₃ concatenated with Z₃ è (1001,1101)

R1 (1001,1101) è (1101,(1001+0010)) è (1101,1011)

R2 (1101,1011) è (1011,(1101+1101)) è (1011,0000) = Y₄

permute M₄ with lower 4 bits of Y₄ (Z₄) è (0100)+(0000) è (0100) = C₄

X₅ is lower 4 bits of X₄ concatenated with Z₄ è (1101,0000)

R1 (1101,0000) è (0000,(1101+1101)) è (0000,0000)

R2 (0000,0000) è (0000,(0000+1111)) è (0000,1111) = Y₅

permute M₅ with lower 4 bits of Y₅ (Z₅) è (1110)+(1111) è (0001) = C₅

X₆ is lower 4 bits of X₅ concatenated with Z₅ è (0000,1111)

R1 (0000,1111) è (1111,(0000+0101)) è (1111,0101)

R2 (1111,0101) è (0101,(1111+0000)) è (0101,1111) = Y₆

permute M₆ with lower 4 bits of Y₆ (Z₆) è (0011)+(1111) è (1100) = C₆

C = (0010),(1010),(0011),(0100),(0001),(1100)

(iv) Find the cryptogram which results from encrypting M when block cipher is used

in CFB mode with four bits of feedback and the same initialisation vector as in

(ii). (2 marks)

n=8, let X_t=(x₀,x₁), Y_t=(x₂,x₃), two rounds h=2,

L=n/2=4 and that Z_t=lower 4 bits of Y_t

where x_i+1 = x_i-1 + F_i(x_i) mod 2

IV = (1010,1010) = X₁

M = (1110)(0011)(1110)(0100)(1110)(0011)

M = (M₁)(M₂)(M₃)(M₄)(M₅)(M₆)

R1 (1010,1010) è (1010,(1010+0110)) è (1010,1100)

R2 (1010,1100) è (1100,(1010+0110)) è (1100,1100) = Y₁

permute M₁ with lower 4 bits of Y₁ (Z₁) è (1110)+(1100) è (0010) = C₁

rotate C₁ into lower 4 bits of X₂ è (1010,0010)

R1 (1010,0010) è (1010,(1010+1011)) è (0010,0001)

R2 (0010,0001) è (0001,(0010+1011)) è (0001,1001) = Y₂

permute M₂ with lower 4 bits of Y₂ (Z₂) è (0011)+(1001) è (1010) = C₂

rotate C₂ into lower 4 bits of X₃ è (0010,1010)

R1 (0010,1010) è (1010,(0010+0110)) è (1010,0100)

R2 (1010,0100) è (0100,(1010+1010)) è (0100,0000) = Y₃

permute M₃ with lower 4 bits of Y₃ (Z₃) è (1110)+(0000) è (1110) = C₃

rotate C₃ into lower 4 bits of X₄ è (1010,1110)

R1 (1010,1110) è (1110,(1010+0011)) è (1110,1001)

R2 (1110,1001) è (1001,(1110+1100)) è (1001,0010) = Y₄

permute M₄ with lower 4 bits of Y₄ (Z₄) è (0100)+(0010) è (0110) = C₄

rotate C₄ into lower 4 bits of X₅ è (1110,0110)

R1 (1110,0110) è (0110,(1110+1111)) è (0110,0001)

R2 (0110,0001) è (0001,(0110+1011)) è (0001,1101) = Y₅

permute M₅ with lower 4 bits of Y₅ (Z₅) è (1110)+(1101) è (0011) = C₅

rotate C₅ into lower 4 bits of X₆ è (0110,0011)

R1 (0110,0011) è (0011,(0110+0001)) è (0011,0111)

R2 (0011,0111) è (0111,(0011+1110)) è (0111,1101) = Y₆

permute M₆ with lower 4 bits of Y₆ (Z₆) è (0011)+(1101) è (1110) = C₆

C = (0010)(1010)(1110)(0110)(0011)(1110)

(v) Recover M back by decrypting each of the cryptograms formed in (i)-(iv). Show

working. (4 marks)

ECB (i) C = (1111,0001)(1001,1000)(1111,0001)

R2 (0001,1111) è (1111,(0001+0010)) è (1111,0011)

R1 (1111,0011) è (0011,(1111+0001)) è (0011,1110)

M1 = (1110,0011)

R2 (1000,1001) è (1001,(1000+1100)) è (1001,0100)

R1 (1001,0100) è (0100,(1001+0111)) è (0100,1110)

M2 = (1110,0100)

R2 (0001,1111) è (1111,(0001+0010)) è (1111,0011)

R1 (1111,0011) è (0011,(1111+0001)) è (0011,1110)

M3 = (1110,0011)

M = (1110,0011)(1110,0100)(1110,0011)

CBC (ii) C = (1010,0001)(1110,0010)(1000,0000)

IV = (1010,1010)

R2 (0001,1010) è (1010,(0001+1000)) è (1010,1001)

R1 (1010,1001) è (1001,(1010+1110)) è (1001,0100)

permute Z₁ by IV è (0100,1001)+(1010,1010) è (1110,0011)

R2 (0010,1110) è (1110,(0010+0111)) è (1110,0101)

R1 (1110,0101) è (0101,(1110+1010)) è (0101,0100)

Permute Z₂ by C₁ è (0100,0101)+(1010,0001) è (1110,0100)

R2 (0000,1000) è (1000,(0000+0001)) è (1000,0001)

R1 (1000,0001) è (0001,(1000+1000)) è (0001,0000)

Permute Z₃ by C₂ è (0000,0001)+(1110,0010) è (1110,0011)

M = (1110,0011)(1110,0100)(1110,0011)

OFB (iii) C = (0010)(1010)(0011)(0100)(0001)(1100)

M = (1110)(0011)(1110)(0100)(1110)(0011)

CFB (iv) C = (0010)(1010)(1110)(0110)(0011)(1110)

M = (1110)(0011)(1110)(0100)(1110)(0011)

18. (2 marks)

Suppose that it is known that an encryption algorithm of the form C = AP (modulo

2 arithmetic) is used to encrypt plaintext blocks P of length 6 into ciphertext

blocks C of length 6 using the key A (6 by 6 matrix). Suppose that the plaintext-

ciphertext pairs of blocks given below have been intercepted. Use this

information to derive the key A.

P = 1 0 0 0 0 0 C = 1 0 0 0 0 0

0 1 0 1 1 0 0 0 1 0 0 0

0 0 1 0 1 0 0 0 0 1 0 0

1 0 0 1 0 0 0 1 0 0 0 0

0 1 0 0 0 1 0 0 1 0 1 0

0 0 1 0 1 1 1 0 0 0 1 1

C = A . P mod 2

C . P^-1 = A mod 2

A = 1 0 0 0 0 0

1 1 0 1 1 1

1 0 0 1 0 0

0 0 1 0 1 1

0 0 1 0 0 0

0 1 0 1 1 0

19. (7 marks)

Let DES(x,k) represent the encryption of plaintext x with key k using the DES cryptosystem. Suppose y = DES(x,k) and z = DES(x^/,k^/) where ^/ denotes the bitwise complement. Prove that z = y^/ (i.e. if we complement the plaintext and the key, then the ciphertext is also complemented). Note that this can be proved using only the high-level description of DES - the actual structure of S-boxes and other components of the system are irrelevant.

The complement test of a +₂ a^/ gives an all ones vector. On entering the DES F function for each round 32-bits of the block are expanded to 48-bits and XOR-ed with the round subkey. Since x^/, and k^/ are bitwise complement of x and k.

Let x = x₀, x₁

y = x₁, x₂ where x₂ = x₀ +₂ F(x₁ +₂ k)

x^/ = x₀^/, x₁^/

z = x₁^/, X^/ where X^/ = x₀^/ +₂ F(x₁^/ +₂ k^/) = x₀^/ +₂ F(x₁ +₂ k) since a^/ +₂ b^/ = a +₂ b

= 1111..1 +₂ x₀^/ +₂ F(x₁ +₂ k)

= 1111..1 +₂ x₂

= x₂^/

thus z^/ = x₀^/, x₁^/ = y^/

20. (7 marks)

Suppose a sequence of plaintext blocks x₁...x_n is encrypted using DES, producing ciphertext blocks y₁...y_n. Suppose that one ciphertext block, say y_i, is transmitted incorrectly (i.e. some 1's are changed to 0's and vice versa). Show that the number of plaintext blocks that will be decrypted incorrectly is equal to one if ECB or OFB modes were used for encryption; equal to two if CBC mode was used; and equal to three if CFB mode (with feedback block size of 32 bits) was used.

Let y_i be the encrypted block, also assume that i is greater that 2 blocks into stream (otherwise IV has greater effect). Assume that all bits of the block are equally likely to be incorrect.

· For decryption in ECB mode, no feedback register is used, and decryption uses subkeys in reverse order, thus only one block will be decrypted incorrectly - y_iÖx_i.

· For decryption in OFB mode, a LFBR is used but it is independent of the inputted ciphertext. The value of the LFBR will always be dependent on its previous value, thus only one block will be decrypted incorrectly - y_iÖx_i.

· For decryption in CBC mode, no feedback register is used. Decryption of block y_i is also dependent on the value of block y_i-1. As a corollary block y_i+1 is dependent on the value of y_i. To continue y_i+2 is dependent on y_i+1. It is known that only y_i was incorrectly transmitted, thus we can say that two blocks will be decrypted incorrectly – y_iÖx_i and y_i+1Öx_i+1.

· For decryption in CFB mode, a LFBR is used and is feed by values from previous blocks. The LFBR is sized at 64-bits. 32-bits of each block received is shifted into the LFBR for the next cycle. For i greater than 2, the LFBR contains 32-bits of y_i-2 and 32-bits of y_i-1. Decryption of y_i is dependent on the value of the LFBR, thus dependent on y_i-2 and y_i-1. y_i+1 is dependent on y_i-1 and y_i. y_i+2 is dependent on y_i and y_i+1. It is known that only y_i was incorrectly transmitted, thus we can say that three blocks will be decrypted incorrectly – y_iÖx_i, y_i+1Öx_i+1 and y_i+2Öx_i+2.

21. (7 marks)

For AES Rijndael with 128-bit data block and 128-bit master key, the key schedule generates eleven 128-bit subkeys (k₀, k₁, … ,k₁₀). Explain how knowledge of subkey k_i (1 £ I £ 10) enables subkey k_i-1 to be determined.

AES Rijndael uses a 128-bit key (k0), subkeys k₁ to k₁₀ are derived from this. k₀ is broken into 4 32-bit values, call these elements w[0], w[1], w[2], w[3]. Subkeys k₁ to k₁₀ are likewise broken into 4 32-bit values. K₁ is w[4], w[5], w[6], w[7], …, k₁₀ is w[40], w[41], w[42], w[43]. Calculation of the subkeys is done recursively via:

w[j] = w[j-4] +₂ F(j,w[j-1])

w[j+1] = w[j-3] +₂ w[j]

w[j+2] = w[j-2] +₂ w[j+1]

w[j+3] = w[j-1] +₂ w[j+2]

where j = 4,8,12,…,40

and F() contains known byte rotation and substitution functions which are then XOR-ed with a defined constant for each value of j

Given subkey i we have w[4i], w[4i+1], w[4i+2], and w[4i+3]. We also know the defined constant for 4i. Thus calculating w[4i-4], w[4i-3], w[4i-2], and w[4i-1] to provide us with subkey i-1 is straight forward.

w[4i-1] is derived from w[4i+3] and w[4i+2]

w[4i-2] is derived from w[4i+2] and w[4i+1]

w[4i-3] is derived from w[4i+1] and w[4i]

w[4i-4] is derived from w[4i], w[4i-1], and constant defined for 4i

22. (3 marks)

Let X be one of the six messages: A,B,C,D,E,F, where:

p(A) = p(B) = p(C) = 1/4

p(D) = 1/8

p(E) = p(F) = 1/16

Compute the entropy of the message space, H(X).

H(X) = ¼ log₂ (4) + ¼ log₂ (4) + ¼ log₂ (4) + 1/8 log₂ (8) + 1/16 log₂ (16) + 1/16 log₂ (16)

= ¼ (2) + ¼ (2) + ¼ (2) + 1/8 (3) + 1/16 (4) + 1/16 (4)

= 1.5 + 3/8 + .5

= 2.375

23. (3 marks)

Let M be a 6-digit number in the range [0,10⁶-1] enciphered with a Caesar-type shifted substitution cipher with key K, 0£K£9. For example, if K=1, M=123456 is enciphered as 234567. Compute H(M), H(C), and H(K), assuming all values of M and K are equally likely.

H(M) = H(C) = 10⁶ (1/10⁶ log₂ (10⁶)) = 6 log₂ 10 = 19.93

H(K) = log₂ (10) = 3.32

24. (4 marks)

Let X be an integer variable represented with 32 bits. Suppose that the probability is 1/2 that X is in the range [0,2⁸-1], with all such values being equally likely, and 1/2 that X is in the range [2⁸,2³²-1], with all such values being equally likely. Compute H(X).

Find entropy of X

X={X[0],..,X[2⁸-1],X[2⁸],..,X[2³²-1]}

p(X[0],..,X[2⁸-1])=1/2, p(X[2⁸],..,X[2³²-1])=1/2

H(X)=2⁸(1/2⁹ log₂ (2⁹)) + (2³²-2⁸)(1/(2³³ – 2⁹) log₂ (2³³ – 2⁹))

2⁸(1/2⁹ (9)) + (2³²-2⁸)(1/2³³ (33))

4.5 + 16.5 = 21

25. (3 marks)

Compute the unicity distance for each of the following ciphers, assuming that the plaintext is 26-letter English and the redundancy of 26-letter English is 3.2 bits per letter:

(i) a transposition cipher of length 12,

(ii) a Vigenere cipher of period 4,

(iii) a linear transformation cipher of the form c=ap+b.

.

D=3.2

i) N = H(K) / D

= log₂ 12! / 3.2

= 9.0

ii) N = H(K) / D

= log₂ 26⁴ / 3.2

= 5.9

iii) assume modulus 26

gcd(a,26)=1, and f(26)=12, b=any value mod 26

N = H(K) / D

= log₂ (12 * 26) / 3.2

= 2.6

Appendix 1:

Definition: A Caesar cipher is a substitution cipher which moves the i^th character of an alphabet (the plaintext character) to the (i+j)^th character of the alphabet (the ciphertext character), that is:

Encryption: c_i = a_i + j mod 27 (for a 27-character alphabet)

Decryption: a_i = c_i – j mod 27

The value j is called the key shift of the Caesar cipher.

For example: CIPHER ® DJQIFS where j = 1

Appendix 2:

To decipher a transposition cipher, we need to find the period d and the permutation f used in the encryption process.

Break the cryptogram up into blocks of length d (starting with d = 2). We then look at a block and try to “unscramble” the characters in that block. This will give us a contender for the permutation f.

Once a possible permutation is determined, this permutation should be tested on other blocks. If a suitable permutation for a given d cannot be found, try the next size for d.

For example, given the cryptogram O_HWWE_RIETH_ENAMSE_ITSU_IOTNA:

Trial 1: O_ / HW / WE / _R / IE / TH / _E / NA / MS / E_ / IT / SU / _I / OT / NA

Trial 2: O_H / WWE / _RI / ETH / _EN / AMS / E_I / TSU / _IO / TNA

Trial 3: O_HW / WE_R / IETH / _ENA / MSE_ / ITSU / _IOT / NA

Trial 4: O_HWW / E_RIE / TH_EN / AMSE_ / ITSU_ / IOTNA

which decrypts to WHO_WERE_IN_THE_SAME_SITUATION using the decryption key of f^–1 = ( 5 3 1 2 4)

Appendix 3:

A Linear cipher is of the format

c º (ap + b) mod n

where p and c are the numerical representation of the plaintext and ciphertext

characters, n is the modulus for the arithmetic operations, and a and b are two numbers

less than n such that gcd(a,n)=1.

a, b and n define a particular Linear cipher.

How does one decrypt a Linear cipher?

c º (ap + b) mod n

® c – b º ap mod n

® a^–1 ( c – b ) º p mod n

® p º a^–1 ( c – b ) mod n

Appendix 4:

A Hill cipher is of the format

C º KP mod n

where P and C are 2-tuples of plaintext and ciphertext characters, n is the modulus and K is a 2x2 key matrix such that |K| ¹ 1 and gcd(|K|,n)=1 where |K| is the determinant of K.

K and n define a particular Hill cipher.

C º KP mod n

® K^–1 C º P mod n

® P º K^–1 C mod n

Example:

é 4 ù

Let n = 27, and plaintext 2-tuple = (E G) ® P = ë 6 û

é 4 6ù é 4 12ù

and K = ë 1 7û ® K^-1 = ë 11 10û (use BIC to find K^-1 )

Encryption: C º K P

é 4 6ù é 4 ù

º ë 1 7û ë 6 û

é 25 ù

º ë 19 û (use BIC)

which is the ciphertext 2-tuple ZT

Decryption: P º K^-1 P

é 4 12ù é 25 ù

º ë 11 10û ë 19 û

é 4 ù

º ë 6 û

----------------------------------------------------------------------------------------------------------

Plaintext statistics derived from the first 600 000 characters of the Bible*.

Characters

_ 0.198 N 0.058 F 0.021 Y 0.013 Z 0.000

E 0.102 S 0.047 U 0.020 B 0.013 X 0.000

T 0.079 I 0.045 M 0.019 P 0.010 Q 0.000

A 0.072 R 0.043 W 0.016 V 0.007

H 0.070 D 0.042 C 0.014 K 0.005

O 0.060 L 0.031 G 0.013 J 0.002

Digrams

E_ 0.042 AB 0.023 _H 0.014 R_ 0.011 _B 0.009

TH 0.040 ND 0.020 _O 0.013 IN 0.010 Y_ 0.009

_T 0.038 S_ 0.018 _W 0.012 F_ 0.010 O_ 0.009

HE 0.033 T_ 0.018 ER 0.011 RE 0.010 HI 0.008

D_ 0.031 _S 0.015 _I 0.011 OF 0.010 OR 0.008

_A 0.027 N_ 0.014 HA 0.011 H_ 0.009 AT 0.008

Trigrams

_TH 0.031 OF_ 0.009 IS_ 0.005 AT_ 0.004 _BE 0.004

THE 0.025 _OF 0.009 ED_ 0.005 D_A 0.004 ALL 0.004

HE_ 0.020 D_T 0.007 _HE 0.005 HER 0.004 F_T 0.004

ND_ 0.018 TO_ 0.006 ER_ 0.005 _HI 0.004 _SH 0.004

AND 0.018 TH_ 0.006 LL_ 0.005 EN_ 0.004 E_S 0.004

_AN 0.017 E_T 0.005 E_A 0.004 N_T 0.004 HAT 0.004

This plaintext was prepared as follows:

•all lowercase characters converted to uppercase characters

•one space only between words

•only characters ABCDEFGHIJKLMNOPQRSTUVWXYZ_ retained - all other characters deleted