1
$\begingroup$

I know prime numbers are important for several algorithms and protocols. Are there any algorithms and protocols that don't require primes?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Can we assume you mean asymmetric primitives here? Most block ciphers and hash functions don't require primes. But I guess that most post-quantum asymmetric primitives also don't use primes (for security anyway - the number two is also a prime). $\endgroup$ – Maarten Bodewes Mar 13 '16 at 1:40
  • $\begingroup$ Yes, Maarten, I mean asymmetric primitives as well as symmetric ones. Thanks. $\endgroup$ – RichS Mar 13 '16 at 1:44
  • $\begingroup$ OK, that's a very broad question. Do you mean if they rely on primes for security - i.e. large primes? Any particular reason why you are asking this? $\endgroup$ – Maarten Bodewes Mar 13 '16 at 2:29
  • 1
    $\begingroup$ Yes, very large primes, and I know my question is quite broad. I guess this is equivalent to asking if there are other very hard one-way math functions besides those based on primes. that don't rely on the fact that composites of two large primes are easy to create but hard to factor. And why am I asking? I'm writing a story about a mathematician who finds an easy way to factor some numbers, so people want to switch to other cryptographic algorithms. Being a conscientious writer, I want to get the facts right. Thanks. $\endgroup$ – RichS Mar 13 '16 at 6:34
  • $\begingroup$ Could you integrate the information in this comment into the question? $\endgroup$ – Maarten Bodewes Mar 13 '16 at 11:47
2
$\begingroup$

Yes, very large primes, and I know my question is quite broad. I guess this is equivalent to asking if there are other very hard one-way math functions besides those based on primes. that don't rely on the fact that composites of two large primes are easy to create but hard to factor.

I don't think you should call them one way math functions. If RSA was one way then it wouldn't be possible to create RSA (only) encryption. More information here. RSA relies on a trapdoor function and traveling back without "a stair" is expected to be a hard problem. ECC also relies on primes to be secure, so it would also be affected.

Factoring and the RSA trapdoor function is already threatened by quantum cryptography. So generally you can simply look at post-quantum cryptography. So yes, there are problems that don't rely on primes for their security. Lattice based crypto is one of the most promising theories. Within this problem space a promising algorithm seems to be Ring-LWE. This is an algorithm based on the idea that . You can read a story about lattice based crypto here; as a writer you'll love the way it is written. So with regards to scientific research the impact would probably be minimal. A host of new students should be thought harder to learn primitives, but otherwise we already have replacement algorithms and protocols.

Being able to factor numbers won't affect most common symmetric primitives. So stream ciphers, block ciphers and hash functions would not be affected. Neither would any algorithms build from those such as message authentication codes (MAC), deterministic random bit generators and the like.

So what would be affected? Basically signature schemes used for authentication and non-repudiation. Asymmetric encryption (including hybrid encryption) and key agreement would be affected as well. That means that without RSA and ECC the whole PKI infrastructure would break down until an alternative such as lattice based crypto could be introduced.

So impact on the security landscape would be huge. Smart cards contain keys build on RSA and ECC. In general many quantum resistant algorithms have large memory requirements as well, so it may not be a simple task of replacing cards with new cards. SSL/TLS uses PKI for authentication, so the whole PKI eco-system would have to be renewed. A lot of hardware security modules (HSM's, devices used by e.g. banks and certificate authorities used to keep their keys secure) do not have any asymmetric primitives other than RSA or ECC. Embedded systems would need to be upgraded.

Basically if you currently would introduce an algorithm that would allow us to factor some numbers, the effect would be that the large institutions would try and migrate to other numbers still thought to be secure. There would certainly be a panic and a lot of speculation if those numbers would actually be secure. It would probably take some 3-5 years before we could completely migrate away from our current infrastructure to something that would not rely on prime numbers. The reluctance to move away from SHA-1 should be considered a strong warning about the resistance to change by the security industry.

This is one reason why NIST is already moving away from ECC crypto, even though quantum computing is still in its infancy.


Anyway, enough information to write a story about, although that story would be more a story about mayhem in the security world than a story about some genius coming up with a new algorithm to try and avoid it. That's what I would speculate to happen anyway.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ The story is partially about the cybersecurity mayhem that ensues planet wide when people discover some numbers are vulnerable. Thank you! $\endgroup$ – RichS Mar 15 '16 at 8:11
  • $\begingroup$ @RichS Mind you, it takes a lot of work to create actual mayhem. Security companies would be in trouble. But if I order something from a web shop from my home computer I've got little to worry about. To be a man-in-the-middle you first need to be in the middle. That shouldn't stop a good novel though :) $\endgroup$ – Maarten Bodewes Mar 15 '16 at 18:05
1
$\begingroup$

Shamir secret sharing scheme is one of the examples.

| improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ Nit: Shamir secret sharing is based on a field, which always has a prime characteristic... $\endgroup$ – poncho Apr 17 '16 at 19:49
0
$\begingroup$

Most symmetric encryption algorithms do not rely on primes, take a look at AES as an example, it relies on confusion, diffusion and substitution.

Further data is usually encrypted with symmetric encryption. Asymmetric encryption is mainly used to encrypt symmetric encryption keys. HTTPS (TLS) is an example of this usage.

| improve this answer | | | | |
$\endgroup$
0
$\begingroup$

Bitcoin blockchain cryptography algorithm is based on hash function. Finding next coin/block in block chain is equivalent to finding next payload resulting in hash having sufficient amount of leading zeros (adjusting difficult y is based on adjusting value of amount of zeros)

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ That's interesting to know, but how does that relate to prime number cryptography? Are you saying the BitCoin block chains use prime numbers? $\endgroup$ – RichS Apr 17 '16 at 7:41
  • $\begingroup$ The question I read is "Are there any algorithms and protocols that don't require primes?". IMHO bitcoin blockchain can be considered both: algorithm and protocol, and as I presented, does not require primes, not even use them ;). $\endgroup$ – Grzegorz Wierzowiecki Apr 17 '16 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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