Мир ПК, #05/2001
Постоянный адрес статьи: http://www.osp.ru/pcworld/2001/05/048.htm
Криптозащита текстовых файлов
Василий Текин
15.05.2001
Слово за слово — это для человека, а вот текстовый процессор оперирует
только строками, и криптографические преобразования не должны нарушать
работу этого механизма.
Текст по-прежнему выступает основным средством передачи информации
и представляет собой набор абзацев, состоящих из строк. На работу
со строками ориентированы все без исключения текстовые процессоры
турбо-сред компиляторов, а также большинство других текстовых процессоров,
кроме Microsoft Word. Кстати, удобство применения последнего представляется
спорным, ведь никто не ездит по собственной квартире на автомобиле...
Однако почему-то используют этот явно избыточный редактор вместо простых
средств обработки текстов и, хуже того, требуют того же от других.
Большинство языков программирования предоставляют специалисту готовые
средства для работы со строками переменной длины. Традиционно младший
байт внутреннего представления такой строки содержит ее текущую длину,
далее следуют символы строки от первого до последнего. Максимальная
длина строки в таком представлении равна 255 символам. Иногда на описание
текущей длины строки отводится два байта (например, в Delphi), тогда
максимальная длина строки составляет 65 534 символа. В функциях DOS
и программах, написанных на Си и Си++, широко используются также ASCIIZ-строки
теоретически неограниченной длины. Однако большинство текстовых редакторов,
включая turbo-среды самих этих компиляторов, их не используют, отдавая
предпочтение традиционному представлению.
Текстовый файл является последовательностью строк из символов с кодами
20h..FFh длиной от 0 до 255 каждая, разделенную управляющими символами
CR/LF=0Dh/0Ah (возврат каретки/перевод строки). Символы с кодами 00h..1Fh,
включая CR/LF, считаются управляющими и используются в текстах для
специальных целей. Ориентированные на традиционное представление строк
языки программирования высокого уровня, такие как Бейсик и Паскаль,
содержат автоматические средства ввода-вывода для вставки (при записи)
и удаления (при чтении) пар символов CR/LF, разделяющих строки текстового
файла. Для файла, подвергнутого криптографическим преобразованиям,
затрагивающим также разделители строк CR/LF, применение автоматических
средств строкового ввода-вывода становится невозможным.
Автоматические средства разблокирования строк реагируют практически
только на символ возврата каретки CR (код 13h) и перестают работать
правильно, если этот символ оказывается частью строки. Нарушение работы
механизма блокирования/разблокирования связано в данном случае с отличием
внешнего (в файле) и внутреннего (в памяти) представления строк текста.
В этом смысле гораздо удобнее ASCIIZ-строки, разделителем которых
служит символ с кодом 0.
Чтобы использовать традиционные средства ввода-вывода для работы
и с зашифрованным текстовым файлом, необходимо сохранить его строковую
структуру. Иначе говоря, криптографические преобразования не должны
мешать работе механизма блокирования/разблокирования строк. Последнее
условие выполняется, если шифрующие механизмы не порождают символов
CR, разрезающих строку на части при ее записи на диск или выводе на
экран. Конечно, подобное ограничение снижает криптостойкость шифрованных
текстов, но другого выбора нет.
Вначале необходимо уяснить роль управляющих символов системы для
работы с текстовыми файлами. Начать естественнее с DOS, воспользовавшись,
например, программой, приведенной в листинге 1.
Работа этой программы показывает, что из управляющих символов, помимо
упомянутых CR/LF, специальным образом интерпретируются еще символы
звонка BEL (код 07h), <Backspace> BS (код 08h) и горизонтальной
табуляции HT (код 09h), а также маркер конца текста ^Z (код 1Ah),
действие которого проявляется при выводе на экран с помощью команды
TYPE. Остальные управляющие символы в текстовых файлах DOS следует
считать обычными, по крайней мере до тех пор, пока эти файлы не выводятся
на печать.
Криптографические преобразования строк сводятся к перестановкам (перемещениям),
заменам (подстановкам) символов в строке или комбинациям обоих методов.
Поскольку при перестановках коды символов не меняются, то для шифрования
текстовых файлов в большинстве случаев их можно использовать без всяких
ограничений. Пример криптозащиты с помощью перестановок показан в
листинге 2.
Здесь таблица перестановок CryptTab (играющая роль гаммы шифра) создается
случайным образом при каждом вызове программы. Номер элемента I и
соответствующее значение CryptTab [I] указывают положение в строке
переставляемых элементов. Шифрование и дешифрирование отличаются направлением
перебора символов строки. Программа выводит четыре текстовые строки
(каждую своим цветом): исходную (желтый), из текстового файла (зеленый),
шифровку исходной (циан) и результат ее расшифровки (белый). Обратите
внимание на действие преднамеренно введенного управляющего символа
перевода строки.
Криптозащиту с помощью замен рассмотрим на примере шифра Гая Юлия
Цезаря [1, с. 48], описываемого преобразованиями, соответственно прямым:
X = Y + (N – Shift) (mod N)
и обратным:
Y = X + Shift, (mod N)
где X и Y — позиция исходного и кодированного символа в N-символьном
алфавите; <Shift> — сдвиг 1,2...N-1, не зависящий от номера
позиции символа в строке. И взятие по (mod N) напоминает, что соответствующее
значение берется по модулю N числа символов в алфавите. Заметим, что
всегда
Y = Y + N. (mod N)
К сожалению, напрямую подобное преобразование неприменимо из-за несовпадения
способа нумерации строчных символов в алфавите с их кодами в таблице
ASCII. Однако преобразованием можно пользоваться, если положение в
алфавите символа C с кодом Ord (C) из диапазона 20h..FFh считать равным:
X = Ord (C) – 32.
Число символов в таком алфавите (N) равно 224. Для фиксированного
значения сдвига <Shift> программа шифрования/дешифрирования
может быть построена, как показано в листинге 3.
По сути дела, сдвиг и порождает фиксированную таблицу соответствия
между символами исходного и зашифрованного сообщений. Всего таких
таблиц, т. е. способов расшифровки, для N-символьного алфавита может
быть ровно N. Причем каждая таблица имеет простое устройство, и все
они могут быть проверены даже вручную.
Усиление криптостойкости шифра Цезаря достигается в том случае, если
считать сдвиги зависящими от положения шифруемого символа в строке.
Тогда каждому положению символа соответствует своя шифровальная таблица.
Число различных таблиц по-прежнему равно N, однако для расшифровки
уже необходимо знать порядок следования таблиц. Последнее и обусловливает
повышение надежности шифра. При этом достаточно хранить только таблицу
сдвигов, выполняющую функцию гаммы шифра, а сами таблицы преобразований
символов реконструировать по мере надобности, используя приведенные
выше формулы. Способ реализации такого подхода показан в листинге 4.
Для заполнения таблицы сдвигов в этой программе используется встроенный
в Turbo Pascal 3.xx высококачественный датчик случайных чисел. Исследования
показывают, что начальное состояние такого датчика определяется 4-байтовым
числом, что в результате дает всего 4 294 967 296 (232) различных
способов шифрования. Однако это число можно увеличить, используя для
создания гаммы шифра два или более подобных датчиков и комбинируя
порождаемые ими случайные последовательности.
К сожалению, Turbo Pascal 3.xx не предоставляет документированных
способов управления встроенным в него датчиком случайных чисел. Можно,
конечно, разобраться, как это делается, или просто сочинить собственный
датчик (один или несколько), пусть даже и худшего качества. Пример
такого датчика, основанного на рекомендациях Д. Кнута [2, с. 261—267],
представлен в листинге 5.
Для приведения значения Y, вырабатываемого этим генератором, к заданному
диапазону 0..N-1 (N>0) можно воспользоваться следующей формулой:
Z := Y ( mod N);
if Z < 0 then Z := Z + N.
Вместо приведения примеров применения подобных генераторов рассмотрим
прямой способ использования пароля для шифрования по Цезарю. Текст
программы приведен в листинге 6.
Достаточно длинный и не смысловой пароль способен создать уже значительные
трудности при попытке взлома, если только злоумышленник не раздобудет
фрагмент исходного текста, по которому легко восстановить весь пароль
и расшифровать текст.
В программах, приведенных в листингах 3, 4 и 6, предусматривался
обход управляющих символов с кодами 00h..1Fh. Если из обработки надо
исключить только некоторые символы, то перед выполнением криптографических
преобразований их можно просто переместить в конец алфавита, а затем
вернуть на свое место.
Криптографические преобразования, продемонстрированные в листинге 7,
затрагивают все символы строки за исключением символов перевода строки
CR (код 0Dh), возврата каретки CR (код 0Ah), горизонтальной табуляции
HT (код 09h), <Backspace> BS (код 08h), звонка BEL (код 07h)
и, как наследство проклятого прошлого, ^Z — маркера конца текста (с
кодом 1Ah). Эти символы в исходном и кодированном текстах остаются
на своих местах. Сам алгоритм шифрования не отличается от использованного
в листинге
4.
Аналогичным образом решается и задача преобразований только части
символов алфавита с сохранением остальных на своих местах.
Мы рассмотрели применение лишь простейшего способа шифрования текстов
Гая Юлия Цезаря на основе перестановок и циклических замен. Надежность
каждого из подобных шифров невысока. В то же время их последовательное
и многократное применение может повысить криптостойкость шифра. Однако
использование одних лишь перестановок или только замен не повышает
устойчивости шифра ко взлому и даже способно привести к его вырождению
[1, с.126]. Комбинация перестановок и подстановок гораздо устойчивее,
и применяется в профессиональных системах шифрования.
При создании реальных криптосистем для работы с текстовыми файлами
пригодны любые труднообратимые преобразования, отображающие множество
[0..N-1] из N чисел в себя. Очень удобной представляется шифровальная
схема немецкой криптографической машины «Энигма» («Загадка») инженера
Артура Кирха [1, с. 69—75, 141—145], не устаревшая со времен Второй
мировой войны. Ее электронная модель с большим числом шифровальных
колес способна и сегодня нагнать тоску на криптоаналитиков из ФАПСИ.
В заключение заметим, что функция построчного шифрования успешно
используется в многофункциональном и компактном (благодаря архиватору
PKLITE) текстовом процессоре «Слово и Дело» («W&D») А. Е. Гутникова.
К сожалению, автор не раскрывает алгоритм, ограничиваясь лишь заявлением
о его криптостойкости. Однако, судя по скорости работы, используемый
метод шифрования не очень сложен.
Литература
- Жельников В., Криптография от папируса до компьютера.
М.: ABF, 1996.
- Форсайт Дж., Малькольм М., Моулер К. Машинные
методы математических вычислений /Пер. с англ. Х. Д. Икрамова. М.:
Мир, 1980.
ОБ АВТОРЕ
Василий Текин — инженер-программист городской клинической
больницы № 23 г. Москвы. С ним можно связаться по телефону: (095)
915-71-83.
Листинг 1
program DemoTest_1;
(***********************************)
(*Программа демонстрирует использование управляющих символов.*)
(* #07-^G - звонок (BEL); *)
(* #08-^H - <Backspace> (BS); *)
(* #10-^J - перевод строки (LF); *)
(* #13-^M - возврат каретки (CR). *)
(***********************************)
const
CR = #$0D;
LF = #$0A;
TempName = '$$$$$$$$.$$$';
type
StringType = string [80];
RegPack = record
case boolean of
False : (AX,BX,CX,DX,BP,SI,DI,DS,ES,Flags : integer);
True : (AL,AH,BL,BH,CL,CH,DL,DH : byte)
end;
var
C : char;
F : text;
L : StringType;
(*--------------------------------------*)
procedure PutLine (Line : StringType);
(**********************)
(* Печать с задержкой *)
(**********************)
const
Time = 150;
var
I : byte;
Regs : RegPack;
begin
for I := 1 to Length (Line) do begin
Regs.AH := $02; (* печать символа *)
Regs.DL := Ord (Line [I]);
MsDos (Regs);
Delay (Time)
end;
WriteLn;
Exit
end; (* PutLine *)
(*--------------------------------------*)
begin
TextBackGround (Black);
TextColor (LightGray);
ClrScr;
for C := #00 to #31 do begin
Str (Ord (C) : 3, L);
L := L + ' ->' + C + '<-';
if C > #15 then GotoXY (40, WhereY);
PutLine (L);
if C = #15 then GotoXY (1, 1)
end;
GotoXY (1, 18);
Assign (F, TempName);
Rewrite (F);
WriteLn (F, 'Разорванная' + CR + LF + 'строка');
WriteLn (F, 'Разорванная' + LF + CR + 'строка');
WriteLn (F, 'Разорванная' + CR + 'строка');
Close (F);
Reset (F);
while not Eof (F) do begin
ReadLn (F, L);
PutLine (L)
end;
Close (F);
Erase (F);
Halt
end. (* DemoTest_1 *)
Вернуться к
статье
Листинг 2
program CryptDemo_2;
(*********************************)
(*Шифрование строки текста случайной перестановкой символов.*)
(* Turbo Pascal 3.xx *)
(*********************************)
const
TestTxt1 = 'Мама мыла Машу мылом. Маша мыло не любила. '#10;
TestTxt2 = 'Шифрование перестановкой символов.';
FileName = 'DEMO.TXT';
var
I : byte;
C : char;
Line : string [$FF];
CryptTab : array [1..255] of byte;
F : text;
begin
TextBackGround (Black);
(* шифруемый текст *)
Line := TestTxt1 + TestTxt2;
TextColor (Yellow);
WriteLn (Line);
(* ввод-вывод строки через файл *)
TextColor (LightGreen);
Assign (F, FileName);
Rewrite (F);
WriteLn (F, Line);
Close (F);
Reset (F);
ReadLn (F, Line);
Close (F);
Erase (F);
WriteLn (Line);
(* восстановление строки *)
Line := TestTxt1 + TestTxt2;
(* рандомизация ключа шифрования *)
Randomize;
(* подготовка таблицы перестановок *)
for I := 1 to Length (Line) do
CryptTab [I] := Succ (Random (Length (Line)));
(* шифрование перестановкой символов *)
for I := 1 to Length (Line) do begin
C := Line [I];
Line [I] := Line [CryptTab [I]];
Line [CryptTab [I]] := C
end;
TextColor (LightCyan);
WriteLn (Line);
(* дешифрирование перестановки символов *)
for I := Length (Line) downto 1 do begin
C := Line [I];
Line [I] := Line [CryptTab [I]];
Line [CryptTab [I]] := C
end;
TextColor (White);
Write (Line);
TextColor (LightGray);
Writeln;
Halt
end. (* CryptDemo_2 *)
Вернуться к
статье
Листинг 3
program CryptDemo_3;
(****************************)
(*Шифрование строки текста заменой символов 32..255.*)
(* Turbo Pascal 3.xx *)
(****************************)
const
TestTxt1 = 'Мама мыла Машу мылом. Маша мыло не любила. '#10;
TestTxt2 = 'Шифрование заменой символов.';
var
I : byte;
C : char;
Line : string [$FF];
Shift : byte;
begin
TextBackGround (Black);
(* шифруемый текст *)
Line := TestTxt1 + TestTxt2;
TextColor (Yellow);
WriteLn (Line);
(* рандомизация ключа шифрования *)
Randomize;
Shift := 1 + Random (223);
(* шифрование заменой символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then
Line [I] := Chr ((Ord (Line [I]) + 192 - Shift) mod 224 + 32);
TextColor (LightCyan);
WriteLn (Line);
(* дешифрирование замены символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then
Line [I] := Chr ((Ord (Line [I]) - 32 + Shift) mod 224 + 32);
TextColor (White);
Write (Line);
TextColor (LightGray);
WriteLn;
Halt
end. (* CryptDemo_3 *)
Вернуться к
статье
Листинг 4
program CryptDemo_4;
(**************************************)
(*Шифрование строк текста случайными сдвигами символов с кодами 32..255.*)
(* Turbo Pascal 3.xx *)
(**************************************)
const
TestTxt1 = 'Мама мыла Машу мылом. Маша мыло не любила. '#10;
TestTxt2 = 'Шифрование заменой символов.';
var
I : byte;
C : char;
Line : string [$FF];
ShiftTab : array [1..255] of byte;
begin
TextBackGround (Black);
(* шифруемый текст *)
Line := TestTxt1 + TestTxt2;
TextColor (Yellow);
WriteLn (Line);
(* рандомизация ключа шифрования *)
Randomize;
(* подготовка таблицы сдвигов *)
for I := 1 to Length (Line) do
ShiftTab [I] := Random (224);
(* шифрование заменой символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then
Line [I] := Chr ((Ord (Line [I]) + 192 -
ShiftTab [I]) mod 224 + 32);
TextColor (LightCyan);
WriteLn (Line);
(* дешифрирование замены символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then
Line [I] := Chr ((Ord (Line [I]) - 32 + ShiftTab [I])
mod 224 + 32);
TextColor (White);
Write (Line);
TextColor (LightGray);
WriteLn;
Halt
end. (* CryptDemo_4 *)
Вернуться к
статье
Листинг 5
function RndWord (var Y : integer) : integer;
(********************************************)
(*Конгруэнтный генератор случайного слова.*)
(*Перед первым вызовом надо присвоить переменной Y целое
и в дальнейшем его не изменять.*)
(********************************************)
begin
Y := 12869 * Y + 6925;
RndWord := Y;
Exit
end; (* RndWord *)
Вернуться к
статье
Листинг 6
program CryptDemo_6;
(***************************************)
(* Шифрование строк текста сдвигами по паролю символов
с кодами 32..255.*)
(* Turbo Pascal 3.xx *)
(***************************************)
const
TestTxt1 = 'Мама мыла Машу мылом. Маша мыло не любила. '#10;
TestTxt2 = 'Шифрование заменой символов.';
PassWord : array [0..12] of char = 'Сов. секретно';
var
I, J, K : byte;
Line : string [$FF];
begin
TextBackGround (Black);
(* шифруемый текст *)
Line := TestTxt1 + TestTxt2;
TextColor (Yellow);
WriteLn (Line);
(* шифрование заменой символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then begin
J := Ord (Line [I]) - 32;
K := Ord (PassWord [I mod 13]) - 32;
Line [I] := Chr ((J + 224 - K) mod 224 + 32)
end;
TextColor (LightCyan);
WriteLn (Line);
(* дешифрирование замены символов *)
for I := 1 to Length (Line) do
if Line [I] >= #32 then begin
J := Ord (Line [I]) - 32;
K := Ord (PassWord [I mod 13]) - 32;
Line [I] := Chr ((J + K) mod 224 + 32)
end;
TextColor (White);
Write (Line);
TextColor (LightGray);
WriteLn;
Halt
end. (* CryptDemo_6 *)
Вернуться к
статье
Листинг 7
program CryptDemo_7;
(****************************)
(*Шифрование строки текста заменой части символов.*)
(* Turbo Pascal 3.xx *)
(****************************)
const
TestTxt1 = 'Мама мыла Машу мылом. Маша мыло не любила. '#10;
TestTxt2 = 'Шифрование заменой символов.';
var
I : byte;
C : char;
Line : string [$FF];
ShiftTab : array [1..255] of byte;
(*--------------------------------------*)
procedure ChangeCharNum (var C : char);
(************************)
(* Смена номера символа *)
(************************)
begin
case C of
#007..#010: C := Chr (Ord (C) + 243);
#013 : C := #254;
#026 : C := #255;
#250..#253: C := Chr (Ord (C) - 243);
#254 : C := #013;
#255 : C := #026
end;
Exit
end; (* ChangeCharNum *)
(*--------------------------------------*)
begin
TextBackGround (Black);
(* шифруемый текст *)
Line := TestTxt1 + TestTxt2;
TextColor (Yellow);
WriteLn (Line);
(* рандомизация ключа шифрования *)
Randomize;
(* подготовка таблицы сдвигов *)
for I := 1 to Length (Line) do
ShiftTab [I] := Random (250);
(* шифрование заменой символов *)
for I := 1 to Length (Line) do begin
ChangeCharNum (Line [I]);
if Line [I] < #250 then
Line [I] := Chr ((Ord (Line [I]) + 250 - ShiftTab [I])
mod 250);
ChangeCharNum (Line [I])
end;
TextColor (LightCyan);
WriteLn (Line);
(* дешифрирование замены символов *)
for I := 1 to Length (Line) do begin
ChangeCharNum (Line [I]);
if Line [I] < #250 then
Line [I] := Chr ((Ord (Line [I]) + ShiftTab [I]) mod 250);
ChangeCharNum (Line [I])
end;
TextColor (White);
Write (Line);
TextColor (LightGray);
WriteLn;
Halt
end. (* CryptDemo_7 *)
Мир ПК, #05/2001
Постоянный адрес статьи:
http://www.osp.ru/pcworld/2001/05/048.htm
