# Thread: Here's my LargeNumbers module's code

1. ## Here's my LargeNumbers module's code

I've created this so I can start working with absolutely large numbers. Though not yet completed, when it is, I'll be able to start experimenting with RSA and Diffie Hellman, two of the most common asymetric cryptography standards in use. I've been very unsatisfied with all current implementations of these crypto algorithms. They often times force things on the programmer, whether the programmer likes it or not. For example, in the RSA implementation in NewObjects AXPack1 (found on this webpage http://www.newobjects.com/product.asp?Category=63 ) ALWAYS uses the number 0x010001 for the public exponent, and does NOT let the programmer (me) change this, even though I would love to be able to change it, and even though a good library is one that lets the programmer alter all variables involved. And unfortunately it's the ONLY RSA implementation that I've seen that comes CLOSE to what I would like. So I've set out making this LargeNumbers module.

Now unlike other implementations I've seen, which all depend on strings, and are therefore base-10 (decimal), the one I've created is base-256, as it uses a byte arrays (each byte representing a value from 0 to 255, instead of each character representing a value from 0 to 9). This is absolutely necessary for cryptography, and why ALL other large number implementation's I've seen would be 100% useless in cryptography. You see, cryptography is based on base-256, not base-10. A 1024bit RSA key has 128 bytes (1024 bits) of data, not 128 decimal digits. After spending HOURS looking for, and failing to find, something that would fit my need for encryption. I've decided to implement these enecryption standards from scratch using large numbers. And after spending more HOURS looking for, and failing to find, something that would fit my need for handling large numbers, I decided to create my own Large Numbers module (.bas file), completely from scratch, and using only byte arrays (absolutely NO strings, and absolutely NO base-10 math).

So here's my code, at my current point in development for this LargeNumbers module.

Code:
```Public Function AddLN(ByRef In1() As Byte, ByRef In2() As Byte) As Byte()
Dim A() As Byte
Dim B() As Byte
Dim Out() As Byte
Dim In1Size As Long
Dim In2Size As Long
Dim OutSize As Long
Dim n As Long
Dim Carry As Long

In1Size = UBound(In1) + 1
In2Size = UBound(In2) + 1
If In2Size > In1Size Then OutSize = In2Size + 1 Else OutSize = In1Size + 1

A() = In1()
B() = In2()
ReDim Preserve A(OutSize - 1)
ReDim Preserve B(OutSize - 1)
ReDim Out(OutSize - 1)

For n = 0 To OutSize - 1
Carry = Carry + A(n) + B(n)
Out(n) = Carry And 255
Carry = Carry \ 256
Next n

If OutSize > 1 Then
For n = OutSize - 1 To 0 Step -1
If Out(n) > 0 Then
OutSize = n + 1
Exit For
End If
Next n
If OutSize > 0 Then ReDim Preserve Out(OutSize - 1)
End If

End Function

Public Function SubtractLN(ByRef In1() As Byte, ByRef In2() As Byte) As Byte()
Dim A() As Byte
Dim B() As Byte
Dim Out() As Byte
Dim In1Size As Long
Dim In2Size As Long
Dim OutSize As Long
Dim n As Long
Dim Carry() As Long

In1Size = UBound(In1) + 1
In2Size = UBound(In2) + 1
If In2Size > In1Size Then OutSize = In2Size Else OutSize = In1Size

A() = In1()
B() = In2()
ReDim Preserve A(OutSize - 1)
ReDim Preserve B(OutSize - 1)
ReDim Out(OutSize - 1)
ReDim Carry(OutSize - 1)

For n = OutSize - 1 To 0 Step -1
If (A(n) > 0) Or (B(n) > 0) Then
If B(n) > A(n) Then
ReDim Out(-1 To -1)
SubtractLN = Out()
Exit Sub
Else
Exit For
End If
End If
Next n

For n = 0 To OutSize - 1
Carry(n) = Carry(n) + A(n)
If B(n) > Carry(n) Then
Carry(n) = Carry(n) + 256
Carry(n + 1) = -1
End If
Out(n) = Carry(n) - B(n)
Next n

If OutSize > 1 Then
For n = OutSize - 1 To 0 Step -1
If Out(n) > 0 Then
OutSize = n + 1
Exit For
End If
Next n
If OutSize > 0 Then ReDim Preserve Out(OutSize - 1)
End If

SubtractLN = Out()
End Function

Public Function MultiplyLN(ByRef In1() As Byte, ByRef In2() As Byte) As Byte()
Dim Out() As Byte
Dim In1Size As Long
Dim In2Size As Long
Dim OutSize As Long
Dim n As Long
Dim x As Long
Dim y As Long
Dim Carry As Long

In1Size = UBound(In1) + 1
In2Size = UBound(In2) + 1
OutSize = In1Size + In2Size

ReDim Adder(OutSize - 1, In2Size - 1)
ReDim Out(OutSize - 1)

For y = 0 To In2Size - 1
Carry = 0
For n = 0 To In1Size - 1
x = n + y
Carry = Carry + 1& * In1(n) * In2(y)
Adder(x, y) = Carry And 255
Carry = Carry \ 256
Next n
Adder(n + y, y) = Carry
Next y

Carry = 0
For x = 0 To OutSize - 1
For y = 0 To In2Size - 1
Carry = Carry + Adder(x, y)
Next y
Out(x) = Carry And 255
Carry = Carry \ 256
Next x

If OutSize > 1 Then
For n = OutSize - 1 To 0 Step -1
If Out(n) > 0 Then
OutSize = n + 1
Exit For
End If
Next n
If OutSize > 0 Then ReDim Preserve Out(OutSize - 1)
End If

MultiplyLN = Out()
End Function```
As you can see it currently has AddLN, SubtractLN, and MultiplyLN. Unfortunately it's missing DivideLN, as I have yet to figure out a strategy for implementing division of large numbers. If somebody could chip in here with some suggestions, please do so. I'm basically stuck at this point, and don't know how to do division of large numbers.

2. ## Re: Here's my LargeNumbers module's code

Be aware you entered the mod math world. Everything is mod. So ADD, SUB and MPY is ok. But divide does not exist, its mod inv.
Now VB6 was a long time ago for me, I can't help you with this, but have a lok here for a start:

http://www.doc.ic.ac.uk/~mrh/330tutor/ch03.html

3. ## Re: Here's my LargeNumbers module's code

Did you look at .NET or vbCorLib's BigInteger implementation?

(.NET uses an array of UINT32, and vbCorLib uses an array of Integers.)

4. ## Re: Here's my LargeNumbers module's code

This looks like it will become a CodeBank post, but since there is a question at the end of it, I think it would be best in the main forum rather than the CodeBank.

5. ## Re: Here's my LargeNumbers module's code

Originally Posted by Shaggy Hiker
This looks like it will become a CodeBank post, but since there is a question at the end of it, I think it would be best in the main forum rather than the CodeBank.
I guess you are right. A lot has to be done like "MPY", "MOD", "MODinv" and exponentiation. Or split the thread.

6. ## Re: Here's my LargeNumbers module's code

While crypto may not use Divide, it would still be very useful for other tasks involving large numbers. Besides, the Mod function will REQUIRE the use of division, as the very definition of Mod is that it returns the remainder. And Mod most certainly is used for crypto.

7. ## Re: Here's my LargeNumbers module's code

fex. 1024 bit arithmetic (three parts)
http://www.dreamincode.net/forums/to...tic-functions/

Division is the most cpu intensive artihmetic computation, document links below compares some methods.

www.loria.fr/~zimmerma/papers/invert.pdf

Master thesis, Fast Division of Large Integers - a comparison of algortihms
http://treskal.com/s/masters-thesis.pdf

http://www.mersenneforum.org/showthr...t=15682&page=3
https://gmplib.org/list-archives/gmp...er/002549.html

8. ## Re: Here's my LargeNumbers module's code

Originally Posted by Ben321
...ALWAYS uses the number 0x010001 for the public exponent, and does NOT let the programmer (me) change this, even though I would love to be able to change it, and even though a good library is one that lets the programmer alter all variables involved.
Actually it is 0x10000000000000001, but anyway...
Are you sure that changing public exponent does not break the RSA algo?
http://security.stackexchange.com/qu...-to-security-c
http://crypto.stackexchange.com/ques...onent-of-65537
https://en.wikipedia.org/wiki/65537_(number)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured