I'd like to calculate (123 ^ 17) mod 233, for example.

Found this code at stackoverflow:
``template <typename T>T modpow(T base, T exp, T modulus){    base %= modulus;    T result = 1;    while (exp > 0)    {        if (exp & 1) result = (result * base) % modulus;        base = (base * base) % modulus;        exp >>= 1;    }    return result;}``

And this is the result of my attempt to translate it:
``format PE console 4.0entry main;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;	Calculate (123 ^ 17) mod 3233		;	Result should be 855;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;include 'win32a.inc'section '.data' data readable writeablebase dd 123exp dd 17modulus dd 3233result dd 1fmt db "%d", 13, 10, 0section '.code' code readable executablemain:	mov ecx, 	mov ebx, 	xor edx, edx	_while:	cmp ecx, 0			; check if exp > 0 or not	jg _calculate1			; yes, do the if block	jmp _done				; done_calculate1:	and ecx, 1					cmp ecx, 0			; check if (exp & 1) > 0	jg _calculate2			; yes, then process the rest of if block	jmp _calculate3			; no, calculate the rest	_calculate2:	mov eax, dword 	; eax is base	imul ebx, eax			; result = result * base, ebx is result	mov eax, ebx			; copy the result to eax	div dword 		; modulo operation, the reminder is stored in edx	mov ebx, edx			; copy edx to result	jmp _calculate3			; do the rest	_calculate3:	imul eax, eax			; base * base	div dword 		; modulo operation	mov eax, edx			; copy the result into eax	shr ecx, 1	jmp _while_done:	cinvoke printf, fmt, ebx		invoke ExitProcess, 0		section '.idata' import data readablelibrary kernel32,'kernel32.dll', msvcrt,'msvcrt.dll'import kernel32, ExitProcess,'ExitProcess'import msvcrt, printf, 'printf'``

Wonder why the output is 123, and not 855.
These registers juggling make me confused.
And sorry if the code is kinda confusing, I'm still trying to make it shorter and cleaner.
Posted on 2012-09-07 11:34:56 by anta40
(I'm just pointing out what I saw, the comments below might not fully fix the code)

You are making a destructive test at _calculate1 ruining your exp variable (which you hold in ECX)
Replace:
``_calculate1:	and ecx, 1					cmp ecx, 0			; check if (exp & 1) > 0	jg _calculate2			; yes, then process the rest of if block	jmp _calculate3			; no, calculate the rest``
With:
``_calculate1:        test ecx, 1                     ; check if (exp & 1) > 0                                        jz  _calculate3                 ; no, calculate the rest                                        ; yes, then process the rest of if block``

Also, _calculate3 might not have EAX initialized with base at all times, it seems to require _calculate2 to be executed first (which not always happen).
Posted on 2012-09-07 18:21:01 by LocoDelAssembly
Don't look at me, I was confused before I got to the assembly... and even more confused after visiting SO! (not sure how much I trust a place that calls themselves "Stack Overflow"). So I converted it to Nasm syntax (can't help it, I'm a Nasm bigot) and to Linux (likewise). I got rid of the signed stuff ( Shouldn't ever be negative, no?) And...

``; nasm -f elf modpow.asm; ld -o modpow modpow.o -I/lib/ld-linux.so.2 -lc (-m elf_i386 for 64-bit systems)global _startextern printf;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;	Calculate (123 ^ 17) mod 3233		;	Result should be 855;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;section .data    base dd 123    exp dd 17    modulus dd 3233    result dd 1    fmt db "%d", 13, 10, 0section .text_start:    mov ecx,     mov ebx,     mov edi,     mov eax,     xor edx, edx    div edi    mov esi, edx ; base    xor edx, edx_while:    test ecx, ecx    jz _done_calculate1:    test ecx, 1    jz _calculate3_calculate2:    mov eax, ebx			; copy the result to eax    mul esi    div edi    mov ebx, edx			; copy edx to result_calculate3:    mov eax, esi    mul esi    div edi ; modulus    mov esi, edx ; base    shr ecx, 1    jmp _while_done:    push ebx    push fmt    call printfexit:    mov eax, 1    int 80h``

It gives the result you claim is correct. I claim nothing further!

Best,
Frank

Posted on 2012-09-07 19:55:21 by fbkotler
Thanks Frank, you're right.
Ah, I forgot that you could use ESI & EDI too...

BTW, why did you do the modulo first, before the while loop?
I still don't get it
Posted on 2012-09-08 10:47:30 by anta40
Well... that's how I read the "template" you showed, although you didn't do it in your code. I don't think it makes any difference in this case, but maybe with different numbers(?). I'm just flailing around - stopped when I got the "right" answer.

I used esi and edi to try to reduce the "register swapping". I guess it helped. If I understand what this is about, what we need is a few 4k-bit registers!

An interesting philosophical question, does a "fast factoring" algorithm exist? Can "they" decrypt this stuff? I'm inclined to think not, but... who knows?

We sometimes speak of crypto "good enough to fool your little sister". Happens that my little sister is a mathematician and not so easy to fool. I don't think I've ever discussed crypto with her - I don't think she's interested, and I wouldn't understand her anyway...

I think LocoDelAssembly picked up the main problem... "if (exp & 1)"...

Best,
Frank

Posted on 2012-09-08 18:56:50 by fbkotler
I just found a snippet in my computer I thought I could share:
``; ecx = exponent; eax = base  mov  ebx, 1.loop:  shr  ecx, 1  jnc  .skip  imul ebx, eax.skip:  imul eax, eax  or   ecx, ecx  jnz  .loop; eax = base^exponent (mod 2^32)``
I leave as an exercise modifying the code to have variable modulus.

PS: For some unknown reason the snippet doesn't use EDX which would been better to use than EBX since if this was a function, EBX would have to be preserved while EDX wouldn't (for most calling conventions at least). For the modifications required it is good to have EDX already free to use.
Posted on 2012-09-08 19:36:03 by LocoDelAssembly
@Frank
C++'s templates allows classes/methods to work with different types/classes without the need to rewrite for each of them. I don't need that at the moment. Integer is enough.

@Loco
Thanks. I'll take a look at that.
Posted on 2012-09-09 11:21:24 by anta40
Templates are like macros - they express code and data based on the input args.
They get 'expanded' into something that is then directly embedded in your executable.
So it's just like you wrote the entire code for each datatype you implement with a template.
Except that you didn't.

Posted on 2012-09-10 23:19:29 by Homer