Asymmetric Encryption Algorithms

From the DH algorithm, we can see that key pairs consisting of a public key and a private key are highly useful in encryption. The public key can be openly shared, while the private key remains completely confidential, thereby establishing the foundation of asymmetric encryption.

What is Asymmetric Encryption?

Asymmetric encryption means that the keys used for encryption and decryption are not the same: only the same public-private key pair can correctly encrypt and decrypt data.

Therefore, if Xiao Ming wants to encrypt a file to send to Xiao Hong, he should first obtain Xiao Hong’s public key. He then uses Xiao Hong’s public key to encrypt the file and sends the encrypted file to her. Only Xiao Hong’s private key can decrypt this file since her private key is held exclusively by her. This ensures that no one else can decrypt the file except Xiao Hong.

The RSA Algorithm

A typical asymmetric encryption algorithm is the RSA algorithm, named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman, hence the acronym RSA.

The significant advantage of asymmetric encryption over symmetric encryption is that while symmetric encryption requires key negotiation, asymmetric encryption allows each party to safely publish their public keys. In scenarios involving communication among N individuals:

Using Asymmetric Encryption: Only N key pairs are needed. Each person manages their own key pair.
Using Symmetric Encryption: N*(N-1)/2 keys are required. Each person must manage N-1 keys, making key management complex and increasing the risk of key leakage.

Why Not Use Only Asymmetric Encryption?

Despite the advantages, asymmetric encryption cannot entirely replace symmetric encryption due to its primary drawback: asymmetric encryption algorithms are computationally slow compared to symmetric algorithms.

Thus, in practical applications, asymmetric encryption is always used in conjunction with symmetric encryption. For example, if Xiao Ming needs to send an encrypted file to Xiao Hong, they would first exchange their public keys using RSA. Then:

Xiao Ming generates a random AES key.
Xiao Ming encrypts the AES key with Xiao Hong’s RSA public key and sends it to her.
Xiao Hong decrypts the AES key using her RSA private key.
Both parties use this shared AES key for fast symmetric encryption and decryption of their communication.

This approach mirrors the common practice in HTTPS protocols, where browsers and servers first exchange AES keys using RSA, and subsequent communications use the faster AES symmetric encryption instead of the slower RSA asymmetric encryption.

Implementing RSA in Java

Java’s standard library provides an implementation of the RSA algorithm. Below is an example code demonstrating RSA encryption and decryption:

java

import java.security.*;
import javax.crypto.Cipher;
import java.util.HexFormat;

public class Main {
    public static void main(String[] args) throws Exception {
        // Plaintext:
        byte[] plain = "Hello, encrypt use RSA".getBytes("UTF-8");
        // Create a public/private key pair:
        Person alice = new Person("Alice");
        // Encrypt using Alice's public key:
        byte[] pk = alice.getPublicKey();
        System.out.println("public key: " + HexFormat.of().formatHex(pk));
        byte[] encrypted = alice.encrypt(plain);
        System.out.println("encrypted: " + HexFormat.of().formatHex(encrypted));
        // Decrypt using Alice's private key:
        byte[] sk = alice.getPrivateKey();
        System.out.println("private key: " + HexFormat.of().formatHex(sk));
        byte[] decrypted = alice.decrypt(encrypted);
        System.out.println(new String(decrypted, "UTF-8"));
    }
}

class Person {
    String name;
    // Private key:
    PrivateKey sk;
    // Public key:
    PublicKey pk;

    public Person(String name) throws GeneralSecurityException {
        this.name = name;
        // Generate a public/private key pair:
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        kpGen.initialize(1024);
        KeyPair kp = kpGen.generateKeyPair();
        this.sk = kp.getPrivate();
        this.pk = kp.getPublic();
    }

    // Export the private key as a byte array:
    public byte[] getPrivateKey() {
        return this.sk.getEncoded();
    }

    // Export the public key as a byte array:
    public byte[] getPublicKey() {
        return this.pk.getEncoded();
    }

    // Encrypt using the public key:
    public byte[] encrypt(byte[] message) throws GeneralSecurityException {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.ENCRYPT_MODE, this.pk);
        return cipher.doFinal(message);
    }

    // Decrypt using the private key:
    public byte[] decrypt(byte[] input) throws GeneralSecurityException {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.DECRYPT_MODE, this.sk);
        return cipher.doFinal(input);
    }
}

In the RSA algorithm:

Public Key and Private Key: Both can be obtained using the getEncoded() method, which returns a byte[] representation. These can be saved to files as needed.

Restoring Keys from byte[]: To reconstruct the public or private key from a byte[] array, use the following approach:

java

byte[] pkData = ...;
byte[] skData = ...;
KeyFactory kf = KeyFactory.getInstance("RSA");
// Restore the public key:
X509EncodedKeySpec pkSpec = new X509EncodedKeySpec(pkData);
PublicKey pk = kf.generatePublic(pkSpec);
// Restore the private key:
PKCS8EncodedKeySpec skSpec = new PKCS8EncodedKeySpec(skData);
PrivateKey sk = kf.generatePrivate(skSpec);

Key Lengths: RSA keys come in various lengths such as 256, 512, 1024, 2048, and 4096 bits. Longer keys offer greater security but result in slower computation speeds.
Plaintext Size Limitation: For RSA encryption:
- With a 512-bit RSA key, the maximum plaintext length is 53 bytes.
- With a 1024-bit RSA key, the maximum plaintext length is 117 bytes.
This limitation is why RSA is typically used to encrypt AES keys rather than arbitrary-length plaintext.

Note: Additionally, using only asymmetric encryption algorithms does not protect against man-in-the-middle attacks.

Exercise

Use the RSA algorithm to perform encryption and decryption.

Summary

Asymmetric Encryption: Uses different keys for encryption and decryption. Only the corresponding public-private key pair can correctly encrypt and decrypt data.
Man-in-the-Middle Attacks: Using only asymmetric encryption algorithms does not prevent man-in-the-middle attacks.
Hybrid Encryption: Asymmetric encryption is commonly used to securely exchange symmetric keys (like AES), which are then used for efficient and fast encryption of actual data.
RSA Implementation in Java: Demonstrates how to generate key pairs, encrypt data with a public key, and decrypt data with a private key.
Key Management: Proper key management is crucial. Public keys can be shared openly, while private keys must be kept secure to maintain the integrity of the encryption system.

Asymmetric Encryption Algorithms ​

What is Asymmetric Encryption? ​

The RSA Algorithm ​

Why Not Use Only Asymmetric Encryption? ​

Implementing RSA in Java ​

Exercise ​