Public Key Cryptography Explained: Asymmetric Encryption

Digital signatures provide authentication and non-repudiation using the signer's private key to create a signature, verifiable by anyone using the signer's public key. Since only the signer possesses their private key, they cannot deny having signed the message. Public Key Infrastructure (PKI) uses Certificate Authorities (CAs) to manage and verify public keys. A CA issues digital certificates binding a public key to an entity's identity, signed with the CA's private key. This system solves the problem of verifying that a public key truly belongs to the claimed owner, preventing impersonation attacks.

Digital signatures solve authentication problems where mutual trust doesn't exist between parties. They must verify the author, authenticate content at signing time, and allow third-party verification. The mechanism involves hashing the message, encrypting the hash with the sender's private key, and the recipient decrypting with the sender's public key. However, digital signatures alone cannot verify that a public key belongs to its claimed owner. This trust problem requires a trusted third party (Certificate Authority) that maintains a directory of public keys and identities. A digital certificate binds a public key to an identity through a CA's digital signature. The PKI architecture uses a hierarchical chain of trust: Root CA (self-signed) issues certificates to intermediate CAs, which issue certificates to end entities. Registration Authorities (RAs) serve as the interface between users and CAs, verifying identities and processing certificate requests. Certificate management includes issuance, revocation, renewal, and distribution.

Digital certificates are electronic documents that verify the ownership of public keys, solving the problem of asymmetric algorithm attacks where attackers can spoof identities. Public Key Infrastructure (PKI) is the framework that maps digital certificates with public keys, stores them in centralized databases, and manages revocation. PKI consists of three components: Certificate Authorities (CAs) as trusted third parties that verify and issue certificates, digital certificates themselves signed with the CA's private key, and applicants who request certificates. The CA's private key signing ensures that any attempt to spoof an identity will be detected, as the certificate will not match the claimed owner.

Digital signatures ensure authenticity, integrity, and non-repudiation through asymmetric cryptography: sender hashes the message, encrypts the hash with their private key, and recipient verifies using the sender's public key. Public Key Infrastructure (PKI) enables secure communication using public/private key pairs through digital certificates (X.509 standard) binding identities to public keys. Certificate Authorities (CAs) issue and sign certificates, while Registration Authorities (RAs) verify identities. Certificate management includes validation levels (Domain, Organization, Extended Validation), revocation mechanisms (CRL lists, OCSP real-time verification), and trust models (hierarchical, cross-certification, peer-to-peer, bridge CA). PKI is essential for HTTPS websites, email encryption, smart cards, and VPNs.

The first challenge of verifying the authenticity of public keys is overcome through Public Key Infrastructure (PKI), which uses a trusted third party called a Certificate Authority (CA). The CA securely manages and attests to the authenticity of public keys. When requested, the CA provides the correct public key for a communicating person after verifying the user's identity through attestation, notarization, or other verification processes.

Asymmetric encryption algorithms are based on mathematical problems that are easy to compute in one direction but hard to reverse. RSA uses integer factorization (factoring large numbers into primes). Elliptic Curve Cryptography uses elliptic curve mathematics. These mathematical foundations provide the security guarantees of asymmetric encryption. The choice of algorithm affects security level, performance, and key size requirements.

In Diffie-Hellman Key Exchange, Alice and Bob publicly agree on two numbers: a large prime number p (the modulus) and a generator g. Alice chooses a private number a and computes A = g^a mod p, sending A to Bob. Bob chooses a private number b and computes B = g^b mod p, sending B to Alice. Both then compute the shared secret: Alice calculates B^a mod p = (g^b)^a mod p = g^(ab) mod p; Bob calculates A^b mod p = (g^a)^b mod p = g^(ab) mod p. While computing A and B is easy, determining a or b from A or B is extremely difficult—the discrete logarithm problem—which forms the basis of the algorithm's security.

RSA is a public-key cryptosystem based on number theory principles. The algorithm involves: (1) Selecting two distinct prime numbers P and Q, (2) Computing n = P × Q (the modulus), (3) Calculating φ(n) = (P-1)(Q-1) (Euler's totient function), which counts integers relatively prime to n, (4) Choosing integers E and D such that E × D ≡ 1 mod φ(n), where E is the public exponent and D is the private exponent. The public key consists of (E, n), while the private key is D. To encrypt a message M, compute C = M^E mod n. To decrypt, compute M = C^D mod n. The security relies on the mathematical difficulty of factoring large composite numbers into their prime components - if n is sufficiently large, an attacker cannot efficiently determine P and Q from n alone, making it impossible to compute φ(n) and thus derive the private key D.

Secure Sockets Layer/Transport Layer Security (SSL/TLS) protocols provide encryption for application-layer communications, most notably HTTPS (HTTP Secure). When accessing websites with HTTPS, the browser and server negotiate a secure connection using public-key cryptography. The server presents its digital certificate containing its public key, issued by a trusted Certificate Authority. The browser verifies this certificate and, if trusted, uses the public key to establish an encrypted session. This same mechanism secures SSH (Secure Shell) for remote login sessions. Public-key cryptography uses mathematically related key pairs: data encrypted with the public key can only be decrypted with the corresponding private key, ensuring confidentiality even if attackers intercept communications.

Public key cryptography uses mathematically related key pairs: public keys anyone can use to encrypt data, private keys only the recipient can use to decrypt. This enables secure communication without pre-sharing secrets. SSL/TLS (used for HTTPS) and SSH (Secure Shell) implement these concepts to secure internet communications. SSH allows secure remote command-line access to computers. Port forwarding extends SSH's security by creating encrypted tunnels for other network traffic, protecting against eavesdropping on public networks. These protocols protect against eavesdropping and man-in-the-middle attacks through encryption and authentication.

Modern internet security relies on public key cryptography, where each user has a public key for encrypting messages and a private key for decryption, enabling secure data transfer without pre-shared secrets; this system, based on complex mathematical algorithms, forms the foundation of SSL/TLS protocols that protect online communications when you see HTTPS in your browser.

HTTPS (HTTP Secure) combines HTTP with TLS/SSL encryption to provide secure web communications. The most common implementation uses public-key cryptography where the server's public key encrypts a symmetric session key that is then used for efficient symmetric encryption during the communication session. This hybrid approach balances security and performance, enabling private communication on websites like professormr.com and youtube.com.

This section covers public key cryptography and SSL/TLS fundamentals. Public key cryptography uses a pair of keys: a public key that can be shared openly and a private key that must be kept secret. The public key is used to encrypt messages, while only the corresponding private key can decrypt them. This allows secure communication without pre-sharing a secret key. In SSL/TLS, the server's public key is sent to the client, who encrypts sensitive data with it, and only the server can decrypt it with its private key. The Diffie-Hellman algorithm allows two parties to establish a shared secret key over an insecure channel by agreeing on public values (a prime number P and a generator G), then each generating a private number and computing a public value. They exchange these public values, and each party can compute the same shared secret by raising the received public value to their own private number. This shared secret can then be used for symmetric encryption. SSL certificates work through a chain of trust where Certificate Authorities (CAs) issue certificates that browsers trust, displaying padlock icons and green address bars for secure sites.

Post-quantum cryptography addresses the threat that quantum computers pose to current cryptographic systems. In 2024, NIST published standards for quantum-safe algorithms including Kyber (ML-KEM, FIPS 203) for key encapsulation and Dilithium (ML-DSA, FIPS 204) for digital signatures. These lattice-based schemes are designed to replace RSA and elliptic curve cryptography, which Shor's algorithm can break. The course covers the mathematical foundations needed to understand these algorithms, including rings of polynomials and modules of polynomial vectors, while focusing on practical implementation rather than detailed security analysis.

NIST has officially announced the first set of post-quantum cryptography (PQC) standards, which are quantum-resistant encryption algorithms designed to protect data against future quantum computer attacks; these standards, including algorithms like CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and SPHINCS+, address the 'harvest now, decrypt later' threat where malicious actors could store encrypted data today and decrypt it once quantum computers become available, representing a critical milestone in building quantum-safe cybersecurity infrastructure.

The US National Institute of Standards and Technology (NIST) is establishing formal standards for new post-quantum cryptographic algorithms. These standards will enable key establishment and digital signatures that are resistant to quantum computing attacks. The standardized algorithms will be permitted for use in US government systems, contractor systems, and applications requiring FIPS certification.

Facing the quantum threat, cryptographers developed post-quantum cryptography. The National Institute of Standards and Technology (NIST) in the United States is leading efforts to develop standards for cryptography resistant to quantum computers. In August 2024, NIST approved a new post-quantum cryptographic standard. However, cryptographers remain less confident about post-quantum security against quantum computers compared to classical security against classical computers. The development of quantum computers increases cybersecurity concerns even if migration to post-quantum cryptography is achieved.

In 2016, the National Institute of Standards and Technology (NIST) launched a competition to find cryptographic algorithms resistant to both classical and quantum computers. Cryptographers worldwide submitted 82 proposals that were rigorously tested. Some were broken, and on July 5, 2022, NIST selected four algorithms to become part of its post-quantum cryptographic standard. These new algorithms are designed to be secure against attacks from both classical and quantum computers.