BlueGreycalmElegant

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /programs/network/ssh/mpint.inc @ 6469

  → /programs/network/ssh/mpint.inc @ 6922

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Regard whitespace Rev 6469 → Rev 6922

/programs/network/ssh/mpint.inc
1,6 → 1,6
; mpint.inc - Multi precision integer procedures
;
; Copyright (C) 2015-2016 Jeffrey Amelynck
; Copyright (C) 2015-2017 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
15,11 → 15,27
; You should have received a copy of the GNU General Public License
; along with this program. If not, see <http://www.gnu.org/licenses/>.
; Notes:
;
; These procedures work only with positive integers.
; For compatibility reasons, the highest bit must always be 0.
; However, leading 0 bytes MUST at all other times be omitted.
;
; You have been warned!
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:
;;===========================================================================;;
proc mpint_to_little_endian uses esi edi ecx ;///////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Convert big endian MPINT to little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> esi = pointer to big endian MPINT ;;
;> edi = pointer to buffer for little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = MPINT number length ;;
;;===========================================================================;;
; Load length dword
lodsd
43,38 → 59,34
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:
endp
;;===========================================================================;;
proc mpint_to_big_endian uses esi edi ecx ;//////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Convert little endian MPINT to big endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> esi = pointer to little endian MPINT ;;
;> edi = pointer to buffer for big endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = MPINT number length ;;
;;===========================================================================;;
; Load length dword
lodsd
test eax, eax
jz .zero
mov ecx, eax
add esi, ecx
add esi, eax
dec esi
test byte[esi], 0x80 ; Is the highest bit set?
jz @f
inc eax
@@:
push eax
push eax ; we'll return length to the caller later
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
86,30 → 98,20
ret
.zero:
stosd
stosd ; Number 0 has 0 data bytes
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
;;===========================================================================;;
proc mpint_print uses ecx esi eax, src ;/////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Print MPINT to the debug board. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< - ;;
;;===========================================================================;;
DEBUGF 1, "0x"
mov esi, [src]
135,96 → 137,100
endp
proc mpint_zero uses edi ecx eax, dst
;;===========================================================================;;
proc mpint_hob uses edi ecx eax, dst ;///////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Return an index number giving the position of the highest order bit. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< eax = highest order bit number ;;
;;===========================================================================;;
mov edi, [dst]
xor eax, eax
mov ecx, MPINT_MAX_LEN/4+1
rep stosd
lodsd
dec eax ; total length minus one
mov cl, [edi+eax] ; load the highest order byte
shl eax, 3 ; multiply eax by 8 to get nr of bits
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
; Now shift bits of the highest order byte right, until the byte reaches zero, counting bits meanwhile
test cl, cl
jz .end
@@:
inc eax
shr cl, 1
jnz @r
.zero:
.end:
ret
endp
proc mpint_cmp uses esi edi ecx, dst, src
;;===========================================================================;;
proc mpint_cmp uses esi edi ecx eax, dst, src ;//////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Compare two mpints. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< flags are set as for single precision CMP instruction ;;
;;===========================================================================;;
; First, check if number of significant bytes is the same
; If not, number with more bytes is bigger
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
mov ecx, [esi]
cmp ecx, [edi]
jne .got_answer
; Numbers have equal amount of bytes, compare starting from the high order byte
add edi, ecx
add esi, ecx
std
.do_byte:
test ecx, 11b
jz .do_dword
dec esi
dec edi
cmpsb
jne .got_answer
dec ecx
jmp .do_byte
.do_dword:
shr ecx, 2
jz .got_answer
sub esi, 4
sub edi, 4
repe cmpsd
.got_answer:
cld
ret
endp
proc mpint_mov uses esi edi ecx, dst, src
;;===========================================================================;;
proc mpint_mov uses esi edi ecx, dst, src ;//////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Copy mpint. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to buffer for little endian MPINT ;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = src ;;
;;===========================================================================;;
mov esi, [src]
mov edi, [dst]
mov ecx, MPINT_MAX_LEN/4+1
mov ecx, [esi]
push ecx
shr ecx, 2
inc ecx ; for length dword
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
pop ecx
and ecx, 11b
jz @f
rep movsb
add eax, MPINT_MAX_LEN
jz @f
mov ecx, eax
xor eax, eax
rep stosb
@@:
ret
231,49 → 237,95
endp
proc mpint_shl1 uses edi ecx eax, dst
;;===========================================================================;;
proc mpint_shl1 uses esi ecx, dst ;//////////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Shift little endian MPINT one bit to the left. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = dst SHL 1 ;;
;;===========================================================================;;
mov edi, [dst]
add edi, 4
mov ecx, MPINT_MAX_LEN/4-1
mov esi, [dst]
mov ecx, [esi]
test ecx, ecx
jz .done
shl dword[edi], 1
lahf
; Test if high order byte will overflow
; Remember: highest bit must never be set for positive numbers!
test byte[esi+ecx+3], 11000000b
jz @f
; We must grow a byte in size!
; TODO: check for overflow
inc ecx
mov [esi], ecx
mov byte[esi+ecx+3], 0 ; Add the new MSB
@@:
add edi, 4
sahf
rcl dword[edi], 1
lahf
add esi, 4
; Do the lowest order byte first
shl byte[esi], 1
dec ecx
jz .done
; And the remaining bytes
@@:
inc esi
rcl byte[esi], 1
dec ecx
jnz @r
sahf
.done:
ret
endp
proc mpint_shr1 uses edi ecx eax, dst
;;===========================================================================;;
proc mpint_shr1 uses edi ecx, dst ;//////////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Shift little endian MPINT one bit to the right. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = dst SHR 1 ;;
;;===========================================================================;;
mov edi, [dst]
add edi, MPINT_MAX_LEN+4-4
mov ecx, MPINT_MAX_LEN/4-1
mov ecx, [edi]
test ecx, ecx
jz .done
shr dword[edi], 1
lahf
; Do the highest order byte first
dec ecx
shr byte[edi+ecx+3], 1
; Was it 0? If so, we must decrement total length
jnz @f
jc @f
mov [edi], ecx
@@:
sub edi, 4
sahf
rcr dword[edi], 1
lahf
dec ecx
test ecx, ecx
jz .done
; Now do the trailing bytes
add edi, 4
add edi, ecx
@@:
dec edi
rcr byte[edi], 1
dec ecx ; does not affect carry flag, hooray!
jnz @r
sahf
.done:
ret
endp
proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift
;;===========================================================================;;
proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift ;////////////////////;;
;;---------------------------------------------------------------------------;;
;? Left shift little endian MPINT by x bits. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;> shift = number of bits to shift the MPINT ;;
;;---------------------------------------------------------------------------;;
;< - ;;
;;===========================================================================;;
mov ecx, [shift]
shr ecx, 3 ; 8 bits in one byte
313,13 → 365,23
ret
.zero:
stdcall mpint_zero, [dst]
mov eax, [dst]
mov dword[eax], 0
ret
endp
; Left shift and copy
proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift
;;===========================================================================;;
proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift ;////////////;;
;;---------------------------------------------------------------------------;;
;? Left shift by x bits and copy little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;> dst = pointer to little endian MPINT ;;
;> shift = number of bits to shift the MPINT to the left ;;
;;---------------------------------------------------------------------------;;
;< dst = src SHL shift ;;
;;===========================================================================;;
mov ecx, [shift]
shr ecx, 3 ; 8 bits in one byte
360,67 → 422,170
ret
.zero:
stdcall mpint_zero, [dst]
mov eax, [dst]
mov dword[eax], 0
ret
endp
proc mpint_add uses esi edi ecx eax, dst, src
;;===========================================================================;;
proc mpint_add uses esi edi ecx eax, dst, src ;//////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Add a little endian MPINT to another little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = dst + src ;;
;;===========================================================================;;
mov esi, [src]
add esi, 4
mov edi, [dst]
mov ecx, [esi] ; source number length
sub ecx, [dst]
jbe .length_ok
; Length of the destination is currently smaller then the source, pad with 0 bytes
add edi, [edi]
add edi, 4
mov ecx, MPINT_MAX_LEN/4
xor ah, ah ; clear flags (Carry flag most importantly)
@@:
sahf
lodsd
adc [edi], eax
lahf
mov al, 0
rep stosb
.length_ok:
mov ecx, [esi]
mov edi, [dst]
add esi, 4
add edi, 4
; Add the first byte
lodsb
add byte[edi], al
dec ecx
jz .done
; Add the other bytes
@@:
inc edi
lodsb
adc byte[edi], al
dec ecx
jnz @r
sahf
.done:
; check if highest bit OR carry flag is set
; if so, add a byte if we have the buffer space
; TODO: check if we have the buffer space
jc .carry
cmp byte[edi], 0x80
jnz .high_bit_set
ret
.carry:
inc edi
mov byte[edi], 1
mov eax, [dst]
inc dword[eax]
ret
.high_bit_set:
inc edi
mov byte[edi], 0
mov eax, [dst]
inc dword[eax]
ret
endp
proc mpint_sub uses eax esi edi ecx, dst, src
;;===========================================================================;;
proc mpint_sub uses eax esi edi ecx, dst, src ;//////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Subtract a little endian MPINT to another little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;> dst = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = dst - src ;;
;;===========================================================================;;
mov esi, [src]
mov edi, [dst]
mov ecx, [esi] ; destination number length
cmp ecx, [edi]
ja .overflow
add esi, 4
mov edi, [dst]
add edi, 4
mov ecx, MPINT_MAX_LEN/4
.loop:
lodsd
sub [edi], eax
jnc @f
dec dword [edi+4]
; Subtract the first byte
lodsb
sub byte[edi], al
dec ecx
jz .done
; Subtract the other bytes
@@:
add edi, 4
inc edi
lodsb
sbb byte[edi], al
dec ecx
jnz .loop
jnz @r
.done:
stdcall mpint_shrink, [dst]
ret
.overflow:
mov dword[edi], 0
stc
ret
endp
proc mpint_mul uses esi edi ecx ebx eax, dst, A, B
stdcall mpint_zero, [dst]
;;===========================================================================;;
proc mpint_shrink uses eax edi ecx, dst ;////////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Get rid of leading zeroes on a little endian MPINT. ;;
;;---------------------------------------------------------------------------;;
;> src = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< ;;
;;===========================================================================;;
; 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
mov edi, [dst]
lodsd
std
mov ecx, eax
dec eax ; total length minus one
add edi, eax
xor al, al
repe scasb
repe cmpsb
inc ecx
mov edi, [dst]
mov [edi], ecx
cld
je .zero
inc ecx
ret
endp
;;===========================================================================;;
proc mpint_mul uses esi edi ecx ebx eax, dst, A, B ;/////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Multiply to little endian MPINTS and store them in a new one. ;;
;;---------------------------------------------------------------------------;;
;> A = pointer to little endian MPINT ;;
;> B = pointer to little endian MPINT ;;
;> dst = pointer to buffer for little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = A * B ;;
;;===========================================================================;;
; Set result to zero
mov eax, [dst]
mov dword[eax], 0
; first, find the byte in A containing the highest order bit
mov edi, [A]
mov eax, [edi]
test eax, eax
jz .zero
add edi, eax
mov al, [edi+1]
mov esi, edi
mov bl, 8
452,50 → 617,83
endp
proc mpint_mod uses eax ecx, dst, mod
;;===========================================================================;;
proc mpint_mod uses eax ebx ecx, dst, mod ;//////////////////////////////////;;
;;---------------------------------------------------------------------------;;
;? Find the modulo (remainder after division) of dst by mod. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to little endian MPINT ;;
;> mod = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = dst MOD mod ;;
;;===========================================================================;;
locals
mpint_tmp rb MPINT_MAX_LEN+4
endl
; if mod is zero, return
stdcall mpint_zero?, [mod]
jz .zero
mov eax, [mod]
cmp dword[eax], 0
je .zero
stdcall mpint_cmp, [mod], [dst]
stdcall mpint_cmp, eax, [dst]
jb .done ; if dst < mod, dst = dst
je .zero ; if dst == mod, dst = 0
lea ebx, [mpint_tmp]
; 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
stdcall mpint_shlmov, ebx, [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
stdcall mpint_cmp, [dst], ebx
ja @f
; if so, subtract mpint_tmp from dst
stdcall mpint_sub, [dst], mpint_tmp
stdcall mpint_sub, [dst], ebx
@@:
dec ecx
jz .done
; shift mpint_tmp right by 1
stdcall mpint_shr1, mpint_tmp
stdcall mpint_shr1, ebx
jmp .loop
.zero:
stdcall mpint_zero, [dst]
mov eax, [dst]
mov dword[eax], 0
.done:
ret
endp
proc mpint_modexp uses edi eax ebx ecx, dst, base, exp, mod
;;===========================================================================;;
proc mpint_modexp uses edi eax ebx ecx edx, dst, base, exp, mod ;////////////;;
;;---------------------------------------------------------------------------;;
;? Find the modulo (remainder after division) of dst by mod. ;;
;;---------------------------------------------------------------------------;;
;> dst = pointer to buffer for little endian MPINT ;;
;> base = pointer to little endian MPINT ;;
;> exp = pointer to little endian MPINT ;;
;> mod = pointer to little endian MPINT ;;
;;---------------------------------------------------------------------------;;
;< dst = base ** exp MOD mod ;;
;;===========================================================================;;
locals
mpint_tmp rb MPINT_MAX_LEN+4
endl
; If mod is zero, return
stdcall mpint_zero?, [mod]
jz .mod_zero
mov eax, [mod]
cmp dword[eax], 0
je .mod_zero
; Find the highest order byte in exponent
mov edi, [exp]
511,21 → 709,22
shl al, 1
jnc @r
lea edx, [mpint_tmp]
; Initialise result to base, to take care of the highest order bit
stdcall mpint_mov0, [dst], [base]
stdcall mpint_mov, [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_mov, edx, [dst]
stdcall mpint_mul, [dst], edx, edx
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_mov, edx, [dst]
stdcall mpint_mul, [dst], [base], edx
stdcall mpint_mod, [dst], [mod]
.next_bit:
dec bl
543,15 → 742,15
.mod_zero:
DEBUGF 3, "modexp with modulo 0\n"
; if mod is zero, result = 0
stdcall mpint_zero, [dst]
mov eax, [dst]
mov dword[eax], 0
ret
.exp_zero:
DEBUGF 3, "modexp with exponent 0\n"
; if exponent is zero, result = 1
stdcall mpint_zero, [dst]
mov eax, [dst]
mov byte[eax], 1
mov dword[eax], 1
mov byte[eax+4], 1
ret