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) = A^B 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 A^B 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 A^B mod C will never require any more than about 6000 bits of memory storage.

The other problem with computing A^B is the number of multiplications required. Say B is a 3000 bit number. Then the number of multiplications will be roughly of the order: 2³⁰⁰⁰. 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: log₂(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:

A^{B << 1} = [A^B]²

A^{(B << 1) + 1} = [A^B]²*A

For example:

A¹⁰⁰⁰ = A^{1 << 3} = [A^{1 << 2}]² = [[A^{1 << 1}]²]² = [[[A¹]²]²]² = A⁸

And:

A¹¹⁰ = [A¹¹]² = [A^{(1 << 1) + 1}]² = [[A¹]²*A]² = A⁶

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:

A^P-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 ; -------------------------------------------------------------------------------------