double arrow

Асимметричные методы шифрования

В асимметричных методах применяются два разных ключа. Один из них, несекретный, используется для шифровки и может публиковаться вместе с адресом пользователя, другой - секретный, применяется для расшифровки и известен только получателю.

Алгоритм Шамира

Алгоритм может использоваться для передачи короких сообщений, например, ключей.

Пусть абонент А хочет передать сообщение m абоненту В в зашифрованном виде. А выбирает случайное большое число p и открыто передает его В. Затем А выбирает два числа Са и Da, такие что Са · Da mod (p-1) = 1. B точно также выбирает Сb и Db. Поле этого можно передать сообщение m, используя следующий трехступенчатый протокол.

Шаг 1. A вычисляет число x1 = mCa mod p, где m – исходное сообщение, и пересылает x1 к B.

Шаг 2. B, получив x1, вычисляет число x2 = x1Cb mod p и пересылает x2 к A.

Шаг 3. A вычисляет число x3 = x2Da mod p и пересылает его к B.

Шаг 4. B, получив x3,вычисляет число x4 = x3Db mod p.

Криптосистема RSA

Криптосистема RSA, была разработана в 1977 году и по­лу­чила на­зва­ние в честь своих соз­да­те­лей: Рона Рай­ве­ста (Rivest), Ади Ша­ми­ра (Shamir) и Леонарда А­дле­ма­на (Adleman).

Они вос­поль­зо­ва­лись тем фак­том, что на­хо­ж­де­ние боль­ших про­стых чи­сел осу­ще­ст­в­ля­ет­ся лег­ко, но раз­ло­же­ние на мно­жи­те­ли про­из­ве­де­ния двух та­ких чи­сел прак­ти­че­ски не­вы­пол­ни­мо. В 1993 г. метод RSA был обнародован и принят в качестве стандарта (PKCS # 1: RSA Encryption Standard).

Генерация ключей

1. Выбираются два больших простых целых числа p и q приблизительно одинакового размера.

2. Вычисляется модуль системы n = pq и φ(n) = (p-1)(q-1) – функция Эйлера.

3. Выбирается достаточно большое число d, удовлетворяющее условию 1 < d < φ(n), и взаимно простое с φ(n), то есть НОД(d, (p-1)(q-1)) = 1.

4. Используя расширенный алгоритм Евклида, вычисляется большое целое число e, отвечающее условию (ed) mod φ(n) = 1, 1 < e < φ(n). Метод Евклида находит множество пар (e, y), каждая из которых является решением уравнения: e * d + (p - 1)(q - 1) * y = 1 в целых числах.

Таким образом, секретным ключом является пара чисел (n,d), а открытым – пара чисел (n,e), но можно взять и наоборот.

Зашифрование и расшифрование

1. Входное сообщение разбивается на блоки mi, их размер определяется целым k, соответствующим неравенству 10k-1 < n < 10k.

2. Вычисляется значение ci = mie mod n.

3. Значение ci, которое является зашифрованным блоком сообщения, посылается по открытым каналам передачи данных.

4. Расшифрование заключается в вычислении значения mi = cid mod n.

Математические основы RSA

Рас­смот­рим ма­те­ма­ти­че­ские ре­зуль­та­ты, по­ло­жен­ные в ос­но­ву это­го ал­го­рит­ма.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: