Lecture

Cryptography 01
Introduction to Number Theory

Mr. Syed Muhammad Sajjad

Senior Lecturer,
Department of Cyber-Security and Data Science
Riphah Institute of Systems Engineering (RISE),
Riphah International University, Islamabad, Pakistan.
 Instructor
 Mr. Syed Muhammad Sajjad muhammad.sajjad@riphah.edu.pk,

• PhD. Information Security (in progress) from Riphah Institute of Systems

Engineering (RISE), Riphah International University (RIU), Islamabad

• Currently working as Senior Lecturer at Riphah Institute of Systems

Engineering (RISE)

• Ms. Maira Sultan maira.sultan@riphah.edu.pk

• MS Information Security (in progress) from Riphah Institute of Systems

Engineering (RISE), Riphah International University (RIU), Islamabad

• Currently working as Teaching Fellow at Riphah Institute of Systems

Engineering (RISE)
2
Tentative Course Contents
• Introduction to Number Theory
• Finite Fields
• Classical Encryption Techniques
• Block Cipher and Data Encryption Standards
• Advance Encryption Standard
• Block Cipher Operations
• Random Bits Generation and Streams
• Public Key Cryptography and RSA
• Other Public Key Cryptosystems
• Cryptographic Hash Functions
• Message Authentication Codes
• Digital Signature
• Key Management and Distribution
3
 Required Tools For Labs
• Oracle Virtual box/VM Ware 
• https://www.virtualbox.org/wiki/Downloads
• SEEDS Ubuntu 16.04 32bit VM and its User Manual 
from seeds lab website 
http://www.cis.syr.edu/~wedu/seed/lab_env.html
• Crypt‐tool latest version 
• https://www.cryptool.org/en/ct2‐downloads

4
 Marks Distribution of course
• Fist Assessment (After 4 Lectures) 15%

• Second Assessment (After 8 Lectures) 15%

• Assignments 10%

• Quizzes 10%

• Class Participation 5%

• Final 30% theory +15% Practical

5
 Recommended Readings
• Cryptography and Network Security
• 7th Edition
• By: William Stallings

• Selected Research Papers & Standard Documents, RFCs

6
 Introduction to Cryptography
• Cryptography
• – Science of secret writing with the goal of hiding the 
meaning of a message

• – In a broader sense
• Mathematical techniques used to mangling the
information into apparently unintelligible form

• About securing the communication in the presence 
of adversaries

7
 Introduction to Cryptography
• Cryptanalysis
• – The study of methods for obtaining the
meaning of encrypted information without
accessing the secret information

• Cryptology
• – Cryptography + Cryptanalysis

8
 Divisibility
• We say that a nonzero b divides a if a = mb for 
some m, where a, b, and m are integers

• b divides a if there is no remainder on division

• The notation b | a is commonly used to mean b 
divides a

• If b | a we say that b is a divisor of a
The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24
13 | 182; ‐ 5 | 30; 17 | 289; ‐ 3 | 33; 17 | 0

9
 Properties of Divisibility
• If a | 1, then a = ±1
• If a | b and b | a, then a = ±b
• Any b ≠ 0 divides 0 
• If a | b and b | c, then a | c

11 | 66 and 66 | 198 = 11 | 198

• If b | g and b | h, then b | (mg + nh) for arbitrary 

integers m and n
10
 Properties of Divisibility
• To see this last point, note that:
• If b | g , then g is of the form g = b * g1 for some integer g1
• If b | h , then h is of the form h = b * h1 for some integer h1
• So:
• mg + nh = mbg1 + nbh1 = b *  (mg1 + nh1 ) 
and therefore b divides mg + nh

b = 7;  g = 14;  h = 63;  m = 3;  n = 2

7 | 14 and 7 | 63.
To show 7 (3 * 14 + 2 * 63),
we have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9),
and it is obvious that 7 | (7(3 * 2 + 2 * 9)).
11
 Division Algorithm

• Given any positive integer n and any 
nonnegative integer a, if we divide a by n we 
get an integer quotient q and an integer 
remainder r that obey the following 
relationship:

a = qn + r 0 ≤ r < n; q = [a/n]

12
13
 • One of the basic 
techniques of number 
Euclidean  theory

Algorithm • Procedure for 
determining the greatest 
common divisor of two 
positive integers

• Two integers are 
relatively prime if their 
only common positive 
integer factor is 1

14
Greatest Common Divisor 
(GCD)
• The greatest common divisor of a and b is the largest 
integer that divides both a and b
• We can use the notation gcd(a,b)  to mean the 
greatest common divisor of a and b
• We also define gcd(0,0) = 0
• Positive integer c is said to be the gcd of a and b if:
• c is a divisor of a and b
• Any divisor of a and b is a divisor of c

• An equivalent definition is:
gcd(a,b) = max[k, such that k | a and k | b]
15
 GCD
• Because we require that the greatest common divisor be positive, 
gcd(a,b) = gcd(a,‐b) = gcd(‐a,b) = gcd(‐a,‐b)

• In general, gcd(a,b) = gcd(| a |, | b |)
gcd(60, 24) =  gcd(60, ‐ 24) =  12  

• Also, because all nonzero integers divide 0, we have gcd(a,0) = | a |
• We stated that two integers a and b are relatively prime if their 
only common positive integer factor is 1; this is equivalent to 
saying that a and b are relatively prime if gcd(a,b) = 1
8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 
8, and the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on 
both lists.
16
 Example GCD(1970,1066)
1970 = 1 x 1066 + 904  gcd(1066, 904)
1066 = 1 x 904 + 162  gcd(904, 162)
904 = 5 x 162 + 94  gcd(162, 94)
162 = 1 x 94 + 68  gcd(94, 68)
94 = 1 x 68 + 26  gcd(68, 26)
68 = 2 x 26 + 16  gcd(26, 16)
26 = 1 x 16 + 10  gcd(16, 10)
16 = 1 x 10 + 6  gcd(10, 6)
10 = 1 x 6 + 4  gcd(6, 4)
6 = 1 x 4 + 2  gcd(4, 2)
4 = 2 x 2 + 0  gcd(2, 0)

17
18
19
 Table 2.1
Euclidean Algorithm Example

20
 Modular Arithmetic
• The modulus
• If a is an integer and n is a positive integer, we 
define a mod n to be the remainder when a is 
divided by n; the integer n is called the modulus
• Thus, for any integer a:
a =  qn +  r 0 ≤ r < n;  q = [a/ n]
a = [a/ n] *  n + ( a mod n)

11 mod 7 = 4; - 11 mod 7 = 3

21
 Modular Arithmetic

• Congruent modulo n
• Two integers a and b are said to be congruent 
modulo n if (a mod n) = (b mod n)
• This is written as a = b(mod n)2
• Note that if a = 0(mod n), then n | a

73 ≡ 4 (mod 23);
21 ≡ - 9 (mod 10)
-11 ≡ 5 mod 8

22
Properties of Congruences
• Congruences have the following properties:

1. a = b (mod n) if n (a – b)

2. a = b (mod n) implies b = a (mod n)

3. a = b (mod n) and b = c (mod n) imply a = c (mod n)

• To demonstrate the first point, if n (a ‐ b), then (a ‐ b) = kn for 

some k
• So we can write a = b + kn
• Therefore, (a mod n) = (remainder when b + kn is divided by n) = 
(remainder when b is divided by n) = (b mod n)
23 ≡ 8 (mod 5) because 23 - 8 = 15 = 5 * 3
- 11 ≡ 5 (mod 8) because - 11 - 5 = - 16 = 8 * (- 2)
81 ≡ 0 (mod 27) because 81 - 0 = 81 = 27 * 3
23
 Modular Arithmetic
• Modular arithmetic exhibits the following properties:
1.  [(a mod n) + (b mod n)] mod n = (a + b) mod n

2.  [(a mod n) ‐ (b mod n)] mod n = (a ‐ b) mod n

3.  [(a mod n) * (b mod n)] mod n = (a * b) mod n

• We demonstrate the first property:
• Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + 
jn for some integer j and b = rb + kn for some integer k
• Then:
(a + b) mod n = (ra + jn + rb + kn) mod n
= (ra + rb + (k + j)n) mod n
= (ra + rb) mod n
= [(a mod n) + (b mod n)] mod n
24
 Remaining Properties:
• Examples of the three remaining properties:

11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) - (15 mod 8)] mod 8 = - 4 mod 8 = 4
(11 - 15) mod 8 = - 4 mod 8 = 4
[(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5
(11 * 15) mod 8 = 165 mod 8 = 5

25
 Table 2.2(a)
Arithmetic Modulo 8
 Table 2.2(b)
Multiplication Modulo 8
 Table 2.2(c)

Additive 
and 
Multiplicative 
Inverse 
Modulo 8
28
 Table 2.3
Properties of Modular Arithmetic for Integers in Zn

29
 Euclidean Algorithm 
 An efficient way to find the GCD(a,b)
 Uses theorem that: 
• GCD(a,b) = GCD(b, a mod b) 
 Euclidean Algorithm to compute GCD(a,b) is: 
 Euclid(a,b)  
if (b=0) then return a; 
else return Euclid(b, a mod b);
Examples: gcd (55,22) = gcd(22, 55 mod 22) = 
gcd (22, 11) =11
gcd (18, 12) =gcd (12, 18 mod 12) =
gcd (12, 6)= 6
gcd (11, 10) =gcd (10, 11 mod 10)= gcd (10, 1)
gcd (1, 0)= 1

30
 Prime Numbers
• Prime numbers only have divisors of 1 and itself 
• They cannot be written as a product of other numbers 

• Prime numbers are central to number theory

• Any integer a > 1 can be factored in a unique way as

a = p1 a1 * p2 a2 * . . . * pp1 a1

where p1 < p2 < . . .  < pt are prime numbers and where 

each ai is a positive integer

• This is known as the fundamental theorem of 
arithmetic
31
 Prime Numbers
• Prime numbers only have divisors of 1 and self 
• they cannot be written as a product of other 
numbers 
• note: 1 is prime, but is generally not of interest 

• eg. 2,3,5,7 are prime, 4,6,8,9,10 are not

• Prime numbers are central to number theory

32
 Table 2.5 
Primes Under 2000 

33
 Prime Factorisation
 To factor a number n is to write it as a product of other numbers: 
n=a x b x c 

 Note that factoring a number is relatively hard  compared to 
multiplying the factors together to generate the number 

 The prime factorisation of a number n is when its written as a 

product of primes 
• eg. 91=7x13 ; 3600=24x32x52

34
 Relative Prime Numbers & 
GCD
 Two numbers a, b are relatively prime if have no 
common divisors apart from 1 
• eg. 8 & 15 are relatively prime since factors of 8 are 
1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only 
common factor 
 Conversely can determine the greatest common 
divisor by comparing their prime factorizations and 
using least powers
• eg. 300=22x31x52 18=21x32 hence 
GCD(18,300)=21x31x50=6

35
 Fermat's Theorem
• States the following:
• If p is prime and a is a positive integer not 
divisible by p then

ap‐1 ≡ 1 (mod p) (a & p relative prime)

• An alternate form is:
• If p is prime and a is a positive integer then

ap ≡ a (mod p) (a & p not relative prime)

36
 Fermat's Theorem
 ap‐1 ≡ 1 (mod p)
• where p is prime and gcd(a,p)=1
• Example a=3, p=5, 34 ≡ 1 (mod 5)
• 81 ≡ 1 (mod 5)
 Also known as Fermat’s Little Theorem
 Also have: ap ≡ a (mod p)
• Example a=10, p=5 
• 105 ≡ 10 (mod 5)
• 10000 ≡ 10 (mod 5)
37
Euler Totient Function ø(n)
 When doing arithmetic modulo n 

 Complete set of residues is: 0……..n‐1 

 Reduced set of residues is those numbers (residues) 
which are relatively prime to n 
• E.g for n=10, 
• complete set of residues is {0,1,2,3,4,5,6,7,8,9} 
• reduced set of residues is {1,3,7,9} 

 Number of elements in reduced set of residues is 
called the Euler Totient Function ø(n) 

38
Euler Totient Function ø(n)
 To compute ø(n) need to count number of residues to 
be excluded

 In general need prime factorization,
• for p (p prime)  ø(p)=p‐1 
• for p.q (p,q prime)   ø(p.q)=(p‐1)x(q‐1)
• eg.
• ø(37) = 36
• ø(21) = (3–1)x(7–1) = 2x6 = 12

39
 Table 2.6
Some Values of Euler’s Totient Function ø(n)

40
 Euler's Theorem

• States that for every a and n that are relatively 
prime:

aø(n) ≡ 1(mod n) (a & n relative prime)

• An alternative form is:

aø(n)+1 ≡ a(mod n) (a & n not relative prime)

41
 Euler's Theorem
• A generalisation of Fermat's Theorem 
aø(n) ≡ 1 (mod n) for any a,n where gcd(a,n)=1 eg. 
a=3;n=10; ø(10)=4;  hence 34 = 81 = 1 mod 10
• a=2;n=11; ø(11)=10;
• hence 210 = 1024 = 1 mod 11
• Also have: aø(n)+1 ≡ a (mod n)

42
 Chinese Reminder Theorem 
• Let m1, m2……..mk be integers that are pairwise relatively 
primes. M be product of all the mi. Let b1,b2…..bk be integers. 
Then the set of congruence's 

• x ≡ b1 (mod m1),x ≡ b2 (mod m2)……… x ≡ bk (mod mk)

• has a unique solution modulo M.

• Example 

• x ≡ 4 mod 5, x ≡ 6 mod 9, x  ≡ 7 mod 11

43
 Home Task 
• Install Oracle Virtual box or VM Ware Workstation
• https://www.virtualbox.org/wiki/Downloads

• Visit SEED LABS website
http://www.cis.syr.edu/~wedu/seed/index.html
• Install SEEDS Ubuntu 16.04 32bit VM and its User 
Manual  from seeds lab website 
http://www.cis.syr.edu/~wedu/seed/lab_env.html
• Install Crypt‐tool latest version 
• https://www.cryptool.org/en/ct2‐downloads
• Bring laptops in every class
 Summary
• Divisibility and the division  • Fermat’s Theorem
algorithm
• Euler’s totient function
• The Euclidean algorithm
• Greatest Common Divisor • Euler’s Theorem
• Finding the Greatest Common 
Divisor • Testing for primality
• Miller‐Rabin algorithm
• A deterministic primality algorithm
• Modular arithmetic • Distribution of primes
• The modulus
• Properties of congruences • The Chinese Remainder 
Theorem
• Modular arithmetic operations
• Properties of modular arithmetic • Discrete logarithms
• Euclidean algorithm revisited • Powers of an integer, modulo n
• The extended Euclidean algorithm • Logarithms for modular arithmetic
• Calculation of discrete logarithms
• Prime numbers