Поворотная решетка шифр как сделать

Добавил пользователь Евгений Кузнецов
Обновлено: 18.09.2024

1) расскажите, как можно 4-рьмя способами наложить прямоугольный трафарет на прямоугольный лист ? (схемку или рисунок набросайте, плиз. - и Вам полезно будет, и для непонимающих (вроде меня) более понятно.

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

ну в принципе то можно. наложить трафарет на лист(1й вариант), повернуть трафарет на 180 в плоскости параллельной листу(2й вариант). перевернуть трафарет другой стороной и повторить. как раз 4 варианта выходит.

Угу. спасибо. Скорее всего, Вы правы.

ну, если честно, я тоже представлял себе такой вариант (а других я и не смог придумать - для прямоугольного трафарета!).

кстати, очевидно, что для поля размером 2m*2n прорезей в трафарете должно быть m*n. Но, имхо, этого мало. расположение всех прорезей не может быть произвольным - нужно, чтобы при поворотах они не перекрывали друг друга.
Т.е. для каждой прорези строго не должно быть прорези симметричной ей относительно центра шаблона.

насколько я понял простейший трафарет будет для поля 2х2 и будет из одной вырезаной ячейки в четверть трафарета.
По сути вопроса - помоему всё более менее просто.
Сам трафарет я представляю так: ты проходишься по четверти площади трафарета и беря рэндомное значение от 1 до 4 для каждой ячейки в зависимости от этого значения "делаешь прокол" в трафарете - либо в оригинальной четверти, либо в повёрнутой на 180 градусов, либо в перевёрнутых двух вариантах трафарета.
А дальше запомнив полученый трафарет я думаю тоже всё несложно. я бы сделал два вложенных цикла с переменными 1 и -1 и прикрутить к этому всему перебор по координатам трафарета, переменные циклов взяв как коэфициенты.

Кажись готовый алгоритм.

насколько я понял текст пишется подряд( построчно, слева-направо) т.е. если по очереди поставить трафарет во все 4 варианта должен получиться связный текст.

набросал в блокноте примерно следующее

* 0 0 *
0 * * 0
0 1 * 0
1 0 0 *

* 0 0 0 0 0 0 *
0 * 0 0 0 0 * 0
0 0 * 0 0 * 0 0
0 0 0 * * 0 0 0
0 0 0 1 * 0 0 0
0 0 1 0 0 * 0 0
0 1 0 0 0 0 * 0
1 0 0 0 0 0 0 *

вообщем можно мысленно все поле разбить на квадраты.
половина нужного количества проколов делается в углах этих квадратов. остальные на их сторонах. текст разбить на 4 части. и проколы соответствующие каждой части текста делать в одном выбранном положении трафарета. составить что-то типо ключа. напр 3 2 1 4. только надо условиться какое положение трафарета будет под каким номером.

матрица 8х8
ставишь первый прокол в координатах [5,4]
значит координаты 4,4;4,5;5,5 - нельзя использовать

дальше ставишь в координатах [6,3]
координаты 3,3;3,6;6,6; нельзя использовать

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

Проблема: незнание способов шифрования.

Цель: изучить способы шифрования и создать шифры.

Объект исследования: шифрование.

Предмет исследования: способы шифрования.

Гипотеза исследования: узнаем о шифровании и проверим на практике некоторые способы шифрования.

поиск информации о шифровании;

изучение истории шифра;

выделение способов шифрования;

создание своего шифра;

поиск и анализ информации;

Практическая значимость проекта заключается в возможности использования шифров для создания паролей в повседневной жизни.

Глава I . Основная часть. 1.1 История шифрования

Криптография и шифрование тысячи лет используются людьми для защиты разного рода информации. Самый древний текст с элементами криптографии найден в гробнице древнеегипетского вельможи Хнумхотепа II, наследного князя и номарха города Менат-Хуфу, жившего почти 4000 лет назад. Среди иероглифов он использовал несколько необычных символов, которые скрывают прямое значение текста. Такой метод шифрования фактически представляет собой шифр подстановки , когда элементы исходного текста заменяются другими элементами по определённым правилам .

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

В середине XV века итальянский учёный, архитектор, скульптор, художник и математик Леон Батиста Альберти изобрёл систему шифрования на основе шифровального диска . Устройство представляло собой пару дисков разного диаметра. Внешний диск был неподвижным, в него вписывались буквы, расположенные в естественном порядке. Во внутренний подвижный диск, по его окружности были вписаны все буквы смешенного алфавита. Процесс шифрования заключался в нахождении буквы открытого текста на внешнем диске и замену ее на соответствующую (стоящей под ней) букву шифрованного текста. После шифрования нескольких слов диск сдвигался на один шаг. Ключом данного шифра являлся порядок расположения букв на внутреннем диске и его начальное положение относительно внешнего диска.

В XVI веке французский дипломат Блез Виженер на основе концепции многоалфавитного шифра Альберти создал шифр, который получил название шифра Виженера . Он работает точно как система Цезаря за исключением того, что ключ меняется в процессе шифрования. В шифре Виженера применяется решётка из букв, которая задаёт метод подстановки. Её называют квадратом Виженера или таблицей Виженера. Решётка состоит из 26 строк алфавита со смещением на один символ друг относительно друга.

Метод смены одного ключа на другой следует простому шаблону. В качестве ключа шифрования выбирается специальное секретное слово. Каждый символ в исходном тексте заменяется с использованием таблицы. Чтобы определить, на какую букву нужно заменить первый символ, мы совмещаем первый символ исходного текста (по одной оси) с первым символом секретного слова (по другой оси). Метод повторяется для второй и каждой последующей букв, секретное слово используется многократно, пока не закончатся символы в исходном тексте.

В конце XVIII века Томас Джефферсон придумал шифровальную систему , очень похожую на шифр Виженера, но с лучшей защитой. Его шифратор состоял из 26 дисков с буквами алфавита, случайно размещёнными на каждом из них. Диски были пронумерованы и установлены на цилиндр в определённом порядке. Ключом является порядок дисков на оси.

История переписки хранится только на двух устройствах, посредством которых был инициирован чат и удаляется автоматически по истечении определённого времени.

Еще один интересный пример загадочной книги - Кодекс Серафини. Хотя в отличие от Манускрипта Войнича известно, что это творение итальянского архитектора Луиджи Серафини, в котором он изображает таинственный мир, однако, немногочисленный текст этого кодекса до сих пор не расшифрован.

У криптографии даже есть свои памятники– это статуя У Криптос, у офиса ЦРУ в США. Она представляет собой 4 страницы с 4 зашифрованны ми посланиями, которые сделал американский художник Джеймс Санборн. На сегодняшний момент расшифрованы только 3 из 4 посланий.

1.2 Применение шифрования

Шифрование можно использовать для защиты следующих типов данных в сети:

• закрытая передача данных;

• безопасное хранение файлов;

• аутентификация пользователя или компьютера;

• безопасный обмен паролями.

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

Шифрование может быть использовано для защиты данных в устройстве хранения, например данных на жестком диске. Лучший подход к безопасности — предоставить шифрование и расшифровку файлов операционной системе. Данные обычно шифруют для ограничения доступа к ним третьим лицам. И, специально для этого Microsoft разработала систему шифрования данных EFS. Начиная с Windows 2000 и во всех более поздних версиях операционных систем присутствует система шифрования данных. С помощью EFS можно шифровать отдельные файлы и папки.

Работает EFS следующим образом. Когда необходимо зашифровать файл система генерирует случайный ключ называемый FEK — File Encryption Key . Этим ключом с помощью симметричного алгоритма шифрования кодируется файл. Симметричный — значит файл шифруется и расшифровывается одним ключом — FEK.

При первой необходимости шифрования информации Windows создает два ключа пользователя: открытый и закрытый . FEK шифруется с помощью асимметричного алгоритма с использованием открытого ключа пользователя. Асимметричный алгоритм шифрования значит, что файл шифруется одним ключом (в нашем случае открытым), а расшифровывается другим (закрытым). Зашифрованный ключ FEK записывается рядом с зашифрованным файлом.

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

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

При входе в операционную систему Microsoft, например Windows 95, Windows NT или Windows 2000, операционная система не сравнивает введенный пароль с хранимым паролем. Вместо этого она шифрует пароль при помощи однонаправленной криптографической функции и затем сравнивает результат с хранящимся результатом. Многие другие операционные системы работают точно так же. Храня только криптографическое хэш - значение пароля пользователя, операционная система затрудняет хакерам возможность получения всех паролей системы при получении.

Цифровые подписи полезны, потому что проверить подпись может каждый, а создать ее может только лицо с закрытым ключом. Разница между цифровой подписью и сертификатом в том, что можно проверить подлинность сертификата в центре сертификации.

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

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

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

Глава II . Практическая часть. 2.1 Классификация шифров

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

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

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

Существует несколько классификаций шифров. Рассмотрим некоторые из них(см.Приложение).

I. По области применения различают шифры ограниченного и общего использования.

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

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

II. По особенностям алгоритма шифрования шифры общего использования можно разделить на следующие виды: одноключевые (симметричные), двухключевые (ассиметричные), комбинированные (составные).

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

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

Асимметричные алгоритмы шифрования — это алгоритмы, в которых для шифрования и расшифрования используются разные, но математически связанные между собой ключи. Такие связанные ключи называются криптопарой. Один из них является закрытым (private), второй является открытым (public). При этом информация, зашифрованная на открытом ключе, может быть расшифрована только с помощью закрытого ключа, и наоборот, то, что зашифровано закрытым, можно расшифровать только с помощью открытого ключа.

Комбинированный метод шифрования объединяет в себе симметричный и асимметричный виды шифрования, но свободен от присущих им недостатков.

Для установления общения с абонентом с помощью этого метода следует:

1. Каждый из абонентов создает пару асимметричных ключей, после чего происходит обмен открытыми ключами. У вас есть секретный ключ и открытый ключ друга (абонента).

2. Сохраняется удобство обмена асимметричными ключами.

3. Результат: быстрое шифрование с удобным обменом ключами.

IV. По стойкости шифры делятся на три группы:

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

- вычислительная сложность полного перебора;

- известные на данный момент слабости (уязвимости) и их влияние на вычислительную сложность;

2.2 Создание шифра

Решетка Кардано знакома каждому, кто хоть раз смотрел бессмертный советский сериал с Василием Ливановым в роли Шерлока Холмса. В заглавных титрах одной из серий этого фильма показана идея шифрования решеткой Кардано.

Решетка Кардано может быть двух видов — простая и симметрично-поворотная. В первом случае для шифрования применяется трафарет с отверстиями, через которые "фильтруется" полезный текст. Другой вариант решетки, более интересный, состоит в том, чтобы использовать симметричный (квадратный) трафарет, который можно применять несколько раз, просто поворачивая его вокруг центра. Поворотная решетка Кардано позволяет записать текст массивом символов так, что результат будет выглядеть совершенно нечитаемым, например:

Решетка Кардано очень практичная и удобная. Чтобы прочитать секретный текст, не нужно "решать кроссворд" или тратить время на обучение секретному языку. Этим шифром предпочитали пользоваться многие известные личности, например кардинал Ришелье и русский драматург и дипломат Александр Грибоедов.

Было решено сделать симметрично-поворотную решетку Кордано. Возьмем тетрадный лист в клетку или разлинуем квадрат, например со стороной в восемь клеток.

По центру квадрата проведем две перпендикулярные черты, отделив четыре зоны. Затем заполним каждую из зон номерами клеток. Нумерацию клеток следует начинать из угла и вести ее так, чтобы направление нумерации каждый раз было по часовой стрелке. В каждой части квадрата есть набор цифр. Теперь в произвольном порядке выберем и закрасим цифры от 1 до 16 так, чтобы числа не повторялись в разных частях решетки (например, если в первой зоне закрашена двойка, то в других зонах ее закрашивать уже не нужно). Закрашенные клетки — это отверстия, которые необходимо вырезать. Квадратная решетка Кардано готова. Приложим ее к листу и впишем текст. Затем повернем ее на 180 градусов и продолжаем писать текст, затем снова повернем и так до тех пор, пока весь квадрат под решеткой не будет заполнен текстом.

Перевернутые группы

Теперь развернем группы, записав каждую с конца.

Переставим определенным образом местами.

Серединная вставка

Алгоритм данного шифрования немного сложнее шифрования методом перестановки:

Рассмотрим на примере.

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

Разделим на половины с равным количеством букв.

И в этих промежутках разместим буквы второй половины.

Наконец сгруппируем буквы в своего рода слова (необязательная операция).

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

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

п	р	и	г	о	т	о	в	л
р	е	д	ы	в	я	с	л	я
ж	а	т	ь	в	о	й	н	у

Шифр будем составлять, начиная с правого верхнего угла таблицы.

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

Вертикальные перестановки

и	с	т	я	г	о	с	т
н	ы	м	п	у	т	е	м
и	с	с	о	с	т	р	а
д	а	н	ь	е	м

Ключ приведен ниже.

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

Обратная расшифровка вертикальной перестановки

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

Решетка Кардано

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

Трафарет Кардано изготавливается по следующему принципу: вырезанные ячейки при повороте на 90° не должны перекрывать друг друга. То есть после 4 поворотов трафарета вокруг своей оси прорези в нем не должны совпадать ни разу.

Используем для примера простую решетку Кардано (на рисунке ниже).

—	О	—	М	—	—
У
З	Ы
К
В	А
М

Заполняем ячейки трафарета буквами по правилу: сначала справа налево, а затем сверху вниз. Когда ячейки кончатся, поворачиваем трафарет на 90° по часовой стрелке. Таким способом получаем следующую таблицу.

Я	—	—	—	—	—
О	Б	Р
А	Щ
у
С	Ь

И еще раз поворачиваем на 90°.

—	—	—	—	—	С
В	О
З
В	А
Н
Ь	Е

И последний поворот.

После объединения 4 таблиц в одну получаем итоговое зашифрованное послание.

Я	О	М	М	Г	С
В	О	У	Б	О	Р
Г	З	А	З	Щ	Ы
В	Г	К	Г	А	У
Г	В	Г	Н	Г	А
М	С	Ь	Ь	Е	Г

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

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

Анализ шифров перестановки

Рис. 1.7. Пример шифрующей таблицы

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

Решетка Кардано. Решетка Кардано (поворотная решетка) — это прямоугольная или квадратная карточка с четным числом строк и столбцов 2k X 2т. В ней проделаны отверстия таким образом, что при последовательном отражении или поворачивании и заполнении открытых клеток карточки постепенно будут заполнены все клетки листа.

Карточку сначала отражают относительно вертикальной оси симметрии, затем — относительно горизонтальной оси, и снова — относительно вертикальной (рис. 1.8).

Если решетка Кардано — квадратная, то возможен и другой вариант ее преобразований — поворот на 90° (рис. 1.9).

Рис. 1.8. Пример использования решетки Кардано

Рис. 1.9. Пример поворотной решетки Кардано

Рис. 1.10. Пример шифрования с помощью решетки Кардано

Получатель должен знать трафарет и наложить его в той же последовательности, что и при шифровании. Ключом является выбранный тип перемещения решетки (отражение или поворот) и трафарет — расположение отверстий, которые для квадратной решетки размером 2т х 2к могут быть выбраны 4"'* способами (с учетом начальной ориентации трафарета). В этом случае среди трафаретов, считающихся различными, будут встречаться такие, которые являются зеркальным отражением или поворотами других трафаретов, т.е. трафареты, различающиеся только начальным расположением (ориентацией). Если пренебречь начальным расположением трафарета, то, очевидно, различных трафаретов будет в 4 раза меньше — 4"'*'

Например, для решеток размером 4X4 существует 256 возможных вариантов трафарета (с учетом начальной ориентации) или всего 64 различных трафаретов.

Несмотря на то, что число трафаретов для больших решеток достаточно велико (порядка 4 млн (4- 10 е )), оно все же существенно меньше, чем случайных перестановок элементов таблицы, число которых равно (2т ? 2k).

Например, для таблицы размером 4x4 число случайных перестановок составляет порядка 2 ? 10 13 , а для таблиц размером 8x8 — около 10 89 .

Решетки Кардано, так же как и шифрующие таблицы, являются частными случаями шифра маршрутной перестановки.

Читайте также:

и	с	т	я	г	о	с	т
н	ы	м	п	у	т	е	м
и	с	с	о	с	т	р	а
д	а	н	ь	е	м

Я	О	М	М	Г	С
В	О	У	Б	О	Р
Г	З	А	З	Щ	Ы
В	Г	К	Г	А	У
Г	В	Г	Н	Г	А
М	С	Ь	Ь	Е	Г

и	с	т	я	г	о	с	т
н	ы	м	п	у	т	е	м
и	с	с	о	с	т	р	а
д	а	н	ь	е	м

Я	О	М	М	Г	С
В	О	У	Б	О	Р
Г	З	А	З	Щ	Ы
В	Г	К	Г	А	У
Г	В	Г	Н	Г	А
М	С	Ь	Ь	Е	Г

и	с	т	я	г	о	с	т
н	ы	м	п	у	т	е	м
и	с	с	о	с	т	р	а
д	а	н	ь	е	м

Я	О	М	М	Г	С
В	О	У	Б	О	Р
Г	З	А	З	Щ	Ы
В	Г	К	Г	А	У
Г	В	Г	Н	Г	А
М	С	Ь	Ь	Е	Г