Автор: Пользователь скрыл имя, 20 Мая 2013 в 01:01, курсовая работа
Криптоанализ традиционно используется для решения таких задач, как восстановление исходной информации по ее криптограмме, вычисление закрытого ключа по известному открытому, формирование электронной цифровой подписи сообщения без знания закрытого ключа, а также создание фальшивого электронного документа, соответствующего известной подписи.
В данной работе рассмотрим алгоритмы шифрования и дешифрования системы RSA и проведём её криптоанализ.
Введение 3
1 Техническое задание 5
2 Алгоритм шифрования RSA 6
2.1 Описание RSA 6
2.2 Нахождение простых чисел 6
2.3 Нахождение взаимно простых чисел 7
2.4 Решение уравнения Диофанта 8
2.5 Большие числа и работа с ними 8
2.5.1 Хранение больших чисел, алгебраическое сложение, умножение 9
2.5.2 Алгоритм быстрого возведения в степень 9
2.5.3 BigInteger 10
3 Средства взлома 11
3.1 Алгоритм взлома основанный на факторинге 12
4 Руководство пользователя 13
Выводы 16
Список использованной литературы 17
Приложение А (листинг основных модулей) 18
Приложение Б (диск с программой и документацией) 31
Для работы с большими числами можно также воспользоваться специальными библиотеками или типами данных. Например, тип BigInteger библиотеки .Net Framwork 4.
Тип BigInteger является постоянным типом, который представляет сколь угодно большое целое число, значение которого теоретически не имеет верхнего или нижнего предела. Элементы типа BigInteger близки к элементам других целочисленных типов. Этот тип отличается от других целочисленных типов в .NET Framework, диапазон которых указывается их свойствами MinValue и MaxValue.
Экземпляр BigInteger можно использовать точно так же, как и любой другой целочисленный тип. BigInteger перегружает стандартные числовые операторы для выполнения основных математических операций, таких как сложение, вычитание, деление, умножение, вычитания, отрицание и унарное отрицание. Можно также использовать стандартные числовые операторы для сравнения двух значений BigInteger друг с другом. Как и другие типы целого числа, BigInteger поддерживает битовые операторы And, Or, XOr, сдвиг влево и сдвиг вправо. Для языков, не поддерживающих пользовательские операторы, структура BigInteger также предоставляет эквивалентные методы для выполнения математических операций. Это относится к методам Add, Divide, Multiply, Negate, Subtract и некоторым другим.
Многие члены структуры BigInteger напрямую соответствуют членам других целых типов. Кроме того, BigInteger добавляет такие элементы как:
Если не принимать во внимание абсолютно стойкий шифр, массового применения которого пользователями компьютерных сетей не произойдет никогда, то ко всем остальным шифрам можно применить следующее высказывание "отца кибернетики" Норберта Винера: "Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость, и если информация, которую предполагается получить, стоит затраченных средств, усилий и времени…".
В доказательство истинности этого высказывания можно привести задачу, предложенную создателями RSA для всех желающих попробовать свои силы во взломе их шифра. В конце августа 1999 года компания RSA Data Security оповестила о вскрытии 512-битового открытого ключа. Во взломе принимали участие 292 компьютера на протяжении чуть больше пяти месяцев; кроме того, 9 недель ушло на предварительные расчеты. В связи со вскрытием 512-битового ключа RSA Data Security рекомендует пользователям использовать более надежные 768-битовые или даже 1028-битовые ключи.
Существует несколько способов взлома RSA. Наиболее эффективная атака – найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля – и . На основании , и (общий показатель) нападающий может легко вычислить частный показатель . Основная сложность – в поиске главных сомножителей (факторинг) . Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.
Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени из . Поскольку , то корнем степени из является сообщение . Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.
Существуют и другие типы атак, позволяющие расшифровать только одно сообщение и не позволяющие нападающему вскрыть прочие сообщения, зашифрованные тем же ключом.
Самое простое нападение на отдельное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст (например, “Ирина – Анне”), затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака на единственное сообщение применяется в том случае, если отправитель посылает одно и то же сообщение трем корреспондентам, каждый из которых использует общий показатель . Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение .
Такую атаку можно предотвратить,
вводя перед каждым шифрованием
в сообщение несколько
Алгоритм взлома RSA состоит из следующих пунктов:
При запуске программы на экране появится следующая форма:
Рисунок 4.1 – Начальный вид программы
Имеется главное меню. В текстовое окно выводится содержимое исходного файла или расшифрованный текст.
Пункт меню «Файл» содержит подпункты:
Пункт меню «Преобразовать» содержит подпункты:
Пункт меню «Сервис» содержит подпункты:
Для того чтобы взломать ключ, необходимо выбрать пункт меню «Сервис à Взломать ключ». На экране, справа, появляется форма:
Рисунок 4.2 – Взлом ключа
В текстовые окна вводятся значения открытого ключа – числа и соответственно. После нажатия кнопки «Взломать» в текстовом окне появится информация о секретной части ключа.
Для того чтобы дешифровать закодированный по методу RSA исходный текст, необходимо в пункте меню «Преобразовать» выбрать подпункт «Декодировать». В поля, которые появятся на форме ввести общую часть и полученную секретную часть, после чего нажать кнопку «Декодировать».
Рисунок 4.3 – Декодирование сообщения
Программа расшифрует файл, и выведет результат на экран.
Рисунок 4.4 – Результат взлома системы RSA
Выводы
В данной работе была досконально изучена ассиметричная система шифрования/дешифрования RSA. Выявлены её основные достоинства и недостатки. На основании полученных данных были рассмотрены способы взлома данной системы.
Существует несколько способов взлома RSA. Наиболее эффективная атака – найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля . Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени из . Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Самое простое нападение на отдельное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом.
Самым распространённым способом взлома криптосистемы RSA с открытым ключом является метод факторинга открытого ключа. Т. е. разложение большого целого числа на простые сомножители.
В работе описаны алгоритмы, необходимые для реализации взлома системы с помощью факторинга. На основании алгоритмов разработан программный продукт, показывающий возможность взлома системы шифрования/дешифрования RSA. Проанализировав полученные результаты можно сказать, что данная система является недостаточно криптостойкой на малых числах. Но используя достаточно большие значения открытого и закрытого ключей, сложность взлома данной системы резко возрастает и время получения секретной части ключа по открытой части на данный момент является невероятно большим. Это подтверждает то, что система RSA на данный момент является криптостойкой, а её использование оправданное.
Список использованной литературы
Приложение А (листинг основных модулей)
Код интерфейса программы:
<Window x:Class="CodingWPF.MainWindow"
xmlns="http://schemas.
xmlns:x="http://schemas.
Title="Кодирование/
<Grid>
<Grid.RowDefinitions>
<RowDefinition Height="Auto" />
<RowDefinition/>
<RowDefinition Height="Auto" />
</Grid.RowDefinitions>
<Grid.ColumnDefinitions>
<ColumnDefinition/>
<ColumnDefinition Width="Auto"/>
<ColumnDefinition Width="Auto"/>
</Grid.ColumnDefinitions>
<Menu Grid.Row="0" Grid.ColumnSpan="3">
<MenuItem Header="Файл">
<MenuItem Header="Новый" Click="New_Click"/>
<Separator/>
<MenuItem Header="Открыть..." Click="Open_Click"/>
<MenuItem Header="Сохранить..." Click="Save_Click"/>
<Separator/>
<MenuItem Header="Выход" Click="Exit_Click"/>
</MenuItem>
<MenuItem Header="Преобразовать">
<MenuItem Header="Кодировать..." Click="CodingShow_Click"/>
<MenuItem Header="Декодировать..." Click="DecodingShow_Click"/>
</MenuItem>
<MenuItem Header="Сервис">
<MenuItem Header="Получить ключ..." IsCheckable="True" Click="FindKeys_Click"/>
<MenuItem Header="Взломать ключ..." IsCheckable="True" Click="CrackKeys_Click"/>
</MenuItem>
</Menu>
<TextBox Name="text_box_code" TextWrapping="Wrap" Grid.Row="1" />
<StackPanel Grid.Row="2">
<TextBlock Name="text_block_n" Text="Введите общую часть ключа:" Visibility="Collapsed"/>
<TextBox Name="text_box_n" Visibility="Collapsed"/>
<TextBlock Name="text_block_e" Text="Введите открытую часть ключа:" Visibility="Collapsed"/>
<TextBox Name="text_box_e" Visibility="Collapsed"/>
<TextBlock Name="text_block_d" Text="Введите секретную часть ключа:" Visibility="Collapsed"/>
<PasswordBox Name="text_box_d" Visibility="Collapsed"/>
<Button Name="button_coding" Content="Кодировать" Visibility="Collapsed" Click="Coding_Click"/>
<Button Name="button_decoding" Content="Декодировать" Visibility="Collapsed" Click="Decoding_Click"/>
</StackPanel>
<StackPanel Name="stack_panel_find_keys" Grid.Column="1" Grid.Row="1" Grid.RowSpan="2" Visibility="Collapsed">
<TextBlock Text="Простое число p:" Visibility="Collapsed"/>
<Grid Visibility="Collapsed">
<Grid.ColumnDefinitions>
<ColumnDefinition/>
<ColumnDefinition/>