Why are primes important in cryptography

Question

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

User · Answer

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

User · Answer

Most basic and general explanation  cryptography is all about number theory  and all integer numbers  except 0 and 1  are made up of primes  so you deal with primes a lot in number theory   More specifically  some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time  Basically you have a  public key  consisting of a product of two large primes used to encrypt a message  and a  secret key  consisting of those two primes used to decrypt the message  You can make the public key public  and everyone can use it to encrypt messages to you  but only you know the prime factors and can decrypt the messages  Everyone else would have to factor the number  which takes too long to be practical  given the current state of the art of number theory

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

There are some good resources for ramping up on crypto  Here s one    http   research microsoft com en-us groups crypto firstcrypto aspx   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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Most basic and general explanation  cryptography is all about number theory  and all integer numbers  except 0 and 1  are made up of primes  so you deal with primes a lot in number theory   More specifically  some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time  Basically you have a  public key  consisting of a product of two large primes used to encrypt a message  and a  secret key  consisting of those two primes used to decrypt the message  You can make the public key public  and everyone can use it to encrypt messages to you  but only you know the prime factors and can decrypt the messages  Everyone else would have to factor the number  which takes too long to be practical  given the current state of the art of number theory

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

There are some good resources for ramping up on crypto  Here s one    http   research microsoft com en-us groups crypto firstcrypto aspx   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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

There are some good resources for ramping up on crypto  Here s one    http   research microsoft com en-us groups crypto firstcrypto aspx   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

User · Answer

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

User · Answer

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

User · Answer

Most basic and general explanation  cryptography is all about number theory  and all integer numbers  except 0 and 1  are made up of primes  so you deal with primes a lot in number theory   More specifically  some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time  Basically you have a  public key  consisting of a product of two large primes used to encrypt a message  and a  secret key  consisting of those two primes used to decrypt the message  You can make the public key public  and everyone can use it to encrypt messages to you  but only you know the prime factors and can decrypt the messages  Everyone else would have to factor the number  which takes too long to be practical  given the current state of the art of number theory

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Most basic and general explanation  cryptography is all about number theory  and all integer numbers  except 0 and 1  are made up of primes  so you deal with primes a lot in number theory   More specifically  some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time  Basically you have a  public key  consisting of a product of two large primes used to encrypt a message  and a  secret key  consisting of those two primes used to decrypt the message  You can make the public key public  and everyone can use it to encrypt messages to you  but only you know the prime factors and can decrypt the messages  Everyone else would have to factor the number  which takes too long to be practical  given the current state of the art of number theory

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

There are some good resources for ramping up on crypto  Here s one    http   research microsoft com en-us groups crypto firstcrypto aspx   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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

[cryptography] Why are primes important in cryptography?

Examples related to cryptography

Examples related to primes