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 милиона, правейки го досега най-широко използвания алгоритъм за криптиране в света.

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

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

  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.

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

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

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

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

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

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

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

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

.

Тъй като ,

.

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

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