Asymmetric cryptography

Asymmetric cryptography refers to a type of cryptography where the key that is used to encrypt the data is different from the key that is used to decrypt the data. These keys are called private and public keys, respectively, which why asymmetric cryptography is also known as public key cryptography. It uses both public and private keys to encrypt and decrypt data, respectively. Various asymmetric cryptography schemes are in use, including RSA (named after its founders, Rivest, Shamir, and Adelman), DSA (Digital Signature Algorithm), and ElGamal encryption.

An overview of public-key cryptography is shown in the following diagram:

Figure 4.1: Encryption/decryption using public/private keys

The preceding diagram illustrates how a sender encrypts data P using the recipient's public key and encryption function E, and produces an output encrypted data C, which is then transmitted over the network to the receiver. Once it reaches the receiver, it can be decrypted using the receiver's private key by feeding the C encrypted data into function D, which will output plaintext P. This way, the private key remains on the receiver's side, and there is no need to share keys in order to perform encryption and decryption, which is the case with symmetric encryption.

The following diagram shows how the receiver uses public key cryptography to verify the integrity of the received message. In this model, the sender signs the data using their private key and transmits the message across to the receiver. Once the message is received, it is verified for integrity by the sender's public key.

It's worth noting that there is no encryption being performed in this model. It is simply presented here to help you thoroughly understand the material covering message authentication and validation that will be provided later in this chapter:

Figure 4.2: Model of a public-key cryptography signature scheme

The preceding diagram shows that the sender digitally signs the plaintext P with their private key using signing function S, and produces data C, which is sent to the receiver, who verifies C using the sender's public key and function V to ensure the message has indeed come from the sender.

Security mechanisms offered by public key cryptosystems include key establishment, digital signatures, identification, encryption, and decryption.

Key establishment mechanisms are concerned with the design of protocols that allow the setting up of keys over an insecure channel. Non-repudiation (defined in Chapter 3, Symmetric Cryptography, as the assurance that an action, once taken by someone, cannot be denied later) services, a very desirable property in many scenarios, can be provided using digital signatures. Sometimes, it is important not only to authenticate a user but also to identify the entity involved in a transaction. This can also be achieved by a combination of digital signatures and challenge-response protocols. Finally, the encryption mechanism to provide confidentiality can also be obtained using public key cryptosystems, such as RSA, ECC, and ElGamal.

Public key algorithms are slower in terms of computation than symmetric key algorithms. Therefore, they are not commonly used in the encryption of large files or the actual data that requires encryption. They are usually used to exchange keys for symmetric algorithms. Once the keys are established securely, symmetric key algorithms can be used to encrypt the data.

Public key cryptography algorithms are based on various underlying mathematical functions. The three main categories of asymmetric algorithms are described here.

Integer factorization

Integer factorization schemes are based on the fact that large integers are very hard to factor. RSA is a prime example of this type of algorithm.

Discrete logarithm

A discrete logarithm scheme is based on a problem in modular arithmetic. It is easy to calculate the result of a modulo function, but it is computationally impractical to find the exponent of the generator. In other words, it is extremely difficult to find the input from the result (output). This is called a one-way function.

For example, consider the following equation:

32 mod 10 = 9

Now, given 9, the result of the preceding equation, finding 2, which is the exponent of the generator 3 in the equation, is extremely hard to determine. This difficult problem is commonly used in the Diffie-Hellman key exchange and digital signature algorithms.

Elliptic curves

The elliptic curves algorithm is based on the discrete logarithm problem discussed previously, but in the context of elliptic curves. An elliptic curve is an algebraic cubic curve over a field, which can be defined by an equation, as shown here. The curve is non-singular, which means that it has no cusps or self-intersections. It has two variables a and b, as well as a point of infinity:

Here, a and b are integers whose values are elements of the field on which the elliptic curve is defined. Elliptic curves can be defined over reals, rational numbers, complex numbers, or finite fields. For cryptographic purposes, an elliptic curve over prime finite fields is used instead of real numbers. Additionally, the prime should be greater than 3. Different curves can be generated by varying the values of a and/or b.

The most prominently used cryptosystems based on elliptic curves are the Elliptic Curve Digital Signatures Algorithm (ECDSA) and the Elliptic Curve Diffie-Hellman (ECDH) key exchange.

In this section, we discovered the basic principle of public key cryptography and relevant categories of asymmetric algorithms. This understanding will serve as a foundation for the concepts introduced next in this chapter. One of the key concepts in asymmetric cryptography is of public and private keys, which we'll describe next.

Public and private keys

A private key, as the name suggests, is a randomly generated number that is kept secret and held privately by its users. Private keys need to be protected and no unauthorized access should be granted to that key; otherwise, the whole scheme of public key cryptography is jeopardized, as this is the key that is used to decrypt messages. Private keys can be of various lengths, depending on the type and class of algorithms used. For example, in RSA, typically, a key of 1,024 bits or 2,048 bits is used. The 1,024-bit key size is no longer considered secure, and at least a 2,048-bit key size is recommended.

A public key is freely available and published by the private key owner. Anyone who would then like to send the publisher of the public key an encrypted message can do so, by encrypting the message using the published public key and sending it to the holder of the private key. No one else is able to decrypt the message because the corresponding private key is held securely by the intended recipient. Once the public key-encrypted message is received, the recipient can decrypt the message using the private key. There are a few concerns, however, regarding public keys. These include authenticity and identification of the publisher of the public keys.

In the following section, we will introduce two examples of asymmetric key cryptography: RSA and ECC. RSA is the first implementation of public key cryptography where ECC is used extensively in blockchain technology.

RSA

RSA was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adelman, hence the name RSA. This type of public key cryptography is based on the integer factorization problem, where the multiplication of two large prime numbers is easy, but it is difficult to factor the product (the result of the multiplication) back to the two original numbers.

The crux of the work involved with the RSA algorithm happens during the key generation process. An RSA key pair is generated by performing the following steps:

1. Modulus generation:
   • Select p and q , which are very large prime numbers
   • Multiply p and q, n=p.q to generate modulus n
2. Generate the co-prime:
   • Assume a number called e.
   • e should satisfy a certain condition; that is, it should be greater than 1 and less than (p-1) (q-1). In other words, e must be a number such that no number other than 1 can be divided into e and (p-1) (q-1). This is called a co-prime, that is, e is the co-prime of (p-1)(q-1).
3. Generate the public key:
   • The modulus generated in step 1 and co-prime e generated in step 2 is a pair that is a public key. This part is the public part that can be shared with anyone; however, p and q need to be kept secret.
4. Generate the private key:
   • The private key is called d here and is calculated from p, q, and e. The private key is basically the inverse of e modulo (p-1)(q-1). As an equation, it is as follows:

ed = 1 mod(p-1)(q-1)

Usually, an extended Euclidean algorithm is used to calculate d. This algorithm takes p, q, and e and calculates d. The key idea in this scheme is that anyone who knows p and q can easily calculate private key d by applying the extended Euclidean algorithm. However, someone who does not know the value of p and q cannot generate d. This also implies that p and q should be large enough for the modulus n to become extremely difficult (computationally impractical) to factor.

Now, let's see how encryption and decryption operations are performed using RSA. RSA uses the following equation to produce ciphertext:

C = Pe mod n

This means that plaintext P is raised to the power of e and then reduced to modulo n. Decryption in RSA is provided in the following equation:

P = Cd mod n

This means that the receiver who has a public key pair (n, e) can decipher the data by raising C to the value of the private key d, and then reducing to modulo n.

We'll look at a practical example of encryption and decryption with RSA later in the chapter. For now, let's explore the fundamentals of ECC.

Elliptic curve cryptography

ECC is based on the discrete logarithm problem founded upon elliptic curves over finite fields (Galois fields). The main benefit of ECC over other types of public key algorithms is that it requires a smaller key size, while providing the same level of security as, for example, RSA. Two notable schemes that originate from ECC are ECDH for key exchange and ECDSA for digital signatures.

ECC can also be used for encryption, but it is not usually used for this purpose in practice. Instead, key exchange and digital signatures are used more commonly. As ECC needs less space to operate, it is becoming very popular on embedded platforms and in systems where storage resources are limited. By comparison, the same level of security can be achieved with ECC when only using 256-bit operands as compared to 3,072 bits in RSA.

Mathematics behind ECC

To understand ECC, a basic introduction to the underlying mathematics is necessary. An elliptic curve is basically a type of polynomial equation known as the Weierstrass equation, which generates a curve over a finite field. The most commonly used field is where all arithmetic operations are performed modulo a prime number p. Elliptic curve groups consist of points on the curve over a finite field.

An elliptic curve is defined in the following equation:

Here, A and B belong to a finite field Zp or Fp (prime finite field), along with a special value called the point of infinity. The point of infinity is used to provide identity operations for points on the curve.

Furthermore, a condition also needs to be met that ensures that the equation mentioned earlier has no repeated roots. This means that the curve is non-singular.

The condition is described in the following equation, which is a standard requirement that needs to be met. More precisely, this ensures that the curve is non-singular:

To construct the discrete logarithm problem based on elliptic curves, a large enough cyclic group is required. First, the group elements are identified as a set of points that satisfy the previous equation. After this, group operations need to be defined on these points.

Basic group operations on elliptic curves are point addition and point doubling. Point addition is a process where two different points are added, and point doubling means that the same point is added to itself.

Point addition

Point addition is shown in the following diagram. This is a geometric representation of point addition on elliptic curves. In this method, a diagonal line is drawn through the curve that intersects the curve at two points shown below P and Q, which yields a third point between the curve and the line.

This point is mirrored as P+Q, which represents the result of the addition as R. This is shown as P+Q in the following diagram:

Figure 4.3: Point addition over R

The group operation denoted by the + sign for addition yields the following equation:

P + Q = R

In this case, two points are added to compute the coordinates of the third point on the curve:

P + Q = R

More precisely, this means that coordinates are added, as shown in the following equation:

(x1, y1) + (x2, y2) = (x3, y3)

The equation of point addition is as follows:

X3 = s2 – x1 – x2 mod p

y3 = s (x1 – x3) -y1 mod p

Here, we can see the result of the preceding equation:

S in the preceding equation depicts the line going through P and Q.

An example of point addition is shown here. It was produced using Certicom's online calculator. This example shows the addition and solutions for the equation over finite field F₂₃. This is in contrast to the example shown earlier, which is over real numbers and only shows the curve but provides no solutions to the equation:

Figure 4.4: Example of point addition

In the preceding example, the graph on the left-hand side shows the points that satisfy this equation:

There are 27 solutions to the equation shown earlier over finite field F₂₃. P and Q are chosen to be added to produce point R. Calculations are shown on the right-hand side, which calculates the third point R. Note that in the preceding graph, in the calculation shown on the right-hand side, l is used to depict the line going through P and Q.

As an example, to show how the equation is satisfied by the points shown in the graph, a point (x, y) is picked up where x = 3 and y = 6. This point can be visualized in the graph shown here. Notice the point at coordinate (3, 6), indicated by an arrow:

Figure 4.5: Point (3, 6) shown with an arrow (this graph was generated using sagemath)

Using these values shows that the equation is indeed satisfied:

The next section introduces the concept of point doubling, which is another operation that can be performed on elliptic curves.

Point doubling

The other group operation on elliptic curves is called point doubling. This is a process where P is added to itself. This is the case when P and Q are at the same point, so effectively the operation becomes adding the point to itself, and is therefore called point doubling. In this method, a tangent line is drawn through the curve, as shown in the following graph. The second point is obtained, which is at the intersection of the tangent line drawn and the curve. This point is then mirrored to yield the result, which is shown as 2P = P + P:

Figure 4.6: Graph representing point doubling

In the case of point doubling, the equation becomes:

Here, S is the slope of the tangent line going through P, which is the line shown at the top in the preceding graph. In the preceding example, the curve is plotted as a simple example, and no solution to the equation is shown.

The following example shows the solutions and point doubling of elliptic curves over finite field F₂₃. The graph on the left-hand side shows the points that satisfy the equation:

Figure 4.7: Example of point doubling over real numbers

As shown on the right-hand side of the preceding graph, the calculation that finds R after P is added to itself (point doubling). There is no Q shown here because the same point P is used for doubling. Note that in the calculation shown previously on the right-hand side of the graph, l is used to depict the tangent line going through P.

With this, we have covered basics of ECC. In the next section, an introduction to the discrete logarithm problem based on ECC will be presented. The discrete log problem was introduced earlier in this chapter and can be depicted with a simple equation; that is, given y, find x such that g^x = y. Fundamentally, it is a one-way function, which is easy to evaluate but extremely hard (computationally) to invert.

Using addition and doubling we can construct another operation, called point multiplication, which we introduce next.

Point multiplication

This operation is also called scalar point multiplication. It is used to multiply points on elliptic curves by a given integer. Let's call this integer d and the point P. We get dP by repeatedly adding P, d times. This operation can be described as follows:

P + P + … + P = dP, where P is added d times.

Any point on the curve can be added multiple times to itself. The result of this operation is always another point on the curve.

The addition operation is not efficient for large values of d. However, point multiplication operation can be made efficient by utilizing double and add algorithm, which combine point addition and doubling operations to achieve exponential performance gain.

For example, if using addition only, to get 9P we have to do P + P + P + P + P + P + P + P + P,which can become infeasible pretty quickly if the number of Ps increases. To address this we can use the double and add mechanism where we first convert nine into binary, then starting from the most significant bit, for each bit that is 1 (high) perform double and addition operation and for each 0 perform only the double operation. We do not perform any operation on the most significant bit. As nine is 1001 in binary, we get for each bit, starting from left to right, P, 2P, 4P, 8P+P. This process produces 9P only with three double operations and one addition operation, instead of 9 addition operations.

In this example, point doubling and addition has been used to construct an efficient operation of scalar multiplication.

Now consider that dP results in producing another point on the curve; let's call that point T. We can say that with all these doublings and additions we have computed a point called T. We multiplied a point P on the curve with a number d to compute another point T.

Here's the key idea now: even if we know points P and T, it is computationally infeasible to reconstruct the sequence of all the double and addition operations that we did to figure out the number d. In other words, even if someone knows P and T, it is almost impossible for them to find d. This means that it is a one-way function, and it is the basis of the Elliptic Curve Discrete Logarithm Problem (ECDLP). We describe the discrete logarithm problem in more detail next.

The discrete logarithm problem in ECC

The discrete logarithm problem in ECC is based on the idea that, under certain conditions, all points on an elliptic curve form a cyclic group.

On an elliptic curve, the public key is a random multiple of the generator point, whereas the private key is a randomly chosen integer used to generate the multiple. In other words, a private key is a randomly selected integer, whereas the public key is a point on the curve. The discrete logarithm problem is used to find the private key (an integer) where that integer falls within all points on the elliptic curve. The following equation shows this concept more precisely.

Consider an elliptic curve E, with two elements P and T. The discrete logarithmic problem is to find the integer d, where 1 <= d <= #E, such that:

P + P + … + P = dP = T

Here, T is the public key (a point on the curve, (x, y)), and d is the private key. In other words, the public key is a random multiple of the generator P, whereas the private key is the integer that is used to generate the multiple. #E represents the order of the elliptic curve, which means the number of points that are present in the cyclic group of the elliptic curve. A cyclic group is formed by a combination of points on the elliptic curve and the point of infinity.

The initial starting point P is a public parameter, and the public key T is also published, whereas d, the private key, is kept secret. If d is not known, it is impractical to calculate it by only having the knowledge of T and P, thus creating the hard problem on which ECDLP is built.

A key pair is linked with the specific domain parameters of an elliptic curve. Domain parameters include field size, field representation, two elements from the field a and b, two field elements Xg and Yg, order n of point G, which is calculated as G = (Xg, Yg), and the cofactor h = #E(Fq)/n. A practical example using OpenSSL will be described later in this section.

Various parameters are recommended and standardized so they can be used as curves with ECC. An example of the SECP256K1 specification is shown here. The following figure is the specification that is used in Bitcoin, which can be accessed here: http://www.secg.org/sec2-v2.pdf.

Figure 4.8: Specification of SECP256K1

An explanation of all of these values in the sextuple follows:

• P is the prime p that specifies the size of the finite field.
• a and b are the coefficients of the elliptic curve equation.
• G is the base point that generates the required subgroup, also known as the generator. The base point can be represented in either compressed or uncompressed form. There is no need to store all points on the curve in a practical implementation. The compressed generator works because the points on the curve can be identified using only the x coordinate and the least significant bit of the y coordinate.
• n is the order of the subgroup.
• h is the cofactor of the subgroup.

We can also use the OpenSSL command line to view these parameters of SECP256K1. This can be seen here:

$ openssl ecparam -param_enc explicit -text -noout -name secp256k1

This command will show the output as follows:

Field Type: prime-field
Prime:
  00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
  ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:ff:
  ff:fc:2f
A:  0
B:  7 (0x7)
Generator (uncompressed):
  04:79:be:66:7e:f9:dc:bb:ac:55:a0:62:95:ce:87:
  0b:07:02:9b:fc:db:2d:ce:28:d9:59:f2:81:5b:16:
  f8:17:98:48:3a:da:77:26:a3:c4:65:5d:a4:fb:fc:
  0e:11:08:a8:fd:17:b4:48:a6:85:54:19:9c:47:d0:
  8f:fb:10:d4:b8
Order: 
  00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
  ff:fe:ba:ae:dc:e6:af:48:a0:3b:bf:d2:5e:8c:d0:
  36:41:41
Cofactor: 1 (0x1)

This output can be readily compared and verified using the SECP256K1 specification shown earlier.

In the following section, two examples of using OpenSSL will be shown to help you understand the practical aspects of RSA and ECC.

RSA using OpenSSL

The following example illustrates how RSA public and private key pairs can be generated using the OpenSSL command line.

First, the RSA private key can be generated using OpenSSL as follows:

Private key

$ openssl genpkey -algorithm RSA -out privatekey.pem -pkeyopt rsa_keygen_bits:1024
...............................++++++
....................++++++

After executing the command, a file named privatekey.pem is produced, which contains the generated private key, as follows:

$ cat privatekey.pem
-----BEGIN PRIVATE KEY-----
MIICdgIBADANBgkqhkiG9w0BAQEFAASCAmAwggJcAgEAAoGBAKJOFBzPy2vOd6em Bk/UGrzDy7TvgDYnYxBfiEJId/r+EyMt/F14k2fDTOVwxXaXTxiQgD+BKuiey/69 9itnrqW/xy/pocDMvobj8QCngEntOdNoVSaN+t0f9nRM3iVM94mz3/C/v4vXvoac PyPkr/0jhIV0woCurXGTghgqIbHRAgMBAAECgYEAlB3s/N4lJh0l1TkOSYunWtzT 6isnNkR7g1WrY9H+rG9xx4kP5b1DyE3SvxBLJA6xgBle8JVQMzm3sKJrJPFZzzT5 NNNnugCxairxcF1mPzJAP3aqpcSjxKpTv4qgqYevwgW1A0R3xKQZzBKU+bTO2hXV D1oHxu75mDY3xCwqSAECQQDUYV04wNSEjEy9tYJ0zaryDAcvd/VG2/U/6qiQGajB eSpSqoEESigbusKku+wVtRYgWWEomL/X58t+K01eMMZZAkEAw6PUR9YLebsm/Sji iOShV4AKuFdi7t7DYWE5Ulb1uqP/i28zN/ytt4BXKIs/KcFykQGeAC6LDHZyycyc ntDIOQJAVqrE1/wYvV5jkqcXbYLgV5YA+KYDOb9Y/ZRM5UETVKCVXNanf5CjfW1h MMhfNxyGwvy2YVK0Nu8oY3xYPi+5QQJAUGcmORe4w6Cs12JUJ5p+zG0s+rG/URhw B7djTXm7p6b6wR1EWYAZDM9MArenj8uXAA1AGCcIsmiDqHfU7lgz0QJAe9mOdNGW 7qRppgmOE5nuEbxkDSQI7OqHYbOLuwfCjHzJBrSgqyi6pj9/9CbXJrZPgNDwdLEb GgpDKtZs9gLv3A==
-----END PRIVATE KEY-----

Public key

As the private key is mathematically linked to the public key, it is also possible to generate or derive the public key from the private key. Using the example of the preceding private key, the public key can be generated as follows:

$ openssl rsa -pubout -in privatekey.pem -out publickey.pem 

 writing RSA key

The public key can be viewed using a file reader or any text viewer:

$ cat publickey.pem
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCiThQcz8trznenpgZP1Bq8w8u0 74A2J2MQX4hCSHf6/hMjLfxdeJNnw0zlcMV2l08YkIA/gSronsv+vfYrZ66lv8cv 6aHAzL6G4/EAp4BJ7TnTaFUmjfrdH/Z0TN4lTPeJs9/wv7+L176GnD8j5K/9I4SF dMKArq1xk4IYKiGx0QIDAQAB
-----END PUBLIC KEY-----

In order to see more details of the various components, such as the modulus, prime numbers that are used in the encryption process, or exponents and coefficients of the generated private key, the following command can be used (only part of the output is shown here as the actual output is very long):

$ openssl rsa -text -in privatekey.pem 
Private-Key: (1024 bit)
modulus:
00:a2:4e:14:1c:cf:cb:6b:ce:77:a7:a6:06:4f:d4:
1a:bc:c3:cb:b4:ef:80:36:27:63:10:5f:88:42:48:
77:fa:fe:13:23:2d:fc:5d:78:93:67:c3:4c:e5:70:
c5:76:97:4f:18:90:80:3f:81:2a:e8:9e:cb:fe:bd:
f6:2b:67:ae:a5:bf:c7:2f:e9:a1:c0:cc:be:86:e3:
f1:00:a7:80:49:ed:39:d3:68:55:26:8d:fa:dd:1f:
f6:74:4c:de:25:4c:f7:89:b3:df:f0:bf:bf:8b:d7:
be:86:9c:3f:23:e4:af:fd:23:84:85:74:c2:80:ae: 
ad:71:93:82:18:2a:21:b1:d1
publicExponent: 65537 (0x10001) privateExponent:
00:94:1d:ec:fc:de:25:26:1d:25:d5:39:0e:49:8b:
a7:5a:dc:d3:ea:2b:27:36:44:7b:83:55:ab:63:d1:
fe:ac:6f:71:c7:89:0f:e5:bd:43:c8:4d:d2:bf:10:
4b:24:0e:b1:80:19:5e:f0:95:50:33:39:b7:b0:a2:
6b:24:f1:59:cf:34:f9:34:d3:67:ba:00:b1:6a:2a:
f1:70:5d:66:3f:32:40:3f:76:aa:a5:c4:a3:c4:aa:
53:bf:8a:a0:a9:87:af:c2:05:b5:03:44:77:c4:a4:
19:cc:12:94:f9:b4:ce:da:15:d5:0f:5a:07:c6:ee: 
f9:98:36:37:c4:2c:2a:48:01
prime1:
00:d4:61:5d:38:c0:d4:84:8c:4c:bd:b5:82:74:cd:
aa:f2:0c:07:2f:77:f5:46:db:f5:3f:ea:a8:90:19:
a8:c1:79:2a:52:aa:81:04:4a:28:1b:ba:c2:a4:bb:
ec:15:b5:16:20:59:61:28:98:bf:d7:e7:cb:7e:2b: 
4d:5e:30:c6:59
prime2:
00:c3:a3:d4:47:d6:0b:79:bb:26:fd:28:e2:88:e4:
a1:57:80:0a:b8:57:62:ee:de:c3:61:61:39:52:56:
f5:ba:a3:ff:8b:6f:33:37:fc:ad:b7:80:57:28:8b:
3f:29:c1:72:91:01:9e:00:2e:8b:0c:76:72:c9:cc:
9c:9e:d0:c8:39

Exploring the public key

Similarly, the public key can be explored using the following commands. Public and private keys are base64-encoded:

$ openssl pkey -in publickey.pem -pubin -text
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCiThQcz8trznenpgZP1Bq8w8u0 74A2J2MQX4hCSHf6/hMjLfxdeJNnw0zlcMV2l08YkIA/gSronsv+vfYrZ66lv8cv 6aHAzL6G4/EAp4BJ7TnTaFUmjfrdH/Z0TN4lTPeJs9/wv7+L176GnD8j5K/9I4SF dMKArq1xk4IYKiGx0QIDAQAB
-----END PUBLIC KEY-----
Public-Key: (1024 bit) Modulus:
00:a2:4e:14:1c:cf:cb:6b:ce:77:a7:a6:06:4f:d4:
1a:bc:c3:cb:b4:ef:80:36:27:63:10:5f:88:42:48:
77:fa:fe:13:23:2d:fc:5d:78:93:67:c3:4c:e5:70:
c5:76:97:4f:18:90:80:3f:81:2a:e8:9e:cb:fe:bd:
f6:2b:67:ae:a5:bf:c7:2f:e9:a1:c0:cc:be:86:e3:
f1:00:a7:80:49:ed:39:d3:68:55:26:8d:fa:dd:1f:
f6:74:4c:de:25:4c:f7:89:b3:df:f0:bf:bf:8b:d7:
be:86:9c:3f:23:e4:af:fd:23:84:85:74:c2:80:ae: 
ad:71:93:82:18:2a:21:b1:d1
Exponent: 65537 (0x10001)

Now, the public key can be shared openly, and anyone who wants to send you a message can use the public key to encrypt the message and send it to you. You can then use the corresponding private key to decrypt the file.

Encryption and decryption using RSA

In this section, an example will be presented that demonstrates how encryption and decryption operations can be performed using RSA with OpenSSL.

Encryption

Taking the private key we generated in the previous example, the command to encrypt a text file message.txt can be constructed, as shown here:

$ echo datatoencrypt > message.txt

$ openssl rsautl -encrypt -inkey publickey.pem -pubin -in message.txt -out message.rsa

This will produce a file named message.rsa, which is in binary format. If you open message.rsa in the nano editor or any other text editor of your choice, it will show some scrambled data, as shown in the following screenshot:

Figure 4.9: message.rsa showing scrambled data

Decryption

In order to decrypt the RSA-encrypted file, the following command can be used:

$ openssl rsautl -decrypt -inkey privatekey.pem -in message.rsa -out message.dec

Now, if the file is read using cat, decrypted plaintext can be seen, as shown here:

$ cat message.dec 
datatoencrypt

ECC using OpenSSL

OpenSSL provides a very rich library of functions to perform ECC. The following section shows how to use ECC functions in a practical manner in OpenSSL.

ECC private and public key pairs

In this section, first, an example will be presented that demonstrates the creation of a private key using the ECC functions available in the OpenSSL library.

Private key

ECC is based on domain parameters defined by various standards. You can see the list of all available standards defined and the recommended curves available in OpenSSL using the following command (once again, only part of the output is shown here, and it is truncated in the middle):

$ openssl ecparam -list_curves
secp112r1 : SECG/WTLS curve over a 112 bit prime field secp112r2 : SECG curve over a 112 bit prime field secp128r1 : SECG curve over a 128 bit prime field secp128r2 : SECG curve over a 128 bit prime field secp160k1 : SECG curve over a 160 bit prime field secp160r1 : SECG curve over a 160 bit prime field secp160r2 : SECG/WTLS curve over a 160 bit prime field secp192k1 : SECG curve over a 192 bit prime field secp224k1 : SECG curve over a 224 bit prime field secp224r1 : NIST/SECG curve over a 224 bit prime field secp256k1 : SECG curve over a 256 bit prime field secp384r1 : NIST/SECG curve over a 384 bit prime field secp521r1 : NIST/SECG curve over a 521 bit prime field
prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field
.
.
.
.
brainpoolP384r1: RFC 5639 curve over a 384 bit prime field brainpoolP384t1: RFC 5639 curve over a 384 bit prime field brainpoolP512r1: RFC 5639 curve over a 512 bit prime field brainpoolP512t1: RFC 5639 curve over a 512 bit prime field

In the following example, SECP256k1 is used to demonstrate ECC usage.

Private key generation

In this section, a private key based on SECP256k1 will be generated using the OpenSSL command-line tool.

$ openssl ecparam -name secp256k1 -genkey -noout -out ec-privatekey.pem

This command will produce a file named ec-privatekey.pem, which we can view using the command shown here:

$ cat ec-privatekey.pem
-----BEGIN EC PRIVATE KEY-----
MHQCAQEEIJHUIm9NZAgfpUrSxUk/iINq1ghM/ewn/RLNreuR52h/oAcGBSuBBAAK oUQDQgAE0G33mCZ4PKbg5EtwQjk6ucv9Qc9DTr8JdcGXYGxHdzr0Jt1NInaYE0GG ChFMT5pK+wfvSLkYl5ul0oczwWKjng==
-----END EC PRIVATE KEY-----

The file named ec-privatekey.pem now contains the elliptic curve private key that is generated based on the SECP256K1 curve. In order to generate a public key from a private key, issue the following command:

$ openssl ec -in ec-privatekey.pem -pubout -out ec-pubkey.pem 

read EC key
writing EC key

Reading the file produces the following output, displaying the generated public key:

$ cat ec-pubkey.pem
-----BEGIN PUBLIC KEY----- MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAE0G33mCZ4PKbg5EtwQjk6ucv9Qc9DTr8J
dcGXYGxHdzr0Jt1NInaYE0GGChFMT5pK+wfvSLkYl5ul0oczwWKjng==
-----END PUBLIC KEY-----

Now, the ec-pubkey.pem file contains the public key derived from ec-privatekey.pem. The private key can be further explored using the following command:

$ openssl ec -in ec-privatekey.pem -text -noout 
read EC key
Private-Key: (256 bit) priv:
00:91:d4:22:6f:4d:64:08:1f:a5:4a:d2:c5:49:3f:
88:83:6a:d6:08:4c:fd:ec:27:fd:12:cd:ad:eb:91: e7:68:7f
pub:

04:d0:6d:f7:98:26:78:3c:a6:e0:e4:4b:70:42:39:
3a:b9:cb:fd:41:cf:43:4e:bf:09:75:c1:97:60:6c:
47:77:3a:f4:26:dd:4d:22:76:98:13:41:86:0a:11:
4c:4f:9a:4a:fb:07:ef:48:b9:18:97:9b:a5:d2:87:
33:c1:62:a3:9e 
ASN1 OID: secp256k1

Similarly, the public key can be further explored with the following command:

$ openssl ec -in ec-pubkey.pem -pubin - text -noout
read EC key
Private-Key: (256 bit) pub:
04:d0:6d:f7:98:26:78:3c:a6:e0:e4:4b:70:42:39:
3a:b9:cb:fd:41:cf:43:4e:bf:09:75:c1:97:60:6c:
47:77:3a:f4:26:dd:4d:22:76:98:13:41:86:0a:11:
4c:4f:9a:4a:fb:07:ef:48:b9:18:97:9b:a5:d2:87:
33:c1:62:a3:9e 
ASN1 OID: secp256k1

It is also possible to generate a file with the required parameters—in this case, SECP256K1—and then explore it further to understand the underlying parameters:

$ openssl ecparam -name secp256k1 -out secp256k1.pem 
$ cat secp256k1.pem
-----BEGIN EC PARAMETERS-----
BgUrgQQACg==
-----END EC PARAMETERS-----

The file now contains all the SECP256K1 parameters, and it can be analyzed using the following command:

$ openssl ecparam -in secp256k1.pem -text -param_enc explicit -noout

This command will produce output similar to the one shown here:

Field Type: prime-field Prime:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:ff: ff:fc:2f
A: 0
B: 7 (0x7)
Generator (uncompressed): 04:79:be:66:7e:f9:dc:bb:ac:55:a0:62:95:ce:87:
0b:07:02:9b:fc:db:2d:ce:28:d9:59:f2:81:5b:16:
f8:17:98:48:3a:da:77:26:a3:c4:65:5d:a4:fb:fc:
0e:11:08:a8:fd:17:b4:48:a6:85:54:19:9c:47:d0:
8f:fb:10:d4:b8 Order:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:fe:ba:ae:dc:e6:af:48:a0:3b:bf:d2:5e:8c:d0:
36:41:41
Cofactor: 1 (0x1)

The preceding example shows the prime number used and the values of A and B, along with the generator, order, and cofactor of the SECP256K1 curve domain parameters.

With the preceding example, our introduction to public key cryptography from an encryption and decryption perspective is complete.

Another application of hash functions is in digital signatures, where they can be used in combination with asymmetric cryptography. This concept will be explored in detail in the following section.

Digital signatures

Digital signatures provide a means of associating a message with an entity from which the message has originated. Digital signatures are used to provide data origin authentication and non-repudiation.

Digital signatures are used in blockchains, where transactions are digitally signed by senders using their private key, before the sender broadcasts the transaction to the network. This digital signing proves that the sender is the rightful owner of the asset; for example, bitcoins. These transactions are verified again by other nodes on the network to ensure that the funds indeed belong to the node (user) who claims to be the owner. We will discuss these concepts in more detail in the chapters dedicated to Bitcoin and Ethereum in this book.

Digital signatures are calculated in two steps. As an example, the high-level steps of the RSA digital signature scheme are as follows.

RSA digital signature algorithms

RSA-based digital signature algorithms are calculated using the two steps listed here. Fundamentally, the idea is to first compute the hash of the data and then sign it with the private key:

1. Calculate the hash value of the data packet. This will provide the data integrity guarantee, as the hash can be computed at the receiver's end again and matched with the original hash to check whether the data has been modified in transit. Technically, message signing can work without hashing the data first, but that is not considered secure.
2. Sign the hash value with the signer's private key. As only the signer has the private key, the authenticity of the signature and the signed data is ensured.

Digital signatures have some important properties, such as authenticity, unforgeability, and non-reusability:

• Authenticity means that the digital signatures are verifiable by a receiving party.
• The unforgeability property ensures that only the sender of the message can use the signing functionality using the private key. Digital signatures must provide protection against forgery. Forgery means an adversary fabricating a valid signature for a message without any access to the legitimate signer's private key. In other words, unforgeability means that no one else can produce the signed message produced by a legitimate sender. This is also called the property of non-repudiation.
• Non-reusability means that the digital signature cannot be separated from a message and used again for another message. In other words, the digital signature is firmly bound to the corresponding message and cannot be simply cut from its original message and attached to another.

The operation of a generic digital signature function is shown in the following diagram:

Figure 4.10: Digital signing (left) and verification process (right) (example of RSA digital signatures)

If a sender wants to send an authenticated message to a receiver, there are two methods that can be used: sign then encrypt and encrypt then sign. These two approaches of using digital signatures with encryption are as follows.

Sign then encrypt

With this approach, the sender digitally signs the data using the private key, appends the signature to the data, and then encrypts the data and the digital signature using the receiver's public key. This is considered a more secure scheme compared to the encrypt then sign scheme described next.

Encrypt then sign

With this method, the sender encrypts the data using the receiver's public key and then digitally signs the encrypted data.

Various schemes, such as RSA-, DSA-, and ECDSA-based digital signature schemes, are used in practice. RSA is the most commonly used; however, with the traction of ECC, ECDSA-based schemes are also becoming quite popular. This is beneficial in blockchains because ECC provides the same level of security that RSA does, but it uses less space. Also, the generation of keys is much faster in ECC compared to RSA, so it helps with the overall performance of the system. The following table shows that ECC is able to provide the same level of cryptographic strength as an RSA-based system with smaller key sizes:

Now that we understand how the RSA digital signature scheme works, in the next section, we'll introduce ECDSA, which is another popular digital signature scheme.

The elliptic curve digital signature algorithm

ECDSA is a DSA based on elliptic curves. The DSA is a standard for digital signatures. It is based on modular exponentiation and the discrete logarithm problem. It is used on the Bitcoin and Ethereum blockchain platforms to validate messages and provide data integrity services. Now, we'll describe how ECDSA works.

In order to sign and verify using the ECDSA scheme, the first key pair needs to be generated:

1. First, define an elliptic curve E with the following:
   • Modulus P
   • Coefficients a and b
   • Generator point A that forms a cyclic group of prime order q
2. An integer d is chosen randomly so that 0 < d < q.
3. Calculate public key B so that B = d A.
   • The public key is a sextuple in the form shown here:

     Kpb = (p,a,b,q,A,B)

   • The private key is a randomly chosen integer d in step 2:

   Kpr = d

   Now, the signature can be generated using the private and public key.

4. An ephemeral key Ke is chosen, where 0 < Ke < q. It should be ensured that Ke is truly random and that no two signatures have the same key; otherwise, the private key can be calculated.
5. Another value R is calculated using R = Ke A; that is, by multiplying A (the generator point) and the random ephemeral key.
6. Initialize a variable r with the x coordinate value of point R so that r = xR.
7. The signature can be calculated as follows:
   

   Here, m is the message for which the signature is being computed, and h(m) is the hash of the message m.

8. Signature verification is carried out by following this process:
   • Auxiliary value w is calculated as w = s-1mod q
   • Auxiliary value u1 = w. h(m) mod q
   • Auxiliary value u2 = w. r mod q
   • Calculate point P, P = u1A + u2B
9. Verification is carried out as follows:
   • r, s is accepted as a valid signature if the x-coordinate of point P calculated in Step 4 has the same value as the signature parameter r mod q; that is:

Xp = r mod q means valid signature

Xp != r mod q means invalid signature

Various practical examples will now be shown that demonstrate how the RSA digital signature can be generated, used, and verified using OpenSSL.

How to generate a digital signature using OpenSSL

The first step is to generate a hash of the message file:

$ openssl dgst -sha256 message.txt 
SHA256(message.txt)=
eb96d1f89812bf4967d9fb4ead128c3b787272b7be21dd2529278db1128d559c

Both hash generation and signing can be done in a single step, as shown here. Note that privatekey.pem was generated in the steps provided previously:

$ openssl dgst -sha256 -sign privatekey.pem -out signature.bin message.txt

Now, let's display the directory showing the relevant files:

$ cat signature.bin

In order to verify the signature, the following operation can be performed:

$ openssl dgst -sha256 -verify publickey.pem -signature signature.bin message.txt
Verified OK

Similarly, if some other signature file that is not valid is used, the verification will fail, as shown here:

$ openssl dgst -sha256 -verify publickey.pem –signature someothersignature.bin message.txt
Verification Failure

Next, an example will be presented that shows how OpenSSL can be used to perform ECDSA-related operations.

ECDSA using OpenSSL

First, the private key is generated using the following commands:

$ openssl ecparam -genkey -name secp256k1 -noout -out eccprivatekey.pem
$ cat eccprivatekey.pem
-----BEGIN EC PRIVATE KEY-----
MHQCAQEEIMVmyrnEDOs7SYxS/AbXoIwqZqJ+gND9Z2/nQyzcpaPBoAcGBSuBBAAK oUQDQgAEEKKS4E4+TATIeBX8o2J6PxKkjcoWrXPwNRo/k4Y/CZA4pXvlyTgH5LYm QbU0qUtPM7dAEzOsaoXmetqB+6cM+Q==
-----END EC PRIVATE KEY-----

Next, the public key is generated from the private key:

$ openssl ec -in eccprivatekey.pem -pubout -out eccpublickey.pem 
read EC key
writing EC key
$ cat eccpublickey.pem
-----BEGIN PUBLIC KEY----- MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEEKKS4E4+TATIeBX8o2J6PxKkjcoWrXPw
NRo/k4Y/CZA4pXvlyTgH5LYmQbU0qUtPM7dAEzOsaoXmetqB+6cM+Q==
-----END PUBLIC KEY-----

Now, suppose a file named testsign.txt needs to be signed and verified. This can be achieved as follows:

1. Create a test file:

   $ echo testing > testsign.txt
   
   $ cat testsign.txt 
   testing
   

2. Run the following command to generate a signature using a private key for the testsign.txt file:

   $ openssl dgst -ecdsa-with-SHA1 -sign eccprivatekey.pem testsign.txt > ecsign.bin
   

3. Finally, the command for verification can be run, as shown here:

   $ openssl dgst -ecdsa-with-SHA1 -verify eccpublickey.pem -signature ecsign.bin testsign.txt 
   Verified OK
   

A certificate can also be produced by using the private key generated earlier by using the command shown here:

$ openssl req -new -key eccprivatekey.pem -x509 -nodes -days 365 - out ecccertificate.pem

This command will produce an output similar to the one shown here. Enter the appropriate parameters to generate the certificate:

You are about to be asked to enter information that will be incorporated into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN. There are quite a few fields but you can leave some blank
For some fields there will be a default value, If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:GB
State or Province Name (full name) [Some-State]:Cambridge Locality Name (eg, city) []:Cambridge
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Dr.Equinox! Organizational Unit Name (eg, section) []:NA
Common Name (e.g. server FQDN or YOUR name) []:drequinox Email Address []:drequinox@drequinox.com

The certificate can be explored using the following command:

$ openssl x509 -in ecccertificate.pem -text –noout

Figure 4.11: An X509 certificate that uses the ECDSA algorithm with SHA-256

In this section, we covered digital signature schemes and some practical examples. Next, we'll present some more advanced cryptography topics.