There is a very basic tool that everyone uses that works with servers and infrastructure. It is ssh, ssh uses both symmetric and public-key cryptography to keep the data safe in transit. In this article, we are going to talk about the math behind public-key cryptography.
Public-key cryptography depends on the prime numbers and large prime numbers. The bigger the prime number more safe is your cryptography. Now let’s see what properties of the prime numbers are used here.
Maths behind public-key cryptography
For modulus calculations, we have used this https://planetcalc.com/8326/
Take two prime numbers
p = 11 q = 17
n = p*q
n = 11*17
n = 187
Now calculate the euler quotient
φ(n) = (p-1) * (q-1)
φ(187) = 10*16
φ(187) = 160
Now assume a number which is coprime with 160. Lets take 23
e = 23
compute d, which is modular multiplicative inverse of e(mod(φ(n))
e^-1 = d(mod(φ(n))
23^-1 = d(mod(φ(187))
23^-1 = d(mod(160)
d = 7
If we solve this we can get of d multiple values of d. We solved it for 7.
Private Key:
n = 187, d = 7
Public Key:
n = 187, e = 23
Now lets encrpt a message with this and then check if everything is working fine.
Lets assume message is m = 20, encrypt it with public key n = 187, e = 23
c(20) = 20^23(mod(187))
c(20) = 113
Now lets decrypt it with private key. n = 187, d = 7
dec(113) = 113^7(mod(187))
dec(113) = 20
20 was out inital message. So we verified here that the decryption and encryption is working fine. Now you must be thinking is very easy to guess the numbers. Exactly, the power of encryption lies in the fact that very large numbers are used. Calculating large prime numbers and then calculating their coprime and then testing them one by one is a huge task. This is what makes it very secure.
This combination can also be used to verify if you have sent the message. To accomplish that you can encrypt the hash of your actual message and then encrypt it with your private key and then send it. The receiver can use your public key to get the hash after decryption and then calculate its own hash of the message. Compare them and verify if they are the same.
m = 20
hash = hash_func(m)
Most basic hash function that you can think of is modulus it self. Lets use that we will use hash with 3. The same will be present with the other user. This is predefined with all the user what hash will be used for signature. Both knows how to hash.
hash = 20%3
hash = 2
Next we create signature with our hash and private key.
signature(20) = 2^7(mod(187))
signature(20) = 128
We pass this and message to other user. m=20, signature = 128
Next the use public key to decrypt the signature to hash and calculate our own hash to compare
d(128) = 128^23(mod(187))
d(128) = 2
Here got the hash from send. Now calculate our own hash.
hash = 20%3
hash = 2
here our hashes are matching thus we can say that the message is same as it is sent. These are the two methods how you can encrypt the message and verify the signature of the message. Generally when two users talk to each other. The main message is encrypted with other user’s public keys and the signature is calculated using or own private keys. The receiving user decrypts the message with their private key and verifies the signature using our public key.
Why primes?
If you multiply two prime numbers, you get a number that has only two factors both of which are prime. Primes are hard to calculate, especially when we have to calculate co-primes
This was a very basic introduction to the maths behind public-key cryptography. You can read more about Massive Mersenne primes. You can also learn how to generate prime numbers using python.
If you like the article please share and subscribe.