; file: small_rsa.asm
; who:  Marcus Fritzsch <mATfritschy-DOTde>
; when: 20050208
; desc: sample implementation of the RSA algorithm using _REALLY_ small
;       primes
; note: JUST FOR FUN!
;
; nasm -f elf mini_rsa.asm && ld mini_rsa.o -o mini_rsa

%define _O_RDONLY 0

%ifndef PRIM_MASK
  %define PRIM_MASK 0xff
%endif

%ifndef RSA_E_BASE
	%define RSA_E_BASE 0xf1
%endif

global _start

segment .bss
_numbuf	resb		35		; number conversion strings will go here

_rnd_seed	resd 1

; rsa context
_rsa_ctx_p	resd 1		; first prime, P
_rsa_ctx_q	resd 1		; secnd prime, Q
_rsa_ctx_n	resd 1		; PQ
_rsa_ctx_m	resd 1		; (P-1)(Q-1)
_rsa_ctx_e	resd 1		; E, public key
_rsa_ctx_d	resd 1		; D, private key

_ciphertext resd 1
_decrypted  resd 1

segment .data
_rnd_magic0	dd 1103515245
_rnd_magic1	dd 12345
_rnd_inited	dd 0
_rnd_devrandom	db "/dev/urandom", 0

_nl db 10, 0
_sp db " ", 0
_ar db "-> ", 0

_what dd 10

segment .text
_start:
	call small_rsa_init

	push dword [_what]
	call small_rsa_encrypt
	mov dword [_ciphertext], eax

	push eax
	call small_rsa_decrypt
	mov dword [_decrypted], eax

	push dword [_what]
	call putsint
	push _ar
	call puts

	push dword [_ciphertext]
	call putsint
	push _ar
	call puts

	push dword [_decrypted]
	call putsint

	push _nl
	call puts

	xor eax, eax
	push eax
	call exit

putsint:
	enter 0,0

	push dword [ebp+8]
	call istr
	push eax
	call puts
	push _sp
	call puts

	leave
	ret

; func:     small_rsa_encrypt, encrypt arg1 by the current rsa ctx
; params:   arg1:uint
; destroys: eax
small_rsa_encrypt:
	enter 0,0

	push dword [ebp+8]
	push dword [_rsa_ctx_e]
	push dword [_rsa_ctx_n]
	call ipowm
	add esp, 12

	leave
	ret

; func:     small_rsa_decrypt, decrypt arg1 by the current rsa ctx
; params:   arg1:uint
; destroys: eax
small_rsa_decrypt:
	enter 0,0

	push dword [ebp+8]
	push dword [_rsa_ctx_d]
	push dword [_rsa_ctx_n]
	call ipowm
	add esp, 12

	leave
	ret

; func:     ipowm, compute (bas ** exp) % mod
; params:   bas:uint, exp:uint, mod:uint
; destroys: eax
ipowm:
%define bas ebp+16
%define exp ebp+12
%define mod ebp+8
	enter 0,0
	push ebx
	push ecx
	push edx
	push edi

	mov ecx, [exp]
	mov eax, 1

	mov ebx, [bas]
	mov edi, [mod]

.loop:
	mul ebx
	div edi
	mov eax, edx
	loop .loop

	pop edi
	pop edx
	pop ecx
	pop ebx
	leave
	ret
%undef bas
%undef exp
%undef mod

; func:     small_rsa_init, init small_rsa state
; args:     -
; destroys: eax
small_rsa_init:
	enter 0,0
	push ebx
	push ecx
	push edx

.genprimes:
	; P = getptime (0x1ff);
	push PRIM_MASK
	call getprime
	mov dword [_rsa_ctx_p], eax
	add esp, 4

	; HACK, reinit RNG
	call rnd_init_random

	; Q = getprime (0x1ff);
	push PRIM_MASK
	call getprime
	add esp, 4

	; if (Q == P)
	cmp eax, dword [_rsa_ctx_p]
	jz .genprimes
	mov dword [_rsa_ctx_q], eax

	; calculate N = PQ
	mov eax, dword [_rsa_ctx_q]
	mul dword [_rsa_ctx_p]
	mov dword [_rsa_ctx_n], eax

	; calculate M = (P-1)*(Q-1)
	push dword [_rsa_ctx_p]
	push dword [_rsa_ctx_q]
	call phi
	add esp, 8
	mov dword [_rsa_ctx_m], eax

	; calculate E
	call small_rsa_calc_e
	mov dword [_rsa_ctx_e], eax

	; calculate D
	call small_rsa_calc_d
	mov dword [_rsa_ctx_d], eax

	xor eax, eax

	pop edx
	pop ecx
	pop ebx
	leave
	ret

; func:     small_rsa_calc_d, calculate D for RSA ctx
;           D is also known as the mod inverse of (E, M)
; params:   -
; destroys: eax
small_rsa_calc_d:
	enter 0,0
	push ebx
	push ecx
	push edx

	; while ((x*m + 1) % e) ++x;
	; d = (x*m + 1) / e;
	mov eax, 2
.loop:
	mov ebx, eax
	mul dword [_rsa_ctx_m]
	inc eax
	xor edx, edx
	div dword [_rsa_ctx_e]
	mov ecx, edx

	jecxz .end

	mov eax, ebx
	add eax, 2
	jmp .loop

.end:
	mov eax, ebx
	mul dword [_rsa_ctx_m]
	xor edx, edx
	inc eax
	div dword [_rsa_ctx_e]

	pop edx
	pop ecx
	pop ebx
	leave
	ret

; func:     small_rsa_calc_e, calculate E for RSA ctx
;           E and (P-1)(Q-1) must be relatively prime
; params:   -
; destroys: eax
small_rsa_calc_e:
	enter 0,0
	push ebx

	mov ebx, RSA_E_BASE
.loop:
	push ebx
	push dword [_rsa_ctx_m]
	call gcd
	add esp, 8
	cmp eax, 1
	jz .end
	add ebx, 2
	jmp .loop
.end:
	mov eax, ebx

	pop ebx
	leave
	ret

; func:     getprime, return prime of about arg1 bits size
; args:     size:uint
; destroys: eax
getprime:
	enter 0,0
	push ebx

	mov ecx, dword [ebp+8]
	mov ebx, ecx
	shr ebx, 1
.loop:
	call get_rand_int

	; check that eax is nearly as big as the mask
	and eax, ecx
	cmp eax, ebx
	jl .loop

	push eax
	call isprime
	add esp, 4

	test eax, eax
	jnz .end

	jmp .loop

.end:
	pop ebx
	leave
	ret

; func:     phi, compute (arg1-1)*(arg2-1)
; args:     p:uint, q:uint
; destroys: eax
phi:
%define p ebp+12
%define q ebp+8
	enter 0,0
	push edx

	mov eax, dword [p]
	dec eax
	dec dword [q]
	mul dword [q]

	pop edx
	leave
	ret
%undef p
%undef q

; func:     gcd, compute the greatest common divisor of arg1 and arg2
; args;     a:uint, b:uint
; destroys: eax
gcd:
%define a ebp+12
%define b ebp+8
	enter 0,0
	push ebx
	push ecx
	push edx

	mov eax, [a]
	mov ebx, [b]

	; if aor b is negative, correct it
	cmp eax, 0
	jge .next
	neg eax
.next:
	cmp ebx, 0
	jge .loop
	neg ebx

.loop:
	; v = a % b
	xor edx, edx
	div ebx
	test edx, edx
	; if (!v) return ...;
	jz .end

	mov ecx, ebx
	; b = v
	mov ebx, edx
	; a = b
	mov eax, ecx
	jmp .loop

.end:
	mov eax, ebx

	pop edx
	pop ecx
	pop ebx
	leave
	ret
%undef a
%undef b

; func:     get_rand_int, return random pos. integer by the expression
;           _rnd_seed = _rnd_seed * _rnd_magic0 + _rnd_magic1
; params:   -
; destroys: eax
get_rand_int:
	push edx

	; if (! _rnd_inited)
	mov eax, dword [_rnd_inited]
	test eax, eax
	jnz .lbl1

	call rnd_init_random

.lbl1:
	mov eax, [_rnd_seed]
	mul dword [_rnd_magic0]
	add eax, [_rnd_magic1]
	mov dword [_rnd_seed], eax
	and eax, 0x7fffffff

	pop edx
	ret

; func:     rnd_init_random, initialize _rnd_seed by reading random data
;           from /dev/random
; params:   -
; destroys: eax
rnd_init_random:
%define fd    [ebp-4]
	enter 8,0
	push ebx
	push ecx
	push edx

	; fd = open ("/dev/random", O_RDONLY);
	mov eax, 5 ; open
	lea ebx, [_rnd_devrandom]
	mov ecx, _O_RDONLY
	xor edx, edx
	int 0x80

	; if (fd < 0)
	cmp eax, -1
	jz .error2

	mov dword fd, eax

	; bytes = read (fd, mbuf, 5);
	mov eax, 3
	mov ebx, fd
	lea ecx, [_rnd_seed]
	mov edx, 4
	int 0x80

	; if (bytes < 4)
	cmp eax, 4
	jl .error1

	mov eax, 6 ; close
	mov ebx, fd
	int 0x80

	inc dword [_rnd_inited]

	jmp .end

.error1:
	mov eax, 6 ; close
	mov ebx, fd
	int 0x80
.error2:
	call rnd_init_time
.end:
	pop edx
	pop ecx
	pop ebx
	leave
	ret
%undef fd

; func:     rnd_init_time, initialize _rnd_seed by time ()
; params:   -
; destroys: eax
rnd_init_time:
	push ebx
	mov eax, 13	; time
	xor ebx, ebx
	int 0x80

	mov dword [_rnd_seed], eax

	inc dword [_rnd_inited]
	pop ebx
	ret

; func:     isprime
; args:     arg1:int
; desc:     determines if arg1 is prime, on prime return arg1 else 0
; clobbers: eax
isprime:
	enter 0,0
	push ebx
	push ecx
	push edx
	push edi

	mov ebx, [ebp+8]

	; if (n < 2)
	cmp ebx, 2
	;   return 0;
	jl .false
	jz .true

	test ebx, 1
	jz .false

	; si = isqrt (n)
	push ebx
	call isqrt
	add esp, 4
	mov edi, eax

	; j = 2
	xor ecx, ecx
	inc ecx

.loop:
	; ++j;
	inc ecx

	; if (n % j == 0) return 0;
	xor edx, edx
	mov eax, ebx
	div ecx
	test edx, edx
	jz .false

	; if (j <= si) continue;
	cmp ecx, edi
	jle .loop
	; else return 1;
	jmp .true

.fast:
	mov eax, [ebp+8]
	jmp .end
.false:
	; return 0;
	xor eax, eax
	jmp .end
.true:
	; return n;
	mov eax, ebx
.end:
	pop edi
	pop edx
	pop ecx
	pop ebx
	leave
	ret

; func:     isqrt
; args:     arg1:int
; desc:     return int sqrt (arg1)
; clobbers: eax
isqrt:
	enter 0,0
	push ebx
	push ecx
	push edx
	push edi

	mov edi, [ebp+8]

	;mov dword j, 0
	xor ebx, ebx
	mov ecx, 0x4000

.loop:
	; k = (j+i) * (j+i);
	mov eax, ebx
	add eax, ecx
	mul eax

	; if (k <= n)
	cmp eax, edi
	jg .next
	;   j += i;
	add ebx, ecx

.next:
	; if (k == n)
	cmp eax, edi
	;   break
	je .end

	; if (i == 0) break
	jecxz .end

	; i >>= 1
	shr ecx, 1
	jmp .loop

.end:
	; return j
	mov eax, ebx

	pop edi
	pop edx
	pop ecx
	pop ebx
	leave
	ret

; func:     istr, return the integer as a decimal string
; params:   num:int
; destroys: eax
istr:
%define num ebp+8
%define sign ebp-1
%define rbuf ebp-14
	enter 16,0
	push ebx
	push ecx
	push edx
	push edi

	mov byte [sign], 0
	cmp dword [num], 0
	jnl .continue

	inc byte [sign]
	neg dword [num]

.continue
	mov edi, 10
	xor ecx, ecx
	mov eax, [num]

.loop:
	xor edx, edx
	div edi
	add dl, '0'
	mov byte [rbuf+ecx], dl
	mov byte [rbuf+ecx+1], 0

	inc ecx
	or eax, eax
	jnz .loop

	xor ebx, ebx
	inc ecx

	mov al, [sign]
	or al, al
	jz .reverse

	mov byte [rbuf+ecx-1], '-'
	mov byte [rbuf+ecx], 0

.reverse
	mov dl, [rbuf+ecx-1]
	mov byte [_numbuf+ebx], dl
	inc ebx
	mov byte [_numbuf+ebx], 0
	loop .reverse

	mov byte [_numbuf+eax], 0
	lea eax, [_numbuf]
	inc eax	; NASTY: need to eliminate this first 0!!!

	pop edi
	pop edx
	pop ecx
	pop ebx
	leave
	ret
%undef num
%undef rbuf
%undef sign

; func:     puts, put str to stdout
; params:   strp:ptr to string - zero terminated
; destroys: -
puts:
%define strp ebp+8
	enter 4,0
	push eax
	push ebx
	push ecx
	push edx

	; determine the length
	push dword [strp]
	call strlen
	add esp, 4
	mov edx, eax

	mov eax, 4
	mov ebx, 0
	mov ecx, [strp]
	; eax is set after call to strlen
	int 0x80

	pop edx
	pop ecx
	pop ebx
	pop eax
	leave
	ret

; func:     strlen, determine the length of a 0 terminated string
; params:		str:char* - zero terminated
; destroys: eax
strlen:
%define str ebp+8
	enter 0,0
	push edi

	mov edi, [str]         ; ptr to str
	mov ecx, 0xffffffff    ; largest possible value
	xor al, al
	cld

	repnz scasb            ; scan for terminating zero

	mov eax, 0xfffffffe    ; repnz goes one step too far, use -2
	sub eax, ecx

	pop edi
	leave
	ret

exit:
	enter 0,0
	mov eax, 1
	mov ebx, [ebp+8]
	int 0x80