程序代写代做代考 algorithm 17crypto_L01

17crypto_L01

Modular Arithmetic

Crpto & SecDev 2017 © Ron Poet:
Lecture 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

�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

�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

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

� 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 = 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

� 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

� 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

�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

� 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

� 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

�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

� 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

� 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

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

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

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

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

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

�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)

� 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

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.

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.

� 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.

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

// 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

Lint z1 = z; // reduce exponent

Exponential Algorithm (5)

while (z1 > 0)
{
while (z1 % 2 == 0) // even

{
z1 = z1 / 2;

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

z1 even 3 4 1

z1 odd 12≡5 4 0

� So the answer is 5.

Published by admin

Leave a Reply Cancel reply