Prime Numbers and Cybersecurity

A NP Problem

Image for post
Image for post

Prime numbers are whole numbers that can only be divided by themselves or one, and they are used in our every day lives through encryption and cybersecurity.

Multiplying two prime numbers, even if the numbers are very large is “easy” by easy I mean, it can be solved and verified in polynomial time or O(n^k) in complexity theory, which puts this problem in class P. In computational complexity theory, class P contains all decision problems that can be solved and verified in polynomial time, some other known problems in the P class would be finding the greatest common divisor (GCD) and determining if a number is prime or not.

Unlike the example below “41 x 11” , computers use extremely large prime numbers to multiply together.

 41 x 11 = 451

However finding the prime factorization is “hard” by hard we mean there is no known solution in polynomial time or is currently Little-Omega(n^k) in complexity theory, which puts this problem in the NP class. Although it may not seem hard to figure out the two prime numbers that are being multiplied together knowing the product, it is difficult for larger prime numbers because the only known method of finding the two prime factors of a large number is to check all the possibilities one by one which isn’t practical because there are so many prime numbers. For example, a 128 bit public key would be a number between 1 and

340,282,366,920,938,000,000,000,000,000,000,000,000

The work of Legendre, Gauss, Littlewood, Te Riele, Tchebycheff, Sylvester, Hadamard, de la Vallée Poussin, Atle Selberg, Paul Erdös, Hardy, Wright, and von Koch showed that the number of prime numbers between one and n is approximately n / ln(n). Therefore, there are about:

2¹²⁸ / ln( 2¹²⁸ ) =
3,835,341,275,459,350,000,000,000,000,000,000,000

different prime numbers in a 128 bit key. That means that even with enough computing power to check one trillion of these numbers a second, it would take more than 121,617,874,031,562,000 years to check them all. That’s about 10 million times longer than the universe has existed so far.

p x q = 451 , what is the value of p and q given the product 451 ?

In computational complexity theory, NP (nondeterministic polynomial time) class is the set of all problems that can be verified in polynomial time, and yes this set contains the set/class P, although the reverse may or may not be true, which brings us to the million dollar question do all NP problems = P problems.

Finding the prime factorizations of a number may be hard, but once we have the two primes we can easily verify the solution by multiplying them together and seeing if the product equals that number. If you want to read more about P and NP I have a link to my article on this topic below.

The RSA encryption system uses prime numbers to encrypt data. The reason for this is because of how difficult or hard it is to find the prime factorization. This system, which was developed by Ron Rivest, Leonard Adleman, and Adi Shamir, allows for secure transmission of data like credit card numbers online.

In RSA encryption, the prime numbers being multiplied together A.K.A (p and q) are used to create the users public keys. In general the two prime numbers are used to create both the users public and private keys.

p x q = half_of_public_key 

The RSA encryption system use really big prime numbers to form the private and public keys, the reason for this is to make it very difficult and time-consuming to prime-factor your public key — which of course would breach your security. The biggest prime number currently known as of this writing (Aug 2018) is 2^(77,232,917) — 1 which has 23,249,425 digits.

Sending Secret Messages With Primes

Suppose Harry and Ron want to send some secret message over the internet.
They need an encryption system. If they were able to meet in person first, then they could come up with a method to encrypt and decrypt the message such that only they could read the message. Since the communication will be done online, they will first need to communicate the encryption system itself.

However, if Harry chose two really big prime numbers, and then calculates their product and sends this information openly through the internet, then finding out what his two original prime numbers were will be very hard as only he knows those prime factors.

So Harry sends the product of the two prime numbers to Ron, keeping the two prime numbers a secret only he knows. Ron then uses Harry’s product to encrypt his message back to Harry, this message can only be decrypted using the two prime factors that Harry knows. If the eavesdropper Bellatrix is eavesdropping, she can’t decipher Ron’s message unless she has the two prime factors or private keys from Harry. We know she doesn’t, because only Harry has those prime numbers. If Bellatrix uses the fastest supercomputer known today, it is thought that it would take her till the time that the Sun dies to read that secret message.

The Actual Math For RSA Encryption

A. Start with two random large prime numbers (here I will continue to use the small prime numbers 3 and 11). If someone has these two numbers they can calculate both your public and private key.

p = 3 and q = 11

B. Calculate the modulus (this will be used as the modulus in encryption and decryption of the message). Let n = modulus. This number is also half of your public key and half of your private key.

3 x 11 = 33,      n = modulus = 33

C. Calculate the totient. Totient(n) = (p-1) * (q-1). The totient is the other half of your private key.

Totient(33) = (3-1) x (11-1) = 20

D. Choose a number between 1 and n (modulus) as e. If you choose a prime number then all you need to do is check that e isn’t a divisor of n.

e = 17,  1< 17 < n

E. Calculate the modular multiplicative inverse of e * (mod totient(n)). This number will be the other half of your public key. Another way of looking at it is “what is the integer solution for d, given (e * d— 1) mod (totient(n)) = 0. You can use the function below to solve this. Remember our e= 17, and our totient(n) = 20

int solved(int e, int totient){	int i = 1, x, d;	while(true){
x = (e * i - 1) % totient;
if(x == 0){
d = i;
return d;
}
}
i++;
}
d = 13

F. Putting it all together, we have the following:

p=3
q=11
n=33
totient(n) = 20
e = 17
d = 13

Our public key = the pair of numbers( e=17 , n= 33)
Our private key = the pair of numbers(d=13, n=33)

Now that we have calculated our private and public key we can encrypt some data or message.

Let m, be the plain-text message expressed as an integer number.

m = 9

To encrypt with the public key, you take m to the power of e (in the public-key) mod n.

m^e mod n
9^17 mod 33 = 15

Our encrypted value we will call c, is 15.

c = 9^17 mod 33 = 15

This message can be decrypted using the private key. To decrypt this message, take the c to the power of d (the private-key) mod n

c^d mod n
15^13 mod 33 = 9

Now we have our original value/message. This is why people say that breaking RSA just boils down to factoring large numbers. Because if I could factor p* q into p and q, then I could re-derive the private key.

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store