 | ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
Черноголовка, 2005 год.
Участники проекта:
Васяева Александра
Заболотский Андрей
Овчинников Михаил
Савельянов Даниил
Фанасков Роман
Чекунов Александр
Руководитель: Березин Андрей Всеволодович
На нашем проекте мы занимались исследованием различных методов зашифровки информации, разработкой своих собственных методов шифрования, а также расшифровкой зашифрованных документов.
Ход работы.
В начале участники проекта ломали голову над тем, зачем нужно шифрование информации и где может применятся. Потом все пытались вспомнить, кто какие методы шифровки знает. После вопроса АВБ о дальнейшей деятельности каждого, проект разделился на "Сциталь" (Что такое сциталь - см. дополнение 1) и "Не Сциталь". В то время как "Сциталисты" постигали проверенный веками способ шифровки, все остальные пытались придумать какой-нибудь новый хитрый шифр (взломав попутно пару шифров простой замены). Вариантов было множество, один замысловатей другого. Хотя впоследствии все эти "супер-шифры" оказались слегка поднавороченными шифрами простой замены или сдвига, все упорно программировали в надежде создать идеальный шифр.
В результате были созданы программы, зашифровывающие и расшифровывающие тексты различными методами. Shifr2 использует усложнённый сдвиг, а Scital шифрует сциталью, роль ключа играют размеры таблицы.
Кроме того, М. Овчинников создал программу Decrypt, взламывающую шифр простой парной замены методом частотного анализа (см. Дополнение 2). Можно использовать различные таблицы частот и редактировать расшифровку.
Что такое Сциталь.
Сциталь - это шифр замены, в котором символы меняются местами с помощью таблицы.
Алгоритм шифровки сциталем:
1. Определить размеры таблицы и записать в неё текст по строкам.
2. Если текст не помещается в одну таблицу, создайте еще одну таблицу того же размера, что и первая, и запихайте в нее остаток текста. Если текста не хватает, дополните его пробелами.
3. Записанный в таблицу текст выпишите по столбцам.
4. Для более сложного шифра засциталируйте текст несколько раз, но рано или поздно он примет исходный вид.
Алгоритм расшифровки засциталированного текста:
1. Узнать размеры таблицы и записать в неё текст по столбцам.
2. Если текст не кончился, нарисуйте ещё одну таблицу и допишите в неё остатки текста.
3. Выписать текст по строкам и прочитать его.
4. Если текст не расшифруется, повторите предыдущие пункты.
5. Если у вас всё равно ничего не получилось, то у вас неправильная таблица.
| П | Р | О | Е | К |
| Т | Ш | И | Ф | |
| Р | О | В | К | А |
| П | Т | Р | Р | |
| О | О | Ш | В | Е |
| И | К | К | Ф | А |
Пусть есть таблица с текстом m x n. Есть утверждение, что после p сциталирований символ, в исходном тексте имевший номер k, будет иметь номер knp mod (mn-1) (обозначим это число как k'). При этом нумерация строк, столбцов и символов начинаются с 0.
Доказательство по индукции:
Перед сциталированием номер строки, где находится символ, равен k' mod n, а столбца - k' div n.
Тогда
k=m(k' mod n)+k' div n.
Возьмём выражение
n(m(k' mod n)+k' div n) mod (mn-1) = nk mod (mn-1).
Преобразуем его:
n(m(k' mod n)+k' div n) mod (mn-1) =
= (mn(k' mod n)+n(k' div n)) mod (mn-1) =
= ((mn-1)(k' mod n)+k'-k' mod n+k' mod n) mod (mn-1) = k'
Получаем k'.
Мы доказали, что nk mod (mn-1)=k'. Это - база индукции.
Теперь переход: нужно доказать, что
((npk) mod (mn-1))'=(np+1k) mod (mn-1).
Делаем это так:
((npk) mod (mn-1))'=
= (n((npk) mod (mn-1))) mod (mn-1) =
= (n npk) mod (mn-1) =
= (np+1k) mod (mn-1)
Утверждение доказано.
Далее, после нескольких сциталирований текст примет исходный вид. Чтобы узнать это число, нужно найти p через m и n с помощью уравнения (npk) mod (mn-1)=k. Сделано этого не было.
Принцип взлома шифров программой Decrypt.
Программа использует достаточно простой и эффективный метод частотного анализа. После создания отсортированной таблицы частот программа сравнивает её с заранее выбранной пользователем стандандартной таблицей и выводит результаты замены на экран. После проведения стандартного анализа пользователь может сам редактировать выданный программой результат, а затем сохранить результаты работы в файл.
Примечание: За неимением времени автор не успел сделать программу, работающую с шифром непарной замены, то есть программа дает хорошие результаты на шифрах с таблицей замены вида:
А Б
Б А
В Ю
Ю В и т.д.