ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

Asymmetric encryption

Asymmetric ciphers are also referred to as ciphers with public and private keys. They use two keys, one for encryption of messages and the other one during decryption.

Definition The system of asymmetric encryption consists of three algorithms (G, E, D):
  • G( ) - the nondeterministic algorithm which returns a pair of keys (pk, sk),
  • E(pk, m) - the nondeterministic algorithm which encrypts plaintext m and returns ciphertext c,
  • D(sk, c) - the deterministic algorithm which decrypts c and returns plaintext m.
All the three algorithms must provide consistency. For each pair of keys (pk, sk) created by G and for every plaintext message m the following condition must be fulfilled:
  • D(sk, E(pk, m)) = m

The public key is widely known and everybody can use it to encrypt any messages. The idea of asymmetric encryption is that only the owner of the second key (the private key, which is not known to anybody else), can decrypt the message. Similarly, data encrypted with the private key can only be decrypted with the corresponding public key.

The intruder can encrypt any messages using the known public key. Asymmetric ciphers are therefore vulnerable to the chosen plaintext attacks. The ciphers with public key encryption must provide security against such attacks. After encrypted two messages using the same public key, the intruder can't be able to distinguish which ciphertext is connected with which plaintext. Also, an observer which analyses two messages encrypted using the same algorithm and the same public key, can not be able to distinguish their ciphertexts.

Asymmetric ciphers are much slower than symmetric ciphers (usually thousand times slower). It is common practice to use public key encryption only to establish the secure connection and negotiate the new secret key, which is then used to protect further communication by using symmetric encryption.

Asymmetric algorithms:

  1. Merkle's puzzles
  2. Diffie–Hellman protocol
  3. RSA