RSA make key

KREIRANJE RSA KLJUČA

1.	Izmislimo si 2 praštevili p in q. Za kateri velja p !=q. Za primer vzemimo p =11 in q =17.

2.	Izračunamo n=p*q. V našem primeru n = 11*17=187

3.	Izračunamo Фn= (p-1)*(q-1). Pri nas Фn = (11-1)*(17-1)=160


4.	Izberemo e, pri tem pazimo (e, Фn)=1, to pomeni da si morata biti e in Фn tuji števili. Se pravi edini delitelj, ki si ga delita je samo 1. Jaz sem izbral 9. (uporaba programa [PHP] RSA javni kjuc)

5.	Z uporabo razširjenega Evklidovega algoritma izračunamo Y.

(uporaba programa [PHP] RSA make key)

Pri tem predpostavimo:
E*d mod Фn = 1
9*d mod 160 =1

Zapišemo v obliki algoritma:
160x + 9y = 1

160 = 17*9+7
9=1*7+2
7=3*2+1

Sedaj izrazimo ostane:
160 – 17*9 = 7
9 – 1*7 = 2
7 – 3*2 = 1

Začnemo z spodnjim izrazom:
7 – 3*2 = 1

Namesto 2 ustavimo izraz (9-1*7):
7 – 3*(9-1*7) = 1

7 – 3*9 + 3*7 = 1
4*7 – 3*9 = 1

Postopek ponovimo za 7:
4*(160-17*9) – 3*9 = 1
4* 160 – 68*9 – 3*9 = 1
4*160 – 71*9 = 1

Iz zgornje enačbe je razvidno da je:
X = 4; Y = -71

6.	Sedaj se pojavita 2 možnosti:

a)	Če je Y manjši od 0 (Y<0):
d = Фn + Y

V našem primeru:
D = 160 -71
D = 89

b)	Če je Y večji od 0 (Y>0):
D = Y

7.	Sedaj imamo javni in zasebni ključ:

a)Javni ključ (n,e): n=187, e = 9
b)Zasebni ključ(n,d): n=187, d=89

Zasebni ključ in praštevili, ki smo jih izbrali na začetku hranimo v tajnosti, saj z praštevili lahko izračunaš zasebni ključ, z njim pa lahko dekodiraš kodirano sporočilo.