BinaryBrother

Large Prime Numbers

6 posts in this topic

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! ^.^

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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).


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

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'. ^.^

Share this post


Link to post
Share on other sites

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)

1 person likes this

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now