RSA

Վիքիպեդիայից՝ ազատ հանրագիտարանից
RSA securityID

RSA (Rivest, Shamir ու Adleman ազգանուններից ստեղծված հապավում է), բաց բանալիով գաղտնագրային ալգորիթմ է։ RSA-ը առաջին համակարգն էր, որը կարելի էր օգտագործել և՛ գաղտնագրելու, և՛ թվային ստորագրությունների համար։ Մեծ մասամբ ալգորիթմը օգտագործվում է PGP, S/MIME, TLS/SSL, IPSEC/IKE և այլ գաղտնագրային ծրագրերում։

Պատմություն[խմբագրել]

1976թ. Ուիթֆիլդ Դիֆֆին և Մարթին Հելլմանը գաղտնագրային համակարգում առաջարկեցին նոր մոտեցում` բաց բանալիով գաղտնագրություն, որը փոխեց գաղտնագրության մասին պատկերացումները։ Մասաչուսեթսի տեխնոլոգիական ինստիտուտից (MIT) Ռոն Ռիվեսթը, Ադի Շամիրը և Լեոնարդ Ադլիմանը ուսումնասիրելով Դիֆֆի-Հելլմանի «Նոր ուղղություններ գաղտնագրությունում» (անգլ. «New Directions in Cryptography») հոդվածը` սկսեցին փնտրել մաթեմատիկական ֆունկցիա, որը թույլ կտար իրագործել Դիֆֆի-Հելլմանի առաջարկած գաղտնահամակարգի մոդելը բաց բանալիով։ Ավելի քան 40 տարբեակների վրա աշխատելուց հետո, նրանց հաջողվեց գտնել ալգորիթմ, որի անունն էլ դրեցին երեք գիտնականների ազգանունների սկզբնատառերով RSA:

Ալգորիթմի գեներացում[խմբագրել]

  1. Վերցնում ենք երկու պարզ թիվ` p և q, p≠q
  2. բազմապատկում ենք n=p·q
  3. հաշվում ենք Էիլերի ֆունկցիան F(n)=(p-1)(q-1)

Գտնում ենք բաց բանալին, որը պիտի բավարարի F(n) > e > 1 և (F(n), e)= (1;1)։ Փակ բանալին գտնում ենք Էվկլիդյան բանաձևի միջոցով` d = e-1(mod (F(n))։ Բաց բանալին կլինի e,n զույգը։ Փակ բանալին կլինի d,n զույգը։ Ընտրում ենք բնօրինակ, որը պետք լինի փոքր n-ից (M < n)։ Գաղտնագրված տեքստը կլինի` C = Me modn: Վերծանելու համար` M = Cd mod n:

Օրինակ[խմբագրել]

 p = 7, q = 17,
 n = p \cdot q = 119
 F(n)= (p-1)(q-1)=96
 e=5,
 d=e-1 mod (F(n))= 77
 PU = (5,119)
 PB= (77,119)
 M=19
 C=195 mod 119=66
 D= 6677 mod 119= 19

Ալգորիթմ հաշվարկման համար ab mod n[խմբագրել]

c ← 0 ; f ← 1
for i ← k downto 0
do c ← 2 x c
f ← (f · f ) mod n
if bi=1
then c ← c+1
f ← (f · a) mod n
return f

Անվտանգությունը[խմբագրել]

Չորս եղանակ կա RSA ալգորիթմի հարձակման համար

  1. Կոպիտ գրոհ` փորձելով բոլոր հնարավոր փակ բանալիները
  2. Մաթեմատիկական հարձակում` փորձելով հասկանալ, որոնք են ընտրված պարզ թվերը
  3. Ժամանակային հարձակումներ` սա կախված է վերծանման ալգորիթմի ծախսվելիք ժամանակից
  4. Ընտրված ծածկագրված տեքստի հարձակում, որը օգտագործում է RSA ալգորիթմիհատկությունները