Файл: Методы кодирования данных (позволяющие выполнять шифрование).pdf

(4)

Для того, чтобы вычислить CRC сообщения, выбирается другой многочлен, называемый порождающим полиномом G(x). G(x) должен иметь степень больше нуля и меньше, чем у многочлена M(x). Другое требование для G(x) – это ненулевой коэффициент члена x0. Это приводит к нескольким возможным вариантам полинома-генератора и, следовательно, к необходимости стандартизации. CRC-16 является одним из таких стандартов, который использует генерирующий полином:

(5)

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

CRC-32 использует другой генераторный полином:

(6)

В общем случае n-битный CRC вычисляется путем представления потока данных в виде полинома M(x), умножения M(x) на xⁿ (где n – степень полинома G(x)) и деления результата на порождающий полином G(x). Полученный остаток добавляется к многочлену M(x) и передается по каналу. Полный переданный полином затем делится на этот же порождающий полином на стороне получателя. Если результат этого деления не имеет остатка, это означает, что нет ошибок передачи. Математически это можно представить так:

(7)

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

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга [8.]. Использование другого полинома – CRC-32C – позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше – поэтому в наши дни он тоже пользуется популярностью [13.]. К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

Полином (3) в шестнадцатеричном виде выглядит как 0x04C11DB7 – этот многочлен является рекомендованным для стандарта IEEE 802 с подгруппой 802.3. Эта подгруппа является основой семейства технологий пакетной передачи данных Ethernet. IEEE 802.3 определяет многочлен M(x) как адрес назначения, адрес источника, длину / тип и данные фрейма с добавлением первых 32-битных данных. Остаток от вычисления CRC выше дополняется, и в результате получается 32-битный CRC IEEE 802.3, называемый полем Frame Check Sequence (FCS). FCS добавляется в конец кадра Ethernet и передается первым битом высшего порядка (x³¹, x³⁰, …, x¹, x⁰).

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

(8)

где

R(x) – полином, представляющий значение CRC;

P(x) – полином, коэффициенты которого представляют входные данные;

G(x) – порождающий полином;

N – степень порождающего полинома (1 ≤ N ≤ 256).

Алгоритмы вычисления циклических избыточных кодов

Прямой алгоритм вычисления CRC определяет контрольную CRC побитно [9.], его можно описать следующим образом в соответствии с (5):

1) дополнить исходное сообщение нулями для выравнивания (количество нулей обусловливается степенью порождающего полинома). P(x)´ = P(x)000…N;

2) выполнять операцию сдвига влево последовательности бит сообщения P(x)´ до тех пор, пока бит в ячейке не станет равным единице или количество бит станет меньше, чем в делителе;

3) если старший бит станет равным единице, то произвести операцию XOR между сообщением и порождающим полиномом и повторить шаг 2;

4) конечный остаток от последовательности P(x)´ является CRC-остатком.

В приведенном описании G(x) – полином, N – степень полинома, P(x) – исходное сообщение, а P(x)´ – дополненное исходное сообщение.

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

Табличный алгоритм вычисления CRC используется для ускорения расчета контрольной суммы CRC [10.].

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

Предпосылкой появления таблицы явилось то, что при выполнении операции XOR содержимого с постоянной величиной при различных ее сдвигах всегда будет существовать некоторое значение, которое при применении операции XOR с исходным содержимым даст тот же самый результат [2.]. Следовательно, можно составить таблицу таких величин, где индексом является исходное содержимое [15.].

Алгоритм составления таблицы:

1) вычислить значение в таблице для каждого байта от 0x00 до 0xff:

а) выполнять 8 раз операцию «сдвиг вправо», причем, если младший бит равен 1, то выполняется операция XOR с полиномом G;

б) все что осталось от двух байт, становится значением в таблице.

Алгоритм вычисления контрольной суммы CRC по таблице:

1) просматривается каждый байт сообщения P(x):

а) над младшим байтом текущего значения CRC и текущим байтом сообщения проводится операция XOR – это индекс в таблице;

б) старший байт текущего значения CRC сдвигается вправо на 8 и становится младшим, затем объединяется по XOR со значением таблицы – это будет новое значение CRC;

2) в результате получено значение CRC.

Практическая реализация алгоритмов

Выбор языка и среды разработки

Данный раздел посвящен разработке простых прикладных программ с графическим интерфейсом пользователя. Учитывая цели данной курсовой работы, в качестве языка программирования был выбран язык высокого уровня C# версии 7.0 как один из наиболее популярных среди современных языков программирования, предназначенных для обучения. В качестве среды разработки выбрана Visual Studio 2019 Community. Выбор среды разработки для реализации программного приложения был мотивирован тем, что выбираемая среда должна быть простой в использовании, чтобы позволить сосредоточиться на изучении концепций программирования, а также многофункциональной для того, чтобы научиться создавать простые программы для решения прикладных задач [16.].

В качестве проектируемых приложений рассматриваются две программы с графическим пользовательским интерфейсом. Первая из рассматриваемых программ позволяет вычислять контрольные суммы файлов, выбранных пользователем, при помощи алгоритма CRC-32, вторая – выполнять шифрование и дешифрование текста, заданного пользователем, при помощи алгоритма RSA. Для реализации был выбран интерфейс программирования приложений Windows.Forms, являющийся частью Microsoft .NET Framework. С помощью Windows.Forms можно создавать приложения с полнофункциональным графическим интерфейсом, в то же время простые в использовании и обновлении [4.]. Выбранный язык программирования вместе со средой разработки позволяет полностью реализовать программу, отвечающую всем предъявленным ей требованиям [12.].

Разработка программного кода для алгоритма CRC-32

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

Вычисление контрольной суммы производится в соответствии с алгоритмами, рассмотренными в подразделе 3.2. В листинге 1 приведен фрагмент программы, выполняющий построение таблицы, в листинге 2 – фрагмент программы, выполняющий вычисление CRC в соответствии с построенной таблицей.

Листинг 1. Исходный код для реализации алгоритма построения таблицы CRC-32

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

{

Crc32 = (uint) i;

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

if ((Crc32 & 1) == 1)

Crc32 = (Crc32 >> 1) ^ POLYNOMIAL;

else

Crc32 >>= 1;

table_CRC32[i] = Crc32;

}

Листинг 2. Исходный код для реализации вычисления контрольной суммы в соответствии с таблицей CRC-32

int count = stream.Read(buffer, 0, buffer_size);

while (count > 0)

{

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

result = ((result) >> 8) ^ table_CRC32[(buffer[i]) ^ ((result) & 0x000000FF)];

count = stream.Read(buffer, 0, buffer_size);

}

Полный исходный код программы приведен в приложении 1.

Тестовый пример, приведенный в данном подразделе, можно рассматривать как руководство пользователя. Для запуска программы достаточно запустить файл CRC32List.exe. Программа корректно работает в MS Windows 7/8/10. Установка не требуется.

Пример работы программы после запуска и перетаскивания файлов в область экрана (в список на форме приложения) приведен на рисунке 2. Для проверки были взяты файлы текущего проекта программы.

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

Рисунок 2 – Результат работы программы

Рисунок 3 – Результат вычисления контрольных сумм при помощи программы WinRAR

Разработка программного кода для алгоритма RSA

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

При вводе чисел и пользователем необходимо выполнить их проверку на простоту. Для проверки простоты числа, заданного пользователем, в программе используется алгоритм Миллера-Рабина с 10 раундами. Исходный код функции, реализующей алгоритм, с комментариями к коду приведен в листинге 3.

Листинг 3. Исходный код функции Миллера-Рабина

public static bool MillerRabin(int n, int k)

{

for (int i = 0; i < k; i++) // цикл по количеству раундов

{

// проверка элементарных случаев:

if (n % 2 == 0)

return false;

if (n == 2)

return true;

if (n <= 1)

return false;

// представление n - 1 как 2 ^ s * m

int s = 0;

int m = n - 1;

while (m % 2 == 0)

{

s++;

m = m / 2;

}

// выбор случ. целого числа a в отрезке [2, n − 2]

Random r = new Random();

int a = r.Next(n - 1) + 1;

// поиск mod = a ^ m % n

int temp = m;

long mod = 1;

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

mod = (mod * a) % n;

// вычислить в цикле mod как mod ^ 2 % n

while (temp != n - 1 && mod != 1 && mod != n - 1)

{

mod = (mod * mod) % n;

temp *= 2;

}

// если mod = 1, то составное

// если mod != n - 1, то составное

if (mod != n - 1 && temp % 2 == 0)

return false;

}

return true; // вернуть "вероятно простое"

}

В основной программе для реализации шифрования и дешифрования используется две основных функции – getEncryptedText и getDecryptedText соответственно. Каждая из них является методом класса RSA, в котором реализована основная логика приложения. В зависимости от способа задания значений и – случайным образом или вручную – каждый из методов вызывается с тремя параметрами (исходный или шифрованный текст в виде строки; пара значений и или пара значений закрытого ключа) либо с одним (исходный или шифрованный текст в виде строки). Для шифрования текста с заданными значениями и вычисление необходимых значений открытого ключа осуществляется внутри метода класса в соответствии с описанием алгоритма. Шифрование и дешифрование текста с известными значениями открытого и закрытого ключа осуществляются при помощи методов textEncrypt и textDecrypt соответственно. Каждый из этих методов осуществляет посимвольное преобразование, используя механизм возведения в степень по модулю (см. раздел 1). Исходный код методов приведен в листинге 4. Блоки байтов при шифровании отделяются друг от друга символом «*».