flat assembler
Message board for the users of flat assembler.
Index
> Windows > Specific usage of bignum multiplication Goto page Previous 1, 2 
Author 

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


15 Apr 2008, 01:49 

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.


15 Apr 2008, 03:27 

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


15 Apr 2008, 12:49 

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

15 Apr 2008, 13:31 

f0dder
revolution wrote:
_________________  carpe noctem 

15 Apr 2008, 13:46 

revolution
f0dder wrote:


15 Apr 2008, 13:51 

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

15 Apr 2008, 21:02 

revolution
AlexP wrote: I'm sure they'd lend me their credit card just trusting some guy named Revolution. AlexP wrote: NOTE: I am unable to buy the article. The publication website's store has 'withdrawn' it. 

16 Apr 2008, 02:01 

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


16 Apr 2008, 02:12 

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 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 Calling convension might seem odd, but it's rather trivial to wrap the fragment in PUSHAD/POPAD and load the arguments off the stack. 

16 Apr 2008, 04:45 

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 .
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, pseudoprime algo's, much other stuff that is needed. 

16 Apr 2008, 22:30 

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.


17 Apr 2008, 00:43 

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! 

17 Apr 2008, 00:49 

AlexP
Quote: MyBigNum dd $34560200,$4567 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 byteswapped 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
AlexP wrote: ordered HIGH > LOW like normal. (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. 

23 Apr 2008, 03:49 

AlexP
Quote: (If you read my comments I specifically note the zero case.) Quote: All those bswaps are just a waste 

23 Apr 2008, 13:55 

revolution
Who recommended that?


23 Apr 2008, 13:59 

AlexP
*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:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.