Java Program for McEliece Code Based Cryptosystem

Introduction

Robert McEliece published "A Public-Key Cryptosystem Based on Algebraic Coding Theory" in 1978 in the JPL DSN Progress Report, the same year RSA appeared. The McEliece cryptosystem was the first code-based public-key encryption scheme and the first practical alternative to number-theoretic public-key cryptography. McEliece's insight was that decoding a random linear code is NP-hard in general, but decoding a specific structured code (a binary Goppa code) can be done efficiently; by hiding the structure of the Goppa code behind a random-looking generator matrix, the public key looks like a random code that is hard to decode, while the private key allows efficient decoding.

For Java learners, McEliece is the cleanest example of code-based cryptography. The whole scheme fits in roughly 150 lines of Java using only integer matrix arithmetic over GF(2). It is also the only post-quantum candidate from the original 1970s wave of cryptography: McEliece with binary Goppa codes has resisted 47 years of cryptanalysis, and the Classic McEliece submission to NIST (round 4 alternate) is essentially the original 1978 construction with updated parameters.

What is McEliece Cryptosystem?

The McEliece cryptosystem is a public-key encryption scheme in the code-based family. Unlike RSA (whose hardness rests on factoring) or NTRU (whose hardness rests on the shortest vector problem in lattices), McEliece's hardness rests on the syndrome decoding problem: given a random binary matrix H of size (n-k) x n and a syndrome s, find a binary vector e of weight t such that H * e^T = s^T. This problem is provably NP-hard in the worst case for random matrices, and is conjectured hard on average.

The scheme exploits the gap between general decoding (hard) and structured decoding (easy). A binary Goppa code G of length n = 2^m and dimension k = n - m*t can correct up to t errors using the Berlekamp-Massey algorithm in O(n^2) operations. The public key is a scrambled version G_pub = S * G * P of the Goppa generator matrix, where S is a random invertible k x k matrix over GF(2) and P is a random n x n permutation matrix. The scrambling S * G * P produces a matrix that looks random (the Goppa structure is hidden), so the public key appears to define a generic random code that is hard to decode. The private key (S, G, P) allows the legitimate decryptor to undo the scrambling and use the Goppa decoder.

How McEliece Works - Step by Step

Step 1: Pick code parameters. For Classic McEliece the recommended parameter set is m = 12, n = 4096, k = 3488, t = 128 (corresponding to the 8192128-bit security level). For our demo we use the [7, 4, 3] Hamming code (m = 3, n = 7, k = 4, t = 1) which can correct exactly 1 error per codeword. The Hamming code is used here as a stand-in for the Goppa code because both have an efficient syndrome decoder; the scheme's security analysis would be different with Hamming codes (which are not Goppa codes), but the encryption and decryption mechanics are identical.

Step 2: Key generation. Generate the systematic generator matrix G of size k x n in the form [I_k | A] where I_k is the k x k identity and A is k x (n-k). Generate a random invertible k x k matrix S over GF(2) and a random n x n permutation matrix P. Compute the public generator G_pub = S * G * P. The public key is G_pub; the private key is the tuple (S, G, P) along with the decoder for the underlying code.

Step 3: Encryption. To encrypt a k-bit message m, sample a random n-bit error vector e of weight exactly t (in our demo t = 1, so e has a single 1 in a random position). Compute the ciphertext c = m * G_pub + e mod 2. The ciphertext is n bits long.

Step 4: Decryption. Compute c * P^-1 = m * G * P * P^-1 + e * P^-1 = m * G + e * P^-1. The permuted error e * P^-1 still has weight t. Apply the syndrome decoder to recover m * G from the noisy codeword m * G + (e * P^-1). Extract m * S as the first k bits of the decoded codeword (since G is systematic, the first k bits of m * G equal m * S). Multiply by S^-1 to recover m.

Java Program for McEliece Cryptosystem

import java.util.Arrays;

public class McElieceDemo {

    static final int N = 7, K = 4, T = 1;

    // Systematic [7,4,3] Hamming generator G = [I_4 | A]
    static int[][] G = {
        {1, 0, 0, 0, 1, 1, 0},
        {0, 1, 0, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1, 1},
        {0, 0, 0, 1, 1, 1, 1}
    };

    // Parity check H = [A^T | I_3] - used by the syndrome decoder
    static int[][] H = {
        {1, 1, 0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0, 1, 0},
        {0, 1, 1, 1, 0, 0, 1}
    };

    // Scrambling matrix S (4x4 invertible over GF(2))
    static int[][] S = {
        {1, 1, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 1, 0},
        {0, 1, 0, 1}
    };

    // Permutation P (7x7): swap columns 0 and 4
    static int[][] P;

    static {
        P = new int[N][N];
        for (int i = 0; i < N; i++) P[i][i] = 1;
        for (int i = 0; i < N; i++) {
            int t = P[i][0];
            P[i][0] = P[i][4];
            P[i][4] = t;
        }
    }

    // Matrix-matrix multiplication mod m
    static int[][] mulMat(int[][] A, int[][] B, int mod) {
        int a = A.length, b = B[0].length, k = B.length;
        int[][] C = new int[a][b];
        for (int i = 0; i < a; i++)
            for (int j = 0; j < b; j++) {
                int s = 0;
                for (int l = 0; l < k; l++) s = (s + A[i][l] * B[l][j]) % mod;
                C[i][j] = (s + mod) % mod;
            }
        return C;
    }

    // Row-vector times matrix: v * M (returns row vector)
    static int[] mulVec(int[] v, int[][] M, int mod) {
        int[] out = new int[M[0].length];
        for (int j = 0; j < out.length; j++) {
            int s = 0;
            for (int i = 0; i < v.length; i++) s = (s + v[i] * M[i][j]) % mod;
            out[j] = (s + mod) % mod;
        }
        return out;
    }

    static int[] addVec(int[] a, int[] b, int mod) {
        int[] c = new int[a.length];
        for (int i = 0; i < a.length; i++) c[i] = (a[i] + b[i]) % mod;
        return c;
    }

    static int[][] transpose(int[][] M) {
        int[][] T = new int[M[0].length][M.length];
        for (int i = 0; i < M.length; i++)
            for (int j = 0; j < M[0].length; j++)
                T[j][i] = M[i][j];
        return T;
    }

    // Inverse of a square matrix mod 2 via Gauss-Jordan elimination
    static int[][] inverseMod2(int[][] A) {
        int n = A.length;
        int[][] aug = new int[n][2 * n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) aug[i][j] = A[i][j];
            aug[i][n + i] = 1;
        }
        for (int col = 0; col < n; col++) {
            int pivot = -1;
            for (int r = col; r < n; r++) {
                if (aug[r][col] == 1) { pivot = r; break; }
            }
            if (pivot == -1) throw new RuntimeException("singular matrix");
            int[] tmp = aug[col]; aug[col] = aug[pivot]; aug[pivot] = tmp;
            for (int r = 0; r < n; r++) {
                if (r != col && aug[r][col] == 1) {
                    for (int j = 0; j < 2 * n; j++) {
                        aug[r][j] ^= aug[col][j];
                    }
                }
            }
        }
        int[][] inv = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) inv[i][j] = aug[i][n + j];
        return inv;
    }

    // Hamming syndrome decoder: returns the input with one error corrected
    static int[] decode(int[] c) {
        int[] s = new int[3];
        for (int i = 0; i < 3; i++) {
            int sum = 0;
            for (int j = 0; j < 7; j++) sum ^= H[i][j] & c[j];
            s[i] = sum;
        }
        int errPos = -1;
        for (int j = 0; j < 7; j++) {
            boolean match = true;
            for (int i = 0; i < 3; i++) {
                if (H[i][j] != s[i]) { match = false; break; }
            }
            if (match) { errPos = j; break; }
        }
        int[] corrected = Arrays.copyOf(c, c.length);
        if (errPos >= 0) corrected[errPos] ^= 1;
        return corrected;
    }

    public static void main(String[] args) {
        // Public key: G' = S * G * P (mod 2)
        int[][] Gpub = mulMat(mulMat(S, G, 2), P, 2);
        int[][] Sinv = inverseMod2(S);
        int[][] Pinv = transpose(P);   // permutation inverse = transpose

        System.out.println("McEliece params: n=" + N + " k=" + K + " t=" + T);
        System.out.println("Public key G' = S*G*P (4x7 over GF(2)):");
        for (int i = 0; i < 4; i++) {
            System.out.println("  row " + i + ": " + Arrays.toString(Gpub[i]));
        }

        // Encrypt m = (1, 0, 1, 0) with one error at position 5
        int[] m = {1, 0, 1, 0};
        int[] e = {0, 0, 0, 0, 0, 1, 0};
        int[] c = addVec(mulVec(m, Gpub, 2), e, 2);

        System.out.println("Message m = " + Arrays.toString(m));
        System.out.println("Error  e = " + Arrays.toString(e));
        System.out.println("Cipher c = m*G' + e mod 2 = " + Arrays.toString(c));

        // Decrypt
        int[] cP = mulVec(c, Pinv, 2);             // c * P^-1
        int[] decoded = decode(cP);                 // remove one error
        int[] mS = new int[4];
        for (int i = 0; i < 4; i++) mS[i] = decoded[i];  // first k bits = m*S
        int[] mRec = mulVec(mS, Sinv, 2);            // m = m*S * S^-1

        System.out.println("c*P^-1   = " + Arrays.toString(cP));
        System.out.println("Decoded  = " + Arrays.toString(decoded));
        System.out.println("m*S      = " + Arrays.toString(mS));
        System.out.println("Recovered m = " + Arrays.toString(mRec));
    }
}

Code Explanation - Line by Line

The matrices G, H, S, P encode the system parameters. G is the systematic generator of the [7, 4, 3] Hamming code in the form [I_4 | A] where A is the 4x3 redundancy block. H is the matching parity check matrix [A^T | I_3] of size 3x7; each column of H is the binary representation of a unique number from 1 to 7 (modulo a column ordering), which is the structure that makes Hamming syndrome decoding work.

The static initializer block builds P as the identity matrix with columns 0 and 4 swapped, which is a valid permutation matrix. The transpose function is overloaded for any rectangular matrix and is used both to compute P^-1 = P^T (permutation matrices are orthogonal) and to build H^T when needed.

The inverseMod2 method computes the inverse of a matrix over GF(2) using Gauss-Jordan elimination on the augmented matrix [A | I]. The XOR-elimination step (aug[r][j] ^= aug[col][j]) works because addition and subtraction are identical in GF(2): both are XOR. After the algorithm completes, the right half of the augmented matrix contains A^-1.

The decode method implements the syndrome decoder for the Hamming code. It computes the syndrome s = H * c^T mod 2 (a 3-bit vector), then searches for the column of H that matches s. The matching column index tells us the error position; flipping that bit corrects the codeword. With at most one error, this decoder always succeeds. The main method runs the full scheme end to end: key generation, encryption with one error, and decryption via P-inverse multiplication, syndrome decoding, m*S extraction, and S-inverse multiplication.

Sample Input and Output

McEliece params: n=7 k=4 t=1
Public key G' = S*G*P (4x7 over GF(2)):
  row 0: [1, 1, 0, 1, 1, 0, 0]
  row 1: [1, 1, 1, 0, 0, 1, 0]
  row 2: [1, 0, 1, 0, 1, 0, 1]
  row 3: [0, 1, 0, 1, 0, 1, 0]
Message m = [1, 0, 1, 0]
Error  e = [0, 0, 0, 0, 0, 1, 0]
Cipher c = m*G' + e mod 2 = [0, 1, 1, 1, 0, 1, 1]
c*P^-1   = [0, 1, 1, 1, 0, 1, 1]
Decoded  = [0, 1, 1, 1, 0, 0, 1]
m*S      = [0, 1, 1, 1]
Recovered m = [1, 0, 1, 0]

The output confirms the full McEliece round trip. The ciphertext c = m * G' + e differs from m * G' in exactly one bit (position 5). After multiplying by P^-1, the error moves to a new position (here the swap of 0 and 4 means position 5 is unaffected, so the error is still at position 5). The syndrome decoder corrects it, yielding a clean codeword m * S * G whose first 4 bits equal m * S. Multiplying by S^-1 recovers the original message m exactly.

Common Mistakes to Avoid

1. Choosing an error weight that exceeds the code's correction capacity. The Hamming [7, 4, 3] code can correct exactly 1 error. If you accidentally add 2 errors to the ciphertext, the decoder might silently produce the wrong codeword (it would treat the second error as a single-bit error in a different position). Production McEliece uses Goppa codes with t = 128 or 256, but the same constraint applies: the error weight must be exactly t, never more.

2. Forgetting that P^-1 = P^T for permutation matrices. Some textbooks derive the inverse of P by tracing where each position maps, but the cleaner approach is to note that permutation matrices are orthogonal: P * P^T = I. Computing the inverse via Gauss-Jordan would still work but is overkill for permutation matrices and is a common source of bugs.

3. Using a non-systematic G matrix. The decryption step that extracts m * S from the first k bits of the decoded codeword relies on G being in systematic form [I_k | A]. If G is in random form, the first k bits of m * S * G do not equal m * S, and you would need to solve a linear system to recover m * S, which is much slower.

4. Confusing matrix order in multiplication. McEliece uses row-vector times matrix notation: c = m * G_pub + e where m is a row vector. If you accidentally transpose and compute G_pub * m, the dimensions match only if G is square, and the cryptographic correctness breaks. The order m * G_pub is the standard convention in coding theory and must be respected throughout.

Real-World Applications

Classic McEliece (Bernstein, Chou, Lange, von Maurich, Persichetti, Piesse, Sendrier 2017) was a round-4 alternate in the NIST Post-Quantum Cryptography standardization. Classic McEliece uses binary Goppa codes with parameters m = 12, n = 4096, k = 3488, t = 128 (the 8192128 parameter set). The public key is 8 MB and the ciphertext is 194 bytes; the scheme is favored for long-term-quantum-safe key establishment where large public keys can be distributed out of band (e.g., committed to root certificate stores).

The German Federal Office for Information Security (BSI) recommends Classic McEliece as the preferred post-quantum key-establishment mechanism for long-term-quantum-safe document signing, because the scheme has 47 years of cryptanalysis history with no weakening and a tight reduction to a provably NP-hard problem (syndrome decoding of random codes).

The Post-Quantum Cryptography Study Group of the European Telecommunications Standards Institute (ETSI) includes Classic McEliece in its quantum-safe VPN trials, where the large public key is distributed as part of a pre-shared key ceremony rather than transmitted in every handshake.

Academic prototypes such as micro-McEliece by the Bochum Embedded Security group have demonstrated McEliece keypair generation and decryption on Cortex-M4 microcontrollers in under 200 ms, showing the scheme is feasible for IoT form factors despite its large public-key size.

Conclusion

McEliece is the oldest post-quantum public-key scheme and the only one of the original 1978 wave that survives unchanged into 2024. Our Java program demonstrated systematic generator matrices, GF(2) matrix operations, syndrome decoding, and the S-G-P scrambling pipeline. Next, study binary Goppa codes and the Berlekamp-Massey algorithm (which the real Classic McEliece uses instead of our Hamming stand-in), the Niederreiter variant which uses a parity-check matrix as the public key (smaller public key, faster decryption), and the BIKE and HQC code-based KEMs which use quasi-cyclic codes instead of Goppa codes for smaller public keys.