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