Лабораторная работа 4 Тема- Разработка программ тестирования защитных процедур
Работа добавлена на сайт samzan.net:
|
Евразийский национальный университет им. Л.Н. Гумилева |
Учебно-методическое пособие |
Издание: третье |
Лабораторная работа № 4
Тема: «Разработка программ тестирования защитных процедур». Генерация псевдослучайных кодов. Одноразовый блокнот
Цель работы: Изучить алгоритм шифрования файлов случайными байтами.
Теоретические сведения: В самом общем виде алгоритм шифрования файлов случайными байтами состоит из последовательности выполнения следующих действий:
1 Создание Множества строк длиной от 128 до 1024 строки. Все строки в множестве имеют длину 256 байт. Все строки содержат байты от 0 до 255 ровно по одному разу. Байты в строках расположены в разных местах. Множество не имеет одинаковых строк. Множество строк, которое хранится в исполняемом коде программы, называется Внутренним множеством строк. Множество строк, которое хранится во внешнем файле, называется Внешним множеством строк. Если множество строк (внешнее или внутреннее) используется для обмена зашифрованными файлами между структурными подразделениями одного юридического лица, то такое множество называется Частным внутреннем множеством строк или Частным внешним множеством строк. Если множество строк (внешнее или внутреннее) используется для обмена зашифрованными файлами между различными юридическими лицами, то такое множество называется Публичным внутреннем множеством строк или Публичным внешним множеством строк. Таким образом, программа использует не одно единственное множество строк, а бесконечную совокупность множеств строк.
2 Создание Случайного одноразового блокнота длиной от 512 до 1024 строки. Блокнот - это массив строк. В блокнот строки считываются из Частного внутреннего множества строк, или из Публичного внутреннего множества строк, или из Частного внешнего множества строк, или из Публичного внешнего множества строк. Считывание строк из Множества строк в блокнот осуществляется не по порядку 1,2,...,1024, а случайным образом. Поэтому блокнот называется случайным одноразовым блокнотом, так как вероятность повторного создания одного и того же блокнота при использовании одного и того множества строк не превосходит 5,1х10-1024. При считывании строк из множества в блокнот каждая вторая строка заменяется на дополнительную строку. Все байты дополнительной строки вычисляются как разность между 255 и байтом основной строки. Строки заменяются на дополнительные не строго по порядку 2,4,...,1024, а случайным образом. Поэтому в среднем заменяется на дополнительную строку половина считываемых строк из множества. В каждом конкретном случае может быть различное количество дополнительных строк, в том числе и нулевое. Считывание строк из множества в блокнот осуществляется случайным выбором с повторениями. Поэтому случайный одноразовый блокнот может содержать одинаковые строки в отличие от множества строк, которое содержит все разные строки.
файла пользователя. Поскольку заранее неизвестна длина файла пользователя, то приходится все файлы пользователя шифровать порциями длиной от 100 байт до 32760 байт. Длина порции генерируется случайным образом в момент создания зашифрованной копии исходного файла.
Выбор строк из одноразового случайного блокнота осуществляется способом, аналогичным способу заполнения случайного одноразового блокнота строками из множества строк.
Для этого генерируются две случайные строки байтов со случайной длиной от 512 до 2048 байт. Строки одинаковые по размеру, но содержат разные наборы случайных байтов. Максимальная длина строк в данном случае в два раза превосходит максимальную длину строк, предназначенных для считывания строк из множества строк. Это связано с тем, что максимальная длина пароля составляет 1024 байта. При шифровании пароль записывается либо в первую строку, либо во вторую строку через один байт по четным или нечетным местам. Запись пароля осуществляется случайным образом. Информация о способе записи пароля хранится в самом зашифрованном файле в зашифрованном виде.
Для шифрования первого байта файла пользователя из созданных двух случайных строк берем первые байты, увеличиваем их на 1 и перемножаем. Результат делим на длину случайного одноразового блокнота и находим остаток от деления. Остаток увеличиваем на 1. Это и есть номер первой строки случайного одноразового блокнота, используемой для шифрования первого байта файла пользователя.
Для шифрования второго байта файла пользователя из созданных двух случайных строк берем вторые байты, увеличиваем их на 1 и перемножаем. Результат делим на длину случайного одноразового блокнота и находим остаток от деления. Остаток увеличиваем на 1. Это и есть номер второй строки случайного одноразового блокнота, используемой для шифрования второго байта файла пользователя. Результат шифрования второго байта совершенно не зависит от результата шифрования первого байта файла пользователя. Поэтому первый и второй байты файла пользователя могут быть одинаковыми, а результат шифрования может различным. И, наоборот, первый и второй байты файла пользователя могут быть разными, а результат шифрования может быть одним и тем же.
Способ шифрования таков, что результат шифрования зависит от взаимного расположения строк в множестве строк и взаимного расположения строк в случайном одноразовом блокноте. Если взять из множества строк все строки по порядковому номеру 1,2,…,1024 и записать их в случайный одноразовый блокнот, то будет один вариант шифрования. Если взять из множества строк все строки в обратном порядке 1024,1023,…,1 и записать их в случайный одноразовый блокнот, то это будет уже другой вариант шифрования. Если взять из множества строк все строки произвольным образом, например, 55,1000,…,1,1024 и записать их в случайный одноразовый блокнот, то это будет третий вариант шифрования. Если взять из множества строк все строки другим произвольным образом, например, 7,945,…,991,500 и записать их в случайный одноразовый блокнот, то это будет четвертый вариант шифрования. Таким образом, количество вариантов шифрования зависит от количества строк в множестве, от количества строк в случайном одноразовом блокноте, от взаимного расположения строк в множестве строк, от взаимного расположения строк в случайном одноразовом блокноте.
Как видно из приведенного описания, какая-либо функциональная или статистическая связь между исходными байтами файла пользователя и байтами зашифрованного файла пользователя отсутствует. Это связано с тем, что отсутствует связь между величиной байта и его местом расположения в случайных строках из множества строк. Очевидно, что исходный байт файла пользователя и адрес расположения этого же байта в строке из множества строк никак между собой не связаны, поэтому связь между ними совершенно случайная. Анализ зашифрованных файлов показывает, что все байты от 0 до 255 встречаются в зашифрованном файле примерно в одинаковом количестве. Следовательно, байты в зашифрованном файле подчиняются равномерному закону распределения вероятностей.
Далее при реализации описанного алгоритма встали вопросы:
1Где сохранять множество строк;
2 Где сохранять случайные строки, используемые для создания случайного одноразового блокнота и для шифрования файла пользователя;
3 Где сохранять пароли (ключи), позволяющие пользователю расшифровывать свои зашифрованные файлы.
Перечисленные задачи мы решили следующим образом:
1 Множества строк сохраняются либо в коде программы, либо в отдельных файлах:
1.1 Публичное внутреннее множество строк генерируется программно, так сказать из ничего, у всех программ одно и то же, предназначено для обмена зашифрованными файлами между различными комплектами программы (различными юридическими и/или физическими лицами).
1.2 Публичное внешнее множество строк генерируется по желанию пользователя в неограниченном количестве, сохраняется в отдельном файле, предназначено для обмена зашифрованными файлами между различными комплектами программы (различными юридическими и/или физическими лицами).
1.3 Частное внутреннее множество строк генерируется в момент создания программы, встроено в код программы, во всех вариантах одного и того же комплекта программы одно и то же, предназначено для обмена зашифрованными файлами между вариантами программы из одного и того же комплекта программы (структурными подразделениями одного и того же юридического и/или физического лица).
1.4Частное внешнее множество строк генерируется по желанию пользователя в неограниченном количестве, сохраняется в отдельном файле, предназначено для обмена зашифрованными файлами между вариантами программы из одного и того же комплекта программы (структурными подразделениями одного и того же юридического и/или физического лица).
Как внешнее множество строк, так и внутреннее множество строк сохраняются в зашифрованном виде, как в коде программы, так и во внешних файлах. Исключение, составляет публичное внутреннее множество строк, которое создается при запуске программы и поэтому не требует шифрования. Алгоритм генерации публичного внутреннего множества строк является шифром этого множества.
2 Случайные строки, используемые для создания случайного одноразового блокнота и для для шифрования файла пользователя сохраняются в оболочке зашифрованного файла в зашифрованном виде.
3 Пароль, введенный пользователем при шифровании файла, сохраняется в оболочке зашифрованного файла в зашифрованном виде. Таким образом, пароль передается пользователю вместе с зашифрованным файлом.
Кроме того, реализован еще один механизм передачи пароля - это открытая публикация так называемых «Открытых паролей». Открытые пароли предназначены для публичного распространения. Файлы, зашифрованные открытыми паролями расшифровываются исключительно соответствующими закрытыми паролями. Каждый закрытый пароль расшифровывает файлы, зашифрованные тремя различными открытыми паролями.
Файлы, зашифрованные произвольным паролем, расшифровываются этим паролем, а также расшифровываются закрытыми паролями. Таким образом, обеспечивается многообразие передачи паролей и многообразие способов расшифровки файла различными паролями.
Файлы, зашифрованные закрытыми паролями, расшифровываются только этими же закрытыми паролями, либо расшифровываются закрытыми паролями более высокого уровня управления.
Открытые и закрытые пароли сохраняются вместе с множествами строк в зашифрованном виде: либо в коде программы, либо в отдельном файле вместе с множеством строк.
В целом зашифрованный файл отличается от исходного файла наличием оболочки, не превосходящей по размеру 32000 байт. Структурно зашифрованный файл состоит из смеси областей со случайными байтами и зашифрованных 4 областей. Начинается зашифрованный файл с набора случайных байтов и заканчивается набором случайных байтов. Все зашифрованные области отделены друг от друга наборами случайных байтов. Длины случайных наборов генерируются случайным образом в процессе создания каждого зашифрованного файла.
Оболочка зашифрованного файла имеет особые параметры у каждого комплекта программы. Поэтому разные комплекты программы не распознают в качестве зашифрованных файлы, зашифрованные другими комплектами программы. Все варианты одного и того же комплекта программы имеют одинаковые параметры оболочки зашифрованного файла. Поэтому варианты одного и того же комплекта программы распознают в качестве зашифрованных файлы, зашифрованные другими вариантами одного и того же комплекта программы и, поэтому расшифровывают эти файлы.
Поскольку зашифрованный файл представляет собой набор адресов, то допускается неограниченное повторное шифрование файла. В этом случае зашифрованный файл воспринимается как единое целое. Поскольку байты зашифрованного файла и адреса этих байтов в множествах строк никак не связаны, то повторное шифрование увеличивает мощность шифрования. Разумеется, при повторном шифровании файла создается новая оболочка.
Описанный алгоритм шифрования файла можно считать процессом расшифровки файла, и, наоборот. В программе эти процессы используются случайным образом, что многократно увеличивает мощность шифрования.
Без наличия программы, зашифровавшей файл, расшифровать этот зашифрованный файл физически невозможно. При наличии программы, но при отсутствии внешнего множества строк, использованного для шифрования файла, расшифровать такой зашифрованный файл физически невозможно.
Для исключения возможности создания программы по взлому исполняемого кода программы исходные коды программы генерируются в терминах случайных наименований процедур и функций, случайного взаимного расположения процедур и функций коде программы, случайного расположения независимых частей процедур и функций в коде программы. Компиляция исходного кода программы в исполняемый код программы производится последовательным переводом строк исходного кода в машинные коды. То есть компиляторы берут строки исходного кода по порядку 1,2,..., n и по порядку превращают их в строки машинных команд и по порядку записывают эти строки машинных команд в файл исполняемого кода программы. Поскольку в исходном коде даже одного и того же комплекта программы разное расположение исходного кода, то исполняемые коды двух вариантов одного и того же комплекта программы становятся настолько различными, что становится невозможным провести сравнительный анализ. Два варианта одного и того же комплекта программы логически различаются всего 2 байтами. Физическое различие этих же вариантов программы превышает 50%.
Наша программа, по-видимому, является одной из самых трудно взламываемых в истории человечества на сегодняшний день, так как изменяется случайным образом не только ее содержание, но и размер - от 8 до 16 Мегабайт. Более того, наша программа генерирует саму себя. Поэтому колоссальный труд, затраченный на анализ исполняемого кода одного варианта программы, ничего не дает для анализа другого варианта программы. Никакие хакеры, никакие программы-роботы не способны взломать исполняемый код программы, так как количество вариантов записи исходного кода программы превышает 103000.
Наглядное описание алгоритма шифрования файлов случайными байтами
Множество строк, используемое для шифрования, представляет собой одномерный массив случайных строк, записанный в отдельный файл или, встроенный в код программы.
Как видно из таблицы 12, множество строк - это одномерный массив, состоящий из одинаковых по размеру (256 байт) случайных строк, имеющих порядковые номера от 1 до N = 128 - 512 для частного внутреннего множества строк, N = 512-1024 для частного и публичного внешнего множества строк, N = 1024 для публичного внутреннего множества строк. Для определенности описания положим N=128.
Из множества строк случайным образом с повторениями выбираются строки и помещаются в случайный одноразовый блокнот, который имеет длину от 512 до 1024 строки. Размер случайного одноразового блокнота генерируется случайным образом в момент шифрования файла. Пример случайного одноразового блокнота представлен в таблице 13.
Как видно из таблицы 13 , порядковые номера строк случайного одноразового блокнота не совпадают с порядковыми номерами строк в множестве строк. Для примера строки из множества строк, показанные в таблице 1 перенесены в случайный одноразовый блокнот почти на те же самые места. В действительности такой вариант, конечно, не исключается, но маловероятен. Кроме того, каждая строка из множества строк содержит информацию еще об одной случайной строке - дополнительной, все байты которой равны разности между числом 255 и байтом случайной строки. Поэтому при считывании строк из множества строк эти строки равновероятно записываются в случайный одноразовый блокнот либо в виде дополнительной строки, либо в виде основной строки. В приведенной таблице под номером 99 указана строка номер (-N), байты которой равны разности между 255 и соответствующим байтом строки номер N. Таким образом, в случайный одноразовый блокнот считываются строки и/или дополнения строк из множества строк. Поэтому множество строк, например, имеет 128 строк и 128 дополнительных строк. То есть минимальное количество строк в множестве строк равно не 128, а 256. И, соответственно, максимальное количество строк, используемых для заполнения случайного одноразового блокнота, составляет не 1024, а 2048 строк. Для определенности описания положим K=1024.
|
Таблица 12 - Пример множества строк |
||||||||||||||
|
Номера байтов в строках (Величина байтов в строках от 0 до 255) |
||||||||||||||
|
|
N |
1 |
2 |
3 |
4 |
5 |
6 |
... |
... |
... |
254 |
255 |
256 |
|
|
Номера строк |
1 |
5 |
240 |
1 |
95 |
0 |
7 |
... |
... |
... |
126 |
20 |
11 |
|
|
от 1 до |
2 |
220 |
0 |
4 |
33 |
37 |
1 |
... |
... |
... |
19 |
27 |
28 |
|
|
N = 128 - 1024 |
3 |
55 |
70 |
80 |
4 |
89 |
2 |
... |
... |
... |
5 |
1 |
16 |
|
|
|
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
|
Физическое |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
|
расположение |
N-2 |
255 |
117 |
0 |
22 |
43 |
4 |
... |
... |
... |
9 |
10 |
11 |
|
|
строк в множестве |
N-1 |
111 |
35 |
9 |
1 |
2 |
0 |
... |
... |
... |
4 |
5 |
221 |
|
|
строк |
N |
65 |
198 |
2 |
27 |
88 |
5 |
... |
... |
... |
144 |
0 |
1 |
|
|
Таблица 13 –Пример случайного одноразового блокнота |
||||||||||||||
|
Номера байтов в строках (Величина байтов в строках от 0 до 255) |
||||||||||||||
|
|
|
N |
1 |
2 |
3 |
4 |
5 |
6 |
... |
... |
... |
254 |
255 |
256 |
|
Номера строк |
1 |
3 |
55 |
70 |
80 |
4 |
89 |
2 |
... |
... |
... |
5 |
1 |
16 |
|
в блокноте от 1 |
2 |
N-1 |
111 |
35 |
9 |
1 |
2 |
0 |
... |
... |
... |
4 |
5 |
221 |
|
до K=512- |
3 |
2 |
220 |
0 |
4 |
33 |
37 |
1 |
... |
... |
... |
19 |
27 |
28 |
|
-1024 |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
|
99 |
-N |
190 |
57 |
253 |
228 |
167 |
250 |
... |
... |
... |
111 |
255 |
254 |
|
Физическое |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
расположение |
K-2 |
N |
65 |
198 |
2 |
27 |
88 |
5 |
... |
... |
... |
144 |
0 |
1 |
|
строк в |
K-1 |
1 |
5 |
240 |
1 |
95 |
0 |
7 |
... |
... |
... |
126 |
20 |
11 |
|
блокноте |
K |
N-2 |
255 |
117 |
0 |
22 |
43 |
4 |
... |
... |
... |
9 |
10 |
11 |
Выбор строк из множества строк осуществляется следующим образом. Генерируются две случайных строки длиной от 512 до 1024 байтов. Строки одинаковые по длине, но содержащие разные случайные байты. Пример, таких строк представлен ниже.
|
Таблица 14 – Пример строк |
|||||||||
|
Номера байтов в строках |
1 |
2 |
3 |
... |
... |
... |
948 |
949 |
950 |
|
Величина байтов 1-й строки S1 |
111 |
||||||||
|
Величина байтов 2-й строки S2 |
255 |
Величина байтов в строках и длина строк выбраны произвольно, для примера. Номер строки, считываемой первой из множества строк, вычисляется следующим образом:
Берем первые байты из строк, увеличиваем их на 1 и перемножаем: (14+1) х (17+1) = 270. Полученное число делим на длину множества строк N=128 и находим остаток - 14. Увеличиваем этот остаток на 1. Получаем - 15. Номера строк в множестве строк имеют номера от 1 до 128, а остаток от деления любого числа на 128 изменяется от 0 до 127. Поэтому необходимо увеличивать остаток на 1. Таким образом, первой строкой в случайном одноразовом блокноте будет 15 строка из множества строк.
Номер строки, считываемой второй из множества строк, вычисляем аналогично.Берем вторые байты из строк и перемножаем: (250+1) х (200+1) = 50451. Полученное число делим на длину множества строк N=128 и находим остаток - 19. Увеличиваем этот остаток на 1. Получаем - 20. Номера строк в множестве строк имеют номера от 1 до 128, а остаток от деления любого числа на 128 изменяется от 0 до 127. Поэтому необходимо увеличивать остаток на 1. Таким образом, второй строкой в случайном одноразовом блокноте будет 20 строка из множества строк. И так далее.
Строки имеют по 950 байтов, а случайный одноразовый блокнот имеет 1024 строки. Поэтому после считывания 950 строки, переходим к считыванию первой строки, затем второй и т.д. Помещаем эти строки в случайный одноразовый блокнот под номером 951, 952, …, 1024.
Кроме того, по величине байта строки S1 определяется содержание считываемой строки из множества строк. Если байт меньше 128, то считывается сама строка. Если байт больше 127, то байты считанной строки заменяются дополнением до 255. Таким образом, в приведенном примере первая считанная строка из множества строк под номером 15 помещается в случайный одноразовый блокнот без изменения (так как 14<128), а вторая считанная строка из множества строк под номером 20 заменяется на дополнение и помещается в случайный одноразовый блокнот (так как 250>127).
Рассмотрим пример шифрования какой-либо строки. Пример приведен ниже.
Задание: Используя теоретические сведения и примеры, программно реализовать нижеописанный алгоритм, осуществляющий шифрование и дешифрование на любом (по выбору студента) языке программирования.
Лабораторная работа №5
Тема: Разработка процедур защиты от отладчика и дизассемблера Алгоритм DES
Цель работы: Изучить алгоритм DES.
Теоретические сведения: Стандарт шифрования DES (Data Encryption Standard) был разработан в 1970-х годах, он базируется на алгоритме DEA.
Исходные идеи алгоритма шифрования данных DEA (data encryption algorithm) были предложены компанией IBM еще в 1960-х годах и базировались на идеях, описанных Клодом Шенноном в 1940-х годах. Первоначально эта методика шифрования называлась lucifer (разработчик Хорст Фейштель, название dea она получила лишь в 1976 году. Lucifer был первым блочным алгоритмом шифрования, он использовал блоки размером 128 бит и 128-битовый ключ. По существу этот алгоритм являлся прототипом DEA. В 1986 в Японии (NIT) разработан алгоритм FEAL(Fast data Encipherment ALgorithm), предназначенный для использования в факсах, модемах и телефонах (длина ключа до 128 бит). Существует и ряд других разработок.
DEA (ANSI x3.92-1981) оперирует с блоками данных размером 64 бита и использует ключ длиной 56 бит. Такая длина ключа соответствует 1017 комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 64 бит (например, LOKI) или вообще замены DES другим стандартом.
Входной блок данных, состоящий из 64 бит, преобразуется в выходной блок идентичной длины. Ключ шифрования должен быть известен, как отправляющей так и принимающей сторонам. В алгоритме широко используются перестановки битов текста.
Вводится функция f, которая работает с 32-разрядными словами исходного текста (А) и использует в качестве параметра 48-разрядный ключ (J). Схеме работы функции f показана на рис. 6.4.1.1. Сначала 32 входные разряда расширяются до 48, при этом некоторые разряды повторяются. Схема этого расширения показана ниже (номера соответствуют номерам бит исходного 32-разрядного кода).
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Для полученного 48-разрядного кода и ключа выполняется операция исключающее ИЛИ (XOR). Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка согласно схеме показанной ниже (числа представляют собой порядковые номера бит).
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Рисунок 8 – Алгоритм работы функции f
Таблица 17 – Схема сдвигов
|
Номер итерации |
Число сдвигов влево |
|
1 |
1 |
|
2 |
1 |
|
3 |
2 |
|
4 |
2 |
|
5 |
2 |
|
6 |
2 |
|
7 |
2 |
|
8 |
2 |
|
9 |
1 |
|
10 |
2 |
|
11 |
2 |
|
12 |
2 |
|
13 |
2 |
|
14 |
2 |
|
15 |
2 |
|
16 |
1 |
Задание: Используя теоретические сведения и примеры, программно реализовать нижеописанный алгоритм, осуществляющий шифрование и дешифрование на любом (по выбору студента) языке программирования.
Лабораторная работа № 6
Тема: Исследование и комплексная оценка сложности процедур защиты Алгоритм RSA
Цель работы: Изучить алгоритм RSA.
Теоретические сведения: Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. В этом алгоритме используется два ключа – открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое число субъектов (N) должно общаться по схеме все-со-всеми. В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное число используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное число ключей равно N.
Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:
f(M) є Md mod n,
где M и f(M) оба Ј n-1. Как было показано, может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием 6, если
dc є(p-1)1, тогда (Md)eє p1.
Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.
Аналогично (Md)e є qM, если dc є (q-1)1. e удовлетворяет этим двум условиям, если cd є (p-1) (q-1)1. Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.
Так как (Md)e – M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действует до 2000 года).
Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.
Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.
Задание: Используя теоретические сведения и примеры, программно реализовать нижеописанный алгоритм, осуществляющий шифрование и дешифрование на любом (по выбору студента) языке программирования.
Контрольные вопросы
1 Какие шрифты являются наиболее известными и часто используемыми?
2 В чем отличие шифров замены от шифра Цезаря?
3 В чем отличие шифра Цезаря от шифров подстановки?
4 Что общего в методе Гронсфельда и шифре Вижинера?
5 Генерация псевдослучайных кодов.
2. Тема Внешние эффекты и общественные благаНекурящий человек находясь рядом с курильщиками получает
3. Задание 3.3.1. а составить и объяснить по каждой хозяйственной операции проводку и записать в регистрационны
4. 37 недель Генитальный герпес ремиссия
5. Тема 12. СТАТИСТИКА НАЦИОНАЛЬНОГО БОГАТСТВА Основные вопросы 1.
6. Пермская государственная медицинская академия имени академика Е
7. Город ЙошкарОла в декабре 2013 г
8. Алтынсарин Абай ~~нанбаев Ш
9. Предъявление искового заявления в суд общей юрисдикции
10. 1649 рр. Визвольна війна середини XVII століття Визвольна війна середини 17 ст
11. КОММЕРЧЕСКОЕ ИСПОЛЬЗОВАНИЕ ОБЪЕКТОВ ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ
12. 30 Minuten ruhen lssen Teig zu einem Strng 15 2 cm rollen und St~cke bschneiden 1 15 cm
13. Становище болгарської діаспори в Україні та діяльність болгарських товариств
14. век Разума относящаяся к XVII XVIII вв
15. Аудит история и современность
16. Модуль Русский язык- введение в языкознание спец
17. Фундаменты мелкого заложения и свайные фундаменты
18. 1 История 1.2 Актуальность темы 1
19. Статья- Основные пути поддержания целеустремленности и настойчивости
20. Шлюмбергера, Декабрист, Варварина коса