Mathematics in Cryptography: Part 1
Cryptography revolves around a lot of Number Theory and Algebra Concepts, starting from the basic to all around complex concepts. This article will cover some super Basic math to kick start your journey in Cryptography! Here we will see the python implementation also, as we are more interested in it!!
In case if you are totally new to cryptography, I will highly suggest you take a look at this article to get a big picture on cryptography: links.dscsastra.com/crypto101
Let’s get started!
1. Modular Arithmetic:
Sometimes we are only interested in the remainder, upon dividing two numbers. Modulo Operator is specifically used in this case. In general, we can visualize it with the 12-hour clock. The general representation is given by, x mod N which is literally asking the remainder of x when it is divided by N. If two numbers say a and b have the same remainder when divided by N, then we say a≡b(mod N). i.e., a and b are concurrent. For example, 52≡24(mod 7) both 52 and 24 are having the same remainder 3 when divided by 7.
Why Modular Arithmetic in Cryptography?
In general Modular Arithmetic has lots of use cases in mathematics and computer science. Here, in cryptography especially in public Key Cryptography, some operations which are crucial for other ops are done by this math. More about this in upcoming articles!
Python Implementation :
# Let's find the value of 31 mod 24 a = 31 % 24 # % = modulo operator
print(a)# a = 7
For further read on Modular Arithmetic, check this out, here.
2. Modulo Multiplicative Inverse:
Assume you have two numbers a and N, then the modulo multiplicative inverse of a under modulo N is an integer x such that ax≡1 (mod N). We have a couple of conditions here,
1. x should be in the range of 1 to m-1.
2. The multiplicative inverse of a and N exists only if both of them are relatively prime. i.e., gcd(a,N) = 1.
Why this math in crypto?
This also has practical application in Public Key Cryptography. For now, remember that we will use this somewhere in the RSA algorithm.
For further read on Modulo Inverse, check this out, here.
Python Implementation:
#Finding modularInverse of 54 and 16#Importing sympy lib import sympy as sp
modularInverse = sp.mod_inverse(54,16)
print(modularInverse)# Output= 11
3. Euclid’s gcd :
Everyone knows about the greatest common divisor(gcd). It is the greatest number (say N) that divides both numbers a and b without leaving a remainder. Numbers a and b are called co-prime when they satisfy gcd(a,b)=1. The below image will give you an exact idea of how this Euclid’s gcd algorithm ( This algorithm assumes a > 0 and b > 0 ) is working.
Why this math in Cryptography?
This math is used in forming various essential algorithms in the field of Cryptography and security protocols. We will encounter this very frequently in most places of Cryptography.
Python Implementation :
def gcd(m,n):
if m<n:
(m,n) = (n,m)
if(m%n) == 0:
return n
else:
return (gcd(n, m % n)) print(gcd(8,12))ORimport sympy as sp
print(sp.gcd(8,12))#output = 4
For further read on Euclid’s GCD, check this out, here.
4. Extended Euclidean Algorithm:
The Extended Euclidean Algorithm follows the same steps as Euclid’s algorithm but with some extra information to be tracked. Explaining the working process is not necessary as of now. But, you can read the complete working principle of this algorithm here.
Why this math in Cryptography?
Extended Euclidean algorithms are widely used in Cryptography, especially in calculating the Modulo Inverse Multiplicative (when integers a and b are co-prime) for deriving the key pairs of RSA public-key encryption.
Python Implementation:
# Python program to demonstrate working of extended
# Euclidean Algorithm
# function for extended Euclidean Algorithm
def gcdExtended(a, b):
# Base Case
if a == 0 :
return b,0,1
gcd,x1,y1 = gcdExtended(b%a, a)
# Update x and y using results of recursive
# call
x = y1 - (b//a) * x1
y = x1
return gcd,x,y# Driver code
a, b = 35,15
g, x, y = gcdExtended(a, b)
print("gcd(", a , "," , b, ") = ", g)#Ouput = 5
#Source Code from GeekForGeeks
That’s it!
Make sure you read all the linked articles for better understanding so that the upcoming articles doesn’t seem odd!!
Don’t worry if the above concepts are unclear as this article’s objective is just to introduce some cool math used in Cryptography. We will see some applications of those in the upcoming articles to clarify all your doubts. And, don’t forget to follow DSC SASTRA Deemed to be University on Medium to read articles on Cryptography and other Tech-ED topics!
P.S: If you like my article, consider following me at Hasher.exe on Medium to read some cool tech articles :)
