I’m trying to implement the Diffie-Hellman key exchange algorithm to use for end-to-end encryption in Roblox lua. However I have run into an important issue when it comes to generating the public keys between the two parties that are supposed to be send over the server in between.
More specifically the key exchange is supposed to happen the following way:
A known prime p and generator g are used. This step is easy, all I had to do is copy them from the RFC 3526 2048-bit MODP Group, in this case g is the number 2 and p(the prime and also a safe prime) is the one mentioned in hex on the website(2048-bit/256-byte prime).
Both parties create a random 256-bit integer private key. This is also easy since we just need to generate 32 random bytes(values between 0 and 255), making those truly random is an issue of its own but this isn’t what this post is about.
Both parties compute the public keys to send over the server to each other, as g^a mod p where a is their private key, however, this is where the actual issue appears, since Roblox doesn’t provide a built in way to calculate such astronomically large numbers in a precise manner. So the question is how should I approach this? I’ve heard there’re community libraries for large numbers, for example BigInteger, can those libraries fit this purpose? Or they lack precision? How should I perform such a calculation despite Roblox limitations?
The last part involves both parties sending the calculated public keys over to each other and then calculating a shared secret by combining them with their private keys, the math here is the same as above, so technically if I solve the above problem I can also solve this one.
In short, I want to figure out a way to calculate something like 2^x mod p in a precise manner. Where x can be any value between zero and 2^256, and p is a huge prime that is referenced in the RFC document linked.
UPDATE: I’m still working on the problem and decided to implement the operations needed for the task myself. However interestingly enough it didn’t take me long to realize that my initial approach of flipping each bit one by one would need a loop that performs 2^256 iterations, which would take longer than the age of the universe to complete. Then I remembered that the Roblox VM isn’t a CPU and I can get away with performing the same operations on larger numbers as long as I respect the related symmetries, a number I found perfectly fit for this is 2^32. This is because numbers up to 2^32 can be represented 100% accurately and it also divides the other powers of two I care about(in this case 256 and 2048). After that I noticed that lua has an entire library for doing funny things with such numbers named bit32, which made me think that I’m kind of re-inventing the wheel while dealing with this.
Anyways going through the weird bit by bit step helped me because now I have pinpointed down the exact logic and calculations needed between said numbers/bytes, so the problem is now much easier to tackle.
I will probably re-update this post once I have a solution or I’m very close to it.
Managed to get the first half of it working(participant one generating their private and public keys to send over the untrusted channel) despite lua number limitations:
Basically what I had to do is create my own numbering system that is an array of normal lua numbers in base 2^24 and represents a huge precise number I can do calculations on. Then to reduce the amount of bytes/array positions needed I stacked two algorithms together, the modular exponentiation and modular multiplication algorithms. That way by doing the modulo steps one by one I was able to avoid dealing with numbers larger than my initial ones(because powers get broken down to multiplications and multiplications to additions, additions can only double the final result/move it one bit since both numbers being added together are of same size). Lastly what I had to do is implement many operations needed for the task myself by copying the algorithms used to multiply, divide, add and subtract numbers in school. But by instead of having a number bigger than 10 with digits between 0 and 9 I have a number bigger than 2^24 with digits between 0 and 2^24-1.
The test message you see being printed on the output is the iterations of the modular exponentiation function, the max iterations according to my knowledge are 256, since I’m using 256 bits for the randomized private key.
Currently the algorithm runs entirely on my custom numbering system without any external libraries attached on it(initially I was experimenting by writing code in python and using a Roblox BigNum library for help) and it takes around 20 seconds to run. This is still heavily unoptimized and I bet I can bring down the execution time by a lot.
