4 ms·

Can anyone explain to me why primes are so important in cryptography? I understand that they are used for factorization, where it is easy to multiply two prime

by mudil 9y ago

Can anyone explain to me why primes are so important in cryptography? I understand that they are used for factorization, where it is easy to multiply two primes and get a number, but it is difficult from a big number to find what two primes were used to get it. So, the question is why not to have a big database of primes, and when we have that big factorized number we try to divide that number by each prime from the database and see if the result is another prime from the database? Wouldn't that work?

Retric 9y ago
These numbers are simply huge, so there are far to many primes to check. But the idea is you find a large random number and see if it's prime, and repeat until you find 2 primes. There are shortcuts but let's assume you simply try to factor them. 2,3,5... up to the square root of the number this is W(Work) checks. Now not every random number is prime so let's assume you do this 1,000times. You did 1000 W work to get two prime numbers. But when you multiply them someone needs to check not W numbers but W * W numbers. Now let's say W = 1,000,000,000. You did 1000 W or 1,000,000,000,000 but to break it would take a million times the effort. Further, anything that makes it take less effort to factor a number, means you can just factor larger numbers to start with. That's the basic idea. However, you just care if something is prime which takes even less effort so it's not 10^6 W, but 10^50 or more W.
yathern 9y ago
I think because once you get into the range of 20-digit prime numbers, there become quite a lot, such that it's infeasible to test all permutations to find the prime factors.
- wickawic 9y ago
  Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bits. So to store all the prime numbers from 1 to x you need about a*b bits, or just 'x'. So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.
  - xyzzyz 9y ago
    Why log_2? It should be natural logarithm.
    - bonzini 9y ago
      It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.
      - xyzzyz 9y ago
        Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.
        jacobolus 9y ago
        The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities https://en.wikipedia.org/wiki/Prime-counting_function#Inequa... x/log x < π(x) < 1.25506x/log x If you want to rewrite that using log2, you get: 1.44270x/log2 x < π(x) < 1.81067x/log2 x I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.
        xyzzyz 9y ago
        You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113. If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.
mixedmath 9y ago
It is standard to take two primes that each have at least 100 digits or so. There are approximately 10^100 / 230 primes of of this size (this is the Prime Number Theorem). There is simply not enough space or time to store or interpret 10^100 numbers.
- dalore 9y ago
  yes but you don't store the number, you store the index to the prime and a function to generate it.
  - mixedmath 9y ago
    The parent asked why we don't just search through all candidate primes. Phrased differently, my response is that there are too many. This remains true if you replace "primes" by "indices" --- there are still too many.
LiveOverflow 9y ago
There is a database for prime factorisation: https://factordb.com/ https://factordb.com/ And like the other people responded, there are just wayyyy to many primes to make that feasible. Though it is a common Challenge in security competitions to find the factors to a public key through factordb. Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor).
- schoen 9y ago
  > Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor). I wrote a puzzle in 2012 to help people understand this issue: http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/
schoen 9y ago
I posted further down in this thread about my puzzle http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/ which is nominally about a particular vulnerability (common factor attacks), but actually if you're interested in this topic, I suggest that you read this piece and try to solve the puzzle, because you will really get a sense of the size of the numbers involved, and what particular kinds of arithmetic operations you have to do when using RSA. I even have a section about estimating the number of prime numbers of a particular size (e.g. 512-bit primes, which are the secrets associated with 1024-bit RSA public keys). As other people have said, the size of the numbers involved will make it impractical to list all of them or crack keys by brute force. My puzzle and the associated discussion might make that a little more concrete for you! (Although tptacek might also want you to know that RSA is obsolescent, and more modern cryptography does not actually use prime factorization, but rather other kinds of arithmetic problems.)
infinity0 9y ago
They are not that important in cryptography. They are important for particular types of cryptography. Cryptography often involves finding algebraic structures that have certain properties, that can be used to implement a particular security property. For example, only someone who knows a particular value, can perform operations on these other values. Many algebraic structures include prime numbers as special members. Other algebraic structures do not. Yet other algebraic structures don't even have "number" as members, but something else. An algebraic structure is roughly, a collection of abstract objects (numbers, vectors over numbers, etc) and operations (add, multiply, etc) that follow a particular set of associated laws. You can make up your own, but throughout the centuries, mathematicians, scientists and engineers, have discovered that certain structures are very useful for various tasks. e.g. groups, rings, fields, etc etc. So, why primes show up so often in cryptography is not due to them specifically being "primes", but due to them having special properties within many common algebraic structures. Other things show up in many parts of mathematics as well, like pi, e, i, etc etc etc. There is nothing particularly special about primes in cryptography in general. For example AES does not directly use prime numbers (apart from the number 2).

by mudil 9y ago

Retric 9y ago

These numbers are simply huge, so there are far to many primes to check. But the idea is you find a large random number and see if it's prime, and repeat until you find 2 primes. There are shortcuts but let's assume you simply try to factor them. 2,3,5... up to the square root of the number this is W(Work) checks. Now not every random number is prime so let's assume you do this 1,000times. You did 1000 W work to get two prime numbers. But when you multiply them someone needs to check not W numbers but W * W numbers. Now let's say W = 1,000,000,000. You did 1000 W or 1,000,000,000,000 but to break it would take a million times the effort. Further, anything that makes it take less effort to factor a number, means you can just factor larger numbers to start with. That's the basic idea. However, you just care if something is prime which takes even less effort so it's not 10^6 W, but 10^50 or more W.

yathern 9y ago

I think because once you get into the range of 20-digit prime numbers, there become quite a lot, such that it's infeasible to test all permutations to find the prime factors.

wickawic 9y ago
Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bits. So to store all the prime numbers from 1 to x you need about a*b bits, or just 'x'. So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.
- xyzzyz 9y ago
  Why log_2? It should be natural logarithm.
  - bonzini 9y ago
    It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.
    - xyzzyz 9y ago
      Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.
      - jacobolus 9y ago
        The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities https://en.wikipedia.org/wiki/Prime-counting_function#Inequa... x/log x < π(x) < 1.25506x/log x If you want to rewrite that using log2, you get: 1.44270x/log2 x < π(x) < 1.81067x/log2 x I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.
        xyzzyz 9y ago
        You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113. If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.

mixedmath 9y ago

It is standard to take two primes that each have at least 100 digits or so. There are approximately 10^100 / 230 primes of of this size (this is the Prime Number Theorem). There is simply not enough space or time to store or interpret 10^100 numbers.

dalore 9y ago
yes but you don't store the number, you store the index to the prime and a function to generate it.
- mixedmath 9y ago
  The parent asked why we don't just search through all candidate primes. Phrased differently, my response is that there are too many. This remains true if you replace "primes" by "indices" --- there are still too many.

LiveOverflow 9y ago

There is a database for prime factorisation: https://factordb.com/ https://factordb.com/ And like the other people responded, there are just wayyyy to many primes to make that feasible. Though it is a common Challenge in security competitions to find the factors to a public key through factordb. Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor).

schoen 9y ago
> Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor). I wrote a puzzle in 2012 to help people understand this issue: http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/

schoen 9y ago

I posted further down in this thread about my puzzle http://www.loyalty.org/~schoen/rsa/ http://www.loyalty.org/~schoen/rsa/ which is nominally about a particular vulnerability (common factor attacks), but actually if you're interested in this topic, I suggest that you read this piece and try to solve the puzzle, because you will really get a sense of the size of the numbers involved, and what particular kinds of arithmetic operations you have to do when using RSA. I even have a section about estimating the number of prime numbers of a particular size (e.g. 512-bit primes, which are the secrets associated with 1024-bit RSA public keys). As other people have said, the size of the numbers involved will make it impractical to list all of them or crack keys by brute force. My puzzle and the associated discussion might make that a little more concrete for you! (Although tptacek might also want you to know that RSA is obsolescent, and more modern cryptography does not actually use prime factorization, but rather other kinds of arithmetic problems.)

infinity0 9y ago

They are not that important in cryptography. They are important for particular types of cryptography. Cryptography often involves finding algebraic structures that have certain properties, that can be used to implement a particular security property. For example, only someone who knows a particular value, can perform operations on these other values. Many algebraic structures include prime numbers as special members. Other algebraic structures do not. Yet other algebraic structures don't even have "number" as members, but something else. An algebraic structure is roughly, a collection of abstract objects (numbers, vectors over numbers, etc) and operations (add, multiply, etc) that follow a particular set of associated laws. You can make up your own, but throughout the centuries, mathematicians, scientists and engineers, have discovered that certain structures are very useful for various tasks. e.g. groups, rings, fields, etc etc. So, why primes show up so often in cryptography is not due to them specifically being "primes", but due to them having special properties within many common algebraic structures. Other things show up in many parts of mathematics as well, like pi, e, i, etc etc etc. There is nothing particularly special about primes in cryptography in general. For example AES does not directly use prime numbers (apart from the number 2).