One thing that always strikes me as a non-cryptographer: Why is it so important to use Prime numbers? What makes them so special in cryptography?
Does anyone have a simple short explanation? (I am aware that there are many primers and that Applied Cryptography is the Bible, but as said: I am not looking to implement my own cryptographic algorithm, and the stuff that I found just made my brain explode - no 10 pages of math formulas please :))
Thanks for all the answers. I've accepted the one that made the actual concept most clear to me.
This question is related to
cryptography
primes
It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).
As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.
The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.
It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.
Simple? Yup.
If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.
Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.
Here is a very simple and common example.
The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.
Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.
I think what are important in cryptography are not primes itself, but it is the difficulty of prime factorization problem
Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.
By the way, there is a published paper on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)
One more resource for you. Security Now! episode 30(~30 minute podcast, link is to the transcript) talks about cryptography issues, and explains why primes are important.
Because factorization algorithms speed up considerably with each factor found. Making both private keys prime ensures the first factor found will also be the last. Ideally, both private keys will also be nearly equal in value since only the strength of the weaker key matters.
Simple? Yup.
If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.
Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.
It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).
As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.
The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.
It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.
I think what are important in cryptography are not primes itself, but it is the difficulty of prime factorization problem
Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.
By the way, there is a published paper on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)
I'm not a mathematician or cryptician, so here's an outside observation in layman's terms (no fancy equations, sorry).
This whole thread is filled with explanations about HOW primes are used in cryptography, it's hard to find anyone in this thread explaining in an easy way WHY primes are used ... most likely because everyone takes that knowledge for granted.
Only looking at the problem from the outside can generate a reaction like; but if they use the sums of two primes, why not create a list of all possible sums any two primes can generate?
On this site there's a list of 455,042,511 primes, where the highest primes is 9,987,500,000 (10 digits).
The largest known prime (as of feb 2015) is 2 to the power of 257,885,161 - 1 which is 17,425,170 digits.
This means that there's no point keeping a list of all the known primes and much less all their possible sums. It's easier to take a number and check if it's a prime.
Calculating big primes in itself is a monumental task, so reverse calculating two primes that has been multiplied with each other both cryptographers and mathematicians would say is hard enough ... today.
It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).
As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.
The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.
It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.
Here is a very simple and common example.
The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.
To be a little more concrete about how RSA uses properties of prime numbers, the RSA algorithm depends critically upon Euler's Theorem, which states that for relatively prime numbers "a" and "N", a^e is congruent to 1 modulo N, where e is the Euler's totient function of N.
Where do primes come into that? To compute the Euler's totient function of N efficiently requires knowing the prime factorization of N. In the case of the RSA algorithm, where N = pq for some primes "p" and "q", then e = (p - 1)(q - 1) = N - p - q + 1. But without knowing p and q, computation of e is very difficult.
More abstractly, many crypotgraphic protocols use various trapdoor functions, functions which are easy to compute but difficult to invert. Number theory is a rich source of such trapdoor functions (such as multiplication of large prime numbers), and prime numbers are absolutely central to number theory.
Simple? Yup.
If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.
Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.
Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.
Prime numbers are mainly used in cryptography since it consumes considerable time in determining whether a given number is prime number or not. For the hacker if any algorithm takes lot of time to break the code it becomes useless for them
Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.
I think what are important in cryptography are not primes itself, but it is the difficulty of prime factorization problem
Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.
By the way, there is a published paper on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)
Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.
Prime numbers are mainly used in cryptography since it consumes considerable time in determining whether a given number is prime number or not. For the hacker if any algorithm takes lot of time to break the code it becomes useless for them
Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.
Because factorization algorithms speed up considerably with each factor found. Making both private keys prime ensures the first factor found will also be the last. Ideally, both private keys will also be nearly equal in value since only the strength of the weaker key matters.
One more resource for you. Security Now! episode 30(~30 minute podcast, link is to the transcript) talks about cryptography issues, and explains why primes are important.
Here is a very simple and common example.
The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.
There are some good resources for ramping up on crypto. Here's one:
From that page:
In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.
Bruce Schneier's book Applied Cryptography is another. I highly recommend that book; it's fun reading.
One more resource for you. Security Now! episode 30(~30 minute podcast, link is to the transcript) talks about cryptography issues, and explains why primes are important.
Simple? Yup.
If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.
Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.
Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.
Here is a very simple and common example.
The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.
I would suggest the book A Mathematical Journey In Code. The book has a nice down to earth feel, which is surprising, since it is about cryptography. The book summarizes Sarah Flannery’s journey from learning puzzles as a child to creating the Cayley-Purser (CP) algorithm at the age of 16. It gives an amazingly detailed explanation of one way functions, number theory, and prime numbers and how they relate to cryptography.
What makes this book even more specific to your question is Sarah tried to implement a new public key algorithm using matrix's. It was much faster then using prime numbers but a loop hole was found that could exploit it. It turns out her algorithm was better used as a private encryption mechanism. The book is a great testament to using prime numbers for encryption as it has stood the test of time and the challenges of very smart individuals.
Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.
Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.
It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).
As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.
The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.
It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.
To be a little more concrete about how RSA uses properties of prime numbers, the RSA algorithm depends critically upon Euler's Theorem, which states that for relatively prime numbers "a" and "N", a^e is congruent to 1 modulo N, where e is the Euler's totient function of N.
Where do primes come into that? To compute the Euler's totient function of N efficiently requires knowing the prime factorization of N. In the case of the RSA algorithm, where N = pq for some primes "p" and "q", then e = (p - 1)(q - 1) = N - p - q + 1. But without knowing p and q, computation of e is very difficult.
More abstractly, many crypotgraphic protocols use various trapdoor functions, functions which are easy to compute but difficult to invert. Number theory is a rich source of such trapdoor functions (such as multiplication of large prime numbers), and prime numbers are absolutely central to number theory.
I'm not a mathematician or cryptician, so here's an outside observation in layman's terms (no fancy equations, sorry).
This whole thread is filled with explanations about HOW primes are used in cryptography, it's hard to find anyone in this thread explaining in an easy way WHY primes are used ... most likely because everyone takes that knowledge for granted.
Only looking at the problem from the outside can generate a reaction like; but if they use the sums of two primes, why not create a list of all possible sums any two primes can generate?
On this site there's a list of 455,042,511 primes, where the highest primes is 9,987,500,000 (10 digits).
The largest known prime (as of feb 2015) is 2 to the power of 257,885,161 - 1 which is 17,425,170 digits.
This means that there's no point keeping a list of all the known primes and much less all their possible sums. It's easier to take a number and check if it's a prime.
Calculating big primes in itself is a monumental task, so reverse calculating two primes that has been multiplied with each other both cryptographers and mathematicians would say is hard enough ... today.
There are some good resources for ramping up on crypto. Here's one:
From that page:
In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.
Bruce Schneier's book Applied Cryptography is another. I highly recommend that book; it's fun reading.
To be a little more concrete about how RSA uses properties of prime numbers, the RSA algorithm depends critically upon Euler's Theorem, which states that for relatively prime numbers "a" and "N", a^e is congruent to 1 modulo N, where e is the Euler's totient function of N.
Where do primes come into that? To compute the Euler's totient function of N efficiently requires knowing the prime factorization of N. In the case of the RSA algorithm, where N = pq for some primes "p" and "q", then e = (p - 1)(q - 1) = N - p - q + 1. But without knowing p and q, computation of e is very difficult.
More abstractly, many crypotgraphic protocols use various trapdoor functions, functions which are easy to compute but difficult to invert. Number theory is a rich source of such trapdoor functions (such as multiplication of large prime numbers), and prime numbers are absolutely central to number theory.
I think what are important in cryptography are not primes itself, but it is the difficulty of prime factorization problem
Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.
By the way, there is a published paper on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)
There are some good resources for ramping up on crypto. Here's one:
From that page:
In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.
Bruce Schneier's book Applied Cryptography is another. I highly recommend that book; it's fun reading.
One more resource for you. Security Now! episode 30(~30 minute podcast, link is to the transcript) talks about cryptography issues, and explains why primes are important.
To be a little more concrete about how RSA uses properties of prime numbers, the RSA algorithm depends critically upon Euler's Theorem, which states that for relatively prime numbers "a" and "N", a^e is congruent to 1 modulo N, where e is the Euler's totient function of N.
Where do primes come into that? To compute the Euler's totient function of N efficiently requires knowing the prime factorization of N. In the case of the RSA algorithm, where N = pq for some primes "p" and "q", then e = (p - 1)(q - 1) = N - p - q + 1. But without knowing p and q, computation of e is very difficult.
More abstractly, many crypotgraphic protocols use various trapdoor functions, functions which are easy to compute but difficult to invert. Number theory is a rich source of such trapdoor functions (such as multiplication of large prime numbers), and prime numbers are absolutely central to number theory.
Source: Stackoverflow.com