Transcript Slide 1

Introduction to
Cryptography
Lecture 2
Functions
x1
x2
f
f(x1)
f(x3)
f(x2)
x3
Domain
Range
Functions
Definition: A function is a relation, such that
each element of a set (the domain) is
associated with a unique element of
another (possibly the same) set (the range)
x1
f
x2
x3
Domain
x1
f
f(x1)
f(x1)
f(x2)
x2
f(x2)
Not a function
Function
Range
Domain
Range
Functions
Definition: A function is called one to one if
each element of domain is associated with
precisely one element of the range.
Definition: A function is called onto if each
element of range is associated with at
least one element of the domain.
Functions
f
x1
f
x2
x1
f(x1)
f(x1)
x2
f(x1)
f(x2)
x3
f(x2)
x3
Range
Domain
Not one to one
Onto
y
Range
Domain
One to one
Not onto
Functions
A one to one and onto function always has
an inverse function
Definition: Given a function f an inverse
1
1
function f is computed by rule: f ( y)  x
if f ( x)  y.
x
1
f
(
x
)

e
f
( y)  log x .
Example: If
, then

Functions and Cryptography
Cipher can be represented as a function
Example 1:
f(Secret message)= YpbzobqjbZqqyec
Example 2:
1
f
f(son) = girl
(girl) = son
1
f(girl) = son
f (son) = girl

Functions and Cryptography

For each key, an encryption method
defines a one-to-one and onto function;
and the corresponding decryption method
is the inverse of this function.
Permutations
Definition: A permutation of n ordered
objects is a way of reordering them.
 It is a mathematical function
 It is one-to-one and onto
 An inverse of permutation is a permutation
Permutations
Example:
x
1
2
3
4
5
p(x)
3
1
5
4
2
x
1
2
3
4
5
q(x)
2
5
1
4
3
Prime Numbers
Definition: A prime number is an integer
number that has only two divisors: one
and itself.
Example: 1, 2,17, 31.
 Prime numbers distributed irregularly
among the integers
 There are infinitely many prime numbers
Factoring
The Fundamental Theorem of Arithmetic
tells us that every positive integer can
be written as a product of powers of
primes in essentially one way.
Example: 6647 172  23

90  2  3  5
2
Factoring
Problem of factoring a number is very hard
 The decision if n is a prime or composite
number is much easier
 Fermat’s factoring method sometimes can
be used to find any large factors of a
number fair quickly (pg.251)

Greatest Common Divisors - GCD
Definition: Let x and y be two integers.
The greatest common divisor of x and
y is number d such that d divides x and
d divides y.
Definition: x and y are relatively prime if
gcd(x,y)=1.
Greatest Common Divisors - GCD
Example: gcd(3,16) = 1
gcd(-28,8) = 4
 One way to find gcd is by finding
factorization of both numbers
 Euclidean Algorithm is usually used in
order to find gcd
Division Principle

Let m be a positive integer and let b be
any integer. Then there is exactly one pair
of integers q (quotient) and r (remainder)
such that b = qm +r.
Euclidean Algorithm

Input x and y

x0 = x, y0 = y
 For I >= 0 do
xi+1 = yi, yi+1 = xi mod yi
 If yi =0, stop

Output gcd(x,y) = xi
Euclidean Algorithm
Example: Let x = 4200 and y = 1485
i
xi
yi
qi
ri
0
4200 1485
2
1230
1
1485 1230
1
255
2
1230
255
4
210
3
255
210
1
45
4
210
45
4
30
5
45
30
1
15
6
30
15
2
0
7
15
0
Extended Euclidean Algorithm
For every x and y there are integers s and
t such that sx + ty = gcd(x,y)
 We can find s and t using Euclidean
Algorithm

Extended Euclidean Algorithm

Input x and y

x0 = x, y0 = y, s0 = t-1 = 0, t0 = s-1 = 1
 For I >= 0 do
xi+1 = yi, yi+1 = xi mod yi,
si+1 = si-1 – qisi, ti+1 = ti-1 - qiti
 If yi =0, stop

Output gcd(x,y) = xi, si-1,ti-1
Extended Euclidean Algorithm
Example: Let x = 4200 and y = 1485
i
xi
yi
qi
ri
si
ti
0
4200 1485
2
1230
0
1
1
1485 1230
1
255
1
-2
2
1230
255
4
210
-1
3
3
255
210
1
45
5
-14
4
210
45
4
30
-6
17
5
45
30
1
15
29
-82
6
30
15
2
0
-35
99
7
15
0
Homework
Read Section 1.2.
 Exercises: 4, 5 on pg.46-47.
 Read Section 4.1.
 Exercises: 6(a,c), 11(b,d), on pg.260-262
 Those questions will be a part of your
collected homework.
