Maths Introduction for Cryptography

Department of ISE
Faculty of Computing - SLIIT

Kavinga Yapa Abeywardena – [email protected]

Faculty of Computing, Information Systems Engineering Department
Sri Lanka Institute of Information Technology
Outline

1 Mathematical Objects

2 Mathematical Operations and Algorithms

3 Basic Number Theory

Kavinga Yapa Abeywardena – [email protected] Maths Introduction 2 / 36

Integers

Mathematical symbol: Z
Numbers such as -3,-1,0,10,2000,...
(Almost) most natural mathematical object
Good for computer arithmetic, if not too big
Surprisingly difficult to prove mathematical properties
(Proving is for mathematicians)
Number theory = "Queen of mathematics"
Believed to be without serious applications, before the invention of
cryptography
Will need large numbers for good security
Rational numbers: Fractions

Maths Introduction 3 / 36
Number systems

Number system: a scheme to represent integers (or rationals)

using digits
Traditionally humans have used the decimal system (Why?)
Writing d in a number system with basis b means computing
d(b) = dk bk + . . . + d1b + d0 (di ∈ { 0 . . . b − 1} )

Here b is the basis and the di the digits

Decimal system: b = 10
Binary: b = 2, hexadecimal: b = 16, ternary: b = 3
Can also represent fractions, using negative powers of b

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 4 / 36

Mini-Exercise 1

Convert 1010110(2) into decimal notation.

Write the integer 12 as a decimal, binary and ternary number.
Convert 0.011(2) into decimal notation.
Write 5 as a binary (optional: ternary) number.
8

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 5 / 36

Prime Numbers

Definition: a prime number is any integer >1 that is divisible only

by itself and 1.
Examples: 2, 3, 5, 7, 11, 47, 1997,. . .
There is an infinite number of prime numbers
Computers can decide relatively efficiently whether a given
number is a prime number
Every non-zero integer can be written uniquely (up to sign) as
product of prime numbers:
Example: 10 = 2 ∗5, 12 = 2 ∗2 ∗3, 19 = 19
Factorisation of an integer: writing a given integer as product of
prime numbers (Prime Factorization)
This is a very difficult task for large integers!

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 6 / 36

Mini-Exercise 2

Decompose into prime factors

33
45
1001
2013

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 7 / 36

Polynomials

Z[x]: ring of univariate polynomials with coefficients in the integers

Xd
f (x) ∈ Z[x] : f (x) = ai x i
i=0
d = deg f is the degree of f
ai are the coefficients Example:
f (x) = 10x 2 − 5x + 1
Evaluation of f (x) at x = x0: substitute for value and compute the
expression
Interpolation: reconstruction of polynomial f with degree d, using
d + 1 distinct points (xi , f (xi ))

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 8 / 36

Mini-Exercise 3

Given f (x) = 3x 2 − 4x + 5, evaluate this polynomial at the points

0,1 and 2
Perform interpolation using the points (1, 1) and (2, −3) in order to
compute a polynomial g(x) of degree 1, satisfying g(1) = 1 and
g(2) = −3.

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 9 / 36

Outline

1 Mathematical Objects

2 Mathematical Operations and Algorithms

3 Basic Number Theory

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 10 / 36

Boolean Algebra

x y x AND y x OR y x ⊕y x⇒y x ⇔y
0 0 0 0 0 1 1
0 1 0 1 1 1 0
1 0 0 1 1 0 0
1 1 1 1 0 1 1

Used in logics/mathematical proofs

Also: computers use binary numbers internally
Reason: easy to represent digit value of 0 or 1 in hardware
Arithmetic can then be implemented using logical operations

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 11 / 36

Mini-Exercise 4

Compute, by inserting leading 0s if needed:

101101 ⊕ 111
101 OR 1100

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 12 / 36

Integers and Their Arithmetic

We consider integer numbers: union of positive and negative

numbers, including 0
Examples: 10, 0, -12, 19
We can perform addition, subtraction, multiplication and division
with remainder
Examples for division:
10:5 = 2 since 10 = 2*5 + 0 (remainder 0)
19:2 = 9 since 19 = 9*2 + 1 (remainder 1)
23:5 = 4 since 23 = 4*5 + 3 (remainder 3)
We say that a is divisible by b if the division of a by b gives
remainder 0
In the above example, 10 is divisible by 5

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 13 / 36

The Modulo Operation – Definition

Introducing a mod m: the modulo operation is defined

as remainder(r) of division of a by m.
This is equivalent to saying m divides a − r. (This is the
Mathematician’s preferred definition.)
Properties:
a mod m is always smaller than m
a mod m= a if a < m
a + k ·m mod m = a mod m (useful if a is negative)

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 14 / 36

The Modulo Operation – Examples

You can use the Calculator in Windows to evaluate the mod

function
Small numbers can be done without a tool
19 mod 5 = 4
10 mod 5 = 0
19 mod 2 = 1
23 mod 5 = 3
We know that 25h is the same as 1h
The clock is counted modulo 24, so m = 24

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 15 / 36

The Modulo Operation – Notations

Unfortunately, over time mathematicians have adopted different

notations
Functional notation: mod(a, m)
Example: The input a = 15 and m = 4 gives the output 3
Equational notation: a ≡ r (mod m) means a mod m = a mod m
We also write a ≡ r (m)
Examples:
15 ≡ 11( mod3)
4 ≡ 19 ≡ 24 ≡ −1 (5)

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 16 / 36

Mini-Exercise 5

Compute
17 mod 5
343 mod 2
0 mod 77
97 mod 98
98 mod 97
−4 mod 6

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 17 / 36

Modular Arithmetic

We can perform addition, subtraction and multiplication modulo m

This confines results to range [0..n − 1] No
"overflow"
Notation: a + r mod m means (a + r) mod m
Similar for "−" and "∗", also use power raising
Examples:
7 + 5 = 2 mod 10
Reason: 7 + 5 = 12 and 12 mod 10 = 2
7 ∗5 = 5 mod 10
Reason: 7 ∗ 5 = 35 and 35 mod 10 = 5
75 = 16807 = 7 mod 10

Kavinga Yapa Abeywardena - Maths Introduction 18 / 36

Associativity of Modular Arithmetic

An operation is associative, if brackets can be grouped freely

In other words: intermediate results can be computed in any order
It is easy to see that normal addition is associative: e.g.
(1 + 3) + 4 = 1 + (3 + 4) = 8
This is correct for modular arithmetic as well!
Example:
We want to compute (25 ) 2 mod 30

Compute (25 mod 30) 2 mod 30 = (32 mod 30) 2 mod 30

= 22 mod 30
= 4

On the other hand, check that (25 ) 2 = 1024 = 4 mod 30

Remarks: this is used in the proof of correctness for the RSA
algorithm

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 19 / 36

Mini-Exercise 6

Compute
5 + 7 mod 10
1 + 1 mod 2
1 − 1 mod 2
4 ∗7 mod 27
147 mod 13

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 20 / 36

Modular Arithmetic Tables

A table can be used to illustrate arithmetic – entry in position (i, j)

is assigned to i + j mod m (or i ∗j mod m)
For example, arithmetic mod 4 can be illustrated using the
following tables:

Addition mod 4: Multiplication mod 4:

+ 0 1 2 3 * 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 21 / 36

Mini-Exercise 7

Sketch tables for addition and multiplication mod 2.

How could you express this using Boolean operations?

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 22 / 36

Greatest Common Divisor

Definition: given two integers a and b, their greatest common

divisor is the greatest integer dividing both a and b
Notation: gcd(a, b)
Example: a = 28, b = 24, gcd(28, 24) = 4
Can be computed e.g. using prime factor decomposition
Let
α β β
a = p1 1 ···pnα n and b = p 1 1 ···pn n

with αi , βi ≥ 0, pi prime.
Then Y
gcd(a, b) = pmin(α i ,βi ).
i

We say that a and b are co-prime if gcd(a, b) = 1.

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 23 / 36

The Euclidean Algorithm

Euclidean algorithm computes the greatest common divisor of two

numbers
Based on following recursive identity:

gcd(a, b) = gcd(b, a mod b)

and gcd(a, 0) = a (base case)

We explain this using an example: compute gcd(80, 45)
80 : 45 = 1 and 80 − 1∗45 = 35
45 : 35 = 1 and 45 −1∗35 = 10
35 : 10 = 3 and 35 −3∗10 = 5
10 : 5 = 2 and 10 −2∗5 = 0 algorithm terminates!
Solution: gcd(80, 45) = 5
Reason: gcd(80, 45) = gcd(45, 35) = ···= gcd(5, 0) = 5

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 24 / 36

Mini-Exercise 8

Compute the gcd of 75 and 28, using

Prime factor decomposition,
The Euclidean algorithm.
Find the greatest common divisor g of 799 and 987. Find integers x
and y such that 799x + 987y = g.

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 25 / 36

Modular Inverse

Let a, n be integers
The inverse of a modulo n is an integer x such that ax = 1 mod n
Also write: a− 1 mod n
Note: inverse does not always exist Fact:
inverse of a exists ⇔gcd(a, n) = 1 Of
course, then also xa = 1 mod n
Example:
a = 3, n = 20
The inverse of a is x = 7 since 3 ∗7 = 21 = 1 mod 20
Of course, also 7 ∗3 = 1 mod 20
How can inverse be computed?
From multiplication table
Try and error
Extended Euclidean Algorithm

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 26 / 36

The Extended Euclidean Algorithm

Question: How can we compute a− 1 mod n?

Solution: use the extended version of Euklidean Algorithm:
This computes u, v such that

ua + vb = gcd(a, b)

If gcd(a, b) = 1: computes u as modular inverse of a mod b

Proof: ua = 1 − vb so ua ≡ 1 mod b
Example: a = 3, b = 20. EEA: u = 7, v = 1
Check: 7 ·3 − 1 ·20 = 1
Hence: 3− 1 ≡ 7(20)

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 27 / 36

The Extended Euclidean Algorithm – Example

Example: Compute modular inverse of 29 (41)

Step 1: Euclidean Algorithm
41 : 29 = 1 and 41 − 1 ∗29 = 12
29 : 12 = 2 and 29 − 2 ∗12 = 5
12 : 5 = 2 and 12 − 2 ∗5 = 2
5 : 2 = 2 and 5 − 2 ∗2 = 1
Step 2: Redo operations on input (0, 1)
0-1*1 = -1
1-2*(-1) = 3
-1-2*3 = -7
3-2*(-7) = 17
Solution: 17

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 28 / 36

Mini-Exercise 9

Compute the modular inverse of 28 mod 75.

Solve the following linear equations:
8x ≡ 1 (mod 13)
6x ≡ 11 (mod 29
8x ≡ 7 (mod 11)

Kavinga Yapa Abeywardena - Maths Introduction 29 / 36

Polynomials

Given f ∈ R[x], we can perform addition, subtraction,

multiplication and division with remainder
Given f , g ∈ R[x], we can divide f by g (with remainder):
f = q ·g + r (deg r < deg g)
We call f reducible if
f = g ·h (g, h ∈ R[x], deg g > 0, deg h > 0)
Example: x 2 − x = f = x(x − 1)
Otherwise: f is called irreducible

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 30 / 36

Mini-Exercise 10

Given the polynomials f (x) = x 3 − 3x + 1 and g(x) = x − 1. Compute

f +g
f −g
fg

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 31 / 36

Outline

1 Mathematical Objects

2 Mathematical Operations and Algorithms

3 Basic Number Theory

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 32 / 36

Euler’s Function

Euler’s function φ(n) plays an important role in computational

number theory
For n > 1, φ(n) is the number of integers k (1 ≤ k ≤ n − 1) that
are co-prime to n
So:
φ(n) =| { k ∈ { 1, .., n − 1} : gcd(k, n) = 1} |
Examples:
φ(6) = 2
φ(15) = 8

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 33 / 36

Mini- Exercise 11

Compute φ(16), by successively examining the integers 1, 2, . . ., 15.

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 34 / 36

Fermat’s Little and Euler’s Theorems

Fermat’s Little Theorem: if p is prime and p ∤a, then

ap− 1 ≡ 1 ( modp)
Euler’s Theorem: if gcd(a, n) = 1 then aφ(n) ≡ 1 ( modn)
Many applications in cryptography
Primality testing
Integer factorisation
RSA

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 35 / 36

Mini-Exercise 12

Verify Euler’s Theorem for n = 15 and a = 2

How are Euler’s and Fermat’s Theorem related? Hint: what is φ(p)
for p prime?
Prove that for p, q prime, one has

a(p− 1)(q− 1) ≡ 1 (mod pq)

Hint: Use Euler’s theorem and the fact that φ(nm) = φ(n)φ(m).

Kavinga Yapa Abeywardena - [email protected] Maths Introduction 36 / 36