17crypto_L01
Modular Arithmetic
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
1
Text as Integers
� Text can be represented as bitstrings.
�Use the ASCII code.
� Bitstrings can be treated as a series of integers.
�Binary numbers.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
2
�Binary numbers.
� Thus text can be treated as a series of integers.
� Arithmetic with integers is inconvenient because dividing
two integers does not normally produce another integer.
� Decryption is the inverse of encryption.
� If encryption uses multiplication then decryption must use
division.
Simple Example
� Letters can be represented by the 26 numbers between 0
and 25.
� A simple way of encrypting is to
�Multiply by a number between 2 and 24, the secret key
�Take the remainder when dividing by 26.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
3
�Take the remainder when dividing by 26.
�This gives a number between 0 and 25. The encrypted
text is also made up of letters.
� The secret message is decrypted by dividing by the secret
key.
�Multiplying by 1 / key.
Integers mod n
� Assume we have a finite range of integers.
�All the integers between 0 .. n-1 for some n.
�n can be very large.
� Any integer outside the range is converted to an integer
inside the range by taking the remainder when dividing by .
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
4
inside the range by taking the remainder when dividing by n.
� Integers mod 7 contain the following 7 numbers:
�{ 0, 1, 2, 3, 4, 5, 6 }
�10, 17, 24 … are all the same as 3.
Defining Inverses
� If a is an integer mod n, then we define its inverse x as the
solution of the equation
� ax = 1 mod n
� Any number multiplied by its inverse is 1.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
5
� Any number multiplied by its inverse is 1.
� x must also be an integer mod n, but modular arithmetic
makes this possible.
Example: Integers mod 7
� 0 does not have an inverse.
� The inverse of 1 is 1.
� The inverse of 6 is 6. (6 ≡ -1)
�6 * 6 = 36 ≡ 1 (mod 7).
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
6
�6 * 6 = 36 ≡ 1 (mod 7).
� The inverse of 2 is 4 (and inverse of 4 is 2).
�2 * 4 = 8 ≡ 1 (mod 7).
� The inverse of 3 is 5 (and inverse of 5 is 3).
�3 * 5 = 15 ≡ 1 (mod 7).
Example: Integers mod 4
� Possible values are { 0, 1, 2, 3 }
� The inverse of 1 is 1.
� The inverse of 3 is 3.
� 2 does not have an inverse.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
7
� 2 does not have an inverse.
�2 times anything is always an even number.
�Dividing by 4 always leaves an even remainder
�Therefore the remainder cannot be 1.
� Modular arithmetic does not guarantee that all numbers
have inverses.
Simple Example: Encryption
� The message “SECRET” is converted to integers, their
position in the alphabet (A = 0 etc):
<18, 4, 2, 17, 4, 19>.
� Choose key 5. Multiply all the numbers by 5 and take the
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
8
� Choose key 5. Multiply all the numbers by 5 and take the
remainder when dividing by 26:
<12, 20, 10, 7, 20, 17>.
� Converting back to letters gives the cipher text: “MUKHUR”
Simple Example: Decryption
� The inverse of 5 is 21.
�5*21 = 105 and 105 % 26 = 1.
� Multiplying the cipher text numbers by 21 and taking the
remainder when dividing by 26 gives:
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
9
�12) 12*21 = 252 252%26 = 18
�20) 20*21 = 420 420%26 = 4
�10) 10*21 = 210 210%26 = 2
� 7) 7*21 = 147 147%26 = 17
�20) 20*21 = 420 420%26 = 4
�17) 17*21 = 357 357%26 = 19
� This is the original message.
When will a number have an
Inverse?
� Let a be an integer mod n.
� a will have an inverse if and only if
�gcd(a, n) = 1
� gcd is the greatest common divisor or highest common
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
10
� gcd is the greatest common divisor or highest common
factor of two numbers.
�gcd(2,4) = 2 and so 2 does not have an inverse in
the integers mod 4 number system.
� If a number has a common factor with n then it will not
have an inverse.
� The proof is beyond the scope of the course.
Calculations with Integers mod n
� The previous slide shows when an inverse exists but not
how to calculate it.
� An algorithm will follow.
� Firstly, we need a general theorem that is applicable to all
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
11
� Firstly, we need a general theorem that is applicable to all
calculations with integers mod n.
The Homomorphism Theorem
� We can perform the modulus operation whenever it is
convenient. The final answer will always be the same.
� (a ⊗ b) % n = ((a % n) ⊗ (b % n)) % n
�where ⊗ is +, – or *
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
12
�where ⊗ is +, – or *
�and % is the modulus operator.
� The proof is beyond the scope of the course.
� Example, calculate 20 * 11 with integers mod 7.
� (20 * 11) % 7 = 220 % 7 = 3 (after some long division)
� (20%7) * (11%7) % 7 = (6*4) % 7 = 24 % 7 = 3.
Example 35 % 7
� Use a repeated squaring algorithm.
� 32 = 9
� 34 = 92 = 81
� 35 = 3 * 34 = 3 * 81 = 243
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
13
� 35 = 3 * 34 = 3 * 81 = 243
� 243 % 7 = 5
Example 35 % 7 (2)
� Alternatively, do % at each step.
� 32 % 7 = 9 % 7 = 2
� 34 % 7 = 22 % 7 = 4 % 7 = 4
� 35 % 7 = (3 * 4) % 7 = 12 % 7 = 5
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
14
� 35 % 7 = (3 * 4) % 7 = 12 % 7 = 5
� This approach is preferable because the numbers stay
small.
� Numbers are typically very large in cryptography.
�Calculate (100 digit)100 digit % 100 digit!
Euclid’s Algorithm for gcd
� Euclid’s algorithm is based on the observation that if g is a
factor of both a and b, then it is also a factor of a-b.
�Assuming a > b, if a < b then swap a and b. � Proof Crpto & SecDev 2017 © Ron Poet: Lecture 1 15 � Proof �a = ug for some integer u since g is a factor �b = vg for some integer v since g is a factor �a - b = (u - v)g. �Thus g is a factor. Euclid’s Algorithm and Remainder � We can repeatedly subtract b from a until the number we have left is less than b. � Any factor of a and b will also be a factor of this number. � This number is the remainder a % b. � We now discard a and calculate the gcd of b and a % b. Crpto & SecDev 2017 © Ron Poet: Lecture 1 16 � We now discard a and calculate the gcd of b and a % b. �new_a = b, new_b = a % b. � A similar problem but with smaller numbers. �Keep going until a % b is 0. �The gcd is then b. � There is also a faster subtraction version of Euclid’s algorithm based on binary numbers. Recursive Algorithm Lint gcd(Lint a, Lint b) // a > b, Lint any big integer type
{
Lint c = a % b;
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
17
Lint c = a % b;
if (c == 0)
return b;
else
return gcd(b, c);
}
Iterative Algorithm
Lint gcd(Lint a, Lint b) // a > b
{
for (;;)
{
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
18
Lint c = a % b;
if (c == 0)
return b;
a = b;
b = c;
}
}
Example
a = 906659
b = 363532
179595
4342
1573
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
19
1573
1196
377
65
52
13
0
So gcd(906659, 363532) = 13
Binary Algorithm for GCD
� If a number n is even then it is easy to find out if it has any
factors of 2 and if so remove them.
�n & 0x1 gives us the last bit. If it is 0 then the
number is even.number is even.
�n >>= 1 shifts the bits along 1, dividing by 2.
� We can do this with both a and b, counting the number of
factors of 2 in each. g will have the minimum of these
two counts as its factors of 2.
� We can then consider the problem of finding gcd(a,b)
when a and b are odd.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
20
Binary Algorithm for GCD (2)
� First of all if a < b then swap them so that a > b.
� Let c = a–b, which is even, since both a and b are odd.
� The gcd of two odd numbers will be odd.
� Therefore we can remove all the powers of 2 from c, until � Therefore we can remove all the powers of 2 from c, until
we end up with an odd number.
� This will be smaller than a (assuming a > b), and so we
have a smaller problem, find the gcd of b and c.
� We stop when c = 1.
� This is faster because it does not involve division, an
expensive operation.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
21
Inverse Algorithm and Division
� The inverse algorithm solves the equation (find x given a
and n).
�ax ≡ 1 (mod n)
�The inverse of a is x.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
22
�The inverse of a is x.
� This also gives us a way to do division
�a / b (mod n) ≡ a * (1/b) (mod n)
� Dividing by b is the same as multiplying by 1/b.
Finding the Inverse
� The following equation is trivially true
n * x ≡ n (mod n)
� We want to solve
a * x ≡ 1 (mod n)
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
23
� We subtract the two equations to get a third equation.
� If the number on the right is negative, add n.
�This is allowed with integers mod n.
� Discard the equation with the largest number in front of x
and repeat.
� Stop when the number in front of x is 1.
Example
�Calculate the inverse of 8 mod 13.
13x ≡ 13 (mod 13) E1: always true
8x ≡ 1 (mod 13) E2: starting equation
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
24
8x ≡ 1 (mod 13) E2: starting equation
5x ≡ 12 (mod 13) E3: E1 – E2
3x ≡ -11 ≡ 2 (mod 13) E4: E2 – E3
2x ≡ 10 (mod 13) E5: E3 – E4
x ≡ -8 ≡ 5 (mod 13) E6: E4 – E5
�Check: 8 * 5 = 40 = 3*13 + 1
Remainder Algorithm
� An iterative algorithm based on remainders rather than
subtraction can also be used to calculate the inverse.
� It is more efficient than the subtraction algorithm, but this
simple algorithm is useful with small examples.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
25
simple algorithm is useful with small examples.
Exponential Algorithm
� Exponentiation is important for many encryption
algorithms.
�The RSA public key algorithm
�The Diffie-Helman algorithm for internet security.
� Here are the rules for exponentiation.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
26
� Here are the rules for exponentiation.
abac = ab+c
(ab)
c
= abc
Exponential Algorithm (2)
� Here is a fast algorithm.
�We prove it works using loop invariants.
� Note that the loop invariant is true at the start of the
algorithm.
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
27
algorithm.
� Both calculations preserve the invariant.
�If z is even then az = (a2)z/2
�If z is odd then az = a * az-1
Exponential Algorithm (3)
// Returns (a ^ z) % n
// Uses the loop invariant
// x * (a1 ^ z1) % n = (a ^ z) % n
// initially x=1, a1=a, z1=z
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
28
// initially x=1, a1=a, z1=z
// Terminates when z1 == 0,
// The answer is x
Exponential Algorithm (4)
Lint exponent(Lint a, Lint z, Lint n)
{
Lint x = 1; // build up result
Lint a1 = a; // build up powers
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
29
Lint a1 = a; // build up powers
Lint z1 = z; // reduce exponent
Exponential Algorithm (5)
while (z1 > 0)
{
while (z1 % 2 == 0) // even
{
z1 = z1 / 2;
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
30
z1 = z1 / 2;
a1 = (a1 * a1) % n;
}
// z1 must be odd here
z1 = z1 – 1; // z1 now even
x = (x * a1) % n;
}
return x;
}
Example 35 % 7
x a1 z1
Initially 1 3 5
z1 odd 3 3 4
z1 even 3 9≡2 2
Crpto & SecDev 2017 © Ron Poet:
Lecture 1
31
z1 even 3 9≡2 2
z1 even 3 4 1
z1 odd 12≡5 4 0
� So the answer is 5.