# 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 to produce a repeatable result.

```poly = primpoly(m,'nodisplay'); primeFactors = unique(factor(2^m-1)); rng(123456); while 1 g = gf(randi([1,q-1]),m,poly); isPrimitive = true; for i = 1:length(primeFactors) if g^((q-1)/primeFactors(i)) == gf(1,m,poly) isPrimitive = false; break; end end if isPrimitive break; end 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));```
```vTchba~*TzEC> *o_c;a5 vS>Do7]{B#wDc0`YCDVxV]:FC0|o| ],7 S)d/uW ]A=]T sKX+q3K&q ex_>f=C_gZ"*slX=N&\$~*[Xh+R[<5:(NpO6 8+@/)9sBm &is#Z<DN`Qo~?GaOFIzYA~a+Lygzv?l ```

### 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```