ШИФРОВАНИЕ И СЖАТИЕ ДАННЫХ

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

КРАТКАЯ ИСТОРИЯ КРИПТОГРАФИИ

Хотя никто не знает, когда появилась тайнопись, но глиняная табличка, сделанная приблизительно 1500 лет до нашей эры, содержит один из самых ранних ее примеров. Она содержит закодированную формулу изготовления глазури для покрытия сосудов. Греки применяли коды по крайней мере с 475 года до нашей эры, а высшие слои в Риме использовали простые шифры в период царствования Юлия Цезаря. В начале нашей эры интерес к криптографии (также, как и к другим интеллектуальным занятиям) упал; единственными, кто иногда применял ее, были монахи. С наступлением эпохи возрождения искусство криптографии стало расцветать. Во времена Луи ХIV во Франции для правительственных сообщений использовалось шифрование, основанное на 587 произвольно набранных ключах.
В ХIX веке два фактора способствовали развитию криптографии. Первым фактором были истории Эдгара Алана По такие, как «Золотой жук», в которых фигурируют закодированные сообщения и которые волновали воображение многих читателей. Вторым фактором явилось изобретение телеграфа и азбуки Морзе. Азбука Морзе была первым двоичным представлением (точка и тире) алфавита, которое получило широкое распространение.
В первую мировую войну в ряде стран были разработаны «шифровальные машины», которые позволяют легко кодировать и декодировать текст, используя сложный шифр. С этого момента история криптография становится историей дешифрации кодов.
До того, как для кодирования и декодирования стали использоваться механические устройства, сложные шифры применялись не часто, так как требовали много времени и сил для кодирования и декодирования. Поэтому большинство кодов можно было расшифровать за относительно короткий промежуток времени. Однако, дешифрация стала гораздо более сложной, когда стали применяться шифровальные машины. Хотя современные компьютеры могли бы расшифровать эти коды относительно легко, но даже компьютеры не могут приблизиться к выдающемуся таланту Герберта Ядлея, который до сих пор считается самым выдающимся дешифровальщиком всех времен. Он расшифровал в 1915 году в свое свободное время дипломатический код США, а затем в 1922 году дипломатический код Японии, хотя он даже не знал японского языка.
Во время второй мировой войны главный метод дешифровки кодов основывался на краже неприятельской дешифровальной машины, таким образом можно было избежать утомительного процесса расшифровки кодов. Фактически обладание службой Аллеса германской шифровальной машиной, что было не известно Германии, способствовало в определенной степени исходу войны. С приходом компьютеров, особенно многопользовательских, необходимость в засекречивании информации и в недешифруемых кодах стала еще более острой. Необходимо не только защищать файлы, но и управлять доступом собственно к компьютеру. Было разработано множество методов шифрования файлов данных и алгоритм DES (Стандарт шифрования данных), принятый национальным бюро по стандартам, считается недоступным для расшифровки. Однако, DES труден для реализации и подходит не для всех случаев.

ТИПЫ ШИФРОВ

Большинство традиционных методов кодирования относится к одному из двух основных типов: замена и перестановка. В шифрах замены один символ заменяется другим, но порядок следования символов в сообщении не изменяется. В шифрах перестановки в соответствии с некоторым правилом перемешиваются символы сообщения. Эти типы кодов могут быть любого уровня сложности и даже могут быть применены совместно. Цифровые компьютеры привнесли третий основной тип шифрования, называемый битовой обработкой, в котором по некоторому алгоритму изменяется машинное представление данных.
Все три метода могут использовать ключ. Ключ - это строка символов, необходимая для дешифрования сообщения. Не путайте ключ с методом. Знание ключа не дает возможности дешифровать сообщение, необходимое также знать алгоритм шифрования. С другой стороны знание метода шифрования без ключа также не дает такой возможности; необходимо знать и метод и ключ. В данной главе описываются машинные методы, которые основаны на базовых методах кодирования текстовых файлов. Будет продемонстрирован ряд коротких программ, которые осуществляют кодирование и декодирование текстовых файлов. За одним исключением все эти программы осуществляют выполнение функций как кодирования, так и декодирования: функция декодирования всегда является обратной по отношению к кодированию, используемому для получения шифрованного текста.

ШИФРЫ ЗАМЕНЫ

Один из простейших шифров замены представляет собой смещенный на определенное число позиций алфавит. Например, если каждая буква была смещена на три позиции, то алфавит

abcdefghijklmnopqrstuvwxyz

превращается в

defghijklmnopqrstuvwxyzabc

Отметим, что буквы abc выдвинулись и добавились в конец. Для того, чтобы закодировать сообщение, используя данный метод, вы просто подставляете символы сдвинутого алфавита вместо реальных символов. Например, сообщение

meet me at sunset

превращается в

phhw ph dw vxqvhw

Программа, показанная далее, позволяет зашифровать любое текстовое сообщение, используя любое по вашему выбору смещение: шифр простой замены.

Program subst;
 
Type 
  str80 = string[80];
 
Var 
  inf, outf: str80;
  start: integer;
  ch: char;
 
Procedure code (inf, outf: str80; start: integer);
Var 
  infile, outfile: file Of char;
  ch: char;
  t: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := upcase(ch);
    If (ch>='A') And (ch<='Z') Then
      Begin
        t := ord(ch)+start;
        If t>ord('Z') Then t := t-26;
        ch := chr(t);
      End;
    Write(outfile, ch);
  End;
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80; start: integer);
 
Var 
  infile, outfile: file Of char;
  ch: char;
  t: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    read(infile, ch);
    ch := upcase(ch);
    If (ch>='A') And (ch<='Z') Then
      Begin
        t := ord(ch)-start;
        If t<ord('A') Then t := t+26;
        ch := chr(t);
      End;
    Write(outfile, ch);
  End;
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
Begin
  Write('введите имя входного файла : ');
  ReadLn(inf);
  Write('введите имя выходного файла : ');
  ReadLn(outf);
  Write('начальная позиция (1-26): ');
  ReadLn(start);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf, start)
  Else If upcase(ch)='D' Then decode(inf,outf,start);
End.

Хотя шифр замены, основанный на постоянном смещении, одурачит ученика младших классов, он не подходит для большинства применений из-за того, что его слишком легко расколоть. Существует только 26 возможных смещений и легко за довольно короткое время перебрать их все. Можно улучшить шифр замены, использовав перемешанный алфавит вместо просто смещенного.
Вторая слабость шифра простой замены состоит в том, что он сохраняет пробелы между словами, что еще упрощает его дешифрацию. Поэтому следующим улучшением могло бы быть кодирование пробела (кроме того, следует кодировать и другие знаки препинания). Например, вы могли бы отобразить алфавит

abcdefghijklmnopqrstuvwxyz<пробел>

в произвольную строку, которая содержит все буквы алфавита, например

qazwsxedcrfvtgbyhnujm ikolp

Вы можете пожелать узнать, значительно ли улучшается стойкость шифрования при использовании перемешанного варианта алфавита по сравнению с вариантом простого смещения. Ответ: да. Дело в том, что существует 26! вариантов перестановок алфавита, а с пробелом число вариантов достигает 27!. Факториал числа представляет собой произведение всех чисел, не превосходящих данного. Например, 6! равно 6х5х4х3х2х1, то есть 720. Следовательно 26! очень большое число.

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

meet me at sunset

используя программу реализации улучшенного шифра замены, получится строка

tssjptspqjpumgusj

которую значительно труднее дешифровать. Улучшенный шифр замены, который использует перемешанный алфавит

Program subs1;
 
Type 
  str80 = string[80];
 
Var 
  inf, outf: str80;
  alphabet,sub: str80;
  ch: char;
 
{данная функция возвращает индекс в алфавите замены }
 
Function find(alphabet: str80; ch: char): integer;
 
Var 
  t: integer;
Begin
  find := -1; { код ошибки  }
  For t := 1 To 27 Do
    If ch=alphabet[t] Then find := t;
End;
 
{данная функция возвращает TRUE истина, если с - это буква алфавита }
 
Function isalpha(ch: char): boolean;
Begin
  isalpha := (upcase(ch)>='A') And (upcase(ch)<='Z');
End;
 
Procedure code(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  ch: char;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := upcase(ch);
    If isalpha(ch) Or (ch=' ') Then
      Begin
        ch := sub[find(alphabet, ch)]; { найти замену  }
      End;
    Write(outfile, ch);
  End;
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  ch: char;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := upcase(ch);
    If isalpha(ch) Or (ch=' ') Then ch := alphabet[find(sub,ch)];
    {замена снова на реальный алфавит }
    Write(outfile, ch);
  End;
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
 
Begin
  alphabet := 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ';
  sub := 'CAZWSXEDCRFVTGBYHNUJM IKOLP';
  Write('введите имя входного файла : ');
  ReadLn(inf);
  Write('введите имя выходного файла : ');
  ReadLn(outf);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf)
  Else If upcase(ch)='D' Then decode(inf, outf);
End.

Хотя дешифрация рассматривается далее в этой главе, вам следует знать, что даже такой улучшенный код замены может быть сравнительно легко дешифрован, используя частотные таблицы английского языка, в которых дана статистическая информация по использованию каждой буквы алфавита. Как вы можете легко заметить, глядя на зашифрованное сообщение, «s» почти наверняка является буквой «е», наиболее часто встречающейся буквой английского алфавита, а «р» - пробелом. Оставшаяся часть сообщения может быть дешифрована быстро и легко.
Чем больше шифрованное сообщение, тем легче расшифровать его с помощью частотных таблиц. Для того, чтобы осложнить успех дешифровальщика, применяющего частотные таблицы, вы можете использовать шифр множественной замены. Одна и та же буква в исходном сообщении не обязательно преобразуется в одну букву шифрованного текста. Один из возможных методов реализации шифра множественной замены состоит в добавлении второго перемешанного алфавита и переключении с одного алфавита на другой при встрече в тексте пробела. Пусть вторым перемешанным алфавитом будет следующий:

poi uytrewqasdfghjklmnbvcxz

Тогда, используя данный подход, сообщение

meet me at sunset

будет зашифровано в вид

tssj su qj kmdkul

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

abcdefghijklmnopqrstuvwxyz<пробел>

замена:

qazwsxedcrfvtgbyhnujm ikolp

замена2:

poi uytrewqasdfghjklmnbvcxz

В начале работы программы используется первый алфавит. Это означает, что «meet» кодируется в «tssj». Когда встречается первый пробел происходит переключение на второй алфавит, приводящее к кодированию слова «me» в «su». Следующий пробел заставляет программу использовать снова первый алфавит. Этот процесс продолжается до тех пор, пока не будет закодировано все сообщение.

Шифр множественной замены

Данная программа создает шифр множественной замены:

Program subs3;
 
Type
  str80 = string[80];
 
Var
  inf, outf: str80;
  alphabet, sub, sub2: str80;
  ch: char;
 
{данная функция возвращает индекс в алфавите подстановки }
 
Function find(alphabet: str80; ch: char): integer;
Var
  t: integer;
Begin
  find := -1; { код ошибки  }
  For t:= 1 To 27 Do
    If ch=alphabet[t] Then find := t;
End;
 
{ This function returns TRUE if ch is a letter of the alphabet.}
Function isalpha(ch: char): boolean;
Begin
  isalpha := (upcase(ch)>='A') And (upcase(ch)<='Z');
End;
 
Procedure code(inf, outf: str80);
Var
  infile, outfile: file Of char;
  ch: char;
  change: boolean;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  change := TRUE;
  while not eof(infile) Do
  Begin
    Read(infile,ch);
    ch := upcase(ch);
{ переключение алфавитов при каждом пробеле  }
    If ch=' ' Then change := Not change;
    If isalpha(ch) Then
      Begin
        If change Then
          ch := sub[find(alphabet,ch)]
        Else
          ch := sub2[find(alphabet,ch)];
      End;
    Write(outfile, ch);
  End;
  WriteLn('файл закодирован ');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80);
Var
  infile, outfile: file Of char;
  ch: char;
  change: boolean;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  change := TRUE;
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := upcase(ch);
    If ch=' ' Then change := Not change;
    If isalpha(ch) Then
      Begin
        If change Then
          ch := alphabet[find(sub, ch)] {find substitution}
        Else
          ch := alphabet[find(sub2, ch)]; {second sub}
      End;
    Write(outfile, ch);
  End;
  WriteLn('файл декодирован ');
  close(infile);
  close(outfile);
End;
 
Begin
  alphabet := 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ';
  sub := 'QAZWSXEDCRFVTGBYHNUJM IKOLP'; {алфавит #1}
  sub2 := 'POI UYTREWQASDFGHJKLMNBVCXZ'; {алфавит #2}
  Write('введите имя входного файла : ');
  ReadLn(inf);
  Write('введите имя выходного файла : ');
  ReadLn(outf);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf)
  Else If upcase(ch)='D' Then decode(inf, outf);
End.

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

ШИФРЫ ПЕРЕСТАНОВКИ

Одним из ранних вариантов шифра перестановки был разработан стандартами в 475 году до нашей эры. Он использовал устройство в виде длинной узкой ленты, которая накручивалась на цилиндр и на которой сообщение писалось поперек. Лента затем разматывалась и поставлялась получателю, который имел точно такой же цилиндр. Теоретически возможно прочитать ленту без цилиндра, так как буквы все-таки сохраняют порядок следования. Однако, на практике данный метод остается только возможным, так как необходимо перепробовать большое количество различных размеров цилиндров прежде, чем сообщение начинает вырисовываться.
Вы можете создать машинную версию такого шифра, поместив исходное текстовое сообщение в матрицу одним способом и выведя его другим способом. Для того, чтобы сделать это, для хранения кодируемого сообщения используется одновременная строка, но сообщение записывается в дисковый файл в виде матрицы. В нашем варианте исходный текст, представляющий собой строку длиной 100 байт, записывается на диск, как матрица 5х20. Однако, вы могли бы использовать матрицу любой другой размерности. Так как сообщение помещается в матрицу фиксированного размера, то существует вероятность того, что не все элементы матрицы будут использованы. Это делает необходимым инициализацию матрицы перед помещением в нее исходного текста. На практике лучше инициализировать матрицу произвольными символами, однако, для простоты используется символ »#».
Если вы поместите сообщение

meet me at sunset

в матрицу, она будет выглядеть следующим образом:

m e e t
m e a t
s u n s
e t 
# # # # #

Если вы затем осуществите запись матрицы по столбцам, то сообщение будет выглядеть следующим образом:

mm e...eest...e u...tan... ts

где точки обозначают соответствующее количество символов »#». Для декодирования сообщения заполняются столбцы матрицы. Затем матрица может быть отображена в нормальном порядке. Программа Skytale использует данный метод для кодирования и декодирования сообщений:

шифр skytale

примечание: наибольшее сообщение, которое может быть закодировано, состоит из 100 байт

Program skytale;
 
Type 
  str100 = string[100];
  str80 = string[80];
 
Var 
  inf, outf: str80;
  sky: str100;
  t: integer;
  ch: char;
 
Procedure code(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  t, t2: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  t := 1;
{ считывание текстового файла, как одномерной матрицы }
  while (Not eof(infile)) and (t<=100) Do
  Begin
    Read(infile, sky[t]);
    t := t+1;
  End;
{запись в матрицу размера 5х20}
  For t := 1 To 5 Do
    For t2 := 0 To 19 Do
      Write(outfile, sky[t+(t2*5)]);
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  t, t2: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
{ считывание матрицы размером 5х20  }
  For t := 1 To 5 Do
    For t2 := 0 To 19 Do
      Read(infile, sky[t+(t2*5)]);
{ вывод в качестве строки   }
  For t := 1 To 100 Do
    Write(outfile, sky[t]);
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
 
Begin
{ заполнение символов "#"  }
  For t := 1 To 100 Do
    sky[t] := '#';
  Write('введите имя входного файла: ');
  ReadLn(inf);
  Write('введите имя выходного файла: ');
  ReadLn(outf);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf)
  Else If upcase(ch)='D' Then decode(inf, outf);
End.

шифр перемешивания.

Существуют другие методы получения перемешанных сообщений. Один метод, особенно подходящий для компьютера, использует перестановку букв внутри сообщения с некоторым алгоритмом. Длина сообщения не должна превышать 100 символов. Следующая программа перемешивает буквы:

 
Program transpose;
 
Type 
  str100 = string[100];
  str80 = string[80];
 
Var 
  inf, outf: str80;
  message: str100;
  ch: char;
  t: integer;
 
Procedure code(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  temp: char;
  t, t2: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  t := 1;
  while (Not eof(infile)) and (t<=100) Do
  Begin
    Read(infile, message[t]);
    t := t+1;
  End;
  message[t-1] := '#'; {удаление знака конца файла }
{теперь перемешиваются символы }
  For t2 := 0 To 4 Do
    For t := 1 To 4 Do
      Begin
        temp := message[t+t2*20];
        message[t+t2*20] := message[t+10+t2*20];
        message[t+10+t2*20] := temp;
      End;
{ now write it out }
  For t := 1 To 100 Do
    Write(outfile, message[t]);
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  temp: char;
  t, t2: integer;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  t := 1;
  while (Not eof(infile)) and (t<=100) Do
  Begin
    Read(infile, message[t]);
    t := t+1;
  End;
  message[t-1] := '#'; {удаление знака конца файла }
{теперь перемешиваются символы  }
  For t2 := 0 To 4 Do
    For t := 1 To 4 Do
      Begin
        temp := message[t+t2*20];
        message[t+t2*20] := message[t+10+t2*20];
        message[t+10+t2*20] := temp;
      End;
{теперь осуществляем вывод }
  For t := 1 To 100 Do
    Write(outfile, message[t]);
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
 
Begin
  For t := 1 To 100 Do
    message[t] := '#';
  Write('введите имя входного файла : ');
  ReadLn(inf);
  Write('введите имя выходного файла : ');
  ReadLn(outf);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf)
  Else If upcase(ch)='D' Then decode(inf, outf);
End.

Хотя коды перестановки могут быть эффективными, алгоритмы, если требуется высокий уровень секретности, становятся очень сложными.

ШИФРЫ ПОБИТОВОЙ ОБРАБОТКИ

Цифровые компьютеры положили начало новому методу шифрования, основывающемуся на обработке бит, составляющих символы исходного текста. Хотя побитовая обработка является вариацией шифра замены, концепции, методы и возможности отличаются столь значительно, что он должен рассматриваться, как отдельный вид шифра.
Шифры побитовой обработки хорошо подходят для применения в компьютерах, так как они используют операции, легко выполняемые компьютерами.
В общем случае шифры побитовой обработки применимы только для файлов компьютеров и не могут быть использованы для создания печатной копии, так как побитовая обработка ведет к порождению непечатных знаков. По этой причине предполагается, что любой файл, зашифрованный методами побитовой обработки, будут оставаться компьютерными файлами.
Шифры побитовой обработки преобразуют исходную информацию в шифрограмму, изменяя исходную битовую комбинацию каждого символа с помощью одного или нескольких следующих логических операторов:

AND OR NOT XOR

Турбо Паскаль является одним из лучших языков для реализации шифров побитовой обработки, так как он поддерживает данные операторы для использования над типом данных byte. Когда данный оператор применяется к байтовым переменным, операция осуществляется на байт-байтовой основе, легко выполняя изменения состояний битов в байте.
Простейший и наименее стойкий шифр использует только оператор NOT (напомним, что оператор NOT вызывает инверсию каждого бита в байте: 1 переходит в 0, а 0 в 1). Следовательно, байт, инвертированный дважды, равен исходному. Следующая программа, называемая Complement (дополнение), шифрует любой текстовый файл инвертированием битов внутри каждого символа. Так как Турбо Паскаль строг в отношении типов переменных, в программе следует использовать переменные типа byte (байтовые), а не char (символьные), чтобы можно было применить операторы побитовой обработки.

шифр дополнения до 1

Program complement;
 
Type 
  str80 = string[80];
 
Var 
  inf,outf: str80;
  ch: char;
 
Procedure code(inf, outf: str80);
 
Var 
  infile, outfile: file Of byte;
  ch: byte;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := Not ch;
    Write(outfile, ch);
  End;
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80);
 
Var 
  infile, outfile: file Of byte;
  ch: byte;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := Not ch;
    Write(outfile, ch);
  End;
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  Write('введите имя выходного файла: ');
  ReadLn(outf);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf)
  Else If upcase(ch)='D' Then decode(inf,outf);
End.

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

XOR | 0 | 1
--------------
0 | 0 | 1
--------------
1 | 1 | 0

Результат операции XOR равен TRUE (истина) тогда и только тогда, когда один оператор равен TRUE, а второй - false (ложь). Это дает XOR уникальные свойства: если выполнить операцию XOR над двумя байтами, один из которых называется ключем, а затем взять результат и ключ и снова применить к ним операцию XOR, то в результате получим исходный байт, как показано ниже:

1101 1001
XOR 0101 0011 /ключ/ 
1000 1010
равны
1000 1010
XOR 0101 1001 /ключ/ 
1101 1001

Будучи примененными для кодирования файлов, данный процесс разрешает две проблемы, присущие методу, основанному на операции инвертирования. Во-первых, так как применяется ключ, наличие только программы декодирования не позволяет дешифровать файл; во-вторых, из-за того, что использование ключа делает каждый файл своеобразным, то он будет очевиден тем, кто изучал только вычислительную технику.
Ключ не обязательно должен быть только однобайтовым. Например, вы могли бы использовать несколько символов и применять их последовательно на одном файле. Однако, в приведенной ниже программе для простоты используется однобайтовый ключ.

шифр на основе операции XOR с ключом

Program xor_with_key;
 
Type 
  str80 = string[80];
 
Var 
  inf, outf: str80;
  key: byte;
  ch: char;
 
Procedure code(inf, outf: str80; key: byte);
 
Var 
  infile, outfile: file Of byte;
  ch: byte;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := key xor ch;
    Write(outfile, ch);
  End;
  WriteLn('файл закодирован');
  close(infile);
  close(outfile);
End;
 
Procedure decode(inf, outf: str80; key: byte);
 
Var 
  infile, outfile: file Of byte;
  ch: byte;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := key xor ch;
    Write(outfile, ch);
  End;
  WriteLn('файл декодирован');
  close(infile);
  close(outfile);
End;
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  Write('введите имя выходного файла; ');
  ReadLn(outf);
  Write(' введите односимвольный ключ : ');
  ReadLn(ch);
  key := ord(ch);
  Write('кодировать или декодировать (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then code(inf, outf, key)
  Else If upcase(ch)='D' Then decode(inf, outf, key);
End.

СЖАТИЕ ДАННЫХ

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

Восемь в семь

Большинство современных компьютеров используют размеры байта, которые являются степенью двойки. Заглавные и строчные буквы и знаки пунктуации составляют приблизительно 63 кодов, что требует 6 бит для представления байта (6-битовый байт может принимать значения от 0 до 63). Однако, большинство компьютеров использует 8-битовый байт; таким образом 25% байта тратится зря в текстовых файлах. Следовательно, можно упаковать 4 символа и 3 байта. Единственная проблема состоит в том, что в коде ASCII существует более 63 различных символов. Это означает, что некоторые необходимые символы требуют по крайней мере 7 бит. Можно использовать представление не в коде ASCII, но это нежелательно. Самый простой вариант - это упаковка 8 символов в 7 байт, основывающийся на том факте, что ни буквы, ни знаки пунктуации не используют восьмого бита в байте. Следовательно, вы можете использовать восьмой бит каждого из семи байт для запоминания восьмого символа. Данный метод экономит 12,5% памяти. Однако, многие компьютеры, включая IBM PC, используют весь 8-битовый байт для представления специальных и графических символов. Кроме того, некоторые текстовые процессоры используют восьмой бит для задания команд текстовой обработки. Следовательно, использование данного типа упаковки данных возможно только с файлами типа ASCII, которые не используют восьмого бита. Для демонстрации того, как это происходит, рассмотрим следующие 8 символов, представленные как 8-битовые байты:

   байт 1 0111 0101
   байт 2 0111 1101
   байт 3 0010 0011
   байт 4 0101 0110
   байт 5 0001 0000
   байт 6 0110 1101
   байт 7 0010 1010
   байт 8 0111 1001

Как вы видите, восьмой байт всегда равен 0. Так происходит всегда, кроме случая, когда восьмой бит используется для контроля четности. Самый простой способ сжатия 8 символов в 7 байт состоит в том, чтобы распределить 7 значащих бит байта 1 в семь неиспользуемых восьмых битовых позиций байтов 2-8. Семь оставшихся байт будут выглядеть следующим образом:

   байт 2 1111 1101
   байт 3 1010 0011
   байт 4 1101 0110
   байт 5 0001 0000
   байт 6 1110 1101
   байт 7 0010 1010
   байт 8 1111 1001
   байт 1 - читать вниз

Для восстановления байта 1 вы собираете вместе восьмые биты каждого из 7 байт. Данный метод сжимает любой текстовый файл на 1/8 или на 12,5%. Это весьма существенная экономия. Например, если вы передавали исходный текст вашей любимой программы другу по телефонной линии на большое расстояние, то вы сократите расходы на 12,5% (напомним, что объектный и исполнительные коды программы требуют всех 8 бит).
Следующая программа осуществляет сжатие текстового файла, используя описанный метод: данная программа сжимает 8 байт в 7

Program compress_file;
 
Type 
  str80 = string[80];
 
Var 
  inf, outf: str80;
  ch: char;
  t: integer;
 
Procedure compress(inf, outf: str80);
 
Var 
  infile, outfile: file Of byte;
  ch, ch2: byte;
  done: boolean;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  done := FALSE;
  Repeat
    Read(infile, ch);
    If eof(infile) Then
      done := TRUE
    Else
      Begin
        ch := ch shl 1; { выдвижение свободного бита for t := 0 to 6 do }
        Begin
          If eof(infile) Then
            Begin
              ch2 := 0;
              done := TRUE;
            End
          Else Read(infile, ch2);
          ch2 := ch2 And 127; { сброс старшего бита}
          ch2 := ch2 Or ((ch shl t) And 128); {pack bits}
          Write(outfile, ch2);
        End;
      End;
  Until done;
  WriteLn('file compressed');
  close(infile);
  close(outfile);
End;
 
Procedure decompress(inf, outf: str80);
 
Var 
  infile, outfile: file Of byte;
  ch, ch2: byte;
  s: array[1..7] Of byte;
  done: boolean;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile,outf);
  rewrite(outfile);
  done := FALSE;
  Repeat
    ch := 0;
    For t := 1 To 7 Do
      Begin
        If eof(infile) Then
          done := TRUE
        Else
          Begin
            Read(infile, ch2);
            s[t] := ch2 And 127; { сброс старшего бита }
            ch2 := ch2 And 128; { очистка младших битов }
            ch2 := ch2 shr t;{  распаковка }
            ch := ch Or ch2; { встраивание восьмого байта }
          End;
      End;
    Write(outfile, ch);
    For t := 1 To 7 Do
      Write(outfile, s[t]);
  Until done;
  WriteLn('file decompressed');
  close(infile);
  close(outfile);
End; { decompress }
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  Write('введите имя выходного файла: ');
  ReadLn(outf);
  Write('сжатие или распаковка (C or D): ');
  ReadLn(ch);
  If upcase(ch)='C' Then compress(inf, outf)
  Else If upcase(ch)='D' Then decompress(inf,outf);
End.

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

Шестнадцатибуквенный алфавит

Хотя это не подходит для всех ситуаций, интерес представляет метод сжатия данных, в котором уничтожаются ненужные буквы из слова, то есть слово сокращается. Сжатие данных происходит за счет того, что неиспользуемые символы не запоминаются. Экономия пространства за счет сокращений довольно распространена, например, «Mr» используется вместо «Mister». Вместо применения общепринятых сокращений в описываемом в данном разделе методе осуществляется автоматическое удаление различных букв из сообщения. Для реализации этого необходимы «минимальный алфавит. Минимальным называется такой алфавит, из которого исключены редко используемые буквы и оставлены только те, которые необходимы для составления большинства слов или для избежания неоднозначности. Следовательно, любой символ, который не входит в минимальный алфавит, будет удален из слова, в котором он появился. Предметом выбора является минимальный алфавит. В данном разделе используются 14 наиболее часто встречающихся букв плюс символы пробела и возврата каретки.
Автоматизация процесса сокращения требует, чтобы вы знали, какие буквы в алфавите используются наиболее часто, чтобы можно было составить минимальный алфавит. Теоретически вы могли бы подсчитать буквы в каждом слове словаря; однако, у различных людей словарные смеси отличаются, поэтому частотная диаграмма, построенная только на словах английского языка, не может отражать действительной частоты использования букв. В качестве альтернативы вы можете подсчитать частоты использования букв в данной главе и использовать их в качестве основы для составления вашего минимального алфавита. Для реализации этого вы могли бы использовать следующую простую программу. Данная программа пропускает все знаки пунктуации, исключая точку, запятую и пробел. данная программа подсчитывает число символов каждого типа в файле.

Program countchars;
 
Type 
  str80 = string[80];
 
Var 
  inf: str80;
  t: integer;
  alpha: array[0..25] Of integer;
  space, period, comma: integer;
 
{ данная функция возвращает TRUE, если ch является буквой алфавита }
 
Function isalpha(ch: char): boolean;
Begin
  isalpha := (upcase(ch)>='A') And (upcase(ch)<='Z');
End;
 
{ подсчет числа встреч каждого символа в файле  }
 
Procedure count(inf: str80);
 
Var 
  infile: file Of char;
  ch: char;
Begin
  assign(infile, inf);
  reset(infile);
  while not eof(infile) Do
  Begin
    Read(infile, ch);
    ch := upcase(ch);
    If isalpha(ch) Then
      alpha[ord(ch)-ord('A')] := alpha[ord(ch)-ord('A')]+1
    Else Case ch Of
           ' ': space := space+1;
           '.': period := period+1;
           ',': comma := comma+1;
      End;
  End;
  close(infile);
End;
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  For t := 0 To 25 Do
    alpha[t] := 0;
  space := 0;
  comma := 0;
  period := 0;
  count(inf);
  For t := 0 To 25 Do
    WriteLn(chr(t+ord('A')), ': ', alpha[t]);
  WriteLn('space:', space);
  WriteLn('period:', period);
  WriteLn('comma:', comma);
End.

После прогона данной программы с текстом данной главы вы получите следующую таблицу частот:

A 2525 P 697
B 532 Q 62
C 838 R 1656
D 1145 S 1672
E 3326 T 3082
F 828 U 869
G 529 V 376
H 1086 W 370
I 2242 X 178
J 39 Y 356
K 94 Z 20
L 1103
M 1140 Space 1 5710
N 2164 Period 2 234
O 1767 Comma 3 513
1 - пробел; 2 - точка; 3 - запятая.

Данные частоты использования букв хорошо согласуются со стандартной смесью английского языка, а некоторое отклонение объясняется повторяющимся использованием ключевых слов Турбо Паскаля в программах.
Для того, чтобы добиться значительного сжатия данных, вы должны существенно урезать алфавит за счет наименее часто используемых букв. Хотя существует много вариантов минимального алфавита, в данной главе в него включены 14 наиболее часто используемых букв и пробел, которые составляют 85% всех символов данной главы. Так как символ возврата каретки необходим для предотвращения разрывов слов, он также должен быть включен в алфавит. Таким образом, минимальный алфавит будет следующим:

A B D E H I L M N O R S T U <пробел><возврат каретки>

Следующая программа удаляет все символы, кроме выбранных. Программа записывает комбинацию возврат каретки/перевод строки, если она присутствует. Это делает вывод читабельным. программа сжатия и удаления символов

Program compres2;
 
Type 
  str80 = string[80];
 
Var 
  inf, outf: str80;
 
Procedure comp2(inf, outf: str80);
 
Var 
  infile, outfile: file Of char;
  ch: char;
  done: boolean;
Begin
  assign(infile, inf);
  reset(infile);
  assign(outfile, outf);
  rewrite(outfile);
  done := FALSE;
  Repeat
    If Not eof(infile) Then
      Begin
        Read(infile, ch);
        ch := upcase(ch);
        If pos(ch,'ABCDEJILMNORSTU')<>0 Then Write(outfile,ch);
        If ord(ch)=13 Then Write(outfile, ch);
        If ord(ch)=10 Then Write(outfile, ch);
      End
    Else done := TRUE;
  Until done;
  WriteLn('файл сжат ');
  close(infile);
  close(outfile);
End;
 
Begin
  Write('введите имя входного файла:');
  ReadLn(inf);
  Write('введите имя выходного файла: ');
  ReadLn(outf);
  comp2(inf, outf);
End.

Программа использует встроенную функцию Pos для определения того, входит ли считанный символ в минимальный алфавит. Роs возвращает 0, если не входит, и номер позиции символа в алфавите, если входит.
Если вы примените программу к следующему сообщению

Attention High Command:
Attack successul. Please send additional supplies and fresh troops. This is essential to maintain our foolhold.
General Frashier

сжатое сообщение будет следующим

ATTENTOIN I COMMAND
ATTAC SUCCESSUL LEASE SEND
ADDITIONAL SULEIS AND RES TROOS TIS
IS ESSENTIAL TO MAINTAIN OUR OOTOLD
ENERAL RASIER

Как вы видите, сообщение является довольно читабельным, хотя некоторая неоднозначность присутствует. Неоднозначность является главным недостатком данного метода. Однако, если вы знакомы со словарем писавшего сообщение, то возможно выберите лучший минимальный алфавит, который снимет часть неясностей и неоднозначностей.
Исходное сообщение имеет длину 168 байт, а упакованное сообщение - 142 байта, следовательно, экономия составляет приблизительно 16%.
Если к данному сообщению применить и удаление символов и битовое сжатие, то сообщение сократится приблизительно на 28%. Например, если бы вы были капитаном подводной лодки и хотели послать сообщение в штаб, но не желали бы выдать ваше местоположение, то вы могли бы захотеть сжать сообщение, используя оба метода, чтобы оно было как можно короче.
Как метод битового сжатия, так и метод удаления символов используются в криптографии. Битовое сжатие само по себе шифрует информацию и делает декодирование более трудным. Метод удаления символов при применении его до шифрования имеет одно преимущество: он изменяет частоту использования символов в исходном тексте.

ДЕШИФРАЦИЯ

Глава о криптографии была бы не полной без краткого обзора дешифрации. Искусство дешифрации - это в сущности метод проб и ошибок. Без применения цифрового компьютера благодаря исчерпывающему анализу могут быть расколоты относительно простые шифры. Однако, более сложные коды либо не могут быть расшифрованы, либо требуют методов и ресурсов, которых не существует. Для простоты в данном разделе сосредоточимся на дешифрации наиболее простых кодов. Если вы желаете расшифровать сообщение, которое было зашифровано с помощью метода простой замены со смещенным алфавитом, то вы должны попробовать все 26 возможных смещения, чтобы выяснить, какое из них подходит. Программа для реализации этого показана ниже: программа дешифрования кода для шифра простой замены. сообщения не могут быть длинее 1000 символов

Program brksub;
 
Type 
  str80 = string[80];
 
Var 
  inf: str80;
  message: array[1..1000] Of char;{ взять входное сообщение }
 
{данная функция возвращает TRUE, если ch является буквой алфавита }
 
Function isalpha(ch: char): boolean;
Begin
  isalpha := (upcase(ch)>='A') And (upcase(ch)<='X');
End;
 
Procedure break(inf: str80);
 
Var 
  infile: file Of char;
  ch: char;
  done: boolean;
  sub, t, t2, l: integer;
Begin
  assign(infile, inf);
  reset(infile);
  done := FALSE;
  l := 1;
  Repeat
    Read(infile, message[l]);
    message[l] := upcase(message[l]);
    l := l+1;
  Until eof(infile);
  l := l-1; { удалить знак конца файла }
  t := 0;
  sub := -1;
{ попробовать каждое возможное смещение }
  Repeat
    For t2 := 1 To l Do
      Begin
        ch := message[t2];
        If isalpha(ch) Then
          Begin
            ch := chr(ord(ch)+t);
            If ch>'Z' Then ch := chr(ord(ch)-26);
          End;
        Write(ch);
      End;
    WriteLn;
    WriteLn('декодирован? Y/N): ');
    ReadLn(ch);
    If upcase(ch)='Y' Then sub := t;
    t := t+1;
  Until (t=26) Or (upcase(ch)='Y');
  If sub<> -1 Then Write('offset is ', sub);
  close(infile);
End;
 
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  break(inf);
End.

С незначительными вариациями вы можете применить данную программу для дешифрации шифров, которые используют произвольный алфавит. В данном случае подставляется вводимый вручную алфавит, как показано в данной программе:
программа дешифрации кода для шифров подстановки с произвольным алфавитом

Program beksub2;
 
Type 
  str80 = string[80];
 
Var 
  inf: str80;
  sub: string[26];
  message: array[1..1000] Of char;
 
{ данная функция возвращает TRUE, если ch является буквой алфавита  }
 
Function isalpha(ch: char): boolean;
Begin
  isalpha := (upcase(ch)>='A') And (upcase(ch)<='Z');
End;
 
Procedure break2(inf: str80);
 
Var 
  infile: file Of char;
  ch: char;
  done: boolean;
  t, l: integer;
Begin
  assign(infile, inf);
  reset(infile);
  done := FALSE;
  l := 1;
  Repeat
    Read(infile, message[l]);
    message[l] := upcase(message[l]);
    l := l+1;
  Until eof(infile);
  l := l-1; { очистка признака конца файла }
  Repeat
    Write('введите алфавит замены: ');
    ReadLn(sub);
    For t := 1 To l Do
      Begin
        ch := message[t];
        If isalpha(ch) Then
          ch := sub[ord(ch)-ord('A')];
        Write(ch);
      End;
    WriteLn;
    WriteLn('декодирован ? (Y/N): ');
    ReadLn(ch);
    If upcase(ch)='Y' Then done := TRUE;
  Until done;
  WriteLn('алфавит подстановки : ', sub);
  close(infile);
End;
 
Begin
  Write('введите имя входного файла: ');
  ReadLn(inf);
  break2(inf);
End.

В отличие от шифров замены шифры перестановки и манипуляции битами труднее для дешифрации методами проб и ошибок. Если вы должны расшифровать более сложный код, то желаем удачи.

 
articles/crypting_and_data_compression.txt · Последние изменения: 2006/06/18 16:32 От romtek
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki