Deakin University SIT281 Trimester 2 Cryptography Assignment Solution

This document presents a solved cryptography assignment, addressing several key concepts. The solution includes the application of affine ciphers, linear feedback shift registers (LFSR), and the extended Euclidean algorithm to find the greatest common divisor (GCD). It also covers the application of Fermat's theorem. The assignment demonstrates the student's ability to solve problems related to cryptographic principles, including calculations and explanations. The document offers a comprehensive breakdown of each question, along with references to relevant literature, providing a solid foundation for understanding cryptographic concepts. The assignment is designed for a course at Deakin University, SIT281, and is suitable for students studying cryptography.

Running head: CRYPTOGRAPHY 1
Cryptography
Student Name
Institution

CRYPTOGRAPHY 2
Question 1
a)
(1, 7) (0, 2)
x1 =1 y1 =0
x2 =7 y2 =2
Equation of line
(y- y1) = y2− x1
x2 −x1
(x- x1)
y-0 = 2−0
7−1 (x-1)
y= 2
6 (x-1)
y= 1
3(x-1)
b)
(1, 6) (0, 1)
x1 =1 y1 =0
x2 =6 y2 =1
Equation of line
(y- y1) = y2− x1
x2 −x1
(x- x1)
y-0 = 1−0
6−1 (x-1)
y= 1
5(x-1)
y= 1
5(x-1)

CRYPTOGRAPHY 3
Question 1
a)
LSFR I the main element of pseudo random generator used to generate a set of encryption keys
(González Vasco & Steinwandt, 2008). LSFR are easily generalized in any finite model; GF (p).
LSFR is easily implemented in software and hardware thus they are widely applied in stream
cipher (Bhandari, 2016; Pardo & Luis, 2013).
The LFSR equation is given as: xn+5 = xn + xn+3
When x=0
X0+5 = x0 + x0+3 = 0+0 = 0
When x=1
X1+5 = x1 + x1+3 = 1+0 = 1
When x=2
X2+5 = x2 + x2+3 = 0+0 = 0
Thus the sequence becomes: 0, 1, 0……
Therefore, the first 20 bits : 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,1
b)
By investigation; the first 20 bit follows a PN-sequence. A PN-sequence and the pseudo noise
sequences have a period of the general formula2n−1. Therefore, the period is 2n−1.
Question 2
Definition

CRYPTOGRAPHY 4
Let “a” and “b” be the integers that are not both zero. The greatest common divisor of a and b,
denote gcd(a,b) , is the integer “d” with the following properties :
i) “d” is a common divisor of “a” and “b”. in other words, d|a and d|b
ii) For all integers c, if c is a common divisor of both “a” and “b”, then “c” is less than or
equal to “d”. In other words, for all integers c, if c|a and c|b, then c≤d.
Integers “a” and “b” are called relatively prime if and only if their GCD is 1 (Kim, Wu &
Phan, 2018).
Given the numbers; 4883 and 4369
The objective is to use the extended Euclidean algorithm to find the greatest common divisor of
4883 and 4369 and them in a linear combination.
Step 1: Calculating the GCD
4883= 1(4369) +514
⇒ 514 = 4883-4369
4883
4369 = 1 remainder 514
But
4369
514 = 8 remainder 257
And,
4883
514 =9 remainder 257
Thus
514
257 = 2 remainder 0
Since the remainder is zero, the GCD is the divisor, 257

CRYPTOGRAPHY 5
GCD = 257
Step 2: expressing the number in linear combination
257 = -8(4883) +9(4369)
Therefore, the GCD of 4883 and 4369 is 257
Number 4
a)
Let n= 391 = 17*23
n-1 = 390
Φ (n) = Φ (17) Φ = (23) = 16*22 = 352
2390 = 2352,238
29 =512 thus 29= 512(mod391)
238 ≡ 285 (mid391)
Now using Fermat Theorem with a=2, n=391ged (a, n) =1
So,
aΦ(n ) = 1(mod, n)
2Φ(n) = 1(mod, n) ⇒ 2352 ≡≡1(mod391)
2391−1 =2390 = 2352,238
Thus
2391−1 ≡2352 =2352,238(mod391)
2390 ≡238(mod391)
2391≡ 238 (mod391) ⇒ 2285(mod391)
b)
2 j ≡ 1 (mod, n)

CRYPTOGRAPHY 6
By Fermat theorem
J = Φ (n) = Φ (391) = 352
So, J = 352
References
Bhandari, S. (2016). A New Era of Cryptography: Quantum Cryptography. International
Journal on Cryptography and Information Security, 6(3/4), 31-37. doi:
10.5121/ijcis.2016.6403
González Vasco, M., & Steinwandt, R. (2008). Applications of algebra to cryptography. Discrete
Applied Mathematics, 156(16), 3071. doi: 10.1016/j.dam.2008.01.025
Kim, J., Wu, H., & Phan, R. (2018). Cryptography and Future Security. Discrete Applied
Mathematics, 241, 1. doi: 10.1016/j.dam.2018.03.001
Pardo, G., & Luis, J. (2013). Introduction to cryptography with Maple. Choice Reviews
Online, 50(12), 50-6806-50-6806. doi: 10.5860/choice.50-6806