Introduction to Cryptography Part 4

In this Part we will continue our discussion about the mathematical side of cryptography, In this Part we will discuss important topic prime numbers which is one of the fundamentals things to understand Modern public key cryptography.

prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number.

Wikipedia

That’s Wikipedia definition I have a more simple definition

An integer is called a prime number if p >= 2 and only is divisible by itself or by 1

For example the first 5 prime numbers are {2, 3, 5, 7, 11} notice that 2 is the only even number and prime.

If we factorize a positive integer a into primes, each prime number appears to a specific power, and we use ord_p(a) = e where p means the prime number , a is the number we want to factorize and e is the exponent raised to the prime number .

Example 4.1 : the factorization of 1728 is 1728 = 2^6 . 3^3, so

we write ord_2(1728) = 6, ord_3(1728) = 3.

Now we will start a new concept after we have good understanding about modulo classes in part 3 of this series, we begin by introducing Integer Rings definition and it’s properties, a Ring is a set of elements with two binary
operations, called addition and multiplication. The integer ring Z_m consist of:

  • The set of Z_m = {0, 1, 2, …, m-1}
  • two operations ‘+’ and ‘×’ for all a, bZ_m such that :
    1. a + b ≡ c mod m , (c ∈ Z_m)
    2. a × b ≡ d mod m , (d ∈ Z_m)

The properties of the ring are:

  1. We can add and multiply two numbers and the result is always in the ring
  2. Addition is always associative (e.g) a + (b + c) = (a + b) + c for all a,b,c ∈ Z_m
  3. There is a neutral element (identity element) with respect to addition, for every element a ∈ Z_m it holds that a + 0 ≡ a mod m.
  4. For any element a in the ring the additive inverse always exists a + (-a) ≡ 0 mod m
  5. There is a neutral element (identity element) with respect to multiplication, for every element a ∈ Z_m it holds that a × 1 ≡ a mod m.
  6. The multiplicative inverse exists only for some, not all element in the ring, such that if a ∈ Z then the inverse of a^-1 is defined as follows a × a^-1 ≡ 1 mod m.

Now we are interested on how to get the multiplicative inverse because this is very important to be understood for most of the public key Cryptography Algorithms especially for RSA cryptography system.

We’ve discussed in part 3 of this series of to get gcd of two numbers if you , please make sure to understand the gcd algorithm because we will build upon it.

Extended Euclidean Algorithm (EEA) , we have seen that finding the gcd(a,b) gives us the greatest common divisor between two numbers (EEA) allows us to write the linear combination of those numbers of the form:

gcd(a, b) = q × a + g × b where q , b are integer coefficients. Let’s dive into an Example to make things more easier

Example 4.2 Consider the following:

a = 973, b = 301

The procedure is as follows:

  1. We get the gcd value of the two numbers
  2. We keep the reminder on one side of the equation
  3. To make things more easier we change the numbers by there corresponding symbol
  4. we substitute equation 1 into equation 2 then equation 1 and equation 2 into equation 3 etc .. , think of it recursively.

Step 1 :

973 = 3 × 301 + 70

301 = 4 × 70 + 21

70 = 3 × 21 + 7 -> this our gcd(973, 301) = 7

21 = 7 × 3 + 0

Step 2 :

70 = 973 – 3× 301

21 = 301 – 4×70

7 = 70 – 3×21

Step 3 :

70 = a – 3×b -> equation 1

21 = b – 4×70 -> equation 2

7 = 70 – 3×21 -> equation 3

Step 4 :

21 = b – 4×(a – 3× b) -> we substituted equation 1 into equation 2

after basic math calculations we get.

21 = 13×b – 4×a

7 = ( a – 3×b ) – 3×(13×b – 4×a) -> we substituted equation 1 and equation 2 into equation 3.

after basic math calculations we get.

7 = 13×a – 42×b

so now we can write the gcd(973, 301) as linear combination of form:

7 = 973×(13) × (-42)×301 = 12649 – 12642.

We will take another example to make things more clear

Example 4.3 Consider the following:

We want to get the multiplicative inverse of 12 in ring of 67 ( Z_m) , first we make sure that the two numbers are relatively prime so we know that 12 has multiplicative inverse in ring of 67, in order for this condition to be satisfied the gcd(67, 12) must be equal to 1, gcd(67, 12) = 1 I’ll leave this as an exercise for the reader.

Now we will apply EEA to obtain the coefficients.

a = 67, b = 12

Step 1

67 = 5×12 + 7

12 = 1×7 + 5

7 = 5 × 1 + 2

5 = 2 × 2 + 1 -> gcd(67, 12)

2 = 2×1 + 0

Step 2, 3

7 = a – 5×b

5 = b – 7

2 = 75

1 = 5 – 2 × 2

Step 4

5 = b – ( a – 5×b ) = 6×b – a

2 = ( a – 5×b ) – 11( 6×b – a ) = 2×a – 11×b

1 = ( 6×b – a ) – 2 ( 2×a – 11×b ) = 28 × b – 5 × a

So now we can write the gcd(67, 12) as linear combination of form:

(-5) × 67 + (28) × 12 = 1.

So the inverse of 12 is 28:

28 × 12 ≡ 1 mod 67.

Note that (-5) coefficient is not needed.

Python code for (EEA)

def egcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

The Fast Powering Algorithm, this algorithm allows us to compute large powers of constant g modulo N where N may have hundreds of digits and thus we have to learn it for RSA and DH cryptosystems.

The native way to compute to compute g^A is by repeated multiplication by g.

g_1 ≡ g (mod N), g_2 ≡ g · g_1 (mod N). etc ….. you get the point.

But what if A is very large. For example A = 1000, 2^1000 then repeated multiplication would take very long time.

Example 4.4 Suppose that we want to compute 3^218 (mod 1000) .

Here’s our procedure:

  1. Write the exponent as powers of 2 by using binary representation of the exponent.
  2. Create Table list the powers of 3 mod 1000
  3. Each successive entry in the table is equal to the square of the previous entry

Step 1

218 = 2 + 2^3 + 2^4 + 2^6 + 2^7

3^218 = 3^2 . 3^2^3 . 3^2^4 . 3^2^6 . 3^2^7

Step 2

i01234567
3^2^i (mod 1000)3981561721841281961

Step 3

3^218 = 3^2 . 3^2^3 . 3^2^4 . 3^2^6 . 3^2^7

3^218 ≡ 9 . 561 . 721 . 281 . 961 (mod 1000).

3^218 ≡ 489 (mod 1000).

Note that in computing the product of 9 . 561 . 721 . 281 . 961 we reduced to modulo of 1000 after each multiplication so we don’t need to deal with very large number.

Example 4.5 Suppose that we want to compute 47^69 (mod 143)

Step 1

69 = 2^0 + 2^2 + 2^6

47^69 = 47 . 47^2^2 . 47^2^6

Step 2

i0123456
47^2^i (mod 143)47649227145392

Step 3

47^69 = 47 . 47^2^2 . 47^2^6

47^69 ≡ 47 . 92 . 92 (mod 143)

47^69 ≡ 47 . 92 . 92 (mod 143)

Note that in computing the product of 47 . 92 . 92 we reduced to modulo of 143 after each multiplication so we don’t need to deal with very large number.

Well that’s it for this part, please if you have any question or idea to improve my articles feel free to e-mail me on omarobaniessa@gmail.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s