Public-Key (Asymmetric) Ciphers
Public-Key (Asymmetric) Ciphers
Part 1
Slides Original Source:
1.
M. Stamp, “Information Security: Principles and Practice,” John Wiley
2.
C. Paar and J. Pelzl, “Understanding Cryptography – A Textbook for Students and
Practitioners,”
Springer (
)
3.
B. Forouzan, ” Cryptography and
Network Security,” McGraw-Hillwww.crypto-textbook.com
O
u
t
l
i
n
e
•
Motivation
•
Principles behind public-key ciphers
•
Prime numbers & Modulo operation
2/31
O
u
t
l
i
n
e
•
Motivation
•
Principles behind public-key ciphers
•
Prime numbers & Modulo operation
3/31
Understanding Cryptography by Christof Paar and Jan Pelzl
P
u
b
l
i
c
-
k
e
y
C
i
p
h
e
r
s
i
n
t
h
e
F
i
e
l
d
o
f
C
r
y
p
t
o
l
o
g
y
4/31
Understanding Cryptography by Christof Paar and Jan Pelzl
I
s
s
u
e
s
w
i
t
h
S
y
m
m
e
t
r
i
c
-
k
e
y
C
i
p
h
e
r
s
5/31
•
S
y
m
m
e
t
r
i
c
-
k
e
y
c
i
p
h
e
r
s
(
e
.
g
.
,
A
E
S
o
r
3
D
E
S
)
a
r
e
v
e
r
y
s
e
c
u
r
e
,
f
a
s
t
,
a
n
d
w
i
d
e
s
p
r
e
a
d
b
u
t
:
•
Key distribution problem:
Secret key must be transported securely
•
Number of keys:
In a network, each pair of users requires a unique key
•
n
users in the network require keys with each user
storing (
n
– 1) keys!!
•
Cheating:
Alice or Bob can cheat each other, because they have
identical keys!!!
•
Repudiation by Alice
•
Fabrication by Bob
O
u
t
l
i
n
e
•
Motivation
•
Principles behind public-key ciphers
•
Prime numbers & Modulo operation
6/31
7
Public-Key Cryptography
Two keys
o
Sender uses recipient’s
public key
to
encrypt
o
Recipient uses
private key
to
decrypt
Based on “trap door one way function”
o
“One way” means easy to compute in one direction,
but hard to compute in other direction
o
“Trap door” used to create key pairs
The main idea behind asymmetric-key cryptography is the
concept of the
trapdoor
one-way function
.
Trapdoor One-Way Function
A
function
is a rule mapping a domain to a range
1
0
.
9
Trapdoor
One-Way Function (TOWF)
Trapdoor One-Way Function
(Continued)
One-Way Function (OWF)
1. f is easy to compute.
2. f
−1
is difficult to compute.
3. Given
y
and a trapdoor
k’
,
x
can
be computed easily.
10.1.4 Continued
Example 10. 1
Example 10. 2
When
n
is large,
n
=
p
×
q
is a
one-way function
. Given
p
and
q
, it is always easy to calculate
n
; given
n
, it is very difficult to
compute
p
and
q
. This is the
factorization problem
.
When
n
is large, the function
y
=
x
k
mod
n
is a
trapdoor
one-way
function
. Given
x
,
k
, and
n
, it is easy to calculate
y
. Given
y
,
k
,
and
n
, it is very difficult to calculate
x
. This is the
discrete
logarithm problem
. However, if we know the
trapdoor
,
k
′, such
that
k
×
k
′ = 1 mod
(
n
), we can use
x
=
y
k
′
mod
n
to easily find
x
.
Understanding Cryptography by Christof Paar and Jan Pelzl
H
o
w
t
o
b
u
i
l
d
P
u
b
l
i
c
-
K
e
y
A
l
g
o
r
i
t
h
m
s
11/31
•
O
n
e
w
a
y
f
u
n
c
t
i
o
n
s
a
r
e
b
a
s
e
d
o
n
m
a
t
h
e
m
a
t
i
c
a
l
l
y
h
a
r
d
p
r
o
b
l
e
m
s
•
Three main families:
•
F
a
c
t
o
r
i
n
g
i
n
t
e
g
e
r
s
(
R
S
A
,
.
.
.
)
•
Given a composite integer
n
, find its prime factors
•
Multiply two primes: easy
•
D
i
s
c
r
e
t
e
L
o
g
a
r
i
t
h
m
(
D
L
)
(
D
i
f
f
i
e
-
H
e
l
l
m
a
n
,
E
l
g
a
m
a
l
,
D
S
A
,
…
)
•
Given
a, y
and
m,
find
x
such that
y
=
a
x
mod
m
•
Exponentiation
a
x
: easy
•
E
l
l
i
p
t
i
c
C
u
r
v
e
s
(
E
C
)
(
E
C
D
H
,
E
C
D
S
A
)
•
Generalization of discrete logarithm
•
N
o
t
e
:
T
h
e
p
r
o
b
l
e
m
s
a
r
e
c
o
n
s
i
d
e
r
e
d
m
a
t
h
e
m
a
t
i
c
a
l
l
y
h
a
r
d
,
b
u
t
n
o
p
r
o
o
f
e
x
i
s
t
s
(
s
o
f
a
r
)
Understanding Cryptography by Christof Paar and Jan Pelzl
K
e
y
L
e
n
g
t
h
s
a
n
d
S
e
c
u
r
i
t
y
L
e
v
e
l
s
12/31
•
The exact complexity of RSA and DL is difficult to estimate
•
The existence of quantum computers would probably be the end for EC,
RSA ,& DL (at least 2-3 decades away, and some people doubt that QC
will ever exist)
13
Public-Key Cryptography
Encryption
o
Suppose we
encrypt
M
with Bob’s
public
key
o
Bob’s
private
key can
decrypt
to recover
M
Digital Signature
o
Sign
by “encrypting” with your
private
key
o
Anyone can
verify
signature by “decrypting” with
public
key
o
But only you could have signed
o
Like a handwritten signature, but way better…
O
u
t
l
i
n
e
•
Motivation
•
Principles behind public-key ciphers
•
Prime numbers & Modulo operation
14/31
15
Modular Addition/Multiplication
Notation and facts
o
7 mod 6
1
o
7
13
1 mod 6
o
((
a
mod
n
) + (
b
mod
n
)) mod
n
= (
a
+
b
) mod
n
o
((
a
mod
n
)(
b
mod
n
)) mod
n
=
ab
mod
n
Addition Examples
o
3 + 5
2 mod 6
o
2 + 4
0 mod 6
o
3 + 3
0 mod 6
o
(7 + 12) mod 6 = 19 mod 6 = 1 mod 6
o
(7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6
16
Modular Addition/Multiplication
Multiplication Examples
o
3
4
0 (mod 6)
o
2
4
2 (mod 6)
o
5
5
1 (mod 6)
o
(7
4) mod 6 =
28
mod 6 = 4 mod 6
o
(7
4) mod 6 =
(1
4) mod 6 = 4 mod 6
17
Modular Inverses
Additive inverse
of
x
mod
n
, denoted
–
x
mod
n
, is the number that must be
added to
x
to get
0 mod
n
o
-2 mod 6
4
, since
2 + 4
0 mod 6
Multiplicative inverse
of
x
mod
n
,
denoted
x
-1
mod
n
, is the number that
must be multiplied by
x
to get
1 mod
n
o
3
-1
mod 7
5, since 3
5
1 mod 7
18
Modular Arithmetic Quiz
Q: What is
-3 mod 6
?
A:
3
Q: What is
-1 mod 6
?
A:
5
Q: What is
5
-1
mod 6
?
A:
5
Q: What is
2
-1
mod 6
?
A: No number works!
Multiplicative inverse might not exist
19
Relative Primality
x
and
y
are
relatively prime
if they
have no common factor other than
1
x
-1
mod
y
exists only when
x
and
y
are
relatively prime
If it exists,
x
-1
mod
y
is easy to
compute using
Extended Euclidean
Algorithm
(more later!)
20
Euler’s Totient Function
(
n
)
is “the number of numbers less than
n
that are relatively prime to
n
”
o
Here, “numbers” are positive integers
Examples
o
(4) = 2
since
4
is relatively prime to
3
and
1
o
(5) = 4
since 5 is relatively prime to
1
,
2
,
3
,
4
o
(12) = 4
o
(
p
) =
p
- 1
if
p
is prime
o
(
pq
) = (
p
- 1)(
q
- 1)
if
p
and
q
prime
E
u
c
l
i
d
e
a
n
A
l
g
o
r
i
t
h
m
•
C
o
m
p
u
t
e
t
h
e
g
r
e
a
t
e
s
t
c
o
m
m
o
n
d
i
v
i
s
o
r
g
c
d
(
r
0
,
r
1
)
o
f
t
w
o
i
n
t
e
g
e
r
s
r
0
a
n
d
r
1
•
g
c
d
i
s
e
a
s
y
f
o
r
s
m
a
l
l
n
u
m
b
e
r
s
:
1. factor
r
0
and
r
1
2. gcd = highest common factors
•
E
x
a
m
p
l
e
:
•
r
0
= 84 = 2 . 2 . 3 . 7
•
r
1
= 30 = 2 . 3 . 5
•
The gcd is the product of all common prime factors
2 . 3 = 6 =
gcd
(30,84)
•
Factoring is complicated for large numbers
Understanding Cryptography by Christof Paar and Jan Pelzl
21/31
E
u
c
l
i
d
e
a
n
A
l
g
o
r
i
t
h
m
•
O
b
s
e
r
v
a
t
i
o
n
:
g
c
d
(
r
0
,
r
1
)
=
g
c
d
(
r
0
–
r
1
,
r
1
)
•
R
e
d
u
c
e
t
h
e
p
r
o
b
l
e
m
o
f
f
i
n
d
i
n
g
g
c
d
o
f
t
w
o
n
u
m
b
e
r
s
t
o
t
h
a
t
o
f
t
h
e
g
c
d
o
f
t
w
o
s
m
a
l
l
e
r
n
u
m
b
e
r
s
•
Repeat process recursively
•
T
h
e
f
i
n
a
l
g
c
d
(
r
i
,
0
)
=
r
i
i
s
t
h
e
a
n
s
w
e
r
!
g
c
d
c
a
n
b
e
c
o
m
p
u
t
e
d
a
s
f
o
l
l
o
w
s
:
•
gcd
(
a
, 0) =
a
•
gcd
(
a
,
b
) =
gcd
(
b
,
a
mod
b
) –– faster than
gcd
(
a
–
b
,
b
) but same result!
•
E
x
a
m
p
l
e
:
•
gcd
(30, 18) =
gcd
(18, 30 mod 18) =
•
gcd
(18, 12) =
gcd
(12, 18 mod 12) =
•
gcd
(12, 6) =
gcd
(6, 12 mod 6) =
gcd
(6, 0) = 6
•
N
o
t
e
:
c
o
m
p
l
e
x
i
t
y
o
f
m
e
t
h
o
d
g
r
o
w
s
l
i
n
e
a
r
l
y
w
i
t
h
t
h
e
n
u
m
b
e
r
o
f
b
i
t
s
(
g
r
e
a
t
!
)
Understanding Cryptography by Christof Paar and Jan Pelzl
22/31
E
x
t
e
n
d
e
d
E
u
c
l
i
d
e
a
n
A
l
g
o
r
i
t
h
m
(
E
E
A
)
•
V
e
r
y
i
m
p
o
r
t
a
n
t
f
o
r
p
u
b
l
i
c
-
k
e
y
c
i
p
h
e
r
s
•
Extend the Euclidean algorithm to
r
1
-1
mod
r
0
•
EEA computes
s
,
t
, and the
gcd
:
•
U
s
e
t
h
e
r
e
l
a
t
i
o
n
f
o
r
m
o
d
r
0
C
o
m
p
a
r
e
w
i
t
h
t
h
e
d
e
f
i
n
i
t
i
o
n
o
f
m
o
d
u
l
a
r
i
n
v
e
r
s
e
:
t
r
1
-
1
m
o
d
r
0
•
Note:
r
0
and
r
1
must be relatively prime for the inverse to exist
(i.e.,
gcd (r
0
, r
1
)
= 1)
•
R
e
c
u
r
s
i
v
e
f
o
r
m
u
l
a
e
t
o
c
a
l
c
u
l
a
t
e
s
&
t
i
n
e
a
c
h
s
t
e
p
(
n
e
x
t
s
l
i
d
e
)
•
EEA can be used to find multiplicative inverses in Galois fields
Understanding Cryptography by Christof Paar and Jan Pelzl
23/31
E
x
t
e
n
d
e
d
E
u
c
l
i
d
e
a
n
A
l
g
o
r
i
t
h
m
Understanding Cryptography by Christof Paar and Jan Pelzl
24/31
E
x
t
e
n
d
e
d
E
u
c
l
i
d
e
a
n
A
l
g
o
r
i
t
h
m
Understanding Cryptography by Christof Paar and Jan Pelzl
25/31
stop when
r
i
= 1
E
u
l
e
r
’
s
P
h
i
(
T
o
t
i
e
n
t
)
F
u
n
c
t
i
o
n
1
/
3
Understanding Cryptography by Christof Paar and Jan Pelzl
26/31
E
u
l
e
r
’
s
P
h
i
(
T
o
t
i
e
n
t
)
F
u
n
c
t
i
o
n
2
/
3
Understanding Cryptography by Christof Paar and Jan Pelzl
27/31
E
u
l
e
r
’
s
P
h
i
(
T
o
t
i
e
n
t
)
F
u
n
c
t
i
o
n
3
/
3
28/31
•
(
n
) can be computed recursively by:
(1) = 1
2.
if
n
is a
prime power
,
n = p
e
, then
(
n
) = (
p
– 1)
p
(
e
– 1)
3.
if gcd(
m, n
) = 1, then
(
mn
) =
(
m
) .
(
n
)
•
E
x
a
m
p
l
e
s
:
•
(17) = 16
•
(25) = 5
2
= (5 – 1) . 5 = 20
•
(16) = 2
4
= (2 – 1) . 2
3
= 8
•
(105) =
(3 . (5 . 7)) = 2 . (4 . 6) = 48
•
(200) =
(2
3
. 5
2
) = ((2 – 1) . 2
2
) ((5 – 1) . 5) = 4 . 20 = 80
F
e
r
m
a
t
’
s
L
i
t
t
l
e
T
h
e
o
r
e
m
Understanding Cryptography by Christof Paar and Jan Pelzl
29/31
•
V
e
r
y
u
s
e
f
u
l
i
n
p
u
b
l
i
c
-
k
e
y
c
i
p
h
e
r
s
(
e
.
g
.
,
p
r
i
m
a
l
i
t
y
t
e
s
t
i
n
g
w
h
i
l
e
g
e
n
e
r
a
t
i
n
g
k
e
y
s
)
•
Recall that arithmetic in finite fields
GF
(
p
) is done modulo
p
theorem holds for all integers
a
GF
(
p
)
•
A
l
t
e
r
n
a
t
e
f
o
r
m
:
a
p
a
−
1
=
a
p
−
1
≡
1
(
m
o
d
p
)
(
w
h
y
?
)
a
a
p
−
2
≡
1
(
m
o
d
p
)
a
−
1
≡
a
p
−
2
(
m
o
d
p
)
•
Quick way to find mult. inverse if modulus is a prime!!
•
But slower than EEA unless a hardware accelerator is used
for fast exponentiation
•
E
x
a
m
p
l
e
:
L
e
t
p
=
7
a
n
d
a
=
2
a
−
1
=
a
p
−
2
=
2
5
=
3
2
≡
4
m
o
d
7
E
u
l
e
r
’
s
T
h
e
o
r
e
m
Understanding Cryptography by Christof Paar and Jan Pelzl
30/31
•
Generalization of Fermat’s Little Theorem for any modulus
•
E
x
a
m
p
l
e
:
L
e
t
m
=
1
2
a
n
d
a
=
5
g
c
d
(
1
2
,
5
)
=
1
(12) =
(2
2
·
3) =
(
2
2
−
2
1
)(3
1
−
3
0
)
=
4
Verify:
5
(12)
= 5
4
= 625
≡
1 mod 12
•
Theorem is used to prove correctness of RSA (most popular
public-key crypto)
E
u
l
e
r
’
s
T
h
e
o
r
e
m
Understanding Cryptography by Christof Paar and Jan Pelzl
31/31
•
Another important use of Euler’s theorem is the following:
if
k
≡
j
(mod
(
n
)) then
a
k
=
a
j
mod
n
•
Helps in exponentiation computation (needed in RSA)
•
E
x
a
m
p
l
e
1
:
2
4
6
=
2
2
(
m
o
d
5
)
,
s
i
n
c
e
4
6
2
(
m
o
d
(
5
)
)
•
E
x
a
m
p
l
e
2
:
C
o
m
p
u
t
e
t
h
e
f
o
l
l
o
w
i
n
g
:
a.
14
52
(mod 11)
14
52
≡ 3
52
(mod 11). Since
(11) = 10
52 ≡ 2 (mod 10)
14
52
≡ 3
52
≡ 3
2
≡ 9 (mod 11)
b.
463
91
(mod 15)
463
91
≡ 13
91
≡ (–2)
91
(mod 15). Since
(15) = 2 × 4 = 8
91 ≡ 3 (mod 8)
(–2)
91
≡ (–2)
3
≡ –8 ≡ 7 (mod 15)
Principles and significance of public-key cryptography, including its motivation, trapdoor one-way functions, and the issues with symmetric-key ciphers. Learn about asymmetric ciphers, key distribution problems, and the use of prime numbers in encryption.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Public-Key (Asymmetric) Ciphers Part 1 Slides Original Source: 1. M. Stamp, Information Security: Principles and Practice, John Wiley 2. C. Paar and J. Pelzl, Understanding Cryptography A Textbook for Students and Practitioners, Springer (www.crypto-textbook.com) 3. B. Forouzan, Cryptography and Network Security, McGraw-Hill
Outline Motivation Principles behind public-key ciphers Prime numbers & Modulo operation 2/31
Outline Motivation Principles behind public-key ciphers Prime numbers & Modulo operation 3/31
Public-key Ciphers in the Field of Cryptology Cryptology Cryptography Cryptanalysis Asymmetric Ciphers Protocols Symmetric Ciphers Block Ciphers Stream Ciphers Understanding Cryptography by Christof Paar and Jan Pelzl 4/31
Issues with Symmetric-key Ciphers Symmetric-key ciphers (e.g., AES or 3DES) are very secure, fast, and widespread but: Key distribution problem: Secret key must be transported securely Number of keys: In a network, each pair of users requires a unique key n users in the network require storing (n 1) keys!! Cheating: Alice or Bob can cheat each other, because they have identical keys!!! Repudiation by Alice Fabrication by Bob keys with each user Understanding Cryptography by Christof Paar and Jan Pelzl 5/31
Outline Motivation Principles behind public-key ciphers Prime numbers & Modulo operation 6/31
Public-Key Cryptography Two keys o Sender uses recipient s public key to encrypt o Recipient uses private key to decrypt Based on trap door one way function o One way means easy to compute in one direction, but hard to compute in other direction o Trap door used to create key pairs 7
Trapdoor One-Way Function The main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function. A function is a rule mapping a domain to a range
Trapdoor One-Way Function (Continued) One-Way Function (OWF) 1. f is easy to compute. 2. f 1 is difficult to compute. Trapdoor One-Way Function (TOWF) 3. Given y and a trapdoor k , x can be computed easily. 10.9
10.1.4 Continued Example 10. 1 When n is large, n = p q is a one-way function. Given p and q, it is always easy to calculate n; given n, it is very difficult to compute p and q. This is the factorization problem. Example 10. 2 When n is large, the function y = xk mod n is a trapdoor one-way function. Given x, k, and n, it is easy to calculate y. Given y, k, and n, it is very difficult to calculate x. This is the discrete logarithm problem. However, if we know the trapdoor, k , such that k k = 1 mod (n), we can use x = yk mod n to easily find x.
How to build Public-Key Algorithms One way functions are based on mathematically hard problems Three main families: Factoring integers (RSA, ...) Given a composite integer n, find its prime factors Multiply two primes: easy Discrete Logarithm (DL) (Diffie-Hellman, Elgamal, DSA, ) Given a, y and m, find x such that y = axmod m Exponentiation ax: easy Elliptic Curves (EC) (ECDH, ECDSA) Generalization of discrete logarithm Note: The problems are considered mathematically hard, but no proof exists (so far) Understanding Cryptography by Christof Paar and Jan Pelzl 11/31
Key Lengths and Security Levels The exact complexity of RSA and DL is difficult to estimate The existence of quantum computers would probably be the end for EC, RSA ,& DL (at least 2-3 decades away, and some people doubt that QC will ever exist) Understanding Cryptography by Christof Paar and Jan Pelzl 12/31
Public-Key Cryptography Encryption o Suppose we encryptM with Bob s public key o Bob s private key can decrypt to recover M Digital Signature o Sign by encrypting with your private key o Anyone can verify signature by decrypting with public key o But only you could have signed o Like a handwritten signature, but way better 13
Outline Motivation Principles behind public-key ciphers Prime numbers & Modulo operation 14/31
Modular Addition/Multiplication Notation and facts o 7 mod 6 1 o 7 13 1 mod 6 o ((a mod n) + (b mod n)) mod n = (a + b) mod n o ((a mod n)(b mod n)) mod n = ab mod n Addition Examples o 3 + 5 2 mod 6 o 2 + 4 0 mod 6 o 3 + 3 0 mod 6 o (7 + 12) mod 6 = 19 mod 6 = 1 mod 6 o (7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6 15
Modular Addition/Multiplication Multiplication Examples o 3 4 0 (mod 6) o 2 4 2 (mod 6) o 5 5 1 (mod 6) o (7 4) mod 6 = 28 mod 6 = 4 mod 6 o (7 4) mod 6 = (1 4) mod 6 = 4 mod 6 16
Modular Inverses Additive inverse of x mod n, denoted x mod n, is the number that must be added to x to get 0 mod n o -2 mod 6 4, since 2 + 4 0 mod 6 Multiplicative inverse of x mod n, denoted x-1 mod n, is the number that must be multiplied by x to get 1 mod n o 3-1 mod 7 5, since 3 5 1 mod 7 17
Modular Arithmetic Quiz Q: What is -3 mod 6? A: 3 Q: What is -1 mod 6? A: 5 Q: What is 5-1 mod 6? A: 5 Q: What is 2-1 mod 6? A: No number works! Multiplicative inverse might not exist 18
Relative Primality x and y are relatively prime if they have no common factor other than 1 x-1 mod y exists only when x and y are relatively prime If it exists, x-1 mod y is easy to compute using Extended Euclidean Algorithm (more later!) 19
Eulers Totient Function (n) is the number of numbers less than n that are relatively prime to n o Here, numbers are positive integers Examples o (4) = 2 since 4 is relatively prime to 3 and 1 o (5) = 4 since 5 is relatively prime to 1,2,3,4 o (12) = 4 o (p) = p - 1 if p is prime o (pq) = (p - 1)(q - 1) if p and q prime 20
Euclidean Algorithm Compute the greatest common divisor gcd (r0, r1)of two integers r0and r1 gcd is easy for small numbers: 1. factor r0and r1 2. gcd = highest common factors Example: r0= 84 = 2 . 2 . 3 . 7 r1= 30 = 2 . 3 . 5 The gcd is the product of all common prime factors 2 . 3 = 6 = gcd (30,84) Factoring is complicated for large numbers Understanding Cryptography by Christof Paar and Jan Pelzl 21/31
Euclidean Algorithm Observation: gcd (r0, r1) = gcd (r0 r1, r1) Reduce the problem of finding gcd of two numbers to that of the gcd of two smaller numbers Repeat process recursively The final gcd (ri, 0) = riis the answer! gcd can be computed as follows: gcd (a, 0) = a gcd (a, b) = gcd (b, a mod b) faster than gcd (a b, b) but same result! Example: gcd (30, 18) = gcd (18, 30 mod 18) = gcd (18, 12) = gcd (12, 18 mod 12) = gcd (12, 6) = gcd (6, 12 mod 6) Note: complexity of method grows linearly with the number of bits (great!) = gcd (6, 0) = 6 Understanding Cryptography by Christof Paar and Jan Pelzl 22/31
Extended Euclidean Algorithm (EEA) Very important for public-key ciphers Extend the Euclidean algorithm to r1-1 mod r0 EEA computes s,t, and the gcd: Use the relation for mod r0 Compare with the definition of modular inverse: t r1-1 mod r0 Note: r0 and r1 must be relatively prime for the inverse to exist (i.e., gcd (r0, r1) = 1) Recursive formulae to calculate s & t in each step (next slide) EEA can be used to find multiplicative inverses in Galois fields Understanding Cryptography by Christof Paar and Jan Pelzl 23/31
Extended Euclidean Algorithm Understanding Cryptography by Christof Paar and Jan Pelzl 24/31
Extended Euclidean Algorithm stop when ri = 1 Understanding Cryptography by Christof Paar and Jan Pelzl 25/31
Eulers Phi (Totient) Function 1/3 Understanding Cryptography by Christof Paar and Jan Pelzl 26/31
Eulers Phi (Totient) Function 2/3 Understanding Cryptography by Christof Paar and Jan Pelzl 27/31
Eulers Phi (Totient) Function 3/3 (n) can be computed recursively by: 1. (1) = 1 2. if n is a prime power, n = pe, then (n) = (p 1) p(e 1) 3. if gcd(m, n) = 1, then (mn) = (m) . (n) Examples: (17) = 16 (25) = 52 = (5 1) . 5 = 20 (16) = 24 = (2 1) . 23 = 8 (105) = (3 . (5 . 7)) = 2 . (4 . 6) = 48 (200) = (23 . 52) = ((2 1) . 22) ((5 1) . 5) = 4 . 20 = 80 28/31
Fermats Little Theorem Very useful in public-key ciphers (e.g., primality testing while generating keys) Recall that arithmetic in finite fields GF(p) is done modulo p theorem holds for all integers a GF(p) Alternate form:ap a 1= ap 1 1 (mod p) (why?) a ap 2 1 (mod p) a 1 ap 2(mod p) Quick way to find mult. inverse if modulus is a prime!! But slower than EEA unless a hardware accelerator is used for fast exponentiation Example: Let p = 7 and a = 2 a 1= ap 2= 25= 32 4 mod 7 Understanding Cryptography by Christof Paar and Jan Pelzl 29/31
Eulers Theorem Generalization of Fermat s Little Theorem for any modulus Example: Let m = 12 and a = 5 gcd (12, 5) = 1 (12) = (22 3) = (22 21)(31 30) = 4 Verify: 5 (12)= 54= 625 1 mod 12 Theorem is used to prove correctness of RSA (most popular public-key crypto) Understanding Cryptography by Christof Paar and Jan Pelzl 30/31
Eulers Theorem Another important use of Euler s theorem is the following: if k j (mod (n)) then ak = ajmod n Helps in exponentiation computation (needed in RSA) Example 1: 246 = 22 (mod 5), since 46 2 (mod (5)) Example 2: Compute the following: a. 1452 (mod 11) 1452 352 (mod 11). Since (11) = 10 52 2 (mod 10) 1452 352 32 9 (mod 11) b. 46391 (mod 15) 46391 1391 ( 2)91 (mod 15). Since (15) = 2 4 = 8 91 3 (mod 8) ( 2)91 ( 2)3 8 7 (mod 15) Understanding Cryptography by Christof Paar and Jan Pelzl 31/31
