# The Mathematics of Digital Signatures

Angela Robinson

Communicated by Notices Associate Editor Emilie Purvine

Handwritten signatures have been used to verify the authenticity of documents for centuries. In the late 1970s, mathematicians discovered pivotal techniques to construct digital signatures for authenticating any message or data that can be represented as bit strings DH76RSA78. Digital signatures quickly evolved from theoretical tools to essential components of our global digital world. Software patches and updates are digitally signed by the provider so that before a device installs the update, the device can verify the origin of the software and that the software package was not modified after the signature was applied. Transactions on public blockchains like Bitcoin and Ethereum are digitally signed by the coin-sender to authenticate the details of the transaction (coin amount to be sent, recipient, etc.) and to prevent unauthorized changes to the transaction details.

### Components of a digital signature

Digital signature algorithms (DSAs) are used to establish authenticity and integrity. The former assures that the signed message originated from the claimed sender and the latter assures that the message has not been changed during transit. A typical example is illustrated in Figure 1.

There are three components of a digital signature scheme: key generation, sign, verify.

During the first phase of the protocol, key generation generates a pair of keys: one public key for signature verification and one secret key for signing messages. To prevent forgeries, it is critical that the signer does not share with anyone.

The sign algorithm can use to sign any message or data. Unlike handwritten signatures, a digital signature depends on the message and will thus vary. Upon receipt of a signed message, the message recipient uses public knowledge of to run the verify algorithm to determine whether the signature is valid with respect to the message.

### Constructing digital signatures

Many digital signature schemes are constructed using trapdoor functions. That is, functions that are easy to compute but difficult to invert without some knowledge of the trapdoor. One such digital signature scheme is the Edwards-curve Digital Signature Algorithm (EdDSA).

EdDSA belongs to a family of digital signature algorithms that use elliptic curves over finite fields. It is well known that for an elliptic curve defined over a finite field , forms an abelian group under addition with respect to a particular addition law. At a high level, an Edwards curve is defined by over , Edw07. Some examples of Edwards curves over with various values are given in Figure 2. The Edwards addition law is, for two points ,

The security of EdDSA is based on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). Let be a point of prime order , and let be the subgroup generated by . For any , for some . The ECDLP is, given , find . Computing is computationally easy, but solving the ECDLP requires significantly more computation time. In fact, for appropriately chosen parameters, solving the ECDLP is computationally infeasible.

### EdDSA

The following is a highly simplified version of how the components of EdDSA are used to sign a message using an Edwards curve . Let be a function that maps messages of arbitrary length to bit strings of a fixed size in a manner that is difficult to invert and difficult to find a pair of distinct input strings that map to the same output.

key generation: Selects a point of prime order , and a random integer . The point is a public parameter, is the point , and is the scalar .

sign: Given message and , computes integer and point . For simplicity, assume that and points are encoded in such a way that enables addition modulo . Let . The signature on is the pair .

verify: Computes and two points: , and . If , the signature is accepted. Otherwise, rejected. The curious reader is encouraged to check that verify accepts well-formed signatures.

Integrity is broken if an attacker manages to forge a signature on a new message . It is not known how to forge EdDSA (at cryptographic sizes) signatures without knowledge of , and recovering from requires one to solve the ECDLP. The security of EdDSA depends on the difficulty of solving the ECDLP.

The predecessor of EdDSA, the elliptic curve digital signature algorithm (ECDSA), emerged in the 1990s and performed remarkably better than the DSAs of the 1970s. EdDSA varies a bit from ECDSA but can provide even more efficiency with additional security protections. EdDSA has recently been included in US cryptographic standards Nat23.

## References

[DH76]
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654, DOI 10.1109/tit.1976.1055638. MR437208,
Show rawAMSref \bib{diffie1976new}{article}{ author={Diffie, Whitfield}, author={Hellman, Martin E.}, title={New directions in cryptography}, journal={IEEE Trans. Inform. Theory}, volume={IT-22}, date={1976}, number={6}, pages={644--654}, issn={0018-9448}, review={\MR {437208}}, doi={10.1109/tit.1976.1055638}, } 
[Edw07]
Harold M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 3, 393–422, DOI 10.1090/S0273-0979-07-01153-6. MR2318157,
Show rawAMSref \bib{edwards2007normal}{article}{ author={Edwards, Harold M.}, title={A normal form for elliptic curves}, journal={Bull. Amer. Math. Soc. (N.S.)}, volume={44}, date={2007}, number={3}, pages={393--422}, issn={0273-0979}, review={\MR {2318157}}, doi={10.1090/S0273-0979-07-01153-6}, } 
[Nat23]
National Institute of Standards and Technology, Digital signature standard (DSS), Technical Report Federal Information Processing Standards (FIPS) Publication 186-5, U.S. Department of Commerce, Washington, D.C., 2023.,
Show rawAMSref \bib{FIPS186-5}{techreport}{ author={{National Institute of Standards and Technology}}, title={Digital signature standard ({DSS})}, institution={{U.S. Department of Commerce}}, address={{Washington, D.C.}}, date={2023}, number={Federal Information Processing Standards (FIPS) Publication 186-5}, } 
[RSA78]
R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126, DOI 10.1145/359340.359342. MR700103,
Show rawAMSref \bib{rivest1978method}{article}{ author={Rivest, R. L.}, author={Shamir, A.}, author={Adleman, L.}, title={A method for obtaining digital signatures and public-key cryptosystems}, journal={Comm. ACM}, volume={21}, date={1978}, number={2}, pages={120--126}, issn={0001-0782}, review={\MR {700103}}, doi={10.1145/359340.359342}, } 

## Credits

Figure 1 and Figure 2 are courtesy of Angela Robinson.

Photo of Angela Robinson is courtesy of Keyi Liu.