Открытый ключ с закрытыми глазами

kIlka (kilka@linkin-park.ru)

Спецвыпуск Xakep, номер #041, стр. 041-008-1

Практикуемся в реализации RSA

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

Принцип действия RSA был достаточно подробно рассмотрен, так что перейдем сразу к делу. Программировать будем на С++. Если точнее, то на C++ стандарта ANSI/ISO. То есть иногда я, как человек ленивый, использовал всякие вкусности из STL (стандартной библиотеки шаблонов). Если у тебя возникнут какие-то трудности при чтении исходников, обращайся к [3]. Возможно, использование C или какого-нибудь другого процедурно-ориентированного языка (в следующий раз стоит попробовать GW-BASIC =)) сделало бы программу понятнее для тех, кто плохо знаком с ООП. Однако мне кажется, что C++ для решения этой задачи удобнее. Сейчас будет ясно, почему.

Кстати, все касающиеся RSA исходники из этой статьи, объединенные в полностью рабочую программу, можно найти на нашем диске. Для ее компиляции потребуется BCC v5.5 и ТASM v5. Их ты тоже найдешь на диске. Подробнее о компиляции смотри в файле readme.

Начало большого пути

Класс Number

Первая проблема, которая сразу приходит на ум, когда задумываешься о реализации RSA - как организовать работу с большими числами. Ведь числа r и h должны иметь длину, по крайней мере, 512 бит (моя реализация использует 1024-битные числа).

Разумное решение - хранить большие числа в массиве unsigned long int. Для удобства обзовем этот тип dword. Но ведь эти числа нужно складывать, вычитать, возводить в степень. Можно было бы, конечно, реализовать все это через функции. Но это неудобно. Гораздо приятнее воспользоваться перегруженными операторами. Создадим класс Number, который и будем использовать для представления больших чисел. В общих чертах он выглядит так:

class Number

{

public:

dword* data; // Массив, где лежит число..

: Конструкторы :

bool operator[] (int); // Обращение к отдельному биту

void operator= (Number ); // Присваивание больших чисел

friend ostream& operator<< (ostream &, Number &); // Печать

: Остальные операторы :

};

Класс имеет несколько конструкторов - для создания числа со значением, загружаемым из памяти, со значением типа int. Конструктор по умолчанию создает число с нулевым значением. Для обращения к отдельному биту (они лежат на отрезке [1, length]) используется operator[]. Его реализация элементарна и для пущей эффективности может быть выполнена на ассемблере.

Перегруженный оператор помещения в поток

Остальные операторы - оператор сложения (+=), вычитания (-=), сравнения и побитового сдвига влево на 1 бит. Операторы сложения и вычитания написаны на асме (в виде ассемблерных вставок). Вот, к примеру, оператор сложения:

void Number::operator+= (Number &number)

{

dword* destination = data;

dword* source = number.data;

asm {

mov edi, destination

mov esi, source

mov ecx, LENGTH_DWORD

xor eax, eax

cycle1:mov eax, [esi]