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 b_i=1
then c ← c+1
f ← (f · a) mod n
return f

Անվտանգությունը

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

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