Assembly Language Programming

April 10, 2012

FASM – x86 Modular Exponentiation

The x86 code below implements the modular exponentiation calculation. The algorithm I use to do this calculation is the left to right binary method which uses exponentiation by squaring.

The program was developed using FASM – the flat assembler. It uses a dialog box as the main window and looks like this:

Exponentiation by Squaring – Left to Right Binary Method

The modular exponentiation calculation is:

Mod_Exp(A,B,C) = AB mod C

One problem with doing a calculation of this type is the potentially massive size of the numbers generated. For example, say that both A and B are 3000 bit numbers. Then AB will end up being 9,000,000 bits in size. However, this problem can be avoided by applying a useful property of the modulus operation:

(A * B) mod C = ((A mod C) * (B mod C)) mod C

Therefore every time A is multiplied by B the modulus operation can be applied to reduce the size of the result. So even when A and B are both 3000 bits in length, the calculation of AB mod C will never require any more than about 6000 bits of memory storage.

The other problem with computing AB is the number of multiplications required. Say B is a 3000 bit number. Then the number of multiplications will be roughly of the order: 23000. Exponentiation by squaring is a method that is used to drastically reduce the number of multiplications needed. This method only requires one or two multiplications for each bit in B. So the number of multiplications will be of the order: log2(B).

Exponentiation by squaring is done by examining the binary bits in the exponent B from left (the most significant bit) to right. The result is initialised to 1. Then for each bit that is processed (0 or 1) the result is squared. If the bit is 1, then the result is also multiplied by the base (A in this case). The method is based on the following identities:

AB << 1 = [AB]2

A(B << 1) + 1 = [AB]2*A

For example:

A1000 = A1 << 3 = [A1 << 2]2 = [[A1 << 1]2]2 = [[[A1]2]2]2 = A8

And:

A110 = [A11]2 = [A(1 << 1) + 1]2 = [[A1]2*A]2 = A6

The following pseudo-code shows how modular exponentiation by squaring is implemented:

Compute AB mod C:

// initialise the result to 1

result=1;

// process the bits in B from left to right (msb first)

for(each bit in B)
{
 // square the result for each bit in B (0 or 1)

 result = (result * result) mod C;

 // if the bit is 1, multiply by A (the base)

 if(bit==1) result = (result * A) mod C;
}

Looking at the 2nd example above shows how the method works:

Set result  = 1.

Process the bits in 110:

msb = 1:

- square the result => result = 1.

- the bit is 1, so multiply by A => result = [A].

2nd bit = 1:

- square the result => result = [A]2.

- the bit is 1, so multiply by A => result = [A]2*A.

3rd bit = 0:

- square the result => result = [[A]2*A]2.

Testing The Program

When dealing with large numbers (especially when in hexadecimal format) it can be hard to know whether the modular exponentiation function within the program is giving the correct answer. One way to get around this is to use the function to test big numbers for primality, by using numbers that are known to be prime or not prime.

To do this I make use of part of Fermat’s Primality Test:

AP-1 mod P = 1

– where A is some random integer greater than 1, and P is a prime number.

Simply enter A as parameter 1, P-1 as parameter 2 and P as parameter 3. As long as P is prime, the result should always be 1 for any A.

A complete list of all the primes (in decimal format) up to 10,000,000,000 can be found at:

http://www.prime-numbers.org/.

Examples for some very large primes (the domain parameters p and q for the Digital Signature Algorithm) can be found in this pdf:

http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/DSA2_All.pdf

The primes (and non primes) found in this document are much larger (from 160 to 3072 bits) than the ones listed on prime-numbers.org and are also in hexadecimal format. So they are perfect for testing the modular exponentiation calculation within the program.

Usage

The program can accept up to 3 input parameters, depending on the function being called. The inputs are hexadecimal numbers, which can be up to 400 bytes (or 800 hex digits) in length. Whitespace and CRLF characters can be included in the input for formatting purposes. These will be ignored (along with any other non-hex characters) when the input strings are read. The hex digits in the input string are read from right to left. Once 800 digits have been read, the program stops reading. The program also recognises the minus sign. If a minus sign is found the program stops reading and writes the two’s complement of the preceding hex value to memory.

The output text field can display a hex number of up to 800 bytes (1600 digits) in length. This is just for testing purposes since the result of the modular exponentiation calculation will always be 400 bytes or less.

The following operations are needed to implement the modular exponentiation calculation: ADD, SUB, MUL, MOD, SHL, SHR.

ADD: this operation takes 2 input parameters. The CalcSum procedure that pressing this button calls adds the inputs as two 800 byte numbers (since this is required by the modular exponentiation calculation). Therefore, for testing purposes, if the input string contains a minus sign, the sign will be extended up through the higher 400 bytes of the resulting hex value.

SUB: this operation takes 2 input parameters. The CalcDiff procedure that pressing this button calls treats the inputs as two 800 byte numbers (since this is required by the modular exponentiation calculation). Therefore, for testing purposes, if the input string contains a minus sign, the sign will be extended up through the higher 400 bytes of the resulting hex value.

MUL: this operation takes 2 input parameters. The inputs are treated as two 400 byte numbers, which means the result may be up to 800 bytes in length. The output field can display numbers of up to 800 bytes in size, so this is no problem.

MOD: this operation takes 2 input parameters, which are treated as two 400 byte numbers in this case. However internally the CalcMod function that pressing this button calls handles the 2 inputs as 800 byte numbers, which is necessary for the modular exponentiation calculation.

SHL: this operation takes 1 input parameter, which is read from the output field and can be up to 800 bytes in size. Making the input and output fields the same means that the SHL button can be pressed multiple times, without having to copy the output back to the input each time.

SHR: this operation takes 1 input parameter, which is read from the output field and can be up to 800 bytes in size. Making the input and output fields the same means that the SHR button can be pressed multiple times, without having to copy the output back to the input each time.

The MOD EXP operation itself takes 3 parameters, which can be up to 400 bytes each. Internally the CalcModExp function uses 800 byte numbers to do the calculation, but the final result will be 400 bytes or less.

The first parameter is the base, the second is the exponent, and the third is the modulus.

The Fasm Code

To grab this code, select it with the mouse and copy it. It can then be pasted directly into the FASM IDE.

; -------------------------------------------------------------------------------------

 format PE GUI 4.0

 entry start

 include 'win32a.inc'

; -------------------------------------------------------------------------------------

 IDD_BIG_HEX_CALC_DIALOG = 102
 IDC_PARAM_1 = 1000
 IDC_PARAM_2 = 1001
 IDC_PARAM_3 = 1002
 IDC_OUTPUT = 1004
 IDC_BTN_ADD = 1005
 IDC_BTN_SUB = 1006
 IDC_BTN_MUL = 1007
 IDC_BTN_MOD = 1008
 IDC_BTN_SHL = 1009
 IDC_BTN_SHR = 1010
 IDC_BTN_MOD_EXP = 1011
 IDC_BTN_RESET = 1012

; -------------------------------------------------------------------------------------

 STR_LEN = 2000
 HEX_LEN = 400
 DBL_HEX_LEN = 2*HEX_LEN

; -------------------------------------------------------------------------------------

section '.code' code readable executable

 start:

   invoke GetModuleHandle,0
   invoke DialogBoxParam,eax,IDD_BIG_HEX_CALC_DIALOG,0,DialogProc,0

 exit:

   invoke ExitProcess,0 

; -------------------------------------------------------------------------------------

proc DialogProc uses ebx esi edi,hwnddlg,msg,wparam,lparam

        cmp [msg],WM_INITDIALOG
        je .wminitdialog

        cmp [msg],WM_COMMAND
        je .wmcommand

        cmp [msg],WM_CLOSE
        je .wmclose

        xor eax,eax

        jmp .quit

  .wminitdialog:
        
        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_1,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_2,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,""

        jmp .done

  .wmcommand:

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_RESET
        je .CLEARDATA

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_ADD
        je .GET_INPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SUB
        je .GET_INPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MUL
        je  .GET_INPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MOD
        je .GET_INPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MOD_EXP
        je .GET_INPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SHL
        je .GET_OUTPUT

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SHR
        je .GET_OUTPUT

        jmp .done

  .GET_INPUT:

        ; get parameter 1

        invoke GetDlgItemText,[hwnddlg],IDC_PARAM_1,bfInput,STR_LEN

        lea eax,[bfInput]
        lea edx,[hxBase]

        ; write to hex value in memory

        stdcall StrToHex

        ; write formatted string back to the edit box

        lea eax,[hxBase]
        lea edx,[bfDisplayStr]
        mov ecx,HEX_LEN

        stdcall HexToStr

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_1,bfDisplayStr

        ; get parameter 2

        invoke GetDlgItemText,[hwnddlg],IDC_PARAM_2,bfInput,STR_LEN

        lea eax,[bfInput]
        lea edx,[hxExp]

        ; write to hex value in memory

        stdcall StrToHex

        ; write formatted string back to the edit box

        lea eax,[hxExp]
        lea edx,[bfDisplayStr]
        mov ecx,HEX_LEN

        stdcall HexToStr

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_2,bfDisplayStr

        ; get parameter 3

        invoke GetDlgItemText,[hwnddlg],IDC_PARAM_3,bfInput,STR_LEN

        lea eax,[bfInput]
        lea edx,[hxMod]

        ; write to hex value in memory

        stdcall StrToHex

        ; write formatted string back to the edit box

        lea eax,[hxMod]
        lea edx,[bfDisplayStr]
        mov ecx,HEX_LEN

        stdcall HexToStr

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,bfDisplayStr

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_ADD
        je .SUM

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SUB
        je .SUB

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MUL
        je .MUL

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MOD
        je .MOD

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_MOD_EXP
        je .MOD_EXP

        jmp .done

  .GET_OUTPUT:

        ; get the input from the output edit box (for SHL and SHR functions)

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        invoke GetDlgItemText,[hwnddlg],IDC_OUTPUT,bfInput,STR_LEN

        lea eax,[bfInput]
        lea edx,[hxResult]

        ; write to hex value in memory

        stdcall StrToHex

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SHL
        je .SHL

        cmp [wparam],BN_CLICKED shl 16 + IDC_BTN_SHR
        je .SHR

        jmp .done

  .SET_OUTPUT:

        lea eax,[hxResult]
        lea edx,[bfDisplayStr]
        mov ecx,DBL_HEX_LEN

        stdcall HexToStr

        invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplayStr

        jmp .done

  .SUM:

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,""

        stdcall onBtnAdd

        jmp .SET_OUTPUT

        jmp .done

  .SUB:

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,""

        stdcall onBtnSub

        jmp .SET_OUTPUT

        jmp .done

  .MUL:

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,""

        stdcall onBtnMul

        jmp .SET_OUTPUT

        jmp .done

  .MOD:

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,""

        stdcall onBtnMod

        jmp .SET_OUTPUT

        jmp .done

  .MOD_EXP:

        stdcall onBtnModExp

        jmp .SET_OUTPUT

        jmp .done

  .SHL:

        stdcall onBtnShl

        jmp .SET_OUTPUT

        jmp .done

  .SHR:

        stdcall onBtnShr

        jmp .SET_OUTPUT

        jmp .done

  .CLEARDATA:

        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_1,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_2,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_PARAM_3,szInitText
        invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,""

        jmp .done

  .wmclose:

        invoke EndDialog,[hwnddlg],0

  .done:

        mov eax,1

  .quit:

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnAdd

        lea eax,[hxBase]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        stdcall SignExtend

        lea eax,[hxExp]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        stdcall SignExtend

        lea eax,[hxTemp]
        lea edx,[hxResult]

        stdcall CalcSum

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnSub

        lea eax,[hxExp]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        stdcall SignExtend

        lea eax,[hxBase]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        stdcall SignExtend

        lea eax,[hxTemp]
        lea edx,[hxResult]

        stdcall CalcDiff

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnShl

        lea eax,[hxResult]

        stdcall ShiftLeft

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnShr

        lea eax,[hxResult]

        stdcall ShiftRight

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnMul uses ebx

  ; compute C = A x B

        ; A is hxBase

        ; B is hxTemp

        lea eax,[hxExp]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        ; C is hxResult

        ; call the multiply function:

        ; the address of A is passed in EAX
        ; the address of B is passed in EBX
        ; the address of C is passed in EDX

        lea eax,[hxBase]
        lea ebx,[hxTemp]
        lea edx,[hxResult]

        stdcall Multiply

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnMod

  ; compute A mod B

        ; hex value for A in parameter 1

        lea eax,[hxBase]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        ; hex value for B in parameter 2

        lea eax,[hxExp]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        lea eax,[hxResult]
        lea edx,[hxTemp]

        stdcall CalcMod

        ; the result is left in A (hxResult)

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnModExp

  ; compute pow(A,B) mod C

        ; hex value for A in parameter 1

        lea eax,[hxBase]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        ; hex value for B in parameter 2

        ; hex value for C in parameter 3

        lea eax,[hxMod]
        lea edx,[hxDblMod]

        stdcall CopyHexToDHex

        ; call the proc

        stdcall CalcModExp

        ; result is left in hxResult

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnTest

  ; for testing only, not in the final version

        ; stdcall onBtnBigLeftShift

        ; stdcall onBtnIsZero

        ; stdcall onBtnIsLessThan

        ; stdcall onBtnFindHighOrderBit

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnBigLeftShift

  ; for testing only, not in the final version of the program

  ; test the BigLeftShift procedure

        ; hex value to shift in parameter 1

        lea eax,[hxBase]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        ; size of shift passed in parameter 2 (2 bytes only)

        ; copy to dx so it can be passed to the proc

        mov dx,word [hxExp]

        ; call the proc

        lea eax,[hxResult]

        stdcall BigLeftShift

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnIsZero

  ; for testing only, not in the final version of the program

  ; test the IsZero procedure

        ; hex value to test in parameter 1

        lea eax,[hxBase]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        ; the output

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        ; call the proc

        lea eax,[hxTemp]

        stdcall IsZero

        ; test AL to get the result

        cmp al,1

        jne .done

        mov byte [hxResult],1

  .done:

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnIsLessThan

  ; for testing only, not in the final version of the program

  ; test the IsLessThan procedure (is A less than B)

        ; hex value for A in parameter 1

        lea eax,[hxBase]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        ; hex value for B in parameter 2

        lea eax,[hxExp]
        lea edx,[hxResult]

        stdcall CopyHexToDHex

        lea eax,[hxTemp]
        lea edx,[hxResult]

        stdcall IsLessThan

        ; the output

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        ; test AL to get the result

        cmp al,1

        jne .done

        mov byte [hxResult],1

  .done:

        ret

endp

; -------------------------------------------------------------------------------------

proc onBtnFindHighOrderBit

  ; for testing only, not in the final version of the program

  ; test the FindHighOrderBit procedure

        ; hex value to test in parameter 1

        lea eax,[hxBase]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        ; the output

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        ; call the proc

        lea eax,[hxTemp]

        stdcall FindHighOrderBit

        ; get the result from EAX

        mov dword [hxResult],eax

        ret

endp

; -------------------------------------------------------------------------------------

proc StrToHex uses ebx esi edi

  ; convert a string containing a hex number to a hex value in memory

  ; filter out any non hex chars

        locals

          count db 0

        endl

        ; address of input string in EAX
        ; address of hex buffer in EDX

        ; zero output hex buffer

        stdcall ZeroHexBuffer

        mov esi,eax
        mov edi,edx

        ; get length of instr

        stdcall GetStrLength

        ; quit if null string

        cmp ecx,0

        jle .DONE

        ; adjust esi to point to last byte in string

        add esi,ecx
        dec esi

  .GET_CHARS:

        mov al,[esi]

        stdcall HexDigitToValue

        ; just skip and get the next char if not a hex digit

        cmp eax,0xffff

        je .NOT_HEX

        ; AL contains a nibble, determine where to place it in the dest byte

        ; if count is even, the nibble is mapped to the upper 4 bits in dest
        ; if count is odd, the nibble is mapped to the lower 4 bits in dest

        inc [count]

        ; even if count & 1 == 0

        test [count],1

        jz .EVEN

  .ODD:

        or [edi],al

        jmp .NOT_HEX

  .EVEN:

        shl al,4

        or [edi],al

        inc edi

  .NOT_HEX:

        cmp byte [esi],45

        je .MINUS

        dec ecx

        cmp ecx,0

        je .DONE

        dec esi

        jmp .GET_CHARS

  .MINUS:

        ; a minus sign was detected - negate the hex value and exit

        ; address of hex value still in EDX

        stdcall NegateHexValue

  .DONE:

        ret

endp

; -------------------------------------------------------------------------------------

proc NegateHexValue uses edi

  ; negate the hex value: -A = ~A + 1

  ; address is passed in EDX

        mov edi,edx

        mov cx,0

  .NOT:

        not byte [edi]

        inc edi
        inc cx

        cmp cx,HEX_LEN

        jne .NOT

        ; add 1

        mov edi,edx

        mov cx,0

  .ADD:

        add byte [edi],1

        jnc .QUIT

        inc edi
        inc cx

        cmp cx,HEX_LEN

        jne .ADD

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc ZeroHexBuffer uses edi ecx

  ; zero the hex value in memory

  ; address is passed in EDX

        mov edi,edx

        mov cx,0

  .ZERO:

        mov [edi],byte 0

        inc edi
        inc cx

        cmp cx,HEX_LEN

        jne .ZERO

        ret

endp

; -------------------------------------------------------------------------------------

proc ZeroDoubleHexBuffer uses edi ecx

  ; zero the double hex value in memory

  ; address is passed in EDX

        mov edi,edx

        mov cx,0

  .ZERO:

        mov [edi],byte 0

        inc edi
        inc cx

        cmp cx,DBL_HEX_LEN

        jne .ZERO

        ret

endp

; -------------------------------------------------------------------------------------

proc GetStrLength uses esi

  ; get string length by searching for NULL terminator

  ; address of input string in EAX

  ; length returned in ECX

        mov esi,eax

        mov ecx,0

  .GET_LEN:

        cmp [esi],byte 0

        je .DONE

        inc ecx

        ; make sure search doesn't go beyond end of string buffer

        cmp ecx,STR_LEN

        jge .DONE

        inc esi

        jmp .GET_LEN

  .DONE:

        ret

endp

; -------------------------------------------------------------------------------------

proc HexDigitToValue

  ; convert a hex digit to a 4 bit value

  ; input in AL
  ; output in AL

        ; set EAX to 0xffff if input is not a valid hex digit

        ; is AL in the range: 48 - 57 (0 - 9) ?

        cmp al,48

        jl .NOT_HEX

        cmp al,57

        jg .A_Z

        sub al,48

        jmp .DONE

        ; is AL in the range: 65 - 70 (A - B) ?

  .A_Z:

        cmp al,65

        jl .NOT_HEX

        cmp al,70

        jg .a_z

        sub al,55

        jmp .DONE

        ; is AL in the range: 97 - 102 (a - b) ?

  .a_z:

        cmp al,97

        jl .NOT_HEX

        cmp al,102

        jg .NOT_HEX

        sub al,87

        jmp .DONE

        ; not a hex digit

  .NOT_HEX:

        mov eax,0xffff

  .DONE:

        ret

endp

; -------------------------------------------------------------------------------------

proc HexToStr uses ebx esi edi

  ; print a hex value to string

  ; address of hex value in EAX (size up to DBL_HEX_LEN bytes)
  ; address of string in EDX (size up to STR_LEN bytes)
  ; size of hex value in ECX (HEX_LEN or DBL_HEX_LEN)

        mov esi,eax
        mov edi,edx

        locals

          count db 0

        endl

        ; length has been passed in CX

        cmp ecx,DBL_HEX_LEN

        ; if not equal to DBL_HEX_LEN, make sure it is set to HEX_LEN

        jne .1xLEN

        jmp .START

  .1xLEN:

        mov ecx,HEX_LEN

  .START:

        ; hex value is little endian, therefore
        ; start from the end of the hex value

        add esi,ecx
        sub esi,4

        ; find the first non zero dword - don't want to print leading zeroes

  .FIND:

        cmp dword [esi],0

        jne .FOUND

        sub esi,4

        sub cx,4

        ; always print the low dword, even if it is zero

        cmp cx,4

        jle .FOUND

        jmp .FIND

  .FOUND:

        ; adjust ESI to point to the high byte in the dword that was just tested

        add esi,3

  .CONVERT:

        ; byte to digits

        mov al,[esi]

        stdcall ByteToDigits

        ; add the 2 digits to the string

        mov [edi],ah
        inc edi

        mov [edi],al
        inc edi

        ; update ESI

        dec esi

        ; add spaces and CRLF to the output string

        ; a space after every 8 chars
        ; a CRLF after every 64 chars

        add [count],2

        test [count],7

        jne .NEXT

        test [count],63

        je .ADD_CRLF

        mov [edi],byte 32

        inc edi

        jmp .NEXT

  .ADD_CRLF:

        mov [edi],byte 13

        inc edi

        mov [edi],byte 10

        inc edi

  .NEXT:

        dec cx

        cmp cx,0

        jne .CONVERT

        mov [edi],byte 0

        ret

endp

; -------------------------------------------------------------------------------------

proc ByteToDigits uses ebx esi edi

  ; convert 1 byte to 2 hex digits

  ; input in AL
  ; output in AX

        ; copy AL to AH

        mov ah,al

        ; AH: get the upper 4 bits of the byte

        shr ah,4

        ; nibble to hex digit

        add ah,48

        cmp ah,57

        jle .NEXT

        add ah,7

  .NEXT:

        ; AL: get the lower 4 bits of the byte

        and al,0xf

        ; nibble to hex digit

        add al,48

        cmp al,57

        jle .DONE

        add al,7

  .DONE:

        ; output is in AX

        ret

endp

; -------------------------------------------------------------------------------------

proc CopyHexToDHex uses esi edi ecx

  ; copy a hex value to a double hex value

  ; address of hex value is in EAX
  ; address of double hex value is in EDX

        stdcall ZeroDoubleHexBuffer

        mov esi,eax
        mov edi,edx

        mov cx,0

  .COPY:

        mov eax,[esi]
        mov [edi],eax

        add esi,4
        add edi,4

        add cx,4

        cmp cx,HEX_LEN

        jl .COPY

        ret

endp

; -------------------------------------------------------------------------------------

proc SignExtend uses edi ecx

  ; call after a hex value has been copied to a double hex value - if needed

  ; extend the sign of the hex value up through the higher bytes

  ; address of double hex value is in EDX

        mov edi,edx

        add edi,HEX_LEN-1

        test byte [edi],0x80

        jz .QUIT

        inc edi

        mov cx,0

  .EXTEND:

        mov byte [edi],0xff

        inc edi

        inc cx

        cmp cx,HEX_LEN

        jl .EXTEND

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc CopyHexToHex uses esi edi ecx

  ; copy a hex value to a hex value

  ; address of src hex value is in EAX
  ; address of dest hex value is in EDX

        mov esi,eax
        mov edi,edx

        mov cx,0

  .COPY:

        mov eax,[esi]
        mov [edi],eax

        add esi,4
        add edi,4

        add cx,4

        cmp cx,HEX_LEN

        jl .COPY

        ret

endp

; -------------------------------------------------------------------------------------

proc CalcSum uses ebx esi edi ecx

  ; Add two double sized hex numbers

  ; address of src number is in eax
  ; address of dest number is in edx

        mov esi,eax
        mov edi,edx

        mov cx,0

        ; save CF from iteration to iteration

        ; init CF = 0

        clc

        ; push flags register to the stack

        pushf

  .SUM:

        mov eax,dword [esi]

        ; get the flags register from the stack

        popf

        ; [EDI] = [EDI] + [ESI] + CF

        adc dword [edi],eax

        ; save the flags register to the stack, for the next iteration

        pushf

        ; these affect the CF, which is why it has to be saved to the stack

        add esi,4
        add edi,4

        add cx,4

        ; cmp also affects the CF

        cmp cx,DBL_HEX_LEN

        jl .SUM

        ; clean up the stack

        popf

        ret

endp

; -------------------------------------------------------------------------------------

proc CalcDiff uses ebx esi edi ecx

  ; Calc difference between two double sized hex numbers

  ; diff = dest - src

  ; address of src number is in eax
  ; address of dest number is in edx

        mov esi,eax
        mov edi,edx

        mov cx,0

        ; compute diff as: diff = dest + ~src + 1

        ; the 1 is introduced by initialising CF to 1

        ; save CF from iteration to iteration

        ; init CF = 1

        stc

        ; push flags register to the stack

        pushf

  .SUB:

        mov eax,dword [esi]

        ; ~src here:

        not eax

        ; get the flags register from the stack

        popf

        ; [EDI] = [EDI] + ~[ESI] + CF

        adc dword [edi],eax

        ; save the flags register to the stack, for the next iteration

        pushf

        ; these affect the CF, which is why it has to be saved to the stack

        add esi,4
        add edi,4

        add cx,4

        ; cmp also affects the CF

        cmp cx,DBL_HEX_LEN

        jl .SUB

        ; clean up the stack

        popf

        ret

endp

; -------------------------------------------------------------------------------------

proc ShiftLeft uses edi ecx

  ; Shift dest number left by 1 bit

  ; address of dest number is in eax

        mov edi,eax

        ; start from the high order double word in the dest

        add edi,DBL_HEX_LEN-4

        mov cx,DBL_HEX_LEN-4

  .SHIFT:

        mov eax,dword [edi-4]

        shld dword [edi],eax,1

        sub edi,4

        sub cx,4

        cmp cx,0

        jg .SHIFT

        shl dword [edi],1

        ret

endp

; -------------------------------------------------------------------------------------

proc ShiftRight uses edi ecx

  ; Shift dest number right by 1 bit

  ; address of dest number is in eax

        mov edi,eax

        mov cx,0

  .SHIFT:

        mov eax,dword [edi+4]

        shrd dword [edi],eax,1

        add edi,4

        add cx,4

        cmp cx,DBL_HEX_LEN-4

        jl .SHIFT

        shr dword [edi],1

        ret

endp

; -------------------------------------------------------------------------------------

proc Multiply uses esi edi ebx ecx

  ; calculate C = A * B

        locals

          addr_A dd ?
          addr_B dd ?
          addr_C dd ?

          nBit db 0

        endl

        ; the address of A is in EAX
        ; the address of B is in EBX
        ; the address of C is in EDX

        mov dword [addr_A],eax
        mov dword [addr_B],ebx
        mov dword [addr_C],edx

        ; zero C

        stdcall ZeroDoubleHexBuffer

        ; B and C are hex values of length DBL_HEX_LEN
        ; A is a hex value of length HEX_LEN

        ; Algorithm:

        ; first find the byte in A containing the high order bit

        ; then starting from this byte, iterate through the bits in A
        ; start from the high order bit down to the low order bit

        ; for each iteration:

        ; (1) left shift C by 1 bit
        ; (2) test the bit
        ; (3) if the bit is set, add B to C

        ; A and B are not modified by this proc

        mov cx,HEX_LEN

        mov esi,dword [addr_A]

        ; start from end of A (the highest byte)

        add esi,HEX_LEN-1

  .FIND_HOB:

        ; is the byte zero ?

        cmp byte [esi],0

        jne .FOUND

        dec esi

        dec cx

        cmp cx,0

        je .QUIT

        jmp .FIND_HOB

  .FOUND:

        ; esi now points to the byte in A that has the high order bit
        ; cx contains the byte number (index into A)

        mov [nBit],byte 7

        ; load the byte at address ESI into BL for testing

        mov bl,byte [esi]

  .FIND_BIT:

        test bl,0x80

        jnz .HO_BIT

        shl bl,1

        dec [nBit]

        cmp [nBit],byte 0

        jl .QUIT

        jmp .FIND_BIT

  .HO_BIT:

        ; the high order bit has been found

        ; initialise C to B

        mov eax,dword [addr_B]
        mov edx,dword [addr_C]

        push cx

        stdcall CalcSum

        pop cx

  .NEXT_BIT:

        ; get the next bit

        shl bl,1

        dec [nBit]

        cmp [nBit],byte 0

        jl .NEXT_BYTE

        jmp .SHIFT

  .NEXT_BYTE:

        ; get the next byte

        dec esi

        dec cx

        ; no more bytes when cx = 0

        cmp cx,0

        jle .QUIT

        mov [nBit],byte 7

        mov bl,byte [esi]

  .SHIFT:

        mov eax,dword [addr_C]

        push cx

        stdcall ShiftLeft

        pop cx

        ; test the current bit to see if an addition is required

        test bl,0x80

        jz .NEXT_BIT

  .ADD:

        ; add B to C

        mov eax,dword [addr_B]
        mov edx,dword [addr_C]

        push cx

        stdcall CalcSum

        pop cx

        jmp .NEXT_BIT

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc CalcMod uses edi esi ebx ecx

  ; calculate A mod B

  ; the address of A is passed in EAX
  ; the address of B is passed in EDX

  ; A is a hex value of length DBL_HEX_LEN
  ; B is a hex value of length HEX_LEN

  ; B is passed in a buffer of length DBL_HEX_LEN

  ; A and B are both modified by this proc

  ; the result will be left in A

        locals

          addr_A dd ?
          addr_B dd ?

        endl

        mov dword [addr_A],eax
        mov dword [addr_B],edx

        ; if B is zero, return

        mov eax,dword [addr_B]

        stdcall IsZero

        cmp al,1

        je .QUIT

        ; if A is less than B, return (in which case: A mod B = A)

        mov eax,dword [addr_A]
        mov edx,dword [addr_B]

        stdcall IsLessThan

        test al,1

        jnz .QUIT

        ; left shift B until the high order bits of A and B are aligned

        locals

          offset_A dw 0
          offset_B dw 0

          shift_B dw 0

        endl

        ; find the high order bit in A

        mov eax,dword [addr_A]

        stdcall FindHighOrderBit

        ; check if the high order bit was found

        cmp eax,0xffffffff

        je .QUIT

        mov word [offset_A],ax

        ; find the high order bit in B

        mov eax,dword [addr_B]

        stdcall FindHighOrderBit

        ; check if the high order bit was found

        cmp eax,0xffffffff

        je .QUIT

        mov word [offset_B],ax

        ; compute how much to shift B by

        mov ax,[offset_A]
        sub ax,[offset_B]
        mov word [shift_B],ax

        ; do the shift

        mov eax,dword [addr_B]
        xor edx,edx
        mov dx,word [shift_B]

        stdcall BigLeftShift

        ; the high order bits of A and B are now aligned

        ; Algorithm:

        ; for (shift_B + 1) bits in A starting from the high order bit:

        ; (1) determine if A is less than B
        ; (2) if false, subtract B from A
        ; (3) right shift B by 1 bit
        ; (4) repeat from (1)

        mov cx,word [shift_B]

  .CALC_MOD:

        mov eax,dword [addr_A]
        mov edx,dword [addr_B]

        stdcall IsLessThan

        test al,1

        jnz .SHIFT

        mov eax,dword [addr_B]
        mov edx,dword [addr_A]

        stdcall CalcDiff

  .SHIFT:

        ; want to retain the original value of B
        ; so when cx reaches 0, quit before the final shift

        cmp cx,0

        jle .QUIT

        ; right shift B

        mov eax,dword [addr_B]

        stdcall ShiftRight

        dec cx

        jmp .CALC_MOD

        ; the result is now in A

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc BigLeftShift uses esi edi ecx

  ; left shift a double hex value by more than 1 bit

  ; address is passed in EAX
  ; size of shift passed in EDX

        mov edi,eax
        mov esi,eax

        locals

          nBytes dw 0
          nBits db 0

          addr dd ?

        endl

        ; save the address for later

        mov dword [addr],eax

        ; size of shift = 8 * nBytes + nBits

        ; get nBits

        mov al,dl

        and al,7

        mov byte [nBits],al

        ; get nBytes

        shr dx,3

        mov word [nBytes],dx

        cmp word [nBytes],0

        je .BITS

        cmp word [nBytes],DBL_HEX_LEN

        jge .ZERO_HEX

        ; copy up the bytes in the hex value by nBytes

        add edi,DBL_HEX_LEN-1
        add esi,DBL_HEX_LEN-1

        sub si,word [nBytes]

        mov cx,DBL_HEX_LEN
        sub cx,word [nBytes]

        ; copy up (DBL_HEX_LEN - nBytes) bytes

  .COPY_UP:

        mov al,[esi]
        mov [edi],al

        dec esi
        dec edi

        dec cx

        cmp cx,0

        jg .COPY_UP

        mov cx,word [nBytes]

        ; fill the rest of the hex array with zero bytes

  .FILL_0:

        mov [edi],byte 0

        dec edi

        dec cx

        cmp cx,0

        jg .FILL_0

        ; all done if nBits is zero

        cmp byte [nBits],0

        je .DONE

  .BITS:

        ; set edi back to the high order dword in the hex value

        mov edi,dword [addr]

        add edi,DBL_HEX_LEN-4

        mov cx,DBL_HEX_LEN-4

  .SHIFT_BITS:

        mov eax,[edi-4]

        push cx

        mov cl,byte [nBits]

        shld dword [edi],eax,cl

        pop cx

        sub edi,4

        sub cx,4

        cmp cx,0

        jg .SHIFT_BITS

        mov cl,byte [nBits]

        shl dword [edi],cl

        jmp .DONE

  .ZERO_HEX:

        ; shift is greater than the size of the hex value, just set to zero

        mov edx,edi

        stdcall ZeroDoubleHexBuffer

  .DONE:

        ret

endp

; -------------------------------------------------------------------------------------

proc FindHighOrderBit uses esi ebx ecx

  ; scan a double hex length value for the high order bit

  ; return an index number giving the position of the high order bit

  ; address passed in EAX

  ; index returned in EAX

        mov esi,eax

        ; start from the high order byte

        add esi,DBL_HEX_LEN-1

        mov cx,DBL_HEX_LEN

        mov eax,DBL_HEX_LEN-1

        ; scan byte by byte for the first non-zero byte

  .SCAN:

        cmp byte [esi],0

        jne .FOUND

        dec cx

        cmp cx,0

        ; not found if cx = 0, so quit

        jle .NOT_FOUND

        dec esi
        dec eax

        jmp .SCAN

  .FOUND:

        ; multiply EAX by 8

        shl eax,3

        mov ebx,7

        mov dl,byte [esi]

  .FIND_BIT:

        test dl,0x80

        jnz .FINISH

        shl dl,1

        dec bl

        cmp bl,0

        jl .NOT_FOUND

        jmp .FIND_BIT

  .FINISH:

        ; add the bit position to get the final index value

        add eax,ebx

        jmp .DONE

  .NOT_FOUND:

        mov eax,0xffffffff

  .DONE:

        ret

endp

; -------------------------------------------------------------------------------------

proc IsLessThan uses esi edi ecx

  ; is A less than B ?

  ; A and B are treated as unsigned values

  ; address of A passed in EAX
  ; address of B passed in EDX

        mov edi,eax
        mov esi,edx

        ; start from the high order bytes

        add esi,DBL_HEX_LEN-4
        add edi,DBL_HEX_LEN-4

        mov cx,0

        ; result is returned in AL

        xor al,al

  .CHECK_LT:

        mov edx,dword [edi]
        cmp edx,dword [esi]

        jb .LESS_THAN

        jnbe .QUIT

        add cx,4

        cmp cx,DBL_HEX_LEN

        jge .QUIT

        sub esi,4
        sub edi,4

        jmp .CHECK_LT

        ; AL = true if less than

  .LESS_THAN:

        mov al,1

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc IsZero uses esi ecx

  ; test a double hex value

  ; address passed in EAX

        mov esi,eax

        mov cx,DBL_HEX_LEN

        ; the result is returned in AL

        xor al,al

  .CHECK_IF_0:

        cmp dword [esi],0

        ; just quit if found to be non zero

        jne .QUIT

        sub cx,4

        ; if cx reaches zero, the hex value is zero

        cmp cx,0

        jle .IS_ZERO

        add esi,4

        jmp .CHECK_IF_0

        ; AL = true if the value is zero

  .IS_ZERO:

        mov al,1

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

proc CalcModExp uses esi edi

  ; compute A = pow(A,B) mod C

  ; A is in hxResult
  ; B is in hxExp
  ; C is in hxDblMod

        locals

          nBit db 0

        endl

        ; if C is zero, return

        lea eax,[hxDblMod]

        stdcall IsZero

        cmp al,1

        je .QUIT

        ; if B is zero, set hxResult = 1 and return

        lea eax,[hxExp]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        lea eax,[hxTemp]

        stdcall IsZero

        cmp al,0

        je .START

        lea edx,[hxResult]

        stdcall ZeroDoubleHexBuffer

        mov [hxResult],byte 1

        jmp .QUIT

  .START:

        ; find the high order byte in B

        mov cx,HEX_LEN-1

        lea esi,[hxExp]

        add esi,HEX_LEN-1

  .FIND_HOB:

        cmp [esi],byte 0

        jne .FOUND

        dec cx
        dec esi

        cmp cx,0

        jl .QUIT

        jmp .FIND_HOB

  .FOUND:

        ; now find the high order bit

        mov al,byte [esi]

        mov [nBit],byte 7

  .FIND_BIT:

        test al,0x80

        jnz .NEXT_BIT

        shl al,1

        dec [nBit]

        cmp [nBit],byte 0

        jge .FIND_BIT

        ; something is wrong - quit

        jmp .QUIT

        ; ESI now points to the high order byte in B
        ; nBit gives the index of the high order bit within this byte

        ; for the high order bit in B, nothing needs to be done,
        ; because hxResult has already been initialised to hxBase

        ; so get the next bit
        ; if nBit = 0, will need to get the next byte

  .NEXT_BIT:

        cmp [nBit],byte 0

        jle .NEXT_BYTE

        dec [nBit]

        shl al,1

        jmp .PROCESS

  .NEXT_BYTE:

        ; get the next byte

        ; if cx = 0, there is no next byte, so quit

        cmp cx,0

        jle .QUIT

        dec esi

        dec cx

        mov [nBit],byte 7

        mov al,byte [esi]

  .PROCESS:

        push eax

        ; for each bit, square hxResult

        lea eax,[hxResult]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        lea eax,[hxResult]
        lea edx,[hxTempHex]

        stdcall CopyHexToHex

        ; C = A * B

        ; the address of A is passed in EAX
        ; the address of B is passed in EBX
        ; the address of C is passed in EDX

        lea eax,[hxTemp]
        lea ebx,[hxTempHex]
        lea edx,[hxResult]

        stdcall Multiply

        ; the result is in hxResult

        ; compute the MOD: A = A mod B

        ; the address of A is passed in EAX
        ; the address of B is passed in EDX

        lea eax,[hxResult]
        lea edx,[hxDblMod]

        stdcall CalcMod

        pop eax

        ; test the bit in AL

        test al,0x80

        jz .NEXT_BIT

        ; if the bit is set multiply hxResult by the base

        push eax

        lea eax,[hxResult]
        lea edx,[hxTemp]

        stdcall CopyHexToDHex

        lea eax,[hxBase]
        lea edx,[hxTempHex]

        stdcall CopyHexToHex

        lea eax,[hxTemp]
        lea ebx,[hxTempHex]
        lea edx,[hxResult]

        stdcall Multiply

        ; compute the MOD: A = A mod B

        lea eax,[hxResult]
        lea edx,[hxDblMod]

        stdcall CalcMod

        pop eax

        jmp .NEXT_BIT

  .QUIT:

        ret

endp

; -------------------------------------------------------------------------------------

section '.idata' import data readable writeable

  library kernel,'KERNEL32.DLL',\
        user,'USER32.DLL'

  import kernel,\
        GetModuleHandle,'GetModuleHandleA',\
        ExitProcess,'ExitProcess'

  import user,\
        DialogBoxParam,'DialogBoxParamA',\ 
        SetDlgItemText,'SetDlgItemTextA',\
        GetDlgItemText,'GetDlgItemTextA',\
        EndDialog,'EndDialog'

; -------------------------------------------------------------------------------------

section '.data' readable writeable

  szInitText db "Input Parameter: max length = 1000 chars (800 hex digits plus white space)",0

  bfInput rb STR_LEN
  bfDisplayStr rb STR_LEN

  hxBase rb HEX_LEN
  hxExp rb HEX_LEN
  hxMod rb HEX_LEN

  hxTempHex rd HEX_LEN

  hxTemp rb DBL_HEX_LEN
  hxDblMod rb DBL_HEX_LEN
  hxResult rb DBL_HEX_LEN

; -------------------------------------------------------------------------------------

section '.rc' resource data readable

  directory RT_DIALOG,dialogs

  resource dialogs,IDD_BIG_HEX_CALC_DIALOG,LANG_ENGLISH+SUBLANG_DEFAULT,mod_exp_dialog

  dialog mod_exp_dialog,\
  'FASM - Modular Exponentiation',50,50,360,378,\
  DS_MODALFRAME+WS_MINIMIZEBOX+WS_POPUP+WS_VISIBLE+WS_CAPTION+WS_SYSMENU,\
  0,0,"Lucida Console",11

  dialogitem 'BUTTON','Enter Input Parameters',-1,7,5,346,224,BS_GROUPBOX+WS_VISIBLE,0
  dialogitem 'BUTTON',"Output",-1,7,256,346,112,BS_GROUPBOX+WS_VISIBLE,0

  dialogitem 'EDIT',0,IDC_PARAM_1,13,18,335,60,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0
  dialogitem 'EDIT',0,IDC_PARAM_2,13,83,335,60,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0
  dialogitem 'EDIT',0,IDC_PARAM_3,13,148,335,60,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0

  dialogitem 'BUTTON',"ADD",IDC_BTN_ADD,7,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"SUB",IDC_BTN_SUB,47,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"MUL",IDC_BTN_MUL,87,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"MOD",IDC_BTN_MOD,127,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"SHL",IDC_BTN_SHL,167,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"SHR",IDC_BTN_SHR,207,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"MOD EXP",IDC_BTN_MOD_EXP,247,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0
  dialogitem 'BUTTON',"CLEAR",IDC_BTN_RESET,287,234,36,14,BS_PUSHBUTTON+WS_VISIBLE,0

  dialogitem 'EDIT',0,IDC_OUTPUT,13,270,335,90,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0

  enddialog

; -------------------------------------------------------------------------------------
Advertisements

Blog at WordPress.com.

%d bloggers like this: