Asymmetric Encryption

Asymmetric encryption is based on the concept of the cryptographic key pair - two mathematically related keys: public key is kept open and is used to encrypt a message, private key known only to its originator is employed for decryption:

It is computationally infeasible to derive the private key from knowledge of the public key. There's a set of established asymmetric encryption algorithms. The most popular include RSA, ElGamal, and encryption based on the elliptic curve cryptography. RSA created by Ron Rivest, Adi Shamir and Leonard Adleman is a classical public-key cryptosystem offering encryption as well as creation of digital signatures. RSA is implemented in all cryptographic libraries, so we'll use its main principles and definitions to illustrate the essence of asymmetric encryption.

RSA Key Pair

An RSA public key consists of two components - the RSA modulus and public exponent:

(n, e)

The modulus n is a product of primes - large odd numbers. The public exponent e sometimes called encryption exponent is a positive integer between 3 and n - 1.

The private key can have two representations. The compact form represents the private key as the pair of the modulus n and the RSA private exponent d:

K = (n, d)

Here's an example of generating an RSA key pair with the help of openssl:

openssl genrsa

The command output is PEM-encoded key data with e equal to 65537 (10001 in hexadecimal notation). The modulus has 512 bits in length. These parameters can be indicated explicitly:

openssl genrsa -3 2048

The key data can be saved to a file:

openssl genrsa -out rsa.pem 1024

DES, Triple DES or IDEA ciphers can be employed to protect the key material:

openssl genrsa -out rsa.pem -des3 1024

Another way to create an RSA key pair is to launch genpkey:

openssl genpkey -algorithm RSA

The command produces a 1024-bit modulus. To feed another key length to the command, the -pkeyopt option should be used:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048

The output format is specified as PEM (default) or ASN.1 DER:

openssl genpkey -outform DER -out rsa.der -algorithm RSA

ASN.1 (Abstract Syntax Notation One) is a notation system for representing data in telecommunications and computer networking. ASN.1 only defines an abstract specification of data. A concrete representation (transfer syntax) depends on a chosen encoding scheme. DER, or Distinguished Encoding Rules, is one of such schemes. Other ASN.1 encodings may include BER - Basic Encoding Rules, CER - Canonical Encoding Rules, or XER - XML Encoding Rules. DER is a restricted version of BER. PEM files contain DER-encoded data in Base64 format as well as additional header and footer lines. To parse ASN.1 structures with the help of openssl, asn1parse command is used. certutil, one of Windows system tools, provides similar functionality:

openssl genpkey -outform DER -out rsa.der -algorithm RSA asn1parse -inform DER -in rsa.der certutil.exe -asn rsa.der

Format conversion is performed via rsa or pkey OpenSSL commands:

openssl rsa -in rsa.pem -outform DER -out rsa.der openssl pkey -in rsa.pem -outform DER -out rsa.der

RSA Primitives

RSA primitives are elementary mathematical operations on which more complex crypto techniques are built. Data conversion primitives employed in asymmetric encryption are I2OSP - Integer-to-Octet-String primitive and OS2IP - Octet-String-to-Integer primitive:

X = I2OSP (x, ln)

x = OS2IP (X)

I2OSP takes a nonnegative integer x and produces an octet string X. The string has a length equal to ln. OS2IP performs the contrary operation and converts an octet string to a nonnegative integer.

RSA cryptographic primitives are encryption and decryption. The encryption primitive produces a ciphertext representative c from a message representative m under the control of the RSA public key (n, e):

c = RSAEP ((n, e), m)

The decryption primitive derives m from c using the private key K:

m = RSADP (K, c)

Both ciphertext and message representatives are integers between 0 and n - 1.

Encryption Scheme

An encryption scheme combines encryption or decryption primitives with an encoding method. One of RSA encryption schemes is RSAES-OAEP: the scheme uses RSAEP in conjunction with EME-OAEP (Optimal Asymmetric Encryption Padding) encoding method. The formula of encryption can be represented as

C = RSAES-OAEP-ENCRYPT ((n, e), M, L)

The flow of operation includes the following stages:

EME-OAEP encoding method is applied to the original message M; as a result, M is converted into the encoded message EM; encoding techniques rely on the use of a hash function and a mask generation function; L is an optional label used to create EM; recommended hash function for the RSAES-OAEP encryption scheme is Secure Hash Algorithm (SHA-1/256/384/512); one of mask generation functions proposed by RSA is MGF1;
OS2IP data conversion primitive is applied to EM to obtain an integer message representative m;
the RSA public key (n, e) is used in RSAEP encryption primitive; the result of encryption is an integer ciphertext representative c;
the last stage is based on the I2OSP primitive: the ciphertext representative c is converted into a ciphertext C.

Decryption operation presumes the use of the RSA private key K:

M = RSAES-OAEP-DECRYPT (K, C, L)

Decryption passes through the following phases:

the ciphertext C is converted into an integer ciphertext representative c;
the private key K is used to decrypt c and produce an integer message representative m;
m is converted into an encoded message EM;
EME-OAEP decoding is applied to EM; the final output is the message M - a plaintext represented as an octet string.

RSA Implementation

RSA algorithm is widely implemented in cryptographic libraries, e. g., in PHP OpenSSL crypto extension. The openssl command line utility can be used to create key material prior to server-side programming. In the example below, the public key is extracted from the previously created PEM file, then both files are used to encrypt and decrypt a chunk of plaintext in PHP:

openssl rsa -in rsa.pem -out public.pem -pubout

<?php $private_key_file=fopen("rsa.pem", "r"); // file pointer resource $public_key_file=fopen("public.pem", "r"); // another file handler $private_key_data=fread($private_key_file, filesize("rsa.pem")); // binary-safe file read $public_key_data=fread($public_key_file, filesize("public.pem")); fclose($private_key_file); // closing file pointers fclose($public_key_file); $private_key=openssl_get_privatekey($private_key_data); // getting private key $public_key=openssl_get_publickey($public_key_data); // getting public key openssl_public_encrypt("plaintext", $ciphertext, $public_key); // encryption openssl_private_decrypt($ciphertext, $restored, $private_key); // decryption openssl_free_key($private_key); // removing keys from memory openssl_free_key($public_key); ?>

PyCrypto supports asymmetric encryption based on the RSA algorithm, too. Another asymmetric algorithm implemented in PyCrypto is ElGamal. In the example below, a key pair is generated with the modulus length of 1024 bits:

from Crypto.PublicKey import RSA rsa=RSA.generate(1024) # key pair is generated public_key=rsa.publickey() # public key object ciphertext=rsa.encrypt("plaintext", public_key) # public key is used to encrypt the plaintext restored=rsa.decrypt(ciphertext) # private key is used for decryption

The RSA standard name is used in Java Cryptography to create Cipher objects, build a key factory or launch an instance of KeyPairGenerator. Another standard name for Cipher-based asymmetric encryption is ECIES - Elliptic Curve Integrated Encryption Scheme. Additional crypto engines are exposed by the BouncyCastle provider: these are ElGamal and Naccache-Stern.

KeyPairGenerator keyPairGenerator=KeyPairGenerator.getInstance("RSA"); // algorithm-specific Initialization KeyPair keyPair=keyPairGenerator.genKeyPair(); // holder for cryptographic keys RSAPrivateKey privateKey=(RSAPrivateKey) keyPair.getPrivate();

RSAPrivateKey is a subinterface of both java.security.PrivateKey and java.security.interfaces.RSAKey APIs. To obtain private key details, the following methods can be called:

String algorithm=privateKey.getAlgorithm(); // returns RSA String encodingFormat=privateKey.getFormat(); // returns PKCS#8 BigInteger modulus=privateKey.getModulus(); // RSA modulus n BigInteger privateExponent=privateKey.getPrivateExponent(); // RSA private exponent d byte[] keyBytes=privatekey.getEncoded();

The key bytes array can be saved to a file:

FileOutputStream privateKeyStream=new FileOutputStream("private_key.der"); privateKeyStream.write(privateKey.getEncoded()); . . .

The file can be further parsed with openssl commands:

openssl asn1parse -inform DER -in private_key.der openssl rsa -inform DER -in private_key.der -outform PEM -out private_key.pem

PKCS #8 is the default encoding format of the generated RSAPrivateKey. PKCS #8 exports two ASN.1 types: these are PrivateKeyInfo and EncryptedPrivateKeyInfo. To create EncryptedPrivateKeyInfo key data structure, pkcs8 command can be invoked:

openssl pkcs8 -in private_key.pem -topk8 -out encrypted_private_key.pem

An RSA public key is also derived from the KeyPair instance:

RSAPublicKey publicKey=(RSAPublicKey) keyPair.getPublic();

RSAPublicKey inherits methods from java.security.PublicKey and java.security.interfaces.RSAKey. Its default encoding format is X.509. The default public key exponent is 65537: this value is returned by the getPublicExponent() method. The public key data can also be saved to an external file and fed to openssl commands:

FileOutputStream publicKeyStream=new FileOutputStream("public_key.der"); publicKeyStream.write(publicKey.getEncoded()); . . . openssl asn1parse -inform DER -in public_key.der openssl rsa -inform DER -in public_key.der -outform PEM -out public_key.pem -pubin

Similar to symmetric enciphering, RSA encryption in Java is based on the use of Cipher class.

Cipher cipher=Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding");

In the example above, the Cipher instance is obtained by calling getInstance() static factory method. The desired cryptographic transformation is described in terms of algorithm/mode/padding. The padding scheme is the EME-OAEP encoding method using SHA-1 and MGF1 (mask generation function) to transform the plaintext message M into encoded message EM. The next step is to initialize the Cipher for encryption:

cipher.init(Cipher.ENCRYPT_MODE, privateKey); byte[] ciphertext=cipher.doFinal("plaintext".getBytes()); // single-part operation

Decryption is performed with the public key:

AlgorithmParameters OAEPParameters=cipher.getParameters(); cipher.init(Cipher.DECRYPT_MODE, publicKey, OAEPParameters); byte[] decryptedData=cipher.doFinal(ciphertext); String restored=new String(decryptedData);

.NET Framework System.Security.Cryptography.RSA represents the base class from which RSACryptoServiceProvider inherits its methods:

byte[] plaintext=new UnicodeEncoding().GetBytes("plaintext"); RSACryptoServiceProvider csp=new RSACryptoServiceProvider(1024); byte[] ciphertext=csp.Encrypt(plaintext, true); // OAEP padding is used byte[] decrypted=csp.Decrypt(ciphertext, true);

JavaScript RSA implementations are contained in such cryptographic libraries as pidCrypt and Cryptico. pidCrypt's RSA implementation is based on JavaScript solutions created by Tom Wu:

var rsa=new pidCrypt.RSA(); rsa.generate(512, "3"); var ciphertext=rsa.encrypt("plaintext"); console.log(ciphertext); var restored=rsa.decrypt(ciphertext); console.log(restored);

In Cryptico, modulus can be 512, 1024, 2048, 4096, or 8192 bits long:

var rsa=cryptico.generateRSAKey("secret", 1024); var publicKey=cryptico.publicKeyString(rsa); // public key component of the generated key pair var encrypted=cryptico.encrypt("plaintext", publicKey); // encryption console.log(encrypted.status); // returns "success" console.log(encrypted.cipher); // returns ciphertext var restored=cryptico.decrypt(encrypted.cipher, rsa); // decryption console.log(restored.plaintext);