МИНИСТЕРСТО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

КАФЕДРА: «Компьютерные технологии»

ДИСЦИЛИНА: «ОИБ» 
 
 
 

ОТЧЕТ

по курсовой работе

Тема: «Реализация криптографического алгоритма (AES) Rijndael» 
 
 
 
 

Выполнил: ст. гр. БВТ 09-4

Рахматуллин А.А.

Проверил:

доцент  Шайхин Б.М.

  
 
 
 
 

Алматы 2011 

Содержание

Введение 2

История AES 3

Описание AES 4

Программная реализация алгоритма AES 11

Листинг программы 13

Заключение 32

Список  использованной литературы 33 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

 

Шифрование — способ преобразования открытой информации в закрытую и обратно. Применяется для хранения важной информации в ненадёжных источниках или передачи её по незащищённым каналам связи. Согласно ГОСТ 28147-89, шифрование подразделяется на процесс зашифровывания и расшифровывания.

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

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

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

История AES

В далеком 1998 году NIST объявил конкурс на создание алгоритма, удовлетворяющего выдвинутым институтом требованиям. Он опубликовал все  несекретные данные о тестировании кандидатов на роль  AES и потребовал от авторов алгоритмов сообщить о  базовых принципах построения используемых в них констант. В отличие от ситуации с DES, NIST при выборе  AES не стал опираться на секретные и, как  следствие, запрещенные к публикации данные об исследовании алгоритмов-кандидатов. 

Чтобы быть утвержденным в качестве стандарта, алгоритм должен был:

реализовать шифрование частным ключом;

представлять  собой блочный шифр;

работать со 128-разрядными блоками данных и ключами  трех размеров (128, 192 и 256 разрядов). 

Дополнительно кандидатам рекомендовалось:

использовать  операции, легко реализуемые как  аппаратно (в микрочипах), так и  программно (на персональных компьютерах  и серверах);

ориентироваться на 32-разрядные процессоры;

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

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

Перед первым туром  конкурса в NIST поступило 21 предложение, 15 из которых соответствовали выдвинутым критериям. Затем были проведены исследования этих решений, в том числе связанные с дешифровкой и проверкой производительности, и получены экспертные оценки специалистов по криптографии. В августе 1999 года NIST объявил пять финалистов, которые получили право на участие во втором этапе обсуждений. 2 октября 2000 года NIST сообщил о своем выборе – победителем конкурса стал алгоритм  RIJNDAEL (произносится как «райндол») бельгийских криптографов  Винсента Раймана и  Йоана Дамана, который зарегистрирован в качестве официального федерального стандарта как  FIPS 197 (Federal Information Processing Standard). 

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

Описание AES

Определения и вспомогательные процедуры

Block - последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байт

Cipher Key - секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок.

Ciphertext - выходные данные алгоритма шифрования

Key Expansion - процедура используемая для генерации Round Keys из Cipher Key

Round Key - Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании

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

S-box - нелинейная таблица замен, использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта. Предварительно рассчитанный S-box - можно увидеть ниже.

Nb - число столбцов(32-ух битных слов), составляющих State.

Для, AES Nb = 4

Nk - число 32-ух битных слов, составляющих шифроключ.

Для AES, Nk = 4,6, или 8

Nr - число раундов, которое является функцией Nk и Nb. Для AES, Nr = 10, 12, 14

Rcon[] - массив, который состоит из битов 32-х разрядного слова и является постоянным для данного раунда. Предварительно рассчитанный Rcon[] можно увидеть ниже.

S-box

Sbox = array(

        0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,

        0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,

        0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,

        0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,

        0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,

        0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,

        0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,

        0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,

        0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,

        0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,

        0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,

        0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,

        0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,

        0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,

        0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,

        0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16,

    ); 
 

Rcon[]

Rcon = array(

        array(0x00, 0x00, 0x00, 0x00),

        array(0x01, 0x00, 0x00, 0x00),

        array(0x02, 0x00, 0x00, 0x00),

        array(0x04, 0x00, 0x00, 0x00),

        array(0x08, 0x00, 0x00, 0x00),

        array(0x10, 0x00, 0x00, 0x00),

        array(0x20, 0x00, 0x00, 0x00),

        array(0x40, 0x00, 0x00, 0x00),

        array(0x80, 0x00, 0x00, 0x00),

        array(0x1b, 0x00, 0x00, 0x00),

        array(0x36, 0x00, 0x00, 0x00),

    ); 

Вспомогательные процедуры

AddRoundKey() - трансформация при шифровании и обратном шифровании, при которой Round Key XOR’ится c State. Длина RoundKey равна размеру State(те, если Nb = 4, то длина RoundKey равна 128 бит или 16 байт)

InvMixColumns() - трансформация при расшифровании которая является обратной по отношению к MixColumns()

InvShiftRows() - трансформация при расшифровании которая является обратной по отношению к ShiftRows()

InvSubBytes() - трансформация при расшифровании которая является обратной по отношению к SubBytes()

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

RotWord() - функция, использующаяся в процедуре Key Expansion, которая берет 4-х байтное слово и производит над ним циклическую перестановку

ShiftRows()  - трансформации при шифровании, которые обрабатывают State, циклически смещая последние три строки State на разные величины

SubBytes() - трансформации при шифровании которые обрабатывают State используя нелинейную таблицу замещения байтов(S-box), применяя её независимо к каждому байту State

SubWord() - функция, используемая в процедуре Key Expansion, которая берет на входе четырёх-байтное слово и применяя S-box к каждому из четырёх байтов выдаёт выходное слово 

Шифрование

AES является стандартом, основанным на алгоритме Rijndael. Для AES длина input(блока входных  данных) и State(состояния) постоянна  и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. При  этом, исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит с шагом в 32 бита. Для обозначения выбранных длин input, State и Cipher Key в байтах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

В начале шифрования input копируется в массив State по правилу s[r,c] = in[r + 4c], для  и . После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу out[r + 4c] = s[r,c], для и .

Отдельные трансформации SubBytes(), ShiftRows(), MixColumns(), и AddRoundKey() — обрабатывают State. Массив w[] — содержит key schedule. 

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

begin

    byte state[4,Nb]

   

    state = in 

    AddRoundKey(state, w[0, Nb-1]) 

    for round = 1 step 1 to Nr-1

        SubBytes(state)

        ShiftRows(state)

        MixColumns(state)

        AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

    end for 

    SubBytes(state)

    ShiftRows(state)

    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) 

    out = state

end 

SubBytes()

 В процедуре  SubBytes, каждый байт в state заменяется  соответствующим элементом в  фиксированной 8-битной таблице поиска, S; bij = S(aij).

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя  нелинейную замену байтов используя  таблицу замен (S-box). Такая операция обеспечивает нелинейность алгоритма  шифрования. Построение S-box состоит  из двух шагов. Во-первых, производится взятие обратного числа в поле Галуа . Во-вторых, к каждому байту b из которых состоит S-box применяется следующая операция: