RSA

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

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

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

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.

Шифриране

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

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

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

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

Дешифриране

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

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

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

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

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

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

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

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

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

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