Kafedra: Kibertəhlükəsizlik

Azərbaycan Respublikası Elm və Təhsil Nazirliyi
Azərbaycan Texniki Universiteti

Kafedra: Kibertəhlükəsizlik

Falüktə: İnformasiya və Telekommunikasiya Texnologiyaları
Fənn: Kriptoqrafiyanın Əsasları
İxtisas: 050615- İnformasiya Təhlükəsizliyi
Qrup: 640a2
Kurs: 3

Laboratoriya işi 4

Müəllim: Hüseynli Məhəmməd
Tələbə: Həsənov Rəvan


RSA alqoritmi.Böyük sadə ədədlər və sadə ədəd testləri
RSA alqoritmi.
RSA (Rivest, Shamir və Adleman soyadlarından abbreviatura) – açıq açarlı kriptoqrafik alqoritm, böyük tam ədədlərin sübutu probleminin hesablama mürəkkəbliyinə əsaslanır. RSA açıq açarı ilə açılan kriptoqrafiq sistemlərin 2 böyük sadə ədədin təsvirinin əsasında mürəkkəb faktor məsələsi durur. Şifrələmə əməliyyatı üçün böyük ədədin modulunu qüvvətə yüksəltmə əməliyyatı yerinə yetirilir. İstənilən vaxtdan sonra deşifrələmə üçün Eyler funksiyasından istifadə edərək böyük ədədin sadə vuruqlara ayırmaq lazımdır.
Açıq açarlı kriptoqrafik sistemdə hər iştirakçı həm şifrələmə, həm də deşifrələmə əməliyyatını yerinə yeritə bilər.
RSA açarları aşağıdakı qayda ilə əmələ gəlir:
1. Verilmiş ölçülərdə təsadüfi 2 müxtəlif sadə ədəd p və q seçilir.
2. Modul adlanan onların hasili hesablanır.
3. ədədindən Eyler funksiyası hesablanır :

4. funksiyasının mənası ilə 1 < e < Φ(n) tam ədədi seçilir.
5. modulundan e ədədinə əks olan d ədədi hesablanır.
Yəni : d*e ≡ 1 (d*e mod Φ(n) = 1)
6.  cütlüyü RSA-nın açıq açarı kimi istifadə olunur.
7. cütlüyü RSA-nın məxfi açarı rolunu oynayır və həmişə gizli saxlanılır .
Şifrləmə m məlumatı şifrlənir (m < n tam ədəddir): c = E(m) = m^e mod n.
Deşifrləmə: c şifrmətni deşifrlənir: m = D(c) = c^d mod n.
Misal
İlk olaraq qaydaya uyğun p və q qarşılıqlı sadə ədədlərini tapaq.

1. 
   p=5, q=8
   
2. 
   Sistemin modulu və Eyler funksiyası
   

n=p*q (n)=(p-1)(q-1)
n=5*8 (n)=(5-1)(8-1)
n=40 (n)=4*7
(n)=28

3. 
   1<e<(n) şərtini ödəyən və (n) ilə qarşılıqlı sadə olan e ədədi seçək. O zaman e ədədinə 5 rəqəmini verək.
   

1<e<28 e=5

4. 
   ed = 1 (mod (n)), 1 < d < (n) şərtlərini ödəyən d ədədi hesablayaq. E 5 olduğuna görə d-ni tapaq.
   

5*d=1
5*d=1
d= 17

5. 
   (d, n) ədədlər cütü gizli açar, (e, n) ədədlər cütü açıq açar olduğuna görə:
   

(d,n)  (17,40) (e,n)  (5,40)

Şifrləmə m məlumatı şifrlənir (m < n tam ədəddir): c = E(m) = m^e mod n.
m=3
c = E(m) = m^e mod n.
c = E(m) = 3⁵ mod 40.
c = 243mod40
c = 243/40=6(qalıq 3)
c=3
Deşifrləmə c şifrmətni deşifrlənir. Düsturu yazaq.
m = D(c) = c^d mod n.
m=d(c)=3¹⁷mod40
m=d(c)=129.140.163mod40
m=d(c)=129.140.163/40=3.228.504(qalıq 3)
m=3
Sadə ədədlərin generasiyası
Tutaq ki, n = 221- in sadə olub olmadığını müəyyən etmək istəyirik .
Biz n −1 -i
2² *55 kimi yazırıq ki, s = 2 və d = 55 olsun. Təsadüfi olaraq a rəqəmini seçirik ki,
1 < a < n - 1, deyək ki, a = 174. Hesablamağa davam edirik:
A^{2 0} · d mod n = 174 55 mod 221 = 47 ≠ 1, n − 1
A^{2 1}· d mod n = 174 110 mod 221 = 220 = n − 1.
220 ≡ −1 mod n olduğundan , ya 221 əsas, ya da 174 221 üçün güclü yalançıdır. Bizbaşqa bir təsadüfi a cəhd edirik, bu dəfə a = 137 seçirik :

A^{2 0}· d mod n = 137 55 mod 221 = 188 ≠ 1, n − 1

A^{2 1}· d mod n = 137 110 mod 221 = 205 ≠ n − 1.
Beləliklə, 137 221-in birləşməsinə şahiddir və 174 əslində güclü yalançı idi. Qeyd edim ki, bu, 221 (13 və 17) faktorları haqqında bizə heç nə demir. Bununla belə, sonrakı bölmədə 341 ilə nümunə bu hesablamaların bəzən n faktorunu necə yarada biləcəyini göstərir .