RSA

RSA
Տեսակ	cryptosystem?
Դաս	Հանրային բանալիների գաղտնագրություն
Օգտագործում է	integer factorization? և modular exponentiation?
Անվանված է	Ron Rivest?, Ադի Շամիր և Leonard Adleman?

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-1mod(F(n))=77$

$PU=(5,119)$

$PB=(77,119)$

$M=19$

$C=195mod119=66$

$D=6677mod119=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 ալգորիթմի հատկությունները