Краткие теоретические сведения. В основе рассматриваемых систем шифрования лежит метод «наложения» ключевой последовательности – гаммы – на открытый текст

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

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

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

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

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

Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок псевдослучайной последовательности (ПСП) и по нему восстанавливается вся последовательность. Однако, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности.

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

Датчики псевдослучайных чисел (ПСЧ).

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

Конгруэнтные датчики

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

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

T(i+1) = (A*T(i)+C)modm,

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n, где n - длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и А mod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел x(j) размерностью b, где j=1, 2,..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j).

Датчики М-последовательностей

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

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

Строго это можно представить в виде следующих отношений:

r₁:=r₀ r₂:=r_1... r_k-1:=r_k-2

r₀:=a₀r₁ Åa₁r₂ Å...Åa_k-2r_k-1

Г_i:=r_k-1-

Здесь r₀ r_1... r_k-1 - k однобитных регистров, a₀ a_1... a_k-1 - коэффициенты неприводимого двоичного полинома степени k-1. Г_i - i-е значение выходной гаммы.

ПериодМ -последовательности исходя из ее свойств равен 2 ^k -1.

Другим важным свойством М -последовательности является объем ансамбля, т.е. количество различных М -последовательностей для заданного k. Эта характеристика приведена в таблице 3.1.

Таблица 3.1

k	Объем ансамбля

Очевидно, что такие объемы ансамблей последовательности неприемлемы.

Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М -последовательностей. Объемы ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М -последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М -последовательности) до 388000.

Также перспективными представляются нелинейные датчики ПСП (например сдвиговые регистры с элементом “И” в цепи обратной связи), однако их свойства еще недостаточно изучены.

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

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

Шифр Вернама – шифр, в котором открытый текст записан в двоичном виде (последовательность 0;1), ключ - случайная равновероятная двоичная последовательность той же длины, что и открытый ключ, шифрованный текст получается суммированием по модулю 2 (т.е. 0+0=1+1=0, 0+1=1+0=1). Процедура расшифрования совпадает с процедурой шифрования.

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

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

При наличии на руках шифрованного текста

ШИФР = 10011000100010001001010010010000

используя для расшифрования ключ

00010010000000110000101000000111

мы получим открытый текст

КЛЮЧ = 1000 1010 1000 1011 1001 1110 1001 0111

используя для расшифрования ключ

00010111000011010001100100001100

мы получим открытый текст

ПЕНЬ = 10001111100001011000110110011100

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

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

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

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

A + B, если (A+B) меньше C

A + B по модулю C =

A + B -C, если (А+ B) больше или равно С,

A - B, если (A-B) больше или равно нулю

A - B по модулю C =

A - B + C, если (А- B) меньше нуля

Например для С=3 эти операции определяются следующим образом

0+0=0 1+0=1 2+0=2

0+1=1 1+1=2 2+1=0

0+2=2 1+2=0 2+2=1

0-0=0 1-0=1 2-0=2

0-1=2 1-1=0 2-1=1

0-2=1 1-2=2 2-2=0

Пусть каждый знак открытого сообщения может принимать С значений (например для русского алфавита без учетов знаков препинания С=33). Занумеруем их от 0 до (С-1).

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

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

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

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

2. Отсутствие возможности практического восстановления неизвестных отрезков гаммы (в том числе и ключа) по известным.

 

 

#include <iostream>

#include <string>

#include <vector> //что за библиотека? Библиотека подключает тип данных Vector по сути тот же массив

 

using namespace std;

 

string alphavit = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890!@#$%^&*()_+-;:?<>/{}[]\\\"'";

int gen_num(int input){

return (11 * input + 3) % 50;}

 

void xor_alg(string input_str, long long int key){ \\что за xor? Это начало функции

vector<int> gamma;

vector<int> code;

for(int i=0; i<input_str.size(); i++){

for(int j=0; j<alphavit.size(); j++){

if(input_str[i] == alphavit[j]){

code.push_back(j); \\что это? ДОзапись элемента в конец вектора(массива)

break;

}}}

gamma.push_back(gen_num(key)); \\что это? ДОзапись элемента в конец вектора(массива)

for(int i=0; i<code.size(); i++){

gamma.push_back(gen_num(gamma.back())); \\что это? ДОзапись элемента в конец вектора(массива)

 

}

cout << endl;

for(int i=0; i<code.size(); i++){

int new_code = code[i] ^ gamma[i]; // ^- оперция XOR

cout << alphavit[new_code];

new_code = 0; //почему 0? Обнуление переменной new_code в конце каждой итерации

}} которая заканчивается тут

int main(){

string input_buffer;

long long int key_buffer = 0;

cout << "Enter a word: ";

cin >> input_buffer;

cout << "Enter a key: ";

cin >> key_buffer;

xor_alg(input_buffer, key_buffer);

return 0;

Сложе́ние по мо́дулю 2 (логи́ческая неравнозна́чность, исключа́ющее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент, жегалкинское сложение) — булева функция, а также логическая и битовая операция. В случае двух переменных результат выполнения операции является истинным тогда и только тогда, когда один из аргументов является истинным, а второй ложным. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных 1, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

 

 

Прототип функции toupper:

int toupper(int character);

Заголовочный файл

Название	Язык
ctype.h	С
cctype	С++

Описание

Функция toupper выполняет преобразование строчных букв в прописные. То есть, преобразует свой параметр в прописной эквивалент, если символ строчный. Если, передаваемый символ итак заглавный, то преобразование не выполняется и значение остаётся неизменным.

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

В С++ локализованная версия функции toupper определена в заголовочном файле <locale>.

Параметры:

• сharacter
  Строчная буква, которую необходимо преобразовать в заглавную, типа int, или EOF.

Возвращаемое значение

Прописной эквивалент символа, если такое значение существует, или — символ без изменений, в противном случае. Возвращаемое значение имеет тип данных int, оно может быть неявно преобразовано в char.

 

Прототип функции tolower:

int tolower (int c);

Заголовочный файл

Название	Язык
ctype.h	С
cctype	С++

Описание

Функция tolower выполняет преобразование прописных букв в строчные. То есть, преобразует свой параметр в строчный эквивалент, если символ с заглавной буквы. Если, передаваемый символ итак строчный, то преобразование не выполняется и значение остаётся неизменным.

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

В С++ локализованная версия функции tolower определена в заголовочном файле <locale>.

Параметры:

• сharacter
  Заглавная буква, которую необходимо преобразовать в строчную, типа int, или EOF.

Возвращаемое значение

Строчный эквивалент символа, если такое значение существует, или — символ без изменений, в противном случае. Возвращаемое значение имеет тип данных int, оно может быть неявно преобразовано в char.