RSA

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


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


== Ալգորիթմի գեներացում ==
Վերցնում ենք երկու պարզ թիվ՝ p և q, p≠q
բազմապատկում ենք n=p·q
հաշվում ենք Էիլերի ֆունկցիան 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
        ,
      
    
    {\displaystyle p=7,q=17,}
  
  
    
      
        n
        =
        p
        ⋅
        q
        =
        119
      
    
    {\displaystyle n=p\cdot q=119}
  
  
    
      
        F
        (
        n
        )
        =
        (
        p
        −
        1
        )
        (
        q
        −
        1
        )
        =
        96
      
    
    {\displaystyle F(n)=(p-1)(q-1)=96}
  
  
    
      
        e
        =
        5
        ,
      
    
    {\displaystyle e=5,}
  
  
    
      
        d
        =
        e
        −
        1
        m
        o
        d
        (
        F
        (
        n
        )
        )
        =
        77
      
    
    {\displaystyle d=e-1mod(F(n))=77}
  
  
    
      
        P
        U
        =
        (
        5
        ,
        119
        )
      
    
    {\displaystyle PU=(5,119)}
  
  
    
      
        P
        B
        =
        (
        77
        ,
        119
        )
      
    
    {\displaystyle PB=(77,119)}
  
  
    
      
        M
        =
        19
      
    
    {\displaystyle M=19}
  

  
    
      
        C
        =
        195
        m
        o
        d
        119
        =
        66
      
    
    {\displaystyle C=195mod119=66}
  

  
    
      
        D
        =
        6677
        m
        o
        d
        119
        =
        19
      
    
    {\displaystyle 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 bi=1 
		then c ← c+1 
			f ← (f · a) mod n 
return f


== Անվտանգություն ==
Չորս եղանակ կա RSA ալգորիթմի հարձակման համար

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