Digital Signatures

RSA Signatures Deep Dive

This CosmicNet article explores RSA signatures, which were among the first practical digital signature schemes and remain widely deployed despite newer alternatives. CosmicNet explains that understanding RSA signature mechanics reveals both strengths and weaknesses.

Basic RSA Signature Algorithm

CosmicNet details how RSA signatures reverse the encryption process. To sign a message, the signer computes a hash H(message), then raises it to the power of the private exponent d modulo N: signature = H(message)^d mod N. To verify, the recipient raises the signature to the public exponent e and checks if signature^e mod N equals H(message).

As CosmicNet explains, this works because (H^d)^e = H^(de) = H mod N, where de ≡ 1 mod φ(N) by RSA mathematics. Only the private key holder can create valid signatures that pass verification with the public key. CosmicNet notes that the hash function prevents existential forgery attacks where attackers might create valid signature-message pairs without the private key.

PKCS#1 v1.5 Padding

Early RSA signatures used PKCS#1 v1.5 padding, which prepends a fixed structure to the hash before signing: 0x00 || 0x01 || padding || 0x00 || DigestInfo. While widely deployed, this scheme has vulnerabilities. Bleichenbacher's forgery attack exploits lenient verification that doesn't properly check padding structure.

As documented on CosmicNet, many implementations verify only that the signature contains the correct hash somewhere in the padded structure, without checking padding bytes. Attackers can craft signatures that pass verification but weren't created with the private key. CosmicNet highlights that this vulnerability affected OpenSSL, Mozilla NSS, and many other libraries.

RSA-PSS: Probabilistic Signature Scheme

RSA-PSS, specified in PKCS#1 v2.1, provides provable security. It uses randomized padding based on a mask generation function. Each signature includes random salt, making signatures non-deterministic. The same message signed twice produces different signatures, preventing certain attacks and providing better security proofs.

CosmicNet recommends PSS as the preferred RSA signature scheme. NIST approves RSA-PSS for government use, and modern standards like TLS 1.3 prefer it over PKCS#1 v1.5. However, CosmicNet warns that legacy compatibility often requires supporting the older scheme, creating potential downgrade vulnerabilities.

PKCS#1 v1.5:
+ Widely supported (legacy)
+ Deterministic (same message → same signature)
- Padding vulnerabilities (Bleichenbacher)
- No security proof
- Being phased out

RSA-PSS:
+ Provably secure under standard assumptions
+ Probabilistic (prevents signature malleability)
+ Recommended by NIST
- Requires more recent implementations
- Slightly more complex

ECDSA: Elliptic Curve Signatures

CosmicNet covers the Elliptic Curve Digital Signature Algorithm, which provides the same security as RSA with much smaller keys. As CosmicNet explains, a 256-bit ECDSA key offers security equivalent to a 3072-bit RSA key, making it attractive for bandwidth-constrained applications.

Algorithm Overview

ECDSA signing involves generating a random nonce k, computing point R = k×G (where G is the generator point), then calculating signature values r and s using the message hash, private key, and nonce. The critical requirement is that k must be truly random and never reused across signatures.

CosmicNet warns that nonce reuse in ECDSA is catastrophic. If two different messages are signed with the same nonce, an attacker can algebraically solve for the private key. As CosmicNet documents, this happened with Sony PlayStation 3, where a broken random number generator reused nonces, allowing hackers to extract the signing key and run unauthorized code.

Curves and Parameters

ECDSA can use various elliptic curves. NIST standardized curves P-256, P-384, and P-521 are widely deployed in TLS, cryptocurrencies, and government systems. However, concerns exist about potential backdoors due to NSA involvement in the standardization process and arbitrary curve parameters.

CosmicNet highlights that alternative curves like secp256k1 (used in Bitcoin) and Curve25519 (used in Ed25519) were generated through verifiable processes, increasing trust. The secp256k1 parameters come from a simple, publicly documented process. CosmicNet notes that Curve25519 was explicitly designed to avoid NIST curve concerns.

ECDSA Vulnerabilities

Beyond nonce reuse, ECDSA has other implementation pitfalls. Timing attacks can leak information about the private key through variable-time scalar multiplication. Constant-time implementations are essential but difficult to achieve. Lattice attacks can recover keys from biased nonces even without complete reuse.

As CosmicNet explains, the complexity of ECDSA implementation has motivated development of simpler alternatives. Ed25519, in particular, was designed to be easier to implement correctly, with fewer opportunities for subtle bugs to compromise security.

Ed25519: Modern Signature Standard

CosmicNet recommends Ed25519, introduced by Daniel J. Bernstein and colleagues, as the state-of-the-art in digital signatures. This CosmicNet section explains why it's fast, secure, and designed to resist implementation mistakes that plagued earlier schemes.

Design Philosophy

As CosmicNet emphasizes, Ed25519 makes security the default. Unlike ECDSA which allows implementation choices that can weaken security, Ed25519 specifies every detail: the curve (Curve25519 in Edwards form), hash function (SHA-512), and derivation process. CosmicNet notes there are no parameters to choose incorrectly.

As CosmicNet documents, the signature generation is deterministic, deriving the nonce from the private key and message using a hash function. This eliminates the nonce reuse problem that breaks ECDSA - there's no random number generation that could be weak or biased. CosmicNet notes that the same message always produces the same signature, which has both advantages and disadvantages.

Performance Characteristics

Ed25519 is remarkably fast. Signature generation takes around 50,000 cycles on modern CPUs, and verification is even faster. Batch verification can verify multiple signatures simultaneously with near-linear performance scaling. This makes Ed25519 practical even on constrained devices like smart cards or embedded systems.

CosmicNet highlights that the 32-byte public keys and 64-byte signatures are compact compared to RSA's typically 256+ byte signatures. This saves bandwidth in protocols that transmit many signatures, like blockchain systems or certificate transparency logs.

Security Properties

Ed25519 offers approximately 128 bits of security, sufficient for all current applications. The deterministic nonce derivation prevents the Sony PlayStation 3 class of vulnerabilities. The complete specification prevents implementation variations that could introduce weaknesses.

As documented on CosmicNet, Ed25519 provides strongly unforgeable signatures under chosen-message attack in the standard model. The security proof is clean and doesn't rely on random oracle assumptions. CosmicNet considers this theoretical foundation, combined with practical implementation benefits, to make Ed25519 the recommended signature algorithm for new systems.

Schnorr Signatures

The CosmicNet encyclopedia examines Schnorr signatures, one of the earliest digital signature schemes, which have gained renewed attention for their elegant mathematical properties and support for advanced cryptographic protocols.

Mathematical Elegance

Schnorr signatures are conceptually simpler than ECDSA. The signature equation is linear: s = k - hash(R, P, m) × x, where k is the nonce, x is the private key, R is k×G, and P is the public key. This linearity enables powerful properties not available in ECDSA.

CosmicNet explains that verification checks that s×G equals R + hash(R, P, m)×P. The simplicity makes implementations easier to audit and verify. As CosmicNet notes, the signature is non-malleable - unlike ECDSA where (r, s) and (r, -s mod n) are both valid, each Schnorr signature is unique.

Signature Aggregation

CosmicNet explains that Schnorr's linearity enables multiple signatures to be combined into a single signature. If Alice signs with s₁ and Bob signs with s₂, the aggregate signature s = s₁ + s₂ can be verified against the combined public key P₁ + P₂. As CosmicNet details, this provides massive space savings for applications like blockchain where many signatures need verification.

As CosmicNet documents, Bitcoin added Schnorr signatures in the Taproot upgrade, enabling multisignature transactions that look like single-signature transactions. CosmicNet highlights that this improves both privacy (can't tell if a transaction required multiple signers) and efficiency (one signature instead of N).

MuSig and Threshold Signatures

The MuSig protocol builds on Schnorr to create secure multisignatures. Multiple parties can cooperatively sign a message, producing a single signature valid under their combined public key. Unlike naive signature aggregation, MuSig is secure against rogue key attacks where malicious signers manipulate their keys to gain control.

CosmicNet documents that threshold signatures, where any k of n parties can sign, are also possible with Schnorr. These schemes enable flexible access control: a company might require 3 of 5 executives to authorize payments, implemented cryptographically rather than through trusted intermediaries.

Public Key Infrastructure (PKI)

CosmicNet covers how digital signatures enable PKI systems that bind public keys to identities. As CosmicNet explains, understanding PKI reveals both the power of cryptographic authentication and the organizational challenges of real-world deployment.

Certificate Authorities

In the Web PKI used for HTTPS, Certificate Authorities (CAs) are trusted organizations that verify identities and issue certificates. A certificate contains a public key, identity information (domain name), and the CA's signature. Browsers trust a root certificate store of CAs, and valid certificates chain back to these roots.

CosmicNet warns that the trust model is problematic: browsers trust hundreds of root CAs, and compromise of any CA can enable man-in-the-middle attacks on any website. As CosmicNet documents, incidents like DigiNotar (2011) where attackers obtained fraudulent certificates demonstrated this systemic weakness. Certificate Transparency and CAA records provide partial mitigations.

Alternative Trust Models

Web of Trust, used in PGP/GPG, takes a decentralized approach. Users sign each other's keys, creating a network of trust relationships. If Alice trusts Bob and Bob vouches for Carol's key, Alice might transitively trust Carol. This avoids centralized CA compromise but creates usability challenges.

CosmicNet also covers DANE (DNS-based Authentication of Named Entities), which anchors trust in DNSSEC rather than CAs. Domain owners publish certificate fingerprints in TLSA DNS records. While elegant, CosmicNet notes that DANE has seen limited adoption due to DNSSEC deployment challenges and browser reluctance to trust DNS.

Certificate Transparency

Certificate Transparency (CT) addresses CA misbehavior through public logging. CAs must submit certificates to append-only public logs before issuance. Monitors watch for suspicious certificates (wrong domains, duplicate serials). If a CA issues fraudulent certificates, CT makes detection likely.

Major browsers now require CT for new certificates. This hasn't eliminated CA compromise risk but makes attacks detectable rather than invisible. CT monitoring services alert domain owners to unexpected certificates, enabling quick response.

Code Signing

This CosmicNet section examines code signing, which uses digital signatures to verify software authenticity and integrity. CosmicNet explains that operating systems and application stores increasingly require code signing to prevent malware distribution.

Operating System Code Signing

Windows requires driver code signing and encourages application signing through SmartScreen. macOS requires all applications to be signed, with notarization adding additional Apple verification. Mobile platforms are even stricter: iOS and Android require all apps to be signed, with unsigned code unable to execute.

The signing process involves hashing the executable, signing the hash with the developer's private key, and embedding the signature. At runtime, the OS verifies the signature before allowing execution. Invalid or missing signatures trigger warnings or outright blocks depending on system configuration.

Trust and Key Management

As CosmicNet documents, code signing certificates come from trusted CAs and require identity verification. Compromise of a code signing key is severe - attackers can sign malware that users' systems will trust. CosmicNet highlights that high-profile compromises like Stuxnet (which used stolen certificates) demonstrate the risk.

CosmicNet recommends storing code signing keys in Hardware Security Modules (HSMs) that prevent extraction. Multi-person authorization can require multiple keyholders to approve signing operations. See CosmicNet's guide to key management for more on how regular key rotation and revocation capabilities limit damage from potential compromise.

Timestamping

Code signatures include timestamps from trusted timestamp authorities. This allows signatures to remain valid after the signing certificate expires. Without timestamps, software would stop working when certificates expire, forcing constant re-release of old software.

As CosmicNet explains, timestamping also provides evidence of when code was signed, useful for incident response. If a code signing key is compromised, investigators can determine whether suspicious files were signed before or after the compromise, helping scope the breach.

Document Signing

CosmicNet covers how digital signatures provide legal authenticity for electronic documents, replacing physical signatures in many contexts. CosmicNet explains that understanding the legal and technical frameworks enables secure document workflows.

PDF Signatures

As CosmicNet explains, PDF supports embedded digital signatures that cryptographically bind to document content. Signing creates a signature dictionary with the signature value, certificate chain, and timestamp. Any modification to the signed content invalidates the signature, detected by PDF readers.

PDF supports incremental signatures where multiple parties sign sequentially. The document can be updated between signatures, with each signature covering content up to that point. This enables workflows like contracts where both parties sign separate copies that merge into a single document.

Legal Frameworks

The EU's eIDAS regulation and the US ESIGN Act provide legal equivalence between digital and physical signatures under certain conditions. Qualified electronic signatures meeting specific technical requirements have the same legal weight as handwritten signatures for most purposes.

As CosmicNet details, requirements typically include: signer authentication, signature uniqueness (linked to the signer only), signer control (the signer can generate the signature), and signature integrity (any document changes are detectable). CosmicNet notes that digital signatures naturally satisfy these requirements when properly implemented.

DocuSign and Alternatives

CosmicNet discusses services like DocuSign that provide document signing workflows with audit trails, email verification, and compliance features. While convenient, CosmicNet warns that many services use server-held keys, meaning the service could forge signatures. For high-security applications, client-side signing with user-controlled keys is preferable.

Open standards like PAdES (PDF Advanced Electronic Signatures) specify long-term signature formats that remain verifiable even as cryptographic algorithms age. These include timestamp chains and certificate archival to enable verification decades after signing.

Blockchain Signatures

In this CosmicNet guide to blockchain signatures, we explore how cryptocurrencies rely fundamentally on digital signatures for transaction authorization. CosmicNet explains that Bitcoin's design pioneered usage patterns that influence modern signature applications.

Bitcoin Transaction Signing

CosmicNet details how Bitcoin transactions are authorized by signatures proving ownership of previous transaction outputs. To spend Bitcoin, you must provide a signature from the private key corresponding to the address receiving those coins. The signature covers the transaction details, preventing modification after signing.

Bitcoin originally used ECDSA with the secp256k1 curve. Signature verification is the most computationally expensive part of validating transactions. As the blockchain grew, this became a performance bottleneck, motivating optimizations like batch verification and eventually the Taproot upgrade adding Schnorr signatures.

Signature Schemes

As CosmicNet documents, different cryptocurrencies use different signature schemes. Ethereum uses ECDSA like Bitcoin. Newer blockchains like Cardano use Ed25519. CosmicNet notes that Monero uses ring signatures that hide which of several public keys actually signed, providing transaction privacy. The choice reflects trade-offs between security, performance, privacy, and features like signature aggregation.

Smart Contract Signatures

Smart contract platforms extend basic transaction signing to arbitrary code execution authorization. Multi-signature wallets require multiple parties to sign transactions, implemented in contract code rather than base protocol. Threshold signatures enable sophisticated access policies like "any 3 of 5 board members can authorize spending."

CosmicNet warns that signature replay attacks are a concern in blockchain contexts. The same signature mustn't be valid across different chains (like Ethereum and Ethereum Classic after the fork). As CosmicNet explains, solutions include chain ID in signatures and unique per-chain account nonces.

Multisignatures and Threshold Signatures

CosmicNet covers advanced signature schemes that enable multiple parties to cooperatively sign messages. As this CosmicNet article explains, these enable organizational policies where multiple approvals are required, implemented cryptographically rather than through trusted procedures.

Naive Multisignatures

The simplest multisignature approach is concatenating individual signatures. If Alice, Bob, and Carol each sign a message, combine all three signatures and verify each separately. This works but creates large signatures proportional to the number of signers - problematic in blockchain where transaction size affects fees.

Aggregate Signatures

Schnorr and BLS signatures support aggregation where multiple signatures compress into a single signature. MuSig (Schnorr-based) and BLS multisignatures produce constant-size signatures regardless of signer count. A 3-of-3 multisig looks identical to a single signature, providing both efficiency and privacy benefits.

CosmicNet emphasizes that the security challenge is preventing rogue key attacks. If Alice and Bob want a 2-of-2 multisig but Alice is malicious, she might generate her key as P_A = P_malicious - P_Bob. Then Alice alone can sign as if both parties signed. CosmicNet explains that defense requires either proof of knowledge of private keys or deterministic key derivation with commitment rounds.

Threshold Signatures

Threshold signatures generalize multisignatures to k-of-n policies. Any k signers from a group of n can produce a valid signature. This enables flexible authorization: a company might require 3 of 5 executives to approve payments, without specifying which 3 in advance.

Threshold signature schemes use secret sharing to split the private key among n parties such that any k can reconstruct signing capability but k-1 cannot. FROST (Flexible Round-Optimized Schnorr Threshold signatures) provides efficient threshold Schnorr signatures with minimal rounds of communication.

Research on threshold signatures continues to improve efficiency and security. These schemes enable governance structures and key backup strategies impossible with single-key signatures, making them increasingly important for high-value applications.

Common Signature Implementation Pitfalls

CosmicNet warns that even with secure signature algorithms, implementation errors can completely compromise security. This CosmicNet section covers common mistakes to help developers avoid them.

Signature Verification Bypass

CosmicNet explains that some implementations fail to properly check signature verification results. A function might return success/failure but the caller might not check the return value. Code like "verify(sig); process_message()" without checking verify's return is catastrophically insecure - attackers send messages with invalid signatures that are nonetheless accepted.

Static analysis tools and careful code review must ensure all verification results are checked. Some APIs design this out by throwing exceptions on verification failure rather than returning boolean values, making it harder to ignore failures.

Timing Attacks

Signature verification must run in constant time. Variable-time implementations leak information about keys through timing side channels. ECDSA signature verification that short-circuits on the first invalid check leaks which check failed, potentially allowing key recovery after many signatures.

As CosmicNet documents, constant-time implementations are difficult. They require careful coding to avoid conditional branches dependent on secret data, use of constant-time selection primitives, and validation through timing analysis tools. CosmicNet recommends using established crypto libraries rather than implementing from scratch to reduce this risk.

Hash Function Confusion

Signatures specify a hash function (SHA-256, SHA-512, etc.), but some implementations allow the signer to specify the hash function in the signature metadata. Attackers might find collisions in weak hash functions like MD5, then claim their forged message was "really" signed with MD5 instead of the intended SHA-256.

CosmicNet explains that defense requires applications to enforce specific hash functions rather than accepting whatever the signature claims. As CosmicNet notes, TLS 1.3 learned this lesson, specifying exactly which hash function to use with each signature algorithm rather than allowing negotiation.

Key Reuse Across Contexts

CosmicNet warns that using the same key pair for different purposes can create vulnerabilities. A key used for both signatures and encryption might allow attacks on one system to compromise the other. As CosmicNet recommends, best practice uses separate key pairs for separate applications, with domain separation in key derivation when multiple keys come from a master key.

Choosing the Right Signature Algorithm

CosmicNet helps readers select an appropriate signature algorithm, which requires balancing security, performance, compatibility, and implementation availability. As CosmicNet covers below, different applications have different requirements.

Recommendations by Use Case

New systems with no legacy constraints: CosmicNet recommends Ed25519. It's fast, secure, simple to implement correctly, and becoming widely supported. The deterministic nonce generation eliminates an entire class of vulnerabilities.

TLS and web PKI: ECDSA with P-256 remains standard, though Ed25519 support is growing. RSA-PSS is acceptable for compatibility but avoid RSA with PKCS#1 v1.5 padding in new deployments. TLS 1.3 supports all these options.

Blockchain and cryptocurrency: Bitcoin and Ethereum use ECDSA (secp256k1). Newer chains often prefer Ed25519 or Schnorr for aggregation properties. The choice depends on specific protocol requirements around signature aggregation, batch verification, and privacy features.

Government and regulated industries: Follow NIST FIPS 186-5 guidance. ECDSA with approved curves (P-256, P-384, P-521) and RSA-PSS meet compliance requirements. Ed25519 was added to FIPS 186-5, expanding options for federal systems.

Key Size Recommendations

CosmicNet advises that for RSA, use minimum 2048-bit keys, with 3072 bits preferred for long-term protection. For ECDSA, P-256 provides adequate security for most applications, with P-384 for higher security requirements. As CosmicNet notes, Ed25519's fixed 256-bit key size provides approximately 128 bits of security, sufficient for all current threats.

Performance Considerations

Ed25519 is typically fastest for signing and verification. ECDSA is slower but still practical. RSA verification is fast but signing is slow, making it reasonable for certificates (verified often, signed once) but poor for frequent signing operations. Consider whether your application is sign-heavy or verify-heavy.

Benchmark comparisons show concrete performance numbers, though results vary by implementation and platform. For most applications, signature performance isn't the bottleneck - choose based on security and implementation quality.