The Asymmetric schemes are based on a “one-way function f()”:
- Computing y = f(x) is computationally easy.
- Computing x = f-1(y) is computationally infeasible.
One way functions, in fact, are based on mathematically hard problems such as:
- Factoring Integers (e.g. RSA): Given a composite integer n, find its prime factors.
- Discrete Logarithm (e.g. Diffie-Hellman, Elgamal & DSA): Given a, y and m, find x such that ax = y mod m.
- Elliptic Curves or EC (e.g. ECDH & ECDSA): Generalization of discrete logarithm
Remember: The problems are considered mathematically hard, but no proof exists (so far).
Note: There are many other public-key schemes such as, NTRU or systems based on hidden field equations, which are not in wide spread use. Often, their security is not very well understood.
Facts about Asymmetric Algorithms:
- Public-key algorithms have capabilities that symmetric ciphers do not have, in particular digital signature and key establishment functions.
- Public-key algorithms are computationally intensive (a nice way of saying that they are slow), and hence are poorly suited for bulk data encryption.
- Only three families of public-key schemes are widely used. This is considerably fewer than in the case of Symmetric algorithms.