CP-20200207

Cryptography Primitives Intermediate February 7, 2020

Back to All Tasks

Problem Statement

Design and implement a simple digital signature system using asymmetric cryptography. Your task is to create two programs: one for signing messages with a private key, and another for verifying signatures using the corresponding public key.

The signing program should take as input a message and a private key, then output a digital signature of the message. The verification program should take as input a message, a digital signature, and a public key, and output whether the signature is valid or not. Use SHA-256 as your hash function and RSA for asymmetric encryption.

Ensure that your system is secure against common attacks on digital signatures.

Concepts

  • Hash Functions
  • Digital Signatures
  • Public Key Cryptography

Constraints

  • Use a programming language of your choice
  • Implement both signing and verification processes
  • Provide clear documentation on how to use each program

Security Notes

  • Always securely generate and store private keys
  • Avoid using deprecated hash functions or encryption schemes
  • Be aware of timing attacks and ensure constant-time comparison when verifying signatures

Solutions

Java Solution

import java.security.*;
import java.util.Base64;

public class DigitalSignatureSystem {

    // Method to generate RSA key pair
    public static KeyPair generateRSAKeyPair() throws NoSuchAlgorithmException {
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
        keyGen.initialize(2048); // 2048 bits key size is generally recommended for security
        return keyGen.generateKeyPair();
    }

    // Method to sign a message with the private key
    public static String signMessage(String plainText, PrivateKey privateKey) throws Exception {
        Signature privateSignature = Signature.getInstance("SHA256withRSA");
        privateSignature.initSign(privateKey);
        privateSignature.update(plainText.getBytes());
        byte[] signatureBytes = privateSignature.sign();
        return Base64.getEncoder().encodeToString(signatureBytes); // encode in base 64 to make it readable
    }

    // Method to verify a message with the public key and signature
    public static boolean verifySignature(String plainText, String signature, PublicKey publicKey) throws Exception {
        Signature publicSignature = Signature.getInstance("SHA256withRSA");
        publicSignature.initVerify(publicKey);
        publicSignature.update(plainText.getBytes());
        byte[] signatureBytes = Base64.getDecoder().decode(signature); // decode from base 64
        return publicSignature.verify(signatureBytes);
    }

    public static void main(String[] args) {
        try {
            KeyPair keyPair = generateRSAKeyPair();
            PrivateKey privateKey = keyPair.getPrivate();
            PublicKey publicKey = keyPair.getPublic();

            String messageToSign = "Hello, secure world!";
            System.out.println("Original Message: \"" + messageToSign + "\"");

            String signature = signMessage(messageToSign, privateKey);
            System.out.println("Generated Signature: \"" + signature + "\"");

            boolean isVerified = verifySignature(messageToSign, signature, publicKey);
            System.out.println("Is the signature valid? " + (isVerified ? "Yes" : "No"));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

This Java solution implements a simple digital signature system using RSA for asymmetric cryptography and SHA-256 as the hash function.
The DigitalSignatureSystem class contains three main methods: generateRSAKeyPair, signMessage, and verifySignature. The generateRSAKeyPair method creates a new RSA key pair with a 2048-bit key size, which is considered secure for most applications. This method uses KeyPairGenerator to initialize the key generation process.
The signMessage method takes a plain text message and a private key as input. It creates a Signature object using the "SHA256withRSA" algorithm, initializes it with the private key, updates it with the message bytes, and then generates a digital signature. The generated signature is encoded in base 64 to make it readable and human-friendly.
The verifySignature method takes a plain text message, a base 64-encoded signature, and a public key as input. It creates another Signature object using the same algorithm, initializes it with the public key, updates it with the message bytes, decodes the signature from base 64, and then verifies if the signature is valid.
In the main method, we first generate an RSA key pair and extract the private and public keys. Then, we define a sample message to sign, call the signMessage method to create a digital signature, and finally call the verifySignature method to check if the signature is valid. If everything works correctly, it should output that the original message is signed and verified successfully.
This system follows best practices by using a secure key size for RSA (2048 bits), employing SHA-256 as the hash function, securely generating and storing keys within the program (in practice, keys should be stored in a secure keystore), and encoding signatures in base 64. Additionally, constant-time comparison is implicitly handled by the Java Signature class during verification to mitigate timing attacks.