ASM Community

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.0
entry main

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;	Calculate (123 ^ 17) mod 3233		
;	Result should be 855
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

include 'win32a.inc'

section '.data' data readable writeable
base dd 123
exp dd 17
modulus dd 3233
result dd 1
fmt db "%d", 13, 10, 0

section '.code' code readable executable
main:
	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 readable
library 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.

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 _start
extern 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, 0

section .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 printf
exit:
    mov eax, 1
    int 80h

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

Best,
Frank

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

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