RSA

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

RSA е алгоритъм за шифриране на данни, при който се използват различни ключове за шифриране и дешифриране. Наименованието идва от фамилните имена на създателите му Ronald L. Rivest, Adi Shamir и Leonard Adleman. Патентован е през 1983 г, освободен е от патент през 2000 г. Ключът с дължина от 512 до 1024 бита се използва за кодиране и е различен от ключа, използван за декодиране. Алгоритъмът на RSA предоставя процедура за подписване на електронен документ и за проверка на автентичността на подписа. Подписът на електронен документ е доста различен от подписване на документ (на лист), където подписът е същият за всички документи на лист. Електронният подпис не може да бъде константа — той е реквизит на електронния документ, на който е „положен“.

Операциите на RSA, независимо дали кодирането, декодирането, подписването или проверката, всъщност представляват модулно експоненциране. Това изчисление се извършва като серия модулни „умножения“.

RSA в момента е използван широко в много продукти, платформи и промишлености по света. Той намира разпространение в много търговски софтуерни продукти и е планирано да бъде използван в много повече.

RSA е приложен в операционни системи на Майкрософт, Епъл, Сън и Новел. В практиката RSA може да бъде открит в телефони, на мрежови карти за Интернет и на смарт карти. Като цяло, RSA е внедрен като мярка за сигурност във всички главни протоколи за сигурни интернет-комуникации, включвайки S / MIME формат, SSL, и S / WAN.

RSA е също така използван вътрешно в много институции, включително клонове на американското правителство, водещи корпорации, национални лаборатории и университети.

Лицензът за технологията на RSA е придобит от около 350 компании. Приблизителният брой на машините за кодиране на базата на RSA е около 300 милиона, правейки го досега най-широко използвания алгоритъм за криптиране в света.

Начин на шифриране[редактиране | edit source]

Генериране на двойка ключове[редактиране | edit source]

  1. Избират се две различни прости числа p и q. За по-добра сигурност те трябва да бъдат случайни и с еднакъв брой цифри (представени в двоична бройна система).
  2. Изчислява се n=pq. Това е модулът на частния и публичния ключ.
  3. Изчислява се функцията на Ойлер: φ(n) = (p-1)(q-1).
  4. Избира се цяло число e, така че 1 < e < φ(n), и освен това e и φ(n) да нямат общи делители. Експонента на публичния ключ е e.
  5. Изчислява се d, което удовлетворява уравнението de≡1 (mod φ(n)). С други думи, ed – 1 може да бъде разделено без остатък на (p-1)(q-1). Експонента на частния ключ е d.

Публичният ключ е съставен от модула n и от публичната експонента e. Частният ключ съдържа модула n и частната експонента d.

Шифриране[редактиране | edit source]

Получателят предава публичния си ключ (n,e) на изпращача и съхранява частния ключ. Изпращачът изпраща съобщение M.

Първоначално M е превърнато в число 0 < m < n като се използва предварително договорен за целта протокол. След което се шифрира: изчислява се c, където:

 c \equiv m^e \pmod{n}.

Алгоритъм за бързо степенуване позволява бързото му изчисление, след което c бива изпратено.

Дешифриране[редактиране | edit source]

Получателят възстановява m от c, като използва ключовата експонента d от:

m \equiv c^d \pmod{n}.

Ако е дадено m, оригиналното съобщение M може да бъде възстановено, като се обърне схемата.

Доказателство:

c^d \equiv (m^e)^d \equiv m^{ed}\pmod{n}.

Тъй като ed = 1 + k\varphi(n),

m^{ed} \equiv m^{1 + k\varphi(n)} \equiv m (m^k)^{\varphi(n)} \equiv m \pmod{n}.

Последното съждение следва от Теорема на Ойлер където m е взаимно просто с n. Използвайки китайска теорема за остатъка може да бъде доказано, че уравнението важи за всички m.

С това се доказва, че сме получили първоначалното съобщение:

c^d \equiv m \pmod{n}.