Asmcodes: Modular Exponentiation

Back in November I discussed Modular Exponentiation and how to use this function for Diffie-Hellman key exchange.

The new function was a joint effort between Peter Ferrie and myself and is currently between 137 (if using byte version which is slower) or 140 bytes. Unfortunately, it’s incredibly slow with large numbers but the intention was to optimize for size.

; -----------------------------------------------
; Modular Exponetiation in x86 assembly
;
; size: 137 bytes or 140 for slightly faster version
;
; global calls use cdecl convention
;
; -----------------------------------------------

 ;%define BYTES 1

  bits 32
  
  %ifndef BIN
    global _modexp
    global modexp
  %endif

_modexp:
modexp:
    pushad
    lea    esi, [esp+32+ 4]
    lodsd
    cdq
    xchg   ecx, eax          ; ecx = max bytes
    lodsd
    push   eax               ; save base
    lodsd
    xchg   ebx, eax          ; ebx = exponent
    lodsd
    xchg   ebp, eax          ; ebp = modulus
    lodsd                   
    xchg   edi, eax          ; edi = result
    pop    esi               ; esi = base    
    inc    edx               ; edx = x=1
    db     0b0h              ; mov al, 0x60 to mask pushad
mulmod:
    pushad                   ; save registers
; cf=1 : r = mulmod (r, t, m);
; cf=0 : t = mulmod (t, t, m);
    push   edi               ; save edi
    ; r=x
    sub    esp, ecx          ; create space for r and assign x
    mov    edi, esp
    pushad
    dec    ecx               ; skip 1
    xchg   eax, edx          ; r=x
    stosb
    xor    al, al            ; zero remainder of buffer
    rep    stosb
    popad
    ; *************
    ; t=b
    sub    esp, ecx          ; create space for t and assign b
    mov    eax, esp
    pushad
    xchg   eax, edi
    rep    movsb
    popad
    xchg   eax, esi          
    call   ld_fn
    
; cf=1 : r = addmod (r, t, m);
; cf=0 : t = addmod (t, t, m);

; ebp  : m
; esi  : t
; edi  : r or t
; ecx  : size in bytes
;
addmod:
%ifndef BYTES
    shr    ecx, 2            ; /= 4
%endif
    clc
    pushad
am_l1:
%ifndef BYTES
    lodsd
    adc    eax, [edi]
    stosd
%else
    lodsb
    adc    al, [edi]
    stosb
%endif
    loop   am_l1
    popad
    mov    esi, ebp
    push   ecx
    dec    ecx
am_l2:
%ifndef BYTES
    mov    eax, [edi+ecx*4]
    cmp    eax, [esi+ecx*4]
%else
    mov    al, [edi+ecx]
    cmp    al, [esi+ecx]
%endif
    loope  am_l2
    pop    ecx
    jb     am_l4
am_l3:
%ifndef BYTES
    mov    eax, [edi]
    sbb    eax, [esi]
    stosd
    lodsd
%else
    mov    al, [edi]
    sbb    al, [esi]
    stosb
    lodsb
%endif
    loop   am_l3
am_l4:
    ret
    ; -----------------------------
ld_fn:
    dec    edx
    js     cntbits
    sub    dword[esp], addmod - mulmod
cntbits:
    xor    edx, edx
    lea    eax, [edx+ecx*8]
cnt_l1:
    dec    eax
    jz     xm_l1
    bt     [ebx], eax
    jnc    cnt_l1
xm_l1:
    ; if (e & 1)
    bt     [ebx], edx
xm_l2:
    pushfd
    pushad
    cdq
    cmovnc edi, esi          ; if (cf==0) do t = xmod(t, t, m)
    mov    ebx, edi          ; else r = xmod(r, t, m)
    call   dword[esp+32+4]   ; invoke mulmod or addmod
    popad
    popfd
    cmc
    jnc    xm_l2
    
    inc    edx
    dec    eax
    jns    xm_l1

    ; return r
    mov    esi, edi
    lea    esp, [esp+ecx*2+4]
    pop    edi
    rep    movsb
    popad
    ret

Check sources here and here

Advertisements
This entry was posted in assembly, cryptography, diffie hellman merkle, key exchange protocol, programming, security and tagged , , , , . Bookmark the permalink.

One Response to Asmcodes: Modular Exponentiation

  1. Pingback: Shellcode: A Windows PIC using RSA-2048 key exchange, AES-256, SHA-3 | modexp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s