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
