CSCI361: Consider the Affine Cipher on the alphabet Z26 = {A, B, . . . , Z} with the usual identification: Cryptography and Secure Applications Assignment, UOW, Singapore

Aims:

1. To gain a basic familiarity with some security concepts, and with classical ciphers, including statistical methods for cryptanalysis of them.

2. To become familiar with block ciphers, mode of operations, the importance of S-box and cryptanalysis of linear cipher.

In this assignment, you will implement two “mini” versions of DES called LDES and MDES which work on 4-bit block message and 2-bit key.

In the first algorithm LDES, the S-box is removed and replaced with a linear operation making LDES a linear cipher.

You will perform cryptanalysis on LDES. The second algorithm MDES has a S-box and it is secure against linear cryptanalysis.

3. To understand classical cipher, modern block cipher and stream cipher.

Part 1. Affine Cipher

Consider the Affine Cipher on the alphabet Z26 = {A, B, . . . , Z} with the usual identification A = 0, B = 1, . . . , Z = 25, and the encryption function with key (a, b):
C = aM + b (mod 26).

1. Which of the following keys are valid? and why?
(i) (13, 9) (ii) (8, 3) (iii) (11, 0) (iv) (0, 15) (v) (5, 1)

2. For each of the above valid keys, determine the decryption function formula. (Please show all your working steps.)

3. Implement the cipher.

The program should be able to do both encryption and decryption. Lowercase characters a-z will be encrypted/decrypted to lowercase characters. Uppercase characters A-Z will be encrypted/decrypted to uppercase characters. Other characters not in the range (a-z, A-Z) will be unchanged.

The program should accept the following parameters: a flag to indicate encryption or decryption, a secret key, an input file name, and an output file name. For example:
myProgram -key 3 8 -encrypt -in file1.txt -out file2.txt

myProgram -key 3 8 -decrypt -in file2.txt -out file3.txt

The program should be able to detect invalid key and display an error message if it encounters an invalid key.

4. Test your program (both encryption and decryption) with the keys in question 1. You need to create your own test data for this task.

Part 2. Encryption Question

The content of this part has been encrypted by the Affine Cipher. The ciphertext is contained in the file A1Task2.txt on Moodle site. You need to use your program in Part 1 to decrypt this file in order to know the question and answer it.
The contents of the file is quoted as follows:

Vhn oin Pygnq fu Zfpyzpgnyzn rnoifg lh gnrfyhoalong py oin knzovan of gnonarpyn oin dnx lyg gnzaxmo oin ufkkfjpyb zpminaonqo fu oin Cpbnynan zpmina.

Py xfva anmfao, hifj honm-sx-honm ifj xfv upyg fvo oin dnx lyg oin mklpyonqo, mknlhn pyzkvgn lkk anknclyo hzannyhifoh. Xfv jpkk YFO sn bpcny rlad pu xfv wvho bpcn oin dnx lyg oin mklpyonqo jpoifvo lyx nqmklylopfy.
Inan ph oin zpminaonqo. Bffg kvzd!

Pbbqq lwcleyrn tq oijer yjs md kwfdoop xriyqr iihqerdeq ook iihqerde hqenodtl, xi dcqyqr xlbs xld kurb lxiqrp ook xdbcqufsxqw srdvzkl emwu fl vdvswcerp xqja yoperyjjsurp opdwkx jj rv douipx jffyrbo qqpzjseb xlqrurx phj
ypnoqkq. Ox nw cvcpyps aiqr ox vzj kvdyoa, dobxzaqq phj izqsorqk bdxsstxsdl obathq, emwdd tq o pjjddlviokybr thcqrukd th ryr pqhphj kjj SPS

vdvywkxtobboq rv vubbfw ile psrtxoa rhffeobhrhr bcp qpjhihb. Iairj kddedfsg lbl bqdc yjdcxsktwj bl obd jd ryr qrqpxqrti pqtodfsyqx th Ollxdboyo ej aqds xld kwubcpk vy toz rhxveiqhrhr, opxsvcun bcp kepxq rjlqqcaqosq, jdywbxr,
qqpzjseb ubw yybbciq fcpyxsjsdl.

Fiil ox emw xlsedd nyna ww so ptn vy xldlw oqruk dcqyqthe emwdd tq bbsyiopt cbquvfoyrn so ubthrbth ook byfop ile wkxrhrfpt kdelsprq ook qrvq xldv ddvv bqfck jfljycswj, wrqrqjgqw, jj ryewoerhqw, phj emur vzj pdeqiopt soyodhpxsvc yk ojx cvvayotioerp, kypjqw, gyklptsurp iq phoabqqw nyryjer vzj pdeasxlyio.

Part 3. LDES

The figure below describes a block cipher LDES (“linear” DES).

LDES is a mini example of a block cipher that has 2 rounds in the Feistel structure. It operates on 4-bit block and 2-bit key. The important feature of LDES is that the S-box has been replaced with a linear operation, which makes the whole cipher linear. The purpose of this exercise is to help you understand the importance of S-box in DES. Without the S-box, the cipher becomes linear and can be totally broken.

This exercise will guide you step-by-step to break the linear cipher LDES.

1. Based on the encryption in the figure above, draw a diagram for the corresponding decryption.

2. Implement the encryption / decryption algorithms using C++, Java, or Python.

3. For each key = 00, 01, 10, 11, calculate E(0000), E(1000), E(0100), E(0010), E(0001), E(1100), E(1010), E(1001), E(0110), E(0101), E(0011), E(0111), E(1011), E(1101), E(1110), E(1111).

Verify that, for every key, E(1100) = E(1000) + E(0100) + E(0000).

Write similar equations for E(1010), E(1001), E(0110), E(0101), E(0011), E(0111), E(1011), E(1101),

E(1110), E(1111) in terms of E(0000), E(1000), E(0100), E(0010), E(0001).

This demonstrates that if an adversary knows E(0000), E(1000), E(0100), E(0010), E(0001), he can encrypt any message. In general, for a linear cipher with block size n, if an adversary knows n + 1 pairs of plaintext/ ciphertext, he can encrypt/decrypt any messages without even knowing the key

Part 4. MDES

Consider a block cipher MDES (“mini” DES) which works exactly the same as LDES (Part 3), except that the operation from (I1,I2,I3) to (J1,J2) is based on the following S-box

1. Implement the encryption / decryption algorithms of MDES using C++, Java, or Python.

2. Using MDES, for each key = 00, 01, 10, 11, calculate E(0000), E(1000), E(0100), E(0010), E(0001), E(1100), E(1010), E(1001), E(0110), E(0101), E(0011), E(0111), E(1011), E(1101), E(1110), E(1111).

Verify that the equations that you observe in question 3 now is no longer valid.

1. Implement MDES in two modes: ECB and CBC using C++, Java, or Python. Both modes ECB and CBC do not need message padding. Your program should accept a key as 2-bit binary string, a message as hex string and outputs a ciphertext as a hex string on the console. For example:

YourProgram -key 10 -mode ECB -encrypt f4a5a32
YourProgram -key 01 -mode ECB -decrypt b6f7a11
YourProgram -key 11 -mode CBC -iv a -encrypt 2a45def
YourProgram -key 00 -mode CBC -iv 4 -decrypt b412ab2

Part 5. 4-bits OFB

This part comprises three sections.

Section 1. This task is to implement a 4-bit OFB TEA algorithm using C++, Java, or Python. See the code for TEA in the lecture notes.

Section 2. Encrypt your student number using 4-bit OFB TEA algorithm as devised above.

Section 3. Add all the digits of your student number mod 8. Let the result be c. If c equals 4, then set c as 6. Implement c-bit OFB TEA algorithm, and encrypt your student number using this algorithm.

Compare the time needed to encrypt using 4-bit OFB TEA algorithm and c-bit OFB TEA algorithm, and write your result in the PDF file. Explain what has happened.

Part 6. Synchronous Stream Cipher

The following stream cipher operates on character A-Z one at a time. A character A-Z is mapped to Z26 = {0,1,2,…,25} in the usual way. For a key k ∈ Z26, a key stream k1k2k3 … is generated by the following rule:
.
For a message m = m1m2 …mt, where mi ∈ Z26, the ciphertext c = c1c2 …ct is calculated as follows ci = mi + ki (mod 26)

a. Describe the decryption algorithm.
b. Implement the above algorithm, for both encryption and decryption, using C++, Java, or Python.
c. Encrypt the message WOLLONGONG with key = 5.
d. Decrypt the ciphertext CNLBX with key = 5.