Cryptography, LFSR, GCD, and Fermat's Theorem Assignment

This document presents a complete solution to an AI assignment focused on cryptography. The solution begins with an affine cipher problem, including finding the equation of the cipher and using it for encryption and decryption. It then delves into Linear Feedback Shift Registers (LFSRs), computing the first 20 bits of a given LFSR and determining its period. The assignment also includes a problem involving the Extended Euclidean Algorithm to calculate the Greatest Common Divisor (GCD) of two integers and express it as a linear combination. Finally, the solution applies Fermat's Theorem to a given number, demonstrating a comprehensive understanding of cryptographic principles and mathematical concepts relevant to AI and data security. The document showcases the student's ability to apply these concepts to solve practical problems and provides detailed explanations for each step.

Surname 1
Student’s Name
Professor’s Name
Subject
Date
Question 1
a)
(1, 7) (0, 2)
x1 =1 y1 =0
x2 =7 y2 =2
Calculating the linear equation
(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
Calculating the linear equation
(y- y1) = y2− x1
x2 −x1
(x- x1)

Surname 2
y-0 = 1−0
6−1 (x-1)
y= 1
5(x-1)
y= 1
5(x-1)
Question 1
a)
LSFR is defined as the element of pseudo random generator which generates a set of encryption
keys (Kim 3). The general formula 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 (Gómez 4; Denning 42).
The LFSR equation: xn+5 = xn + xn+3
When x=0, then X0+5 = x0 + x0+3 = 0+0 = 0
When x=1, then X1+5 = x1 + x1+3 = 1+0 = 1
When x=2, then X2+5 = x2 + x2+3 = 0+0 = 0
When x=3, then X3+5 = x3 + x2+3 = 0 = 1
When x=4, then X4+5 = x4 + x4+3 = 0+0 = 0
Thus the LSFR sequence becomes: 0, 1, 0, 1,0……
Therefore, the first 20 bits are: 0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1
b)
The first 20 bit follows a PN-sequence by investigation. The PN-sequences a period generalized
using the formula2n−1. Therefore, the period of LSFR is 2n−1.
Question 2
Definition

Surname 3
Let “a” and “b” be the integers and non-zero. The GCD of a and b, written as the gcd(a,b) , is the
integer “d” with the two main properties :
i) d is a common divisor of a and b i.e d|a and d|b
ii) Ѱ of c, if c is a common divisor of both a and b, then c ≤ d. In other words, for all
integers c, if c|a and c|b, then c ≤d.
Solution
Integers a and b are called relatively prime iff their GCD is 1 (Bhandari 33).
Given two numbers; 4883 and 4369
We have to use the extended Euclidean algorithm to find the GCD of 4883 and 4369 and express
them as a linear combination.
Step 1: Calculating the GCD
4883= 1(4369) +514
Thus 514 = 4883-4369
4883
4369 = 1 rem 514
But
4369
514 = 8 rem 257
And,
4883
514 =9 rem 257
Thus
514
257 = 2 rem 0
Since the remainder is 0, the greatest common divisor is the divisor, 257

Surname 4
Therefore, GCD = 257
Step 2: Expressing GCD as a linear combination
257 = -8(4883) +9(4369)
Therefore, the greatest common divisor of 4883 and 4369 is 257
Number 4
a)
Let n= 391
Factorizing 391 gives; 391= 17*23
n-1 = 390
Φ (n) = Φ (17) Φ = (23) = 16*22 = 352
2390 = 2352,238
29 =512 thus 29= 512(mod391)
238 ≡ 285 (mid391)
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)

Surname 5
2391≡ 238 (mod391) ⇒ 2285(mod391)
b)
2 j ≡ 1 (mod, n)
Applying the Fermat theorem
J = Φ (n) = Φ (391) = 352 thus J = 352
Work Cited
Bhandari, Sandeepak. "A New Era Of Cryptography : Quantum Cryptography". International
Journal On Cryptography And Information Security, vol 6, no. 3/4, 2016, pp. 31-
37. Academy And Industry Research Collaboration Center (AIRCC),
doi:10.5121/ijcis.2016.6403.
D. Denning. “Cryptography and Data Security Addison-Wesley Publishing Company”. 2013.
Gómez, Pardo J. L. Introduction to Cryptography with Maple. Heidelberg: Springer-Verlag,
2013. Internet resource.
Kim, Kwangjo. "Cryptography: A New Open Access Journal". Cryptography, vol 1, no. 1, 2016,
p. 1. MDPI AG, doi:10.3390/cryptography1010001.