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