Гаммирование

Реализация и криптоанализ шифра гаммирования

Гаммирование

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

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр гаммирования

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

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

Расшифровка выполняется аналогичным образом. Складываем символы зашифрованного текста с символами гаммы и получаем открытый текст.

Реализация шифра гаммирования на Python

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

Функция шифрования

На вход поступает открытый текст без пробелов, в виде массива символов, и ключ — гамму. Анализируем длину текста, «растягиваем» гамму до нужного размера и выполняем посимвольное сложение.

def encrypt(text, gamma):    textLen = len(text)    gammaLen = len(gamma)     #Формируем ключевое слово(растягиваем гамму на длину текста)    keyText = []    for i in range(textLen // gammaLen):        for symb in gamma:            keyText.append(symb)    for i in range(textLen % gammaLen):        keyText.append(gamma[i])     #Шифрование    code = []    for i in range(textLen):        code.append(alphabeth[(alphabeth.index(text[i]) + alphabeth.index(keyText[i])) % 26])     return code

Функция расшифрования

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

def decrypt(code, gamma):    codeLen = len(code)    gammaLen = len(gamma)     #Формируем ключевое слово(растягиваем гамму на длину текста)    keyText = []    for i in range(codeLen // gammaLen):        for symb in gamma:            keyText.append(symb)    for i in range(codeLen % gammaLen):        keyText.append(gamma[i])     #Расшифровка    text = []    for i in range(codeLen):        text.append(alphabeth[(alphabeth.index(code[i]) — alphabeth.index(keyText[i]) + 26) % 26])     return text

Реализация взлома шифра гаммирования

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

По традиции можно выделить два основных этапа.

  1. получение длины гаммы.
  2. получение значения гаммы.

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

Где n — длина текста, f_i — количество появлений в тексте i-го символа алфавита.

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

На практике я заметил, что если длина подходящая, то индекс первого столбца будет гарантированно превышать значение 0.053. А когда длина плохая, он будет колебаться от 0.03 до 0.044.

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

Где f_i — количество появлений i-го символа в первом столбце, g_i — во втором, n — длина первого столбца, n — длина второго. В нашем случае n = n`, столбцы одинаковой длины.

Мы разбиваем код на столбцы по длине гаммы, которую нашли на прошлом этапе, и перебираем все их пары, начиная с первого. У второго столбца в паре перебираем все сдвиги(от 1 до 26) и считаем для каждого взаимный индекс совпадений. В тот момент, когда индекс будет близок к 0.066, запоминаем смещение и переходим к следующей паре столбцов.

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

Источник: http://MindHalls.ru/gamma-code/

Режим гаммирования ГОСТ 34.13. Блочные алгоритмы шифрования

Гаммирование

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

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

Блочные алгоритмы шифрования ГОСТ 34.13

Для начал вот несколько ссылкок, про то, как применять блочные криптоалгоритмы «Кузнечик» и «Магма» для шифрования сообщений, размер которых превышает размер одного блока (для «Кузнечика» он составляет 16 байт, а для «Магмы» — 8 байт) с использованием режима простой замены (ECB, от английского Electronic Codebook). Этот режим описан в ГОСТ 34.13—2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров». Этот нормативный документ, помимо режима простой замены, определяет еще несколько способов применения блочных шифров, а именно:

  • режим гаммирования (CTR, от английского Counter);
  • режим гаммирования с обратной связью по выходу (O, от английского Output Feedback);
  • режим простой замены с зацеплением (CBC, от английского Cipher Block Chaining);
  • режим гаммирования с обратной связью по шифртексту (C, от английского Cipher Feedback);
  • режим выработки имитовставки (MAC, от английского Message Authentication Code).

Что ж, давайте разберемся, как работает гаммирование и как его применять на практике.

Общие принципы реализации режима гаммирования

В настоящее время ГОСТ 34.12—2015 и ГОСТ 34.13—2015 обрели статус межгосударственных (в рамках нескольких государств СНГ) и получили наименования соответственно ГОСТ 34.12—2018 и ГОСТ 34.13—2018. Оба стандарта введены в действие в качестве национальных стандартов Российской Федерации с 1 июня 2019 года.

Гамма шифра

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

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

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

Принцип реализации режима гаммирования при зашифровывании сообщения

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

Принцип реализации режима гаммирования при расшифровывании сообщения

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

Усечение блока гаммы при несовпадении размеров блока исходного сообщения и блока гаммы

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

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

Псевдослучайность блоков гаммы при этом реализуется путем шифрования этого вектора с использованием выбранного алгоритма (мы используем «Магму»).

Инициализирующий вектор

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

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

РЕКОМЕНДУЕМ:
Поиск энтропии на микросхеме для повышения стойкости шифра

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

В случае «Магмы» длина синхропосылки равна четырем байтам, длина инициализирующего вектора — восьми.

Вторая часть инициализирующего вектора (заполненная нулями) будет использоваться в качестве того самого счетчика (Counter), который и лег в основу англоязычного сокращения CTR.

Выработка инициализирующего вектора в режиме гаммирования с алгоритмом блочного шифрования «Магма»

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

Выработка гаммы шифра

Зашифровываем и расшифровываем

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

Зашифровывание в режиме гаммирования

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

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

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

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

Дешифровка в режиме гаммирования

Пишем необходимые функции

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

Ксорим блоки гаммы и текста

Для начала определим функцию сложения блоков по модулю 2.

void add_xor(const uint8_t *a, const uint8_t *b, uint8_t *c)  for (i = 0; i > 8);    ctr[i] = internal & 0xff;

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

Удаляем ключи из памяти

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

void GOST_Magma_Destroy_Key()    memset(iter_key[i], 0x00, 4);

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

Ссылки

Заключение

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

РЕКОМЕНДУЕМ:
Что такое и как работает IPsec

В этой статье режим гаммирования рассмотрен применительно к алгоритму «Магма», но если понадобится «Кузнечик», то нет проблем — все необходимые функции мы уже написали.

(5 5,00 из 5)
Загрузка…

Источник: https://tech-geek.ru/gost-34-13/

Принцип шифрования гаммированием

Гаммирование

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

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

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

В этом случае криптостойкость определяется размером ключа.

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

Метод гаммирования с обратной связью

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

1. Генерация сегмента гаммы H(1) и наложение его на соответствующий участок шифруемых данных.

2. Подсчет контрольной суммы участка, соответствующего сегменту гаммы H(1).

3. Генерация с учетом контрольной суммы уже зашифрованного участка данных следующего сегмента гамм H(2).

4. Подсчет контрольной суммы участка данных, соответствующего сегменту данных H(2) и т.д.

Под контрольной суммой понимают функцию f(t(1), … t(n)), где t(i) – i-е слово шифруемых данных.

Зашифруем исходный текст “абв”, представленный в виде последо-вательности 00001 00010 00011. Пусть A=5; C=3;b=5; M=32;T(0)=7. Тогда:

T(1)=(5*7+3) mod 32 = 6 (00110).

В качестве контрольной суммы участка данных, выберем количество единиц на этом участке. Тогда сегменту H(1) соответствует участок 00001, количество единиц равно 1.

T(2)=(5*1+3) mod 32 = 8 (01000).

Контрольная сумма следующего участка (00010) равна 1.

T(3)=(5*1+3) mod 32 = 8 (01000).

Полученная шифрограмма:

00001 00010 00011

00110 00001 01000

00111 00011 01011

что соответствует тексту “еик”.

Описание исходных данных

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

Варианты индивидуальных заданий

Генераторы ПСЧ

№ варианта

Вид генератора ПСЧ

Количество разрядов b

6

Гаммирование с обратной связью

8

Алгоритм работы программы

1 Считывание исходной строки.

2 Если перебор всех символов строки еще не окончен, то выбирается очередной символ, иначе переход к п.7.

3 Получение очередного псевдослучайного числа, при помощи ПСЧ датчика.

4 Определяем код (Unicode) текущего символа в алфавите.

5 Выполняем сложение по модулю 2 порядкового номера и псевдослучайного числа и выбираем символ из алфавита с полученным порядковым номером.

6 Прибавляем полученный символ к кодовой последовательности и переходим к п.2.

7 Конец.

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

Текст программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace ZILAB2

{

public partial class Form1 : Form

{

int state;

int A, b, C, M,T0;

private void button2_Click(object sender, EventArgs e)

{

Close();

}

public Form1()

{

InitializeComponent();

state = 1;

A = 5;

C = 3;

b = 8;

M = (int)Math.Pow(2, b);

T0 = 7;

}

int T(int t)

{

return (A * t + C) % M;

}

Int32 H(char c)

{

Int32 res=0;

for (byte i = 0; i < 32; i++) if ((1 & (((Int32)c) >> i)) > 0) res++;

return res;

}

char[] GetChars()

{

return textBox1.Text.ToCharArray();

}

void SetChars(char[] c)

{

textBox1.Clear();

textBox1.Text = new String(c);

}

char[] crypt(char[] msg,bool f)

{

int oldh=T0;

char[] res = new char[msg.Length];

for (int i = 0; i < msg.Length; i++)

{

res[i] = (char)(T(oldh) (int)msg[i]);

if (f) oldh = H(msg[i]);

else oldh = H(res[i]);

}

return res;

}

private void button1_Click(object sender, EventArgs e)

{

switch (state)

{

case 1://Зашифровать

{

groupBox1.Text = “Криптограмма“;

button1.Text = “Расшифровать“;

SetChars(crypt(GetChars(),true));

state = 2;

break;

}

case 2://Расшифровать

{

groupBox1.Text = “Исходный текст“;

button1.Text = “Зашифровать“;

SetChars(crypt(GetChars(),false));

state = 1;

break;

}

}

}

}

}

Результаты работы программы

Исходный текст криптограммы:

После шифрования:

После пасшифровки:

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

Обсудите на форуме куда поехать, туризм. www.voyagetravel.org – форум о путешествиях и туризме.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Источник: http://crypto.pp.ua/2010/04/82/

Все термины
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: