Introduction: A Walk in the Park of Cryptography.
Cryptography is the art of hiding information and it has been a friend to humans for a rather long period of time. Here i will be presenting a few algorithms with it's logic, code and the math behind them.
Step 1: PRNG - Algortihm : (Linear_Congruential_Generator)
PRNG algorithm stands for Pseudo-Random Number Generating algorithm. In cryptography generating a random number are extremely important, even in day to day programming random numbers have a great role to play.
I would start by showing a very basic PRNG algorithm.
LCG is a Pseudo-Random Number Generating algorithm. This algorithm is used by languages like Java. The random numbers are calculated with a discontinuous piecewise linear equation.
The math behind it :-
X n + 1 = ( a X n + c ) mod m
X n + 1 ---> next random number
Xn -----> current random number
a ----> multiplyer
c ----> incremeant
m ----> modulos
values for a,c,m are selected before hand , where as Xn is the current number thus using the current random number it generates a new random number.
Step 2: Diffie–Hellman Key Exchange
Diffie–Hellman key exchange is a method of securely exchanging cryptographic keys over a public channel. Most cryptography algorithms are based on keys. Thus it is very important to exchange keys between the two partitciapants, Diffie–Hellman key exchange is widely used for this purpose.
The math behind it ( With example):-
Alice and Bob publicly agree to use a modulus p = 23 and base g = 5 (which is a primitive root modulo 23).
Alice chooses a secret integer a = 4, then sends Bob A = g^a mod p ,A = 5^4 mod 23 = 4
Bob chooses a secret integer b = 3, then sends Alice B = g^b mod p, B = 5^3 mod 23 = 10
Alice computes s = B^a mod p ,s = 104 mod 23 = 18
Bob computes s = A^b mod p ,s = 43 mod 23 = 18
Alice and Bob now share a secret (the number 18).
Step 3: Mersenne Prime
In mathematics, a Mersenne prime is a prime number that is one less than a power of two.
Prime numbers play a great role in the world of cryptography.
2^1 -1 =1 -----> 1
2^2 -1 =3 -----> 11
2^3 -1 =7 -----> 111
2^4 -1 =15 (not a prime number) -----> 1111
2^5 -1 =31 -----> 11111
2^6 -1 =63 -----> 111111
2^7 -1 = 127 (not a prime number) -----> 11111111
This is one of the algorithms or methods used to find large prime numbers.
it is mostly based on the fact that when a Messene prime is converted to binary it is divisible by few of the previous messene prime numbers. thus can be broken into parts that are itself Messene primes.
11111111 can be broken into the previous messene numbers.
Step 4: Affine Cipher
The affine is a type of monoalphabetic substitution cipher, wherein each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter.
The encryption function for each letter :
E ( x ) = ( a x + b ) mod m ,
The value a must be chosen such that 'a' and 'm' are co-prime
The decryption function for each letter :
D ( x ) = a(inverse) ( x − b ) mod m,
the values of a , a(inverse) and m satisfies the equation :
1 = a a(inverse) mod m.
Plain letter : 'F' , a = 5, b = 8 , m = 26
'F' is the fifth alphabet , thus x = 5.
(5x + 8) mod 26 = 7.
cipher Text = 'H' as it is the 7 th alphabet.
a(inverse) is 21
'H' is the 7 th alphabet., thus y = 7.
21(y − 8) mod 26 = 5.
plain Text = 'F' as it is the 5 th alphabet.
Participated in the
Made with Math Contest