Расчет показателей и построение основных элементов защищенных вычислительных сетей. Разработка программной реализации криптографических алгоритмов

Размещено на http://www.allbest.ru/

Курсовое проектирование по дисциплине «Компьютерная безопасность»

Тема: «Расчет показателей и построение основных элементов защищенных вычислительных сетей. Разработка программной реализации криптографических алгоритмов»

ОГЛАВЛЕНИЕ

1. Постановка задачи на курсовое проектирование

2. Описание компонентов сети конфиденциальной связи

2.1 Система распределения ключей на основе линейных преобразований (основная)

2.2 Система распределения ключей на основе алгоритма Диффи и Хелмана (резервная)

2.3 IDEA в режиме обратной связи по выходу

2.3.1 Обзор IDEA

2.3.2 Скорость IDEA

2.3.4 Криптоанализ IDEA

2.3.5Выводы по алгоритму

3. Описание разработанных программ

4. Криптостойкость алгоритма распределения ключей

Заключение

Литература

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Приложение 5

1. Постановка задачи на курсовое проектирование

В соответствии с исходными данными необходимо разработать систему засекреченной связи на основе использования симметричного блочного алгоритма IDEA с OFB при этом обеспечить распределение основных сеансовых ключей на основе линейных преобразований, а распределение резервных - с применением алгоритма Диффи и Хелмана.

Исходные данные (вариант №16):

IDEA в режиме обратной связи по выходу OFB (Output Feed Back):

Число выдерживаемых компрометаций - 5;

Простое число Р = 0xCE2AF780C0F289AE51EAC188FA20BCD3 (60);

Количество пользователей конфиденциальной сети -50000;

2. Описание компонентов сети конфиденциальной связи

2.1 Система распределения ключей на основе линейных преобразований (основная)

1. ЦРК генерирует и рассылает пользователям их открытые ключи:

Р_i = (Р_{i 1}, Р_{i 2},….,Р_{i L}), где i=1,2,…,V (количество пользователей);

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

- выбирается случайное число а (например 23);

- вектор адресов рассчитывается следующим образом:

Р_i = (aⁱ, a^i*2 ,…., a^i*L),

где i=1,2,…,V , а L - количество компрометаций;

- размер Рⁱ_j составляет 16 бит (максимальное значение 65535), что определяет количество пользователей (в задании 50000).

2. ЦРК генерирует L*L симметричную случайную матрицу

Т=(m*n),

где элементы матрицы t_mn выбираются равновероятными и взаимонезависимыми, и имеют размерность 128 бит равную длине ключа.

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

S_i = T*P_i^T;

4. Формирование парного ключа между i и j пользователем происходит следующим образом:

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

К_ij = S_i*P_j^T;

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

К_ji = S_j*P_i^T;

В виду симметричности матрицы Т ключи К_ij и K_ji будут равными. Далее ключ поступает в ключевое устройство блока шифрации алгоритма IDEA.

2.2 Система распределения ключей на основе алгоритма Диффи и Хелмана (резервная)

1. Пользователи сети заранее уславливаются о модуле Р (большом простом числе 128 бит) и примитивном элементе gZ_p (64 бит).

2. Для установления связи между i и j пользователем они заранее выбирают собственные секретные ключи X и Y (128 бит).

3. Далее пользователь i вычисляет открытый ключ:

К_i = g^X(mod P),

а пользователь j - открытый ключ:

К_j = g^Y(mod P).

4. Обменявшись открытыми ключами, пользователи вычисляют общий секретный ключ:

пользователь i: К_ij = (g^X)^Y(mod P);

пользователь j: К_ji = (g^Y)^X(mod P);

Очевидно, ключи К_ij и K_ji будут равными. Далее ключ поступает в ключевое устройство блока шифрации алгоритма IDEA.

2.3 IDEA в режиме обратной связи по выходу OFB

сеть ключ программа шифрование

Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифрования). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального криптоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования). В 1992 году название IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных).

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

2.3.1 Обзор IDEA

IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и дешифрирования используется один и тот же алгоритм. Как и другие блочные шифры IDEA использует и запутывание, и рассеяние. Философия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп".

Смешиваются три алгебраические группы, и все они могут быть легко реализованы как аппаратно, так и программно:

-- XOR

-- Сложение по модулю 2¹⁶

Размещено на http://www.allbest.ru/

-- Умножение по модулю 2¹⁶ + 1. (Это операцию можно рассматривать как S-блок IDEA.)

Все эти операции работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.

В курсовой работе рассматривается работа алгоритма в режиме обратной связи по выходу (OFB).

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

Положим M = M1, M2, ..., Mn. Для всех i = 1... n Сi = Mi Рi, где Рi - старшие k битов операции IDEA (C_i-1). Обновление сдвигового регистра осуществляется путем отбрасывания старших k битов и дописывания справа Pi.

Все три операции несовместимы в том смысле, что:

* никакая пара из этих трех операций не удовлетворяет ассоциативному закону, например а + (b с) (а + b) с;

* никакая пара из этих трех операций не удовлетворяет дистрибутивному закону, например а + (bс) (а + b) (а + с).

Комбинирование этих трех операций обеспечивает комплексное преобразование входа, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".

Общая схема алгоритма IDEA приведена в ПРИЛОЖЕНИИ 1. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле имеет место следующая последовательность операций:

(1) - умножение субблока X1 и первого подключа.

(2) + - сложение субблока X2 и второго подключа.

(3) + - сложение субблока Х3 и третьего подключа.

(4) - умножение субблока Х4 и четвертого подключа.

(5) - сложение результатов шагов (1) и (3).

(6) - сложение результатов шагов (2) и (4).

(7) - умножение результата шага (5) и пятого подключа.

(8) + - сложение результатов шагов (6) и (7).

(9) - умножение результата шага (8) с шестым подключом.

(10) + - сложение результатов шагов (7) и (9).

(11) - сложение результатов шагов (1) и (9).

(12) - сложение результатов шагов (3) и (9).

(13) - сложение результатов шагов (2) и (10).

(14) - сложение результатов шагов (4) и (10).

Выходом цикла являются четыре субблока, которые получают как результаты выполнения шагов (11), (12), (13) и (14). В завершение цикла переставляют местами два внутренних субблока (за исключением последнего цикла), и в результате формируется вход для следующего цикла.

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

(1) - умножение субблока X1 и первого подключа.

(2) + - сложение субблока X2 и второго подключа.

(3) + - сложение субблока Х3 и третьего подключа.

(4) - умножение субблока Х4 и четвертого подключа.

Наконец, эти результирующие четыре субблока Y1...Y4 вновь объединяют для получения блока шифртекста.

Алгоритм использует 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делят на восемь 16-битовых подключей. Это - первые восемь подключей для алгоритма (шесть подключей - для первого цикла и первые два подключа - для второго цикла). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые четыре из них используют во втором цикле; последние четыре - в третьем цикле. Ключ снова циклически сдвигается влево еще на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.

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

Таблица 1 Подключи шифрования алгоритма IDEA

Цикл	Подключи шифрования
1	Z11 Z21 Z31 Z41 Z51 Z61
2	Z12 Z22 Z32 Z42 Z52 Z62
3	Z13 Z23 Z33 Z43 Z53 Z63
4	Z14 Z24 Z34 Z44 Z54 Z64
5	Z15 Z25 Z35 Z45 Z55 Z65
6	Z16 Z26 Z36 Z46 Z56 Z66
7	Z17 Z27 Z37 Z47 Z57 Z67
8	Z18 Z28 Z38 Z48 Z58 Z68
Преобразование выхода	Z19 Z29 Z39 Z49

2.3.2 Скорость IDEA

Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2400 Кбит/с.

Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц. Другая СБИС, разработанная ETH Zurich и состоящая из of 251000 транзисторов на кристалле площадью 107.8 мм 2 , шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте 25 МГц.

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

2.3.3 Криптоанализ IDEA

Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2¹²⁸ (10³⁸) шифрований. Если создать микросхему, которая может проверять миллиард ключей в секунду, объединить миллиард таких микросхем, то потребуется 10¹³ лет для решения проблемы - это больше, чем возраст вселенной. 10²⁴ таких микросхем могут найти ключ за день, но во вселенной не найдется столько атомов кремния, чтобы построить машину.

Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу. Они определили понятие марковского шифра и продемонстрировали, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно. Криптоаналитик Лай (Lai) утверждал (он привел подтверждение, но не доказательство), что IDEA устойчив к дифференциальному криптоанализу уже после 4 из 8 этапов. Согласно Бихаму, его попытка вскрыть IDEA с помощью криптоанализа со связанными ключами также не увенчалась успехом.

Вилли Майер (Willi Meier) исследовал три алгебраических операции IDEA и показал, что, хотя они несовместимы, есть случаи, когда эти операции можно упростить так, чтобы в некоторой степени облегчить. Его вскрытие 2-этапного IDEA оказалось эффективнее вскрытия грубой силой (2⁴² операций), но для IDEA с 3 и более этапами эффективность этого вскрытия была ниже вскрытия грубой силой. Безопасность полного 8-этапного IDEA осталась непоколебимой.

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

0000,0000,0x00,0000,0000,000x,xxxx,x000

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

В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2⁹⁶ . Опасность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом 0x0dae.

IDEA может работать в любом из режимов работы блочного шифра, описанных в главе 9. Против двойных реализаций IDEA может быть предпринято то же вскрытие "встреча посередине", что и против DES. Однако, так как ключ IDEA более чем в два раза длиннее ключа DES, это вскрытие непрактично. Объем нужной для такого вскрытия памяти составит 64*2¹²⁸ битов, или 10³⁹ байтов.

Можно реализовать IDEA с независимыми подключами, особенно если средства распределения ключей позволяют работать с длинными ключами. Для IDEA нужно всего 52 16-битовых ключа, общей длиной 832 битов. Этот вариант определенно безопасней, но никто не сможет сказать насколько.

В наивной модификации может быть увеличен вдвое размер блока. Алгоритм также прекрасно работал бы с 32-битовыми подблоками вместо 16-битовых и с 256-битовым ключом. Шифрование выполнялось бы быстрее, и безопасность возросла бы в 2³² раза. Или нет? Теория, на которой основан алгоритм, опирается на то, что 2¹⁶ +1 является простым числом. А 2³² + 1 простым числом не является. Может быть алгоритм и можно изменить так, чтобы он работал, но его безопасность будет совсем иной. Лай говорит, что заставить работать такой алгоритм будет нелегко.

Хотя IDEA кажется намного безопаснее DES, не всегда можно легко заменить один алгоритм другим в существующем приложении. Если ваша база данных и шаблоны сообщений могут работать с 64-битовым ключом, реализация 128-битового ключа IDEA может быть возможной. Для таких приложений можно создать 128-битовый ключ, объединив 64-битовый ключ сам с собой. Но эта модификация заметно ослабляет IDEA.

Если больше волнует скорость работы, а не безопасность, можно вариант IDEA с меньшим числом этапов. Сегодня лучшее вскрытие IDEA быстрее вскрытия грубой силой только для 2.5 и менее этапов, 4-этапный IDEA будет в два раза быстрее и, насколько мне известно, его безопасность не уменьшится.

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

2.3.4Выводы по алгоритму

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

IDEA запатентован в Европе и Соединенных Штатах. Патент принадлежит Ascom-Tech AG. Для некоммерческого использования лицензирование не нужно.

3. ОПИСАНИЕ РАЗРАБОТАННЫХ ПРОГРАММ

Каждый абонент сети конфиденциальной связи имеет в своём распоряжении следующие программные продукты:

- генератор секретного ключа X и открытого Y для использования системы распределения ключей на основе алгоритма Диффи и Хелмана (описание и листинг представлены в приложении 2);

- программа шифрования (расшифрования) согласно IDEA с OFB (описание и листинг представлены в приложении 3). Причём k = 32 бита.

Программное обеспечение центра распределения ключей (Приложение 4) включает:

- генератор случайной матрицы размером L*L*128 бит;

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

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

Все приложения реализованы в среде алгоритмического программирования Turbo C++ v1.01, и из-за того, что используют инструкции только i8086 процессора имеют очень низкие требования к системе. Реализация приложений на аssembler'е позволит несколько увеличить скорость шифрования.

4. Криптостойкость алгоритма распределения ключей

При использовании метода линейных преобразований для формирования общего ключа (основной режим) выбор размера используемых матриц определялся исходя из заданного количества выдерживаемых компрометаций (L=5). Таким образом, симметричная матрица Т имеет размерность Т[6,6] и длину каждого элемента матрицы равную длине ключа шифрования (128 бит). Элементы матрицы генерировались равновероятно и взаимонезависимо.

Адреса абонентов являются векторами вида Р_i=(P₁ⁱ,P₂ⁱ, …,P_Lⁱ), где L = 6. Размер каждого элемента адреса равен 16 битам, что определяется максимальным количеством абонентов конфиденциальной сети (2¹⁶ > 50000). Адрес каждого пользователя рассчитывается так, чтобы элементы вектора были линейно-независимыми.

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

При использовании алгоритма Диффи и Хелмана для формирования сеансового ключа (резервный режим) использовались следующие данные:

- Р - 128 битовое простое число;

- g - генератор поля Z_p (64 бита, выбирался случайно с проверкой по теотеме Альберта);

- X - случайное число размерности 64 бита;

- K_ij - сеансовый ключ, имеющий длину 128 бит.

Криптостойкость данной схемы распределения основывается на трудности решения задачи дискретного логарифмирования. Для ключа 128 бит задача практически неразрешима. Таким образом, выбор значений N и g имеет существенное влияние на безопасность этой системы. Число (N-1)/2 также должно быть большим простым числом, а число g должно быть генератором большой подгруппы мультипликативной группы по модулю N.

Заключение

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

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

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

1. А.П. Баранов, Н.П. Борисенко и другие, Математические основы информационной безопасности. - Орёл, 1997г.

2. А.В. Домашев и другие, Программирование алгоритмов защиты информации. -М. «Нолидж», 2000г.

ПРИЛОЖЕНИЕ 1

Схема алгоритма IDEA (режим шифрования).

ПРИЛОЖЕНИЕ 2

Генератор секретного и открытого ключа.

#include “ext128.cpp”

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

void main (int argc, char **argv)

{

FILE *keyX;

FILE *_ey;

unsigned P[8] = {0xbcd3,0xfa20,0xc188,0x51ea,0x89ae,0xc0f2,0xf780,0xce2a};

unsigned a[8] = {0x89e,0xc55,0x8fb,0x5b42,0,0,0,0};

unsigned X[8] = {0,};

char dest1[9];

char dest2[9];

char *n1 = “u”, *ext1 = “.x”, *ext2 = “.y”;

strcpy(dest1, n1);

strcat(dest1, argv[1]);

strcat(dest1, ext1);

keyX = fopen ( dest1 , “wb”);

strcpy(dest2, n1);

strcat(dest2, argv[1]);

strcat(dest2, ext2);

_ey = fopen ( dest2 , “wb”);

randomize();

for (int i=0; i<7; i++) X[i] = rand()%0xffffU;

X[7] = rand()%0xce29U;

fwrite(&X, sizeof(unsigned), 8, keyX);

fclose(keyX);

unsigned temp1[18] = {0,};

Pow_N(a, X, P, temp1);

fwrite(&temp1, sizeof(unsigned), 8, _ey);

fclose(keyY);

}

Управление осуществляется из командной строки, в которой после имени файла указывается номер абонента: genx_y.exe 20. Где 20 - номер абонента.

Результатом работы будут файлы u20.x и u20.y.

ПРИЛОЖЕНИЕ 3

Программа шифрования по алгоритму IDEA с OFB.

#include “idea.cpp”

#include <conio.h>

#include <io.h>

#include <stdio.h>

#include <iostream.h>

int main (int argc, char **argv)

{

clrscr();

//------------------------data-----------------------

FILE *message;

FILE *sincfile;

FILE *rezfile;

FILE *keyfile;

unsigned key[8] = {0,};

unsigned WorkKey[52] = {0,};

unsigned sinc[4] = {0,};

//---------------------end of data-------------------

if ((message = fopen ( argv[1] , “rb”)) == NULL)

{

cout << “ input file “ << argv[1] << “ not open.”;

return 1;

}

if ((rezfile = fopen ( argv[2] , “wb”)) == NULL)

{

cout << “ file “ << argv[2] << “ not open.”;

return 1;

}

if ((keyfile = fopen ( argv[3] , “rb”)) == NULL)

{

cout << “ file “ << argv[4] << “ not open.”;

return 1;

}

if ((sincfile = fopen ( argv[4] , “rb”)) == NULL)

{

cout << “ file “ << argv[4] << “ not open.”;

return 1;

}

//---------------------------------------------------

fread(key ,sizeof(unsigned), 8, keyfile);

fclose(keyfile);

GenerateKey(key, WorkKey);

//---------------------------------------------------

fread(sinc ,sizeof(unsigned), 4, sincfile);

fclose(sincfile);

//---------------------------------------------------

long len=filelength(fileno(message));

unsigned temp[3]={0,};

do

{

if (len > 6)

{

fread(temp ,sizeof(unsigned), 3, message);

IDEA_OFB(temp, WorkKey, sinc, 3);

fwrite(&temp, sizeof(unsigned), 3, rezfile);

len -= 6;

}

else

{

memset(temp,0,3);

fread(temp ,sizeof(unsigned char), len, message);

int n = ((len%2)==1)?(len/2+1):len/2;

for (int i=0; i<n; i++) IDEA_OFB(temp, WorkKey, sinc, 1);

fwrite(&temp, sizeof(unsigned), n, rezfile);

len = -1;

}

cout << endl << len;

}while(len > 0);

//---------------------------------------------------

fclose(message);

fclose(rezfile);

//---------------------------------------------------

cout << endl << “© Bashmakov A.V. Orel,2001”;

return 0;

}

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

Например : idea_ofb.exe mao.bmp rez.txt u20.lin sin.sin.

Скорость шифрования данных достигает 100 кбайт в секунду.

ПРИЛОЖЕНИЕ 4

Программное обеспечение ЦРК.

Генератор случайной матрицы.

// generate matrix T[N][N][8];

#include "lin.cpp"

#include <stdio.h>

void main()

{

FILE *file_T;

unsigned T[N][N] = {0,};

file_T = fopen ( "matrix.lin" , "wb");

for (int i=0; i<8; i++)

{

GenerateT(T);

fwrite(&T, sizeof(unsigned), N*N, file_T);

}

fclose(file_T);

}

Результатом выполнения приложения является файл matrix.lin.

Генератор парного ключа.

#include “lin.cpp”

#include “ext128.cpp”

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <iostream.h>

//-------------------------------------------------------

int main (int argc, char **argv)

{

if (argc < 4)

{

cout << endl

<< “ crk.exe U1_number U2_number U1.x U2.y file.t”

<< endl;

return 1;

}

//====================initialization data=================

FILE *osnkey;

FILE *rezkey;

FILE *stat;

FILE *X_file;

FILE *Y_file;

FILE *T_file;

unsigned Num1 = atoi(argv[1]), ©;

unsigned Num2 = atoi(argv[2]);

char dest1[9];

char dest2[9];

char dest3[9];

char *n1 = “u”, *ext1 = “.lin”, *ext2 = “.d_h”;

strcpy(dest1, n1);

strcat(dest1, argv[1]);

strcat(dest1, ext1);

if ((osnkey = fopen ( dest1 , “wb”)) == NULL)

{

cout << “ KeyFile not open.”;

return 1;

}

strcpy(dest2, n1);

strcat(dest2, argv[1]);

strcat(dest2, ext2);

if ((rezkey = fopen ( dest2 , “wb”)) == NULL)

{

cout << “ KeyFile not open.”;

return 1;

}

if ((stat = fopen ( “stat.txt” , “wt”)) == NULL)

{

cout << “ stat.txt not open.”;

return 1;

}

if ((X_file = fopen ( argv[3] , “rb”)) == NULL)

{

cout << argv[2] << “ not open.”;

return 1;

}

if ((Y_file = fopen ( argv[4] , “rb”)) == NULL)

{

cout << argv[3] << “ not open.”;

return 1;

}

if ((T_file = fopen ( argv[5] , “rb”)) == NULL)

{

cout << argv[4] << “ not open.”;

return 1;

}

unsigned key1[8] = {0,};

unsigned key2[8] = {0,};

unsigned X[17] = {0,};

unsigned Y[17] = {0,};

//=====================================================

unsigned R1[N] = {0,};

unsigned R2[N] = {0,};

unsigned T[N][N] = {0,};

GenerateR(R1,Num1);

GenerateR(R2,Num2);

for (©=0; ©<8; ©++)

{

fread(T, sizeof(unsigned), N*N, T_file);

key1[©] = FormDubleKey(T,R1,R2);

}

fclose (T_file);

fwrite(&key1, sizeof(unsigned), 8, osnkey);

fclose (osnkey);

//=====================================================

// X - secret key

// Y - public key

unsigned P[17] = {0xbcd3,0xfa20,0xc188,0x51ea,0x89ae,0xc0f2,0xf780,0xce2a};

// unsigned a[8] = {0x89e,0xc55,0x8fb,0x5b42,0,0,0,0};

fread(X, sizeof(unsigned), 8, X_file);

fclose (X_file);

fread(Y, sizeof(unsigned), 8, Y_file);

fclose (Y_file);

Pow_N(Y,X,P,key2);

fwrite(&key2, sizeof(unsigned), 8, rezkey);

fclose (rezkey);

//=====================================================

int j;

fprintf(stat, «\t\tФайл статистики для ЦРК.\n»);

fprintf(stat, “\tПользователь 1: %d. \tадрес: “, Num1);

for ( j = 5; j >= 0; j--) fprintf(stat, “%.4X”, R1[j]);

fprintf(stat, “\n\tПользователь 2: %d. \tадрес: “, Num2);

for ( j = 5; j >= 0; j--) fprintf(stat, “%.4X”, R2[j]);

fprintf(stat, “\n\t1) Основной ключ:\n\t\t”);

for ( j = 7; j >= 0; j--) fprintf(stat, “%.4X”, key1[j]);

fprintf(stat, “\n\t2) Резервный ключ:\n\t\t”);

for ( j = 7; j >= 0; j--) fprintf(stat, “%.4X”, key2[j]);

fprintf(stat, “\n\n\t ©2001 A. Bashmakov”);

//=====================================================

return 0;

}

Управление осуществляется из командной строки):

crk.exe U1_number U2_number U1.x U2.y matrix.lin.

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

Результатом являются два файла с основным (*.lin) и резервным (*.d_h) ключами, а также файл-отчёта stat.txt.

Пример отчёта:

Файл статистики для ЦРК.

Пользователь 1: 10. адрес: 4F570112060A6AF33436B67A

Пользователь 2: 20. адрес: E827254578884F57060A3436

1) Основной ключ:

4FA0F597B4F49770365581D7ACB2F3BF

2) Резервный ключ:

5FA91077838BDEFB20DD14BAE77A8B19

(c)2001 A. Bashmakov

ПРИЛОЖЕНИЕ 5

Вспомогательные функции.

1. lin.cpp

//===================(c) Bashmakov A.V. Orel,2001===========

//= started 23.10 03.05.01 =

//= finished 21.14 24.05.01 =

//=====================================================

#include <stdlib.h>

//---------------------------------------------------------------------------

#define N 6

//---------------------------------------------------------------------------

void GenerateT (unsigned T[N][N]);

void GenerateR (unsigned R[N], unsigned);

unsigned FormDubleKey(unsigned T[N][N], unsigned R1[N], unsigned R2[N]);

unsigned long Pow_N (unsigned long, unsigned long, unsigned long);

//------------------------------------------------------------------------

void GenerateT(unsigned T[N][N])

{

unsigned temp = 0;

for (int i = 0; i < N; i++)

{

for (int j = temp; j < N ; j++)

{

if( i == j ) T[i][j] = rand()%0xffffU;

else T[i][j] = T[j][i] = rand()%0xffffU;

}

temp ++;

}

}

//-------------------------------------------------------------------------

void GenerateR(unsigned R[N], unsigned number)

{

for (int i=0; i<N; i++) R[i] = Pow_N(23, (number*(i+1)), 0xffffU);

}

//-------------------------------------------------------------------------

unsigned FormDubleKey (unsigned T[N][N], unsigned R1[N], unsigned R2[N])

{

unsigned long temp1 = 0U;

unsigned long temp2 = 0U;

unsigned S[N] = {0U,};

for (int i=0; i<N; i++)

{

temp2 = 0;

for (int j=0; j<N; j++)

{

temp1 = ((unsigned long)T[i][j] * R1[j]);

temp2 = ((temp1%0xffffU) + temp2)%0xffffU;

}

S[i] = (unsigned)temp2;

}

temp2 = 0;

for (i=0; i<N; i++)

{

temp1 = (unsigned long)S[i] * R2[i];

temp2 = ((temp1%0xffffU) + temp2)%0xffffU ;

}

return temp2;

}

//-------------------------------------------------------------------------

unsigned long Pow_N(unsigned long a, unsigned long k, unsigned long n)

{

unsigned long A,B,K,q,r;

K=k;

B=1;

A=a;

s2: q=K/2;

r=K-2*q;

K=q;

if (r==0) goto s5;

B=(A*B)%n;

if (K==0) return B;

s5: A=(A*A)%n;

goto s2;

}

2. ext128.cpp

//====================128 bits ariphmetics==================

//=====================23.05.01====20.42==================

//===================(c) 2001 by A.Bashmakov==============

union Data

{

unsigned a[2];

unsigned long b;

}point;

//----------------------------------------------------------------

void Mult16 (unsigned *, unsigned *, unsigned *);

void Div16 (unsigned *, unsigned *, unsigned *, unsigned *);

void Sum16 (unsigned *, unsigned *, unsigned *);

void Razn16 (unsigned *, unsigned *, unsigned *);

void Pow_N (unsigned *, unsigned *, unsigned *, unsigned *);

void ModN (unsigned *, unsigned *);

//----------------------------------------------------------------

void Mult16(unsigned a[9], unsigned b[9], unsigned rez[18])

{ // a * b = rez; a & b max 128 bit, rez - 256 bit

unsigned st16 = 0U;

unsigned ml16 = 0U;

unsigned long temp = 0L;

for(int j=0; j<16; j++) rez[j] = 0U;

a[8] = 0;

b[8] = 0;

for(j=0; j<9; j++)

{

for(int i=0; i<9; i++)

{

if(i == 0)

{

rez[9 + j] = st16;

st16 = 0;

}

point.b = (unsigned long)a[i] * (unsigned long)b[j];

ml16 = point.a[0];

temp = (unsigned long)rez[i+j] + (unsigned long)ml16 + st16;

rez[i+j] += ml16 + st16;

st16 = point.a[1] + (unsigned)(temp>>16);

if((j == 8)&&(i == 8)) rez[i+j+1] = st16;

}

}

}

//----------------------------------------------------------------

void Sum16(unsigned a[16], unsigned b[16], unsigned rez[16])

{ // a + b = rez;

unsigned perepS = 0;

unsigned j = 0;

for(int i=0; i<8; i++)

{

point.b = (unsigned long)b[i] + (unsigned long)a[i] + perepS;

rez[j] = point.a[0];

perepS = point.a[1];

j++;

}

rez[j] = perepS;

}

//----------------------------------------------------------------

void ModN(unsigned a[16], unsigned m[8])

{ // a(mod m);

int i = 16;

do {i--;} while (a[i]==0);

int j = 8;

do {j--;} while (m[j]==0);

unsigned *temp1 = new unsigned [16];

unsigned *temp2 = new unsigned [16];

if ((i>j)||((i==j)&&(a[i]>m[j])))

{

do

{

for (int g=0; g<16; g++) temp1[g] = 0;

if (a[i] >= m[j])

{

point.b = (a[i] / m[j]);

temp1[i - j] = (point.a[0] == 0)?1:point.a[0];

}

else

{

i--;

point.a[0] = a[i];

point.a[1] = a[i+1];

point.b = (point.b / m[j]) - 1;

temp1[i - j] = (point.a[0] == 0)?1:point.a[0];

temp1[i - j + 1]= point.a[1];

}

Mult16(m, temp1, temp2);

Razn16(a, temp2, temp1);

for (g=0; g<16; g++) a[g] = temp1[g];

i = 16;

do

{ i--;

if(i == -1) {i=0; break;}

}while (a[i]==0);

}while(i!=j);

for (int g=8; g<16; g++) temp2[g] = 0;

for ( g=0; g<8 ; g++) temp2[g] = m[g];

while (a[i]>=m[j])

{

Razn16(a, temp2, temp1);

for (g=0; g<16; g++) a[g] = temp1[g];

};

};

delete temp1;

delete temp2;

}

//----------------------------------------------------------------

void Razn16(unsigned a[16], unsigned b[16], unsigned rez[16])

{ // a - b = rez;

for(int i=0; i<16; i++) rez[i] = 0;

unsigned *temp = new unsigned [17];

for(i=0; i<16; i++) temp[i] = a[i];

temp[17] = 0;

unsigned p = 17;

do {p--;} while (a[p]==0);

for(i=0; i<=p; i++)

{

point.a[0] = temp[i];

point.a[1] = temp[i+1];

point.b -= b[i];

rez[i] = point.a[0];

temp[i+1] = point.a[1];

}

rez[i] = temp[i];

delete temp;

}

//----------------------------------------------------------------

void Pow_N(unsigned a[8], unsigned b[8], unsigned mod[8], unsigned rez[8])

{

unsigned *temp = new unsigned [9];

unsigned *temp1 = new unsigned [16];

int f;

for (int i = 0; i<8; i++) temp[i] = a[i];

temp[8] = 0;

for ( i = 0; i<16; i++) temp1[i] = 0;

unsigned p = 8;

do {p--;} while (b[p]==0);

unsigned g = 16;

do {g--;} while ( ((b[p] >> g)&0x1) == 0);

g--;

for (i = g; i>=0; i--)

{

Mult16(temp, temp, temp1);

ModN (temp1, mod);

for (f = 8; f>=0; f--) temp[f] = temp1[f];

if (((b[p] >> i)&0x1) == 1)

{

Mult16(temp, a, temp1);

ModN (temp1, mod);

for (f = 8; f>=0; f--) temp[f] = temp1[f];

}

}

for (i=p-1; i>=0; i--)

{

for (int j=15; j>=0; j--)

{

Mult16(temp, temp, temp1);

ModN (temp1, mod);

for (f = 8; f>=0; f--) temp[f] = temp1[f];

if (((b[i] >> j)&0x1) == 1)

{

Mult16(a, temp, temp1);

ModN (temp1, mod);

for (f = 8; f>=0; f--) temp[f] = temp1[f];

}

}

}

for (i=7; i>=0; i--) rez[i] = temp[i];

delete temp;

delete temp1;

}

//----------------------------------------------------------------

void Div16(unsigned a[8], unsigned b[8], unsigned rez[8], unsigned ost[8])

{

int i = 8;

do {i--;} while (a[i]==0);

int j = 8;

do {j--;} while (b[j]==0);

unsigned RaznPoz, del;

unsigned ostT [16] = {0,};

for (int g=0; g<8; g++) ostT[g] = a[g];

unsigned *temp1 = new unsigned [17];

unsigned *temp2 = new unsigned [17];

if ((i>j)||((i==j)&&(ostT[i]>b[j])))

{

do

{

for (int g=0; g<17; g++) temp1[g] = 0;

if (ostT[i] > b[j]) del = (ost[i] / b[j]);

else

{

i--;

point.a[0] = ostT[i];

point.a[1] = ostT[i+1];

del = point.b / b[j] - 1;

del = (del == 0)?1:del;

}

RaznPoz = i - j;

temp1[RaznPoz] = del;

rez [RaznPoz] = (rez[RaznPoz]==0)?del:(rez[RaznPoz] + del);

Mult16(b, temp1, temp2);

Razn16(ostT, temp2, temp1);

for(int u=15;u>=0;u--) ostT[u] = temp1[u];

i = 8;

do

{

i--;

if (i==-1) {i = 0; break;}

}while (ostT[i]==0);

}while(i>j);

int pointer = 0;

for (g = 0; g < 8; g++) temp2[g] = b[g];

for (g = 8; g < 16; g++) temp2[g] = 0;

while (ostT[i]>=b[j])

{

Razn16(ostT, temp2, temp1);

for(g=7;g>=0;g--) ostT[g] = temp1[g];

pointer++;

};

rez[0] += pointer;

};

delete temp1;

delete temp2;

}

3. idea.cpp

//==================idea.cpp============================

//-------International Data Encription Algorithm--------

typedef unsigned long type32;

typedef unsigned type16;

typedef unsigned char type8;

//------------------------------------------------------

void EncriptionStep (unsigned *, unsigned *);

void IDEA (unsigned *, unsigned *);

unsigned SdvigMas1_4 (unsigned *);

int GenerateKey (type16 *, type16 *);

int sdvig25 (type16 *);

void IDEA_OFB (unsigned *, unsigned *, unsigned *, int);

unsigned mul (unsigned, unsigned);

//------------------------------------------------------

void EncriptionStep(unsigned *key, unsigned *mes)

{

unsigned long a,b,c,d,e,f,g,h;

a = mul(mes[0], key[0]); // 1

b = ((unsigned long)mes[1] + key[1])%65536; // 2

c = ((unsigned long)mes[2] + key[2])%65536; // 3

d = mul(mes[3], key[3]); // 4

e = a ^ c; // 5

f = b ^ d; // 6

e = mul(e, key[4]); // 7

f = ((unsigned long)f + e)%65336; // 8

f = mul(f, key[5]); // 9

e = ((unsigned long)e + f)%65336; // 10

mes[0] = a ^ f; // 11

mes[1] = c ^ f; // 12

mes[2] = b ^ e; // 13

mes[3] = d ^ e; // 14

}

void IDEA(unsigned *key, unsigned *mes)

{

EncriptionStep(key,mes);

EncriptionStep(key + 6 ,mes);

EncriptionStep(key + 12,mes);

EncriptionStep(key + 18,mes);

EncriptionStep(key + 24,mes);

EncriptionStep(key + 30,mes);

EncriptionStep(key + 36,mes);

EncriptionStep(key + 42,mes);

mes[0] = ((unsigned long)mes[0] * key[48])%65337L;

mes[1] = ((unsigned long)mes[1] + key[49])%65336;

mes[2] = ((unsigned long)mes[2] + key[50])%65336;

mes[3] = ((unsigned long)mes[3] * key[51])%65337L;

}

unsigned SdvigMas1_4(unsigned *mas)

{

unsigned temp = mas[0];

mas[0] = mas[1];

mas[1] = mas[2];

mas[2] = mas[3];

mas[3] = temp;

return (temp);

}

int GenerateKey(type16 *A, type16 *B)

{

for (int i=0;i<8;i++) B[i] = A[i];

sdvig25(A);

for (i=0;i<8;i++) B[i+8] = A[i];

sdvig25(A);

for (i=0;i<8;i++) B[i+16] = A[i];

sdvig25(A);

for (i=0;i<8;i++) B[i+24] = A[i];

sdvig25(A);

for (i=0;i<8;i++) B[i+32] = A[i];

sdvig25(A);

for (i=0;i<8;i++) B[i+40] = A[i];

sdvig25(A);

for (i=0;i<4;i++) B[i+48] = A[i];

return 1;

}

int sdvig25(type16 *A)

{

type32 *massiv = new type32 [4];

type32 *out = new type32 [4];

type32 *bit7 = new type32 [4];

type32 *bit25 = new type32 [4];

*massiv = *(type32*)A;

*(massiv + 1) = *(type32*)(A + 2);

*(massiv + 2) = *(type32*)(A + 4);

*(massiv + 3) = *(type32*)(A + 6);

bit7 [0] = ((massiv[0]&0x7f)<<25)&0xfe000000;

bit25[0] = ((massiv[0]&0xffffff80)>>7)&0x1ffffff;

bit7 [1] = ((massiv[1]&0x7f)<<25)&0xfe000000;

bit25[1] = ((massiv[1]&0xffffff80)>>7)&0x1ffffff;

bit7 [2] = ((massiv[2]&0x7f)<<25)&0xfe000000;

bit25[2] = ((massiv[2]&0xffffff80)>>7)&0x1ffffff;

bit7 [3] = ((massiv[3]&0x7f)<<25)&0xfe000000;

bit25[3] = ((massiv[3]&0xffffff80)>>7)&0x1ffffff;

out[0] = bit7[0]|bit25[3];

out[1] = bit7[1]|bit25[0];

out[2] = bit7[2]|bit25[1];

out[3] = bit7[3]|bit25[2];

*(type32*)A = out[0];

*(type32*)(A + 2) = out[1];

*(type32*)(A + 4) = out[2];

*(type32*)(A + 6) = out[3];

delete massiv;

delete bit7;

delete bit25;

delete out;

return 1;

}

void IDEA_OFB(unsigned *mes,unsigned *key,unsigned *NZ, int n)

{ // mes - n * 16bit

IDEA(key,NZ);

for (int i = 0; i<n; i++) mes[i] ^= NZ[3-i];

SdvigMas1_4(NZ);

}

unsigned mul(unsigned a, unsigned b)

{

unsigned long p;

if (a)

{ if (b)

{ p = (unsigned long)a * b;

b = p&0xffffU;

a = p>>16;

return b - a + (b < a);

}

else return 1-a;

}

else return 1-b;

}

Размещено на Allbest.ru