ElGamal, Big Integers And PowerShell
We had an excellent conference this week on our campus [here]. As part of my presentation I outlined the creation of a prime number which contains a whole sequence of nines:
And for this, I used PowerShell on my Macbook. Why? Well, PowerShell is pretty good with large integer values, whereas Python can struggle with overflows, and so on. At its core is the strength of the .NET framework, and which can be ported onto most platforms (including Microsoft Windows, Mac OSX and Linux). It is also easy to port a compiled C# program into a PowerShell scripted program.
So, let’s push PowerShell a little and get it to handle the mighty ElGamal encryption method. In elliptic curves, we have integer values which can be 256 bits, whereas in discrete log methods we often use values which are greater than 1,024 bits. As our integer values in programs only go up to 64 bits, we need another way of representing our values, and that’s where Big Integers come in.
ElGamal
Initially Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y which is:
