Шифруемся

Дарова,
кулхацкер! Вот ты и подрос в
профессиональном плане, перестал юзать
чужие кульные проги и решил написать свою.
Молодец! Но я думаю, есть у тебя еще одна
трабла - написать прогу ты написал, но вот
твой IQ не смог спрятать твой IP и твой E-mail в
лошадке, и теперь любой желающий, в том
числе и люди в погонах, могут тебя вычислить,
пройдясь отладчиком по твоему творению. Что
делать? Да, нет, не сливать воду, и не
смазывать лыжи, а шифровать(ся). Как? Вот об
этом я тебе я расскажу. Я не буду гнать пургу
насчет DESа (DES умер и уже давно). А вот
несколько самых интересных и конкретных
алгоритмов шифрования я тебе расскажу. Ну,
поехали....

Что такое RSA?

Одним из
признанных алгоритмов шифрования является
RSA. Модификации этого алгоритма весьма
широко распространены - даже всем известная
PGP основана на этом алгоритме. Суть этого
алгоритма весьма проста:

1. Выбираются
большие простые числа M и N;

2. Вычисляется их
произведение: Q=MxN;

3. Выбирается
число D, которое должно быть взаимно простым
с результатом умножения (M-1)x(N-1), т.е. не
должно иметь с ним общих делителей,
отличных от единицы;

4. Вычисляется
число A из выражения (AxD) mod [(M-1)x(N-1)]=1;

Таким образом,
пара чисел (A,Q) будет твоим открытым ключом,
а пара чисел (D,Q) - закрытым ключом. Понятно,
что открытым ключом можно только
закодировать исходный текст, для того,
чтобы его раскодировать, нужен закрытый
ключ.

Кодирование
числа P: C=M^A mod Q;

Обратная
операция: P=C^D mod Q;

Вот и все.
Возникает только один вопрос: ломается ли RSA?
Если крутить что-то достаточно долго, то
ломается все! Тем более зная внутреннее
устройство....

Так вот, для того,
чтобы поломать RSA, сиречь PGP (круто, да?),необходимо
и достаточно уметь разложить число Q (которое
мы возьмем, понятно, из открытого ключа,
помещенного человеком в бурные воды Internet)
на простые множители. Вот тут-то и
начинается самое интересное. 🙂

Простые
множители числа - летопись в теории чисел,
над ними бились многие математики, но увы,
так ничего толком и не добились. В
математике не существует теорем, могущих
надежно предсказать, является ли число
простым. Есть теоремы, которые могут быстро
установить, что число составное, но если
условия теоремы не выполняются, то это не
значит, что число простое: это значит, что
оно ВРОДЕ БЫ простое, и надо применять более
сильные теоремы, которые, увы, на машине
проверяются только перебором. Далее, нет
теорем, которые помогают хотя бы оценить
количество простых сомножителей числа и
порядок их величины. Так что реально число
из, скажем, трехсот десятичных знаков
разложить на простые множители (если они,
правда не лежат близко к корню из числа и т.д.
- есть легкие случаи) за разумное время
нереально. Так, программа на 266 пне
раскладывает число из 17 десятичных знаков
за время, близкое к тридцати секундам, но
время ее работы есть P*exp(n), т.е. число из 300
знаков она будет раскладывать в exp(280) раз
дольше (это около 5*10^279). Естественно, что
если взять более быстрое точило, Cray, к
примеру, то будет побыстрее...:) Но все равно
не слишком. Правда, есть более быстрые
алгоритмы, решето Сива, например, но они
хороши, когда сомножители лежат близко к
корню, и требуют дикое количество памяти.

Сторожевая
Кобра

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

Кобpа - это такой
старенький пpогpаммный комплекс для
установки на pазличные ПЭВМ типа IBM-PC.
Заключения экспеpтов: кpиптостойкость пpевосходит
DES, алгоpитм обладает хоpошими кpиптогpафическими
свойствами со стойкостью ~10^22 относительно
многих методов кpиптоанализа, тpудоемкость
расшифровки составит 10^12 опеpаций,
необходимый объем памяти для
восстановления ключа - 10^10 байт, для
полноценного анализа тpебуются pаботы тpудоемкостью
100..120 чел.мес. и пpодолжительностью 1.5-2 года.
В общем один из наикрутейших
профессиональных программных продуктов
для заинтересованных лиц. Но покупать ее мы,
ессесно, не собираемся. Нас интересует
алгоритм, шифрования, заложенный в его
внутренностях. Рассмотрим его на примере
зашифровывания 512 байт текста. Шифрование
состоит из нескольких основных
последовательных процедур, которые
выполняются в определенном порядке при
разных начальных условиях (значения Uо, Yо, Co,
K1).

Обозначения:

Ti и Ci - i-тые пары
символов исходного текста и шифра,
представленные двухбайтовым числом;
Fm(Ui), Fc(Yi), Fс(Ui), Fm(Yi) - значения пар ключевых
элементов с номерами Ui и Yi, в подключах m и c;
K1 - константа, определяемая паролем; 
Cl - младший байт двухбайтового числа,
отображающего пару символов; 
Ch - старший байт двухбайтового числа,
отображающего пару символов.

¦<------------
подключ m ----------->¦ Fc 
г==T==¬г==T==¬г==T==¬ г==T==¬г==T==¬г==T==¬г==T==¬г==T==¬г==T==¬
L==¦==-L==¦==-L==¦==-L==¦==-L==¦== -L==¦==-L==¦==-L==¦==-L==¦==-

Fm ¦<--------------
подключ c --------------->¦

Общий ключ
длиной 384 байта разбит на два подключа длиной
по 257 байт.

Алгоритм 1-ой
процедуры. (значения входных символов
пронумерованы в обратной
последовательности)

1. Установить
значение счетчика i=1 и задать начальные
положения указателей Uо, Yо и К1 как функцию f1
от пароля.

2. Осуществить
преобразование i-той пары исходных символов:

C'i = (Ti - K1) XOR Fm(Ui-1 mod
256)

3. Вычислить
новые значение указателей U и Y:

Ui = (Ui-1 mod 256) XOR Fc(Yi-1
mod 256)

Уi = (Уi-1 mod 256)+ Cl'i

4. Закончить
преобразование i-той пары исходных символов:

Ci = C'i + Ui

5. Установить i=i+1.
Если i<=256, то перейти к п.2, иначе СТОП. 

Алгоритм 2-ой
процедуры. (значения входных символов
пронумерованы в прямой последовательности)

1. Установить
значение счетчика i=1 и задать начальные
положения указателей Uо, Yо как функцию f2 от
пароля.

2. Осуществить
преобразование i-той пары исходных символов:

C'i = Ti XOR Fс(Ui-1 mod 256)

3. Вычислить
новые значения указателей U и Y:

Ui = (Ui-1 mod 256) XOR Fm(Yi-1
mod 256)

Уi = (Уi-1 mod 256)+ Ch'i

4. Закончить
преобразование i-той пары исходных символов:

Ci = C'i + Ui

5. Установить i=i+1.
Если i<=256, то перейти к п.2, иначе СТОП.

Алгоритм 3-ей
процедуры. (значения входных символов
пронумерованы в обратной
последовательности)

1. Установить
значение счетчика i=1 и задать начальные
положения указателей Uо, Yо и Со как функцию
f3 от пароля.

2. Осуществляется
преобразование i-той пары исходных символов:

C'i = (Ti + C'i-1) XOR Fm(Ui-1
mod 256)

3. Вычислить
новые значение указателей U и Y:

Yi = Yi-1 + Cl'i-1

Ui = ((Ui-1 mod 256) XOR Fc(Yi
mod 256)) + Ch'i-1

4. Закончить
преобразование i-той пары исходных символов:

Ci = C'i + Ui

5. Установить i=i+1.
Если i<=256, то перейти к п.2, иначе СТОП.

Алгоритм 4-ой
процедуры. (значения входных символов
пронумерованы в прямой последовательности)

1. Установить
значение счетчика i=1 и задать начальные
положения указателей Uо, Yо и Со как функцию
f4 от пароля.

2. Осуществляется
преобразование i-той пары исходных символов:

C'i = (Ti + C'i-1) XOR Fс(Ui-1
mod 256)

3. Вычислить
новые значение указателей U и Y:

Yi = Yi-1 + Ch'i-1

Ui = ((Ui-1 mod 256) XOR Fm(Yi
mod 256)) + Cl'i-1

4. Закончить
преобразование i-той пары исходных символов:

Ci = C'i + Ui

5. Установить i=i+1.
Если i<=256, то перейти к п.2, иначе СТОП.

Порядок
выполнения основных последовательных
процедур определяется на этапе
аутентификации пользователя пpи
формировании конкpетного механизма кpиптогpафических
пpеобpазований в зависимости от требуемой
криптостойкости и может пpедусматpивать
такие ваpианты:

четыре три две
две процедуры.

процедуры
процедуры процедуры первая неполная

Здесь цифpа
обозначает номеp основной пpоцедуpы; знаки '-'
и '+' напpавление обpаботки
последовательности символов; индекс f -
модификацию функции от паpоля для
вычисления начальных значений и констант
используемых в основных пpоцедуpах; знак '*'
означает, что этой процедурой
обрабатывается только часть входной
последовательности символов;

Естественно, что
при использовании трех и тем более четырех
процедур вариантов будет больше.

З.Ы. На мой взгляд
один из самых лучших алгоритмов на сегодня,
хотя вот с реализацией придется повозиться.

Наш родной
советский GOST.

Здесь приведена
реализация ГОСТ, пусть не самая эффективная,
но содержащая несколько интересных, на мой
взгляд, идей. Константы C1 и C2 каждый
желающий может посмотреть в ГОСТе, здесь я
их публиковать не буду. (Для тех, кто в танке:
ГОСТ - Государственный СТандарт. Так вот,
для алгоритмов шифрования данных, тоже
разработали стандарт, типа так и не иначе, и
алгоритм такого шифрования получил
соответствующее название ГОСТ ).

Итак,
непосредственная реализация на С++. (big thanks to
Stanislav Asanov). Алгоритм мне уже в лом описывать,
да и тебе практика не помешает. Кому
интересно - прямая дорога в техническую
библиотеку, а там спросите ГOСT-28147-89, ГОСT Р
34.10-94, ГОСТ Р 34.11-94.

#include <stdio.h>
#include "gost.h"
#pragma hdrstop
// Внутренние типы
typedef BYTE PERM_TABLE[256];
// Внутренние переменные
static Inited = NO;
// Ключи
static DWORD X[32];
static PERM_TABLE K[4];
// Внутренние константы.
static int indexes[] =
{ 0, 1, 2, 3, 4, 5, 6, 7,
0, 1, 2, 3, 4, 5, 6, 7,
0, 1, 2, 3, 4, 5, 6, 7,
7, 6, 5, 4, 3, 2, 1, 0 };
void print_block( BYTE * addr, int len );
BOOL init( KEY key, SBOX sbox[8] )
{
int i, j, k;
if( Inited )
return( NO );
for( i = 0; i < NITEMS( X ); i++ )
X[i] = key[indexes[i]];
for( i = 0; i < 4; i++ )
for( j = 0; j < 16; j++ )
for( k = 0; k < 16; k++ )
K[i][ (j<<4) + k ] = ( sbox[i*2+1][j] << 4 ) + sbox[i*2][k];
return( Inited = YES );
};
BOOL terminate( void )
{
int i, j;
if( !Inited )
return( NO );
for( i = 0; i < NITEMS( X ); i++ )
X[i] = 0;
for( i = 0; i < 4; i++ )
for( j = 0; j < 256; j++ )
K[i][j] = 0;
Inited = NO;
return( YES );
};
void ghost_encrypt_sp( void ); // Эта функция должна быть
написа на АСМе, дабы усе быстро летало.
void encrypt_sp( KEY key, BLOCK data )
{
DWORD a, b, a_new;
int i, j;
union {
DWORD d;
BYTE b[4];
} tmp;
if( !Inited )
return;
a = data[0];
b = data[1];
for( j = 0; j < 32; j++ ) { // Цикл шифрования
tmp.d = a + X[j];
for( i = 0; i < NITEMS( tmp.b ); i++ )
tmp.b[i] = K[i][tmp.b[i]];
a_new = ( ((tmp.d&0x001FFFFFUL) << 11) + ((tmp.d&0xFFE00000UL)>>21)
) ;
b = a;
a = a_new;
};
data[0] = b;
data[1] = a;
};
void decrypt_sp( BLOCK data )
{
DWORD a, b, a_new;
int i, j;
union {
DWORD d;
BYTE b[4];
} tmp;
if( !Inited )
return;
a = data[0];
b = data[1];
for( j = 0; j < 32; j++ ) { // Цикл расшифровки
tmp.d = a + X[31-j]; // !!! Вот только этим и отличается
шифрация от дешифрации
for( i = 0; i < NITEMS( tmp.b ); i++ )
tmp.b[i] = K[i][tmp.b[i]];
a_new = ( ((tmp.d&0x001FFFFFUL) << 11) + ((tmp.d&0xFFE00000UL)>>21)
);
b = a;
a = a_new;
};
data[0] = b;
data[1] = a;
};
#define Const_C1 0xXXXXXXXXUL
#define Const_C2 0xXXXXXXXXUL
void encrypt_g( BLOCK synchro, BYTE * data, UINT len )
{
BLOCK gamma;
ULONG lo, hi;
UINT chunk;
BYTE * p;
gamma[0] = synchro[0];
gamma[1] = synchro[1];
encrypt_sp( X, gamma );
lo = gamma[0];
hi = gamma[1];
while( len > 0 ) {
lo += Const_C2;
if( hi < (0xFFFFFFFFUL - Const_C1) )
hi += Const_C1;
else
hi += Const_C1 - 0xFFFFFFFFUL;
gamma[0] = lo;
gamma[1] = hi;
encrypt_sp( X, gamma );
chunk = ( len > 8 ) ? 8 : len;
len -= chunk;
p = (BYTE *) gamma;
while( chunk-- > 0 )
*data++ ^= *p++;
}
};
void encrypt_gfb( BLOCK synchro, BYTE * data, UINT len )
{
BLOCK gamma, * blk_data;
BYTE * p;
gamma[0] = synchro[0];
gamma[1] = synchro[1];
encrypt_sp( X, gamma );
while( len >= sizeof( BLOCK ) ) {
blk_data = (BLOCK *) data;
data += sizeof( BLOCK );
gamma[0] ^= (*blk_data)[0];
gamma[1] ^= (*blk_data)[1];
(*blk_data)[0] = gamma[0];
(*blk_data)[1] = gamma[1];
encrypt_sp( X, gamma );
len -= sizeof( BLOCK );
}
p = (BYTE *) gamma;
while( len-- > 0 )
*data++ ^= *p++;
};
void decrypt_gfb( BLOCK synchro, BYTE * data, UINT len ){
BLOCK newgamma, gamma, * blk_data;
BYTE * p;
gamma[0] = synchro[0];
gamma[1] = synchro[1];
encrypt_sp( X, gamma );
while( len >= sizeof( BLOCK ) ) {
blk_data = (BLOCK *) data;
data += sizeof( BLOCK );
newgamma[0] = (*blk_data)[0];
newgamma[1] = (*blk_data)[1];
(*blk_data)[0] ^= gamma[0];
(*blk_data)[1] ^= gamma[1];
gamma[0] = newgamma[0];
gamma[1] = newgamma[1];
encrypt_sp( X, gamma );
len -= sizeof( BLOCK );
}
p = (BYTE *) gamma;
while( len-- > 0 )
*data++ ^= *p++;
}

.h к этому тексту,
я думаю, напишешь сам.

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