Diffie-Hellman Key Agreement Protocol

2004-06-17 SRIV The Diffie-Hellman key agreement protocol (also called exponential key agreement) was developed by Diffie and Hellman in 1976. The protocol allows two users to exchange a secret key over an insecure medium without any prior secrets.

Because the numbers calculated in the program are larger than what stock tcl can handle, you must load a bignum extension. For a simple pure tcl demonstration, I chose to use the MPA extension to handle the large integers. This operates relatively slow, so keep your numbers small, perhaps around 4 digits maximum.

You would typically run this program on two separate computers, although for testing just run it two times on the same computer.

  #Can be any prime number  
  set prime_num 571
  #Has to be a number that is less than prime_num, typically small for speed
  set number 3

  puts -nonewline "Enter a secret number:< "
  flush stdout
  gets stdin private_val

  #Calculate public value 3 ^ $private_val mod $prime_num
  # Sarnold change : use powmod which does it faster than calling pow and then mod
  # SRIV changed it back, as its just for a simple demo designed NOT to use any extensions
  set        public_val [expr $number ^ $private_val % $prime_num]
  puts "This is a public value that you send to your partner site:> $public_val"

  puts -nonewline "Enter the public value that you received from your partner site:< "
  flush stdout
  gets stdin public_val

  #Calculate your common key value $public_val ^ $private_val % $prime_num
  set        common_val [expr $public_val ^ $private_val % $prime_num]

  puts "Your commmon key value to use for encryption is:> $common_val"

Sample results from two instances

Machine #1:

 Enter a secret number:< 123
 This is a public value that you send to your partner site:> 343
 Enter the public value that you received from your partner site:< 217
 Your commmon key value to use for encryption is:> 277

Machine #2:

 Enter a secret number:< 321
 This is a public value that you send to your partner site:> 217
 Enter the public value that you received from your partner site:< 343
 Your commmon key value to use for encryption is:> 277

Note how both machines derive a common number, 277, without revealing enough information to actually calculate that common number.

To use this method for the exchange of real cryptographic keys, you must use larger numbers. Here's an example using the bignum extension, which is ultra fast at calulating these formulas with even 2040 bit numbers.

  lappend auto_path lib
  package require bignum

  #Can be any prime number  
  set prime_num 12745216229761186769575009943944198619149164746831579719941140425076456621824834322853258804883232842877311723249782818608677050956745409379781245497526069657222703636504651898833151008222772087491045206203033063108075098874712912417029101508315117935752962862335062591404043092163187352352197487303798807791605274487594646923

  #Has to be a number that is less than prime_num, typically small for speed
  set number 3

  puts "Enter a secret number:< "
  gets stdin private_val

  #Calculate public value 3 ^ $private_val mod $prime_num
  set        public_val [bigint::powm $number $private_val $prime_num]
  puts "This is a public value that you send to your partner site:>\n$public_val"

  puts -nonewline "Enter the public value that you received from your partner site:<\n"
  gets stdin public_val

  #Calculate your common key value $public_val ^ $private_val % $prime_num
  set        common_val [bigint::powm $public_val $private_val $prime_num]

  puts "Your commmon key value to use for encryption is:>\n$common_val"

Sample results from two instances

Machine #1:

 Enter a secret number:< 
 12345678901234567890
 This is a public value that you send to your partner site:>
 8573801149397668110751249248820628833719384071044245703672658941317816299449437242214741304057956802075207785420370066561696671584641294418041784405376723453020168911779292942945044617215237668186882455401684481591575658277387779989149505295821307742282002873630169402186945322119506321698990885141675839935145175604089914334
 Enter the public value that you received from your partner site:<
 5909205313535379180970361338677738241264107559742899050944438227943819950978988901324262967853141283495777940436593929333243287431334572267347054569630915878830144869488696556346209305791549400800040756239221780289105122749435098962277884943418744964574897032846053463613793874683208771065687008866458799864728494898095277896
 Your commmon key value to use for encryption is:>
 1569518947138460411067304170198679282348857619571437028846096736471119975333812334789462297104945589997284133708250277389331391382934079348500529494250621935846456061836590159765805069268649277993356664316144128659964751473179066727259024414399365682038439746355679194474137148293365593344278579893004665198741676727086051559

Machine #2:

 Enter a secret number:< 
 98765432109876543210
 This is a public value that you send to your partner site:>
 5909205313535379180970361338677738241264107559742899050944438227943819950978988901324262967853141283495777940436593929333243287431334572267347054569630915878830144869488696556346209305791549400800040756239221780289105122749435098962277884943418744964574897032846053463613793874683208771065687008866458799864728494898095277896
 Enter the public value that you received from your partner site:<
 8573801149397668110751249248820628833719384071044245703672658941317816299449437242214741304057956802075207785420370066561696671584641294418041784405376723453020168911779292942945044617215237668186882455401684481591575658277387779989149505295821307742282002873630169402186945322119506321698990885141675839935145175604089914334
 Your commmon key value to use for encryption is:>
 1569518947138460411067304170198679282348857619571437028846096736471119975333812334789462297104945589997284133708250277389331391382934079348500529494250621935846456061836590159765805069268649277993356664316144128659964751473179066727259024414399365682038439746355679194474137148293365593344278579893004665198741676727086051559

Notes: The Diffie-Hellman key exchange is vulnerable to a middleperson attack. See http://www.hack.gr/users/dij/crypto/overview/diffie.html for examples and solutions.

Todo:

DSA Digital Signature Algorithm

DSS Digital Signature Standard