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

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

Открытый и закрытый ключи
Открытый(публичный) ключ – это ключ, который известен каждому и не является секретной частью алгоритма шифрования. С его помощью, любой желающий может зашифровать сообщение.
Закрытый ключ – это часть алгоритма, которая является секретной, только обладая этим ключом можно расшифровать сообщение, полученное с помощью открытого ключа и криптографического преобразования.

Другими словами
Любой желающий может с помощью открытого ключа зашифровать своё послание и отправить его владельцу секретного ключа
Имеет место следующее преобразование:
Сообщение + открытый ключ пользователя = шифртекст
Шифртекст + секретный ключ пользователя = сообщение

Односторонняя(вычислительно необратимая функция)
Функция реализующая преобразование, которое сложно обратить, без знания некоторой секретной информации.

Вариант алгоритма асимметричного шифрования
Выбрать два простых числа p и q
Вычислить N=p•q
Выбрать E, такое, что
Найти D, такое, что
Т.е.

Вариант алгоритма ассиметричного шифрования
Положим
p=7
q=11
Тогда
N=77
E=13
D=37
Следовательно для зашифровывания числа 8
А для расшифровывания

Это так, потому что
Все сравнимые по модулю числа, мы считаем равными друг другу
При возведении числа в степени в степень, степени умножаются
Произведение числа с обратным ему, в кольце вычетов даёт 1
Следовательно

В чём проблема
Эффективность такого рода алгоритмов базируется на сложности некоторых математических проблем, так в данном случае эксплуатируется сложность разложения числа на простые множители.
В тоже время перемножение двух простых чисел для получения числа N не представляется сложной задачей
Без знания p и q не возможно найти обратное(«d») к известному «e», т.к. зная «e» можно вычислить обратное к нему, только зная модуль, а он в свою очередь равен (p-1)•(q-1), найти это значение, можно только зная p и q, но чтобы их найти, надо разложить N на простые множители

Экскурс в прошлое(или откуда (p-1)•(q-1))
Число элементов кольца вычетов взаимнопростых с модулем, даётся ф-ей Эйлера
По аналогии с Малой теоремой Ферма, теорема Лагранжа в частности позволяет нам утверждать, что

Как происходит шифрование
Открытый текст разбивается на блоки длинны меньше N
Например текст «crypt» можно разбить так
Каждый блок зашифровывается по вышеописанной схеме, т.е.
Первые два(N,E) известны всем, D - хранится в тайне

Процедура шифрования

Процедура расшифровывания

Как выглядит переписка при использовании шифрования с закрытым ключом
Алиса
Боб
Сообщение зашифрованное открытым ключом Боба
У себя на компьютере Боб расшифрует его своим закрытым ключом и прочтёт
Потом он зашифрует ответ для Алисы, её открытым ключом
А Алиса расшифрует его ответ своим закрытым ключом
Алиса и Боб обменяются открытыми ключами по не защищённому каналу

Как работает ЭЦП
Алиса
Боб
Её важный документ
ХЭШ её важного документа
Зашифрованный Алисиным закрытым ключом ХЭШ
Боб расшифрует ХЭШ документа открытым ключом Алисы, а потом вычислит ХЭШ документа, который пришёл вместе с зашифрованным. Если значения ХЭШ функций совпадут, БОБ может быть уверен в подлинности документа.
В данном случае закрытый ключ используется для зашифровывания, а открытый для расшифровывания

Знать
Что такое вычислительно необратимые ф-и
Что такое ассиметричное шифрование
Что такое закрытый и открытый ключи
Знать приведённый в презентации примитив RSA
Уметь объяснять почему это работает
Знать как происходит процесс шифрования
Уметь строить простые примеры зашифровывания аналогичные приведённым в презентации