Diffie-Hellman Key Exchange

General
1

I need to be able to perform a DH Key Exchange as part of an app I’m working on, that is to say your standard diffie-hellman (not elliptic curve).
i.e.
A = g^a mod p
B = g^b mod p
S = B^a mod p = A^b mod p
where g is the base (2), p is a large prime number, a and b are large private integers and S is the resulting shared secret

I note that Xojo’s Crypto module doesn’t implement any functions for this but the Crypto++ library which it uses does apparently support it. I wondered therefore, if it was possible through external API declares to call the necessary functions from the library within my app? Can anyone offer any advice in this regard?

Xojo doesn’t seem to support an integer type bigger than 64bit, otherwise I could just perform the maths directly.

NOTE: I’m trying to avoid using an external plugin for this solution

2

I know you said you don’t want a plug-in, but @Robert_Delaney ‘s fpPlugin is very good (and free!) and adds Big types that support extended precision. You might consider trying it: http://delaneyrm.com/fpPlugin.html

1 Like
3

Thanks
I gave it a try and I’ve managed to get what i wanted working for now. I didn’t want to bloat my project with large plugins but the size isn’t too bad so I can live with it for now.
It’s a shame more of these functions are not built-in to Xojo already but maybe in the future

1 Like
4

Try and perform your own Montgomery Multiplier function for the Elliptical side - Over 2 minutes with high optimization. It’s .02ms in C and 4ms in Python … We settled on Python.

5

I’m curious. Do you still have the Xojo code that you can post or share?

6

Let me check the CVS archive and I’ll get back to you.

1 Like
7

Apparently Andy never checked it in. I have the C and Python code, but his REAL Studio code is not there …

8

Can you share those? I want to see what I can do.

9

Or just point me in the direction of the right algorithm.

10

Hang on - I’ll put them into a DropBox folder.

11

Thanks. I can get that later, maybe tonight.

12

While waiting, I found this:

I translated it to this:

Public Function Mont(a As Integer, b As Integer, n As Integer) as Integer
  #if not DebugBuild
    #pragma BackgroundTasks false
    #pragma BoundsChecking false
    #pragma NilObjectChecking false
    #pragma StackOverflowChecking false
  #endif
  
  var bitLength as integer = 1
  var tester as integer = 2
  do
    if n < tester then
      bitLength = bitLength - 1
      exit
    end if

    bitLength = bitLength + 1
    tester = tester + tester
  loop
  
  var result as integer
  
  tester = 1
  for i as integer = 0 to bitLength
    var adder as integer = if( ( a and tester ) <> 0, 1, 0 )
    var q as integer = ( ( result + adder ) * b ) and 1
    result = ( result + q * b + q * n ) \ 2
    
    tester = tester + tester
  next
  
  return result mod n
End Function

This takes about 30 ms on the first pass, then around 1-2 ms on subsequent passes using the same values.

Edit: I forgot to mod the result.
Edit 2: “BackgroundTasks”, not “BreakOnExceptions”. Yeesh!

13

Ugh - sorry - meetings, meetings, and more meetings.

Ours is quite a bit more complex, but your numbers are definitely in the same realm as ours.

Oh, and what is this thing called “var”? Your new fancy coding confuses us caveman coders :smiley:

14

To be clear, the numbers I posted (which are actually better than posted because of my mistake with the pragma) are in the same realm as the old RS code, or the current Python code?

15

Our Python code. Our RB code was abysmal because we didn’t have a big number plugin back then.

16

How big a number (in bits) are we talking?

17

2048 bits

18

That’s… a big number.

I’m looking forward to seeing your current code.