In modern cryptography, digital signatures ensure the authenticity and integrity of a message. One of the most widely used techniques for digital signing is based on the RSA algorithm. This post will guide you through the basic concept of how RSA digital signatures work and provide a simple Java implementation to illustrate the signing and verification process.

What is an RSA Digital Signature?

An RSA Digital Signature is a cryptographic method where the sender signs the message using their private key, and the receiver verifies it using the sender’s public key. This ensures:

• The message is not altered during transit.
• The message truly comes from the claimed sender.

Here’s how it works conceptually:

1. The sender selects two large prime numbers p and q.
2. Computes N = p * q and phi = (p - 1)(q - 1).
3. Chooses a public exponent e such that 1 < e < phi and gcd(e, phi) = 1.
4. Computes the private key d = e^(-1) mod phi.
5. To sign a message m, the sender calculates the signature s = m^d mod N.
6. To verify, the receiver computes m' = s^e mod N and checks if m' == m.

Java Implementation

Here’s a basic Java program that demonstrates the concept:

import java.util.*;
import java.math.BigInteger;

public class ds {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger p, q, phi, p1, q1, e, m, m2, N, t, d;

        // Step 1: Accept two prime numbers 'p' and 'q'
        System.out.println("Enter values for p and q:");
        p = in.nextBigInteger();
        q = in.nextBigInteger();

        N = p.multiply(q); // N = p * q
        p1 = p.subtract(BigInteger.ONE);
        q1 = q.subtract(BigInteger.ONE);
        phi = p1.multiply(q1); // phi = (p-1)(q-1)

        // Step 2: Sender chooses public key 'e' and calculates private key 'd'
        System.out.println("At Sender's end");
        System.out.println("Enter sender's public key (e):");
        e = in.nextBigInteger();
        d = e.modInverse(phi); // d = e^(-1) mod phi

        // Step 3: Sender enters the message to be signed
        System.out.println("Enter Message to be signed:");
        m = in.nextBigInteger();
        t = m.modPow(d, N); // Signature: s = m^d mod N

        // Step 4: Receiver verifies the signature
        System.out.println("At Receiver's end");
        System.out.println("The received message with digital signature is: " + t);
        m2 = t.modPow(e, N); // Decryption: m' = s^e mod N
        System.out.println("The decrypted message is: " + m2);
    }
}

Sample Output

Below is a sample run of the program:

Enter values for p and q:
17
11
At Sender's end
Enter sender's public key (e):
7
Enter Message to be signed:
11
At Receiver's end
The received message with digital signature is: 88
The decrypted message is: 11

Explanation of Output

We chose p = 17, q = 11.
Then N = 17 * 11 = 187 and phi = (17-1)(11-1) = 160.

Sender chooses public key e = 7, which is coprime with phi.
Private key d = 7^(-1) mod 160 = 23.

To sign message m = 11:
Signature s = 11^23 mod 187 = 88.

Receiver receives signature 88, computes:
m' = 88^7 mod 187 = 11.

The original and decrypted messages match (m == m'), confirming the message’s authenticity.

This simple Java program demonstrates how RSA digital signatures work conceptually. While real-world applications use much larger keys and hashing algorithms (like SHA-256) for added security, this example offers a foundational understanding of how digital signatures are generated and verified using RSA.