flat assembler
Message board for the users of flat assembler.

Index > Windows > Specific usage of bignum multiplication

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
AlexP wrote:
Hmm, I tried some x9.31 I believe, apparently I have to buy them?! ...

PS: is X9.62 about ECC?! Everywhere I go I cannot get near an ANSII spec because I have to pay for them, or login. Is there some site I can go to to view ANSII specs?
Yeah, you gotta buy them. But perhaps my website will help you to obtain a copy through other means Wink
Post 15 Apr 2008, 01:44
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
.... That's still not funny. I'm just glad that I know your little trick Smile....
Post 15 Apr 2008, 01:49
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
X9.62 is ECC based, but it has descriptions of algos for PKE tasks. ECC is mostly a superset of RSA in terms of algos used, so all the modular multiply and prime finding things still apply to RSA.
Post 15 Apr 2008, 03:27
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
I figured that, but I couldn't get the publish anyways. I'll keep looking for a copy.
Post 15 Apr 2008, 12:49
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
AlexP wrote:
I figured that, but I couldn't get the publish anyways. I'll keep looking for a copy.
Why not just buy?
Post 15 Apr 2008, 13:31
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
revolution wrote:
AlexP wrote:
I figured that, but I couldn't get the publish anyways. I'll keep looking for a copy.
Why not just buy?
That's usually easy enough for us old geezers with job and steady income, but night be so easy for the young whipper-snappers... Smile

_________________
Image - carpe noctem
Post 15 Apr 2008, 13:46
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
f0dder wrote:
revolution wrote:
Why not just buy?
That's usually easy enough for us old geezers with job and steady income, but night be so easy for the young whipper-snappers... Smile
Hehe, just ask your mum and dad nicely, don't forget to say please. Tell them I said it was okay, that ought to convince them.
Post 15 Apr 2008, 13:51
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
Smile I'm sure they'd lend me their credit card just trusting some guy named Revolution.

NOTE: I am unable to buy the article. The publication website's store has 'withdrawn' it. Darn, do you have a copy revolution?

NOTE2: For the Miller-Rabin test, you have to compute 'x' and 'y' in the equation (2^x)y. I made this for finding the highest power of two which divides a number, to be used in a loop for bignum:

Note, does not work for the last dword of a bignum:
Code:
    bsf temp,source  ; temporarily obtain the number of zero's on the right
    jnz @f           ;
    add temp, 32     ; it was all zero's
@@: add dest,temp    ; add the temp to the summation
    


It will effectively give you the highest power of two that divides a number. For finding the other variable, 'y', all you need to do is shift the bignum to the right 'x' places. Example:

Code:
Num    X    Y
10       1    1
100     2    1
110     1    3
1000   3    1
1010   1    5
    

You get the point. I think it is a very efficient way to calculate those variables for anyone doing the Miller-Rabin.
Post 15 Apr 2008, 21:02
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
AlexP wrote:
Smile I'm sure they'd lend me their credit card just trusting some guy named Revolution.
Good, I am glad they are trusting me.
AlexP wrote:
NOTE: I am unable to buy the article. The publication website's store has 'withdrawn' it.
That probably means there is a later version. You should buy the later version instead.
Post 16 Apr 2008, 02:01
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
... I'll look for it. The (2^x)y code I made actually works! (and pretty fast, too). Only thing is, I need to shift > 15... I can't do that with one reg, I'll have to work on that...
Post 16 Apr 2008, 02:12
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
Code:
; Find (2^X)Y for big number
;
; ESI = big number
; EBP = address past big number end

        push esi
        mov ebx,-32
        mov edi,esi
.0:     bsf ecx,[esi]
        lodsd
        lea ebx,[ebx+32]
        jz .0
        mov edx,eax
        add ebx,ecx

.1:     lodsd
        shrd edx,eax,cl
        shr eax,cl
        xchg eax,edx
        stosd
        cmp esi,ebp
        jbe .1

        mov eax,0
        pop esi
        jmp .2a
.2:     stosd
.2a:    cmp edi,ebp
        jc .2

; EBX = (X)
; ESI = big number (Y)
; EBP = address past big number end    
...works for any size big integer as long as the dword following the big integer represents the sign.
Code:
MyBigNum dd $34560200,$4567
MyBigNum.end dd 0 ; 0 for positive, -1 for negative number

lea esi,[MyBigNum]
lea ebp,[MyBigNum.end]
call _2powX_Y ; call it whatever
; ebx = power of two    
I aimed for minimal instructions for the general case. It doesn't handle zero, but that is because I figured the big number would be copied prior and that is where the zero check would be. I tested it a little.

Calling convension might seem odd, but it's rather trivial to wrap the fragment in PUSHAD/POPAD and load the arguments off the stack.

_________________
¯\(°_o)/¯ unlicense.org
Post 16 Apr 2008, 04:45
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
Bitrake: I did already have code much like that, I'll work with yours for now because it looks a little more efficient than mine Smile.

And I'm considering a bignum library, because I do need many different bignum operations:

1) SEveral types of bignum multiplication
2) Several types of bignum Modular exponentiation (I'm going to try several reduction techniques, CRT, I'll take a stab at FFT, ect...)
3) Bignum euclidean, code like the one above, pseudo-prime algo's, much other stuff that is needed.
Post 16 Apr 2008, 22:30
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
I have a lot of misc stuff around for various problems I've solved - nothing in 'library' form. Usually, I find some way to use brute force, so the stuff is optimized to work in the problem domain. If I can help in any way I certainly will.

_________________
¯\(°_o)/¯ unlicense.org
Post 17 Apr 2008, 00:43
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
Maybe, but for now I'm content with reading through this RSA book.

EDIT:

The reason I'm not working with your code right now is that my lifestyle between Monday -> Friday only allows me a couple of hours a night for studies. On weekends I usually do the coding.

EDIT2:

You don't happen to have any FFT code, do you bitRAKE? Anything relating to bignum multiplication/ powmod would be a very big help!
Post 17 Apr 2008, 00:49
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
Quote:
MyBigNum dd $34560200,$4567
MyBigNum.end dd 0 ; 0 for positive, -1 for negative number

lea esi,[MyBigNum]
lea ebp,[MyBigNum.end]
The code there wouldn't load the right values, are you sure your tests are right?! Also, if the operand of the bsf instruction contains '0', then the result is undefined. It looks like your code will fault in that case.

bitRAKE: Here's my version, it's a little smaller and get's the same job done
- NOTE: In memory, bignum is ordered HIGH -> LOW like normal. All DWORDS are byte-swapped so they load into regs normally
Code:
; (2^v)w computer
;
; input: esi = start address of 'v'
;        edi = start address of 'w'
;        ebp = end address of 'w' minus 4
;
; output: ebx = 'v'
;         'w' is in memory

vw: std                  ; we want to work with/store LOW -> HIGH
    xor     ebx, ebx     ; zero the accumulator
.1: lodsd
    test    eax, eax
    jnz     .2
    add     ebx, 32      ; it's zero, add 32 and loop again
    jmp     .1           ; it'll never end off with zero
.2: bsf     ecx, eax     ; it's got a value, so bsf and you're done
    add     ebx, ecx     ; do the final add into the accumulator
    mov     edx, eax     ; edx for next loop = first dword with value
.3: lodsd                ; load the next value after it (higher)
    shrd    edx, eax, cl ; shift bits of eax -> edx (higher -> lower)
    xchg    eax, edx     ; exchange them for next loop
    stosd                ; store in 'w' starting from lowest position
    cmp     edi, ebp     ; if it's reached end of 'w'
    jnz     .3
    ret
    
Post 20 Apr 2008, 19:53
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
AlexP wrote:
ordered HIGH -> LOW like normal.
Whatever. Intel ordering is low byte low, which is low word low, and low dword low, etc... All those bswaps are just a waste - to design a library for x86 like that is just silly unless there is some file format being supported for another system.

(If you read my comments I specifically note the zero case.)

Thanks for fixing the (.3) loop - I was shifting twice - which doesn't work.

_________________
¯\(°_o)/¯ unlicense.org
Post 23 Apr 2008, 03:49
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
Quote:
(If you read my comments I specifically note the zero case.)
I didn't mean the entire bignum being zero, only a single dword. The revised code works fine.
Quote:
All those bswaps are just a waste
Yeah, people recommend having it reversed and everythign bswapped?!.
Post 23 Apr 2008, 13:55
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17332
Location: In your JS exploiting you and your system
revolution
Who recommended that?
Post 23 Apr 2008, 13:59
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
*shouldn't say 'recommended', should have said 'that's what their code did'.
Post 23 Apr 2008, 21:03
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.