Lesson 1 : Introduction to Congruence and Modular Arithmetic



000010100100110100101010101001010101001010100101010101010010101010100101010101011101010101001100101010010101010010000101010101110100101010010101001011111011010010100101001010101001101001010010001011111010010110010101000111001010101001001010010100010101011010101100101000101101001010100101010101001010100101010100101001010101010100101010010101010010101011001010101010010100101010100101010010100101010010101001000101001010110010101001010100101010100101010101001010100101010101101001010100110010100011101001010100101010100101010100101010101001010101010010101010010101010010010101001001010101001010100101001010101010001010101001010100101010101001010101010101001010100101011010010101010101010100100

Chapter 4: Some Basic Number Theory

Number theory is a branch of pure mathematics that deals with the properties of numbers, with integers in particular. In this elective, we will introduce some topics in number theory involving integers that we require to better appreciate modern day cryptography.

Some Background Information:

Before the discovery of public key cryptography, encryption and decryption of ciphers involved the two communicating parties to have a secure prior agreement on the keys to be used in the cipher. This means that the two parties must trust each other in the handling of the keys, and keep the keys private, i.e., private key cryptography, as the decryption keys can be easily obtained from the encryption keys, and vice versa.

However, with the invention of the internet, there is a need to create a public key, such that people are able to use the key to encrypt their information, e.g., credit card pin for payment, and yet no one should be able to decrypt the information from the encryption key itself. Only through the field of mathematics, are we able to create this “Trapdoor function” where the above is possible.

“Mathematics is the queen of the sciences and number theory is the queen of mathematics.”

– Gauss

Section 4.1 Clock Mathematics!

Okie! In this section 4.1, we will learn about clock mathematics! Hmm, so it isn’t really called clock mathematics in real life. It is one branch of mathematics called modular arithmetic under congruence, but it really just works the same way as a clock. If you can read a clock, you can do basic congruence. (

4.1.1 Introduction to Congruence

Definition 1:

Suppose that a and b are two integers and n a positive integer. We say that a is congruent to b if n divides a ( b, written as a ( b (mod n).

Layman Definition 1:

In layman terms, it means a and b are congruent to each other if they have the same remainder after been divided by n.

For example,

1. Seconds and minutes:

90 ( 30 (mod 60),

75 ( 15 (mod 60),

(5 ( 55 (mod 60).

2. Hours:

15 ( 3 (mod 12),

48 ( 0 (mod 12),

(3 ( 9 (mod 12).

3. Days of the week:

8 ( 1 (mod 7),

(8 ( 6 (mod 7),

14 ( 0 (mod 7).

Example 1: Decide which of the following congruences are true and which are false.

(a) 18 ( 3 (mod 5) (b) 18 ( -3 (mod 6) (c) 35 ( 9 (mod 4) (d) -17 ( 3 (mod 4)

So, was that easy? ( Now, we move on to slightly more advanced stuff.To understand and prove congruence, we just need to use one definition.

If a ( b (mod n), then we can always write a = kn + b, for some integer k.

AND, it is always possible to find b such that 0 ( b < n. (Why? Remainder lo!)

Theorem 1: Properties of Congruence

Below are some properties of congruence. Some of the properties are given. Fill the empty spaces with other properties that you may discover.

Let n and k be positive integers and a, b, c, d be integers. Then

(a) a ( a (mod n). [reflexive]

(b) If a ( b (mod n), then b ( a (mod n). [symmetric]

(c) If a ( b (mod n) and b ( c (mod n), then a ( c (mod n). [transitive]

(d) If a ( b (mod n) and c ( d (mod n), then a + c ( b + d (mod n).

(e) If a ( b (mod n) and c ( d (mod n), then ac ( bd (mod n).

(f) If a ( b (mod n), then ak ( bk (mod n)

(g) If a ( b (mod n), then ka ( kb (mod n).

[Warning: the reverse for the above conditions may not be true.]

So, if you want to simplify congruence, you will need to use the above!

Example 2:

By using the properties of congruence, find the remainder (without using a calculator) when

(a) 238 is divided by 7 (b) 4100 is divided by 10 (c) 456 is divided by 13

Solution:

(a) 23 = 8 ( 1 (mod 7).

So using Property (f) above, 812 ( 112 (mod 7), i.e., 236 ( 1 (mod 7)

Since 22 ( 22 (mod 7), we have 236 . 22 ( 1 . 22 (mod 7)

Hence, 238 ( 4 (mod 7). Thus the remainder is 4.

(b)

(c)

Section 4.2 Modular Arithmetric and Euclidean Algorithm

Ok. Now that you realized that congruence are sometimes, not so easy to find, I will impart you some secrets of the trade, i.e., some formulas and tricks to simplify congruence. But first, you need to understand some terms.

4.2.1 Introduction to Prime and Composite Numbers

All integers are built up from the most basic elements – “indivisible units” called prime numbers or what we simply call primes.

Definition 1: Prime Numbers

A prime number is a positive integer p which is greater than 1 and is divisible by 1 and p only.

The first few primes are 2, 3, 5, 7, 11, etc, and the only even prime number is 2. (Why?)

Definition 2: Composite Numbers

A composite number is a positive integer n, greater than 1, and has a factor other than 1 and n.

(Hence, if P is the set of prime numbers, then the set of composite numbers C = (+ ( P.)

Definition 3: Greatest Common Divisor (gcd)

The greatest common divisor of any two positive integers, a and b, i.e., gcd(a, b), is the highest common factor of the two numbers. E.g., gcd(42, 54) = 6.

Definition 4: Coprime

Two positive integers a and b are coprime to each other if gcd(a, b) = 1. (In other words, the two numbers have no common factors other than 1).

E.g., 10 and 21 are coprime to each other as gcd(10, 21) = 1, although 10 and 21 are composite numbers.

Activity 1: Internet Search (Questions Questions Questions)

What is the greatest prime number discovered today? How did we find this number? Does the largest prime number exist? Can you prove it?

4.2.2 Euler’s Phi Function and Euler’s Theorem

Theorem 1: Fermat’s Little Theorem

Let p be a prime and suppose that p does not divide a. Then ap – 1 ( 1 (mod p).

Hence, if p is a prime, then ap ( a (mod p) for any integer a.

Example 1:

Use Fermat’s Little Theorem to find the remainders when

(a) 318 is divided by 19;

(b) 355 is divided by 19; (note that : 55 = 3 ( 18 + 1)

(c) 16103 is divided by 11.

Ok, so the above only works for modulo primes. To learn more tricks, we have to learn a bit more now. By the way, the above theorem can be used as a check for primes! If the above condition is not true for any number x, we know for sure it is not a prime!

Definition 1: Euler’s Phi Function / The indicator or Totient function

For n ( 1, let ( (n) denote the number of positive integers not exceeding n that are coprime to n.

A few first values:

((1) =1, ( (2) = 1, ( (3) = 2, ( (4) = 2, ( (5) = 4, ( (6) = 2, ( (7) = 6,

( (8) = 4, ( (9) = 6, ( (10) = 4, ( (11) =10, ( (12) = 4, ( (13) = 12, etc.

Example 2: Find ( (15) and ( (19).

Below are some useful results involving the Euler’s Phi Function.

Theorem 2: For n > 1, ( (n) = n – 1 if and only if n is a prime number.

Theorem 3: If p is a prime and k > 0, then ( (pk) = pk – pk – 1 = [pic].

E.g., ( (27) = 33 (1 – [pic]) = 33 ( [pic] = 18.

Theorem 4: The function ( is a multiplicative function, i.e., ( (pq) = ( (p) ( ( (q), when p and q are coprime to each other.

E.g., ( (21) = ( (3) ( ( (7) = 2 ( 6 = 12.

Example 3: Find ( (1800) and ( (1323).

Theorem 6: Euler’s Theorem

If n ( 1 and gcd (a, n) = 1, then a( (n) ( 1 (mod n).

Note: Euler's Theorem is a generalization of Fermat's Little Theorem. Why?

Also, a must be coprime to n.

Example 4:

Use Euler’s Theorem to find the remainders when

(a) 5228 is divided by 21.

(b) 7174 is divided by 10;

(c) 5228 is divided by 36;

(d) 1818240 is divided by 18527.

In fact, examples like d is the basis of the modern cryptosystems. Just that, the prime numbers used are very very large. Before we can go to these system, we need just a bit more.

4.2.3 Modular Addition and Multiplication

Definition 5: Modular Addition and Multiplication

We define the set (n = {0, 1, 2, …, n – 1} and the operation +n and (n as follows :

a +n b : the remainder when (a + b) is divided by n and

a (n b : the remainder when (a ( b) is divided by n, where a, b ( (n.

Note: We usually use the set [pic] to denote the set {1, 2, …, n – 1}, i.e., no zero element.

For example, if a (25 b = 1, then when ab is divided by 25 the remainder is 1.

We can write: ab = 25k + 1 where k is the quotient, an integer.

Or ab ( 1 (mod 25)

Example 1:

For (5 = {0, 1, 2, 3, 4 }, we have the following tables for modular addition and multiplication.

Definition 6a: Additive Identity Element and Additive Inverse

In the table above for +5, we see that any element in (5 , say a, a +5 0 = a and 0 +5 a = a.

We say that 0 is the additive identity element in (5.

We also notice that 1 +5 4 = 0 , 4 +5 1 = 0, 2 +5 3 = 0 and 3 +5 2 = 0.

We say that 1 is the additive inverse of 4 in (5 and 2 is the additive inverse of 3 in (5.

It is clear from the table that any number multiplied with zero will give zero, which is not very useful in our following discussions. Hence, we now discuss all the elements in (5, except the element 0, i.e., (5 ({0} or [pic].

Definition 6b: Multiplicative Identity Element and Multiplicative Inverse

In the table above for (5, we see that any element in [pic] , say a, a (5 1 = a and 1 (5 a = a.

We say that 1 is the multiplicative identity element in [pic].

We also notice that 2 (5 3 = 1 , 3 (5 2 = 1, and 4 (5 4 = 1.

We say that 2 is the multiplicative inverse of 3 in [pic]and 4 is the multiplicative inverse of itself in [pic].

Example 2:

(a) For (7 = {0, 1, 2, 3, 4, 5, 6} and [pic] = {1, 2, 3, 4, 5, 6}, complete the following tables.

(b) What is the additive inverse and multiplicative inverse of 5 in (7 and [pic] respectively?

Note: From the Table above we see that each element in [pic] has a multiplicative inverse.

Example 3: Complete the following tables.

Question: What can you say about the inverse elements in both tables?

Observation 1:

For modular multiplication, (n, in [pic] where n is a prime number, all elements in [pic] have multiplicative inverse.

However, for (n, in [pic] where n is a composite number, numbers that share common factors as n, other than 1, will have no multiplicative inverse in [pic]. (in other words, only numbers that are coprime to n have multiplicative inverse in [pic].)

Why are we learning additive and multiplicative inverse?

We need the use of ideas of additive and multiplicative inverse of numbers when we try to use modular arithmetic in our cryptosystems.

Additive inverse is easy enough, but multiplicative inverses are really a bug. Hence, we need to discuss the follow method to obtain a multiplicative inverse of a number.

4.2.4 Euclidean Algorithm

Given any two positive integers a and b, we can find the greatest common divisor of a and b by listing down all the factors of a and b, and finding the common factors.

For example, gcd(276, 126) = 6, since   276 = 22 . 3 . 23   and   126 = 2 . 32 . 7.

However, this is a long and tedious process if a and b are large numbers. There must be a more efficient way, since Maple (a Mathematical software, see ) can calculate the gcd of two 60-digit numbers in well under a second, while taking a long time (about 10 minutes on a 600 Mhz pentium computer) to factorize either one of them.

We now introduce the Euclidean Algorithm, which has been around thousands of years, and it will enable us to find the greatest common divisor easily for such numbers.

Algorithm 1: Euclidean Algorithm

Example 4: Find the greatest common divisor of 274 and 126.

276 = 2 ( 126 + 24 (Divide 274 by 126, getting remainder 24.)

126 = 5 ( 24 + 6 (Divide 126 by the remainder 24)

24 = 4 ( 6 + 0 (Divide 24 by the remainder 6)

The algorithm terminates when the remainder (calculated at each step) becomes zero. The previous remainder calculated is the greatest common divisor. Hence, gcd(274, 126) = 6.

Example 5: Find the greatest common divisor of (a) 344 and 560, (b) 414 and 322.

Observation 2:

From Observation 1 on page 8, only numbers, a, that are coprime to n, (i.e., gcd(a, n) = 1) have multiplicative inverse in [pic]. For small n, we can check the modular multiplication table for [pic] to find the multiplicative inverse (if it exists) of an element in [pic].

However, if n is large, the Euclidean Algorithm will again be more efficient in finding the multiplicative inverse of an element. Hence, if we obtain gcd(a, n) = 1 from the Euclidean Algorithm, we can use the steps involved to find the multiplicative inverse of a in [pic].

Algorithm 2: “Extended” Euclidean Algorithm

Example 6: Suppose we want to find the multiplicative inverse of 9 in [pic]

25 = 2 ( 9 + 7 (Divide 26 by 9, getting remainder 7.)

9 = 1 ( 7 + 2 (Divide 9 by the remainder 7)

7 = 3 ( 2 + 1 (Divide 7 by the remainder 2)

2 = 2 ( 1 + 0 (Repeat the steps until we reach 0)

(Hence, gcd(9, 25) = 1.)

Now, we start to write the steps“backwards” as follows:

1 = 7 – 3 ( 2

2 = 9 – 1 ( 7

7 = 25 – 2 ( 9

We will now eliminate 2 and 7 as follows:

1 = 7 – 3 ( (9 – 1 ( 7) = ((3) ( 9 + 4 ( 7

= ((3) ( 9 + 4 ( (25 – 2 ( 9)

= 4 ( 25 – 11 ( 9

So we have 9 ( (–11) = ((4) ( 25 + 1, which means 9 ( ((11) (1 (mod 25).

But (–11) is not in (25. However, since –11 ( 14 (mod 25), so 9 ( (14) (1 (mod 25).

Hence, we have 14 as the multiplicative inverse of 9 in (25. (Check that 9 ( 14 = 5 ( 25 + 1).

Example 6: Find the multiplicative inverse of (a) 5 in [pic] (b) 8 in [pic]

Section 4.3 Applications in Cryptography

(A) General Shift Cipher (The General Form of Shift Cipher)

(B) Multiplicative Cipher

(C) Affine Cipher (Combination of Multiplicative and Shift Cipher)

(C) Exponential Cipher

(A) General Shift Cipher

We also call the shift cipher the Additive cipher. This is especially clear when we use the set (26 and +26 to define the cipher.

We associate each letters by a number as follows :

ABC …….WXYZ123  ..…..2324250So written in (26, the plaintext < ATTACKTONIGHT> appears as a sequence

.

In Caesar cipher, we can define it using the following encryption key:

Given that m and c are corresponding letters in the plaintext and the ciphertext,

Encryption Key: f(m) = m +26 3 = c

So f(1) = 1 +26 3 = 4, f(20) = 20 +26 3 = 23 etc

Hence, the ciphertext is

To decipher the text, the receiver must know the additive inverse of 3 in (26, which is 23 as

3 +26 23 = 0. For example, 4 +26 23 = 1 -- represents A indeed.

Hence, the decryption key is as follows:

Decryption Key: f(1(c) = c +26 23 = m.

It should be clear that the decryption key can be easily obtained if one knows the encryption key.

Hence, the general shift cipher is defined as follows mathematically:

Let n be a positive integer and k be in (n with k ( 0. The additive cipher based on k is

c = f(m) = m +n k where m is a string of numbers representing the text message. k here is called the key. Equivalently, c = f(m) ( m + k (mod n)

To decipher the text, we have m = f(1(c) = c +n k( where c is the ciphered text and k( is the additive inverse of k in (n (that is k + k( = 0). Equivalently, m = f(1(c) ( c – k (mod n).

Exercise 1:

Encipher the message BE BACK AT 1150 using the following encoding of symbols :

0 = 00, 1 = 01, 2 = 02, … , 9 = 09, A = 10, B =11, C = 12, …., Y = 34, Z = 35.

And an additive cipher with key k = 14. (i.e., shift forward by 14)

Solution

From the plaintext (a sequence of numbers representing the message) :

m :

We compute the relevant values of c = f (m) = m + 14 (mod 36). Why mod 36?

m 11 14 11 10 12 20 10 29 01 01 05 00

c 25 28 25 24 26

The ciphertext is:

(B) Multiplicative Cipher

Let n be a positive integer and k in (n be coprime with n.

Then for any plaintext to be encrypted, m, and the its corresponding ciphertext¸ c, the multiplicative cipher is defined as follows:

Encryption Key: Ek (m) = k (n m = c (mod n)

Decryption Key: [pic](c) = k( (n c = m. (mod n) (where k( is the multiplicative inverse of

k in (n)

Example 2:

A multiplicative cipher on (26 is defined by the function G7(m) = 7 (26 m.

(i) Determine the multiplicative inverse of 7 in (26.

(ii) A message is enciphered using G7 to give the ciphertext

where 1 represents A and 0 represents Z.

What is the original message?

Solution:

(C) Affine Cipher

It is clear that the shift cipher is not a very strong cipher, with only a small number of possible keys. Hence, using the set of modular arithmetic that we used to define the shift cipher earlier, we now use the same tools, with the additional tool of (n, to define another cipher, the Affine cipher. We also make use of the multiplicative cipher to define the Affine Cipher.

Encryption key: f(m) = (a ( m) + b ( c (mod n).

Decryption key: f(1(c) = (c ( b) ( a(1 ( m (mod n).

Question: 1) Are there any restrictions to note, when choosing a?

2) How many keys are there in affine ciphers using English alphabets?

Exercise 3:

Encipher the message using the affine cipher, where a = 7, b = 5.

Answer:

Decipher the message

Answer:

(D) Exponential Cipher

Before the discussion on public key cryptography, we now discuss an exponential cipher that will incorporate some of the essentials concepts required in public key cryptography.

Exponential Cipher

Let p be a prime number and k in [pic]such that k is coprime to p – 1.

The exponential cipher Ek on [pic] uses the following encryption and decryption keys below.

For any number m and c,

Encryption key: Ek(m) ( mk (mod p)

Decryption key: [pic](c) ( [pic] (mod p) where k( is the multiplicative inverse of k in [pic].

Note: The decryption key can be obtained just from the encryption key.

Example 4: An exponential cipher is defined on (29 by E(m) ( m3 (mod 29).

(i) Determine the multiplicative inverse of 3 in (28.

(ii) A message is enciphered using E above to give the ciphertext : < 8, 9 >.

What was the plaintext?

Solution:

(i)

(ii)

-----------------------

| |0 |1 |2 |3 |4 |5 |

| | | | | | | |

| | | | | | | |

| | | | | | | |

| | | | | | | |

|(6 | | | | | | |

|1 | | | | | | |

|2 | | | | | | |

|3 | | | | | | |

|4 | | | | | | |

|5 | | | | | | |

|(7 |0 |1 |2 |3 |4 |

|1 |0 |1 |2 |3 |4 |

|2 |0 |2 |4 |1 |3 |

|3 |0 |3 |1 |4 |2 |

|4 |0 |4 |3 |2 |1 |

|+5 |0 |1 |2 |3 |4 |

|1 |1 |2 |3 |4 |0 |

|2 |2 |3 |4 |0 |1 |

|3 |3 |4 |0 |1 |2 |

|4 |4 |0 |1 |2 |3 |

|+6 |0 |1 |2 |3 |4 |5 |

|1 | | | | | | |

|2 | | | | | | |

|3 | | | | | | |

|4 | | | | | | |

|5 | | | | | | |

+7 |0 |1 |2 |3 |4 |5 |6 | |0 |0 |1 |2 |3 |4 |5 |6 | |1 |1 |2 |3 |4 |5 |6 |0 | |2 |2 |3 |4 |5 |6 |0 |1 | |3 |3 |4 |5 |6 |0 |1 |2 | |4 |4 |5 | | | | | | |5 |5 | | | | | | | |6 | | | | | | | | |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download