RSA Trapdoor Permutations, Elliptic Curve Diffie-Hellman & X.509 PKI Trust Chains

While symmetric cryptography delivers exceptional data encryption throughput, it suffers from a fundamental architectural limitation: the Key Distribution Problem. For two strangers to communicate securely across the global internet, they must somehow establish a shared secret key without an eavesdropper intercepting it. Asymmetric (Public-Key) Cryptography resolves this dilemma through the elegant mathematics of one-way trapdoor functions. By utilizing distinct but mathematically linked public and private keys, asymmetric cryptography enables secure key negotiation via Diffie-Hellman, unforgeable digital signatures, and global identity verification through X.509 Public Key Infrastructure (PKI).

1. Formal Foundations of Asymmetric Public-Key Cryptography#

In 1976, Whitfield Diffie and Martin Hellman published their groundbreaking paper, New Directions in Cryptography, introducing the concept of asymmetric keys.

+----------------------------------------------------------------------------------------------------+
|                                    ASYMMETRIC KEY DUALITY MODEL                                    |
+----------------------------------------------------------------------------------------------------+
  Public Key (e, n or Public Point Q)               Private Key (d or Private Scalar d)
  - Published openly to the global internet.        - Kept strictly secret by the owner.
  - Anyone can ENCRYPT data for the owner.          - ONLY the owner can DECRYPT data.
  - Anyone can VERIFY a signature made by owner.    - ONLY the owner can GENERATE signatures.
  
  The Trapdoor One-Way Function Invariant:
  Given Public Key, computing the Private Key is computationally intractable!
  Inverting the function requires a secret piece of trapdoor knowledge (e.g. prime factors p and q).
+----------------------------------------------------------------------------------------------------+

The Three Foundational Hard Mathematical Problems#

Modern asymmetric cryptography relies on the computational difficulty of three classical number-theoretic problems:

1. Integer Factorization Problem (IFP):

Given two large prime numbers p and q, computing their product n = p · q is trivial (takes microseconds). However, given composite integer n (where n is 2048 to 4096 bits wide), finding the original prime factors p and q is computationally intractable on classical computers (The foundation of RSA).

1. Discrete Logarithm Problem (DLP):

Given a large prime modulus p, a generator g of the multiplicative group (Z/pZ)*, and an integer element A = g^a mod p:

Computing A from g and a is trivial via modular exponentiation.

Finding the private exponent a given g, p, and A is the Discrete Logarithm Problem, which requires super-polynomial time (The foundation of Diffie-Hellman and DSA).

1. Elliptic Curve Discrete Logarithm Problem (ECDLP):

Given an elliptic curve E over a finite field F_p, a base generator point G on the curve, and a public curve point Q = d · G (where d is an integer scalar):

Finding the scalar multiplier d is the ECDLP (The foundation of ECDH, ECDSA, and Ed25519).

Advantage: Unlike integer factorization (which is weakened by sub-exponential algorithms like the General Number Field Sieve), ECDLP has no known sub-exponential classical attack. It provides equivalent security with dramatically smaller key lengths!

+----------------------------------------------------------------------------------------------------+
|                               ASYMMETRIC KEY SIZE EQUIVALENCE SPECTRUM                             |
+----------------------------------------------------------------------------------------------------+
  Security Level (Bits)    Symmetric Cipher    RSA Modulus Size (Bits)    Elliptic Curve Size (Bits)
  --------------------------------------------------------------------------------------------------
  80 bits (Legacy/Broken)  DES / 2TDEA         1024 bits                  160 bits
  112 bits                 3DES                2048 bits                  224 bits
  128 bits (Standard)      AES-128             3072 bits                  256 bits (Curve25519 / P-256)
  192 bits                 AES-192             7680 bits                  384 bits (P-384)
  256 bits (Military-Grade)AES-256             15360 bits                 512 bits (Ed448 / P-521)
+----------------------------------------------------------------------------------------------------+

2. The RSA Cryptosystem (Rivest, Shamir & Adleman, 1977)#

Developed at MIT in 1977, RSA was the first practical public-key cryptosystem capable of both confidential encryption and digital signatures.

+----------------------------------------------------------------------------------------------------+
|                                    RSA KEY GENERATION ALGORITHM                                    |
+----------------------------------------------------------------------------------------------------+
  Step 1: Select two distinct, randomly chosen large prime numbers p and q (e.g. 1024 bits each).
  
  Step 2: Compute the Modulus:
          n = p · q  (Modulus length: 2048 bits). n is published as part of the public key.
          
  Step 3: Compute Euler's Totient Function:
          phi(n) = (p - 1) · (q - 1)
          
  Step 4: Select Public Exponent e:
          Must satisfy: 1 < e < phi(n) and gcd(e, phi(n)) == 1 (Coprime to phi(n)).
          Standard industry constant: e = 65537 (0x10001, Fermat Prime F4).
          
  Step 5: Compute Private Exponent d:
          Solve for d via the Extended Euclidean Algorithm:
          e · d == 1 (mod phi(n)) <===> d = e^(-1) mod phi(n)
          
  Key Distribution:
  - Public Key:  (e, n)
  - Private Key: (d, n) or (p, q, d)
+----------------------------------------------------------------------------------------------------+

Mathematical Mechanics: Encryption and Decryption#

• Encryption:

To encrypt plaintext message integer M (where 0 <= M < n):

C = M^e mod n

• Decryption:

To decrypt ciphertext C:

M = C^d mod n

Mathematical Proof of Correctness (Euler's Totient Theorem)#

Theorem: For any message integer M coprime to n:

C^d mod n = (M^e)^d mod n = M^(e · d) mod n = M mod n

Proof:

By definition of the modular inverse:

e · d == 1 (mod phi(n)) <===> e · d = 1 + k · phi(n) for some integer k.

Therefore:

M^(e · d) = M^(1 + k · phi(n)) = M · (M^phi(n))^k (mod n)

By Euler's Totient Theorem, if gcd(M, n) = 1, then:

M^phi(n) == 1 (mod n)

Substituting:

M · (1)^k == M (mod n).

(Even if gcd(M, n) != 1, meaning M is a multiple of p or q, the Chinese Remainder Theorem confirms the identity holds unconditionally).

Acceleration via the Chinese Remainder Theorem (CRT)#

In production cryptographic libraries (OpenSSL), RSA private key decryption does not compute C^d mod n directly (which is computationally intensive for a 2048-bit modulus). Instead, it uses the Chinese Remainder Theorem (CRT):

• Compute pre-calculated CRT components:

d_p = d mod (p - 1)

d_q = d mod (q - 1)

q_{inv} = q^(-1) mod p

• Decrypt modulo p and modulo q independently:

m_1 = C^(d_p) mod p

m_2 = C^(d_q) mod q

• Combine:

h = q_{inv} · (m_1 - m_2) mod p

M = m_2 + h · q

Because exponentiating modulo 1024-bit primes is dramatically faster than modulo a 2048-bit composite number, CRT accelerates RSA private key operations by a factor of 4!

Why "Textbook RSA" is Insecure: Optimal Asymmetric Encryption Padding (OAEP)#

Evaluating C = M^e mod n directly on raw data ("Textbook RSA") is vulnerable to critical cryptographic attacks:

1. Deterministic Encryption: Encrypting the same plaintext message always yields the identical ciphertext, allowing dictionary matching.
2. Multiplicative Homomorphism:

E(M_1) · E(M_2) mod n = (M_1^e mod n) · (M_2^e mod n) = (M_1 · M_2)^e mod n = E(M_1 · M_2 mod n).

An adversary can multiply ciphertexts to forge valid encrypted messages!

1. Coppersmith's Small Exponent Attacks: If small exponent e = 3 is used and message M is small (M < n^(1/3)), then M^3 < n. The modulus never wraps around, and the plaintext can be extracted by computing the standard integer cube root!

The Production Solution: RSA-OAEP (RFC 8017):

Modern systems mandate Optimal Asymmetric Encryption Padding (OAEP):

• A Feistel network incorporating cryptographic hash functions and random seed strings transforms plaintext before modular exponentiation.
• Guarantees IND-CCA2 Security (Indistinguishability under Adaptive Chosen-Ciphertext Attack), eliminating homomorphic manipulation and dictionary attacks.

3. The Diffie-Hellman Key Exchange & Perfect Forward Secrecy#

The Diffie-Hellman Key Exchange (DH) allows two parties who have never met to negotiate an identical, shared symmetric secret key across a public, unencrypted network monitored by an eavesdropper.

+----------------------------------------------------------------------------------------------------+
|                                    CLASSIC DIFFIE-HELLMAN KEY EXCHANGE                             |
+----------------------------------------------------------------------------------------------------+
  Public Shared Parameters (Agreed openly):
  - Large Prime Modulus p (e.g. 2048 bits)
  - Primitive Generator g of group (Z/pZ)*
  
  Alice                                                              Bob
  --------------------------------------------------------------------------------------------------
  1. Chooses Secret Private Key a                                     1. Chooses Secret Private Key b
     (Random integer: 1 < a < p - 1)                                     (Random integer: 1 < b < p - 1)
     
  2. Computes Public Key A:                                           2. Computes Public Key B:
     A = g^a mod p                                                       B = g^b mod p
     
  3. Sends A to Bob =============== [ Public Network ] =============> Receives A from Alice
     Receives B from Alice <======= [ Public Network ] ============= Sends B to Alice
     
  4. Computes Shared Secret K:                                        4. Computes Shared Secret K:
     K = B^a mod p = (g^b)^a mod p                                       K = A^b mod p = (g^a)^b mod p
  --------------------------------------------------------------------------------------------------
  Result: Both Alice and Bob independently calculate K = g^(ab) mod p!
  An eavesdropper intercepts p, g, A, and B, but CANNOT compute K without solving the Discrete Logarithm!
+----------------------------------------------------------------------------------------------------+

The Man-in-the-Middle (MITM) Flaw of Unauthenticated DH#

Classic Diffie-Hellman provides secrecy against passive eavesdroppers, but provides zero authentication.

If an active adversary (Eve) sits between Alice and Bob:

1. Alice sends public key A. Eve intercepts A, and sends her own public key E_1 to Bob.
2. Bob sends public key B. Eve intercepts B, and sends her own public key E_2 to Alice.
3. Alice negotiates a shared secret with Eve; Bob negotiates an independent shared secret with Eve.
4. Eve decrypts, inspects, and re-encrypts all traffic transparently!

Resolution: Diffie-Hellman public keys must be cryptographically authenticated using Digital Signatures within an X.509 PKI certificate chain.

Ephemeral Diffie-Hellman (DHE) & Perfect Forward Secrecy (PFS)#

In legacy TLS 1.0 and 1.2 handshakes, clients encrypted a premaster secret using the server's static RSA public key.

• The Catastrophe: If an adversary recorded encrypted internet traffic for years and subsequently compromised or subpoenaed the server's private RSA key, they could retroactively decrypt all recorded historical sessions!
• Perfect Forward Secrecy (PFS) mandates Ephemeral Diffie-Hellman (DHE / ECDHE):

- The client and server generate fresh, temporary private keys (a and b) for every individual session.

- The keys are discarded from RAM immediately after the session key is established.

- Even if the server's long-term private signing key is stolen in the future, past recorded sessions remain cryptographically impossible to decrypt. TLS 1.3 completely banned static RSA key exchanges, mandating ephemeral Diffie-Hellman globally.

4. Elliptic Curve Cryptography (ECC) & Modern Edwards Curves#

While RSA relies on prime factorization, Elliptic Curve Cryptography (ECC) (Koblitz & Miller, 1985) leverages the algebraic geometry of elliptic curves over finite prime fields.

+----------------------------------------------------------------------------------------------------+
|                                    ELLIPTIC CURVE POINT ADDITION GEOMETRY                          |
+----------------------------------------------------------------------------------------------------+
  Weierstrass Equation over Finite Field F_p:
  y^2 = x^3 + a·x + b (mod p)   [Where 4a^3 + 27b^2 != 0]
  
             y ^
               |       *  (Curve: y^2 = x^3 - 3x + 3)
               |     *   *
               |    *  P  *
               |---*-------*-------------------- Line intersects curve at third point R!
               |  *         *  Q
               | *           *
  -------------+--------------*------------------> x
               |               *
               |                * -R  (Reflect R across x-axis to find P + Q!)
               |                 *
               |
  Group Law:
  - Point Addition P + Q: Draw line through P and Q; line intersects curve at R. Reflect across x-axis: P + Q = -R.
  - Point Doubling 2P: Draw tangent line to curve at P; intersects curve at R. Reflect: 2P = -R.
  - Point at Infinity (O): Acts as the identity element: P + O = P.
+----------------------------------------------------------------------------------------------------+

Elliptic Curve Diffie-Hellman (ECDH)#

Let E be an elliptic curve with base generator point G having large prime order n:

1. Alice selects private key scalar d_A (random integer). Computes public point: Q_A = d_A · G.
2. Bob selects private key scalar d_B. Computes public point: Q_B = d_B · G.
3. They exchange public points Q_A and Q_B.
4. Alice computes shared curve point: S = d_A · Q_B = d_A · (d_B · G).
5. Bob computes shared curve point: S = d_B · Q_A = d_B · (d_A · G).

Both derive the identical shared curve point S! The x-coordinate of point S is extracted and hashed through a Key Derivation Function (HKDF) to yield the symmetric session key.

Modern Curve25519 (X25519 & Ed25519)#

Standard NIST curves (such as P-256 / secp256r1) have drawn suspicion due to opaque seed generation and vulnerability to software side-channel attacks (branching conditions during point addition allow timing analysis to leak private keys).

In 2006, Daniel J. Bernstein engineered Curve25519:

• Montgomery Form: y^2 = x^3 + 486662·x^2 + x over prime field 2^255 - 19.
• Constant-Time Montgomery Ladder: Point multiplication computes exclusively using the x-coordinate, executing in constant time with zero data-dependent branches or memory lookups, inherently immune to cache-timing attacks.
• Standardized under RFC 7748 (X25519 for key exchange) and RFC 8032 (Ed25519 for digital signatures), Curve25519 is the default asymmetric algorithm in SSH, TLS 1.3, Signal, and WireGuard.

5. Digital Signatures & The Fragility of ECDSA#

A Digital Signature Scheme consists of three algorithms:

1. KeyGen(): Generates public verification key pk and private signing key sk.
2. Sign(sk, M): Computes digital signature sigma over message M.
3. Verify(pk, M, sigma): Outputs valid (1) or invalid (0).

The Elliptic Curve Digital Signature Algorithm (ECDSA)#

Under ECDSA (used in Bitcoin and legacy TLS), signing a message hash e = H(M) using private key d requires generating a Per-Message Ephemeral Nonce k:

1. Compute point (x_1, y_1) = k · G.
2. Calculate signature component: r = x_1 mod n.
3. Calculate signature component: s = k^(-1) · (e + r · d) mod n.

Signature is the pair (r, s).

+----------------------------------------------------------------------------------------------------+
|                               THE SONY PLAYSTATION 3 PRIVATE KEY CATASTROPHE                       |
+----------------------------------------------------------------------------------------------------+
  THE FATAL FLAW: Nonce k MUST be completely random and UNIQUE for every signature!
  
  In 2010, Sony engineers implemented ECDSA code-signing on the PlayStation 3.
  Instead of generating a random k for each signature, Sony's firmware HARDCODED A STATIC CONSTANT k!
  
  The Mathematical Destruction:
  Suppose an attacker intercepts two signatures (r_1, s_1) and (r_2, s_2) generated with the SAME k:
  Since k is identical, r_1 == r_2 == r!
  
  Subtract the two signature equations:
  s_1 - s_2 = k^(-1) · (e_1 - e_2) (mod n)
  
  Solve for the secret nonce k:
  k = (e_1 - e_2) · (s_1 - s_2)^(-1) mod n   <=== Secret nonce k is now REVEALED!
  
  Once k is known, extract Sony's master private key d via elementary algebra:
  d = (s_1 · k - e_1) · r^(-1) mod n         <=== SONY'S MASTER PRIVATE KEY STOLEN!
  
  Result: Attackers extracted Sony's master root key, permanently breaking PS3 security.
+----------------------------------------------------------------------------------------------------+

The Modern Solution: Deterministic Ed25519 (RFC 8032)#

Ed25519 eliminates the dangerous random nonce generator entirely:

• The nonce k is derived deterministically by hashing the private key concatenated with the message:

k = SHA-512(sk_seed || M)

• Impossible to repeat a nonce across different messages.
• Executes signature generation and verification in constant time at extreme speeds (over 70,000 signatures per second per CPU core).

6. X.509 Public Key Infrastructure (PKI) & Trust Chains#

Even with asymmetric signatures, an identity problem persists: if an attacker transmits their public key claiming to be google.com, how does a web browser verify that the public key genuinely belongs to Google?

The Public Key Infrastructure (PKI) establishes cryptographic identity bindings through X.509 Digital Certificates (RFC 5280).

+----------------------------------------------------------------------------------------------------+
|                                    THE X.509 HIERARCHICAL TRUST CHAIN                              |
+----------------------------------------------------------------------------------------------------+
  [ Root Certificate Authority (e.g. DigiCert Global Root CA) ]
  - Self-Signed: Signed by its own Root Private Key.
  - Installed directly in the operating system / browser Root Trust Store!
        |
        | Issues and signs intermediate certificate using Root Private Key
        v
  [ Intermediate CA (e.g. DigiCert SHA2 Extended Validation Server CA) ]
  - Protects the Root CA; Root private key is kept offline in an air-gapped safe.
        |
        | Issues and signs leaf certificate using Intermediate Private Key
        v
  [ End-Entity / Leaf Certificate (e.g. *.devthesis.com) ]
  - Subject: CN = devthesis.com, SAN = api.devthesis.com
  - Public Key: Curve25519 or RSA-2048 public key of devthesis.com
  - Digital Signature: Signed by Intermediate CA's private key.
+----------------------------------------------------------------------------------------------------+

Certificate Anatomy (X.509 v3)#

A standard X.509 certificate contains:

1. Serial Number: Unique identifier assigned by the CA.
2. Subject: Entity whose public key is certified (e.g., Organization, Country, Domain Name).
3. Issuer: The Certificate Authority that verified identity and signed the certificate.
4. Validity Window: Not Before and Not After timestamps.
5. Subject Public Key Info: The algorithm (RSA, ECDSA, Ed25519) and the public key bits.
6. Extensions:

- Subject Alternative Name (SAN): Specifies all valid domains covered by the certificate (*.devthesis.com, devthesis.com). Common Name (CN) is deprecated.

- Basic Constraints: CA:FALSE for leaf certificates; CA:TRUE, pathlen:0 for intermediate CAs (prevents leaf certificates from creating child CAs!).

- Key Usage: Restricts cryptographic operations (e.g., Digital Signature, Key Encipherment).

1. Signature: Cryptographic signature generated over the certificate body using the Issuer's private key.

Certificate Revocation: CRLs vs. OCSP Stapling#

When an enterprise's private key is leaked or compromised, the certificate must be invalidated before its expiration date:

1. Certificate Revocation Lists (CRL): The CA publishes a downloadable file listing revoked serial numbers. Flaw: CRL files grow to hundreds of megabytes, slowing down page loads and consuming client bandwidth.
2. Online Certificate Status Protocol (OCSP, RFC 6960): Client sends real-time HTTP query to CA's OCSP responder: "Is Serial #12345 revoked?"

- Privacy Flaw: The CA learns every website the user visits.

- Latency Flaw: Adds an extra blocking HTTP lookup to every TLS handshake.

1. OCSP Stapling (RFC 6066):

- The web server queries the CA's OCSP responder periodically (e.g., every hour).

- The CA returns a time-stamped, cryptographically signed OCSP proof.

- When a client connects, the web server "staples" the signed OCSP response directly into the TLS handshake.

- Zero client latency, 100% privacy, and instant revocation verification!

7. Industrial Implementation: Production-Grade Asymmetric Cryptosuite#

Below is a self-contained Python program using the cryptography library demonstrating RSA-OAEP key generation, X25519 ephemeral Diffie-Hellman key exchange with HKDF symmetric derivation, and Ed25519 digital signature signing and verification:

from cryptography.hazmat.primitives.asymmetric import rsa, padding, x25519, ed25519
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from typing import Tuple

class AsymmetricCryptoSuite:
    '''
    Production-grade asymmetric cryptography engine supporting RSA-OAEP,
    X25519 Elliptic Curve Diffie-Hellman, and Ed25519 Digital Signatures.
    '''

    @staticmethod
    def generate_rsa_keypair(key_size: int = 2048):
        '''Generates RSA Private Key with standard e=65537.'''
        private_key = rsa.generate_private_key(
            public_exponent=65537,
            key_size=key_size
        )
        return private_key, private_key.public_key()

    @staticmethod
    def rsa_encrypt_oaep(public_key, plaintext: bytes) -> bytes:
        '''Encrypts plaintext using RSA-OAEP with SHA-256 and MGF1.'''
        return public_key.encrypt(
            plaintext,
            padding.OAEP(
                mgf=padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

    @staticmethod
    def rsa_decrypt_oaep(private_key, ciphertext: bytes) -> bytes:
        '''Decrypts ciphertext using RSA-OAEP.'''
        return private_key.decrypt(
            ciphertext,
            padding.OAEP(
                mgf=padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

    @staticmethod
    def ecdh_x25519_exchange(alice_private, bob_public) -> bytes:
        '''
        Executes X25519 Diffie-Hellman exchange and derives a 256-bit symmetric
        AES key via HKDF-SHA256.
        '''
        raw_shared_key = alice_private.exchange(bob_public)
        # Derive cryptographically strong symmetric key via HKDF
        derived_key = HKDF(
            algorithm=hashes.SHA256(),
            length=32,
            salt=None,
            info=b"x25519-handshake-derivation"
        ).derive(raw_shared_key)
        return derived_key

    @staticmethod
    def ed25519_sign(private_key, message: bytes) -> bytes:
        '''Generates deterministic Ed25519 signature.'''
        return private_key.sign(message)

    @staticmethod
    def ed25519_verify(public_key, message: bytes, signature: bytes) -> bool:
        '''Verifies Ed25519 signature. Returns True if valid, False otherwise.'''
        try:
            public_key.verify(signature, message)
            return True
        except Exception:
            return False

# Verification Execution
if __name__ == "__main__":
    suite = AsymmetricCryptoSuite()

    # 1. Test RSA-OAEP Confidential Encryption
    rsa_priv, rsa_pub = suite.generate_rsa_keypair(2048)
    secret_text = b"TOP_SECRET_SESSION_PREMASTER_SECRET_KEY"
    rsa_ciphertext = suite.rsa_encrypt_oaep(rsa_pub, secret_text)
    decrypted_rsa = suite.rsa_decrypt_oaep(rsa_priv, rsa_ciphertext)

    print("RSA-2048 OAEP Encryption/Decryption:")
    print(f"  Ciphertext (Hex): {rsa_ciphertext.hex()[:40]}... (Len: {len(rsa_ciphertext)} B)")
    print(f"  Decrypted Plaintext: {decrypted_rsa.decode('utf-8')}")

    # 2. Test X25519 Elliptic Curve Diffie-Hellman (ECDH)
    alice_priv = x25519.X25519PrivateKey.generate()
    alice_pub = alice_priv.public_key()

    bob_priv = x25519.X25519PrivateKey.generate()
    bob_pub = bob_priv.public_key()

    # Both parties derive the symmetric key independently
    key_alice = suite.ecdh_x25519_exchange(alice_priv, bob_pub)
    key_bob = suite.ecdh_x25519_exchange(bob_priv, alice_pub)

    print("\nX25519 Diffie-Hellman Key Exchange:")
    print(f"  Alice Derived Key (Hex): {key_alice.hex()}")
    print(f"  Bob Derived Key (Hex):   {key_bob.hex()}")
    print(f"  Derived Keys Match:      {key_alice == key_bob}")

    # 3. Test Ed25519 Digital Signature
    ed_priv = ed25519.Ed25519PrivateKey.generate()
    ed_pub = ed_priv.public_key()
    document = b"Contract: Authorize payment of 1 USD,000,000 to DevThesis Ltd."

    signature = suite.ed25519_sign(ed_priv, document)
    is_valid = suite.ed25519_verify(ed_pub, document, signature)
    
    # Tamper test
    tampered_doc = b"Contract: Authorize payment of 9 USD,000,000 to DevThesis Ltd."
    tamper_valid = suite.ed25519_verify(ed_pub, tampered_doc, signature)

    print("\nEd25519 Digital Signature Verification:")
    print(f"  Signature (64 Bytes Hex): {signature.hex()[:40]}...")
    print(f"  Original Document Valid:  {is_valid}")
    print(f"  Tampered Document Valid:  {tamper_valid}")

8. Common Engineering Pitfalls & Anti-Patterns#

Pitfall 1: Disabling SSL/TLS Certificate Verification in Client Code#

In Python, executing requests.get('https://api.internal', verify=False) or in Node.js setting process.env.NODE_TLS_REJECT_UNAUTHORIZED = '0' completely strips X.509 PKI certificate chain validation. Any network intermediary (an attacker on a coffee-shop Wi-Fi network, a rogue proxy) can present a self-signed certificate and intercept all plaintexts.

Remediation: Never disable verification. If using private internal CAs, load the corporate Root CA certificate explicitly into the client's trusted trust store (verify='/etc/ssl/internal_ca.crt').

Pitfall 2: Static RSA Key Exchanges in Modern Systems#

Configuring web servers to use cipher suites prefixed with TLS_RSA_WITH_AES... violates Perfect Forward Secrecy. If the server's private key is leaked years later, all historical traffic captured by state adversaries can be decrypted.

Production Mandate: Enforce TLS 1.3 exclusively or restrict TLS 1.2 to ephemeral Diffie-Hellman cipher suites (ECDHE-ECDSA-AES256-GCM-SHA384 or ECDHE-RSA-AES256-GCM-SHA384).

Pitfall 3: Reusing Nonces in ECDSA#

As proven by the Sony PlayStation 3 catastrophe, generating even two signatures with the same ephemeral nonce k allows instantaneous recovery of the private key via elementary subtraction. If building custom signing systems, always use deterministic nonces via Ed25519 (RFC 8032) or RFC 6979.

9. Comprehensive Checkpoint Practice Problems#

Problem 1: Manual RSA Key Generation, Encryption & Decryption#

Scenario: Demonstrate the complete mathematical execution of the RSA algorithm using small prime numbers:

• Prime p = 61
• Prime q = 53
• Public exponent e = 17

(a) Compute the modulus n and Euler's totient function phi(n).

(b) Compute the private exponent d using the Extended Euclidean Algorithm.

(c) Encrypt the plaintext message integer M = 65 to produce ciphertext C.

(d) Decrypt ciphertext C using private exponent d and verify that the output equals M = 65.

Step-by-Step Solution:

Part (a): Modulus and Totient Calculation:

1. Modulus:

n = p · q = 61 · 53 = 3233.

1. Euler's Totient:

phi(n) = (p - 1) · (q - 1) = (61 - 1) · (53 - 1) = 60 · 52 = 3120.

Part (b): Private Exponent d via Extended Euclidean Algorithm:

We must solve:

e · d == 1 (mod phi(n)) <===> 17 · d == 1 (mod 3120).

Set up Euclidean division algorithm:

• 3120 = 183 · 17 + 9
• 17 = 1 · 9 + 8
• 9 = 1 · 8 + 1 (gcd is 1; coprimality confirmed)

Back-substitute to express 1 as a linear combination of 17 and 3120:

• 1 = 9 - 1 · 8
• 8 = 17 - 1 · 9 ===> 1 = 9 - 1 · (17 - 1 · 9) = 2 · 9 - 1 · 17
• 9 = 3120 - 183 · 17 ===> 1 = 2 · (3120 - 183 · 17) - 1 · 17
• 1 = 2 · 3120 - 366 · 17 - 1 · 17
• 1 = 2 · 3120 - 367 · 17

Taking modulo 3120:

• 367 · 17 == 1 (mod 3120)

d = -367 mod 3120 = 3120 - 367 = 2753.

Verify:

(17 · 2753) = 46,801.

46,801 / 3120 = 15 with remainder: 46,801 - (15 · 3120) = 46,801 - 46,800 = 1. Valid!

Private Exponent d = 2753.

Part (c): Encryption of Message M = 65:

C = M^e mod n = 65^17 mod 3233.

Compute via modular exponentiation (repeated squaring):

• 17 in binary: 16 + 1 = 10001
• 65^1 mod 3233 = 65
• 65^2 mod 3233 = 4225 mod 3233 = 992
• 65^4 mod 3233 = 992^2 mod 3233 = 984,064 mod 3233 = 1374
• 65^8 mod 3233 = 1374^2 mod 3233 = 1,887,876 mod 3233 = 3014
• 65^16 mod 3233 = 3014^2 mod 3233 = 9,084,196 mod 3233 = 992

Multiply components:

C = (65^16 · 65^1) mod 3233 = (992 · 65) mod 3233 = 64,480 mod 3233 = 2790.

Ciphertext C = 2790.

Part (d): Decryption of Ciphertext C = 2790:

M = C^d mod n = 2790^2753 mod 3233.

Using Chinese Remainder Theorem:

1. Modulo p = 61:

d_p = 2753 mod (61 - 1) = 2753 mod 60 = 53.

c_p = 2790 mod 61 = 45.

m_1 = 45^53 mod 61 = 4.

1. Modulo q = 53:

d_q = 2753 mod (53 - 1) = 2753 mod 52 = 49.

c_q = 2790 mod 53 = 34.

m_2 = 34^49 mod 53 = 12.

1. Combine via CRT:

q_{inv} = 53^(-1) mod 61 = 45 (since 53 · 45 = 2385 = 39 · 61 + 6 = 1 mod 61).

h = q_{inv} · (m_1 - m_2) mod p = 45 · (4 - 12) mod 61 = 45 · (-8) mod 61 = -360 mod 61 = 6.

M = m_2 + h · q = 12 + 6 · 53 = 12 + 318 = 65.

Decryption successfully recovers original message M = 65!

Problem 2: Diffie-Hellman Key Negotiation in Group (Z/23Z)*#

Scenario: Alice and Bob negotiate a shared secret over an insecure channel using Diffie-Hellman:

• Agreed Prime Modulus: p = 23
• Agreed Generator: g = 5
• Alice chooses private key: a = 6
• Bob chooses private key: b = 15

(a) Calculate Alice's public key A.

(b) Calculate Bob's public key B.

(c) Demonstrate Alice's calculation of shared secret K.

(d) Demonstrate Bob's calculation of shared secret K and verify that both values are identical.

Step-by-Step Solution:

Part (a): Alice's Public Key A:

A = g^a mod p = 5^6 mod 23.

Compute modular exponentiation:

• 5^1 mod 23 = 5
• 5^2 mod 23 = 25 mod 23 = 2
• 5^4 mod 23 = 2^2 mod 23 = 4
• 5^6 = (5^4 · 5^2) mod 23 = (4 · 2) mod 23 = 8.

Alice's Public Key A = 8.

Part (b): Bob's Public Key B:

B = g^b mod p = 5^15 mod 23.

Compute:

• 5^2 mod 23 = 2
• 5^4 mod 23 = 4
• 5^8 mod 23 = 4^2 mod 23 = 16 == -7 mod 23
• 5^15 = (5^8 · 5^4 · 5^2 · 5^1) mod 23

= (16 · 4 · 2 · 5) mod 23

= (64 mod 23) · (10) mod 23

= (18 · 10) mod 23 = 180 mod 23 = 19 (since 180 = 7 · 23 + 19).

Bob's Public Key B = 19.

Part (c): Alice's Shared Secret Calculation:

Alice receives B = 19, computes:

K = B^a mod p = 19^6 mod 23.

Since 19 == -4 mod 23:

19^6 == (-4)^6 mod 23 = 4^6 mod 23.

• 4^1 mod 23 = 4
• 4^2 mod 23 = 16
• 4^3 mod 23 = 64 mod 23 = 18 == -5 mod 23
• 4^6 mod 23 = (-5)^2 mod 23 = 25 mod 23 = 2.

Alice computes K = 2.

Part (d): Bob's Shared Secret Calculation:

Bob receives A = 8, computes:

K = A^b mod p = 8^15 mod 23.

• 8^1 mod 23 = 8
• 8^2 mod 23 = 64 mod 23 = 18 == -5 mod 23
• 8^4 mod 23 = (-5)^2 mod 23 = 25 mod 23 = 2
• 8^8 mod 23 = 2^2 mod 23 = 4
• 8^15 = (8^8 · 8^4 · 8^2 · 8^1) mod 23

= (4 · 2 · 18 · 8) mod 23

= (8 · 144 mod 23) mod 23

= (8 · 6) mod 23 = 48 mod 23 = 2 (since 48 = 2 · 23 + 2).

Bob computes K = 2.

Both parties independently derive the exact same symmetric key K = 2!

Problem 3: Sony PS3 ECDSA Private Key Recovery Proof#

Scenario: An attacker intercepts two digital signatures generated by a target server using ECDSA over a curve with base order n:

• Signature 1: Message hash e_1, signature (r_1, s_1)
• Signature 2: Message hash e_2, signature (r_2, s_2)

The attacker notices that r_1 = r_2 = r.

(a) Explain what architectural flaw caused r_1 to equal r_2.

(b) Derive the step-by-step algebraic proof that allows the attacker to compute the secret ephemeral nonce k.

(c) Given e_1 = 15, e_2 = 25, s_1 = 9, s_2 = 4, r = 12, and n = 31:

Calculate the exact numerical value of secret nonce k and master private key d.

Step-by-Step Solution:

Part (a): Root Cause:

Under ECDSA:

r = (k · G)_x mod n.

The value r depends exclusively on the ephemeral nonce k and curve generator G.

If r_1 = r_2, the signer used the exact same nonce k for both distinct messages (the Sony PS3 flaw)!

Part (b): Algebraic Derivation of k and d:

The two signature equations are:

1. s_1 == k^(-1) · (e_1 + r · d) (mod n)
2. s_2 == k^(-1) · (e_2 + r · d) (mod n)

Multiply both equations by k:

1. s_1 · k == e_1 + r · d (mod n)
2. s_2 · k == e_2 + r · d (mod n)

Subtract equation 2 from equation 1:

(s_1 - s_2) · k == (e_1 - e_2) (mod n).

Multiply by modular inverse (s_1 - s_2)^(-1):

k == (e_1 - e_2) · (s_1 - s_2)^(-1) (mod n).

Once k is known, substitute into equation 1 to solve for private key d:

s_1 · k - e_1 == r · d (mod n)

d == (s_1 · k - e_1) · r^(-1) (mod n).

Part (c): Numerical Computation:

Given: e_1 = 15, e_2 = 25, s_1 = 9, s_2 = 4, r = 12, n = 31.

Step 1: Compute k:

e_1 - e_2 = 15 - 25 = -10 == 21 (mod 31).

s_1 - s_2 = 9 - 4 = 5.

Find modular inverse of 5 modulo 31:

5 · 25 = 125 = 4 · 31 + 1 == 1 (mod 31).

5^(-1) mod 31 = 25.

k = (21 · 25) mod 31 = 525 mod 31.

525 / 31 = 16 with remainder: 525 - 496 = 29.

Secret Nonce k = 29.

Step 2: Compute Private Key d:

s_1 · k - e_1 = (9 · 29) - 15 = 261 - 15 = 246.

246 mod 31 = 29 (since 246 = 7 · 31 + 29).

Find modular inverse of r = 12 modulo 31:

12 · 13 = 156 = 5 · 31 + 1 == 1 (mod 31).

12^(-1) mod 31 = 13.

d = (29 · 13) mod 31 = 377 mod 31.

377 / 31 = 12 with remainder: 377 - 372 = 5.

Master Private Key d = 5.

Problem 4: X.509 Certificate Chain Path Validation Algorithm#

Scenario: A web browser connects to https://devthesis.com.

The server transmits a certificate chain consisting of:

• Certificate A: Leaf Certificate for devthesis.com (Issuer: "DigiCert Intermediate CA")
• Certificate B: Intermediate CA Certificate (Subject: "DigiCert Intermediate CA", Issuer: "DigiCert Root CA")

The browser has "DigiCert Root CA" pre-installed in its Root Trust Store.

List the complete verification checklist executed by the browser to validate Certificate A before allowing secure communication.

Step-by-Step Solution:

Phase 1: Validating Intermediate Certificate B against Root CA:

1. Trust Anchor Match: Browser locates "DigiCert Root CA" in its pre-installed local root store.
2. Signature Verification: Browser extracts the public key from the trusted Root CA certificate and verifies the digital signature on Certificate B.
3. Validity Window: Checks that the current system time is between Certificate B's Not Before and Not After timestamps.
4. Basic Constraints: Confirms that Certificate B has IsCA = TRUE, permitting it to sign child certificates.

Phase 2: Validating Leaf Certificate A against Intermediate Certificate B:

1. Issuer Matching: Confirms Certificate A's Issuer string exactly matches Certificate B's Subject string.
2. Signature Verification: Extracts the public key from Certificate B and mathematically verifies the digital signature on Certificate A.
3. Validity Window: Checks current time against Certificate A's Not Before and Not After timestamps.
4. Basic Constraints: Confirms Certificate A has IsCA = FALSE (cannot act as a CA).
5. Name Matching (SAN Validation):

- Browser inspects the Subject Alternative Name (SAN) extension of Certificate A.

- Verifies that the requested URL domain (devthesis.com) is explicitly listed as a DNS name entry.

1. Key Usage: Verifies that Certificate A's Key Usage extension permits Digital Signature and Key Encipherment for TLS Server Authentication.
2. Revocation Check:

- Browser inspects the stapled OCSP response (if present) and verifies its digital signature against the CA.

- Confirms status is Good and not Revoked.

Outcome:

All 11 criteria pass. The certificate chain is authenticated, and the browser initiates the TLS symmetric key exchange with confidence.