Specific usage of bignum multiplication

Index > Windows > Specific usage of bignum multiplication

Goto page Previous 1, 2

Author

Thread

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 15 Apr 2008, 01:44

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

15 Apr 2008, 01:44

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 15 Apr 2008, 01:49

.... That's still not funny. I'm just glad that I know your little trick Smile

....

15 Apr 2008, 01:49

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 15 Apr 2008, 03:27

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.

15 Apr 2008, 03:27

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 15 Apr 2008, 12:49

I figured that, but I couldn't get the publish anyways. I'll keep looking for a copy.

15 Apr 2008, 12:49

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 15 Apr 2008, 13:31

AlexP wrote:

I figured that, but I couldn't get the publish anyways. I'll keep looking for a copy.

Why not just buy?

15 Apr 2008, 13:31

f0dder

Joined: 19 Feb 2004
Posts: 3175
Location: Denmark

f0dder 15 Apr 2008, 13:46

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

_________________

- carpe noctem

15 Apr 2008, 13:46

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 15 Apr 2008, 13:51

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

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.

15 Apr 2008, 13:51

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 15 Apr 2008, 21:02

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.

15 Apr 2008, 21:02

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 16 Apr 2008, 02:01

AlexP wrote:

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.

16 Apr 2008, 02:01

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 16 Apr 2008, 02:12

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

16 Apr 2008, 02:12

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 16 Apr 2008, 04:45

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)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

16 Apr 2008, 04:45

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 16 Apr 2008, 22:30

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.

16 Apr 2008, 22:30

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 17 Apr 2008, 00:43

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)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

17 Apr 2008, 00:43

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 17 Apr 2008, 00:49

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!

17 Apr 2008, 00:49

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 20 Apr 2008, 19:53

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

20 Apr 2008, 19:53

bitRAKE

Joined: 21 Jul 2003
Posts: 4073
Location: vpcmpistri

bitRAKE 23 Apr 2008, 03:49

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)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

23 Apr 2008, 03:49

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 23 Apr 2008, 13:55

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?!.

23 Apr 2008, 13:55

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 23 Apr 2008, 13:59

Who recommended that?

23 Apr 2008, 13:59

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 23 Apr 2008, 21:03

*shouldn't say 'recommended', should have said 'that's what their code did'.

23 Apr 2008, 21:03

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