Asymmetric algorithms

Before getting into more details about the asymmetric algorithms, examine the vlong queue.

Many functions have the following argument, which is a pool of vlongs:

struct vlong **ppVlongQueue

A vlong is a multi-precision integer. All asymmetric algorithms operate on big integers. For example, a 2048-bit RSA keypair is called 2048 because the modulus is 2048 bits long, and the RSA operation is a modular exponentiation.

Because computers do not have arbitrarily long integers (the size of an int is generally 32 bits and the size of a long long is often 64 bits), computations are made using software. The vlong is the type that holds an arbitrarily long integer and the vlong functions perform operations on them such as Add, Subtract, Divide, ModExp, and so on.

Each time an asymmetric computation is made, there are likely to be intermediate values necessary. That is, the software creates new vlong objects each time, and then frees them when done. There is a cost associated with constantly creating and freeing these objects.

An application can create a vlong queue and pass it into the asymmetric function calls. Each time an operation needs a vlong, it will first check the queue. If there is nothing there, create a new vlong. When done with the vlong, store it in the queue. After a while, the queue will likely have existing vlongs available for reuse. Using a vlong from the queue saves the time it would take to allocate and initialize the vlong, storing the vlong in the queue saves the time it would take to free it.

The application does not need to do anything other than declare a variable to be of type vlong, and pass its address to a function that uses a queue. The application does none of the queue’s bookkeeping. When the application is done with the queue (i.e., no more asymmetric operations are going to be called), destroy the queue.

vlong *pQueue = NULL;

...

status = CRYPTO_INTERFACE_RSA_signMessageAux (
  pKey, pPlainText, plainTextLen, pCipherText, &pQueue);

...

if (NULL != pQueue)
  VLONG_freeVlongQueue (&pQueue);

Each time NanoCrypto is done with a vlong, it frees it. However, if there is a queue, the code will overwrite the data in the vlong (to "erase" sensitive data) and store the object in the queue.

When the application calls freeVlongQueue, NanoCrypto frees any vlongs in the queue.

With RSA, it is possible to encrypt, decrypt, sign, or verify data. Encryption and verification will use the RSA public key while decryption and signing are done via the private key. Typically, RSA is much slower than symmetric key encryption algorithms, so it should only be used to encrypt small amounts of data. This is generally not a problem because almost all RSA encryption is done as a "digital envelope". This means bulk data is encrypted using a symmetric algorithm (such as AES or RC5) and the symmetric key is then RSA-encrypted using the recipient’s public key. The recipient can then decrypt using the private key to obtain the symmetric key and decrypt the bulk data.

DSA stands for "Digital Signature Algorithm". This algorithm can only compute and verify digital signatures. It cannot encrypt or perform key exchange. When DSA is computing a signature, it is not encrypting the digest of the data to sign. It is computing a pair of numbers (called r and s) using the private key, the digest, and a random value. The math works out that using the public key, r, and the digest, it is possible to also compute s. If the s from the signature matches the s the verifier computes, the signature verifies.

Before performing any DSA operation, a fixed set of domain parameters must be set or generated. These parameters define a cyclic multiplicative group of order q in a finite field of p elements. The generator of this group is called g. The commonly used language of “key generation” in the context of DSA also means domain parameter generation.

With Diffie-Hellman, two parties each use their own private key together with the other party’s public key to arrive at a common value called a shared secret. The private keys and shared secret itself never have to take on the risk of being transmitted. Only the public keys need to be transmitted and the shared secret is protected by the difficulty of the discrete log problem. Generally, a digest of the shared secret is then used as a symmetric key for encrypting messages or as input to any other key derivation scheme.

Like DSA, Diffie-Hellman operations occur in a multiplicative cyclic group of order q in a finite field of p elements, generated by a value g. Unlike DSA however, the domain parameters p, q, and g are usually not generated but fixed to certain groups deemed trustworthy. The most commonly used groups can be found in RFC5114, RFC3526, or RFC7919. In addition, Diffie-Hellman private/public key pairs themselves are ephemeral and typically not serialized/deserialized.

Elliptic Curve Cryptography (ECC) uses mathematics on the solution set of certain cubic or quartic equations. Before performing any cryptographic operations, a curve must be chosen. The larger the curve, the larger the security, but the slower the operations.

NanoCrypto implements seven curves and two curve forms. Five of these curves are known as prime field curves, defined in FIPS PUB 186-4. The number after “P” also represents the keysize in bits, and the security in bits of an elliptic curve is half the number of bits in the private key:

TrustCore SDK also supports the following two Edwards form curves defined in RFC 7748:

The name 25519 comes about for its over-the-prime field with 2^255 - 19 elements. The keysize in bits is 255 (effectively 252 due to the curve’s cofactor of 8). The name 448 is also the keysize of that curve in bits (effectively it will be 446 bits due to the curve’s cofactor of 4).

ECC can be used to sign or verify messages (ECDSA), exchange keys (ECDH), and encrypt or decrypt messages (ElGamal). Like RSA, ECC keys will either need to be generated, have parameters set, or be deserialized.

One thing to note about an ECC keypair is that the private key and public key live in different worlds. The private key is just a single integer (often called scalar) whose bit size is defined by the curve (i.e., a 256-bit integer for P256). On the other hand, the public key is an (x,y) coordinate pair that satisfies the equation defining the curve. Typical representation of a public key is a single byte identifier of 0x04, followed by the x coordinate and then the y coordinate, both in big-endian byte representation, and both padded to the length of the curve in bytes (if necessary). For example, on P256, a private key is a 32-byte string of octets, but a public key is a 65-byte string of octets beginning with 0x04.