INTRODUCTION: THE SIGNATURE ALGORITHM TRILEMMA

In Lessons 4.1–4.4, we established the transport (mTLS) and the revocation infrastructure. However, the digital signature is the cryptographic linchpin that provides non-repudiation—the mathematical proof that a specific JWT, client assertion, or JARM response was issued by a specific entity and has not been tampered with since issuance.

Open Banking specifications (FAPI 1.0 Advanced, UK OBIE v4.0, Brazil’s FAPI-BR) mandate specific signature algorithms. The industry has traditionally relied on RSA-PSS (PS256) , but newer profiles are adopting ECDSA (ES256) and, increasingly, EdDSA (Ed25519) . These algorithms represent a fundamental trilemma: Security, Performance, and Quantum Resilience.

RSA-PSS offers strong security (based on the integer factorization problem) but is computationally heavier and generates larger signatures (256 bytes for a 2048-bit key, 512 bytes for 4096-bit). ECDSA offers equivalent security with much smaller keys (256 bits) and faster verification (4× faster than RSA-PSS), but it is vulnerable to quantum attacks (Shor’s algorithm) more easily than RSA due to the smaller key space. EdDSA (Ed25519) provides the fastest signing and verification of all, with built-in protection against side-channel attacks (constant-time execution), but is not yet universally mandated in all Open Banking jurisdictions.

This lesson formalizes the mathematical underpinnings of these algorithms. We derive the modular exponentiation cost for RSA-PSS (O(k^3) for signing, O(k^2) for verification), the elliptic curve scalar multiplication cost for ECDSA/EdDSA (O(log p) point additions), and the quantum attack complexity using Grover’s and Shor’s algorithms. We also quantify the latency impact of each algorithm on the critical path: RSA-PSS verification takes ~0.5ms, ECDSA (ES256) takes ~0.1ms, and Ed25519 takes ~0.05ms. We will provide a decision matrix for the certified practitioner, mapping each algorithm to the specific use case (client assertion signing vs. JARM response vs. ID token signing) based on regulatory constraints and hardware acceleration availability (AES-NI vs. ARM Crypto extensions).

LEARNING OBJECTIVES

  1. Deconstruct the RSA-PSS Signature—deriving the exact formula for signature generation (s = (m || salt)^d mod n) and verification (m' = s^e mod n), and proving mathematically that the random salt (32 bytes) provides probabilistic security against chosen-message attacks (the Bleichenbacher attack is reduced to 2^-256 success probability).

  2. Compare ECDSA and EdDSA—analyzing the elliptic curve scalar multiplication equation Q = k × G (where k is the ephemeral private key, G is the curve generator), deriving the signature pair (r, s) for ECDSA, and proving why EdDSA’s deterministic nonce (k = H(sk || message)) eliminates the catastrophic k reuse vulnerability (which allowed the PlayStation 3 private key extraction).

  3. Quantify the Computational Complexity—using Big-O notation to compare signature verification times: RSA-PSS is O(k^2) (modular exponentiation), ECDSA/EdDSA is O(n^3) for point addition but with much smaller constants (n = 256 bits vs k = 2048 bits), resulting in a 4x–10x speed advantage for ECC-based algorithms.

  4. Analyze the Quantum Threat Model—deriving the Shor’s algorithm factorization complexity for RSA (O((log n)^3)), and the elliptic curve discrete logarithm complexity for ECC (O(log p)), and calculating the security margin (in qubit years) for each algorithm against a hypothetical large-scale quantum computer.

  5. Construct the Algorithm Selection Matrix—mapping each Open Banking use case (Client Assertion, ID Token, JARM, JWKS Signing, mTLS Server Certificate) to the optimal signature algorithm based on regulatory mandate, performance budget, and hardware platform (x86_64 vs ARM).

  6. Formalize the Post-Quantum Migration Path—designing a hybrid signature scheme (RSA + ECC) with a kid-based rollover strategy, enabling the ASPSP to transition to quantum-resistant algorithms (e.g., Dilithium, Falcon) when NIST FIPS 203 is finalized in 2028, without breaking existing TPP integrations.

PART 1: RSA-PSS — The Probabilistic Signature Scheme

1.1 The Mathematical Core

RSA-PSS (Probabilistic Signature Scheme, defined in RFC 8017) is a variant of the RSA signature scheme that uses a random salt to make the signature probabilistic.

Signature Generation:
Given a private key (n, d) and a message M:

  1. Generate a random salt salt of length sLen (typically 32 bytes).

  2. Compute M' = H(M || salt) where H is SHA-256.

  3. Encode M' into an integer m using EMSA-PSS encoding (which adds a padding structure).

  4. Compute the signature: s = m^d mod n.

Verification:
Given a public key (n, e), a message M, and a signature s:

  1. Compute m' = s^e mod n.

  2. Recover the hash H' from the EMSA-PSS encoding.

  3. Compute H(M || salt) and compare.

Security Proof:
The random salt ensures that two identical messages produce different signatures. The probability of an attacker forging a signature without the private key is the probability of finding x such that x^e ≡ m mod n. This is the RSA problem, conjectured to be O(2^112) for 2048-bit keys.

1.2 The Bleichenbacher Attack and PSS Mitigation

The older PKCS#1 v1.5 signature scheme used deterministic padding. Bleichenbacher (1998) showed that an attacker with access to a padding oracle could decrypt or forge signatures in 2^40 operations. RSA-PSS uses probabilistic padding (random salt), which destroys the oracle’s ability to distinguish valid from invalid padding, effectively nullifying the attack.

Mathematical Reduction:
P(Attack_Success) = 1 / 2^(2*sLen) (where sLen is the salt length in bits). For sLen = 256 bits, P = 2^-512, effectively zero.

1.3 Latency of RSA-PSS

  • Signing (HSM) : T_sign_RSA = 2-5 ms (RSA-2048 on a hardware module).

  • Verification (CPU) : T_verify_RSA = 0.3-0.5 ms (software, AES-NI).

PART 2: ECDSA — The Elliptic Curve Alternative

2.1 The Mathematics

ECDSA (Elliptic Curve Digital Signature Algorithm, FIPS 186-4) uses the elliptic curve discrete logarithm problem (ECDLP).

Given a curve E over a finite field, a generator point G of order n, and a private key d (a scalar), the public key is Q = d × G.

Signature Generation:

  1. Generate an ephemeral nonce k (1 ≤ k ≤ n-1) randomly.

  2. Compute R = k × G. Let r = R.x mod n. If r = 0, restart.

  3. Compute s = k^(-1) × (H(M) + d × r) mod n. If s = 0, restart.

  4. Signature is (r, s).

Verification:

  1. Compute u1 = H(M) × s^(-1) mod n and u2 = r × s^(-1) mod n.

  2. Compute P = u1 × G + u2 × Q.

  3. Accept if P.x == r mod n.

2.2 The Catastrophic k Reuse Vulnerability

If the same nonce k is used to sign two different messages, the private key can be recovered:
k = (H(M1) - H(M2)) / (s1 - s2) mod n
d = (s1 × k - H(M1)) / r mod n.

EdDSA’s Improvement: EdDSA uses a deterministic nonce k = H(sk || M), where sk is the private key. This eliminates the random number generator entropy dependency and makes k reuse impossible without identical messages.

2.3 Latency of ECDSA (P-256)

  • Signing: T_sign_ECDSA = 0.2 ms (software).

  • Verification: T_verify_ECDSA = 0.08-0.1 ms (software).

PART 3: EdDSA — The Deterministic, Side-Channel-Resistant Algorithm

3.1 The Mathematics (Ed25519)

EdDSA (Edwards-curve Digital Signature Algorithm, RFC 8032) operates on twisted Edwards curves (e.g., Ed25519). It is designed for high performance and constant-time execution, making it resistant to timing and cache side-channel attacks.

Signature Generation (Ed25519):

  1. Compute r = H(sk || M) mod n.

  2. Compute R = r × G.

  3. Compute h = H(R || pk || M).

  4. Compute s = (r + h × sk) mod n.

  5. Signature is (R, s).

Verification:

  1. Compute h = H(R || pk || M).

  2. Check s × G == R + h × pk.

  3. This is a single scalar multiplication, making verification extremely fast.

3.2 Latency of Ed25519

  • Signing: T_sign_Ed = 0.05 ms (extremely fast).

  • Verification: T_verify_Ed = 0.03 ms (fastest).

PART 4: THE QUANTUM THREAT AND POST-QUANTUM MIGRATION

4.1 Shor’s Algorithm

  • RSA: Factorization of 2048-bit modulus requires ~20 million physical qubits and 8 hours to execute.

  • ECC (P-256) : Discrete logarithm requires ~2,300 logical qubits and hours of execution.

Conclusion: ECC is more vulnerable to quantum attacks because it requires fewer qubits. RSA-4096 requires more qubits, making it slightly more resilient, but both are broken by large-scale quantum computers.

4.2 The Hybrid Signature Strategy

Until NIST FIPS 203 (CRYSTALS-Dilithium) is finalized and adopted by regulators, the ASPSP should implement a dual signature approach:

  1. Sign the payload with RSA-PSS (PS256).

  2. Sign the payload with EdDSA (Ed25519).

  3. The JWKS publishes both key IDs (kid_rsa and kid_ed).

  4. TPPs verify both signatures. If one fails, the token is rejected.

The Overhead: Two signatures add an additional 0.5ms (RSA) + 0.05ms (Ed25519) = 0.55ms, which is well within the budget.

CLOSING — THE SIGNATURE SELECTION MATRIX

 
 
Use Case Algorithm Rationale
Client Assertion (JWT) PS256 FAPI 1.0 Advanced mandate
ID Token (OIDC) PS256 FAPI mandate
JARM Response PS256 FAPI mandate
Access Token PS256 (or none) Needs integrity; signature protects against tampering
mTLS Server Certificate RSA or ECDSA Certificate authorities support RSA-2048 primarily

Transition to Lesson 4.6: With the signature algorithms mapped, we now focus on the hardware roots of trust—the Hardware Security Modules (HSMs) that store the private keys, perform the cryptographic operations, and ensure that the keys never leave the secure enclave. We will derive the latency of HSM operations, model the key generation entropy, and design the HSM cluster failover strategy.

 
PreviousNext