# Asymmetric algorithms

There are generally three things asymmetric algorithms can do:

• Encrypt/decrypt

• Sign/verify

• Key exchange

However, not all algorithms can perform all functions:

• RSA: Used for encryption, decryption, signing, and verifying.

• DSA: Used for signing and verifying.

• Diffie-Hellman: Used for key exchange.

• ECC: Used for signing and verifying (ECDSA), key exchange (ECDH), and encryption and decryption (EC ElGamal)

## Vlong queue

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.

## RSA

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.

### RSA encryption

There are two padding modes that can be used for RSA encryption:

1. PKCS #1 v1.5 (RFC 2313)

This version of padding requires a RNG for a minimum of 8 random padding bytes for standard public key encryption. The total padding must consist of at least 11 bytes, so the length of the input plaintext can be no larger than the RSA key size (i.e. modulus size) in bytes minus 11. For example, if using RSA-2048, i.e. a 256 byte modulus, the plaintext cannot be bigger than 245 bytes.

2. PKCS #1 OAEP (RFC 3447)

OAEP (Optimal Asymmetric Encryption Padding) is a more secure way of encoding the plaintext to be the correct length for RSA exponentiation. OAEP uses bit masking, and the NanoCrypto implementation uses the standard MGF1 mask generation function only. The hash functions to be used for the encoding scheme and the MGF method may be passed into the APIs as a runtime parameter, however the NanoCrypto implementation requires these two hash functions to be the same. The maximum size of the plaintext depends on the choice of hash function. Also, an RNG is needed for OAEP padding, and an optional parameter called a Label may be used.

### RSA decryption

Standard private key decryption removes all padding or encoding and results in the plaintext as it was encrypted. Before decryption, you must know which of the padding modes was used for encryption. The input to any RSA decryption method must be the same length in bytes as the RSA key size (i.e. modulus size) in bytes.

### RSA signing

Like RSA encryption, signing also has two padding modes.

1. PKCS #1 v1.5 (RFC 2313)

This padding is analogous to that of encryption, except that it is deterministic and does not use an RNG. Typically one signs the digest or digest Info of a message and not the message itself.

2. PKCS #1 EMSA-PSS (RFC 3447)

The EMSA Probabilistic Signature Scheme (EMSA-PSS) encoding is analogous to OAEP. It also uses a mask generation function (MGF) and an RNG. Instead of a Label we make use of a Salt (i.e. a fixed postfix that will be applied to the message hash). Typically, the length of the salt is the hash result length of the hash algorithm chosen, but not always.

### Note

For either form of padding, the resulting signature is always the same length in bytes as the RSA key length (i.e. the modulus length) in bytes.

### RSA verification

For verification, as with decryption, you must know which padding or encoding scheme to use. Verification is typically performed on the digest or digest Info of the original message.

## DSA

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.

## Diffie-Hellman

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.

## ECC

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:

• P192 (disabled by default): Provides 96 bits security (analogous to RSA-1024)

• P224: Provides 112 bits security (analogous to RSA-2048)

• P256: Provides 128 bits security (analogous to RSA-3072)

• P384: Provides 192 bits security (analogous to RSA-7680)

• P521: Provides (at least) 256 bits security (analogous to RSA-15360)

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

• curve25519 (disabled by default): Provides 126 bits of security

• curve448 (disabled by default): Provides 223 bits of security

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.

### ECDSA/EdDSA

For prime field curves, ECDSA works like DSA, except operations happen on the elliptic curve rather than a finite field. An RNG is needed for the signing operation, and signature components r and s are generated. The size of each r and s in bits is that of the curve itself. Some APIs may concatenate these values, r followed by s, and call that the signature. For Edward’s form curves, an RNG is not needed, and the signature algorithm itself (EdDSA) is different from traditional ECDSA. Typically, ECDSA is applied to a digest of the original message, but EdDSA internally digests the message as part of its definition.

### ECDH/EdDH

Elliptic Curve Diffie-Hellman is analogous to traditional Diffie-Hellman except operations happen on the curve instead of within a finite field. For prime field curves, NanoCrypto supports the raw shared secret generation as either just the x-coordinate, or the x-coordinate concatenated with the y-coordinate. Either coordinate will be big-endian and padded to the length of the curve if necessary. Because TrustCore SDK prime field curves all have cofactor 1, this raw shared secret generation can be considered as either the “DH” or “CDH” primitive (for an example, see NIST Special Publication 800-56A). TrustCore SDK does not implement the concept of the seven traditional modes, such as the “Ephemeral Unified Model”; these modes may be easily developed using TrustCore SDK's (slightly) more primitive APIs. For Edward’s form curves, the shared secret is the traditional little-endian x-coordinate only (see RFC 7748).

### EC ElGamal

ElGamal should be used to encrypt/decrypt a small buffer of data. Like RSA, it is a relatively slow operation and commonly used to encrypt a symmetric key. EC ElGamal APIs are provided to perform raw encryption or decryption where the application must pad the input to the correct size for encryption and remove any unwanted padding after decryption. Also provided are APIs that perform PKCS #1 v1.5 padding analogous to RSA. ElGamal is available only on the prime field curves.