Facts about Public-Key Algorithm and How to Build It

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:

  1. Factoring Integers (e.g. RSA): Given a composite integer n, find its prime factors.
  2. Discrete Logarithm (e.g. Diffie-Hellman, Elgamal & DSA): Given a, y and m, find x such that ax = y mod m.
  3. 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:

  1. Public-key algorithms have capabilities that symmetric ciphers do not have, in particular digital signature and key establishment functions.
  2. Public-key algorithms are computationally intensive (a nice way of saying that they are slow), and hence are poorly suited for bulk data encryption.
  3. Only three families of public-key schemes are widely used. This is considerably fewer than in the case of Symmetric algorithms.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s