Lesson 18

Public-Key Cryptography

VIDEO: Symmetric Key and Public Key Encryption

Public-key cryptography


Public-key cryptography is a class of cryptographic algorithms which requires two separate keys, one of which is secret (or private) and one of which is public. The public key is used to encrypt plaintext or to verify a digital signature; whereas the private key is used to decrypt ciphertext or to create a digital signature. The public key is widely distributed, while the private key is known only to its owner. The keys are related mathematically, but the parameters are chosen so that calculating the private key from the public key is either impossible or very expensive.

Public-key algorithms are based on mathematical problems (one way functions with trapdoor) which currently admit no efficient solution. They are inherent in certain integer factorization, discrete logarithm, and elliptic curve relationships. It is computationally easy for a user to generate their own public and private key-pair and to use it for encryption and decryption. The strength lies in the fact that it is "impossible" (computationally infeasible) for a properly generated private key to be determined from its corresponding public key. Thus the public key may be published without compromising security, whereas the private key must not be revealed to anyone not authorized to read messages or perform digital signatures.


Problems of symmetric key encryption

Symmetric-key algorithms use a single secret key, which must be shared and kept private by both the sender and the receiver, for both encryption and decryption. To use a symmetric encryption scheme, the sender and receiver must securely share a key in advance.


Besides this, the amount of keys that have to be shared is growing exponentially, via the n(n-1)/2 formula, where n is the amount of participants.

Symmetric cryptosystems don’t allow to achieve non-repudiation, a property that requires that the sender of the message is uniquely identified. Since the symmetric key is shared between two parties, there is no way to prevent the sender of information from claiming at a later date that the information was never sent.


Usage of public key cryptography

There are three main uses for public-key cryptography:

  • Public-key encryption, in which a message is encrypted with a recipient's public key. The message cannot be decrypted by anyone who does not possess the matching private key, so only the owner can read it. Encryption is used to ensure confidentiality.

  • Digital signatures, in which a message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key. Digital signatures are used to ensure authentication and non-repudiation.

  • Key exchange, in which both parties communicate over an insecure channel to establish a session key.


Public-key cryptography is a building block for various Internet standards, such as SSL, TLS, PGP and others.

Because symmetric key algorithms are nearly always much less computationally intensive than asymmetric ones, it is common to exchange a key using a key-exchange algorithm, then transmit data using that key and a symmetric key algorithm. PGP and the SSL/TLS family of schemes use this procedure, and are thus called hybrid cryptosystems.


How it works: RSA

RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. It is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem.

The keys for the RSA algorithm are generated the following way:

  1. Choose two random prime numbers p and q.

  2. Compute n = pq. n is used as the modulus for both the public and private keys.

  3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.

  4. Choose an integer e such that e and φ(n) are coprime. e is released as the public key.

  5. Determine d as de−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)). d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and φ(n) must also be kept secret because they can be used to calculate d.

RSA encryption is based on the fact that (me)d = m (mod N), where e – public key, d – private key, m - message. So the general idea is: To encrypt the message raise it to the power e, and to decrypt the ciphertext raise it to the power d.


Properties of information achieved with public key cryptography

Data confidentiality ensures that only authorised users can get access to the information.

Authentication is the process of confirming the identity of a message author.

Data integrity ensures that information is resistant to accidental and deliberate actions. This means that data cannot be modified in an unauthorized or undetected manner.

Non-repudiation ensures that the initiator of a message cannot deny the fact of having sent a transaction.


Key distribution problem

While public key cryptography significantly simplifies key management, there are still some issues existing. The reason for that is that secure key distribution can be done using only these three techniques:

  1. One to one meeting

  2. Usage of the previously distributed key

  3. Usage of a trusted party

Otherwise distributed keys are exposed to so called “man in the middle” attacks.



During this situation, the attacker impersonates the server for the victim, providing its own public key to the victim and vice-versa - impersonating the victim to the server. Therefore the attacker is able to decrypt (and modify) all messages from the victim and the server without any risk of being noticed. Since this attack is able to affect such sensitive applications as internet banking, online payment services etc., protection has to be embedded into the operational system or so. One possible solution is Public key infrastructure (PKI).


Public key infrastructure

A central problem with the use of public-key cryptography is confidence that a particular public key is authentic, that means that it is correct and belongs to the right person and has not been tampered by a malicious third party. The usual approach to this problem is to use a public-key infrastructure, in which one or more third parties – known as certificate authorities – certify ownership of key pairs.

A public key infrastructure is a system for the creation, storage, and distribution of digital certificates which are used to verify that a particular public key belongs to a certain entity. The PKI creates digital certificates which map public keys to entities, securely stores these certificates in a central repository and revokes them if needed.

VIDEO: Introduction to Public-Key Cryptography


comments powered by Disqus

You will get an awesome place to trade your
Bitcoin and more. Click for further information!

Choose your topic

and start the journey