Advanced Public Key Cryptography

Public key cryptography forms the backbone of modern secure communications, enabling secure key exchange, digital signatures, and encryption without requiring a pre-shared secret. This document covers both classical and post-quantum public key cryptography.

Core Concepts

Mathematical Foundations

Security Properties

Classical Public Key Cryptography

RSA Cryptosystem

Elliptic Curve Cryptography (ECC)

Implementation Considerations

Advanced Implementation Examples

Python: ECC with Multiple Curves

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

def generate_ecc_keypair(curve=ec.SECP384R1()):
    """Generate ECC keypair with specified curve."""
    private_key = ec.generate_private_key(curve)
    return private_key, private_key.public_key()

def ecdh_derive_key(private_key, peer_public_key):
    """Derive shared secret using ECDH."""
    shared_key = private_key.exchange(ec.ECDH(), peer_public_key)
    
    # Derive a secure key using HKDF
    derived_key = HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=b'ecdh key derivation',
    ).derive(shared_key)
    
    return derived_key

def encrypt_with_ecc(message, public_key):
    """Encrypt a message using ECIES (Elliptic Curve Integrated Encryption Scheme)."""
    # Generate ephemeral key pair
    ephemeral_private = ec.generate_private_key(public_key.curve)
    ephemeral_public = ephemeral_private.public_key()
    
    # Derive shared secret
    shared_secret = ecdh_derive_key(ephemeral_private, public_key)
    
    # Encrypt with AES-GCM
    nonce = os.urandom(12)
    cipher = AESGCM(shared_secret)
    ciphertext = cipher.encrypt(nonce, message.encode(), None)
    
    # Return ephemeral public key, nonce, and ciphertext
    return {
        'ephemeral_public': ephemeral_public.public_bytes(
            encoding=serialization.Encoding.PEM,
            format=serialization.PublicFormat.SubjectPublicKeyInfo
        ),
        'nonce': nonce,
        'ciphertext': ciphertext
    }

def rsa_decrypt(private_key, ciphertext):
    return private_key.decrypt(
        ciphertext,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    ).decode()

Go: ECDSA Signatures

package main

import (
    "crypto/ecdsa"
    "crypto/elliptic"
    "crypto/rand"
    "crypto/sha256"
    "math/big"
)

func generateKeyPair() (*ecdsa.PrivateKey, error) {
    return ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
}

func signMessage(privKey *ecdsa.PrivateKey, message string) ([]byte, error) {
    hash := sha256.Sum256([]byte(message))
    r, s, err := ecdsa.Sign(rand.Reader, privKey, hash[:])
    if err != nil {
        return nil, err
    }
    
    // Encode r and s as fixed-size big-endian bytes
    const keySize = 32 // For P-256 curve
    sig := make([]byte, keySize*2)
    r.FillBytes(sig[:keySize])
    s.FillBytes(sig[keySize:])
    
    return sig, nil
}

func verifySignature(pubKey *ecdsa.PublicKey, message string, signature []byte) bool {
    const keySize = 32 // For P-256 curve
    if len(signature) != keySize*2 {
        return false
    }
    
    hash := sha256.Sum256([]byte(message))
    r := new(big.Int).SetBytes(signature[:keySize])
    s := new(big.Int).SetBytes(signature[keySize:])
    
    return ecdsa.Verify(pubKey, hash[:], r, s)
}

C: RSA with OpenSSL

#include <openssl/rsa.h>
#include <openssl/pem.h>
#include <openssl/err.h>
#include <openssl/evp.h>

RSA* generate_rsa_keypair(int key_length) {
    RSA *rsa = NULL;
    BIGNUM *bne = NULL;
    int ret = 0;
    
    // Create new RSA key
    rsa = RSA_new();
    if (rsa == NULL) {
        return NULL;
    }
    
    // Create BIGNUM with RSA_F4 (0x10001)
    bne = BN_new();
    if (bne == NULL) {
        RSA_free(rsa);
        return NULL;
    }
    
    if (BN_set_word(bne, RSA_F4) != 1) {
        goto cleanup;
    }
    
    // Generate the RSA key
    if (RSA_generate_key_ex(rsa, key_length, bne, NULL) != 1) {
        rsa = NULL; // Set to NULL to indicate error
        goto cleanup;
    }
    
    ret = 1;
    
cleanup:
    BN_free(bne);
    if (ret != 1) {
        RSA_free(rsa);
        rsa = NULL;
    }
    
    return rsa;
}

int rsa_encrypt(RSA *rsa, const unsigned char *msg, size_t msg_len,
                unsigned char **encrypted, size_t *encrypted_len) {
    int rsa_size = RSA_size(rsa);
    
    // Allocate memory for encrypted data
    *encrypted = (unsigned char *)OPENSSL_malloc(rsa_size);
    if (*encrypted == NULL) {
        return 0;
    }
    
    // Encrypt the data
    *encrypted_len = RSA_public_encrypt(
        (int)msg_len, msg, *encrypted, rsa, RSA_PKCS1_OAEP_PADDING);
    
    if (*encrypted_len == -1) {
        OPENSSL_free(*encrypted);
        *encrypted = NULL;
        return 0;
    }
    
    return 1;
}

void rsa_cleanup(RSA *rsa) {
    if (rsa != NULL) {
        RSA_free(rsa);
    }
}

Rust: Ed25519 Signatures

use ed25519_dalek::{SigningKey, VerifyingKey, Signature, Signer, Verifier};
use rand::rngs::OsRng;
use std::convert::TryInto;

fn generate_keypair() -> (SigningKey, VerifyingKey) {
    let mut csprng = OsRng;
    let signing_key = SigningKey::generate(&mut csprng);
    let verifying_key = signing_key.verifying_key();
    (signing_key, verifying_key)
}

fn sign_message(signing_key: &SigningKey, message: &[u8]) -> Signature {
    signing_key.sign(message)
}

fn verify_signature(verifying_key: &VerifyingKey, message: &[u8], signature: &[u8]) -> bool {
    let sig = match Signature::from_slice(signature) {
        Ok(sig) => sig,
        Err(_) => return false,
    };
    
    verifying_key.verify(message, &sig).is_ok()
}

// Example usage
fn main() {
    // Generate keypair
    let (signing_key, verifying_key) = generate_keypair();
    
    // Sign a message
    let message = b"This is a test message";
    let signature = sign_message(&signing_key, message);
    
    // Verify the signature
    let is_valid = verify_signature(
        &verifying_key,
        message,
        &signature.to_bytes()
    );
    
    println!("Signature is valid: {}", is_valid);
}

Key Management

Public Key Infrastructure (PKI)

Key Storage Best Practices

  1. HSMs: Use Hardware Security Modules for high-security applications
  2. Key Derivation: Use PBKDF2, Argon2, or scrypt for password-based keys
  3. Key Rotation: Regularly rotate keys and update certificates
  4. Key Backup: Securely backup private keys with strong encryption

Security Considerations

Common Attacks

Algorithm Security Level (bits) Key Size
RSA 128 3072
ECC 128 256
Ed25519 128 256
RSA 256 15360
ECC 256 512

Post-Quantum Cryptography

Post-quantum cryptography (PQC) refers to cryptographic algorithms that are thought to be secure against an attack by a quantum computer. These algorithms are being standardized by NIST as part of their Post-Quantum Cryptography Standardization project.

Lattice-based Cryptography

Lattice-based cryptography is based on the hardness of lattice problems, which are believed to be resistant to quantum attacks.

Kyber (Key Encapsulation Mechanism)

# Example using Pycryptodome's PQC implementation
from Crypto.PublicKey import Kyber

# Generate keypair
private_key = Kyber.generate(512)
public_key = private_key.public_key()

# Encapsulate a shared secret
ciphertext, shared_secret = public_key.encrypt()

# Decapsulate the shared secret
decrypted_secret = private_key.decrypt(ciphertext)
assert shared_secret == decrypted_secret

Dilithium (Digital Signature)

package main

import (
    "crypto/rand"
    "fmt"
    "github.com/cloudflare/circl/sign/dilithium"
)

func main() {
    // Select security level (Dilithium2, Dilithium3, or Dilithium5)
    mode := dilithium.Mode3
    
    // Generate keypair
    publicKey, privateKey, _ := mode.GenerateKey(rand.Reader)
    
    // Sign a message
    message := []byte("Sign this message")
    signature := mode.Sign(privateKey, message)
    
    // Verify signature
    if mode.Verify(publicKey, message, signature) {
        fmt.Println("Signature is valid")
    }
}

Hash-based Cryptography

Hash-based signatures are based on the security of cryptographic hash functions.

SPHINCS+

use sphincsplus_rust::{
    keypair, sign, verify,
    params::SphincsPlusParams,
    key::SphincsPublicKey,
};

fn main() {
    // Initialize with recommended parameters
    let params = SphincsPlusParams::sphincssha256256frobust();
    
    // Generate keypair
    let (pk, sk) = keypair(¶ms);
    
    // Sign message
    let message = b"Sign this message with SPHINCS+";
    let signature = sign(¶ms, &sk, message);
    
    // Verify signature
    let is_valid = verify(¶ms, &pk, message, &signature);
    println!("Signature valid: {}", is_valid);
}

Code-based Cryptography

Based on the hardness of decoding random linear codes.

Classic McEliece

Multivariate Cryptography

Based on the difficulty of solving systems of multivariate quadratic equations.

Isogeny-based Cryptography

Based on the difficulty of finding isogenies between elliptic curves.

Migration to Post-Quantum Cryptography

Hybrid Schemes

Combining classical and post-quantum algorithms provides security against both classical and quantum adversaries.

# Hybrid key exchange example (EC + Kyber)
from cryptography.hazmat.primitives.asymmetric import ec
from Crypto.PublicKey import Kyber

def hybrid_key_exchange():
    # Classical ECDH
    private_key_ec = ec.generate_private_key(ec.SECP384R1())
    public_key_ec = private_key_ec.public_key()
    
    # Post-quantum Kyber
    private_key_kyber = Kyber.generate(512)
    public_key_kyber = private_key_kyber.public_key()
    
    # Both parties perform similar operations
    # ...
    
    # Combine both shared secrets
    # shared_secret = KDF(ec_shared_secret | kyber_shared_secret)
    return combined_secret

Implementation Considerations

  1. Performance: PQC algorithms are generally slower and require more memory
  2. Key and signature sizes: Typically larger than classical algorithms
  3. Standardization: Follow NIST PQC standards for algorithm selection
  4. Hybrid approach: Combine with classical cryptography during transition

NIST PQC Standardization Status (as of 2023)

Algorithm Type Status Key Size Signature Size
Kyber KEM Standardized 800 B 768 B
Dilithium Signature Standardized 1.3 KB 2.5 KB
Falcon Signature Standardized 1.3 KB 666 B
SPHINCS+ Signature Standardized 1 KB 17 KB
Classic McEliece KEM Round 4 261 KB N/A

Resources

Quantum Key Distribution (QKD)

While not strictly post-quantum cryptography, QKD provides information-theoretic secure key exchange based on quantum mechanics principles.

BB84 Protocol

# Simplified BB84 QKD simulation
import random

def bb84_protocol(length=256):
    # Alice generates random bits and bases
    alice_bits = [random.randint(0, 1) for _ in range(length)]
    alice_bases = [random.choice(['+', '×']) for _ in range(length)]
    
    # Quantum channel simulation (omitted in this example)
    # Eve could be listening...
    
    # Bob measures in random bases
    bob_bases = [random.choice(['+', '×']) for _ in range(length)]
    bob_bits = []
    
    # Compare bases and keep matching measurements
    sifted_key = []
    for i in range(length):
        if alice_bases[i] == bob_bases[i]:
            sifted_key.append(alice_bits[i])
    
    return sifted_key

Zero-Knowledge Proofs

Zero-knowledge proofs (ZKPs) allow one party (the prover) to prove to another party (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself.

Properties of Zero-Knowledge Proofs

  1. Completeness: If the statement is true, the honest verifier will be convinced by an honest prover.
  2. Soundness: If the statement is false, no cheating prover can convince the honest verifier.
  3. Zero-knowledge: If the statement is true, the verifier learns nothing other than the fact that the statement is true.

Types of Zero-Knowledge Proofs

  1. Interactive ZKPs: Require multiple rounds of communication between prover and verifier.
  2. Non-interactive ZKPs (NIZK): Require only one message from prover to verifier.
  3. zk-SNARKs: Succinct Non-interactive ARguments of Knowledge.
  4. zk-STARKs: Scalable Transparent ARguments of Knowledge.

Example: Schnorr’s Identification Protocol (Interactive ZKP)

# Simplified Schnorr identification protocol
import random
from hashlib import sha256

def schnorr_identification():
    # Public parameters (known to both parties)
    p = 23  # Prime modulus
    g = 5   # Generator
    
    # Prover's secret key
    x = 6   # Private key (normally kept secret)
    y = (g ** x) % p  # Public key
    
    # Prover generates a random value
    k = random.randint(1, p-2)
    r = (g ** k) % p
    
    # Verifier sends a challenge
    c = random.randint(1, 100)
    
    # Prover computes the response
    s = (k - c * x) % (p-1)
    
    # Verifier checks the proof
    lhs = (g ** s) * (y ** c) % p
    rhs = r
    
    return lhs == rhs

zk-SNARK Example using ZoKrates

// Example: Proving knowledge of a hash preimage
// In file `preimage.zok`

def main(private field preimage, field hash) -> bool {
    return sha256(preimage) == hash;
}

// Compile and setup
// $ zokrates compile -i preimage.zok
// $ zokrates setup

// Generate proof
// $ zokrates compute-witness -a <preimage> <hash>
// $ zokrates generate-proof

Applications of Zero-Knowledge Proofs

  1. Privacy-Preserving Transactions: Zcash uses zk-SNARKs for private transactions.
  2. Authentication: Password authentication without revealing the password.
  3. Blockchain Scaling: Rollups use ZKPs to prove transaction validity.
  4. Voting Systems: Verify vote validity without revealing individual votes.
  5. Identity Verification: Prove attributes (e.g., age > 18) without revealing exact age.

Performance Comparison

Operation RSA-3072 ECDSA-256 Ed25519 zk-SNARK (Groth16)
Key Generation 100 ms 1 ms 0.1 ms 10-60 s
Proof Generation N/A N/A N/A 100-500 ms
Verification 0.3 ms 2 ms 1 ms 5-20 ms
Proof Size 384 B 64 B 64 B 128-200 B
Setup Trusted? No No No Yes

zk-STARKs vs zk-SNARKs

Feature zk-SNARKs zk-STARKs
Setup Trusted Yes No
Quantum Resistant No Yes
Proof Size ~200 B ~100 KB
Verification Fast Faster
Proving Time Fast Slower

Further Reading

Best Practices

  1. Always use established libraries: Don’t implement crypto yourself
  2. Keep software updated: Security patches are critical
  3. Use appropriate key sizes: Follow current recommendations
  4. Secure key storage: Protect private keys at rest and in use
  5. Consider post-quantum: Plan for quantum-resistant algorithms

Further Reading