ElGamal Public Key Cryptosystem

Use the Galois field array function, gf, to implement an ElGamal public key cryptosystem.

Key Generation

Define the polynomial degree, m.

m = 15;
q = 2^m;

Find a primitive polynomial and group generator. Set the random number generator seed. Check to confirm g is primitive, but for the seed 123456, the first g selected is primitive.

poly = primpoly(m);

 
Primitive polynomial(s) = 
 
D^15+D^1+1

primeFactors = unique(factor(2^m-1));
rng(123456); % for this seed, first g selected is primitive
g   = gf(randi(q-1), m, poly)

 
g = GF(2^15) array. Primitive polynomial = D^15+D+1 (32771 decimal)
 
Array elements = 
 
   4161

while ~isprimitive(minpol(g))
    g   = gf(randi(q-1), m, poly)
end

Construct private and public keys.

privateKey = 12;
publicKey = {g,g^privateKey,poly};

Encryption

Create and display the original message.

text = ['The Fourier transform decomposes a function of time (a signal)' newline ...
    'into the frequencies that make it up, in a way similar to how a' newline ...
    'musical chord can be expressed as the amplitude (or loudness) of' newline ...
    'its constituent notes.'];
disp(text);

The Fourier transform decomposes a function of time (a signal)
into the frequencies that make it up, in a way similar to how a
musical chord can be expressed as the amplitude (or loudness) of
its constituent notes.

Convert the message to binary and group them every m bits. The message uses ASCII characters. Since the ASCII table has 128 characters, seven bits per character is sufficient.

bitsPerChar = 7;
binMsg = int2bit(int8(text'),bitsPerChar);
numPaddedBits = m - mod(numel(binMsg),m);
if numPaddedBits == m
    numPaddedBits = 0;
end
binMsg = [binMsg; zeros(numPaddedBits,1)];
textToEncrypt = bit2int(binMsg,m);

Encrypt the original message.

cipherText = gf(zeros(length(textToEncrypt),2),m,poly);

for i = 1:length(textToEncrypt)
    k = randi([1 2^m-2]);
    cipherText(i,:) = [publicKey{1}^k, ...
        gf(textToEncrypt(i),m,poly)*publicKey{2}^k];
end

Display the encrypted message.

tmp = cipherText.x;
%disp(de2char(tmp(:,2),bitsPerChar,m));

Decryption

Decrypt the encrypted original message.

decipherText = gf(zeros(size(cipherText,1),1),m,poly);
for i = 1:size(cipherText,1)
    decipherText(i) = cipherText(i,2) * cipherText(i,1)^(-privateKey);
end

Display the decrypted message.

disp(de2char(decipherText.x,bitsPerChar,m));

The Fourier transform decomposes a function of time (a signal)
into the frequencies that make it up, in a way similar to how a
musical chord can be expressed as the amplitude (or loudness) of
its constituent notes.

Supporting Function

de2char converts the bits to char messages.

function text = de2char(msg,bitsPerChar,m)
binDecipherText = int2bit(msg,m);
text = char(bit2int(binDecipherText(1:end-mod(numel(binDecipherText), ...
    bitsPerChar)),bitsPerChar))';
end