Шифрование текстовых сообщений в телефоне с использованием алгоритма с открытым ключом

Товарищ Председатель Государственной  Экзаменационной  Комиссии. Уважаемые товарищи.

Вашему  вниманию предоставляется дипломная  работа студента 65 учебной группы Математического  факультета ТвГУ Козловского Александра Анатольевича , специальность «Математика. Компьютерная безопасность» на тему:

Шифрование  текстовых сообщений  в телефоне с использованием алгоритма с открытым ключом.

Мобилизация всего  и вся в настоящее время  достигла таких высот, что переписка  посредством SMS стала обычным видом  общения, особенно среди высокотехнологичной молодежи. Однако обмениваясь сообщениями, мало кто задумывается о конфиденциальности передаваемой между абонентами информации. Конечно, вряд ли кого-то заинтересуют электронные весточки вида "Привет, как дела?" или "Встречаемся, как договорились", но в отдельных случаях шифрование передаваемых SMS может быть актуальной задачей.

     Тема  и цель дипломной  работы представлены на Слайде 1 и на Слайде 2.

       
 

     

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

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

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

Второй задачей  является необходимость создания таких механизмов, при использовании которых невозможно было бы подменить кого-либо из участников, т.е. нужна цифровая подпись. При использовании коммуникаций для решения широкого круга задач, например в коммерческих и частных целях, электронные сообщения и документы должны иметь эквивалент подписи, содержащейся в бумажных документах. Необходимо создать метод, при использовании которого все участники будут убеждены, что электронное сообщение было послано конкретным участником. Это более сильное требование, чем аутентификация.

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

     Прмеры  таких алгоритмов представлены на Слайде 3.

       

RSA

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

     На  Слайде 4 представлено описание этого алгоритма.

     

Нахождение  простых чисел

В первом пункте алгоритма RSA сказано, что необходимо выбрать два простых числа p и q. Как это сделать, если числа имеют большую разрядность? Простой способ - деление предполагаемого простого числа на все числа меньшие его не работоспособен уже с 32-битными числами (требуется очень много времени на выполнение).

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

     На  Слайде 5 представлен алгоритм поиска простых чисел.

     

Нахождение  взаимно простых  чисел

На шаге 4 алгоритма RSA необходимо найти число d взаимно  простое с m, т.е. не имеющее общих  делителей с ним, кроме единицы. Число d должно быть меньше m, т.о. разрядность числа d равна сумме бит в числах p и q. Для нахождения взаимно простых чисел используется алгоритм Евклида, который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число d и повторить проверку.

     На  Слайде 6 представлен Алгоритм Евклида.

     

Решение уравнения a * x + b * y = 1

В 5-м пункте алгоритма RSA предполагается нахождение такого числа e, чтобы e * d = 1 (mod m). Для этого нужно  использовать модифицированный алгоритм Евклида, который работает только если числа d и m взаимно просты. Вычисление числа e сводится к решению уравнения m * x + d * e = 1 в натуральных числах. Число x не существенно.

На Слайде 7 представлен Алгоритм Решение уравнения a * x + b * y = 1

 В алгоритме RSA очень много возведений в степень по модулю натурального числа. Конечно же, не нужно производить триллиарды умножений, а затем брать остаток от деления числа из миллиардов цифр. Остаток от деления берется после каждого умножения. Таким образом, при перемножении двух чисел, состоящих из k бит потребуется 2 * k-битное число, которое затем делится на модуль и получается остаток, опять же состоящий из k бит (если модульное число состоит из k бит).

Сложность этого  алгоритма может быть оценена  как O(ln m), где m - модуль, по которому производится умножение. Запись O(ln m) означает, что для реализации алгоритма потребуется порядка ln m операций. Например, если число имеет разрядность 1024 бит (при этом длина m не менее 1024 бит), то умножение по модулю необходимо будет провести порядка ln m = ln 2¹⁰²⁴ = 710 раз, что относительно немного.

     На  Слайде 8 представлен Алгоритм быстрого возведения в степень

     

     На  Слайде 9 показана схема шифрования с открытым ключом.

     

     На  Слайде 10 представлена схема  Доли операционных систем установленных на смартфонах. С момента выхода Windows Phone 7 до настоящего времени.

     

     Слайд 11-12 описание программного обеспечения Windows Mobile.

     

     

     Слайд 13 представлен интерфейс Windows Mobile.

     

     Слайд 14 описание интерфейса программы.

     

     Слайд 15-16 Заключение – Всем спасибо.