Asymmetric cryptography and digital signatures – Part 2
The first part of this blog series introduced the concept of symmetric cryptography, which can ensure the confidentiality of data to be exchanged. Symmetric cryptography is based on the fundamental assumption that the key used, which is to be kept secret, must be transmitted between the communication partners via a secure channel, since otherwise third parties with knowledge of the key can access the ciphertext. Accordingly, with the help of symmetric cryptography, the problem of secret message transmission is reduced to secret key transmission only. To get around this problem, this second part of the blog series presents an introduction to the concept of asymmetric cryptography.
Unlike symmetric encryption, asymmetric cryptography requires a matching key pair for the process of encryption and decryption. To encode a message, a key is used which, in contrast to the concept of symmetric cryptography, is publicly accessible to everyone (public key). With another key, which may only be known to the recipient of the message (private key), the message can be decoded again. In contrast to symmetric cryptography, in asymmetric cryptography it is the intended recipient of the message, Bob, who initiates the encryption process. To do this, he generates an asymmetrically designed key pair. The public key is published and can thus be seen by everyone in the communication channel. Alice, as the sender, encrypts the message with the publicly received public key. Because the key pair belongs together, only Bob is able to decrypt the message with the private key that is only known to him. Based on this approach, the exchange of a secret key as in symmetric cryptography becomes obsolete (1).
Asymmetric encryption methods are very complex and an understanding of how they work requires in-depth mathematical knowledge. In order to provide an introduction to the world of asymmetric encryption and to make this complexity comprehensible, we will only consider the generation of an asymmetric key pair in the following.
The construction of asymmetric keys (and also that of the actual encryption methods) is based on the principle of one-way functions. If we recall the classical function from math class, y = f(x), this simply means that it should be possible to resolve a function to y, but not to x. The effort to resolve the function to x, x = F-1 (y), should therefore not be justifiable, for example by taking several thousand years to compute it even with sufficient computational capacity (2, 3). This makes it possible to generate a contiguous key pair (x; y) and publish the public key y without being able to compute the private key x from the public key. Cross sums as a simple example illustrate this principle. A checksum is the sum of the digit values of a natural number. If, for example, the number 9876 is considered, its cross sum results from simple addition: 9+8+7+6=30. Conversely, however, it is no longer possible to readily deduce the original number from 30, which could just as easily have been 3333333333.
In terms of asymmetric encryption methods, it must be possible to calculate the public key of a key pair from the associated private key in an acceptable amount of time, but not vice versa (2). Algorithms that satisfy such properties include computations on elliptic curves, also known as elliptic curve cryptography (ECC) (4). In the following, we describe the basics of the geometric construction of a key pair based on ECC. These geometric constructions serve to visualize the underlying problem in a comprehensible way. In practical use, however, the keys are calculated mathematically (3).
Elliptic curves follow the general mathematical form y2 = x3 + ax+ b due to which they are axisymmetric with respect to the x-axis as a special property. [a]. In the underlying problem of the construction of the key pair is to be derived from two given points located on an elliptic curve P = (xp, yp) and Q = (xQ, yQ) a third point R = (xR, yR) which is also located on the same curve. The x-coordinate of the point R is the public key to be calculated. In the literature this operation is called point addition with R = P + Q. However, the used term does not refer to the classical addition as basic arithmetic but visualizes exclusively the computation of the point R from P and Q (3). Geometrically interpreted, in point addition a straight line is drawn through the points P and Q which, due to the properties of elliptic curves, results in a third intersection point of the curve (see Figure 2). This is mirrored at the x-axis and results by definition in the searched point R (3). Figure 2 visualizes an example point addition on the elliptic curve y2 = X3 + 7 which is also used in the blockchain systems of Bitcoin and Ethereum to generate digital signatures (4).
If the starting points of a point addition are identical, P = Q, the following applies R = P + P = 2P, which is also called point doubling. Since in the geometric interpretation of this operation there are infinitely many possibilities for the construction of a straight line through the two identical points, it has been agreed that the straight line is the tangent line at point P. The resulting intersection point with the elliptic curve is again mirrored at the x-axis and defines the searched point R (4). Figure 3 visualizes the point duplication of the point P. If the starting point P is added with the point 2P the point addition described above yields the point 3P. In general, the multiple point addition is also called point multiplication (4).
The character of a one-way function results for an elliptic curve as follows: If the starting point P is added d times, the result is the point R on the elliptic curve: dP = R. Geometrically, this is done by jumping from one point to the next by repeated point additions on the curve. If beside P now also the point R and thus the public key, is given as the result of the above point multiplication, it is mathematically not possible to infer the underlying number of point additions d, i.e., the private key without an unreasonable effort. (3). In the context of asymmetric cryptography, the point R on the elliptic curve corresponding to the associated public key can be calculated accordingly from the private key d, which corresponds for example to a randomly drawn number and a base point P that is public for all (5).
With a key pair generated from asymmetric algorithms, encryption procedures can then be applied without having to exchange a secret, private key between the communication partners. Thus, it is also not possible for unauthorized third parties to intercept secret keys during a key exchange and gain access to the secret message (6).
Digital signatures
Furthermore, asymmetric encryption methods can also be used to generate digital signatures (3). To do this, Alice, as the signer, must generate a matching key pair using an asymmetric procedure. Alice then generates the digital signature from her secret key and the message to be signed on the basis of a complex signature algorithm. This is transmitted together with the message to Bob, who can verify the signature using the public key (7).
This verification option for digital signatures means that signed messages can be uniquely assigned to their sender, since the signature generated on the basis of the private key can only be validly verified with the associated public key (8). As long as the private key is kept secret, only Alice can generate signatures under her name. If the signature was calculated based on a different private key, it cannot be verified with the public key at hand. In addition, digital signatures guarantee that no change has been made to the message after it has been signed, since Bob cannot subsequently verify the signature with the originally generated public key (8). Accordingly, Bob as the recipient can be sure that the message actually came from Alice and that the message remained unchanged after the signature.
Digital signatures are important cryptographic tools that are used in numerous applications, such as the secure exchange of information via e-mail, online banking, and the legally binding conclusion of digital contracts (3, 9). Similarly, the concept of digital signatures is also applied in blockchains such as Bitcoin and Ethereum, where signatures are created for transactions made on the network using the sender’s private key. The signature confirms the conformity of the transaction, which could only be created by the actual sender (10).
Cryptographic algorithms, the basic concepts of which were presented in the previous section, pursue different security goals. For example, both symmetric and asymmetric encryption methods ensure the confidentiality of information against unauthorized access by third parties. Digital signatures, on the other hand, ensure both the integrity of information, since it cannot be altered unnoticed during transmission, and the authenticity of a message, since the recipient of a message can reliably verify whether the supposed sender has also signed the message (11).
[a] Caution: In this calculation, y and x do not denote the public or private key as in the previous paragraph, but rather the geometric shape used to calculate these two keys. In the Elliptic Curve Cryptography example, the public key is the y-coordinate of the point R, and the private key is denoted by d.
Sources
- Buchmann, J. (2016). Introduction to cryptography. 6th, revised edition. Darmstadt: Springer-Verlag
- Karpfinger, C., & Kiechle, H. (2010). Cryptology. Algebraic methods and algorithms. Munich, Hamburg: Vieweg + Teubner.
- Paar, C.; Pelzl, J. (2016). Cryptography understandable. A textbook for students and users. Bochum, Springer Vieweg.
- Fertig, T., & Schütz, A. (2019). Blockchain for developers: fundamentals, programming, application. Bonn, Rheinwerk Verlag.
- Froehlich, A. (2022). Elliptical curve cryptography (ECC). TechTarget. https://www.techtarget.com/searchsecurity/definition/elliptical-curve-cryptog-raphy#:~:text=Elliptical%20curve%20cryptography%20(ECC)%20is,and%20more%20efficient%20cryptographic%20keys. Accessed on: 28.12.2022.
- SecuPedia. ECC. https://www.secupedia.info/wiki/ECC. Accessed on: 28.12.2022.
- Nakov, S. (2018). ECDSA: Elliptic Curve Signatures. https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages. Accessed on: 28.12.2022.
- Pommerening, K. (2003). Asymmetric encryption. Johannes Gutenberg University Mainz.
- Luber, S.; Schmitz, P. (2020). What is a digital signature? Security Insider. JAN. 21, 2020. https://www.security-insider.de/was-ist-eine-digitale-signatur-a-897198/. Accessed on: 28.12.2022.
- Antonopoulos, A. M (2015). Mastering Bitcoin. Unlocking digital cryptocurrencies. O’Reilly.
- Hellwig, D.; Karlic, G.; Huchzermeier, A. (2021). Develop your own blockchain. A practical guide to distributed ledger technology. Vallendar, New York, Springer.
