XOR-шифрование

Как известно из булевой алгебры, операция логического сложения «⊕» по модулю 2 (или логического исключаещего ИЛИ — XOR, eXclusive OR) имеет следующую семантику:

То есть, операция z = x ⊕ y по сути поразрядная (побитовая — результат не зависит от соседних битов). Если только один из соответствующих битов равен 1, то результат 1. А если оба 0 или оба 1, то результат 0. Если внимательно посмотреть на результат применения XOR к двум двоичным числам, то можно заметить, что мы можем восстановить одно из слагаемых при помощи второго: x = z ⊕ y или y = z ⊕ x.

Отсюда можно сделать следующие выводы: зная число y и применяя XOR к x, мы получим z. Затем, мы, опять же используя y, получим из z обратно число x. Таким образом мы можем преобразовать последовательность чисел (x)_i в последовательность (z)_i. Теперь мы можем назвать число y кодирующим (или шифрующим) ключом. Если человек не знает ключа, то он не сможет восстановить исходную последовательность чисел (x)_i. Но если (x)_i являются байтовым представлением букв текста, то опытный пользователь сможет вскрыть зашифрованный текст. Поскольку каждая буква будет представлена в шифротексте одним и тем же кодом z, то воспользуясь частотным словарем взломщик сможет вычислить шифрующий ключ y, если у него будет в распряжениии достаточно длинный шифротекст.

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

/*
  Генерация ключа: keygen.c
  Формат вызова:
    keygen <имя_файла_с_ключом>
  (C) 1999 Проскурня Максим
*/
#include <stdio.h>
#include <time.h>
 
#define KEY_LENGTH 512
 
void main ( int argc, char[][] argv )
{
  int file;
 
  if ( argc == 2 )
  {
    // Инициализация генератора ПСЧ
    srand ( (unsigned) ::time(0) );
 
    if ( 0 < ( file = open ( argv[1], O_WRONLY ) ) )
    {
      // Генерация и запись ключа
      for ( int i = 0; i < KEY_LENGTH; ++i)
        write ( file, char ( rand () * 255.0 / RAND_MAX ), 1 );
      close ( file );
    }
  }
  else
    printf ("Неверный вызов. Формат: keygen <имя_файла_с_ключом>");
}

А теперь, собственно, кодирование сообщения. Заранее договоримся, что мы будем дописывать PREAMBLE случайных байтов в начало сообщения и TAIL байтов в конец. Поэтому при раскодировании мы сможем сразу опустить содержащий мусор заголовок, а при желании «обрезать» и хвост.

/*
  XOR-шифрование: xorcoder.c
  Формат вызова:
    xorcoder <имя_файла_с_ключом> <файл_с_исходным_текстом> <файл_шифротекста>
  (C) 1999 Проскурня Максим
*/
#include <stdio.h>
#include <time.h>
 
const KEY_LENGTH = 512;
const PREAMBLE   = 117;
const TAIL       = 109;
 
void main ( int argc, char[][] argv)
{
  char     key [KEY_LENGTH];
  char     cipher;
  int      i;
  long     token = 0;
  int      inFile, outFile, keyFile;
 
  if ( argc == 4 )
  {
    // Инициализация генератора ПСЧ
    srand ( (unsigned) ::time(0) );
 
    // Чтение ключа
    if ( 0 < ( keyFile = open ( argv[1], O_RDONLY ) ) )
    {
      read  ( keyFile, key, KEY_LENGTH );
      close ( keyFile );
    }
 
    // Шифрование
    if ( ( 0 < inFile  = open ( argv[2], O_RDONLY ) ) &&
         ( 0 < outFile = open ( argv[3], O_WRONLY ) ) )
    {
      for ( i = 0; i < PREAMBLE; ++i )
        // запись заголовка
        write ( outFile, char ( rand () * 255.0 / RAND_MAX ), 1 );
 
      token = PREAMBLE;
      while ( !eof(inFile) )
      {
        // кодирование
        read ( inFile, & cipher, 1 );
        cipher ^= key [ token % KEY_LENGTH];
        write ( outFile, cipher, 1 );
        ++token;
      }
      close ( inFile );
      for ( i = 0; i < TAIL; ++i )
        // запись хвостовика
        write ( outFile, char ( rand () * 255.0 / RAND_MAX ), 1 );
      close ( outFile );
    }
  }
  else
    printf ("Неверный вызов. xorcoder <имя_файла_с_ключом>"
            "<файл_с_исходным_текстом> <файл_шифротекста>");
}

Для написания раскодировщика нужно просто переписать фрагмент, осуществляющий запись заголовка, на процедуру пропуска первых PREAMBLE байт. Если текст был перед кодированием обработан (например, архиватором), то необходимо, чтобы раскодироващик отбросил TAIL байт с конца для корректного обратного преобразования.