Deakin SIT281 Assignment 1: Affine Cipher, LFSR, and GCD Solutions

This document presents solutions to SIT281 Assignment 1, a cryptography assignment from Deakin University. The solutions cover three main problems: (1) determining the keys for an affine cipher given plaintext-ciphertext pairs and encrypting a given text; (2) analyzing a Linear Feedback Shift Register (LFSR), including finding the output sequence and period; and (3) calculating the Greatest Common Divisor (GCD) of two numbers using the Extended Euclidean Algorithm (EEA) and verifying the result. The assignment requires detailed explanations for each step and the use of Maple for verification where specified. The solutions provide step-by-step calculations and explanations for each part of the assignment, including detailed workings for the EEA and LFSR calculations. The document serves as a comprehensive guide for students tackling similar cryptography problems.

Question 1:
a) Plaintext and cipher text pair is given as (1,7) and (0,2).
As the equation for affine cipher is c= ap +b (mod 26) where c is the ciphertext, p is the plaintext, a and b
are the keys which are unknown. With the help of given information the two equation will be created
as :
So for the given plaintext and cipher text the equation will becomes as-
Equation 1:
 7= a*1+b ( mod 26)
7=a + b (mod 26)
Equation 2:
 2= a*0+ b (mod 26)
2= b (mod 26)
Substiuting the value of b(mod 26) in equation 1:
7= a + 2, a=5
Hence the equation will be – c = 5p +2
b) :
The encryption of the given text into affine cipher by using key as a= 5 and b =7:
Plaintext:
Encrypted by Affine:
Decrypt same with key 5 and 7:

Question 2:
a) Given LFSR be xn+5 = xn + xn+3
x0=0, x1=1, x2=0, x3=0, x4=0
n=0 then
x0+5 = x0 + x0+3
x5 = x0 + x3
x5 = 0 + 0
x5 = 0
n=1 then
x1+5 = x1 + x1+3
x6 = x1 + x4
x6 = 1 + 0
x6 = 1
n=2 then
x2+5 = x2 + x2+3
x7 = x2 + x5
x7 = 0 + 0
x7 = 0
n=3 then
x3+5 = x3 + x3+3

x8 = x3 + x6
x8 = 0 + 1
x8 = 1
n=4 then
x4+5 = x4 + x4+3
x9 = x4 + x7
x9 = 0 + 0
x9 = 0
n=5 then
x10 = x5 + x8 = 0 + 1 =1
n=6 then
x11 = x6 + x9 = 1 + 0 =1
n=7 then
x12 = x7 + x10 = 0 + 1 =1
n=8 then
x13 = x8 + x11 = 1 + 1 =1
n=9 then
x14 = x9 + x12 = 0 + 1 =1
n=10 then
x15 = x10 + x13 = 1 + 1 =1
n=11 then

x16 = x11 + x14 = 1 + 1 =1
n=12 then
x17 = x12 + x15 = 1 + 1 =1
n=13 then
x18 = x13 + x16 = 1 + 1 =1
n=14 then
x19 = x14 + x17 = 1 + 1 =1
The 20 bits are 11111111110101000010
b) The period of it is 2n – 1 = 220 - 1 = 1048575
Question 3: gcd of 4883 and 4369 using EEA:
Writing value of a , b , q (quotient of a/b) and r (reminder of a/b)
a b q r
4883 4369 1 514
It is the first row hence writing s1 and s2 as 1 and 0
a b q r s1 s2
4883 4369 1 514 1 0
This is still the first row, so s3 = s1 - q × s2 = 1-0 =1
a b q r s1 s2 S3
4883 4369 1 514 1 0 1

It is the first row hence writing t1 and t2 as 0 and 1
a b q r s1 s2 s3 t1 t2
4883 4369 1 514 1 0 1 0 1
t3 = t1 - q × t2 = 0 - 1 * 1 = -1.
a b q r s1 s2 s3 t1 t2 t3
4883 4369 1 514 1 0 1 0 1 -1
Now writing for the second row:
a b q r s1 s2 s3 t1 t2 t3
4883 4369 1 514 1 0 1 0 1 -1
4369 514 8 257 0 1 -8 1 -1 9
s3=s1-qxs2= 0-8*1= -8
t3=t1-qxt2= 1-8*-1= 9
Now writing for the third row:
a b q r s1 s2 s3 t1 t2 t3
4883 4369 1 514 1 0 1 0 1 -1
4369 514 8 257 0 1 -8 1 -1 9
514 257 2 0 1 -8 17 -1 9 1
s3=s1-qxs2= 1-2*-8= 17
t3=t1-qxt2= -1-2*-1= 1
As in the third row the reminder becomes zero hence we are done:
The final is:
 gcd(161, 28) = 257

 s = -8
 t = 9
Verifying answer:
s × a + t × b = gcd(a, b).
-8 × 4883 + 9 × 4369 = - 39,064 + 39,321 = 257
Which is verified from above.
Hence the gcd (4883, 4369) = 257
Question 4:
a) Maple gives below result:
> 2^390 mod 391;
It gives 285 which is not the congruent to 1 mod n.
b) For doing this we have used Euler’s which states that, as gcd (2.391) =1 then 2^phi(391) will be 1.
Hence maple gives:
So we can conclude exponent j =352 works.