One of the authentication mechanisms I described earlier are message authentication codes called MACs for short. It is now time to present another type of algorithms that make this service possible. These will be digital signatures implemented by asymmetric algorithms (asymmetric algorithms). These algorithms involve a key pair. So far, we have only dealt with symmetric algorithms, in which there was only a secret key.
Handwritten and digital signatures
What connects and what distinguishes a handwritten signature from its digital counterpart? Both should be attributed to one person and impossible to forge. The signer should not be able to disavow them. They should also be easy to create and easy to verify by any person. A digital signature does not have to be physically attached to the document (it can be stored in another file) and always covers the entire document. Handwritten signatures are usually made on the last page of the document and are the same for all documents we sign. The value of a digital signature depends on the document and always covers the entire document.
Algorithms designed for digital signatures consist of three parts: a key generation operation, a signature creation operation and a signature verification operation. Of course, once generated keys can be used for multiple signatures. The terms digital signature and electronic signature are often used interchangeably. A digital signature is any form of signature stored electronically. In this sense, a scan of a handwritten signature will be an electronic signature. A digital signature is a signature based on cryptographic mechanisms. In what follows, I will focus on digital signatures.
Private and public key
Using asymmetric algorithms, the user, after generating keys, becomes the owner of a pair of keys. One of them is intended to perform the signature operation. Only the owner of the pair of keys should be able to generate the signature therefore this key must be kept secret and hence it is called a private key ( private key). The second key is used in the signature verification operation. It can be performed by all interested parties. The key for this purpose is distributed in public form and is called a public key ( public key). From the public key it is impossible to determine the private key despite the fact that they are connected by mathematical dependencies. To be more precise: this operation is theoretically possible, but by its computational complexity unfeasible in practice with a sufficiently strong key.
In the figure below I have shown a typical diagram of the signature operation. The signer calculates the value of the hash function from the document and transforms it with the private key, obtaining the signature value $$s$$. The verifier independently calculates the value of the hash function from the transmitted document, and then transforms the signature using the public key recovering the document hash calculated by the signer. If the calculated hash function values are equal then the signature corresponds to the received document and the verification operation is successful. Otherwise, the document or signature has been altered and the verification result is negative.
At this point, it is necessary to explain for what reason the signature is applied not to the document, but to its hash. This is for security reasons and is due to the principles of asymmetric algorithms. The use of a hash function prevents an attack that would allow the generation of signatures for other documents based on documents already in possession with their signatures by a person who does not own the private key. To understand exactly why such an attack is possible it is necessary to look deep into asymmetric algorithms.
RSA algorithm
The private key in the RSA algorithm (the acronym comes from the names of the creators: Rivest, Shamir, Adleman) is a pair of numbers $$(d, n)$$, the public key is a pair $$(e, n)$$. The number $$n$$ is called a modulus and is formed by calculating the product of two large random prime numbers $$p$$ and $$q$$ found at the key generation stage ($$n = p * q$$). The private key is associated with the numbers $$p$$ and $$q$$, so they must be kept secret. Their product is a component of the public key, but currently we do not know efficient algorithms for factorizing products of large prime numbers. The strength of the RSA algorithm is based on this problem. An attacker is unable to factorize the modulus and determine the value of $$d$$.
Signing a message $$M$$ is done by calculating $$S = M^e mod n$$, the inverse operation is $$M = S^d mod n$$. Note that these are mathematical formulas, so $$M$$ is a number. In addition, in order for the operations to work correctly $$M$$ must be less than $$n$$. This is one reason why we need to use a hash function for signed documents. If we were signing the entire document it would be necessary to divide it into parts, for example, $$(M1*, M2*, M3*)$$ in such a way that eachpartmeets the given condition $$M$$ smaller than $$n$$. For the given example, the signature would also consist of three components $$(S1*,S2, S3)$$. Based on this, a person who does not own the private key can easily determine the signature for a document $$(M3*, M2*, M1*)$*$.This will be $$(S3,S2, S1)$$. The use of a hash function will prevent such an attack.
The following program, implemented in Java, generates an RSA key pair of 2048 bits in the first step of operation. In the next step, for a sample message, it calculates the value of the digital signature using the SHA-256 hash function (denoted in SHA256withRSA code). The private key is involved in this operation. This signature is then verified. In this step, only the public key is already used.
1import java.security.KeyPair; 2import java.security.KeyPairGenerator; 3import java.security.SecureRandom; 4import java.security.Signature; 5 6public class RSATest { 7 public static void main(String[] args) throws Exception { 8 byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes(); 9 10 // wygenerowanie kluczy 11 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA"); 12 keyGen.initialize(2048, new SecureRandom()); 13 KeyPair keyPair = keyGen.generateKeyPair(); 14 15 // obiekt dla operacji podpisu cyfrowego 16 Signature signer = Signature.getInstance("SHA256withRSA"); 17 18 // złożenie podpisu 19 signer.initSign(keyPair.getPrivate(), new SecureRandom()); 20 signer.update(message); 21 22 byte[] signatureValue = signer.sign(); 23 24 // weryfikacja podpisu 25 signer.initVerify(keyPair.getPublic()); 26 signer.update(message); 27 28 System.out.println(signer.verify(signatureValue)); 29 } 30}
Practically, the operation of RSA digital signature can be tried on this page. As an independent experiment, I suggest that you disturb the signature value or try to verify the signature under the changed message. It is also worth observing the relationship between key length and key generation time. Details on the operation and implementation of the RSA algorithm are presented in RFC 3447.
Elliptic curves
The factorization problem is not the only one of the computationally difficult problems used in public key cryptography. In 1985, Neal Koblitz and Victor S. Miller proposed the use of elliptic curves (EC for short) in cryptography. To use algorithms based on elliptic curves, it is necessary to choose a specific curve, which is defined by a mathematical formula. Such a parameter is called a domain parameter ( domain parameter). The public key on a particular elliptic curve is one of the points selected on it.
The program posted below shows the operation of the Elliptic Curve Digital Signature Algorithm(ECDSA). In the first step, a key pair is generated using an elliptic curve labeled secp256r1. This is followed by the signature submission and verification operations. The pattern of the curve used can be found in the document Recommended Elliptic Curve Domain Parameters, which proposes elliptic curves for use in cryptography.
1import java.security.KeyPair; 2import java.security.KeyPairGenerator; 3import java.security.SecureRandom; 4import java.security.Signature; 5import java.security.spec.ECGenParameterSpec; 6 7public class ECDSATest { 8 public static void main(String[] args) throws Exception { 9 byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes(); 10 11 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 12 keyGen.initialize(new ECGenParameterSpec("secp256r1"), new SecureRandom()); 13 KeyPair keyPair = keyGen.generateKeyPair(); 14 15 Signature signer = Signature.getInstance("SHA256withECDSA"); 16 17 signer.initSign(keyPair.getPrivate(), new SecureRandom()); 18 signer.update(message); 19 20 byte[] signatureValue = signer.sign(); 21 22 signer.initVerify(keyPair.getPublic()); 23 signer.update(message); 24 25 System.out.println(signer.verify(signatureValue)); 26 } 27}
The length of the key specified on the elliptic curve is determined by the selected curve. The one used in the sample program allows generating keys of 256 bits. In terms of security, this corresponds to a key length of 3072 bits of the RSA algorithm. Since clearly shorter keys provide the same level of security, algorithms based on elliptic curves are gaining popularity.
You can also experiment with key generation and the operation of the ECDSA signature algorithm on this page. Cryptographic algorithms based on elliptic curves are described in RFC 6090.
Summary
Asymmetric algorithms simplify the process of exchanging the key between parties because the public key is public, while the private key is not shared and there is no need to create a secure channel to transfer it. This is a major advantage of this type of mechanism. However, it is important to remember that public keys, like any other data, should also be subject to an authentication process. How can we be sure that the public key belongs to the person who transferred it to us? How do we know that this person also owns the private key to the public key given to us? The solution to this problem will be exactly the same mechanism I described above. Public keys can also be accompanied by a digital signature. Such a document, complete with data identifying the owner of a given public key, is called a public key certificate ( public key certificate). I will present it in more detail in a subsequent entry.
