шифрование по известному коду и перевод в различные сс как решать

Шифрование по известному коду и перевод в различные сс как решать

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Для кодирования букв Д, X, Р, О, В решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ХОРОВОД таким способом и результат запишите восьмеричным кодом.

Для кодирования букв О, К, Г, Д, Р решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ГОРОДОК таким способом и результат запишите восьмеричным кодом.

Для кодирования букв X, Е, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ЛЕДОХОД таким способом и результат запишите шестнадцатеричным кодом.

Для кодирования букв И, Д, Т, О, X решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ТИХОХОД таким способом и результат запишите шестнадцатеричным кодом.

Для кодирования букв Р, С, Н, О, Г решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв НОСОРОГ таким способом и результат запишите восьмеричным кодом.

Для кодирования букв Е, П, Н, Ч, Ь решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ПЕЧЕНЬЕ таким способом и результат запишите в восьмеричной системе счисления.

Источник

Взлом шифра Виженера с помощью частотного криптоанализа

На Хабре уже пару раз мелькали статьи о книге Чарльза Уэзерелла «Этюды для программистов». Перед вами фрагмент одного из самых интересных, на мой взгляд, этюдов — «Секреты фирмы», основной задачей в котором является взлом шифра Виженера. Не так давно я реализовал этот этюд, и в моей статье я расскажу о том, как я это сделал и что в итоге получилось.

Задача

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

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

Идея решения

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

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

Таким образом, программа будет состоять из трех частей:
1) Определение длины ключевого слова
2) Поиск ключевого слова
3) Поиск перестановки алфавита и расшифровка текста

Длина ключевого слова

Длину ключевого слова проще всего найти, используя метод индекса совпадений. Этот метод был предложен Уильямом Фридманом в 1922 году для взлома оригинального шифра Виженера, но он сработает и в нашем случае. Метод основан на том факте, что вероятность совпадения двух случайных букв в некотором достаточно длинном тексте (индекс совпадений) — это постоянная величина. Таким образом, если разбить текст на L групп символов, каждая из которых зашифрована шифром простой замены (напомню, это и означает, что L — длина ключевого слова), то индексы совпадений для каждой из групп будут довольно близки к теоретическому значению этой величины; для всех других разбиений индексы совпадений будут гораздо ниже. Индекс совпадений можно посчитать по формуле

(fi — количество i-х букв алфавита в тексте, а n — его длина)

Ниже, например, приведены индексы совпадений для текста, зашифрованного с помощью ключа «проект» (6 символов).

Таким образом, для определения длины ключевого слова нужно посчитать индексы совпадений для разбиения текста на L = 1, 2,… групп, а затем выбрать из полученных величин первую, значительно превосходящую большинство остальных. Но… тут есть небольшая хитрость. Что если текст зашифрован с использованием ключа, который можно разделить на несколько похожих частей? Снизу приведена таблица индексов совпадений для того же текста, что и в первом примере, но зашифрованного с помощью ключа «космос» (те же 6 символов). Как же определить длину ключа в таком случае?

Я поиграл с различными способами и выяснил, что проще всего выбрать необходимый индекс так: нужно взять первый индекс, для которого справедливо: 1.06*ИС > ИСi, i = 1, 2,… Умножения на 1.06 в большинстве случаев хватает, чтобы настоящий ИС стал превосходить «кратные» ИС (в нашем примере это индексы при L = 12 и 18), но недостаточно для того, чтобы ложные индексы (при L = 3, 9 и 15) превзошли настоящие.

Конечно, мой способ не дает 100% результат. Более того, если текст зашифрован с помощью слова, состоящего из одинаковых частей (например, «тартар»), то длина ключевого слова в любом случае будет определена неверно (если, конечно, мы хотим найти осмысленное ключевое слово): нет никакой разницы между шифрованием ключом «тартар» и «тар». Поэтому важно дать пользователю возможность изменять длину ключа в ходе работы программы: к примеру, не подошла 6, значит, стоит попробовать 3 или 12.
К счастью, для зашифрованной записки из книги все определяется довольно просто. Взглянув на таблицу индексов совпадений, можно с уверенностью сказать, что длина ключевого слова — 7 символов.

Ключевое слово

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

Проблема заключается лишь в том, что наилучшее слово далеко не всегда является ключевым. Тесты показали, что уже для текстов из 1024 символов ключ и лучшее слово зачастую различаются на один символ. Например, лучшее слово для записки из книги — «федиска». Не знаю я такого слова! Для более коротких текстов ключ определяется совершенно неверно. Поэтому от поиска ключа на основании только таблицы пришлось отказаться.

Второй способ поиска ключа простой и неинтересный, зато эффективный. Мы берем словарь и вычисляем характеристику каждого подходящего слова (для повышения скорости работы программы я разделил слова по их длинам). Лучшее слово мы берем в качестве ключевого. Такой метод работает корректно даже для коротких (400-500 символов) текстов, но у него есть очевидный недостаток: если ключевого слова нет в словаре, то программа ни при каких условиях не сработает верно.

Впрочем, если ключ в словаре есть, второй метод гораздо эффективнее первого. Поэтому в своей программе я использовал его. Этот метод сразу же дал правильное (как выяснилось позднее) ключевое слово — «редиска».

Перестановка алфавита

(b_ij — количество биграмм в «расшифрованном» тексте, а p_ij — вероятность встречи определенной биграммы в русском языке)

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

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

Также интересно взглянуть на графики зависимости номера итерации от номера успешного изменения таблицы перестановок (слева) и характеристики текста от номера изменения таблицы (справа).

Мы видим, что характеристика текста изменяется с каждым изменением таблицы перестановок более-менее линейно, а число попыток, необходимых для нахождения нового успешного изменения таблицы растет довольно быстро. Зависимость характеристики текста от числа итераций похожа на логарифмическую. Действительно, по нижним графикам видно, что если x — число итераций, y — характеристика и t — номер успешного изменения таблицы, то x∼e^t, y∼t, следовательно, y∼ln(x). Логарифм растет довольно медленно, но его рост не ограничен асимптотами, поэтому на нахождение правильной таблицы соответствий уходит довольно большое, но не бесконечное количество работы. Впрочем, тесты показывают, что 10 — 12 тысяч итераций всегда достаточно.

Заключение

После реализации описанных алгоритмов и добавления графического интерфейса получилась вот такая программа:

Программа успешно расшифровывает тексты длиной 400-500 символов и больше, время работы не превышает 10 секунд. Я думаю, это неплохой результат.

Источник

Шифр Виженера

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

Так как Шифр Цезаря у нас уже есть, было бы логично дополнить его калькулятором, который шифрует/расшифровывает текст используя шифр Виженера.

Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.

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

Еще там можно прочитать про вариант шифра с бегущим ключом (running key), который был когда-то был невзламываемым. Этот вариант заключается в использовании в качестве ключа блока текста, равного по длине исходному тексту. Впрочем, и этот вариант, как оказалось, успешно поддается взлому. Проблема с бегущим ключом шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым, но такие системы уже относятся к классу систем одноразового кода, или одноразового шифр-блокнота (one-time pad). Они действительно не поддаются взлому, однако их практическое применение довольно затруднительно.

Источник

Элементарные шифры на понятном языке

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

Прежде всего, разберемся в терминологии.

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

Исходное сообщение – это, собственно, то, что мы хотим зашифровать. Классический пример — текст.

Шифрованное сообщение – это сообщение, прошедшее процесс шифрования.

Шифр — это сам алгоритм, по которому мы преобразовываем сообщение.

Ключ — это компонент, на основе которого можно произвести шифрование или дешифрование.

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

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

Шифр Атбаша

Самый-самый простой шифр. Его суть – переворот алфавита с ног на голову.

Например, есть у нас алфавит, который полностью соответствует обычной латинице.

Для реализации шифра Атбаша просто инвертируем его. «А» станет «Z», «B» превратится в «Y» и наоборот. На выходе получим такую картину:

И теперь пишем нужное сообшение на исходном алфавите и алфавите шифра

Исходное сообщение: I love habr
Зашифрованное: r olev szyi

Шифр Цезаря

Тут добавляется еще один параметр — примитивный ключ в виде числа от 1 до 25 (для латиницы). На практике, ключ будет от 4 до 10.

Опять же, для наглядности, возьмем латиницу

И теперь сместим вправо или влево каждую букву на ключевое число значений.

Например, ключ у нас будет 4 и смещение вправо.

Исходный алфавит: a b c d e f g h i j k l m n o p q r s t u v w x y z
Зашифрованный: w x y z a b c d e f g h i j k l m n o p q r s t u v

Пробуем написать сообщение:

Шифруем его и получаем следующий несвязный текст:

Шифр Вернама (XOR-шифр)

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

Исходный алфавит — все та же латиница.

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

Теперь вспомним курс электроники и элемент «Исключающее ИЛИ», также известный как XOR.

XOR принимает сигналы (0 или 1 каждый), проводит над ними логическую операцию и выдает один сигнал, исходя из входных значений.

Если все сигналы равны между собой (0-0 или 1-1 или 0-0-0 и т.д.), то на выходе получаем 0.
Если сигналы не равны (0-1 или 1-0 или 1-0-0 и т.д.), то на выходе получаем 1.

Теперь для шифровки сообщения, введем сам текст для шифровки и ключ такой же длины. Переведем каждую букву в ее бинарный код и выполним формулу сообщение XOR ключ

сообщение: LONDON
ключ: SYSTEM

Переведем их в бинарный код и выполним XOR:

В данном конкретном примере на месте результирующих символов мы увидим только пустое место, ведь все символы попали в первые 32 служебных символа. Однако, если перевести полученный результат в числа, то получим следующую картину:

С виду — совершенно несвязный набор чисел, но мы-то знаем.

Шифр кодового слова

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

Например, возьмем для разнообразия, кириллический алфавит.

Придумаем кодовое слово. Например, «Лукоморье». Выдернем из него все повторяющиеся символы. На выходе получаем слово «Лукомрье».

Теперь вписываем данное слово в начале алфавита, а остальные символы оставляем без изменений.

И теперь запишем любое сообщение и зашифруем его.

Получим в итоге следующий нечитаемый бред:

Шифр Плейфера

Классический шифр Плейфера предполагает в основе матрицу 5х5, заполненную символами латинского алфавита (i и j пишутся в одну клетку), кодовое слово и дальнейшую манипуляцию над ними.

Пусть кодовое слово у нас будет «HELLO».

Сначала поступаем как с предыдущим шифром, т.е. уберем повторы и запишем слово в начале алфавита.

Теперь возьмем любое сообщение. Например, «I LOVE HABR AND GITHUB».

Разобьем его на биграммы, т.е. на пары символов, не учитывая пробелы.

Если бы сообщение было из нечетного количества символов, или в биграмме были бы два одинаковых символа (LL, например), то на место недостающего или повторившегося символа ставится символ X.

Шифрование выполняется по нескольким несложным правилам:

1) Если символы биграммы находятся в матрице на одной строке — смещаем их вправо на одну позицию. Если символ был крайним в ряду — он становится первым.

Например, EH становится LE.

2) Если символы биграммы находятся в одном столбце, то они смещаются на одну позицию вниз. Если символ находился в самом низу столбца, то он принимает значение самого верхнего.

Например, если бы у нас была биграмма LX, то она стала бы DL.

3) Если символы не находятся ни на одной строке, ни на одном столбце, то строим прямоугольник, где наши символы — края диагонали. И меняем углы местами.

Например, биграмма RA.

По этим правилам, шифруем все сообщение.

Если убрать пробелы, то получим следующее зашифрованное сообщение:

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

Источник

Шифрование по известному коду и перевод в различные сс как решать

Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Если искомое десятичное число при переводе в другую систему счисления дает последним разрядом 0, это значит, что оно делится на основание этой системы счисления без остатка. Минимальное натуральное десятичное число, имеющее делителями 3 и 5 — это 15.

Я не могу понять: почему не подходит число 0?

Там ведь не сказано из скольких цифр должно состоять число.

Ноль не является натуральным числом.

Ответ запишите в троичной системе (основание системы счисления в ответе писать не нужно).

Основание системы счисления равно 6₁₀ = 20₃.

В системе счисления с некоторым основанием десятичное число 18 записывается в виде 30. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17 в системе счисления с основанием 5.

Запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 5: Запишем по порядку числа от до

Всего цифра «2» встречается 7 раз (два раза в числе 22₅ и по одному разу в числах 20₅, 21₅, 23₅, 24₅ и 32₅).

Укажите, сколько всего раз встречается цифра 3 в записи чисел 19, 20, 21, …, 33 в системе счисления с основанием 6.

Запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 6:

Запишем по порядку числа, в записи которых встречается цифра 3, от до : 31₆, 32₆, 33₆, 34₆, 35₆, 43₆, 53₆. Всего цифра «3» встречается 8 раз.

Аналоги к заданию № 2307: 2314 2323 Все

«Запишем по порядку числа, в записи которых встречается цифра 3, от до : 316, 326, 336, 346, 356, 436, 536. Всего цифра «3» встречается 8 раз.

И тогда ответ получается: 11.

В системе счисления с основанием 6 не может быть цифр 6, 7, 8, 9.

смотрите, вы пишите: «Запишем по порядку числа, в записи которых встречается цифра 3, от до : 31, 32, 33, 34, 35, 43, 53. Всего цифра «3» встречается 8 раз. «

посчитайте внимательно тут не 8 чисел а 7!

«Укажите, сколько всего раз встречается цифра 3 в записи чисел» В записи числа 33 две цифры 3.

В системе счисления с некоторым основанием десятичное число 49 записывается в виде 100. Укажите это основание.

где — основание этой системы счисления. Исходя из уравнения,

Укажите, сколько всего раз встречается цифра 2 в записи чисел 13, 14, 15, …, 23 в системе счисления с основанием 3.

Запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 3:

Запишем все числа из заданного диапазона, содержащие цифру «2»: 112, 120, 121, 122, 200, 201, 202, 210, 211, 212. Итого 2 встречается 13 раз.

Аналоги к заданию № 2307: 2314 2323 Все

В системе счисления с некоторым основанием десятичное число 25 записывается как 100. Найдите это основание.

где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием число 12₁₀ записывается в виде 110_x. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 24 записывается в виде 30. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 36 записывается в виде 40. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 28 записывается в виде 40. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 24 записывается в виде 40. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 24 записывается в виде 40. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 27 записывается в виде 30. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 21 записывается в виде 30. Укажите это основание.

Составим уравнение: где — основание этой системы счисления. Исходя из уравнения,

В системе счисления с некоторым основанием десятичное число 15 записывается в виде 30. Укажите это основание.

Составим уравнение: 30_n = 3 · n 1 + 0 · n 0 = 15₁₀, где n— основание этой системы счисления. Откуда n = 5.

В системе счисления с некоторым основанием десятичное число 12 записывается в виде 30. Укажите это основание.

Составим уравнение: 30_n = 3 · n 1 + 0 · n 0 = 12₁₀, где n— основание этой системы счисления. Откуда n = 4.

В системе счисления с основанием N запись числа 87₁₀ оканчивается на 2 и содержит не более двух цифр. Перечислите через запятую в порядке возрастания все подходящие значения N.

Пусть первая цифра в записи числа 87 в N-ой системе счисления есть . — целое число и .

Тогда . То есть 87 mod N = 2. Тогда 85 делится на N без остатка. .

Если N = 5, то x = 17, но .

N = 17 и N = 85 − подходят.

В системе счисления с основанием N запись числа 87₁₀ оканчивается на 2 и содержит не менее трёх цифр. Чему равно число N?

Пусть y — предпоследняя цифра числа 87 при записи в N-ой системе счисления, .

Пусть . Тогда , ведь при всех больше 1. Но 0 не может быть в начале числа. Тогда

Источник