Editing Public-key cryptography (section)

=== Algorithms ===
All public key schemes are in theory susceptible to a "[[brute-force attack|brute-force key search attack]]".<ref>{{cite book|last1=Paar|first1=Christof|first2=Jan|last2=Pelzl|first3=Bart|last3=Preneel|url=http://www.crypto-textbook.com|title=Understanding Cryptography: A Textbook for Students and Practitioners|publisher=Springer|year=2010|isbn=978-3-642-04100-6}}</ref> However, such an attack is impractical if the amount of computation needed to succeed – termed the "work factor" by [[Claude Shannon]] – is out of reach of all potential attackers. In many cases, the work factor can be increased by simply choosing a longer key. But other algorithms may inherently have much lower work factors, making resistance to a brute-force attack (e.g., from longer keys) irrelevant. Some special and specific algorithms have been developed to aid in attacking some public key encryption algorithms; both [[RSA (algorithm)|RSA]] and [[ElGamal encryption]] have known attacks that are much faster than the brute-force approach.{{cn|date=June 2024}} None of these are sufficiently improved to be actually practical, however.

Major weaknesses have been found for several formerly promising asymmetric key algorithms. The [[Merkle–Hellman knapsack cryptosystem|"knapsack packing" algorithm]] was found to be insecure after the development of a new attack.<ref>{{Cite journal|last1=Shamir|first1=Adi|date=November 1982|title=A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem|url=https://ieeexplore.ieee.org/document/4568386|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=145–152|doi=10.1109/SFCS.1982.5}}</ref> As with all cryptographic functions, public-key implementations may be vulnerable to [[side-channel attack]]s that exploit information leakage to simplify the search for a secret key. These are often independent of the algorithm being used. Research is underway to both discover, and to protect against, new attacks.