Computer Security
Technology And Principles
Professors Dr.sc.ing. Viktors Gopejenko
Department of Computer Technologies and Natural Sciences
ISMA University
Riga, Latvia
Modifying slides originally prepared by Clemens H. Cap, Michael Huth ,
William Stallings and Lawrie Brown
1
Practice
Modular Arithmetic
Short Introduction to Modular
Arithmetic
Why do we need to study modular arithmetic?
Important for asymmetric cryptography (RSA, elliptic curves,
etc.)
Most cryptosystems are based on sets of numbers that are
discrete (sets with integers are particularly useful)
finite (i.e., if we only compute with a finely many numbers)
It is crucial to have an operation which „keeps the numbers
within limits“, i.e., after addition and multiplication they
should never leave the set.
Let’s have a look!
3
Short Introduction to Modular
Arithmetic
Modulo Operation
Let a, r, n be integers and n > 0. We write
a ≡ r mod n
if (r-a) is divisible by n or if n divides a-r
n is called the modulus and r is called the remainder
It is always possible to write
a = q ·n + r for 0 ≤ r < n
with the quotient q and the remainder r.
Examples:
Let a = 11 and n = 9 11 ≡ 2 mod 9 (11 = 1·9 + 2)
Let a = 19 and n = 9 19 ≡ 1 mod 9 (19 = 2·9 + 1)
4
Short Introduction to Modular
Arithmetic
How do we perform modular division?
First, note that rather than performing a division, we prefer to
multiply by the inverse.
The inverse a-1 of a number a is defined such that:
a a-1 ≡ 1 mod n
The inverse of 7 mod 9 is 4 since 7 x 4 ≡ 28 ≡ 1 mod 9.
How is the inverse compute?
The multiplicative inverse of a number a mod n only exists if and
only if: gcd (a, n) = 1 (gcd, greatest common divisor) (note that in
the example above gcd(7, 9) = 1, so that the inverse of 7 exists
modulo 9)
5
Short Introduction to Modular
Arithmetic
Modular Arithmetic
There is the neutral element 0 with respect to addition, i.e., for all a
a + 0 ≡ a mod n
For all a , there is always an additive inverse element –a such that
a + (-a) ≡ 0 mod n
There is the neutral element 1 with respect to multiplication, i.e., for
all a
a x 1 ≡ a mod n
The multiplicative inverse a-1 is defined such that
a x a-1 ≡61 mod n
Shift Cipher
Replaces each plaintext letter by another one.
Replacement rule: Take letter that follows after k positions in the
alphabet
Needs mapping from letters → numbers:
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
7
Shift Cipher
Example for k = 7
Plaintext = ATTACK = 0, 19, 19, 0, 2, 10
Ciphertext = HAAHJR = 7, 0, 0, 7, 9, 17
Note that the letters ”wrap around” at the end of the alphabet, which
can mathematically be expressed as reduction modulo 26, e.g.,
19 + 7 = 26 ≡ 0 mod 26
8
Shift Cipher
Mathematical description of the cipher
Let k, x, y ε {0,1, …, 25}
Encryption: y = ek(x) ≡ x + k mod 26
Decryption: x = dk(x) ≡ y - k mod 26
How secure is the shift cipher?
Exhaustive key search (key space is only 26!)
Letter frequency analysis, similar to attack against
substitution cipher
9
Affine Cipher
Extension of the shift cipher: rather than just adding the
key to the plaintext, we also multiply by the key
Key consists of two parts: k = (a, b)
Let k, x, y ε {0,1, …, 25}
Encryption: y = ek(x) ≡ a x + b mod 26
Decryption: x = dk(x) ≡ a-1(y – b) mod 26
10
Affine Cipher
Since the inverse of a is needed for inversion, we can only
use values for a for which: gcd(a, 26) = 1. There are 12
values for a that fulfil this condition
a ε {1,3,5,7,9,11,15,17,19,21,23,25}
Again, several attacks are possible, including:
Exhaustive key search and letter frequency analysis,
similar to the attack against the substitution cipher
11
Affine Cipher
Example
Let the key be k = (a,b) = (9,13)
-Plaintext = ATTACK =0,19,19,0,2,10
- Ciphertext = NCCNFZ = 13,2,2,13,5,25
12
Short Introduction to Modular
Arithmetic
Modular Reduction
Example: We want to compute 37 mod 7 (note that
exponentiation is extremely important in public-key
cryptography).
1st Approach: Exponentiation followed by modular
reduction
Example: 37 = 2187 ≡ 3 mod 7 the intermediate result is 2187
even though we know that the final result can’t be larger
than 6.
13
Short Introduction to Modular
Arithmetic
2nd Approach: Exponentiation with intermediate modular
reduction
Example: 37 = 33 · 34 = 27 x 81
At this point we reduce the intermediate results
27 modulo 7 and 81 mod 7
37 = 33 · 34 = 27 x 81 ≡ 6 x 4 mod 7
6 x 4 = 24 ≡ 3 mod 7
14
Short Introduction to Modular
Arithmetic
37 = 33 · 34 = 27 x 81 ≡ 6 x 4 mod 7
6 x 4 = 24 ≡ 3 mod 7
We can perform all these multiplications without a pocket
calculator, whereas mentally computing 37 = 2187 is a bit
challenging for most of us
For most algorithms it is advantageous to reduce
intermediate results as soon as possible.
15
Euler's totient function
Euler's totient function counts the positive integers up to
a given integer n that are relatively prime to n
For example, the totatives of n = 9 are the six numbers 1,
2, 4, 5, 7 and 8. They are all relatively prime to 9, but the
other three numbers in this range, 3, 6, and 9 are not,
because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9.
Therefore φ(9) = 6.
if a and n are relatively prime then
𝒂𝝋(𝒏) ≡ 𝟏 𝒎𝒐𝒅 𝒏
Euler's totient function
The RSA cryptosystem
Setting up an RSA system involves choosing large prime
numbers p and q, computing n = pq and k = φ(n), and
finding two numbers e and d such that ed ≡ 1 (mod k). The
numbers n and e (the "encryption key") are released to the
public, and d (the "decryption key") is kept private
Euler's totient function can be used to find inverse e-1
modulo n. (e-1=d)
𝒅 = 𝒆−𝟏 ≡ 𝒆𝝋 𝒏 −𝟏 𝒎𝒐𝒅 𝒏
Some values of the function
φ(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+ 1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60
24 hour clock
calculator by modulus 12
