Professr Posted March 12, 2013 Share Posted March 12, 2013 (edited) 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 Link to comment Share on other sites More sharing options...
Professr Posted March 13, 2013 Author Share Posted March 13, 2013 So, after doing more research, it turns out this is pretty grade-school level I'm working on a better implementation. Link to comment Share on other sites More sharing options...
Professr Posted March 19, 2013 Author Share Posted March 19, 2013 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 Link to comment Share on other sites More sharing options...
nullschritt Posted April 1, 2013 Share Posted April 1, 2013 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? Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now