Monday, November 6, 2017

RSA Algorithm Explained with C code

An RSA algorithm is an important and powerful algorithm in cryptography. It is widely used in Digital Signature and in an SSL.  The algorithm works in the following way
  1. Select at random two LARGE prime number $p$ and $q$.
  2. Multiply $p$ and $q$ i.e. $n = p*q$.
  3. Select a small odd integer $e$ which is relatively prime to $\phi(n)$, where $\phi(n) = (p-1) * (q - 1)$.
  4. Calculate the value of $d$ (explained below). $d$ is calculated as a modular multiplicative inverse of $e$ modulo $n$.
  5. Publish the pair $P = (e, n)$ as a public key. 
  6. Keep secret the pair $S = (d, n)$ as a private key. 
The message is encrypted using $P = (e, n)$ using following formula. 
\[P(M) = M^e \text{ mod } n\]
The message can be decrypted using $P = (d, n)$ using following formula.
\[S(C) = C^d \text{ mod } n\]
Secret key pair $(d, n)$ should be kept secret.

Calculation of Modular Exponentiation in C

Modular Exponentiation takes the following form.
\[A = B^C \text{ mod } D\]
Efficient calculation of modular exponentiation is critical for many cryptographic algorithms like RSA algorithm. The following program calculates the modular exponentiation. The method of repeated squaring solves this problem efficiently using the binary representation of C.

This code is also available on GitHub.

Sunday, November 5, 2017

C Code For Solving Modular Linear Equations

The Extended Euclid's Algorithm solves the equation of the form
\[ GCD(a, n) = d = ax + ny \]
If we multiply the both sides by (mod n), we get
\[ ax + ny \equiv d (\text{ mod } n) \]
This is equivalent to,
\[ ax \equiv d (\text {mod } n)\]
In this article, I present a C Programming Code to solve this type of modular linear equation. 

Congruence Modulo

You just saw a weird kind of mathematical expression of the form
\[ A \equiv B (\text { mod } C) \]
This says that A is congruent to B modulo C. What does it mean? Before I tell you the meaning of above operator, please note that this kind of expression is every common in number theory. If you are interested in Cryptography and starting to learn it, you will encounter this operator numerous time. Lets take an example,
\[ 21 \equiv 5 (\text { mod } 4) \]
A symbol $\equiv$ means "Equivalence". In above equation, 21 and 5 are equivalent. This is because 21 modulo 4 = 1 is equal to 5 modulo 4 = 1. Another example is $51 \equiv 16 (\text{ mod } 7)$

The value of x can be more than one depending upon the GCD of a and n. There are always d number of solutions of x where d = GCD(a, n). If a and n are relatively prime i.e. GCD is 1, there is only one unique solution and this is very important for calculating secret key in RSA algorithm.

Extended Euclid's Algorithm C Code

Before going through this article, please look at my previous article about Euclid's Algorithm. The Extended Euclid's algorithm solves the following equation.
\[GCD(a, b) = d = ax + by\]
In addition to calculating a GCD, it calculates coefficients x and y such that satisfies the above equation. These coefficients x and y are important for calculating modular multiplicative inverses. The Extended Euclid's algorithm is used in a much practical application specifically in cryptography.

The following C code presents the efficient algorithm to solve Extended Euclid's algorithm. The code is also available on GitHub.

Euclid's Algorithm C code

Euclid's algorithm calculates the GCD (Greatest Common Divisor) for two numbers a and b. The following C program uses recursion to get the GCD.

The code is also available on GitHub.

#include <stdio.h>

int euclid(int a, int b) {
 if (b == 0) {
  return a;
 } else {
  return euclid(b, a % b);
 }
}

int main(int argc, char* argv[]) {
 int a = 30, b = 21;
 printf("GCD is %d\n", euclid(a, b));
 return 0;
}

Monday, October 23, 2017

Fastest Fibonacci Sequence/Number Computation

The fastest way (in O(n)) of calculating Fibonacci sequence is by using matrix multiplication approach using following relation.
\[\begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}^n = \begin{bmatrix} F_{n - 1} & F_n \\ F_n & F_{n + 1}\end{bmatrix}\]
Calculating $F_{34}$ is, therefore, multiplying the matrix $\begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}$ 34 times. The $a_{01}$ or $a_{10}$ gives the right fibonacci number. In fact $F_{34}$ can be calculated in less than 34 multiplication in following away.
\[ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{34} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{2} \\\]
This means, the multiplication can be done in logarithmic time. The C code for this computation is given below (also available on GitHub).

Thursday, October 19, 2017

Selection Algorithm implementation in C

How do you find out a median of an array? If someone asks you this question, you will immediately say "First sort it and then find the $\left ( \frac{n}{2}\right)^{th}$ element". Of course, this is correct. But what's the runtime? hmmm... the lower bound of any comparison based sorting algorithm is a ceiling of $\log_2(n!)$ which is in order of $\Theta(n\log_2n)$. No matter what sorting algorithm do you use, the running time is $\Omega(n\log_2n)$. Can we do better? That is, can we find a median of an array in linear time?. The answer is yes. The following code calculates the median of an array in $O(n)$ time. The algorithm is called 'Selection algorithm'. This algorithm calculates the '$k_{th}$' smallest value. Median is, therefore, $\left ( \frac{n}{2}\right)^{th}$' smallest element. The algorithm works as follows: (The code is also available on GitHub)

Largest and Smallest Element of an Array in C

Calculating largest and smallest element in C is straightforward. All you have to do is scan through the array one element at a time and compare it with current largest or smallest value. Since you scan every element of array, there will be n (number of elements in the array) comparisons. Therefore the running time of this algorithm is $\Theta(n)$.

Calculation of Largest Element
int get_largest(int a[], int n) {
 int i, largest = 0;
 for (i = 0; i < n; i++) {
  if (a[i] > largest) {
   largest = a[i];
  }
 }
 return largest;
}

Calculation of Smallest Element
int get_smallest(int a[], int n) {
 int i, smallest = 2147483647;
 for (i = 0; i < n; i++) {
  if (a[i] < smallest) {
   smallest = a[i];
  }
 }
 return smallest;
}

This code is also available in GitHub.