Printer-friendly version

Browse the glossary using this index

Special | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | ALL
Picture of Yee Wei Law

Public-key cryptography

by Yee Wei Law - Wednesday, 31 May 2023, 1:11 PM
 

Also known as asymmetric-key cryptography, public-key cryptography (PKC) uses a pair of keys called a public key and a private key for 1️⃣ encryption and decryption, as well as 2️⃣ signing and verification.

Encryption and decryption

For 👩 Alice to send a confidential message to 🧔 Bob,

  • 👩 Alice uses 🧔 Bob’s public key to encrypt her secret plaintext and sends the ciphertext to Bob.
  • 🧔 Bob uses his private key to decrypt the ciphertext.
  • 👩 Alice’s keys are not involved unless someone wants to send confidential messages to Alice.

However,

  • PKC is not usually used for encryption because of the computational cost and the ciphertext length.
  • The more powerful quantum computers become, the longer the keys need to be, the higher the computational costs and the longer the ciphertexts become.
  • Instead, a key establishment protocol is used to establish a symmetric key between two parties and the symmetric key is used for encryption instead.

Signing and verification

For 👩 Alice to assure 🧔 Bob a message really originated from her (i.e., for Bob to authenticate her message),

  • 👩 Alice signs the message with her private key and sends the signed message to 🧔 Bob.
  • 🧔 Bob uses Alice’s public key to verify the signature attached to the message.
  • Successful verification assures 🧔 Bob that the message was signed by 👩 Alice.
  • Simultaneously, 👩 Alice cannot repudiate (see Definition 1) the fact that she signed the message.
Definition 1: Non-repudiation [NIS13]

A service that is used to provide assurance of the integrity and origin of data in such a way that the integrity and origin can be verified and validated by a third party as having originated from a specific entity in possession of the private key (i.e., the signatory).

The ability of PKC to generate and verify signatures gives rise to 📜 digital certificates, an essential feature of PKC.

Digital certificates and public-key infrastructure (PKI)

Suppose 👩 Alice is somebody everybody trusts.

  • When 👩 Alice signs 🧔 Bob’s public key, anybody can verify Bob’s public key using Alice’s public key.
  • Successful verification means we can trust that the public key is Bob’s because we trust Alice.
  • Essentially, 🧔 Bob’s public key with 👩 Alice’s signature on it serves a 📜 digital certificate (see Definition 2) certifying Bob’s identity.
Definition 3: Digital certificate [ENISA]

Also called a public-key certificate, a digital certificate is an electronic data structure that binds an entity (e.g., an institution, a person, a computer program, a web address) to its public key.

Watch a quick introduction to digital certificates on LinkedIn Learning:

Digital certificates and signing from Ethical Hacking: Cryptography by Stephanie Domas

Digital certificates are only useful if we can trust their signatories.

To ensure signatories and hence certificates can be trusted, PKC relies on a public-key infrastructure (PKI, see Definition 3) to work.

Definition 3: Public-key infrastructure (PKI)

In ENISA’s certificate-centric definition, a PKI is a combination of policies, procedures and technology needed to manage digital certificates in a PKC scheme.

In ITU-T’s [ITU19] key-centric definition, a PKI is an infrastructure able to support the management of public keys able to support authentication, encryption, integrity and non-repudiation services.

Watch a quick introduction to PKI from an operational viewpoint on LinkedIn Learning:

Cryptography: Public key infrastructure and certificates from CISA Cert Prep: 5 Information Asset Protection for IS Auditors by Human Element LLC and Michael Lester

A PKI, as specified in the ITU-T X.509 [ITU19] standard, consist of certification authorities (CAs).

  • One or more CAs are trusted to create and digitally sign public-key certificates in response to certificate signing requests (CSRs).

  • A CA may optionally create the subjects’ keys.

  • A CA certificate is a public-key certificate for one CA [ITU19, Sec. 7.4]

    • issued by another CA, in which case the CA certificate is a cross-certificate;

    • issued by the same CA, in which case the CA certificate is a self-issued certificate.

      If the signing key is the private key associated with the public key signed, the self-issued certificate is a self-signed certificate.

  • Thus, CAs can clearly exist in a hierarchy, e.g., the two-tier hierarchy in Fig. 1, or the three-tier hierarchy in Fig. 2.
  • In a hierarchy, the root CA serves as the trust anchor [ITU19, Sec. 7.5].
  • Examples of CAs: IdenTrust, DigiCert Group, others.
  • An example of a software solution that implements CA functionality is Cloudfare’s CFSSL.

Fig. 1: A two-tier hierarchy of CAs [NCS20, p. 6].

In a 2-tier hierarchy, a root CA issues certificates to intermediate CAs, and intermediate CAs issue certificates to end entities.

Intermediate CAs are often organised to issue certificates for certain functions, e.g., a technology use case, VPN, web application.

Alternatively, the CAs can be organised by organisational function, e.g., user / machine / service authentication.

Fig. 2: A three-tier hierarchy of CAs [NCS20, p. 6].

In a 3-tier hierarchy, there is a root CA and two levels of intermediate CAs, in which the lowest layer issues certificates to end entities.

This setup is often used to give an extra layer of separation between the root CA and the intermediate issuing certificates to end entities.

The number of tiers in a CA hierarchy is a balance between the level of separation required and the tolerable administration overheard.

A PKI also has registration authorities (RAs).

  • One or more RAs are responsible for those aspects of a CA’s responsibilities that are related to identification and authentication of the subject of a public-key certificate to be issued by that CA.
  • An RA may either be a separate entity or be an integrated part of the CA.
  • CAs typically play the role of RA as well.
  • An example of a software solution that implements RA functionality is PrimeKey’s EJBCA Registration Authority.

Although the X.509 standard does not specify any validation authority (VA), a VA allows an entity to check that a certificate has not been revoked [NCS20, p. 3].

  • The VA role is often carried out by an online facility hosted by an organisation who operates the PKI.
  • VAs often use the Online Certificate Status Protocol (OCSP, see RFC 6960) or certificate revocation lists (CRLs) to advertise revoked certificates.
  • Fig. 3 illustrates the interactions among an RA, a CA and a VA in a PKI.
  • An example of a software solution that implements VA functionality is PrimeKey’s EJBCA Validation Authority.
Fig. 3: The human representing an organisation registers their public key with an RA, which gets a CA to generate a digital certificate certifying the organisation’s key. The digital certificate enables website users to verify the organisation’s website. For the verification, a user can use a VA. Image from Wikipedia.

Public-key cryptosystems

Algorithmically speaking, there is more than one way of constructing a public-key cryptosystem.

Standard public-key cryptosystems: 1️⃣ Rivest-Shamir-Adleman (RSA) cryptosystem, 2️⃣ elliptic-curve cryptosystems.

These cryptosystems rely on the hardness of certain computational problems for their security.

The hardness of these computational problems has come under threat of quantum computers and quantum algorithms like Shor’s algorithm.

As a countermeasure, NIST has been searching for post-quantum cryptography (PQC, also called quantum-resistant cryptography).

As of writing, there are three PQC candidates.

References

[ITU19] ITU-T, Information technology – Open Systems Interconnection – The Directory: Public-key and attribute certificate frameworks, Recommendation ITU-T X.509 | ISO/IEC 9594-8, October 2019. Available at https://www.itu.int/rec/T-REC-X.509-201910-I/en.
[NCS20] NCSC, Design and build a privately hosted Public Key Infrastructure: Principles for the design and build of in-house Public Key Infrastructure (PKI), National Cyber Security Centre guidance, November 2020. Available at https://www.ncsc.gov.uk/collection/in-house-public-key-infrastructure/introduction-to-public-key-infrastructure/ca-hierarchy.
[NIS13] NIST, Digital Signature Standard (DSS), FIPS PUB 186-4, Information Technology Laboratory, National Institute of Standards and Technology, 2013. https://doi.org/10.6028/NIST.FIPS.186-4.
[SC16] J. J. Stapleton and W. Clay Epstein, Security without Obscurity: A Guide to PKI Operations, CRC Press, 2016. https://doi.org/10.1201/b19725.