Cryptography and Mathematics: LSFR, GCD and Fermat Theorem

This document explains LSFR, GCD and Fermat Theorem in Cryptography. LSFR is used to generate encryption keys, GCD is used to find the greatest common divisor and Fermat Theorem is used to solve mathematical problems. The document also includes equations and examples to help understand the concepts better.

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