Tag: cryptosystems

RSA (cryptosystem) – Part 1 (Simple mathematics)

In this post, I am going to explain exactly how RSA public key encryption works. Before start coding and using the Secure Socket Layer we need to understand the base algorithm on which it works and RSA is one of the popular algorithm under its wing. Everything in this post (including this one) are very mathematical, I am going to try and make this break down in some important concepts and make it simple with examples.

I would suggest not the use any of the example in the real world scenario as this algorithm requires to work with a secure padding structure.

Background Mathematics – The thing which makes wonders

Set Of Integers : Modulo P

Zp={0,1,2,…,p−1}

This is called the set of integers modulo p (or mod p for short). It is a set that contains Integers from 0 up until p−1.

Example: Z10={0,1,2,3,4,5,6,7,8,9}

Remainder After Division

This concept mostly we have all learnt in School, as for example if we divide 7 by 2, we get remainder as 1. This is stated without any notion of real numbers, only integers. This type of math is really vital to RSA, and is one of the reasons that secures RSA. A formal way of stating a remainder after dividing by another number is an equivalence relationship:

x,y,z,k∈Z, x≡ymodz ⟺ x=k⋅z+y

This equation states that if x is equivalent to the remainder (in this case y) after dividing by an integer (in this case z), then x can be written like so: x=k⋅z+y where k is an integer.

Example: Let’s take y =7 and z=5, then the following values of x will hold for the equation:  x=7,x=12,x=17,…. There are all sought of possibilities to get the value of if we keep on changing the value of k. Therefore, x can be written like so: x =k⋅5+7, where k can be any of the infinite amount of integers.

There are two important things to note:

  1. The remainder stays constant always.
  2. As we stated earlier, y∈Z(y is in the set of integers modulo z)

Greatest Common Divisor and Multiplicative Inverse

A multiplicative inverse for x is a number that when multiplied by x, will be equal to 1. The multiplicative inverse of x is written as x−1 and is defined as so:

x⋅x−1=1

The greatest common divisor (gcd) between two numbers is the largest integer that will divide both numbers. For example, gcd(3,8)=2.

The interesting thing is that if two numbers have a gcd of 1, then the smaller of the two numbers has a multiplicative inverse in the modulo of the larger number. It is expressed in the following equation:

x∈Zp,x−1∈Zp⟺gcd(x,p)=1

The above just says that an inverse only exists if the greatest common divisor is 1.

Example: Lets work in the set Z11, then 3∈Z11 and gcd(3,11)=1. Therefore 3 has a multiplicative inverse (written 3−1) in mod11, which is 4. And indeed, 4⋅3=12=1mod11. But not all numbers have inverses. For instance, 3∈Z9 but 3−1does not exist! This is because gcd(3,9)=3≠1.

Let me just give a more detailed version of how this works:

Consider the modular multiplicative inverse of 3 modulo 11, call it x. In order for x to exist it must be that 3 and 11 are co-prime, which is true.

x=3-1mod11

This is equivalent to the computation of finding x such that

3.x = 1.mod11

By observation the one positive value of x that satisfies this equation is is 4 since

3.4=12=1mod11

As 12 divided by 11 will give you remainder as 1 and thus the equation can be written as above.

Prime Numbers

Prime numbers are very important to the RSA algorithm. A prime is a number that can only be divided without a remainder by itself and 1. For example, 7 is a prime number (any other number besides 1 and 7 will result in a remainder after division) while 10 is not a prime.

This has an important implication: For any prime number p, every number from 1 up to p−1 has a gcd of 1 with p, and therefore has a multiplicative inverse in modulo p.

Euler’s Totient

Euler’s Totient is the number of elements that have a multiplicative inverse in a set of modulo integers. The totient is denoted using the Greek symbol phi (ϕ). The totient is just the count of the number of elements that have their gcd with the modulus equal to 1. This brings us to an important equation regarding the totient and prime numbers:

p∈P, ϕ(p)=p−1

Example: ϕ(9)=|{1,2,4,5,7,8}|=6

As gcd(9,3) =3, gcd(9,6)=3 and gcd(9,9)=9. So only 6 values with which 9 has greatest common divisor as 1.

With the above background, we have enough tools to describe RSA and in the next post we will see, How the RSA algorithm works.

Sources:

Advertisements