Do any cryptography algorithms work on numbers besides primes? I know prime numbers are important for several algorithms and protocols. Are there any algorithms and protocols that don't require primes?
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.