25
$\begingroup$

Why are primes so important? Why can't we just use a random number? My guess is that it's because finding a random prime require more computing power, than finding a random number. Can anybody confirm this?

$\endgroup$
  • $\begingroup$ primes are already very important in arithmetic, they're a very special set of integers. The Fundamental theorem of arithmetic is about prime factorization (it says this factorization is unique). Now crypto is based a lot on arithmetic. $\endgroup$ – Cédric Van Rompay Dec 19 '14 at 10:48
29
$\begingroup$

Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse. When you have a number which you know is the product of two primes, finding these two prime numbers is very hard. This problem is called prime factorization and finding an algorithm which does it fast is one of the unsolved problems of computer science.

$\endgroup$
  • $\begingroup$ @mwhs It is not true, that calculating $\varphi(n)$ is just related to prime factorization because no other way is known. In fact, both problems are equivalent. That means, if you know a prime factorization for $n$, then you can calculate $\varphi(n)$ (which you already mentioned) and on the other hand, if you know $\varphi(n)$, then you can deduce the prime factors. EDIT: This is just true if you know, that $n$ is the product of two prime numbers. $\endgroup$ – Thekwasti Dec 18 '14 at 14:40
  • $\begingroup$ @mwhs First you should calm down a little bit. Second: Suppose you know $n = pq$ and $\varphi(n) = (p-1)(q-1) = pq-p-q+1$ (while $p$ and $q$ are unknown): Then you can express $q$ as $q = n - \varphi(n) - p + 1$. Throwing this into $n=pq$ yields $n = p*(n-\varphi(n) - p + 1) = -p^2 + (n - \varphi(n) + 1)p$. The last equation is a simple quadratic equation where everything is known but p. You can solve that to get $p$. Done. In this regard calculating $\varphi(n)$ and factorizing $n$ is equal when $n$ has exactly two prime factors (since a solution of either yields a solution of the other). $\endgroup$ – Thekwasti Dec 18 '14 at 15:42
  • $\begingroup$ Two problems are equal, if solving one problem yields a (polynomial time) solution for the other and vice versa. And as I showed above: Under the precondition, that you know that $n=pq$ has exactly two prime factors, you can calculate $\varphi(n)$ from knowing ${n,p,q}$ and vice versa, you can calculate ${p,q}$ from knowing ${n,\varphi(n)}$. This means, if you found a magical way to calculate the private key $\varphi(n)$ for some given public RSA key $n$, then you have implicitly solved the factorization problem for $n$. $\endgroup$ – Thekwasti Dec 18 '14 at 16:06
9
$\begingroup$

What's actually important isn't prime numbers as such, it's numbers that have factors (other than 1 and themselves) but are very difficult to factor. You get such numbers by multiplying together two very large primes. Numbers that are equally large but have more smaller factors are very much easier to factor, and hence are unsuitable for cryptography purposes -- for practical purposes, the difficulty of factoring a number varies with the size of its smallest prime factor, regardless of how big the number is, and so your prime factors need to be as large as possible.

$\endgroup$
  • 1
    $\begingroup$ Well, almost, I think. Multiplying 2, a 1000-digit prime, and another 1000-digit prime, will give a number that is still very difficult to factor. It is very easy, even trivial, to find a factor of it, but not all factors. For some purposes, that may be good enough, and for other purposes, it may not be. $\endgroup$ – hvd Dec 17 '14 at 14:15
  • 1
    $\begingroup$ @hvd When you multiply two primes together, the only factors of the product (becides one and itself) are the two original prime numbers. $\endgroup$ – Matthew Dec 17 '14 at 16:00
  • $\begingroup$ @mathh In my example, after finding one of the factors (2), and dividing by that, you do get a smaller number, but not a significantly smaller number. Finding the other factors is still difficult. This answer claims that the difficulty of factoring a number depends on its smallest prime factor, but I'm attempting (admittedly not very clearly) to show that it depends on the other prime factors very much as well. $\endgroup$ – hvd Dec 17 '14 at 16:34
  • $\begingroup$ @Matthew Yes, I know that already. I don't see the point you're trying to make, could you elaborate? $\endgroup$ – hvd Dec 17 '14 at 16:36
  • $\begingroup$ The statement you made "It is very easy, even trivial, to find a factor of it, but not all factors" seems to be incorrect, or at least misleading. Since there's only two factors, either of which would be difficult to find. $\endgroup$ – Matthew Dec 17 '14 at 16:42
8
$\begingroup$

For many areas of encryption, you actually DO want as truly random of a value as possible. Primes (or more accurately, relative primes) only enter in to the equation when dealing with certain forms of asymmetric encryption.

Asymmetric encryption is where one person has a public key to encrypt a message and then the recipient has a different private key which allows them to decrypt the message. You can't simply use a random number for this type of encryption because there needs to be some relationship between the public key and the private key that is hard to determine the private key from the public key, but yet allows the private key to be related so that it can be used for decryption.

If you don't need that relationship, then random numbers are much, MUCH more secure. This is why for a symmetric algorithm like AES, 256 bit encryption is considered highly secure, however for something like RSA, 2056 or even 4092 bit encryption needs to be used to be considered highly secure.

The relationship between the public and private key makes it less secure, but is also the only way that the asymmetric cryptography can function.

It is also worth noting that relative primes is not the only "hard problem" used in the relationship between the public and private keys. There are alternate hard problems such as elliptic curve cryptography that are not based on prime number factorization.

$\endgroup$
  • 2
    $\begingroup$ Primes are still very much relevant for ECC (and discrete log-based systems in general): you want to operate in a group of prime order in order to escape algorithms like Pohlig-Hellman. This is even more the case for systems based on the discrete log problem in finite fields, since the index calculus algorithm is essentially an integer-factoring one. $\endgroup$ – fkraiem Dec 18 '14 at 4:39
  • $\begingroup$ @fkraiem - ok, maybe I need to learn more about ECC, but if it is still relative prime factoring based, then why is it more resistant to quantum factorization? $\endgroup$ – AJ Henderson Dec 18 '14 at 4:50
  • $\begingroup$ Algorithms like Pohlig-Hellman try to speed up discrete log computations by factoring the order of the group, but if the group has prime order, as is the case in any serious implementation, it can't be factored so those algorithms are totally useless, and you're safe. But the fact that we do need to take a group of prime order shows that primes are relevant, if not in exactly the same way as with RSA. $\endgroup$ – fkraiem Dec 18 '14 at 4:57
  • $\begingroup$ @fkraiem - ok, that kind of makes sense but is a bit mathy for me since it's been 9 years since I last did my graduate level crypto and haven't been using it much since then. If you have an idea how to better rewrite the last paragraph, please feel free to suggest an edit. I'm not confident I'd get the correction right. $\endgroup$ – AJ Henderson Dec 18 '14 at 5:36
3
$\begingroup$

Good question. Most of the above commentators got it mostly correct, but they are each telling one part of the story and not describing other aspects in one post. Here is the more full reasons in one post:

For starters as a general rule understand it is public key cryptography that requires quantitative methods and specifically number theory. This is part of a larger picture with using modulo arithmetic and prime numbers as part of this type of math. Although it is not necessary to have an in depth understanding of specific aspects number theory like groups (Abelian) to work with cryptography it does make public key cryptography easier to understand and use. More on the important details later.If you cannot work with modulo arithmetic that would be my first suggestion to learn.

First for asymmetric cryptography there are two theorems that apply:

1.) Fermat's theorem which states: $m^{p-1} - 1 \bmod p=0$ and can also be seen with this notation: $m^p \equiv m \pmod p$ which means: For any prime $p$ and any positive integer $m$ not divisible by $p$ which all results in getting back the same remainder.

2.) Euler's Totient Function aka phi function: $\varphi(n)$ which is the number of integers less than $n$ and relatively prime to $n$.

Euler's theorem related to the totient (NOT quotient) $m^{\varphi(n)} = 1 \bmod n$. Euler's theorem states that there is at least one value of $p$ satisfies the relation $\varphi(p)$; but there could be more.

In symmetric encryption Diffie Hellman utilizes primes and it plays a role with public key cryptography but this too can seem tricky... there are generally two parts with key exchanges within protocols one part asymmetric and then symmetric key formation/sharing.That is for a different post.

The use of primes for Diffie Hellman is as follows: the whole basis is modulo arithmetic as the earlier example, but it also combines modular exponentiation.

Now yes prime factorization can be important for certain applications within number complexity theory but this is not universal.

I will leave one link and a suggestion on prime numbers:

http://www.mersenne.org/

Taken from Introduction to Algorithms (2009) MIT Press Chapter 11:

Large primes are not so are and they can be found with relative ease, however, they are more secure due to not being able to factor the product of large primes. As others have mentioned the discrete logarithms serve as one example.

I also strongly suggest either Daniel Boneh's or Jonathan Katz's free online Coursera courses in Cryptography.

$\endgroup$
  • $\begingroup$ I will add more later about Diffie Hellman $\endgroup$ – Jacob E Mack Dec 23 '14 at 22:34
1
$\begingroup$

Consider the discrete logarithm problem. If the group order does not contain large prime factor, you can solve the problem for each of small prime factors and "combine" them into the full solution.

So, it can be described that here primes are needed because they can't be divided into smaller things.

$\endgroup$
  • $\begingroup$ Well they can be divided but it is a more complex polynomial time issue that helps reduce the attacks to negligible when certain conditions hold. – $\endgroup$ – Jacob E Mack Dec 25 '14 at 18:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.