Skip to content

Public Key Cryptography

Jump to bottom Edit New page
etcimon edited this page Dec 4, 2014 · 5 revisions

Public key cryptography (also called assymmetric cryptography) is a collection of techniques allowing for encryption, signatures, and key agreement.

Key Objects

Public and private keys are represented by classes PublicKey and it's subclass PrivateKey. The use of inheritence here means that a PrivateKey can be converted into a reference to a public key.

None of the functions on PublicKey and PrivateKey itself are particularly useful for users of the library, because 'bare' public key operations are very insecure. The only purpose of these functions is to provide a clean interface that higher level operations can be built on. So really the only thing you need to know is that when a function takes a reference to a PublicKey, it can take any public key or private key, and similiarly for PrivateKey.

Types of PublicKey include RSAPublicKey, DSAPublicKey, ECDSAPublicKey, DHPublicKey, ECDHPublicKey, RWPublicKey, NRPublicKey,, and GOST3410PublicKey. There are corresponding PrivateKey classes for each of these algorithms.

Creating New Private Keys

Creating a new private key requires two things: a source of random numbers (see Random Number Generators) and some algorithm specific parameters that define the security level of the resulting key. For instance, the security level of an RSA key is (at least in part) defined by the length of the public key modulus in bits. So to create a new RSA private key, you would call

class RSAPrivateKey { 
    this(RandomNumberGenerator rng, size_t bits); 
}

A constructor that creates a new random RSA private key with a modulus of length bits.

Algorithms based on the discrete-logarithm problem uses what is called a group; a group can safely be used with many keys, and for some operations, like key agreement, the two keys must use the same group. There are currently two kinds of discrete logarithm groups supported in botan: the integers modulo a prime, represented by DLGroup, and elliptic curves in GF(p), represented by ECGroup. A rough generalization is that the larger the group is, the more secure the algorithm is, but correspondingly the slower the operations will be.

Given a DLGroup, you can create new DSA, Diffie-Hellman, and Nyberg-Rueppel key pairs with

class DSAPrivateKey { 
    this(RandomNumberGenerator rng, const ref DLGroup group, in BigInt x = 0);
}

class DHPrivateKey {
    this(RandomNumberGenerator rng, const ref DLGroup group, in BigInt x = 0);
}

class NRPrivateKey {
   this(RandomNumberGenerator rng, const ref DLGroup group, in BigInt x = 0);
}

class ElGamal_PrivateKey { 
   this(RandomNumberGenerator rng, const ref DLGroup group, in BigInt x = 0);
}

The optional x parameter to each of these constructors is a private key value. This allows you to create keys where the private key is formed by some special technique; for instance you can use the hash of a password (see PBKDF Algorithms for how to do that) as a private key value. Normally, you would leave the value as zero, letting the class generate a new random key.

Finally, given an ECGroup object, you can create a new ECDSA, ECDH, or GOST 34.10-2001 private key with

class ECDSAPrivateKey {
    this(RandomNumberGenerator rng, const ref ECGroup domain, in BigInt x = 0);
}

class ECDHPrivateKey {
   this(RandomNumberGenerator rng, const ref ECGroup domain, in BigInt x = 0);
}

class GOST3410PrivateKey {
   this(RandomNumberGenerator rng, const ref ECGroup domain, in BigInt x = 0);
}

Generating RSA keys

This example will generate an RSA key of a specified bitlength, and put it into a pair of key files. One is the public key in X.509 format (PEM encoded), the private key is in PKCS #8 format (also PEM encoded), either encrypted or unencrypted depending on if a password was given.

todo: add cmd/keygen.cpp

Serializing Private Keys Using PKCS #8

The standard format for serializing a private key is PKCS #8, the operations for which are defined in botan.pubkey.pkcs8. It supports both unencrypted and encrypted storage.

SecureVector!ubyte BER_encode(in PrivateKey key, RandomNumberGenerator rng, 
                               in string password, in string pbe_algo = "")

Takes any private key object, serializes it, encrypts it using password, and returns a binary structure representing the private key.

The final (optional) argument, pbe_algo, specifies a particular password based encryption (or PBE) algorithm. If you don't specify a PBE, a sensible default will be used.

string PEM_encode(in PrivateKey key, RandomNumberGenerator rng, 
                  in string pass, in string pbe_algo = "")

This formats the key in the same manner as BER_encode, but additionally encodes it into a text format with identifying headers. Using PEM encoding is highly recommended for many reasons, including compatibility with other software, for transmission over 8-bit unclean channels, because it can be identified by a human without special tools, and because it sometimes allows more sane behavior of tools that process the data.

Unencrypted serialization is also supported.

⚠️

In most situations, using unecrypted private key storage is a bad idea, because anyone can come along and grab the private key without having to know any passwords or other secrets. Unless you have very particular security requirements, always use the versions that encrypt the key based on a passphrase, described above.

SecureVector!ubyte BER_encode(in PrivateKey key);

Serializes the private key and returns the result.

string PEM_encode(in PrivateKey key);

Serializes the private key, base64 encodes it, and returns the result.

Last but not least, there are some functions that will load (and decrypt, if necessary) a PKCS #8 private key:

PrivateKey loadKey(DataSource in, RandomNumberGenerator rng, in UserInterface ui);

PrivateKey loadKey(DataSource in, RandomNumberGenerator rng, string passphrase = "");

PrivateKey loadKey(in string filename, RandomNumberGenerator rng, in UserInterface ui);

PrivateKey loadKey(in string filename, RandomNumberGenerator rng, in string passphrase = "");

These functions will return an object allocated key object based on the data from whatever source it is using (assuming, of course, the source is in fact storing a representation of a private key, and the decryption was sucessful). The encoding used (PEM or BER) need not be specified; the format will be detected automatically. The key is allocated with new, and should be released with delete when you are done with it. The first takes a generic DataSource that you have to create - the other is a simple wrapper functions that take either a filename or a memory buffer and create the appropriate DataSource.

The versions taking a string attempt to decrypt using the password given (if the key is encrypted; if it is not, the passphase value will be ignored). If the passphrase does not decrypt the key, an exception will be thrown.

The ones taking a User_Interface provide a simple callback interface which makes handling incorrect passphrases and such a bit simpler. A User_Interface has very little to do with talking to users; it's just a way to glue together Botan and whatever user interface you happen to be using.

⚠️

In a future version, it is likely that User_Interface will be replaced by a simple callback using delegate.

To use UserInterface, derive a subclass and implement:

string getPassphrase(in string what, in string source, UIResult result) const;

The what argument specifies what the passphrase is needed for (for example, PKCS #8 key loading passes what as "PKCS #8 private key"). This lets you provide the user with some indication of why your application is asking for a passphrase; feel free to pass the string through gettext(3) or moral equivalent for i18n purposes. Similarly, source specifies where the data in question came from, if available (for example, a file name). If the source is not available for whatever reason, then source will be an empty string; be sure to account for this possibility.

The function returns the passphrase as the return value, and a status code in result (either OK or CANCEL_ACTION). If CANCEL_ACTION is returned in result, then the return value will be ignored, and the caller will take whatever action is necessary (typically, throwing an exception stating that the passphrase couldn't be determined). In the specific case of PKCS #8 key decryption, a DecodingError exception will be thrown; your UI should assume this can happen, and provide appropriate error handling (such as putting up a dialog box informing the user of the situation, and canceling the operation in progress).

Serializing Public Keys

To import and export public keys, use these methods from module botan.pubkey.x509_key:

Vector!ubyte BER_encode(in PublicKey key);

string PEM_encode(in PublicKey key);

PublicKey loadKey(DataSource input);

PublicKey loadKey(in SecureVector!ubyte buffer);

PublicKey loadKey(in string filename);

These functions operate in the same way as the ones described in Serializing Private Keys, except that no encryption option is availabe.

DLGroup

As described in Creating New Private Keys, a discrete logarithm group can be shared among many keys, even keys created by users who do not trust each other. However, it is necessary to trust the entity who created the group; that is why organization like NIST use algorithms which generate groups in a deterministic way such that creating a bogus group would require breaking some trusted cryptographic primitive like SHA-2.

Instantiating a DLGroup simply requires calling

struct DLGroup {
    this(in string name);
}

The name parameter is a specially formatted string that consists of three things, the type of the group ("modp" or "dsa"), the creator of the group, and the size of the group in bits, all delimited by '/' characters.

Currently all "modp" groups included in botan are ones defined by the Internet Engineering Task Force, so the provider is "ietf", and the strings look like "modp/ietf/N" where N can be any of 768, 1024, 1536, 2048, 3072, 4096, 6144, or 8192. This group type is used for Diffie-Hellman and ElGamal algorithms.

The other type, "dsa" is used for DSA and Nyberg-Rueppel keys. They can also be used with Diffie-Hellman and ElGamal, but this is less common. The currently available groups are "dsa/jce/N" for N in 512, 768, or 1024, and "dsa/botan/N" with N being 2048 or 3072. The "jce" groups are the standard DSA groups used in the Java Cryptography Extensions, while the "botan" groups were randomly generated using the FIPS 186-3 algorithm by the library maintainers.

You can generate a new random group using

struct DLGroup {
    this(RandomNumberGenerator rng, PrimeType type, 
	     size_t pbits, size_t qbits = 0);
}

The *type* can be either `Strong`, `Prime_Subgroup`, or
`DSAKosherizer`. *pbits* specifies the size of the prime in
bits. If the *type* is `Prime_Subgroup` or `DSAKosherizer`,
then *qbits* specifies the size of the subgroup.

You can serialize a `DLGroup` using

```D
SecureVector!ubyte DER_Encode(Format format);

or

string PEM_encode(Format format);

where format is any of

  • ANSI_X9_42 (or DHPARAMETERS) for modp groups
  • ANSI_X9_57 (or DSAPARAMETERS) for DSA-style groups
  • PKCS_3 is an older format for modp groups; it should only be used for backwards compatability.

You can reload a serialized group using

void BER_decode(DataSource source, Format format);

void PEM_decode(DataSource source);

ECGroup

An ECGroup is initialized by passing the name of the group to be used to the constructor. These groups have semi-standardized names like "secp256r1" and "brainpool512r1".

Key Checking

Most public key algorithms have limitations or restrictions on their parameters. For example RSA requires an odd exponent, and algorithms based on the discrete logarithm problem need a generator $> 1$.

Each public key type has a function

bool checkKey(RandomNumberGenerator rng, bool strong);

This function performs a number of algorithm-specific tests that the key seems to be mathematically valid and consistent, and returns true if all of the tests pass.

It does not have anything to do with the validity of the key for any particular use, nor does it have anything to do with certificates that link a key (which, after all, is just some numbers) with a user or other entity. If strong is true, then it does "strong" checking, which includes expensive operations like primality checking.

Encryption

Safe public key encryption requires the use of a padding scheme which hides the underlying mathematical properties of the algorithm. Additionally, they will add randomness, so encrypting the same plaintext twice produces two different ciphertexts.

The primary interface for encryption is PKEncryptor

SecureVector!ubyte encrypt(in ubyte* input, size_t length, RandomNumberGenerator rng) const;

SecureVector!ubyte encrypt(in Vector!ubyte input, RandomNumberGenerator rng) const;

These encrypt a message, returning the ciphertext.

size_t maximumInputSize() const;

Returns the maximum size of the message that can be processed, in ubytes. If you call PKEncryptor.encrypt with a value larger than this the operation will fail with an exception.

PKEncryptor is only an interface - to actually encrypt you have to create an implementation, of which there are currently two available in the library, PKEncryptorEME and DLIES_Encryptor. DLIES is a standard method (from IEEE 1363) that uses a key agreement technique such as DH or ECDH to perform message encryption. Normally, public key encryption is done using algorithms which support it directly, such as RSA or ElGamal; these use the EME class PKEncryptorEME:

this(in PublicKey key, string eme);

With key being the key you want to encrypt messages to. The padding method to use is specified in eme.

The recommended values for eme is "EME1(SHA-1)" or "EME1(SHA-256)". If you need compatability with protocols using the PKCS #1 v1.5 standard, you can also use "EME-PKCS1-v1_5".

class DLIESEncryptor:

Available in the module botan.pubkey.algo.dlies

this(in PKKeyAgreementKey key, 
     KDF kdf, 
	 MessageAuthenticationCode mac, 
     size_t mac_key_len = 20);

Where kdf is a key derivation function (see Key Derivation Functions) and mac is a MessageAuthenticationCode.

The decryption classes are named PKDecryptor, PKDecryptorEME, and DLIESDecryptor. They are created in the exact same way, except they take the private key, and the processing function is named decrypt.

Signatures

Signature generation is performed using class PKSigner:

this(in PrivateKey key, in string emsa, Signature_Format format = IEEE_1363);

Constructs a new signer object for the private key key using the signature format emsa. The key must support signature operations. In the current version of the library, this includes RSA, DSA, ECDSA, GOST 34.10-2001, Nyberg-Rueppel, and Rabin-Williams. Other signature schemes may be supported in the future.

Currently available values for emsa include EMSA1, EMSA2, EMSA3, EMSA4, and Raw. All of them, except Raw, take a parameter naming a message digest function to hash the message with. The Raw encoding signs the input directly; if the message is too big, the signing operation will fail. Raw is not useful except in very specialized applications. Examples are "EMSA1(SHA-1)" and "EMSA4(SHA-256)".

For RSA, use EMSA4 (also called PSS) unless you need compatibility with software that uses the older PKCS #1 v1.5 standard, in which case use EMSA3 (also called "EMSA-PKCS1-v1_5"). For DSA, ECDSA, GOST 34.10-2001, and Nyberg-Rueppel, you should use EMSA1.

The format defaults to IEEE_1363 which is the only available format for RSA. For DSA and ECDSA, you can also use DER_SEQUENCE, which will format the signature as an ASN.1 SEQUENCE value.

void update(in ubyte* input, size_t length);
void update(in Vector!ubyte input);
void update(ubyte input);

These add more data to be included in the signature computation. Typically, the input will be provided directly to a hash function.

SecureVector!ubyte signature(RandomNumberGenerator rng);

Creates the signature and returns it

SecureVector!ubyte signMessage(const ubyte* input, size_t length, RandomNumberGenerator rng);
SecureVector!ubyte signMessage(in Vector!ubyte input, RandomNumberGenerator rng);

These functions are equivalent to calling PKSigner.update and then PKSigner.signature. Any data previously provided using update will be included.

Signatures are verified using class PKVerifier:

this(in PublicKey pub_key, in string emsa, Signature_Format format = IEEE_1363);

Construct a new verifier for signatures assicated with public key pub_key. The emsa and format should be the same as that used by the signer.

void update(in ubyte* input, size_t length);
void update(in Vector!ubyte input);
void update(ubyte input);

Add further message data that is purportedly assocated with the signature that will be checked.

bool checkSignature(in ubyte* sig, size_t length);
bool checkSignature(in Vector!ubyte sig);

Check to see if sig is a valid signature for the message data that was written in. Return true if so. This function clears the internal message state, so after this call you can call PK_Verifier.update to start verifying another message.

bool verifyMessage(in ubyte* msg, size_t msg_length, in ubyte* sig, size_t sig_length)

bool verifyMessage(in Vector!ubyte msg, in Vector!ubyte sig);

These are equivalent to calling PKVerifier.update on msg and then calling PKVerifier.checkSignature on sig.

Here is an example of DSA signature generation

todo: add cmd/dsa_sign.cpp

Here is an example that verifies DSA signatures

todo: add cmd/dsa_ver.cpp

Key Agreement

You can get a hold of a PKKeyAgreementScheme object by calling get_pk_kas with a key that is of a type that supports key agreement (such as a Diffie-Hellman key stored in a DHPrivateKey object), and the name of a key derivation function. This can be "Raw", meaning the output of the primitive itself is returned as the key, or "KDF1(hash)" or "KDF2(hash)" where "hash" is any string you happen to like (hopefully you like strings like "SHA-256" or "RIPEMD-160"), or "X9.42-PRF(keywrap)", which uses the PRF specified in ANSI X9.42. It takes the name or OID of the key wrap algorithm that will be used to encrypt a content encryption key.

How key agreement works is that you trade public values with some other party, and then each of you runs a computation with the other's value and your key (this should return the same result to both parties). This computation can be called by using derive_key with either a ubyte array/length pair, or a SecureVector!ubyte than holds the public value of the other party. The last argument to either call is a number that specifies how long a key you want.

Depending on the KDF you're using, you might not get back a key of the size you requested. In particular "Raw" will return a number about the size of the Diffie-Hellman modulus, and KDF1 can only return a key that is the same size as the output of the hash. KDF2, on the other hand, will always give you a key exactly as long as you request, regardless of the underlying hash used with it. The key returned is a SymmetricKey, ready to pass to a block cipher, MAC, or other symmetric algorithm.

The public value that should be used can be obtained by calling public_data, which exists for any key that is associated with a key agreement algorithm. It returns a SecureVector!ubyte.

"KDF2(SHA-256)" is by far the preferred algorithm for key derivation in new applications. The X9.42 algorithm may be useful in some circumstances, but unless you need X9.42 compatibility, KDF2 is easier to use.

Add a custom footer
Add a custom sidebar
Clone this wiki locally