I have learnt a lot about security in the past few years but the use of prime numbers still doesn’t make that much sense to me. I constantly see that asymmetric encryption is based upon the manipulation of two prime numbers and this makes it very difficult to reverse.
My question/s is: What is stopping someone from having a dictionary of prime numbers and brute forcing using all the prime pairs till they generate the key they are trying to break? Also wouldn’t this nullify the whole 2^num of bits security concept as you can eliminate all non primes?
I know my understanding must be wrong, I just haven’t found anything that goes in detail enough to answer these questions.
Just to point you to the right direction (taken from wikipedia):
Primes are used in several routines in information technology, such as public-key cryptography, which makes use of properties such as the difficulty of factoring large numbers into their prime factors.
We use primes because they generate a number that only has 2 known factors
13 * 7 = 91
If we didnt use primes then the outcome would give use a weaker number overall because it would have multiple factors
12 * 8 = 96
2,3,4,6,8,12,16,24,32,48 are all factors of 96. All of these numbers can be used to generate the same key pair.
What is stopping you from just building a rainbow table of primes? The fact that the keyspace is too large and that would take a stupid amount of compute power that can be used elsewhere. This reddit post goes into much more detail about the compute needed for aes256
It depends. No one is entirely sure what will happen to the encryption game with quantum computing. RSA will most likely be broken first as prime factoring is something that quantum computers can do very well.
There will definitely be newer encryption that is quantum computing resistant that use a different type of problem as their root.
Some research has been done on this. A basic public/private key size would need to be in the order of 8 terabits to hopefully make factoring impractical.
Crazy computer scientists are coming up with post quantum encryption schemes though. Source which is a podcast because I am not that kind of crazy.
ok, so most people think (and they are right) enterprise level pub/private keys are created with prime numbers that are still unknown.
Someone with proper resources (without quantum processor at all) can estimate where prime numbers are, and use it to sieve through possible points where prime number should be. (most of certs are using already known prime numbers though, https://primes.utm.edu/primes/) use a database and brute force it with pre-hashed rainbow tables. Again that someone with resources of very small datacenter (lets say 5-10 servers) can make it quite quick.
most of the software is already created, even one to predict where primes will be located at using sierpinski formula.
(and finding prime numbers isn’t that hard anymore anyway, i myself have found 2 prime numbers, running sophie germain formula and LLR)
Also most of pseudo crackers forget that it would be easier to run statistical/differential power analysis attacks - pick your pick and you’ll find there’s less power required to crack it. Who in the right mind brute force through (2 quintillion) options. That reddit post, is taking a sheep running bruteforce - and not using its head.
So from what I gather an organisation of a decent size could guesstimate the rough range the two primes used would be in and could potentially have enough computing power to break some asymmetric encryption that are seen as completely secure? Enabling things like corporate espionage among top tier companies. Or would that range still contain too many primes?
Sorry for my ignorance on the amount of prime numbers I have no idea how many there are. I just assumed that they would be drastically less frequent as numbers get larger but it does not seem to be as fast as I expected.
No, paradoxically there are heaps of prime numbers, and they don’t seem to be less frequent as numbers get bigger. The numberphile channel on youtube covers them a fair bit.
So you are suggesting someone could dead list all primes in a bit space, and use them as some form of dictionary based attack? Interesting idea, not sure if it would be easier than trying to factor.
I am out of my depth here on crypto, it is the true black magic of computers. But my understanding is, modern algorithms don’t just rely on factoring of primes. There is some other elliptic curve bullshit I don’t understand that complicates things even more.
I can see AES128 being potentially vulnerable… but yeah it might be time to move on from RSA but we need something better then Elliptical Curve Cryptography not only because there are concerns of a kleptographic back door in ECC the problem with ECC is that is particularly vulnerable to shor’s algorithm and from what I read RSA 2048 would need at least a 4096 qubit quantum computer to feasibly be cracked in a good amount of time… where as a 224 bit ECC curve could be cracked with a 1300 qubit quantum system due to shor’s algorithm… There is however one quantum resistant cipher suite and that is the Supersingular isogeny Diffie–Hellman key exchange method but its not been implemented into any major encryption system. I hope AES might be able to take advantage of it when used in OpenVPN in alternative to RSA4096 in a later revision… might be worth the next L1T news for discussion @wendell ?
In 2016, researchers from Microsoft posted software for the SIDH which runs in constant time (thus protecting against timing attacks) and is the most efficient implementation to date. They write: “The size of public keys is only 564 bytes, which is significantly smaller than most of the popular post-quantum key exchange alternatives. Ultimately, the size and speed of our software illustrates the strong potential of SIDH as a post-quantum key exchange candidate and we hope that these results encourage a wider cryptanalytic effort.”
