; Sample implementation of Diffie-Hellman key exchange in AutoIt

#Region Includes

; We need a BigNum UDF including the _BigNum_PowerMod function. I posted it on the forum some (long) time ago.
#include "..\..\include\BigNum.au3"

#cs In case your copy doesn't have the function, here it is:

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_PowerMod
; Description ...: Modular Exponentiation Mod($n^$e, $k)
; Syntax.........: _BigNum_PowerMod($n, $e, $k)
; Parameters ....: $n - Positive StringNumber: Digits"0"..."9"
;                  $e - Positive StringNumber: Exponent
;                  $k - Positive StringNumber: Modulus
; Return values .: Success - Result Mod($n^$e, $k)
;                  Failure - -1, sets @error to 1 if $n is not a positive valid StringNumber
;                            -1, sets @error to 2 if $e is not a positive valid StringNumber
;                            -1, sets @error to 3 if $k is not a positive valid StringNumber
; Author ........: jchd
; Date ..........: 17.12.13
; Remarks .......: Fractional exponents not allowed - use BigNum_n_root instead.
; ;===============================================================================================
Func _BigNum_PowerMod($n, $e, $k)
	If Not __BigNum_IsValid($n) Then Return SetError(1, 0, -1)
	If Not __BigNum_IsValid($e) Then Return SetError(2, 0, -2)
	If Not __BigNum_IsValid($k) Then Return SetError(3, 0, -3)

	Local $res = "1"

	While $e <> "0"
		If Mod(StringRight($e, 1), 2) Then
			$res = _BigNum_Mod(_BigNum_Mul($res, $n), $k)
			$e = _BigNum_Sub($e, "1")
		EndIf
		$n = _BigNum_Mod(_BigNum_Mul($n, $n), $k)
		$e = _BigNum_Div($e, "2")
	WEnd

	Return $res
EndFunc   ;==>_BigNum_PowerMod

#ce

#EndRegion


; In this demo, exchanges are done between functions within the same program.
; Variables are simply set this way between requester and responder.
; Use named pipes, TCPIP, HTTP, smoke signals, whatever you see fit for your real-world implementation.

; The protocol is simple:
;   requester selects a significantly large Sophie Germain prime P
;   requester selects a base B in [3,P-1] (relatively small B can do)
;   requester sends P and B to the responder
;   requester selects his secret number X in [3,P-1] (relatively small X can do)
;   requester computes U = Mod[B^X, P]
;   requester sends U to responder
;   responder selects his secret number Y in [3,P-1] (relatively small Y can do)
;   responder computes V = Mod[B^Y, P]
;   responder sends V to requester
;   requester computes the session key K = Mod[V^X, P] (actually Mod[B^(X*Y), P])
;   responder computes the session key K = Mod[U^Y, P] (actually Mod[B^(X*Y), P])

; Notes:
;   This protocol is NOT immune to a man-in-the-middle attack.
;   The prime P and base B can be agreed upon by the two parties beforehand, or once for all sessions if P large enough.
;   P and B never need to be secret (again, if large enough).
;   Discrete logarithm problems are hard to solve so you don't have to use a 4096-bit prime to exchange a temporary secret
;     that is, when a possible attacker would not benefit from hacking the session key exchange shortly after it took place.
;   OTOH if you intend to protect a long-lasting secret (where an attacker can take advantage of taking months or years to
;     find the secret key and still benefit from using it), select your P and B very carefully!
;   BigNum UDF works with strings so it's slow, yet is fast enough with the largest samples below to be useable in practice.
;   One can replace the discrete logarithm problem by finding points on an elliptic curve but I won't implement this.


#Region Variables used by requester

Local $sReq = "Requester "
Local $sReqP
Local $sReqB
Local $sReqX
Local $sReqU
Local $sReqV
Local $sReqK

#EndRegion



#Region Variables used by responder

Local $sResp = "Responder "
Local $sRespP
Local $sRespB
Local $sRespY
Local $sRespU
Local $sRespV
Local $sRespK

#EndRegion



#Region Protocol

$sReqP = Req_SelectP()
ConsoleWrite($sReq & "chooses P  = " & $sReqP & @LF)
Req_SendP()
$sRespP = Resp_GetP()
ConsoleWrite($sResp & "gets P     = " & $sRespP & @LF & @LF)
$sReqB = Req_SelectB()
ConsoleWrite($sReq & "chooses B  = " & $sReqB & @LF)
Req_SendB()
$sRespP = Resp_GetP()
ConsoleWrite($sResp & "gets B     = " & $sRespB & @LF & @LF)
$sReqX = Req_SelectX()
ConsoleWrite($sReq & "chooses X  = " & $sReqX & " as his/her own temporary secret" & @LF)
$sReqU = Req_ComputeU()
ConsoleWrite($sReq & "computes U = " & $sReqU & @LF)
Req_SendU()
$sRespU = Resp_GetU()
ConsoleWrite($sResp & "gets U     = " & $sRespU & @LF & @LF)
$sRespY = Resp_SelectY()
ConsoleWrite($sResp & "chooses Y  = " & $sRespY & " as his/her own temporary secret" & @LF)
$sRespV = Resp_ComputeV()
ConsoleWrite($sResp & "computes V = " & $sRespV & @LF)
Resp_SendV()
$sReqV = Req_GetV()
ConsoleWrite($sReq & "gets V     = " & $sReqV & @LF & @LF)
$sReqK = Req_ComputeK()
ConsoleWrite($sReq & "computes K = " & $sReqK & " as their common secret session key" & @LF)
$sRespK = Resp_ComputeK()
ConsoleWrite($sResp & "computes K = " & $sRespK & " as their common secret session key" & @LF)

; K can now be used by both parties to encrypt what they have to exchange during that session.

#EndRegion




#Region Requester functions

Func Req_SelectP()
	; Sample primes: they are taken from factors used in various entries of the RSA challenge, so we're sure they are Sophie Germain's type.
	;   The last 3 are most probably never used safe primes, supplied by yours truly.
	; Sophie Germain primes are of the form P = 2Q + 1 where Q is also a prime. They are said "safe primes" because solving a discrete log
	;   problem in those fields ℤ/pℤ is provably hard, provided P is large enough.
	; Of course, seriously strong key exchange should only use primes in the 2048-bit size and protect against man-in-the-middle attack.
	; Still this simple example is strong enough to make an eavesdropper busy for a long, long, very LONG time.
	Local Static $aPrimes = [ _
		"39685999459597454290161126162883786067576449112810064832555157243", _
		"6264200187401285096151654948264442219302037178623509019111660653946049", _
		"445647744903640741533241125787086176005442536297766153493419724532460296199", _
		"102639592829741105772054196573991675900716567808038066803341933521790711307779", _
		"47388090603832016196633832303788951973268922921040957944741354648812028493909367", _
		"3586420730428501486799804587268520423291459681059978161140231860633948450858040593963", _
		"476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833", _
		"60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899", _
		"1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571", _
		"3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349", _
		"562545761726884103756277007304447481743876944007510545104946851094548396577479473472146228550799322939273", _
		"8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499", _
		"32929074394863498120493015492129352919164551965362339524626860511692903493094652463337824866390738191765712603", _
		"4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589", _
		"244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447", _
		"33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711", _
		"64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367", _
		"97826372830338240928112256541157908286321115160760682309556339300058971773788832467435230096912361948172618528098129378520954494395010673390834950647702342778559198272159", _
		"10903009614937598971209609729260332096087753395652745660676481856224513082315816572642230321521364619112678600117943547577664934870460193824723896345237056196258757041908988790021346781669901295404684958335571183974988256952903", _
		"1794833603128708897231790903009614937598971209609729260332096087753395652745660676336826403053581232614993612648185622451308231581657264223032153578889209792803213646191126786001179435475776649348704601938247238963452370561962587570419089887900213467816699012954046849583355711839749882551588321643195684332227" _
	]
	Return $aPrimes[Random(0, UBound($aPrimes) - 1 , 1)]
EndFunc

Func Req_SelectB()
	Return String(Random(3, 0x7FFFFFFF, 1))
EndFunc

Func Req_SendP()
	$sRespP = $sReqP
EndFunc

Func Req_SendB()
	$sRespB = $sReqB
EndFunc

Func Req_SelectX()
	Return String(Random(3, 0x7FFFFFFF, 1))
EndFunc

Func Req_ComputeU()
	Return _BigNum_PowerMod($sReqB, $sReqX, $sReqP)
EndFunc

Func Req_SendU()
	$sRespU = $sReqU
EndFunc

Func Req_GetV()
	; passed from variable to variable
	Return $sReqV
EndFunc

Func Req_ComputeK()
	Return _BigNum_PowerMod($sReqV, $sReqX, $sReqP)
EndFunc

#EndRegion


#Region Responder functions

Func Resp_GetP()
	; passed from variable to variable
	Return $sRespP
EndFunc

Func Resp_GetB()
	; passed from variable to variable
	Return $sRespB
EndFunc

Func Resp_GetU()
	; passed from variable to variable
	Return $sRespU
EndFunc

Func Resp_SelectY()
	Return String(Random(3, 65535, 1))
EndFunc

Func Resp_ComputeV()
	Return _BigNum_PowerMod($sRespB, $sRespY, $sRespP)
EndFunc

Func Resp_SendV()
	$sReqV = $sRespV
EndFunc

Func Resp_ComputeK()
	Return _BigNum_PowerMod($sRespU, $sRespY, $sRespP)
EndFunc

#EndRegion