Digital signature

A digital signature is a mathematical scheme used to verify the authenticity of digital messages or documents. It provides a way for a recipient to feel confident that a message actually came from a known sender. While it is similar to a handwritten signature on paper, it is much more secure. A physical signature can be copied onto a different piece of paper through forgery. In contrast, a digital signature is mathematically bound to the specific content of the message. This makes it computationally infeasible for anyone to forge a valid signature on a different message.

To function, a digital signature scheme relies on three distinct mathematical algorithms. The first is a key generation algorithm. This algorithm selects a private key at random from a set of possible keys. It then outputs both that private key and a corresponding public key. The second step is the signing algorithm. This process takes a message and the private key to produce a unique signature. The final step is the signature verifying algorithm. This algorithm uses the message, the public key, and the signature to either accept or reject the claim of authenticity.

For a digital signature to be considered successful, it must meet two main requirements: correctness and security. Correctness means that signatures produced by the signing algorithm must pass the verification algorithm when using the correct public key. Security, often referred to as existential unforgeability under chosen-message attack (EUF-CMA), is also vital. This means it should be nearly impossible for an attacker to generate a valid signature for a party without knowing that party's private key. Even if an attacker can see many valid signatures, they should not be able to create a new one for a new message.

The history of this technology began in 1976. During that year, Whitfield Diffie and Martin Hellman first described the concept of a digital signature scheme. They conjectured that these schemes could exist using functions known as trapdoor one-way permutations. Soon after, Ronald Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm. While "plain" RSA signatures were only a proof-of-concept and not fully secure, they were a major milestone. In 1988, Shafi Goldwasser, Silvio Micali, and Ronald Rivest rigorously defined the security requirements for these schemes. The first widely marketed software to use digital signatures was Lotus Notes 1.0, which was released in 1989 using the RSA algorithm.

In modern practice, many systems do not sign a whole document directly. Instead, they use a method called "hash-then-sign." First, the message is run through a hash function to create a short digest. This digest is then padded to a larger width and signed with a private key. There are several practical reasons for this approach. Using a hash is much more efficient because hashing is generally faster than signing. It also ensures compatibility, as a hash can convert any message into the specific format required by the signature scheme. Finally, it protects integrity by ensuring the receiver can recognize if all parts of a message are present and in the correct order.

Digital signatures are used in many important ways today. They provide authentication, which proves the identity of the sender. This is critical for banks that must verify instructions to change account balances. They also provide integrity, which ensures that no one has modified the message during transit. For example, a software author might sign a patch to ensure computers do not install malicious software, or malware. Furthermore, they provide non-repudiation, which means a sender cannot later deny that they sent the message. Organizations like the United States Government Printing Office use them for laws, and universities like Stanford use them for student transcripts.

Despite their strength, digital signatures have certain limitations. They do not prevent a "replay attack." In a replay attack, a person records a valid signed message and maliciously reuses it later. For instance, a signed request to transfer money could be reused to drain an account if the system lacks unique transaction IDs. Additionally, signatures can sometimes be "malleable," meaning one valid signature might be transformed into another valid signature without knowing the private key. Finally, while a public key can verify a signature, a signature cannot be used to verify that a public key is authentic.