Java Program for Naccache Stern Cryptosystem

Introduction

David Naccache and Jacques Stern published "A New Public Key Cryptosystem based on Higher Residues" at EUROCRYPT 1997 (final journal version 1998). Their construction is one of the few knapsack-based public-key schemes that resists all known attacks. Unlike RSA whose security rests on factoring, Naccache-Stern's security rests on the difficulty of the higher-residuosity problem: given a smooth modulus N (a product of small primes) and a value c, find the subset of prime residue classes whose product equals c mod N.

For Java learners, Naccache-Stern is a beautiful showcase of the Chinese Remainder Theorem in cryptography. The public key consists of N (a smooth modulus) and a vector of u_i values; the private key is just the factorization of N. Encryption is multiplication of selected u_i values; decryption is per-prime residue extraction.

What is the Naccache-Stern Cryptosystem?

Naccache-Stern is a public-key encryption scheme in the multiplicative knapsack family. The modulus N is a product of small primes p_1, p_2, ..., p_k (called a smooth number). For each prime p_i dividing N, a public element u_i is constructed via CRT to satisfy u_i congruent to s mod p_i and u_i congruent to 1 mod p_j for j not equal to i, where s is a random base coprime to N. Encryption of a k-bit message m = sum of m_i * 2^i is the product of u_i over all i with m_i = 1. Decryption requires the factorization of N: for each prime p_i, compute c mod p_i; if the result equals s mod p_i, then bit m_i = 1; otherwise m_i = 0.

The scheme is unique because the message space is exactly k bits where k is the number of primes in the factorization. Unlike RSA which is a one-to-one function on Z_N^*, Naccache-Stern is a one-to-one function on the k-bit binary message space. Its security reduces to the difficulty of recovering the factorization of N when N is smooth, which is conjecturally as hard as factoring any non-smooth number of the same size, given the smoothness does not leak information about the residue classes.

How Naccache-Stern Works - Step by Step

Step 1: Key generation. Pick k small primes p_1, ..., p_k whose product N = p_1 * ... * p_k is large enough to deter factoring. For the demo we use primes 3, 5, 7, 11 (so N = 1155 and k = 4 bits of message space). Pick a random base s coprime to N (we use s = 2). For each prime p_i, construct u_i via CRT such that u_i = s mod p_i and u_i = 1 mod p_j for j != i. The public key is (N, u_1, ..., u_k); the private key is the factorization {p_1, ..., p_k} and the base s.

Step 2: Encryption. Write the message m as a k-bit binary string m_{k-1} ... m_1 m_0. Compute c = product of u_i for all i with m_i = 1, all mod N. If all bits are 0, the ciphertext is 1. The encryption is deterministic (no randomizer), so two encryptions of the same m produce the same c.

Step 3: Decryption. For each prime p_i, compute c mod p_i. Because of the CRT construction, all u_j with j != i are 1 mod p_i, so c mod p_i = u_i^(m_i) mod p_i = s^(m_i) mod p_i. If c mod p_i equals s mod p_i, then m_i = 1; if it equals 1, then m_i = 0.

Step 4: Security argument. Without the factorization, the attacker sees only N and the u_i values. To decrypt, they would need to either factor N (which is conjecturally hard for a smooth N of the size used in practice) or solve the multiplicative knapsack instance directly, which is provably as hard as factoring in the random oracle model.

Java Program for Naccache Stern Cryptosystem

import java.math.BigInteger;
import java.util.Arrays;

public class NaccacheSternDemo {

    // Small primes for the knapsack (bit positions 0..3)
    private static final int[] PRIMES = {3, 5, 7, 11};
    private static final BigInteger N = BigInteger.valueOf(
        3 * 5 * 7 * 11); // 1155
    private static final BigInteger S = BigInteger.valueOf(2); // coprime to N

    // u_i = CRT: u_i = s mod p_i, u_i = 1 mod p_j for j != i
    private static final BigInteger[] U = buildU();

    private static BigInteger[] buildU() {
        BigInteger[] u = new BigInteger[PRIMES.length];
        for (int i = 0; i < PRIMES.length; i++) {
            u[i] = crtForPrime(i);
        }
        return u;
    }

    // Build x such that x = s mod p_target and x = 1 mod p_j (j != target)
    private static BigInteger crtForPrime(int target) {
        BigInteger result = BigInteger.ONE;
        BigInteger modulus = BigInteger.ONE;
        for (int i = 0; i < PRIMES.length; i++) {
            BigInteger p = BigInteger.valueOf(PRIMES[i]);
            BigInteger a = (i == target) ? S : BigInteger.ONE;
            // Find y = result + modulus * k where k = (a - result) * modInverse(modulus, p) mod p
            BigInteger diff = a.subtract(result.mod(p)).mod(p);
            BigInteger k = diff.multiply(modulus.modInverse(p)).mod(p);
            result = result.add(modulus.multiply(k));
            modulus = modulus.multiply(p);
        }
        return result.mod(N);
    }

    // Encrypt by multiplying u_i for each bit set in m
    public static BigInteger encrypt(int m) {
        BigInteger c = BigInteger.ONE;
        for (int i = 0; i < PRIMES.length; i++) {
            int bit = (m >> i) & 1;
            if (bit == 1) {
                c = c.multiply(U[i]).mod(N);
            }
        }
        return c;
    }

    // Decrypt: for each prime, check c mod p_i to recover bit i
    public static int decrypt(BigInteger c) {
        int m = 0;
        for (int i = 0; i < PRIMES.length; i++) {
            BigInteger p = BigInteger.valueOf(PRIMES[i]);
            BigInteger cModP = c.mod(p);
            BigInteger sModP = S.mod(p);
            if (cModP.equals(sModP)) {
                m |= (1 << i); // bit i = 1
            } else if (!cModP.equals(BigInteger.ONE)) {
                throw new IllegalStateException(
                    "corrupt ciphertext at prime " + p);
            }
        }
        return m;
    }

    public static void main(String[] args) {
        System.out.println("Setup: primes=" + Arrays.toString(PRIMES)
            + " N=" + N + " s=" + S);
        System.out.println("u values:");
        for (int i = 0; i < PRIMES.length; i++) {
            System.out.println("  u_" + i + " (for p=" + PRIMES[i]
                + ") = " + U[i]);
        }

        // Encrypt all 16 possible 4-bit messages and verify round-trip
        System.out.println("Encrypt-decrypt round trip:");
        for (int m = 0; m < 16; m++) {
            BigInteger c = encrypt(m);
            int d = decrypt(c);
            System.out.println("  m=" + m + " -> c=" + c
                + " -> decrypt=" + d);
        }

        // Detailed residue inspection for m=13
        BigInteger c = encrypt(13);
        System.out.println("Ciphertext c for m=13: " + c);
        for (int p : PRIMES) {
            System.out.println("  c mod " + p + " = "
                + c.mod(BigInteger.valueOf(p)));
        }
    }
}

Code Explanation - Line by Line

The constants PRIMES, N, S encode the demo group parameters. We use four small primes 3, 5, 7, 11 so that N = 1155 and the message space is exactly 4 bits (values 0 to 15). The base s = 2 is coprime to N. In production you would use hundreds of small primes so that N is thousands of bits long.

The buildU method constructs the public u_i values via CRT. For each prime p_i (the target), it computes the unique x mod N such that x = s mod p_i and x = 1 mod p_j for j != i. The crtForPrime method uses the standard iterative CRT construction: start with result = 1 mod 1, then for each prime in turn, find k such that result + modulus*k satisfies the next congruence, and update the modulus.

The encrypt method multiplies together all u_i values whose corresponding bit in m is set. Each u_i value is precomputed, so encryption is just k BigInteger multiplications mod N. The decrypt method extracts each bit by computing c mod p_i and comparing to s mod p_i (the case for bit = 1) or to 1 (the case for bit = 0).

The main method demonstrates three things: print the u values for inspection; encrypt and decrypt all 16 possible 4-bit messages to confirm the round trip; for m=13 (binary 1101), show the residue c mod p_i for each prime, demonstrating that bits are recoverable from residues.

Sample Input and Output

Setup: primes=[3, 5, 7, 11] N=1155 s=2
u values:
  u_0 (for p=3) = 386
  u_1 (for p=5) = 232
  u_2 (for p=7) = 331
  u_3 (for p=11) = 211
Encrypt-decrypt round trip:
  m=0 -> c=1 -> decrypt=0
  m=1 -> c=386 -> decrypt=1
  m=2 -> c=232 -> decrypt=2
  ...
  m=13 -> c=926 -> decrypt=13
  m=14 -> c=772 -> decrypt=14
  m=15 -> c=2 -> decrypt=15
Ciphertext c for m=13: 926
  c mod 3 = 2
  c mod 5 = 1
  c mod 7 = 2
  c mod 11 = 2

The output confirms that decryption extracts the original 4-bit message in all 16 cases. Note that m=15 (all bits set) encrypts to 2, which equals the base s, because the product of all u_i has residue s mod every prime and hence equals s mod N by CRT. The detailed residue inspection for m=13 shows c mod 3 = 2 (matching s mod 3, so bit 0 = 1), c mod 5 = 1 (so bit 1 = 0), c mod 7 = 2 (so bit 2 = 1), c mod 11 = 2 (so bit 3 = 1), giving binary 1101 = 13.

Common Mistakes to Avoid

1. Using primes so small that the resulting N is easy to factor by trial division. With N = 1155 the demo is trivially factored; production N must be at least 2048 bits with hundreds of small primes. Use NextProbablePrime or Miller-Rabin to generate the small primes.

2. Forgetting that the message space is exactly k bits. If you try to encrypt a message larger than 2^k - 1, the high bits are silently truncated. Always verify the message fits in k bits, or extend the prime list before encryption.

3. Picking s = 1 (the trivial element). With s = 1, every u_i is 1 mod every p_j, so all u_i = 1 mod N and the cryptosystem collapses to identity. Always pick s coprime to N and not equal to 1 mod any p_i.

4. Treating N as a fixed constant in production. The security of the scheme requires that the factorization of N remains secret. If the same N is published and someone factors it (which is conjecturally hard for smooth N of the right size, but not provably so), all messages encrypted under that N are revealed. Rotate N periodically.

Real-World Applications

Naccache-Stern has remained mostly an academic construction, but its design has influenced several real-world protocols. The idea of using CRT-constructed basis elements as a one-way function appears in lattice-based trapdoor functions and in some identity-based encryption schemes built on the Boneh-Franklin framework.

The higher-residuosity problem underlying Naccache-Stern is the same hardness assumption used in some zero-knowledge proof systems for proving properties of integer factorizations. The Benaloh cryptosystem uses a closely related residuosity assumption; both belong to the family of residuosity-based cryptosystems that occupied the literature between Goldwasser-Micali (1982) and Paillier (1999).

In privacy-preserving data mining, the small-message-space structure of Naccache-Stern is useful for encrypting bounded categorical attributes (e.g., disease codes, age brackets) and aggregating counts homomorphically. The deterministic nature of the encryption is suitable when the ciphertext is meant to be a unique identifier rather than a hidden value.

Academic prototypes for short-Payload public-key encryption (e.g., encrypting a 16-byte session key) use Naccache-Stern because the encryption operation is faster than RSA for very small messages and the ciphertext is compact. Production deployments prefer RSA-OAEP for backward compatibility and standardization, but Naccache-Stern remains a useful teaching example.

Conclusion

Naccache-Stern is the canonical example of a multiplicative knapsack cryptosystem built on the Chinese Remainder Theorem and the higher-residuosity problem. Our Java program demonstrated key generation via CRT, encryption as a multiplicative subset-sum, and decryption via per-prime residue extraction. Next study the Goldwasser-Micali bit-encryption scheme (the predecessor), the Paillier generalization to full homomorphism, and lattice-based knapsack cryptosystems that are conjectured post-quantum secure.