Обратимое XOR шифрование текста со случайной гаммой. Поточные шифры Шифрование с помощью xor

The binary operation XOR (stands for eXclusive OR) is a binary operand (as are AND, OR, etc) from Boole algebra. This operand will compare two bits and will produce one bit in return. That bit will be equal to 1 if the two compared bits were different, 0 if they were equal. Xor encryption is commonly used in several symmetric ciphers (especially AES). A symetric cipher is simply a cipher in which the key is used for encryption and decryption process. The XOR operand is so applied to each bit between the text you want to encrypt and the key you"ll choose. Examples are better than words, let"s take the word "xor". We want to encrypt it with the key "cle". First we have to convert the input and the key in binary representation:

Then we compare each bit with the XOR operand. Which will give you this:

Xor: 01111000 01101111 01110010
cle: 01100011 01101100 01100101
00011011 00000011 00010111

If we wanted to go back to the original input ("xor"), we would just have to reapply the XOR between the output and the key. You can note that XOR is a commutative function, as multiplications. Now what do we do if the key is smaller than the input ? This is the case in most situations. If the key was the same length than the input, it wouldn"t be interesting because you would also have to communicate the key to the person you want reading the input. In contrast, when the key and the input have the same length, it is impossible for someone to crack the cipher. So, when the key is smaller than the input, you just reapply it until you reach the end of input. If by instance I wanted to encrypt the word "bonjour" with my key "cle", I would do it this way:

Bonjour: 01100010 01101111 01101110 01101010 01101111 01110101 01110010
cleclec: 01100011 01101100 01100101 01100011 01101100 01100101 01100011

You can see that we simply repeat the key. The smaller you key, the easiest it will be to crack your cipher (obviously). The XOR cracking often are based on frequency analysis. But for that matter, I suggest you to do some researches.

Согласно определению, двухместная однобитовая операция "исключающее ИЛИ" выполняет действия, показанные в табл. 19.1.

Таблица 19.1. Исключающее ИЛИ(ХОЯ)

Вход 1

Вход 2

Выход

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

Данное свойство и положено в основу практически всех алгоритмов шифрования, которые иногда могут быть очень навороченными, но мы не будем углубляться в этот вопрос, а просто попробуем применить этот метод в его изначальном виде. Для проверки можно использовать такую простейшую процедуру. Пусть мы хотим зашифровать некий текстовый файл. Так как мы дипломатические секреты не прячем, то нам хватит обычной в таких случаях длины ключа в 8 символов (64 бита)- этого достаточно, чтобы сделать взлом шифра методом перебора на обычном персональном компьютере задачей "с налета" нерешаемой. Для примера ключом будет служить слово "yvre- vich". Создавать такие ключи из своей фамилии на практике ни в коем случае нельзя, нельзя также употреблять любые словарные слова, даты, номера ге- лефонов- еще Вернам показал, что для эффективного шифрования ключ должен быть строго случайным, здесь это делается только в качестве примера (о том, как можно задавать случайный ключ, мы поговорим позже).

Создадим новый проект (в папке Glaval9\l) под названием ProbaCrypt, и разместим в той же папке некий файл на пробу. Я взял текст песни "Однажды мир прогнется под нас" из репертуара А. Макаревича (в текстовом же формате, файл mashinavremeni.txt) с аккордами, т. к. достаточно сложное форматирование этого текста сделает пример нагляднее 3 .

Поместим на форму компонент Memo, диалог OpenDialog и две кнопки Butt эл. В заголовке Buttoni напишем Зашифровать, в заголовке Buttoni - Расшифровать. Объявим такие переменные:

Forml: TForml ; fname,key:string; fi,fo:file of byte; i:integer; xb:byte;

При создании формы инициализируем ключ и диалог:

procedure TForml.FormCreate(Sender: TObject); begin key:=’yvrevich";

OpenDialogl.InitialDir:=ExtractFiieDir(Application.ExeName); end;

В обработчике нажатия кнопки Buttonl напишем следующий довольно длинный код:

procedure TForml.ButtonlClick(Sender: TObject); begin /Зашифровать/ OpenDialogl. FileName:?= 11 ; (очистим) OpenDialogl.Filter:=”; if OpenDialogl.Execute then fname:=OpenDialogl.FileName else exit; assignfile(fi,fname); {задали исходный файлI try

reset(fi); {открыли исходный) except

exit; {если не открывается – на выход) end;

assignfile(fo,ChangeFileExt(fname, 1 .sec’)) ; rewrite(fo);

read(fi,xb); {прочли первый байт)

Forml.Caption:=’ProbaCrypt: ‘+ExtractFileName(fname);

/название файла – в заголовок) Memol.Lines.Clear; Memol.Lines.Add(‘Подождите…’);

Application.ProcessMessages; Memol.Lines.Clear; while not eof(fi) do begin

xb:=xb xor ord(key[i]); {шифруем)

Memol.Text:=Kemol.Text+chi(xb); {выводим в Memo)

write(fo,xb); (записываем в файл)

read(fi,xb); {если конец файла – выходим) except break; end; end; end;

closefile(fi) ;

erase(fi); {уничтожаем исходник)

closefile(fo);

{зашифровали) end;

Тут мы складываем через операцию XOR каждый байт исходного файла с байтами ключа по очереди; когда ключ заканчивается, мы опять начинаем с его первого символа. Результаты пишем в файл с расширением sec (от "security") и выводим в Memoi. В точности ту же операцию мы производим при расшифровке, только уже с зашифрованным файлом, в результате чего исходный файл восстанавливается полностью:

procedure TForml.Buttor.2Click(Sender: TObject); begin {Pa оцифровать j OpenDialogl.FileName:=”; {очистим/ OpenDialogl.Filter: = ‘№4>poBaHHbie файлы| *.sec’ ; if OpenDialogl.Execute then fname:OpenDialogl.FileName else exit; assignfile(fi, fname); {открыли шифрованный) try

reset(fi); except exit; end;

assignfile(fo,ChangeFileExt(fname, ‘.txt’)); rewrite(fo); {перезаписываем старый) read(fi,xb);

Forml.Caption:=’ProbaCrypt: ‘+ExtractFileNajne (fname) ;

!название файла – в заголовокj

Memol.Lines.Clear;

Memol.Lines.Add(1 Подождите…’);

Application.ProcessMessages; {чтобы увидеть предупреждение) Memol.Lines.Clear; while not eof(fi) do begin /асе без изменений, как выше} for i:=l to length(key) do begin

xb:=xb xor ord(keyU));

Memol.Text:=Memol.Text+chr(xb);

write(fo,xb);

read(fi,xb); except break; end; end; end;

closefile(fi); closefile(fo); {pa сшифровали) end;

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

Есть тонкий момент, связанный с уничтожением оригинала - как известно, при уничтожении дискового файла он не стирается, подобно музыкальной записи на магнитной ленте, а просто в заголовочных структурах FAT место, которое ои занимает, помечается, как свободное (примерно также происходит это и в NTFS). Именно с этой особенностью была связана работа DOS- программы Unerase (если кто помнит, что это такое). Поэтому, если вы даже удалите файл из Корзины (удаленный из нашей программы файл в Корзину, правда, итак не попадает), на диске останется его содержание до тех пор, пока туда не будет записано что-то еще. Поэтому для особо параноидальных личностей продвинутые программы шифрования предлагают опцию, при которой файлы после стирания уничтожаются гарантированно- на их место записываются нули. В нашем случае для этого в принципе достаточно не закрывая файл, заполнить его байтами с нулевым значением (или любым другим, но не увеличивая и не уменьшая размер файла), записать это на диск (закрыв файл), а потом уже его уничтожать. Правда, в Windows стопроцентной гарантии, что он запишется в точности на то же место, я дать не могу, поэтому лучше в таких случаях применять все же "официальные" программы, которые, кстати, уничтожают следы исходника не только в той области диска, где он хранился, но и SWAP-файле Windows, если они там остались.

Что касается генерации случайных ключей, то вот один из способов. I Указывать реализацию полностью я не буду, так как она проста. Генератор псевдослучайных чисел в Delphi (и не только в Delphi) устроен следующим образом: через переменную RandSeea задается начальное число генератора (но умолчанию оно равно 0). Тогда функция Random при последовательном обращении к ней всегда будет возвращать один и гот же набор чисел, независимо от того, в какой программе и когда мы ее используем. Отсюда и способ- вы устанавливаете в программе такой генератор и на его основе генерируете ключ, например. вот так можно сгенерировать случайный 16-байтный (128-битный) набор символов, который будет зависеть только от величины начального смещения генератора init:

init:integer; st:string;

st:=”;

RandSeed:=init; {начальное смещение} while length(st)<16 do begin xb:=Random(255); if xb>31 then st:=st+chr(xb); end;

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

Хочу заметить, чтобы не затемнять суть дела, ранее в программе я использовал традиционное побайтное чтение из дискового файла. Резко ускорить процедуру можно при использовании одного из механизмов предварительного чтения файла в память- file mapping, как в главе 14, потокового чтения или любого другого способа организации динамических массивов в памяти (см. главу 21). В примере с использованием стеганографии, к которому мы сейчас приступим, частично положение будет исправлено.

Поточный шифр выполняет операции над битами или символами (например 8-, 16- или 32-битовыми). Поточный шифр преобразует один и тот же символ открытого текста в разные символы шифртекста, например в зависимости от того, сколько и каких символов было обработано ранее.
Xor-шифрование
Во многих поточных шифрах зашифровывание производится следующим образом. Генератор псевдослучайных чисел выдает последовательность битов (гамму). Эта гамма накладывается на открытый текст с помощью побитовой операции XOR. В результате получается шифртекст. Для расшифровывания необходимо выполнить в точности ту же процедуру, только наложить гамму, полученную с использованием идентичного генератора с точно таким же начальным состоянием, на шифртекст.
Рассмотрим идею этого наипростейшего метода. Как известно из булевой алгебры, операция логического сложения «⊕» по модулю 2 (или логического исключающего ИЛИ – XOR, eXclusive OR) имеет следующую семантику:

Таблица истинности для XOR:

x i ⊕ y i

x = 10011 101

y = 01001 100

z = 11010 001

То есть, операция 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 предложений) с помощью случайного ключа такой же длины, то такое сообщение очень сложно расшифровать. Еще более высоких результатов по надежности можно достичь, если перед шифрованием произвести, например, сжатие текста каким-либо архиватором. Плюс к тому же, если сообщение имеет малую длину, можно добавить в начало и конец сообщения случайные последовательности символов.
Таким образом, стойкость алгоритма зависит исключительно от характеристик гаммы, выдаваемой генератором. Если гамма состоит из одних нулей (вырожденный случай), то данные при шифровании вообще не изменяются. Если гамма имеет короткий период (например 32 бита), то шифрование сводится к операции XOR с 32-битовой константой. Если же гамма представляет собой случайный набор битов, не подчиняющийся никакой закономерности, получается аналог одноразового шифровального блокнота, который обеспечивает абсолютную защиту. Разумеется, детерминированный алгоритм, используемый в генераторе гаммы, не может выдавать истинно случайную последовательность. Если последовательность не удастся повторить, то не удастся и расшифровать сообщение.
Если два сообщения были зашифрованы с использованием одной и той же гаммы и для одного из сообщений (более длинного) удалось каким-нибудь образом получить открытый текст, то легко получить открытый текст и для другого сообщения. Применив операцию XOR К открытому тексту и шифртексту первого сообщения, мы получим фрагмент гаммы. А наложив гамму на шифртекст второго сообщения, мы получим его открытый текст. Именно поэтому нельзя допускать, чтобы одна и та же гамма использовалась при шифровании двух разных потоков или сообщений.
Если гамма генерируется независимо от содержимого сообщения, то такой потоковый алгоритм называется синхронным. Как правило, в синхронных потоковых шифрах ключ шифрования используется для установки начального внутреннего состояния генератора гаммы.

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

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

Немного расскажу как вообще работает XOR :

XOR - это побитовое сложение по модулю (с инвертированием при переполнении), например, 1+1=0 т.к. 1 - максимальное значение.
Все варианты:
0+0=0
0+1=1
1+1=0

Уникальность сложения по модулю состоит в его обратимости! Т.е. если придумать некоторое слово-код (назовем его гаммой) и выполнить XOR 2 раза к открытому тексту - то получим тот же открытый текст.

Пример работы XOR

Допустим, у нас есть открытый текст - "denik.od "
Придумаем для него гамму: "12345678 " (гамма должна быть равной длине текста, т.к. мы весь текст хотим зашифровать)

Конкретный пример рассмотрим на первых 2-х байтах "de " (представим их в двоичной системе):

Для расшифровки, просто применим XOR еще раз:

В результате мы получили наши первые 2 байта (de ). Точно так же делается со всем текстом.

Все остальные усложнения уже заложены в методах генерации этой самой гаммы. Есть много способов ее генерации, но в основу своего способа, я заложил функцию sha1 (создание HEX хеша).

Логика проста, мы составляем гамму длиной в кодируемый текст примерно так:
$gamma .= sha1($passw . $gamma );
Полный пример для PHP:
function strcode($str , $passw ="" ) { $salt = "Dn8*#2n!9j" ; $len = strlen($str ); $gamma = "" ; $n = $len >100 ? 8 : 2 ; while (strlen($gamma )<$len ) { $gamma .= substr(pack("H*" , sha1($passw .$gamma .$salt )), 0 , $n ); } return $str ^$gamma ; }