Elliptic Curve Digital Signature Algorithm

Description

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a public-key cryptography standard for creating digital signatures. It is based on the algebraic structure of elliptic curves over finite fields. In ECDSA, each entity has a private key (a randomly selected integer) and a corresponding public key (a point on the elliptic curve derived from the private key). The algorithm uses the Elliptic Curve Discrete Logarithm Problem (ECDLP) as its foundational hard problem, which is considered computationally infeasible to solve.

The signing process involves the signer's private key and a cryptographic hash of the message. The signer generates a random ephemeral key pair for each signature. Using the private key, the ephemeral private key, and the message hash, the algorithm computes two integers, 'r' and 's', which constitute the signature. The verification process uses the signer's public key, the message hash, and the signature (r, s). The verifier performs a series of elliptic curve point operations to check if a derived equation holds true. If it does, the signature is valid, proving the message was signed by the holder of the private key and was not altered.

Within 3GPP architecture, ECDSA is integrated into several critical security protocols and functions. It is specified as a supported algorithm for the Authentication and Key Agreement (AKA) enhancements, for certificate-based authentication in 5G, and for the integrity protection of signaling messages. For example, in 5G, ECDSA can be used for the digital signatures in SUCI (Subscription Concealed Identifier) computation and for the signatures on platform attestation evidence in concepts like SEAL (Secure Environment for Applications Loaded).

Key components in a 3GPP implementation include the selection of a specific elliptic curve (e.g., NIST P-256, Brainpool curves), a hash function (e.g., SHA-256), and the precise encoding of signatures. The algorithm's role is to provide strong authentication (proving the identity of a network function or UE), data integrity (ensuring signaling messages are not tampered with), and non-repudiation (the signer cannot later deny having signed). Its efficiency makes it suitable for resource-constrained environments like IoT devices and for high-volume signaling scenarios in 5G core networks.

Purpose & Motivation

ECDSA was introduced to address the inefficiencies of earlier digital signature schemes, primarily RSA. While RSA security relies on the difficulty of factoring large integers, achieving high security requires very long keys (e.g., 2048 or 4096 bits), which results in large signatures, high computational overhead, and significant bandwidth consumption. ECDSA was created to provide equivalent or greater security with much smaller key sizes (e.g., a 256-bit ECC key offers security comparable to a 3072-bit RSA key).

The historical motivation within 3GPP stems from the need for stronger and more efficient cryptography as networks evolved. Pre-4G systems relied heavily on symmetric cryptography and RSA-based certificates for core network PKI. With the advent of 4G LTE and especially 5G, the threat model expanded, and the scale of devices (IoT) exploded. RSA's computational and bandwidth costs became a bottleneck. ECDSA solves this by enabling faster signature generation/verification, smaller certificate sizes (reducing storage and transmission overhead), and lower power consumption—critical for battery-powered IoT devices.

Furthermore, ECDSA addresses the need for future-proofing against quantum computing threats more effectively than RSA, although both are vulnerable to Shor's algorithm. The shorter key lengths of ECC-based systems make the transition to post-quantum cryptography (PQC) potentially more manageable. In 3GPP, its adoption, starting in Release 12, was driven by these efficiency gains and the desire to align with global cryptographic best practices (e.g., NIST recommendations), enabling stronger authentication for network functions, UE certificates, and secure boot processes in a scalable manner.

Key Features

• Shorter key lengths: Provides strong security (e.g., 256-bit) comparable to much longer RSA keys.
• Computational efficiency: Faster signature generation and verification than RSA for equivalent security.
• Small signature size: Produces compact signatures, reducing protocol overhead.
• Standardized curves: Supports internationally recognized curves like NIST P-256, P-384, and Brainpool.
• Wide industry adoption: Integral to modern PKI, blockchain, and many internet standards.
• Foundation for advanced protocols: Used in 3GPP for SUCI protection, certificate authentication, and platform integrity.

Evolution Across Releases

Defining Specifications