Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

Simple example of Diffie-Hellman-Merkle secure key exchange

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • Simple example of Diffie-Hellman-Merkle secure key exchange

    'This Powerbasic program is based on an example from a book called
    'THE CODE BOOK, by Simon Singh. I got my copy at Amazon, and I
    'recommend you get your copy now! It's the single most enjoyable
    'book I've read in 2001/2002. It combines amazing stories of the
    'history of cryptography (the codemakers) and cryptanalysis
    '(the codebreakers) with amazing algorithms and is a must read
    'for anyone who has even the slightest fascination with ciphers! :-)
    'ported to PB from textual descriptions by Wayne Diamond, January 2002

    Code:
    #COMPILE EXE
    #INCLUDE "win32api.inc"
     
    FUNCTION OneWayFunc(LongIn AS LONG) AS LONG
    ON ERROR RESUME NEXT
    '// The general one-way function is Y^x (mod P).
    '// Alive and Bob have chosen values for Y and P, and hence
    '// have agreed on the one-way function 7^x (mod 11)
    FUNCTION = (((7 ^ LongIn) MOD 11) MOD 11)
    END FUNCTION
      
    FUNCTION PBMAIN() AS LONG
    ON ERROR RESUME NEXT
    LOCAL A AS LONG, B AS LONG
    LOCAL A2 AS LONG, B2 AS LONG
    LOCAL DecryptKeyA AS LONG, DecryptKeyB AS LONG
    LOCAL Function1Way AS LONG
    'A = Alice, B = Bob
     
    'STAGE 1 - Alice and Bob choose a secret number.
    A = 3
    B = 6
     
    'STAGE 2 - Alice and Bob put their secret numbers into
    '          the one-way function.
    A2 = OneWayFunc(A)  ' = 2
    B2 = OneWayFunc(B)  ' = 4
      
    'STAGE 3 - Alice and Bob tell each other their STAGE2 numbers.
    'Ordinarily, this would be a crucial moment, because Alice and Bob are
    'exchanging information, and therefore this is an opportunity for Eve
    'to eavesdrop and find out the details of the information. However, it
    'turns out that Eve can listen in without it affecting the ultimate
    'security of the system. Alice and Bob could use the same telephone line
    'that they used to agree the values for Y and P, and Eve could intercept
    'the two numbers that are being exchanged, 2 and 4. However, these numbers
    'are not the key, which is why it doesn't matter if Eve knows them.
    '[no code required - imagine Alice and Bob simply telling each other their STAGE2 numbers.
      
    'STAGE 4 - Alice takes Bob's STAGE2 number (B2) and works out the result using the one-way function
    DecryptKeyB = (((B2 ^ A) MOD 11) MOD 11)
    'Bob takes Alice's STAGE2 number (A2) and works out the result using the one-way function
    DecryptKeyA = (((A2 ^ B) MOD 11) MOD 11)
     
    'Display the results...
    STDOUT "Alice has ended up with: " & STR$(DecryptKeyB)
    STDOUT "  Bob has ended up with: " & STR$(DecryptKeyA)
    'Miraculously, both Alice and Bob have ended up with the same key - 9.
    'They can now proceed with secure encryption, knowing that their key (9) is safe.
      
    WAITKEY$
    END FUNCTION
    For obvious reasons this demo uses small numbers. When implementing such a key exchange, all numbers should be made extremely high so that brute-force isn't viable
    Enjoy!


    ------------------


    [This message has been edited by Wayne Diamond (edited January 21, 2002).]
    -

  • #2
    Code:
    'Second example, not so many comments this time, slightly different way of looking at it.
      
    #COMPILE EXE
    #INCLUDE "win32api.inc"
     
    %Key1 = 7
    %Key2 = 11
    FUNCTION OneWayFunc(LongIn AS LONG) AS LONG
    ON ERROR RESUME NEXT
    FUNCTION = (((%Key1 ^ LongIn) MOD %Key2) MOD %Key2)
    END FUNCTION
     
    FUNCTION PBMAIN() AS LONG
    ON ERROR RESUME NEXT
    LOCAL A AS LONG, B AS LONG
    LOCAL A2 AS LONG, B2 AS LONG
    LOCAL DecryptKeyA AS LONG, DecryptKeyB AS LONG
    LOCAL Function1Way AS LONG
    A = 3               'PRIVATE KEY - only Alice ever knows this key 
    B = 6               'PRIVATE KEY - only Bob ever knows this key 
    A2 = OneWayFunc(A)  'PUBLIC KEY - Alice can give this key to anyone
    B2 = OneWayFunc(B)  'PUBLIC KEY - Bob can give this key to anyone
    STDOUT "Alice gives Bob her public key: " & STR$(A2)
    STDOUT "Bob gives Alice his public key: " & STR$(B2)
    DecryptKeyB = (((B2 ^ A) MOD %Key2) MOD %Key2)
    DecryptKeyA = (((A2 ^ B) MOD %Key2) MOD %Key2)
    STDOUT "Alice has ended up with decryption key: " & STR$(DecryptKeyB)
    STDOUT "  Bob has ended up with decryption key: " & STR$(DecryptKeyA)
    WAITKEY$
    END FUNCTION

    [This message has been edited by Wayne Diamond (edited January 21, 2002).]
    -

    Comment


    • #3
      Wayne, I rewrote your code a little bit. I don't think the double MOD operation is necessary. Don't think the second MOD does anything, from a mathematical point of view. Verify it with your calculator...
      I wrote this, using an internet document explaining Diffie-Hellman.
      BTW Bob and Alice are still there...
      All it needs now is large integers.... Working on it...
      Code:
      'Example of the Diffie-Hellman public key algorithm using small integers
      'This code is a modification of Wayne Diamond's example
      
      #COMPILE EXE
      #INCLUDE "win32api.inc"
      DECLARE SUB DEBUG (st$)
      $ConClose = "$CON:CLOSE"
      
      FUNCTION PBMAIN() AS LONG
      
      LOCAL A AS LONG, B AS LONG
      LOCAL A2 AS LONG, B2 AS LONG
      LOCAL DecryptKeyA AS LONG, DecryptKeyB AS LONG
      LOCAL mess AS STRING
      LOCAL ModulusPrime AS LONG, Generator AS LONG
      
      '====================================================
      'Do not choose values too high!! Otherwise you will get unpredictable results
      '====================================================
      
      'ModulusPrime: must be a large prime (not too large in this program...)
      ModulusPrime = 23
      'Generator   : a random number, must be less than 'ModulusPrime'
      Generator    = 16
      
      'A = Alice, B = Bob
      'STAGE 1 - Alice and Bob choose a secret number.
      A = 10   'random secret number, smaller than ModulusPrime-1
      B = 3   'random secret number, smaller than ModulusPrime-1
      
      'STAGE 2 - Alice and Bob calculate their public key
      A2 = (Generator ^ A) MOD ModulusPrime  'Alice's public key
      B2 = (Generator ^ B) MOD ModulusPrime  'Bob's public key
      debug STR$(Generator ^ A) & "<-- if this gets exponential, values are too high.."
      debug STR$(Generator ^ B) & "<-- if this gets exponential, values are too high.."
      debug "Alice's public key:" & STR$(A2)
      debug "  Bob's public key:" & STR$(B2)
      
      'STAGE 3 - Alice and Bob tell each other their public keys.
      'Ordinarily, this would be a crucial moment, because Alice and Bob are
      'exchanging information, and therefore this is an opportunity for Eve
      'to eavesdrop and find out the details of the information. However, it
      'turns out that Eve can listen in without it affecting the ultimate
      'security of the system. Alice and Bob could use the same telephone line
      'that they used to agree the values for Y and P, and Eve could intercept
      'the two numbers that are being exchanged, 2 and 4. However, these numbers
      'are not the key, which is why it doesn't matter if Eve knows them.
      '[no code required - imagine Alice and Bob simply telling each other their STAGE2 numbers.
      
      'STAGE 4 - Alice and Bob each calculate a common (secret) communication key using each others public keys
      DecryptKeyA = (B2 ^ A) MOD ModulusPrime 'Alice's communication key, calculated using her own private key and Bob's public key
      DecryptKeyB = (A2 ^ B) MOD ModulusPrime 'Bob's communication key, calculated using his own private key and Alice's public key
      debug "Common key:" & STR$(DecryptKeyA)
      debug "Common key:" & STR$(DecryptKeyB)
      
      'Display the results...
      mess =  "Alice has calculated this common key:" & STR$(DecryptKeyA) & $CRLF
      mess =  mess & "  Bob has calculated this common key:" & STR$(DecryptKeyB) & $CRLF
      IF DecryptKeyA <> DecryptKeyB THEN
          mess = mess & "DOOOHHH!! Keys didn't match! Error in program!"
      ELSE
          mess = mess & "These must be the same."
      END IF
      
      MSGBOX mess
      
      END FUNCTION
      'For obvious reasons this demo uses small numbers. When implementing such a key exchange, all numbers should be made extremely high so that brute-force isn't viable
      
      '==============================================================================
      'This routine is only used for debugging. Has no real function in the program, other than to display results.
      SUB DEBUG (st$)
          STATIC Hwnd&
          LOCAL szConsole AS ASCIIZ * 255
          IF Hwnd& = 0 THEN
             AllocConsole
             SetConsoleTitle "PBDLL Console"
             Hwnd& = GetStdHandle(%STD_OUTPUT_HANDLE)
             SetConsoleTextAttribute Hwnd&, %FOREGROUND_RED OR _
                                            %FOREGROUND_GREEN OR _
                                            %FOREGROUND_BLUE
          END IF
          IF Hwnd& > 0 THEN
             ' a magic word that close console
             IF st$=$ConClose THEN
                FreeConsole
                Hwnd& = 0
                EXIT SUB
             END IF
             szConsole = st$ & $CRLF
             WriteConsole Hwnd&,szConsole,LEN(szConsole),%NULL,%NULL
          END IF
      END SUB
      Kind regards
      Eddy


      ------------------
      mailto:raimundo4u@yahoo.comraimundo4u@yahoo.com</A>



      [This message has been edited by Eddy Van Esch (edited March 20, 2002).]
      Eddy

      Comment

      Working...
      X