Mathematics of

Cryptography-I

Dr. Bimal Kumar Meher

Associate Professor, Dept. of CSE
Silicon Institute of Technology
Objective
 Euclidean algorithm
 Extended Euclidean algorithm(EEA)
 Modular arithmetic
 Matrix and Residue matrix
Set of Integers and Integer Division

In integer arithmetic, if we divide a by n, we can

get q and r .
Answer the following Question

• When we use a computer or a calculator, r and q are

negative when a is negative.
• How can we make r positive?

-255=(-23 x 11) + (-2)

• The solution is simple, we decrement the value of q by 1
and we add the value of n to r to make it positive.
Divisbility

If a is not zero and we let r = 0 in the

division relation, we get

a=q×n

If the remainder is zero, n a

If the remainder is not zero, n a
Example: Divisibility
a. The integer 5 divides the integer 30 because
30 = 6 × 5. So, we can write 5 30

b. The number 8 42 because 42 = 5 × 8 + 2 has

a remainder of 2.
Properties: Divisibility

Property 1: if a|1, then a = ±1.

Property 2: if a|b and b|a, then a = ±b.

Property 3: if a|b and b|c, then a|c.

Property 4: if a|b and a|c, then

a|(m × b + n × c), where m
and n are arbitrary integers
Continued
Example

Answer the followings:

a. Given 3|15 and 15|45, Can we say 3|45?

b. Given 3|15 and 3|9, Can we say 3|66?

m=2
n=4
mb+nc=2x15+4x9=66
Divisibility

Fact 1: The integer 1 has only one

divisor, itself.

Fact 2: Any positive integer has at least

two divisors, 1 and itself (but it
can have more).
Common divisors of two integers
Greatest Common Divisor(GCD)

The greatest common divisor of two positive

integers is the largest integer that can divide
both integers.

Euclidean Algorithm
Fact 1: gcd (a, 0) = a
Fact 2: gcd (a, b) = gcd (b, r), where r is
the remainder of dividing a by b

Example: a=60, b=25

Gcd(60,25)=gcd(25,10)=gcd(10,5)=gcd(5,0)=Fact 1=5
Finding GCD(a,b) by using Euclidean Algo.
Relatively prime or Coprime

Note

When gcd (a, b) = 1, we say that a and b

are relatively prime.
Examples:
gcd(13,5)=1 => 13 and 5 are relatively prime
gcd(12,5)=1 => 12 and 5 are relatively prime
gcd(10,2)=2
gcd(9,3)=3
gcd(9,5)=1 => 9 and 5 are relatively prime
Finding GCD by using Euclidean Algo.
Example
Find the greatest common divisor of 25 and 60.
Solution:
We have gcd (25, 60) = 5.
GCD
Do by yourself
Find the greatest common divisor of 2740 and 1760.
Solution
We have gcd (2740, 1760) = 20.
Extended Euclidean Algorithm (EEA)
Problem: Given two integers a and b, find other
two integers, s and t, such that

• This equation is also called Bezout’s identity or

Bezout’s Lemma.
• s and t are called Bezout’s coefficients for (a,b).
• The EEA can be used to calculate the gcd (a,
b) and values of s and t.
Process of Extended Euclidean Algorithm
Extended Euclidean Algorithm(EEA)
Solving Problem by using EEA
Example
Given a = 161 and b = 28, find gcd (a, b) and the
values of s and t of Bezout’s identity (s x a + t x b
= gcd(a,b).
Solution
We get gcd (161, 28) = 7, s = −1 and t = 6.
Solving Problem by using EEA
Example
Given a = 17 and b = 0, find gcd (a, b) and the
values of s and t of Bezout’s identity (s x a + t x b
= gcd(a,b). .
Solution
We get gcd (17, 0) = 17, s = 1, and t = 0.
MODULAR ARITHMETIC

 If a is an integer and n is a positive integer,

we define r as the remainder (residue) such
as r = a mod n .
 So, we can write a = q x n + r.
 The integer n is called the modulus.
Examples: Modulo operation
Find the result of the following operations:
a. 27 mod 5 b. 36 mod 12
c. −18 mod 14 d. −7 mod 10
Solution:
a. Dividing 27 by 5 results in r = 2
b. Dividing 36 by 12 results in r = 0.
c. Dividing −18 by 14 results in r = −4. After
adding the modulus r = 10
d. Dividing −7 by 10 results in r = −7. After
adding the modulus to −7, r = 3.
Congruence
 This can be written with the help of a congruence
operator (≡) i.e. a ≡ b (mod n)
 Two integers a and b are said to be congruent
modulo n, if (a mod n)=(b mod n)
Examples:

Can we say 12 ≡ 23 mod 8 ?

14 ≡ 36 mod 7 ?
Properties of Congruence
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
Examples: a ≡ c (mod n)

Example (Property 3):

• 2 ≡ 12 mod 10 and 12 ≡ 22 mod 10,
then 2 ≡ 22 mod 10
Concept of congruence relationship
The set Zn
• The (mod n) operator maps all integers into
the set of integers {0, 1, 2, …, (n-1)}
• This is also called the set of least residues
modulo n, or Zn
• What are the elements of set Z2 ,Z5 , Z10 ?
Z2= {0,1}
Z5 ={0, 1, 2, 3, 4}
Z10={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Example: Modulo operator

Can you give an example of modulo operator, used

in our daily life ?

• We use a clock to measure time.

• Our clock system uses modulo 12 arithmetic.
• However, instead of a 0 we use the number 12.
Operations on set Zn

• The three binary operations (+,  , )

defined on set Z can also be applied to
set Zn.
• The operations are done as usual just
like set Z, but, if the result exceeds
the numbers defined in Zn then it is
converted to a number in Zn using the
mod operator.
• This is called modular arithmetic
Zn: Examples
Perform the following operations (the inputs
come from Zn):
1. Add 7 to 14 in Z15.
2. Subtract 11 from 7 in Z13.
3. Multiply 11 by 7 in Z20.
Zn:Properties
Figure: Properties of mod operator
Examples: Operations in Zn

 (1,723,345 + 2,124,945) mod 11

= (8 + 9) mod 11 = 6
 (1,723,345 − 2,124,945) mod 11
= (8 − 9) mod 11 = 10
 (1,723,345 × 2,124,945) mod 11
= (8 × 9) mod 11 = 6
More Examples: Operations in Zn

Compute the followings:

1012 mod 3 = 1
1050 mod 7 = 350 mod 7 = 2
54 mod 7 = 2

32x25=(32)25=925 mod 7= (9 mod 7)25 =225 mod 7

225(mod 7)=2 x 224 mod 7=2 x (23x8)mod 7
=2 x (23mod 7)8= 2x18 mod 7=2 x 1=2

Square and Multiply Technique

Inverse of a number in Zn

• In modular arithmetic, we often need to

find the inverse of a number relative to
an operation.
• It can be an additive inverse (relative to
an addition operation(+)) or
• a multiplicative inverse(relative to a
multiplication operation ()).
Additive Inverse

In Zn, two numbers a and b are additive inverses

of each other if

Note

• In modular arithmetic, each integer has an

additive inverse.
• The sum of an integer and its additive inverse is
congruent to 0 modulo n.
Examples

1. Find the additive inverse of 4 in Z7

Answer: 3

2. Find all additive inverse pairs in Z10.

Answer:
There are six pairs of additive inverses:
(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), and (5, 5).
Multiplicative Inverse

In Zn, two numbers a and b are the multiplicative

inverse of each other if

Note
• In modular arithmetic, an integer may or may
not have a multiplicative inverse.
• When it has, the product of the integer and its
multiplicative inverse is congruent to 1 modulo n.
Examples
Example 1
Find the multiplicative inverse of 7 and 8 in Z10.
Multiplicative inverse of 7 is 3, but 8 has no
multiplicative inverse.
Note: gcd can help us to quickly find out whether a given number
has multiplicative inverse or not.
gcd(10,7)=1=> 7 has multiplicative inverse in modulo 10
gcd (10, 8) = 2 ≠ 1 => 8 has no multiplicative inverse in modulo 10
Example 2
Find all multiplicative inverses in Z10.
There are only three pairs: (1, 1), (3, 7) and (9, 9). The
numbers 0, 2, 4, 5, 6, and 8 do not have a multiplicative
inverse.
Continued
Example 3

Find all multiplicative inverse pairs in Z11.

We have seven pairs:
(1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9), and (10, 10).
How to find out Multiplicative Inverse
of BIG Number?

Note
• The Extended Euclidean algorithm(EEA) finds
the multiplicative inverses of b in Zn when n
and b are given and gcd (n, b) = 1.
• The multiplicative inverse of b is the value of t
after being mapped to Zn.
Using Extended Euclidean algorithm to
find Multiplicative inverse
Continued
Example
Find the multiplicative inverse of 11 in Z26.

The gcd (26, 11) is 1; the inverse of 11 is 7(=19).

Continued
Example
Find the inverse of 12 in Z26.

The gcd (26, 12) is 2; the inverse does not exist.

Zn and Zn*

Note
• We need to use Zn when additive inverses are
needed
• We need to use Zn* when multiplicative
inverses are needed.
Two More Sets

• Cryptography often uses two more sets:

• Zp and Zp*.
• The modulus in these two sets is a prime
number.
What are the uses of Additive and
Multiplicative inverses in
Cryptography?
 When a sender uses a key for encryption, he
may choose an integer from the set Zn or Zn*
depending on the algorithms used.
 If he chooses from Zn, the receiver has to find
the additive inverse of that integer for getting
the key for decryption.
 Similar logic applies for multiplicative inverse
in Zn*.
MATRICES

• Matrices are widely used in Cryptography.

• A matrix is a linear array of l x m elements.
Examples of Matrices
Operations and Relations
Example

Addition and Subtraction

Continued
Example

Multiplication of a row matrix by a column matrix

Continued
Example

Multiplication of a 2 × 3 matrix by a 3 × 4 matrix

Continued
Example

Scalar multiplication
Inverse of a Square matrix

The inverse of a matrix A , denoted as A-1

should hold the following relation:
A A-1 =I,
where I is the identity matrix

Note

Multiplicative inverses are only defined

for square matrices.
Inverse(Continued)

a b
For A= ,
c d 

the inverse can be found by using the formula:

1 1  d b  1  d b 
A     
det A  c a  ad  bc  c a 
Residue Matrix and Inverse
• Cryptography uses residue matrices.
• Matrices where all elements are in Zn.
• A residue matrix has a multiplicative
inverse if gcd (det(A), n) = 1.
Example
Find the inverse of a matrix  7 3
  mod 26
1 2 
12 21
The inverse of the given matrix   mod 26
7 3 