Fundamentals of Cryptography

Public Key Cryptography

When comparing symmetric key cryptography with public/asymmetric key cryptography two important distinctions occur. Symmetric, while very quick to perform, has the inherent problem of key exchange. Both parties are expected to know the same key, and symmetric key does not provide a means to securely exchange the key. Asymmetric on the other hand, is very computationally expensive to perform, but does not share the problem of key exchange, as no secret keys are shared.

Asymmetric key cryptography is based on the following four rules.

  1. Every entity has a private key that is kept private.
  2. Every entity has a public key that is made public.
  3. The private key and public key are mathematically related.
  4. It is infeasible to derive one key, knowing the other.

The private key is not actually a single number, but several numbers that are the result of a complex calculation using random prime numbers. This key, by its very nature, must be kept private. In many cases, this means the key is not permitted to leave the computer on which it was generated. Since a private key is known only by a single entity, the private key represents identity. Key management and in particular key storage plays a vital role in ensuring the security of a private key. Asymmetric encryption is only effective if it can be trusted that a private key is only accessible to the intended owner. In Windows and other operating systems, private keys are stored as part of the users profile, protected by the users password. More secure implementations store the private key on a smartcard or require biometrics to access the key.

The public key is known by everyone. Since you cannot derive the private key from the public key, the public nature of the key is not a security risk. Also since the public key is mathematically related to only one private key, then the two are linked. Operations performed using a public key are bound to only one private key, and operations performed by a private key are bound to only one public key.

The rules of encryption for public key cryptography are as follows.

Epub{data} = Dpvt{data}


Epvt{data} = Dpub{data}

Simply put, data that is encrypted with one key cannot be decrypted with the same key, it must be decrypted with the corresponding key. This leads to a few interesting conclusions.