Sorry, I saw a similar post about prime numbers and didn’t want to hijack the thread. 😀
In: Technology
Computers can multiply prime numbers very quickly. But to do the operation in reverse is extremely difficult.
So if I have a public key that is a factor of two very large primes, it’s very easy and quick to encrypt. But to find out what the two primes are basically impossible.
So the reason they are used, easy to encrypt, impossible to decrypt (unless you know the primes, but calculating the primes is just about impossible.)
It’s not just prime numbers, it’s really, really large prime numbers – about 150 digits in length. If you take two of these really long prime numbers and multiply them together, you get a very, very long number, but the calculation is trivial for a computer. Takes a fraction of a second. But if you give the computer the very, very long number and ask it to compute the prime factors, the computer is going to take a really long time, in some cases thousands of years or longer (with modern, non-quantum computers).
Encryption relies on the complexity of factoring the very very large number. A message is encrypted and is sent along with a public key to a receiver. If the receiver has a private key (made from knowing what the primes that made the very very large number are), then the receiver can decrypt the message. But without the private key, the message is pretty much forever garbled and unreadable.
Prime numbers have special properties involving what are called mathematical fields… it’s basically a number system where only whole numbers are allowed, starting with 0 and only going up to a certain number. Like, in a “modulo 10” field, only the numbers 0 through 9 (a total of 10 numbers) are allowed, and 9 + 1 equals 0.
Well if you use a prime number instead of 10, certain things become true that otherwise couldn’t be relied upon. It’s a fair bit of math, but RSA famously uses 2 prime numbers and the properties of these weird number ranges to make encryption.
Normally “encryption” requires both parties to know the password, but getting that password to an otherwise unknown party is a problem. RSA is special because it was really the first encryption scheme where you had 2 passwords, one for encrypting and one for decrypting, and one password would not be useful for the wrong operation nor would it give away the other password.
Now RSA isn’t the only user of prime numbers, but it’s the most well known, as it’s existed for over 40 years now. RSA made it necessary for computers to be able to find a random prime number in a certain size range fairly quickly in order to build the encryption keys.
this brushs up against a well known unsolved problem of p vs np. i wont get into it but it basically means. if something is easily verified, can it be also easily solved.
an example is this. what is the solution to 3×7. it is 21. it is very easy to find the answer and verify if it is correct.
what if i changed the question to this. what are 2 prime numbers that multiple into 21. the question got suddenly alot harder to solve.
the essence of encryption is based on the second question. numbers that are hard to solve but very easy to verify if the answer is correct. but with numbers that are way way longer.
we basically encrypt our messages with the very large number, and send it to the other person who has the answers. how they can send it is beyond this.
Latest Answers