Asymmetric Encryption and Key Exchange Questions

Public key cryptography fundamentals, including how public key systems differ from symmetric key systems and when to use each. Core algorithms and primitives such as Rivest Shamir Adleman and elliptic curve cryptography, and the mathematical hardness assumptions that underpin them including integer factorization and the discrete logarithm problem. Key exchange protocols and constructions such as Diffie Hellman and elliptic curve Diffie Hellman, and how they establish shared secrets for subsequent symmetric encryption. Practical considerations including key generation and secure random number generation, key sizes and security levels, padding and message encoding schemes, certificate and public key infrastructure fundamentals, parameter validation, secure key storage and rotation, common implementation pitfalls, and side channel and implementation attacks. Performance and deployment trade offs, and why modern systems often use hybrid approaches combining asymmetric key exchange with symmetric data encryption.

HardTechnical

81 practiced

Given a hardware module performing ECC scalar multiplication, analyze practical SPA and DPA attack vectors on scalar multiplication. Propose a set of hardware and software defenses including scalar blinding, randomized projective coordinates, window blinding, and threshold implementations, and discuss performance/security trade-offs.

Sample Answer

**Situation / Attack surface (brief)** SPA: power/EM reveals bit patterns from fixed/add/multiply sequences (e.g., double-and-add leaks 0/1 via ADD presence). DPA: statistical correlation across many traces recovers intermediate values (precomputed windows, coordinate operations). Fault-based SPA/DPA amplify leakage if not checked.

**Practical attack vectors** - Simple SPA on non-constant-time ladder or mixed-affine ops. - DPA on projective coordinate multiplications where intermediate x,y/z-dependent products correlate with scalar windows. - Template/EM attacks against table lookups (window methods) and against addition formulas with different power profiles. - Combined fault+DPA to bypass blinding.

**Defenses (hardware + software)**- Scalar blinding: replace k with k' = k + r·ord(P); software picks random r each op. Strong vs DPA; negligible cost (one extra scalar add/mul of randomness), requires secure RNG and protection of r generation.- Randomized projective coordinates: randomize Z or use random isomorphisms per operation to decorrelate intermediate leaked values; cheap in hardware (multiply by random Z) and effective vs DPA/EM.- Window blinding / randomized precomputation: randomize precomputed table order or add random offsets to points; prevents correlation across traces but increases memory and RNG usage.- Use Montgomery/Ladder or fixed-sequence scalar multiplication (e.g., Montgomery ladder, atomic double-and-add) to mitigate SPA. Prefer uniform formulas to avoid branching.- Threshold implementations: split sensitive operations/keys into shares across modules (Boolean/GF arithmetic) to obtain provable resistance to first/second-order DPA in hardware; requires careful fresh randomness and non-completing glitches; significant area and latency overhead.- Hardware countermeasures: add noise shaping, randomized clocking, differential routing, shielding to raise attacker cost; include constant-power PA techniques if feasible.- Fault protection: input validation, coordinate checks, result re-scaling, and redundancy to detect injected faults.

**Trade-offs**- Performance: Montgomery ladder + scalar blinding has moderate slowdown (≈2× vs optimized window) but strong SPA/DPA resistance. Window methods + blinding give best throughput but bigger leakage surface and memory. Threshold adds substantial area, complexity, and latency.- Security: Combining scalar blinding + randomized coordinates + uniform ladder yields high practical resistance to SPA/DPA with modest cost. For high-assurance devices, add threshold implementation and fault checks despite resource cost.- Implementation complexity: threshold and correct masking require expert design; RNG quality and side-channel-safe conditional moves are critical.

**Recommendation**For cryptographic-grade hardware: use secure RNG, apply scalar blinding, randomized projective coordinates, constant-time Montgomery ladder, table blinding if using windows, and implement fault-detection. For highest assurance (smartcards, HSMs) layer a threshold/masked hardware implementation and physical countermeasures; accept throughput/area penalties.

MediumTechnical

71 practiced

Explain the concept of a Key Encapsulation Mechanism (KEM) and how it differs from classic Diffie-Hellman key exchange. Provide examples of where KEMs are used in modern protocols, and discuss benefits such as simplified APIs and easier integration with hybrid encryption patterns.

Sample Answer

**Definition & core idea**- A Key Encapsulation Mechanism (KEM) is a public-key primitive that non‑interactively encapsulates a randomly generated symmetric key to a recipient’s public key, producing (ciphertext, symmetric key) for the sender and ciphertext for the recipient. The recipient decapsulates with their private key to recover the same symmetric key.

**How it differs from classic Diffie‑Hellman**- Diffie‑Hellman (DH) is an interactive key‑agreement: both parties contribute secrets and compute a shared secret (e.g., g^{ab}). DH requires both sides to perform key agreement operations and usually ephemeral keypairs for forward secrecy.- KEM is one‑way and non‑interactive for the sender: the sender generates the symmetric key and encapsulates it to the recipient’s static/ephemeral public key. Internally a KEM may use DH or lattice, code, or RSA techniques, but exposes a simpler encapsulate/decapsulate API rather than a two‑party exponentiation protocol.

**Examples in modern protocols**- HPKE (RFC 9180): canonical composition of KEM + KDF + AEAD for hybrid public‑key encryption.- TLS post‑quantum experiments: hybrid KEM+ECDH proposals (combine classical ECDH with a PQ KEM like Kyber).- RSA‑KEM and ECIES are historical/related constructions; Kyber, SABER are PQ KEMs used in KEM-based integrations.

**Benefits**- Simplified API: encapsulate(publicKey) -> (ct, key); decapsulate(privateKey, ct) -> key. Easier to reason about and implement than custom DH flows.- Easier hybrid encryption: combine a post‑quantum KEM with classical DH by XORing/combining derived keys (KDF) to get robust hybrid keys with minimal protocol changes.- Decouples asymmetric primitive from symmetric key derivation and AEAD, enabling modular security proofs (KEM + KDF + AEAD).- Supports non‑interactive sender-driven workflows (email encryption, KEM-based envelopes) and fits well with KDF-based key schedule semantics.

**Practical notes**- Choose IND‑CCA‑secure KEMs and KDFs; when combining with DH, ensure domain separation and robust hybrid key derivation to avoid downgrade or key‑mixing pitfalls.

HardTechnical

69 practiced

A deployed server uses RSA-CRT for signing and an attacker demonstrates a timing-based information leak. Explain how CRT optimization can create timing/fault-based leakage that reveals p or q, and propose practical mitigations such as RSA blinding, constant-time modular exponentiation, and CRT recombination checks. Provide pseudocode-level changes you would apply.

Sample Answer

**Situation — why CRT leaks p or q**

CRT speeds RSA signing by computing s_p = m^(d_p) mod p and s_q = m^(d_q) mod q then recombining. If an attacker measures timing (or injects faults) that depend on operations modulo p or q (e.g., variable-time Montgomery reductions, branch-dependent multiprecision loops, or a single-fault that corrupts s_p), they can recover p or q by:- Timing: correlate operation timing with bit-length or conditional reductions to infer bits of p or q.- Fault: a single wrong CRT share yields s'; gcd(s - s', N) often reveals p or q.

**Why it happens (concise)**- CRT decomposes into smaller moduli; operations leak more information per operation.- Recombination without verification exposes corrupted shares.

Mitigations (practical, prioritized)1. RSA blinding before exponentiation (randomize message/signature call)2. Constant-time modular exponentiation and arithmetic (avoid data-dependent branches/lengths)3. Verify CRT result; on failure recompute without CRT or abort4. Fault-detection: redundant computation or exponent blinding

Pseudocode-level changes

1) Blinding (per-sign)

python

# Inputs: m, private key (p,q,d_p,d_q,qinv)
r = random(1..N-1)
r_e = r^e mod N        # e is public exponent
m_blinded = (m * r_e) mod N
# compute signature on m_blinded using CRT (or full exp)
s_blinded = rsa_crt_sign(m_blinded)
# unblind
s = (s_blinded * inv_mod(r, N)) mod N

2) Constant-time CRT exponentiation (use fixed-window Montgomery, constant loops)

python

# compute s_p = pow_ct(m, d_p, p)  # constant-time modular exponent
# compute s_q = pow_ct(m, d_q, q)
# pow_ct implements fixed-window, avoids data-dependent branches/time

3) Recombination + verification (detect faults)

python

# recombine
h = ((s_p - s_q) * qinv) mod p
s = s_q + q * h
# verify: check s^e mod N == m
if pow_ct(s, e, N) != m:
    # optional: recompute full exp (no CRT) or abort and log
    s_full = pow_ct(m, d, N)   # single-modulus safe path
    if pow_ct(s_full, e, N) != m:
        raise SecurityError("Signing failed integrity check")
    s = s_full
return s

Notes on implementation- Use side-channel resistant bignum libraries (constant-time limb ops, no secret-dependent memory access).- Blinding prevents timing leakage of exponentiation; verification prevents fault extraction.- Logging and rate-limiting on verification failures reduce fault attack utility.

Complexity/practical trade-offs- Blinding and constant-time ops add ~2x slowdown; recompute-on-fail adds occasional cost but prevents key recovery.- For high-assurance systems prefer full-exponent constant-time signing or hardware roots with fault detection.

This set of changes defends against both timing and single-fault CRT attacks while providing fallbacks for integrity failures.

MediumTechnical

89 practiced

List and explain major side-channel countermeasures for asymmetric cryptography: constant-time algorithms, exponent/blinding, scalar blinding, masking, randomized projective coordinates, and hardware protections. For each mitigation describe the attack types it defends against and the main performance or complexity trade-offs.

Sample Answer

**Overview**Below are major side‑channel mitigations for asymmetric crypto, what attacks they counter, and key trade‑offs — from a cryptographer’s implementation view.

**Constant‑time algorithms**- Defends: Timing and simple cache attacks that exploit data‑dependent branches or memory access.- How: Use fixed‑time branches, avoid secret‑dependent memory indices, use bit‑slicing.- Trade‑offs: Often simpler logic but can reduce performance (loss of short‑circuiting) and complicate code; requires careful compiler/auditing.

**Exponent/blinding**- Defends: Simple/SPA and some timing attacks on modular exponentiation (RSA/DSA).- How: Multiply the base or message by random r^e (or add randomization) so observed operations use randomized inputs.- Trade‑offs: Small cost (extra exponentiation or multiplies); must use secure RNG and protect randomness leakage.

**Scalar blinding**- Defends: SPA and DFA on ECC scalar multiplies (leaking k).- How: Replace scalar k with k + r·n or k XOR r and adjust result.- Trade‑offs: Low overhead; needs care with group order and with interactions with precomputation tables.

**Masking**- Defends: Power analysis (DPA/CPA) by decorrelating instantaneous leakage.- How: Split secret into shares and operate on masked values with masked arithmetic.- Trade‑offs: Significant implementation complexity, higher memory/computation, and needs high‑order masking for strong attacks.

**Randomized projective coordinates**- Defends: SPA, some DPA and fault attacks on EC by randomizing representation (e.g., multiply (X:Y:Z) by r).- How: Use randomizer per operation to change Z-scale so intermediate values differ.- Trade‑offs: Minor overhead; must combine with other countermeasures to counter advanced DPA.

**Hardware protections**- Defends: Many physical channels (power, EM, glitching) via filtering, shielding, secure elements, and side‑channel resistant instruction sets.- How: Dedicated secure hardware, noise injection, constant‑power circuits.- Trade‑offs: Cost, reduced flexibility, possible performance limits; still requires secure algorithms at software layer.

Practical note: combine layered mitigations (constant‑time + blinding + masking + hardware) and validate with profiling, leakage testing, and threat modeling.

MediumTechnical

90 practiced

You observe multiple ECDSA signatures produced by a device and find that two signatures reuse the same nonce 'k'. Explain algebraically how nonce reuse leads to private-key recovery in ECDSA. Provide the formulas showing recovery and recommend immediate mitigation strategies for signing implementations.

Sample Answer

**Brief explanation**

Reusing the same ephemeral nonce k in ECDSA makes the signature linear in the private key and allows algebraic elimination to recover k and then the private key d.

**Algebraic derivation**

ECDSA signature on message with hash h:

text

s = k^{-1} * (h + r * d)  (mod q)

For two signatures (r same because k same) with (s1,h1) and (s2,h2):

text

s1 = k^{-1} * (h1 + r * d)  (mod q)
s2 = k^{-1} * (h2 + r * d)  (mod q)

Subtract to eliminate d:

text

s1 - s2 = k^{-1} * (h1 - h2)  (mod q)

Solve for k:

text

k = (h1 - h2) * (s1 - s2)^{-1}  (mod q)

Recover private key d by plugging k into one signature:

text

d = (s1 * k - h1) * r^{-1}  (mod q)

**Why this works**- k appears linearly; two equations with same k allow solving for k and then for d.- All operations in the prime order q of the base point.

**Immediate mitigations (recommendations)**

- Stop using the faulty RNG immediately; revoke keys if reuse occurred.- Switch to deterministic nonces (RFC 6979) or a vetted CSPRNG with entropy health checks.- Implement per-signature uniqueness checks and logging to detect reused r/k.- Use constant-time crypto implementations and side-channel protections to prevent partial leakage of k.- Rotate and revoke exposed keys; reissue certificates and signatures as needed.- Add unit/integration tests that detect nonce-reuse and RNG failures during CI.

These steps restore nonce uniqueness and reduce risk of private-key compromise.

Unlock Full Question Bank

Get access to hundreds of Asymmetric Encryption and Key Exchange interview questions and detailed answers.

Join thousands of developers preparing for their dream job.