Large Prime Numbers

[BinaryBrother]

I'm working on a Diffie Hellman UDF for AutoIt and have ran into some of AutoIt's string and arithmetic limitations, I think.

The function below actually works for generating a Diffie Hellman Public Key.

Func _DiffieHellman_GeneratePublicKey($pPrime, $pGenerator, $pSecret)
    Local $lReturn
    $lReturn = Mod($pGenerator ^ $pSecret, $pPrime)
    If $lReturn=="-1.#IND" Then Return SetError(1,0,0)
    Return $lReturn
EndFunc

That was a lot easier than I thought it would be! However... Upon throwing a 300 digit prime into that function, it returns "-1.#IND".

I extensively tested that the function works with values like Prime=23, Generator=5, and Secret=8... So that leads me to believe that the size of the prime has something to do with the failure.

Thanks for your time! ^.^

[jchd]

You need the BigNum UDF and the PowerMod function as I proposed here.

As an aside, methods to obtain a Sophie Germain prime are AFAIK not deterministic in complexity, you have to rely on chance an patience (vocal pun intended) but in practice you don't have to wait too much, given fast library. Since the BigNum.au3 UDF uses strings of ASCII digits to store numbers and compute results, don't expect too much out of it and regard it as an example possible implementation.

Note that D-H doesn't need a "safe" (SG) prime; it's just better for security against a strong attacker. So insisting on SG primes may (is) overkill for you, at least in AutoIt.

Edited May 25, 2015 by jchd

[BinaryBrother]

With your BigNum UDF, the calculation with a 550 digit prime, a 100 digit random number, and a generator of 5, it takes about 3 full minutes to calculate the private key...

But... It works.

Seeing the situation, now... I'm thinking about trying to figure out OpenSSL's command-line utility for generating DH keys.

[jchd]

BigNum isn't mine, at all. All I did was to add the PowerMod function that was lacking in the thread I pointed to.

3 minutes isn't so bad considering that everything is computed from strings of digits with a slow interpretor like AutoIt. Of course you'll need a fast arbitrary precision arithmetic library to speed that up to some acceptable level. Yet AutoIt and BigNum can be used for some cryptographic primitives tutorial, e.g. for demonstrating how D-H or RSA work (with smallish numbers).

[BinaryBrother]

Oh, it functions well and bridges a clear gap in AutoIt's ability to handle larger numbers! It's definitely a masterpiece and a very good suggestion! The poor performance is perfectly understandable, as it pushes AutoIt beyond its technical limitation.

It will become a permanent addition to my UDF collection as I do run into issues, every once in a while, where I just barely breach an AutoIt variable length or attempt to compute a number slightly too large and have to figure out another way to get around something. Not that I prefer AutoIt when dealing with stuff like this, it's just that 85% of the program is already built, I was just coming back to add security!

I like to keep everything native, but I'm not above stdout use, DLLCall, or assembly tricks. ;P

Also, I just found this. http://factordb.com/listtype.php?t=4&mindig=350&perpage=5000&start=0&download=1 <--- 5000 primes starting at 350 digits.

http://factordb.com/listtype.php?t=4&mindig=300&perpage=5&start=0

The above link is the 'interface'. ^.^

[jchd]

5000 primes starting at 350 digits

And then? Just ask if you need more, there is ample supply! (<-- read the other post I just made)