Deciphering prime numbers and their significance
Deconstructing cryptography into prime numbers
Cryptography is one of the few subjects which never ceases to amaze me . A major reason could be that it is broadly based around number theory and other branches of mathematics that makes it interesting to explore even further.
It is heavily employed in making the cyberspace a better and safe place. A fundamental building block of this subject is the prime number. Wait..what number ?
A prime number is a natural number that has only two factors: 1 and the number itself e.g. 23
But there is more to prime numbers, then just having two factors. They are mysterious even to keep the mathematicians keep scratching their heads ever since Euclid proved that they are endless.
An ongoing project — the Great Internet Mersenne Prime Search — which aims to discover more and more primes of a particularly rare kind, has recently resulted in the discovery of the largest prime number known to date. Stretching to 23,249,425 digits, it is so large that it would easily fill 9,000 book pages. But you may ask why all this hassle?
Enter RSA Algorithm a.k.a. the Taylor Swift of encryption schemes!
One of the most widely used applications of prime numbers in computing is the RSA encryption system. In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman combined some simple, known facts about numbers to create RSA. The system they developed allows for the secure transmission of information — such as credit card numbers and authentication signatures.
The core principle behind this is simple: It is simple to compute the product of two large prime numbers. But factoring a number into two large primes is a tedious task.
“No problem, I have a calculator at my disposal. How hard could be it ?”
A computer can surely multiply two primes even if they are 100 digits long. However, factorizing them back into their components is notoriously difficult, even for supercomputers which will take an absurd amount of time (timescales which are more than the age of this planet).
This is what we call a trapdoor function.
A trapdoor function f with its trapdoor t can be generated by an algorithm Gen. f can be efficiently computed, i.e., in probabilistic polynomial time. However, the computation of the inverse of f is generally hard, unless the trapdoor t is given.
So does this mean, RSA algorithm cannot be broken into ?
In 2009, researchers networked several hundred computers together and spent the equivalent of about 2,000 years for a single computer, using advanced factoring algorithms to factor the “RSA-768” number — that is to say, a number with 232 digits put up by the RSA group as a factoring challenge. Proving it was possible to break 768-bit encryption in non-universal-heat-death timescales is unacceptable for the security world, of course, and so the standard has now moved to RSA-1024, using numbers with 309 digits.
In 2013, the trio of scientists composed by Daniel Genkin, Eran Tromer and co-inventor of famous RSA Shamir have verified that results they first proposed a decade ago are valid, the researchers were able in fact to extract a 4096-bit RSA key from a laptop with an acoustic side-channel attack that enables the recording of noise coming from the device during decryption with using a smartphone placed nearby.
They are able to discover a long RSA key in less than one hour with the method dubbed “acoustic cryptanalysis attack”.
Whether it’s communicating your credit card information to Amazon, logging into your bank, or sending a manually encrypted email to a colleague, we are constantly using computer encryption. And that means we are constantly using prime numbers, and relying on their odd numerical properties for protection of the cyber-age way of life.
By the way, what are the prime factors of 6,436,609? I will not spoil you with the answer, but I will give you a hint: one of its prime factors has three digits.
Thank you for your time. If you like my writing, you can find my previous article here. Do these concepts make sense to you? If you have 12 seconds, I’d love to read your comment below..If this post was helpful, please click the clap 👏button below a few times to show your support!⬇⬇
