Книга: Песни о Паскале

Глава 24 Криптография

Глава 24

Криптография

Говорят, что хороший разведчик стоит целой дивизии. Ещё бы! Ведь лишенный секретов противник почти безоружен. Но вот умолкли пушки, а разведка не спит, – у мирного времени свои тайны: коммерческие и технические секреты. Впрочем, если секретов нет, их можно придумать, – почему бы нам не поиграть в шпионов? Приятно сознавать, что «отмыленное» приятелю письмо никто, кроме вас двоих, не прочтет, – надо лишь зашифровать его. Придумана уйма способов шифрования, есть даже наука об этом – криптография; сейчас и мы коснемся краешка этой премудрости.

Римскому полководцу Юлию Цезарю выпали лихие времена. Отправляя гонца с письмом в отдаленный уголок империи, Цезарь рисковал «подарить» свои тайны недругам, – ведь на дорогах было неспокойно. Это надоумило его шифровать свои письма. В чем заключался метод Цезаря?

Прием Юлия состоял в замене одних букв другими путем кругового сдвига алфавита на несколько позиций. На рис. 54 показано превращение букв при сдвиге алфавита на две позиции. Буква «А» становится буквой «В», буква «Б» – буквой «Г» и так далее. Двум последним уготовано превратиться соответственно в буквы «А» и «Б». Такое шифрование превращает письмо в дикую абракадабру!

Как расшифровать её? Очень просто – сдвинуть буквы в обратную сторону. Но надо знать количество сдвигов – это число называют ключом шифра (в примере на рисунке ключ шифра равен двум). Разумеется, что ключ шифра и метод шифрования знали лишь двое: получатель письма и сам Юлий Цезарь.

Пойдем и мы вслед римскому полководцу, – создадим программу для шифрования текстового файла и его расшифровки. Скажу прямо: задача непростая, а потому решать её будем в два этапа. Вначале освоим шифрование отдельной строки, а уж потом «замахнемся» на файл. Но начнем с шифрования отдельного символа.

Зашифровать строку – значит зашифровать каждый её символ. Будь у нас готовая функция шифрования символа, задача решалась бы вмиг. Так займемся ею и начнем с заголовка. Дадим нашей функции имя Encrypt – «шифровать», она должна принимать исходный символ и возвращать другой, зашифрованный. Значит, заголовок функции может быть таким:

function Encrypt (X: char): char;

Теперь сосредоточимся на теле функции и рассмотрим известные нам приёмы обработки. Один из них состоит в применении каскада условных операторов:

if X=’А’
      then Crypt:=’В’
else if X=’Б’
      then Crypt:=’Г’
else...

Насколько удачно это решение? Прикинем количество вложенных операторов в этой лесенке. В русском алфавите 33 буквы, если взять заглавные и строчные, то получится 66. А если надумаем шифровать ещё и латинские буквы, и цифры и знаки препинания, то наберется около двух сотен символов. Такая лесенка условных операторов растянется на несколько этажей!

Не прибегнуть ли к оператору выбора CASE? Тогда тело функции будет намного проще:

case X of
      ’А’: Crypt:=’В’;
      ’Б’: Crypt:=’Г’;
      ...
end;

Обратите внимание, что метками оператора CASE здесь служат символы, – скоро вы узнаете, почему такое возможно. Этот вариант очевидно лучше первого, хотя две сотни меток – тоже не подарок. Но главное неудобство в ином: при изменении ключа шифра придется переписать все ветви оператора CASE, а это, согласитесь, скучно. Не поискать ли иного решения, простого и гибкого?

Первые компьютеры принесли инженерам массу неудобств. Взять хотя бы ввод и вывод данных. Дисплеи, принтеры и звуковые карты – тогда никто не слышал о них! Результат размышлений цифрового «мозга» высвечивался лампочками на инженерной панели ЭВМ, и в эту двоичную «цветомузыку» был посвящён лишь узкий круг мудрецов. Со временем изобрели простые принтеры, способные печатать лишь цифры, а затем и более совершенные – для печати букв и других символов. Как действуют подобные устройства?

Процессор компьютера, как известно, оперирует с числами. А людям подавай то текст, то картинку. Как связать одно с другим? Здесь инженеры вспомнили об алфавите. Ведь буквы в нём упорядочены, а значит, каждой букве можно сопоставить число; например, букве «А» – один, «Б» – два и так далее. Такое сопоставление называют кодированием, оно и решает проблему представления символов. Намерившись напечатать некоторый символ, компьютер передает его код на принтер, а уж принтер знает, как поступить с этим числом. При вводе с клавиатуры происходит обратное преобразование: нажатие клавиши заставляет клавиатуру отправить в процессор код соответствующего символа.

Итак, символы внутри компьютера кодируются числами. Мы посчитали, что общее количество букв, цифр и других знаков составляет более двухсот. Инженеры не поскупились и отвели для кодирования символов 256 чисел – от 0 до 255 включительно. Почему именно 256, а не 300 или 500?

Дело в том, что в двоичной системе счисления 256 – это круглое число, оно равно двойке в восьмой степени (если вам знакомо слово «байт», то речь о нём). Так был создан «алфавит» для компьютеров, он включает буквы, цифры, знаки препинания и управляющие символы, – последние выполняют специальные действия с печатающим устройством, например, перевод на следующую строку.

Понятно, что можно придумать несметное количество вариантов кодирования символов. Желая добиться взаимопонимания между техническими устройствами разных изготовителей, инженеры договорились о единой системе кодирования. Теперь она известна под именем ASCII (читается «аски») – American Standard Code for Information Interchange – американский стандартный код для обмена информацией. Со временем этот стандарт стал международным. Ныне используют несколько стандартов кодирования, один из них (для MS-DOS) представлен в приложение И.

Все кодируемые символы разбиты на три группы. Первую составляют управляющие символы с кодами от 0 до 31. Их названия вам мало о чем скажут, обратите внимание лишь на символы с кодами 10 и 13, – они служат для разбивки текста на строки.

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

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

Заметьте также, что символы русского и латинского алфавитов со схожими начертаниями (такие, как «А», «В», «Р») представлены разными кодами!

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

Но как превратить символ в число и наоборот, — число в символ? Ведь это данные разных типов. Паскаль поможет вам своими встроенными функциями. Преобразовать число в символ можно либо функцией CHR, которая изначально присутствовала в языке, либо её современным аналогом по имени CHAR, которым я иногда буду пользоваться в дальнейшем. Обе функции принимают число, а возвращают символ, вот их объявления:

function Chr(arg : integer) : char;
function Char(arg : integer) : char;

Случайно ли, что имя функции CHAR совпадает с именем типа данных? Нет, ведь на самом деле обе эти функции ничего не делают! Они лишь подсказывают компилятору, что число в скобках — это код символа. И все! С такими «ненастоящими» функциями мы ещё встретимся, их применяют для преобразования типов данных. Вот как можно напечатать нескольких символов с их кодами.

var n: integer;
begin
      for n:=40 to 50 do
      Writeln(n,' ', Char(n))
end.

Для обратного преобразования — символа в число — применяют другую «ненастоящую» функцию по имени ORD (от ORDER — «порядковый номер»). Cейчас компиляторы предлагают и её аналог по имени Byte. Функция действительно возвращает порядковый номер символа в таблице ASCII, вот её заголовок:

function Ord(arg : char) : integer;

Воспользовавшись ею, мы тоже можем напечатать символы с их кодами.

var с: char;
begin
      for c:=’A’ to ’F’ do
      Writeln(c,' ', Ord(c))
end.

Здесь счетчиком цикла FOR служит переменная символьного типа. Паскаль допускает это, поскольку «знает», что каждому символу соответствует некоторое число – его код.

Итак, научившись превращать числа в символы и наоборот, мы оказались в шаге от поставленной цели – шифрования символа.

Вернемся к функции шифрования Encrypt, теперь мы можем упростить её до предела.

function Encrypt(arg: char): char;
begin
      Crypt:= Char(Ord(arg) + CKey);
end;

Здесь CKey – ключ шифра, хранящийся где-то в глобальной константе или переменной. Превратив символ arg в число, мы прибавляем к нему ключ, а полученную сумму вновь превращаем в символ.

Все хорошо, прекрасная маркиза, за исключеньем пустяка: сумма в скобках может оказаться больше 255, а символа с таким кодом не существует! Как тогда поступит функция Char? Она вернет символ, укоротив его код на 256. Например, функция Char(260) вернет символ с кодом 260–256=4. Устроит нас это? Никак нет, поскольку первые 32 символа таблицы (коды от 0 до 31) – это управляющие символы. К сожалению, такие символы нарушат структуру текстового файла, и редактор не сможет прочесть его.

Значит, при передаче суммы в функцию Char надо проверить, не превышает ли она 255? Если да, то обрубим ей «хвост» и сдвинем ещё на 32 позиции выше, чтобы попасть в область видимых символов с кодами от 32 и далее.

if X>255 then X:=X–256+32; { смещаем «хвост» – в начало видимых символов }

Так получаем окончательный вариант функции шифрования символа.

function Encrypt(arg: char): char;
var x: integer;
begin
      x:= Ord(arg)+ CKey;
      if x>255 then x:= x–256+32;
      Crypt:= Char(x);
end;

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

function Decrypt(arg: char): char;
var x: integer;
begin
      x:= Ord(arg)– CKey;
      if x<32 then x:= x+256–32;
      Decrypt:= Char(x);
end;

Теперь все готово для построения программы шифрования и расшифровки строки «P_24_1».

{ P_24_1 – Шифрование строки}
const CKey = 2; { Ключ Цезаря }
{––––– Шифрование одного символа –––––}
function Encrypt(arg: char): char;
var x: integer;
begin
      x:= Ord(arg)+ CKey;
      if x>255 then x:= x–256+32;
      Encrypt:= Char(x);
end;
{––––– Расшифровка одного символа –––––}
function Decrypt(arg: char): char;
var x: integer;
begin
      x:= Ord(arg)– CKey;
      if x<32 then x:= x+256–32;
      Decrypt:= Char(x);
end;
{––––– Шифрование строки –––––}
procedure EncryptStr(var arg: string);
var k: integer;
begin
      for k:=1 to Length(arg) do
      arg[k]:= Encrypt(arg[k]);
end;
{––––– Расшифровка строки –––––}
procedure DecryptStr(var arg: string);
var k: integer;
begin
      for k:=1 to Length(arg) do
      arg[k]:= Decrypt(arg[k]);
end;
      {––––– Главная программа –––––}
var S: string;
      Oper: integer;
begin
      repeat
      Write('Введите строку: '); Readln(S);
      Writeln('Укажите операцию: 1– шифровать,’+
      ’ 2– расшифровать,’+
      ’ Прочие – выход');
      Readln(Oper);
      case Oper of
      1: EncryptStr(S);
      2: DecryptStr(S);
      else Break;
      end;
      Writeln(S); { печатаем результат }
      until false;
end.

Программа нуждается лишь в кратких пояснениях. Глобальная константа CKey содержит ключ шифра. Если со временем захотите сменить его, достаточно будет изменить константу и заново откомпилировать программу. Далее следуют описания двух функций: Encrypt и Decrypt – для шифрования и расшифровки символа. Процедуры EncryptStr и DecryptStr шифруют и расшифровывают строки, передаваемые им по ссылке VAR. И, наконец, в главной программе организован цикл для ввода шифруемой строки и кода выполняемой операции (Oper).

Откиньтесь в кресле и полюбуйтесь простотой блоков, составляющих эту программу! А во что бы мы превратили её, свалив в кучу эти простые алгоритмы? В заключение приведу протокол шифрования: пользователь ввел слово «pascal» и зашифровал его, получив слово «rcuecn». Затем ввел строку «rcuecn» и расшифровал её, получив назад данное мною слово.

Введите строку: pascal
Операции: 1 – шифровать, 2 – расшифровать, прочие – выход
Введите операцию: 1
rcuecn
Введите строку: rcuecn
Операции: 1 – шифровать, 2 – расшифровать, прочие – выход
Введите операцию: 2
pascal
Операции: 1 – шифровать, 2 – расшифровать, прочие – выход
Введите операцию: 3

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

• В памяти компьютера символы представлены своими кодами – числами.

• Общее количество символов составляет 256, из них первые 32 – это управляющие, а остальные – видимые символы.

• Для преобразования числового кода в символ применяют функцию Char. Для обратного превращения – символа в число – пользуются функцией Ord..

• Паскаль «знает» о том, что символы кодируются числами, поэтому в счетчике цикла FOR допустимы символьные переменные, а в метках оператора CASE – символьные константы.

А) Измените программу шифрования с тем, чтобы ключ задавать с клавиатуры и передавать в процедуры и функции через параметр. Заголовки процедур и функций сделайте такими:

function Encrypt(arg: char; key: integer): char;
procedure EncryptStr(var arg: string; key: integer);

Хотя здесь проще держать ключ в глобальной переменной, но крупные программы этот приём запутывает, – там лучше передавать данные через параметры.

Б) Предположим, вы пятикратно зашифровали строку. Можно ли расшифровать её? И как это сделать?

В) Для введенной пользователем строки напечатать позиции всех входящих в неё символов (кроме пробелов) в алфавитном порядке. Для символов, которые встречаются несколько раз, напечатать их позиции в одной строке. Например, для слова «PASCAL»:

A – 2 5
C – 4
L – 6
p – 1
S – 3

Г) Для введенной пользователем строки напечатать позиции всех встречающихся в ней символов, кроме пробелов, в порядке их следования в строке. Например, для слова «PASCAL»:

P – 1
A – 2 5
S – 3
C – 4
L – 6

Д) Строки текстовых файлов порой содержат управляющие символы, например символ горизонтальной табуляции (код 9). Шифрование этих символов нашей программой нарушит структуру файла. Исправьте функции Encrypt и Decrypt так, чтобы они не изменяли символы, коды которых меньше 32.

Оглавление книги