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.

Шифриране

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

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

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

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

Дешифриране

Получателят възстановява $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}.$