'''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. lappend auto_path lib package require mpa #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 set public_val [::mpa::int::powmod $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 [::mpa::int::powmod $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. Heres 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 ---- [Category Cryptography]