| 0,0 → 1,568 |
|---|
| ; mpint.inc - Multi precision integer procedures |
| ; |
| ; Copyright (C) 2015-2016 Jeffrey Amelynck |
| ; |
| ; This program is free software: you can redistribute it and/or modify |
| ; it under the terms of the GNU General Public License as published by |
| ; the Free Software Foundation, either version 3 of the License, or |
| ; (at your option) any later version. |
| ; |
| ; This program is distributed in the hope that it will be useful, |
| ; but WITHOUT ANY WARRANTY; without even the implied warranty of |
| ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| ; GNU General Public License for more details. |
| ; |
| ; You should have received a copy of the GNU General Public License |
| ; along with this program. If not, see <http://www.gnu.org/licenses/>. |
| |
| MPINT_MAX_LEN = MAX_BITS/8 |
| |
| ; TODO: make procedures use real number length instead of hardcoded maximum length (MPINT_MAX_LEN) |
| |
| mpint_to_little_endian: |
| |
| ; Load length dword |
| lodsd |
| ; Convert to little endian |
| bswap eax |
| stosd |
| test eax, eax |
| jz .zero |
| ; Copy data, convert to little endian meanwhile |
| push eax |
| add esi, eax |
| push esi |
| dec esi |
| mov ecx, eax |
| std |
| @@: |
| lodsb |
| mov byte[edi], al |
| inc edi |
| dec ecx |
| jnz @r |
| cld |
| pop esi eax |
| ; Fill the rest of the buffer with zeros. |
| .zero: |
| mov ecx, MAX_BITS/8 |
| sub ecx, eax |
| xor al, al |
| rep stosb |
| |
| ret |
| |
| mpint_to_big_endian: |
| |
| ; Load length dword |
| lodsd |
| test eax, eax |
| jz .zero |
| mov ecx, eax |
| add esi, ecx |
| dec esi |
| test byte[esi], 0x80 ; Is the highest bit set? |
| jz @f |
| inc eax |
| @@: |
| push eax |
| bswap eax |
| stosd |
| ; Copy data, convert to big endian meanwhile |
| std |
| ; Append zero byte if highest bit is 0 |
| test byte[esi], 0x80 |
| jz @f |
| mov byte[edi], 0 |
| inc edi |
| @@: |
| lodsb |
| mov byte[edi], al |
| inc edi |
| dec ecx |
| jnz @r |
| cld |
| pop eax |
| ret |
| |
| .zero: |
| stosd |
| ret |
| |
| proc mpint_length uses edi eax ecx, mpint |
| |
| mov edi, [mpint] |
| mov ecx, MPINT_MAX_LEN |
| push edi |
| lea edi, [edi + ecx + 4 - 1] |
| xor al, al |
| std |
| repe scasb |
| cld |
| je @f |
| inc ecx |
| @@: |
| pop edi |
| mov [edi], ecx |
| |
| ret |
| |
| endp |
| |
| proc mpint_print uses ecx esi eax, src |
| |
| DEBUGF 1, "0x" |
| mov esi, [src] |
| mov ecx, [esi] |
| test ecx, ecx |
| jz .zero |
| lea esi, [esi + ecx + 4 - 1] |
| pushf |
| std |
| .loop: |
| lodsb |
| DEBUGF 1, "%x", eax:2 |
| dec ecx |
| jnz .loop |
| DEBUGF 1, "\n" |
| popf |
| |
| ret |
| |
| .zero: |
| DEBUGF 1, "00\n" |
| ret |
| |
| endp |
| |
| proc mpint_zero uses edi ecx eax, dst |
| |
| mov edi, [dst] |
| xor eax, eax |
| mov ecx, MPINT_MAX_LEN/4+1 |
| rep stosd |
| |
| ret |
| |
| endp |
| |
| proc mpint_zero? uses edi ecx eax, dst |
| |
| mov edi, [dst] |
| add edi, 4 |
| mov ecx, MPINT_MAX_LEN/4 |
| xor eax, eax |
| repe scasd |
| ret |
| |
| endp |
| |
| ; return an index number giving the position of the highest order bit |
| proc mpint_hob uses edi ecx, dst |
| |
| mov edi, [dst] |
| ; start from the high order byte |
| add edi, MPINT_MAX_LEN+4-1 |
| mov ecx, MPINT_MAX_LEN |
| xor eax, eax |
| ; scan byte by byte for the first non-zero byte |
| std |
| repe scasb |
| cld |
| je .zero |
| ; calculate how many bits this is, plus 7 |
| lea eax, [ecx*8-1] |
| ; load this high order byte into cl |
| mov cl, [edi+1] |
| ; shift bits of this byte right, until the byte reaches zero, counting bits meanwhile |
| @@: |
| inc eax |
| shr cl, 1 |
| jnz @r |
| .zero: |
| ret |
| |
| endp |
| |
| proc mpint_cmp uses esi edi ecx, dst, src |
| |
| mov esi, [src] |
| mov edi, [dst] |
| ; start from the high order byte |
| add esi, MPINT_MAX_LEN+4-4 |
| add edi, MPINT_MAX_LEN+4-4 |
| mov ecx, MPINT_MAX_LEN/4 |
| std |
| repe cmpsd |
| cld |
| ret |
| |
| endp |
| |
| proc mpint_mov uses esi edi ecx, dst, src |
| |
| mov esi, [src] |
| mov edi, [dst] |
| mov ecx, MPINT_MAX_LEN/4+1 |
| rep movsd |
| |
| ret |
| |
| endp |
| |
| proc mpint_mov0 uses esi edi ecx eax, dst, src |
| |
| mov esi, [src] |
| mov edi, [dst] |
| mov ecx, [esi] |
| mov eax, ecx |
| neg eax |
| add esi, 4 |
| add edi, 4 |
| rep movsb |
| add eax, MPINT_MAX_LEN |
| jz @f |
| mov ecx, eax |
| xor eax, eax |
| rep stosb |
| @@: |
| |
| ret |
| |
| endp |
| |
| proc mpint_shl1 uses edi ecx eax, dst |
| |
| mov edi, [dst] |
| add edi, 4 |
| mov ecx, MPINT_MAX_LEN/4-1 |
| |
| shl dword[edi], 1 |
| lahf |
| @@: |
| add edi, 4 |
| sahf |
| rcl dword[edi], 1 |
| lahf |
| dec ecx |
| jnz @r |
| sahf |
| |
| ret |
| |
| endp |
| |
| proc mpint_shr1 uses edi ecx eax, dst |
| |
| mov edi, [dst] |
| add edi, MPINT_MAX_LEN+4-4 |
| mov ecx, MPINT_MAX_LEN/4-1 |
| |
| shr dword[edi], 1 |
| lahf |
| @@: |
| sub edi, 4 |
| sahf |
| rcr dword[edi], 1 |
| lahf |
| dec ecx |
| jnz @r |
| sahf |
| |
| ret |
| |
| endp |
| |
| proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift |
| |
| mov ecx, [shift] |
| shr ecx, 3 ; 8 bits in one byte |
| cmp ecx, MPINT_MAX_LEN |
| jge .zero |
| mov esi, [dst] |
| add esi, MPINT_MAX_LEN+4-4 |
| mov edi, esi |
| and ecx, not 11b |
| sub esi, ecx |
| mov edx, MPINT_MAX_LEN/4-1 |
| shr ecx, 2 ; 4 bytes in one dword |
| push ecx |
| sub edx, ecx |
| mov ecx, [shift] |
| and ecx, 11111b |
| std |
| .loop: |
| lodsd |
| mov ebx, [esi] |
| shld eax, ebx, cl |
| stosd |
| dec edx |
| jnz .loop |
| lodsd |
| shl eax, cl |
| stosd |
| |
| ; fill the lsb bytes with zeros |
| pop ecx |
| test ecx, ecx |
| jz @f |
| xor eax, eax |
| rep stosd |
| @@: |
| cld |
| ret |
| |
| .zero: |
| stdcall mpint_zero, [dst] |
| ret |
| |
| endp |
| |
| ; Left shift and copy |
| proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift |
| |
| mov ecx, [shift] |
| shr ecx, 3 ; 8 bits in one byte |
| cmp ecx, MPINT_MAX_LEN |
| jge .zero |
| mov esi, [src] |
| add esi, MPINT_MAX_LEN+4-4 |
| mov edi, [dst] |
| add edi, MPINT_MAX_LEN+4-4 |
| and ecx, not 11b |
| sub esi, ecx |
| mov edx, MPINT_MAX_LEN/4-1 |
| shr ecx, 2 ; 4 bytes in one dword |
| push ecx |
| sub edx, ecx |
| mov ecx, [shift] |
| and ecx, 11111b |
| std |
| .loop: |
| lodsd |
| mov ebx, [esi] |
| shld eax, ebx, cl |
| stosd |
| dec edx |
| jnz .loop |
| lodsd |
| shl eax, cl |
| stosd |
| |
| ; fill the lsb bytes with zeros |
| pop ecx |
| test ecx, ecx |
| jz @f |
| xor eax, eax |
| rep stosd |
| @@: |
| cld |
| ret |
| |
| .zero: |
| stdcall mpint_zero, [dst] |
| ret |
| |
| endp |
| |
| proc mpint_add uses esi edi ecx eax, dst, src |
| |
| mov esi, [src] |
| add esi, 4 |
| mov edi, [dst] |
| add edi, 4 |
| mov ecx, MPINT_MAX_LEN/4 |
| xor ah, ah ; clear flags (Carry flag most importantly) |
| @@: |
| sahf |
| lodsd |
| adc [edi], eax |
| lahf |
| add edi, 4 |
| dec ecx |
| jnz @r |
| sahf |
| |
| ret |
| |
| endp |
| |
| proc mpint_sub uses eax esi edi ecx, dst, src |
| |
| mov esi, [src] |
| add esi, 4 |
| mov edi, [dst] |
| add edi, 4 |
| mov ecx, MPINT_MAX_LEN/4 |
| |
| ; dst = dst + (NOT src) + 1 |
| stc ; Setting CF takes care of the +1 |
| pushf |
| @@: |
| lodsd |
| not eax |
| popf |
| adc [edi], eax |
| pushf |
| add edi, 4 |
| dec ecx |
| jnz @r |
| popf |
| |
| ret |
| |
| endp |
| |
| proc mpint_mul uses esi edi ecx ebx eax, dst, A, B |
| |
| stdcall mpint_zero, [dst] |
| |
| ; first, find the byte in A containing the highest order bit |
| mov ecx, MPINT_MAX_LEN |
| mov edi, [A] |
| add edi, MPINT_MAX_LEN+4-1 |
| std |
| xor al, al |
| repe scasb |
| cld |
| je .zero |
| inc ecx |
| mov al, [edi+1] |
| mov esi, edi |
| mov bl, 8 |
| @@: |
| shl al, 1 |
| jc .first_hit |
| dec bl |
| jnz @r |
| |
| ; Then, starting from this byte, iterate through the bits in A, |
| ; starting from the highest order bit down to the lowest order bit. |
| .next_byte: |
| mov al, [edi] |
| dec edi |
| mov bl, 8 |
| .next_bit: |
| stdcall mpint_shl1, [dst] |
| shl al, 1 |
| jnc .zero_bit |
| .first_hit: |
| stdcall mpint_add, [dst], [B] |
| .zero_bit: |
| dec bl |
| jnz .next_bit |
| dec ecx |
| jnz .next_byte |
| .zero: |
| ret |
| |
| endp |
| |
| proc mpint_mod uses eax ecx, dst, mod |
| |
| ; if mod is zero, return |
| stdcall mpint_zero?, [mod] |
| jz .zero |
| |
| stdcall mpint_cmp, [mod], [dst] |
| jb .done ; if dst < mod, dst = dst |
| je .zero ; if dst == mod, dst = 0 |
| |
| ; left shift mod until the high order bits of mod and dst are aligned |
| stdcall mpint_hob, [dst] |
| mov ecx, eax |
| stdcall mpint_hob, [mod] |
| sub ecx, eax |
| stdcall mpint_shlmov, mpint_tmp, [mod], ecx |
| inc ecx |
| |
| ; For every bit in dst (starting from the high order bit): |
| .loop: |
| ; determine if dst is bigger than mpint_tmp |
| stdcall mpint_cmp, [dst], mpint_tmp |
| ja @f |
| ; if so, subtract mpint_tmp from dst |
| stdcall mpint_sub, [dst], mpint_tmp |
| @@: |
| dec ecx |
| jz .done |
| ; shift mpint_tmp right by 1 |
| stdcall mpint_shr1, mpint_tmp |
| jmp .loop |
| |
| .zero: |
| stdcall mpint_zero, [dst] |
| .done: |
| ret |
| |
| endp |
| |
| proc mpint_modexp uses edi eax ebx ecx, dst, base, exp, mod |
| |
| ; If mod is zero, return |
| stdcall mpint_zero?, [mod] |
| jz .mod_zero |
| |
| ; Find the highest order byte in exponent |
| mov edi, [exp] |
| mov ecx, [edi] |
| lea edi, [edi + 4 + ecx - 1] |
| ; Find the highest order bit in this byte |
| mov al, [edi] |
| test al, al |
| jz .invalid |
| mov bl, 9 |
| @@: |
| dec bl |
| shl al, 1 |
| jnc @r |
| |
| ; Initialise result to base, to take care of the highest order bit |
| stdcall mpint_mov0, [dst], [base] |
| dec bl |
| jz .next_byte |
| .bit_loop: |
| ; For each bit, square result |
| stdcall mpint_mov, mpint_tmp, [dst] |
| stdcall mpint_mul, [dst], mpint_tmp, mpint_tmp |
| stdcall mpint_mod, [dst], [mod] |
| |
| ; If the bit is set, multiply result by the base |
| shl al, 1 |
| jnc .next_bit |
| stdcall mpint_mov, mpint_tmp, [dst] |
| stdcall mpint_mul, [dst], [base], mpint_tmp |
| stdcall mpint_mod, [dst], [mod] |
| .next_bit: |
| dec bl |
| jnz .bit_loop |
| .next_byte: |
| dec ecx |
| jz .done |
| dec edi |
| mov al, [edi] |
| mov bl, 8 |
| jmp .bit_loop |
| .done: |
| ret |
| |
| .mod_zero: |
| DEBUGF 1, "modexp with modulo 0\n" |
| ; if mod is zero, result = 0 |
| stdcall mpint_zero, [dst] |
| ret |
| |
| .exp_zero: |
| DEBUGF 1, "modexp with exponent 0\n" |
| ; if exponent is zero, result = 1 |
| stdcall mpint_zero, [dst] |
| mov eax, [dst] |
| mov byte[eax], 1 |
| mov byte[eax+4], 1 |
| ret |
| |
| .invalid: |
| DEBUGF 1, "modexp: Invalid input!\n" |
| ret |
| |
| endp |