dcsimg
Results 1 to 9 of 9

Thread: Here's my LargeNumbers module's code

  1. #1

    Thread Starter
    Fanatic Member
    Join Date
    Oct 2008
    Posts
    997

    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
        
        AddLN = Out()
    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 Adder() 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. #2
    Fanatic Member namrekka's Avatar
    Join Date
    Feb 2005
    Location
    Netherlands
    Posts
    639

    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. #3
    PowerPoster
    Join Date
    Jun 2015
    Posts
    2,224

    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.)
    Last edited by DEXWERX; Jun 30th, 2016 at 11:32 AM.

  4. #4
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,889

    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.
    My usual boring signature: Nothing

  5. #5
    Fanatic Member namrekka's Avatar
    Join Date
    Feb 2005
    Location
    Netherlands
    Posts
    639

    Re: Here's my LargeNumbers module's code

    Quote Originally Posted by Shaggy Hiker View Post
    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. #6

    Thread Starter
    Fanatic Member
    Join Date
    Oct 2008
    Posts
    997

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

  8. #8
    Fanatic Member
    Join Date
    Apr 2015
    Location
    Finland
    Posts
    672

    Re: Here's my LargeNumbers module's code

    How about inline asm...

    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

  9. #9
    Fanatic Member
    Join Date
    Apr 2015
    Location
    Finland
    Posts
    672

    Re: Here's my LargeNumbers module's code

    Quote Originally Posted by Ben321 View Post
    ...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)
    Last edited by Tech99; Jul 1st, 2016 at 02:37 PM.

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


Click Here to Expand Forum to Full Width