Signature Algorithms ​

When using asymmetric encryption algorithms, a public-private key pair is typically utilized: the public key is used for encryption, and the private key is used for decryption.

Can We Encrypt with the Private Key? ​

Is it possible to encrypt with the private key and decrypt with the public key? Yes, it is entirely feasible.

However, upon closer consideration, since the private key is confidential and the public key is openly shared, encrypting with the private key means that anyone can decrypt the message using the public key. What is the significance of this encryption method?

The significance lies in the fact that if Xiao Ming encrypts a message with his private key—say, expressing his affection for Xiao Hong—and then publishes the encrypted message, anyone can decrypt it using Xiao Ming’s public key. This allows everyone to verify that the message indeed originated from Xiao Ming, preventing others from forging the message, and ensuring that Xiao Ming cannot deny sending it.

Thus, the ciphertext encrypted with the private key effectively serves as a digital signature. To verify this signature, one must use the public key of the private key holder. The purpose of a digital signature is to confirm that a particular piece of information was indeed sent by a specific sender, preventing forgery and ensuring non-repudiation.

Signing a Message ​

In practical applications, signatures are not created directly on the original message but rather on a hash of the original message. This can be represented as:

signature = encrypt(privateKey, sha256(message))

Verifying the signature involves decrypting it with the public key and comparing the resulting hash with the hash of the original message:

hash = decrypt(publicKey, signature)

Since users always use their private keys to sign messages, the private key effectively serves as the user's identity. The public key is used externally to verify the user's identity.

Common Digital Signature Algorithms ​

Common digital signature algorithms include:

• MD5withRSA
• SHA1withRSA
• SHA256withRSA

These algorithms essentially specify a particular hash algorithm used in conjunction with RSA for signing.

Implementing Digital Signatures in Java ​

Below is an example of using RSA for digital signatures in Java:

import java.nio.charset.StandardCharsets;
import java.security.*;
import java.util.HexFormat;

public class Main {
    public static void main(String[] args) throws GeneralSecurityException {
        // Generate RSA public/private key pair:
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        kpGen.initialize(1024);
        KeyPair kp = kpGen.generateKeyPair();
        PrivateKey sk = kp.getPrivate();
        PublicKey pk = kp.getPublic();

        // Message to be signed:
        byte[] message = "Hello, I am Bob!".getBytes(StandardCharsets.UTF_8);

        // Sign the message with the private key:
        Signature s = Signature.getInstance("SHA1withRSA");
        s.initSign(sk);
        s.update(message);
        byte[] signed = s.sign();
        System.out.println("signature: " + HexFormat.of().formatHex(signed));

        // Verify the signature with the public key:
        Signature v = Signature.getInstance("SHA1withRSA");
        v.initVerify(pk);
        v.update(message);
        boolean valid = v.verify(signed);
        System.out.println("valid? " + valid);
    }
}

In this example:

• Key Pair Generation: An RSA key pair (public and private keys) is generated.
• Signing the Message:
  • A Signature instance is created using the SHA1withRSA algorithm.
  • The signature is initialized with the private key.
  • The message is updated, and the signature is generated.
• Verifying the Signature:
  • Another Signature instance is created for verification.
  • It is initialized with the public key.
  • The same message is updated, and the signature is verified.

Using a different public key or modifying the original message will result in a failed verification.

DSA Signatures ​

Besides RSA, the DSA (Digital Signature Algorithm) can also be used for signing. DSA is an acronym for Digital Signature Algorithm and is based on the ElGamal signature scheme.

DSA is typically used in conjunction with SHA, with common algorithms including:

• SHA1withDSA
• SHA256withDSA
• SHA512withDSA

Compared to RSA digital signatures, DSA offers the advantage of faster performance.

ECDSA Signatures ​

The Elliptic Curve Digital Signature Algorithm (ECDSA) is another commonly used signature algorithm. Its key feature is that the public key can be derived from the private key. Bitcoin’s signature algorithm, for example, uses ECDSA with the standard elliptic curve secp256k1. BouncyCastle provides a complete implementation of ECDSA.

Exercise ​

Use the RSA algorithm to perform digital signatures.

Summary ​

• Digital Signatures: Created using the sender’s private key to sign the original data, allowing verification with the sender’s public key.
• Purposes of Digital Signatures:
  • Prevent Forgery: Ensures that messages are genuinely from the claimed sender.
  • Prevent Denial: The sender cannot deny having sent the message.
  • Detect Tampering: Any alteration to the signed message invalidates the signature.
• Common Digital Signature Algorithms:
  • RSA-Based: MD5withRSA, SHA1withRSA, SHA256withRSA
  • DSA-Based: SHA1withDSA, SHA256withDSA, SHA512withDSA
  • Elliptic Curve-Based: ECDSA