Главная
страница 1



Утверждаю

Ректор университета

______________А.В. Лагерев

«_____»_____________2007г.


Методы и средства защиты информации


СИММЕТРИЧНЫЕ КРИПТОАЛГОРИТМЫ
Методические указания
к выполнению лабораторной работы №4

для студентов очной формы обучения

специальности 220300 – "Системы автоматизированного проектирования"


Брянск 2007

УДК 004.43


Методы и средства защиты информации. Симметричные криптоалгоритмы: методические указания к выполнению лабораторной работы № 4 для студентов очной формы обучения специальности 220300 – "Системы автоматизированного проектирования".– Брянск: БГТУ, 2007. - 16 с.

Разработал: С.М. Рощин, доц., канд. техн. наук

А.Е. Фролов, аспирант

Рекомендовано кафедрой «Компьютерные технологии и системы» БГТУ (протокол № 1 от 6.09.06)


Темплан 2006г., п. 164




Подписано в печать Формат 60х84 1/16. Бумага офсетная. Офсетная печать. Усл. печ. л. 0,63 Уч. – изд. л. 0,63 Тираж 50 экз. Заказ . Бесплатно.

Издательство брянского государственного технического университета, 241035, Брянск, бульвар 50-летия Октября, 7, БГТУ. 54-90-49

Лаборатория оперативной полиграфии БГТУ, ул. Харьковская, 9
1. ЦЕЛЬ РАБОТЫ


  1. Познакомится с основными алгоритмами шифрования.

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

  3. Закрепить навыки программирования


2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Перестановки - Также метод криптографического преобразования. Используется, как правило, в сочетании с другими методами.

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

2. Потоковые шифры (скремблеры)
Потоковые шифры представляют собой разновидность гаммирования и преобразуют открытый текст в шифрованный по­следовательно по 1 биту. Генератор ключевой последователь­ности, иногда называемый генератором бегущего ключа, выда­ет последовательность бит к1, к2, ..., кi, ... Эта ключевая последовательность складывается по модулю 2 (операция XOR) с последовательно­стью бит исходного текста р1, р2, ..., pi, ... для получения шиф­рованного текста:

На приемной стороне шифрованный текст складывается по мо­дулю 2 с идентичной ключевой последовательностью для полу­чения исходного текста:

Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа по следующему алгоритму. Из текущего набора бит выбираются значения определенных разрядов и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение ("0" или "1") помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом (см. рис.1).




Рис.1.

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

Рассмотрим пример кодирования информационной последовательности 0101112 скремблером 1012 с начальным ключом 1102.

скремблер код.бит инф.бит рез-т

1 1 0 ----- 0 XOR 0 = 0

\ \


1 1 1 ----- 1 XOR 1 = 0

\ \


0 1 1 ----- 1 XOR 0 = 1

\ \


1 0 1 ----- 1 XOR 1 = 0

\ \


и т.д.

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

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

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

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

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


3. Блочные шифры
Блочные шифры представляют собой семейство обратимых преобразований блоков (частей фиксированной длины) исходного текста. Фактически блочный шифр – это система подстановки на алфавите блоков. В настоящее время блочные шифры наиболее распространены на практике. Российский и американский стандарт шифрования относятся именно к этому классу шифров.

Американский стандарт криптографического закрытия данных DES (Data Encryption Standard), принятый в 1978г., является типичным представителем блочных шифров. Однако на текущий момент этот стандарт полностью неприемлем для использования по двум причинам : 1) основной – длина его ключа составляет 56 бит, что очень мало на современном этапе развития ЭВМ, 2) второстепенной – при разработке алгоритм был ориентирован на аппаратную реализацию, то есть содержал операции, выполняемые программно (на микропроцессорах) за неприемлимо большое время (например, такие как перестановка бит внутри машинного слова по определенной схеме).


3.1. Международный алгоритм шифрования данных (IDEA)
Международный алгоритм шифрования данных (IDEA — International Data Encryption Algorithm) представляет собой симметричный блочный шифр. Его разработали сотрудники Швейцарского федерального института технологий (Swiss Federal Institute of Technology).

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

IDEA представляет собой блочный шифр, использующий 128-битовый ключ для шифрования данных блоками по 64 бита. Для сравнения DES тоже работает с 64-битовыми блоками, но шифрует их с помощью 56-битового ключа.
3.2. Стандарт AES. Алгоритм Rijndael
В конце 1996 г. Национальным институтом стандартов США (NIST) был объявлен конкурс на создание нового общенацио­нального стандарта шифрования, который должен прийти на замену DES. Разрабатываемому стандарту было присвоено ра­бочее наименование AES (Advanced Encryption Standard). Отбор проходил в два этапа, после первого среди претендентов оста­лось 15 кандидатов, после второго - 5.

2 октября 2000 года было принято окончательное решение. В качестве предлагаемого стандарта был выбран алгоритм Rijndael (произносится "Рейн-дал"). Этот алгоритм был разрабо­тан Винсентом Райманом (Vincent Rijman) и Йоан Дамен (Joan Daemen) и представляет собой алгоритм, не использующий сети Фейштеля.

При описании алгоритма используется поле Галуа GF(28), построенное как расширение поля GF(2) по корням многочлена m(x) = x8 + x4 + х3 + х + 1. Данный многочлен выбран из соображений эффективности представления элемен­тов поля. Элементарные операции, использующиеся в алгорит­ме, выполняются в указанном поле.

Алгоритм Rijndael представляет собой блочный шифр с пе­ременной длиной блока и переменной длиной ключа Длины блока и ключа могут быть выбраны независимо равными 128, 192 или 256 бит. Шифр является последовательностью итера­ций, выполняемых над некоторой промежуточной структурой, называемой состоянием. (Эта терминология заимствована из теории конечных автоматов.) Состояние может быть представ­лено в виде прямоугольного массива байтов. В массиве 4 стро­ки, а число столбцов, обозначаемое как Nb, равно длине блока, деленной на 32. Ключ шифрования аналогичным образом пред­ставляется в виде прямоугольного байтового массива с 4 стро­ками. Количество столбцов, обозначаемое Nk, равно длине ключа, деленной на 32. Входные и выходные значения алгорит­ма представляются в виде одномерных байтовых массивов со­ответствующей длины. Состояние и ключевой массив заполня­ются из этих массивов вначале по столбцам, а затем по строкам. Количество итераций обозначается Nr зависит от Nb и Nk в со­ответствии со следующей таблицей:



Nr

Nb = 4

Nb = 6

Nb = 8

Nk = 4

10

12

14

Nk = 6

12

12

14

Nk = 8

14

14

14

Итерационное преобразование состоит из четырех различ­ных преобразований. На С-подобном псевдокоде это выглядит так:
Round (State, RoundKey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State, RoundKey);

}
Последняя итерация несколько отличается от всех остальных:


FinalRound (State, RoundKey) {
ByteSub(State);
ShiftRow(State);
AddRoundKey(State, RoundKey);

}
Отдельные преобразования описываются ниже.



ByteSub

Это блок нелинейной обратимой байтовой замены (S-бокс), состоящий из двух операций:



  • Каждый байт заменяется на мультипликативный обратный к нему в поле GF(28). Байт со значением '00'h отобража­ется в себя.

  • Над каждым байтом выполняется аффинное преобразование в поле GF(2), задаваемое следующим уравнением:



Это аффинное преобразование может быть описано в полино­миальном виде как b(х) - (х7 + х6 + х2 + х) + а(х)( х7 + х6 + х5 + х4 +1) mod (x8 +1). Полином, на который производится умножение, выбран взаимно простым с модулем, так что умножение являет­ся обратимым.

Обратным к ByteSub будет преобразование, состоящее из обратного аффинного преобразования и взятия мультиплика­тивного обратного в GF(28).



ShiftRow

Это преобразование является циклическим сдвигом влево строк массива состояния на различную величину. Строка 0 не сдвигается, строка 1 сдвигается на С1 позиций, строка 2 - на С2 и строка 3 - на СЗ позиций. Величины сдвига приведены в таб­лице:



Nb

С1

С2

СЗ

4

1

2

3

6

1

2

3

8

1

3

4

Обратным преобразованием будет циклический сдвиг строк массива вправо на то же количество позиций.

MixColumn

В этом преобразовании столбцы массива состояния рассмат­риваются как полиномы над полем GF(28). Преобразование за­ключается в умножении столбца по модулю х4 +1 на фиксиро­ванный полином



Этот полином является взаимно простым с х4 +1 и поэтому ум­ножение обратимо. В матричной форме данное преобразование можно представить как

Обратное преобразование представляет собой умножение на полином, мультипликативно обратный к с(х) по модулю х4 +1:


AddRoundKey

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



Алгоритм обработки ключа.

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



  • Общее число бит ключей итерации равно длине блока, ум­ноженной на количество итераций плюс один. (Например, для блока 128 бит и 10 итераций потребуется 1408 бит ключей итерации).

  • Ключ шифрования расширяется до расширенного ключа.

  • Ключи итерации берутся из расширенного ключа следую­щим образом: первый ключ итерации состоит из первых Nb слов, второй - из следующих Nb слов и т.д.

Алгоритм расширения ключа

Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначается как W[Nb * (Nr + 1)]. Функция расширения ключа зависит от Nk. Существует две версии - для Nk < 6 и для Nk > 6. Для Nk < 6:


KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+l)]) {
for(i = 0;iW[i] = (Key[4*i],Key[4*i+l],Key[4*i+2],Key[4*i+3]);

for(i = Nk; i < Nb * (Nr + 1); i++) {
temp = W[i- 1];
if(i%Nk == 0)
temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk]; W[i] = W[i - Nk] ^ temp;

}

}


Здесь SubByte(W) - функция, возвращающая слово, в кото­ром каждый байт является результатом применения блока заме­ны шифра к байту, находящемуся на соответствующей позиции во входном слове. Функция RotByte(W) - циклический сдвиг байтов в слове, так что входное слово (а, b, с, d) преобразуется в слово (b, с, d, a).

Для Nk > 6 алгоритм выглядит так:


KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+l)]) {

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

W[i] = (key[4*i],key[4*i+l],key[4*i+2],key[4*i+3]);

for(i = Nk; i < Nb * (Nr + 1); i++) {

temp = W[i - 1];

if(i%Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];

else if(i%Nk == 4)

temp = SubByte(temp); W[i] = W[i - Nk] ^ temp;

}

}


Константы итерации Rcon не зависят от Nk и определяются как

Rcon[i] = (RC[i], '00', '00', '00'),

где RC[i] являются представлениями элементов поля GF(28) со значениями х j-1 , т.е. RC[1] = 1 (т.е. '01'), и RC[i] = х (т.е. '02')*RC[i-1].

Выбор ключа итерации

Ключ итерации с номером i задается словами из буфера рас­ширенного ключа, начиная с W[Nb * i] и до W[Nb * (i + 1)].

Итак, процесс шифрования состоит из трех этапов: начального добавления подключа; Nr -1 итераций; конечной итерации.

На псевдокоде это выглядит следующим образом:


Rijndael(State,CipherKey) {

KeyExpansion(CipherKey,ExpandedKey);

AddRoundKey(State,ExpandedKey);

For( i=l ; i

Round(State,ExpandedKey + Nb*i);

FinalRound(State,ExpandedKey + Nb*Nr);

}.
3.3. Алгоритм RC6
В качестве одного из кандидатов фирмой RSA Data Security, Inc. был представлен алгоритм RC6 прошедший второй тур от­бора. В нем предусматривается использование четырех рабочих регистров, а также введена операция целочисленного умноже­ния, позволяющая существенно увеличить возмущения, вноси­мые каждым циклом шифрования, что приводит к увеличению стойкости и/или возможности сократить число циклов.

RC6 является полностью параметризованным алгоритмом шифрования. Конкретная версия RC6 обозначается как RC6-w/r/b, где w обозначает длину слова в битах, r - ненулевое ко­личество итерационных циклов шифрования, а b - длину ключа в байтах. Во всех вариантах RC6-w/r/b работает с четырьмя w-битовыми словами, используя шесть базовых операций, обозна­чаемых следующим образом:



а + b- целочисленное сложение по модулю 2W;

а - b- целочисленное вычитание по модулю 2W;

а b - побитовое "исключающее ИЛИ" w-битовых слов;

а x b - целочисленное умножение по модулю 2W;

a « b - циклический сдвиг w-битового слова влево на вели­чину, заданную log2w младшими битами b;

a » bциклический сдвиг w-битового слова вправо на ве­личину, заданную log2W младшими битами b;

Шифрование при помощи RC6-w/r/b описывается следую­щим образом:

Вход: Исходный текст, записанный в 4 w-битовых входных регистрах А, В, С, D; Число циклов шифрования r; Ключевая таблица S[0; ... 2r + 3] w-битовых слов.

Выход: Шифрованный текст в регистрах А, В, С, D.




Расшифрование в этих обозначениях выглядит очень похо­же:

Вход: Шифрованный текст, записанный в 4 w-битовых входных регистрах А, В, С, D; Число циклов шифрования r; Ключевая таблица S[0; ... 2r + 3] w-битовых слов.

Выход: Исходный текст в регистрах А, В, С, D.


Алгоритм вычисления ключей для RC6-w/r/b выглядит сле­дующим образом:

Пользователь задает ключ длиной b байтов. Достаточное число ненулевых байтов дописываются в конец, чтобы получи­лось целое число слов. Затем эти байты записываются начиная с младшего в массив из с слов, т.е. первый байт ключа записыва­ется в L[0], и т.д., a L[c - 1] при необходимости дополняется со стороны старших разрядов нулевыми байтами. В результате ра­боты алгоритма генерации ключей будет вычислено 2r + 4 слов, которые будут записаны в массиве S[0; ...; 2r + 3].

Константы Р32 = B7E15163h and Q32 = 9E3779B9h - это кон­станты, получаемые из двоичного представления е -2, где е -основание натуральных логарифмов, и ф - 1, где ф - золотое се­чение, соответственно. Подобные же константы могут быть аналогичным образом получены и для RC6 с другим размером слова. Выбор констант является в некотором роде произволь­ным, и поэтому можно использовать и другие константы, полу­чая при этом "частные" версии алгоритма.

Вход: Определенный пользователем b-байтовый ключ, предварительно загруженный в массив L[0;.. .с - 1]; Число циклов шифрования r.

Выход: Ключевая таблица S[0;...2r +4] из w-битовых слов.


Структура шифра RC6 является обобщением сети Фейштеля. Блок текста разбивается не на 2, а на 4 подблока, и на каждой итерации изменяются 2 подблока из четырех. При этом в конце итерации шифрования производится циклический сдвиг под­блоков влево (при расшифровании, соответственно, вправо). Однако, такое обобщение привело к тому, что было утеряно свойство инвариантности блоков шифрования и расшифрова­ния, хотя это и не является определяющим в оценке данного алгоритма.
3.4. Российский стандарт шифрования ГОСТ 28147-89
В Российской Федерации установлен единый стандарт крип­тографического преобразования текста для информационных систем. Он носит обязательный характер для государственных органов, организаций, предприятий, банковских и иных учреж­дений, чья деятельность связана с обеспечением информацион­ной безопасности государства. Для других организаций и част­ных лиц, ГОСТ имеет рекомендательный характер.

Данный стандарт формировался с учетом мирового опыта и, в частности, были приняты во внимание недостатки и нереали­зованные возможности алгоритма DES, поэтому использование стандарта ГОСТ предпочтительнее. Алгоритм шифрования по­строен с использованием сети Фейстеля.



3. Условия работы


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

4. Содержание отчета


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

Отчет должен содержать:



  1. Титульный лист;

  2. Условия работы;

  3. Блок-схему алгоритма;

  4. Листинг программы;

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

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

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


5. Контрольный вопросы

1. Назовите базовые криптографические операции?

2. Назовите основные распространенные блочные шифры?

3. Принцип работы сети Файстеля?

4. Основный логические операции применяемые в блочных шифрах?



6. Список рекомендуемой литературы

  1. Столлингс В. Криптография и защита сетей. Принципы и практика. 2-е изд. – М.: Вильямс, 2001. – 672 с.

  2. Шнайер Б. Прикладная криптография. – М: Триумф, 2002. – 815 с

  3. Бабенко Л.К. Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа. – Гелиос АРВ, 2006. – 376 с.

  4. Смарт Н. Криптография. – Техносфера,2006. – 528 с.

  5. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. Учебное пособие. – Гелиос АРВ, 2001. – 480 с.



Смотрите также:
Методические указания к выполнению лабораторной работы №4 для студентов очной формы обучения
161.7kb.
1 стр.
Методические указания к выполнению практических заданий по курсу "Основы рекламы" Санкт-Петербург 2006
263.55kb.
1 стр.
Методические указания по выполнению практических работ адресованы студентам очной (заочной) формы обучения
3387.57kb.
19 стр.
Методические указания по выполнению лабораторной работы №13 для студентов специальности 071900 «Информационные системы и технологии»
133.9kb.
1 стр.
Методические указания к выполнению лабораторной работы №6 для студентов специальности 071900 "Информационные системы и технологии" Хабаровск
177.85kb.
1 стр.
Методические указания по выполнению контрольной работы для студентов заочной формы обучения по специальности «Юриспруденция»
319.7kb.
1 стр.
Методические указания к выполнению контрольной работы №1 для студентов специальности 1-25 01 07 «Экономика и управление на предприятии»
386.47kb.
3 стр.
Методические указания для студентов экономических специальностей заочной формы обучения
584.02kb.
3 стр.
Методические указания к выполнению контрольной работы для студентов экономической специальности 080507 «Менеджмент организации» заочной формы обучения
198.38kb.
1 стр.
Методические указания по выполнению курсовой работы для студентов очной формы обучения Специальность 120303. 65 «Городской кадастр»
692.46kb.
3 стр.
Методические указания по изучению тем по курсу «Коммерческое право»
1220.74kb.
7 стр.
Методические указания по выполнению контрольных работ для студентов заочной формы обучения и слушателей факультета обучения в сокращенные сроки по специальности 030501 «Юриспруденция»
482.83kb.
3 стр.