# Asymmetric key encryption & BigInt functionality (code included)

## Recommended Posts

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

```#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 = ""
\$size = StringLen(\$string)
For \$i = 1 to \$size [i];for ch in s:[/i]
\$cur = Number(StringMid(\$string, \$i, 1))
If 1 = Mod(\$cur, 2) Then
Else
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, 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
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)
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 by Professr

##### Share on other sites

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

##### Share on other sites

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.

```#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
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)
if not bigLessThan(\$qr[1], \$b) Then
\$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
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)
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)
WEnd
EndFunc

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
\$carry = 1
EndIf
\$d[\$aPos] = \$val
EndIf
Next
If \$carry > 0 Then
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
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))
\$results[0] = \$results[0] & Floor(\$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:

```#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
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```

##### Share on other sites

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?

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...