Asymmetric key encryption & BigInt functionality (code included)

[Professr]

After browsing the forums for a while and only finding a couple of DLL solutions for RSA or asymmetric encryption, I've written just enough of the basics of a BigInt library to do some simple encryption/decryption with small public and private keys. I'm sure there are bugs (and more efficient ways to do it), but it passes my test cases so far. Large numbers are converted to strings of 1s and 0s for the binary math. Do let me know if you find any problems or improvements

expandcollapse popup

#include <Math.au3>
#include <String.au3>

;374a760e6d241 - Private Key - 972687164232257[/i]
$privateKey = "972687164232257"
;69eda918eb380d - Modulus - 29816183077943309[/i]
$modulus = "29816183077943309"
;10001 - Public Key - 65537[/i]
$publicKey = "65537"

; Make some test text and turn it into a binary string[/i]
$text = "Test"
$bin = ""
For $i = 1 to StringLen($text)
$temp = decbin(Asc(StringMid($text, $i, 1)))
$temp = _StringRepeat("0", 8 - StringLen($temp)) & $temp
$bin = $bin & $temp
Next
ConsoleWrite( "Text: " & $bin & @CRLF)

; Encrypt our test binary string with our private key[/i]
$begin = TimerInit()
$cipherInt = binaryPowMod($bin, decbin($privateKey), decbin($modulus))
ConsoleWrite("Encryption took: " & Round(TimerDiff($begin) / 1000, 3) & "s" & @CRLF)
ConsoleWrite( "EncryptedInt: " & $cipherInt & @CRLF)

; Decrypt our encrypted binary string with the public key[/i]
$begin = TimerInit()
$decryptedInt = binaryPowMod($cipherInt, decbin($publicKey), decbin($modulus))[i];[/i]
ConsoleWrite("Decryption took: " & Round(TimerDiff($begin) / 1000, 3) & "s" & @CRLF)

; Pad our decrypted binary string to a byte length[/i]
$decryptedInt = _StringRepeat("0", 8 - Mod(StringLen($decryptedInt), 8)) & $decryptedInt
ConsoleWrite( "DecryptedInt: " & $decryptedInt & @CRLF)

; Convert our decrypted binary string back into ASCII and display it on the Console[/i]
For $i = 1 to StringLen($decryptedInt) Step 8
ConsoleWrite(Chr(bindec(StringMid($decryptedInt, $i, 8))))
Next
ConsoleWrite(@CRLF)

Exit

;********* FUNCTIONS *********[/i]
; Convert a decimal number (in a string) into a string of 1s and 0s[/i]
Func decbin($decString)
$stack = ""
While $decString <> "0"
     If 1 = Mod(Number(StringRight($decString, 1)), 2) Then
         $stack = "1" & $stack
     Else
         $stack = "0" & $stack
     EndIf
     $decString = divByTwo($decString)
WEnd
While "0" = StringLeft($stack, 1)
     $stack = StringTrimLeft($stack, 1)
WEnd
return $stack
EndFunc
; Utility function for decbin[/i]
Func divByTwo($string)
$result = ""
$next_add = 0
$size = StringLen($string)
For $i = 1 to $size [i];for ch in s:[/i]
     $add = $next_add
     $cur = Number(StringMid($string, $i, 1))
     If 1 = Mod($cur, 2) Then
         $next_add = 5
     Else
         $next_add = 0
     EndIf
     $result = $result & Floor(($cur / 2) + $add)
Next
If $result <> "0" Then
     While "0" = StringLeft($result, 1)
         $result = StringTrimLeft($result, 1)
     WEnd
EndIf
return $result
EndFunc

; Convert a string of 1s and 0s into a decimal number (in a string)[/i]
Func bindec($binString)
Local $size = StringLen($binString)
$result = "0"
For $i = 1 to $size
     $result = bigIntAdd($result, $result)
     $result = bigIntAdd($result, Number(StringMid($binString, $i, 1)))
Next
Return $result
EndFunc

; Add two large decimal numbers (in strings)[/i]
Func bigIntAdd($a, $b, $base = 10)
$size = _Max(StringLen($a), StringLen($b))
$a = _StringRepeat("0", $size - StringLen($a)) & $a
$b = _StringRepeat("0", $size - StringLen($b)) & $b
$result = ""[i];[/i]
$carry = 0[i];[/i]
For $i = $size to 1 Step -1
     $valA = Number(StringMid($a, $i, 1))
     $valB = Number(StringMid($b, $i, 1))
     $val = $valA + $valB + $carry
     If $val >= $base Then
         $carry = 1
         $val = Mod($val, $base)
     Else
         $carry = 0
     EndIf
     $result = $val & $result
Next
If 1 = $carry Then
         $result = "1" & $result
EndIf
While "0" = StringLeft($result, 1)
     $result = StringTrimLeft($result, 1)
WEnd
Return $result
EndFunc

; Multiply two large decimal numbers (in strings)[/i]
Func bigIntMultiply($a, $b)
Return bindec(binaryMultiply(decbin($a), decbin($b)))
EndFunc

; Return the modulus of two large decimal numbers (in strings)[/i]
Func bigIntMod($a, $b)
Return bindec(binaryMod(decbin($a), decbin($b)))
EndFunc

; Raise a binary string to a given power, modulo another binary string[/i]
Func binaryPowMod($num, $exp, $mod)
$result = "1"
While $exp <> "0" And StringLen($exp) > 0
     If "1" = StringRight($exp, 1) Then
         $result = binaryMod(binaryMultiply($result, $num), $mod)
     EndIf
     $exp = StringTrimRight($exp, 1)
     $num = binaryMod(binaryMultiply($num, $num), $mod)
WEnd
Return $result
EndFunc

; Add two binary strings together, or subtract them[/i]
Func binaryAdd($a, $b, $subtract = False)
$size = _Max(StringLen($a), StringLen($b))
$a = _StringRepeat("0", $size - StringLen($a)) & $a
$b = _StringRepeat("0", $size - StringLen($b)) & $b
$result = ""[i];[/i]
$carry = 0[i];[/i]
If($subtract) Then $carry = 1
If($subtract) Then
     $matchString = "0"
Else
     $matchString = "1"
EndIf
For $i = $size to 1 Step -1
     $val = 0
     $bitA = StringMid($a, $i, 1)
     $bitB = StringMid($b, $i, 1)
     If "1" = $bitA Then $val = $val + 1
     If $matchString = $bitB Then $val = $val + 1
     $val = $val + $carry
     Switch $val
         case 3
             $carry = 1
             $result = "1" & $result
         case 1
             $carry = 0
             $result = "1" & $result
         case 2
             $carry = 1
             $result = "0" & $result
         case 0
             $result = "0" & $result
     EndSwitch
Next
If 1 = $carry Then
     If Not $subtract Then
         $result = "1" & $result
     EndIf
EndIf
While "0" = StringLeft($result, 1)
     $result = StringTrimLeft($result, 1)
WEnd
Return $result
EndFunc

; Multiply two binary strings together[/i]
Func binaryMultiply($a, $b)
$shiftString = $a
$result = "0"
For $i = StringLen($b) to 1 Step -1
     If "1" = StringMid($b, $i, 1) Then
         $result = binaryAdd($result, $shiftString)
     EndIf
     $shiftString = $shiftString & "0"
Next
return $result
EndFunc

; Return the modulus of two binary strings[/i]
Func binaryMod($a, $b)
$ramp = $b & _StringRepeat("0", (StringLen($a) - StringLen($b)) - 1)
While binaryIsGreater($a, $b)
     $temp = binaryAdd($a, $ramp, TRUE)
     If binaryIsGreater($temp, $a) Then Return $a
     $a = $temp
     While (StringLen($ramp) >= StringLen($a))
         If "1" = StringRight($ramp, 1) Then ExitLoop
         $ramp = StringTrimRight($ramp, 1)
     WEnd
WEnd
Return $a
EndFunc

; Tell whether or not a binary string is greater than another binary string[/i]
Func binaryIsGreater($a, $b)
If StringLen($a) > StringLen($b) Then Return True
If StringLen($a) < StringLen($b) Then Return False
$size = StringLen($a)
For $i = 1 to $size
     $bitA = Number(StringMid($a, $i, 1))
     $bitB = Number(StringMid($b, $i, 1))
     If $bitA <> $bitB Then Return ($bitA > $bitB)
Next
Return False
EndFunc

Edited March 12, 2013 by Professr

[Professr]

So, after doing more research, it turns out this is pretty grade-school level I'm working on a better implementation.

[Professr]

After several days of annoyance, I've finally gotten it to work in base 32768. It's much faster than using binary strings (encrypts the previous example in 1.3s instead of 28s), but it doesn't seem to encrypt properly for inputs of more than 4 base-32768 digits. I'm wondering if my recursive math functions are hitting the recursion limit for such large numbers, but I haven't seen any errors.

expandcollapse popup

#include <Array.au3>
#include <String.au3>
#include <Math.au3>

;***** BIGINT *****
; Uses base 2^16 to get maximum use out of 32-bit integers
Global $base = 32768
Global $debug = False

;*****  Here are some tests you can run to check the math *****
;$pack1 = pack("392979")
;$pack2 = pack("392979")
;$pack3 = pack("154432494441")
;$pack4 = pack("785958")
;ConsoleWrite($result[0] & " " & $result[1] & @CRLF)
;ConsoleWrite(toString(multiplyBig($pack1, $pack2)) & @CRLF & toString($pack3) & @CRLF & @CRLF)
;ConsoleWrite(toString(addBig($pack1, $pack2)) & @CRLF & toString($pack4) & @CRLF & @CRLF)
;ConsoleWrite(toString(subtractBig($pack4, $pack1)) & @CRLF & toString($pack2) & @CRLF & @CRLF)
;$qr = divideBig($pack3, $pack1)
;ConsoleWrite(toString($qr[0]) & @CRLF & toString($pack1) & @CRLF & @CRLF)
;ConsoleWrite(bigLessThan($pack4, $pack1) & @CRLF & bigLessThan($pack1, $pack4) & @CRLF & toString($pack1) & " " & toString($pack4) & @CRLF & @CRLF)
;ConsoleWrite(toString(modBig($pack3, $pack1)) & @CRLF & toString($pack1) & @CRLF & @CRLF)
;ConsoleWrite(toString(modExp(pack(2), pack(3), pack(7))) & @CRLF & toString(pack(2)) & @CRLF & @CRLF)
;***** End tests *****

; Workaround for byref errors
Func toString($array)
Return _ArrayToString($array)
EndFunc

; Returns an array of digits in base $base
Func pack($base10String)
If IsArray($base10String) Then Return $base10String
Local $result[1]
Do
$divisionResults = base10StringDivide($base10String)
$base10String = $divisionResults[0]
;If $result <> "" Then $result = " " & $result
;$result = $divisionResults[1] & $result
_ArrayAdd($result, $divisionResults[1])
Until "" = $base10String
_ArrayDelete($result, 0)
stripZeros($result)
Return $result
EndFunc

; Returns A ^ E mod M
Func modExp($a, $e, $m, $level = 0)
   if bigLessThan($e, pack(1)) Then return pack(1)
   If $debug Then ConsoleWrite(_StringRepeat(">", $level) & toString($a) & " " & toString($e) & " " & toString($m) & @CRLF)
   $nm = modBig($a, $m)
   $qr = divideBig($e, pack(2))
   $r = modExp($nm, $qr[0], $m, $level + 1)
   $r = modBig(multiplyBig($r, $r), $m)
   if (Mod($e[0], 2) = 0) Then Return $r
   return modBig(multiplyBig($r, $nm), $m)
EndFunc

; Return A mod B
Func modBig($a, $b)
Local $qr = divideBig($a, $b)
Return $qr[1]
EndFunc

; Remove zero-padding from most significant digits
Func stripZeros(ByRef $a)
$sizeA = UBound($a) - 1
If $sizeA <= 0 Then Return
For $i = $sizeA To 1 Step -1
If 0 <> $a[$i] And IsNumber($a[$i]) Then
Return
Else
_ArrayPop($a)
EndIf
Next
EndFunc

; Return true if A is less than B
Func bigLessThan($a, $b)
$sizeA = UBound($a) - 1
$sizeB = UBound($b) - 1
If $debug Then ConsoleWrite("? " & toString($a) & " < " & toString($b) & @CRLF)
If $a[$sizeA] < 0 And $b[$sizeB] >= 0 Then Return True
If $sizeA <> $sizeB Then
Return ($sizeA < $sizeB)
Else
For $i = $sizeA To 0 Step -1
If $a[$i] <> $b[$i] Then Return ($a[$i] < $b[$i])
Next
EndIf
Return False
EndFunc

; Divide A by B in base Radix
Func divideBig($a, $b, $level = 0)
    Local $qr[2]
$qr[0] = pack(0)
$qr[1] = pack(0)
    ; base case
    if (bigLessThan($a, $b)) Then
        $qr[0] = pack(0)
        $qr[1] = $a
        return $qr
    EndIf
    ; recursive case
    $qr = divideBig($a, addBig($b, $b), $level + 1)
    $qr[0] = addBig($qr[0], $qr[0])
    if not bigLessThan($qr[1], $b) Then
        $qr[0] = addBig($qr[0], pack(1))
        $qr[1] = subtractBig($qr[1], $b)
    EndIf
If $debug Then ConsoleWrite(_StringRepeat(">", $level) & toString($qr[0]) & " " & toString($qr[1]) & @CRLF)
    return $qr
EndFunc

; Subtract B from A in base Radix
Func subtractBig(ByRef $a, ByRef $b, $radix=$base)
$sizeA = UBound($a) - 1
$sizeB = UBound($b) - 1
Local $d[_Max($sizeA, $sizeB) + 2]
    For $i = 0 To $sizeA
$d[$i] += $a[$i]
If $i <= $sizeB Then $d[$i] -= $b[$i]
If $d[$i] < 0 Then
$d[$i+1] = $d[$i+1] - 1
$d[$i] += $radix
EndIf
Next
stripZeros($d)
If $debug Then ConsoleWrite(toString($a) & " - " & toString($b) & " => " & toString($d) & @CRLF)
    return $d
EndFunc

; Multiply A and B in base Radix
Func multiplyBig($a, $b, $radix = $base)
$sizeA = UBound($a) - 1
$sizeB = UBound($b) - 1
Local $d[$sizeA + $sizeB + 2]
For $i = 0 to $sizeA
$carry = 0
For $j = 0 to $sizeB
$val = ($a[$i] * $b[$j]) + $carry + $d[$i + $j]
$d[$i + $j] = Mod($val, $radix)
$carry = Floor($val / $radix)
Next
$d[$i + $sizeB + 1] = $carry
Next
;ConsoleWrite(toString($a) & @CRLF & toString($b) & @CRLF & toString($d) & @CRLF)
stripZeros($d)
If $debug Then ConsoleWrite(toString($a) & " * " & toString($b) & " => " & toString($d) & @CRLF)
Return $d
EndFunc

Func expand(ByRef $a, $size)
While $size > (UBound($a) - 1)
_ArrayAdd($a, 0)
WEnd
EndFunc

; Add B to A in base Radix
Func addBig($a, $b, $radix = $base)
Local $size = UBound($a) - 1
Local $sizeB = UBound($b) - 1
Local $d[_Max($size, $sizeB) + 1]
Local $carry = 0

For $i = 0 to $size
$aPos = $i
If $aPos > $sizeB Then
$d[$aPos] = $a[$aPos]
Else
$val = $a[$aPos] + $b[$aPos] + $carry
$carry = 0
If $val >= $radix Then
$carry = 1
$val = Mod($val, $radix)
EndIf
$d[$aPos] = $val
EndIf
Next
If $carry > 0 Then
_ArrayAdd($d, $carry)
EndIf
stripZeros($d)
If $debug Then ConsoleWrite(toString($a) & " + " & toString($b) & " => " & toString($d) & @CRLF)
Return $d
EndFunc

; Helper function for converting decimal strings into base Radix
Func base10StringDivide($base10String, $radix = $base)
Local $results[2] ; 0 - quotient, 1 - remainder
$carry = 0
$results[0] = ""
For $i = 1 to StringLen($base10String)
$carry = $carry * 10
$carry = $carry + Number(StringMid($base10String, $i, 1))
If $carry >= $radix Then
$results[0] = $results[0] & Floor($carry / $radix)
$carry = Mod($carry, $radix)
Else
If "" <> $results[0] Then $results[0] = $results[0] & "0"
EndIf
Next
$results[1] = $carry
Return $results
EndFunc

Here's some random code I've been using to test RSA encryption with it, if you can really call 56-bit keys RSA:

expandcollapse popup

#include <Math.au3>
#include <String.au3>
#include "Bigint.au3"

;374a760e6d241 - Private Key - 972687164232257
$privateKey = "2195226017"
;69eda918eb380d - Modulus - 29816183077943309
$modulus = "3290644639"
;10001 - Public Key - 65537
$publicKey = "65537"

; Make some test text and turn it into a binary string
$text = "Testing Testing"
$bin = ""
$bigText = False
For $i = 1 to StringLen($text)
If Mod($i, 2) = 1 Then
$temp16 = Asc(StringMid($text, $i, 1))
Else
$temp16 = $temp16 + (256 * Asc(StringMid($text, $i, 1)))
If IsArray($bigText) Then
_ArrayAdd($bigText, $temp16)
Else
$bigText = pack($temp16)
EndIf
$temp16 = 0
EndIf
;ConsoleWrite($temp16 & " " & toString($bigText) & " " & $i & @CRLF)
Next
If $temp16 <> 0 Then _ArrayAdd($bigText, $temp16)
ConsoleWrite( "Text: " & toString($bigText) & @CRLF)

; Encrypt our test binary string with our private key
$begin = TimerInit()
$cipherInt = modExp($bigText, pack($privateKey), pack($modulus))
ConsoleWrite("Encryption took: " & Round(TimerDiff($begin) / 1000, 3) & "s" & @CRLF)
ConsoleWrite( "EncryptedInt: " & toString($cipherInt) & @CRLF)

; Decrypt our encrypted binary string with the public key
$begin = TimerInit()
$decryptedInt = modExp($cipherInt, pack($publicKey), pack($modulus));
ConsoleWrite("Decryption took: " & Round(TimerDiff($begin) / 1000, 3) & "s" & @CRLF)

ConsoleWrite( "DecryptedInt: " & toString($decryptedInt) & @CRLF)

; Convert our decrypted binary string back into ASCII and display it on the Console
$decryptedText = ""
For $i = 0 to UBound($decryptedInt) - 1
$val = $decryptedInt[$i]
$decryptedText = $decryptedText & Chr(Mod($val, 256))
If $val >= 256 Then
$decryptedText = $decryptedText & Chr(Floor($val / 256))
EndIf
Next
ConsoleWrite("Decrypted text: " & $decryptedText & @CRLF)

Exit

[nullschritt]

Hello, first of all, great script, but might I make a recommendation, to not use bigint? I know from personal experience, it exponentially increases the amount of time required for calculations, why not just use native math?