Шифр простой подстановки

Тема в разделе "Delphi - FAQ", создана пользователем onyx, 30 дек 2007.

Статус темы:
Закрыта.
  1. onyx

    onyx Гость

    Шифрование в Delphi. Шифр простой подстановки

    В шифре простой подстановки производится замена каждой буквы сообщения некоторым заранее определенным символом (обычно это также буква). В данном шифре ключом является просто перестановка алфавита (это верно в том случае, если буквы заменяются буквами). Например, подобная перестановка: ЛОПТВТЭЕГЬИЫНЕКЧШРКДЯЭСБТИНШЛЫЬ. Она используется следующим образом:
    • Буква А открытого текста заменяется буквой Л;
    • Б заменяется Р;
    • В заменяется Э и т.д.
    Как можно понять из определения, данный шифр является довольно простым. Перейдем к примеру, показывающему одну из возможных его реализаций.
    Теперь стоит оговориться, что программа будет шифровать и дешифровать только русский текст, оставляя неизменным все остальное.
    Первым делом нужно ввести необходимые типы для лучшего понимания написанного кода а также следует соответствующим образом объявить класс формы.
    Код (Text):
    type
    TRusDstAlphabet = array [Char] of Char;

    TfmSubstitution = class(TForm)
    mmDecryptMessage: TMemo;
    mmEncryptMessage: TMemo;
    lbDecryptMessage: TLabel;
    lbEncryptMessage: TLabel;
    btnEncryptMessage: TButton;
    btnDecpyptMessage: TButton;
    btnGenRearrangement: TButton;
    vleSubst: TValueListEditor;
    procedure FormCreate(Sender: TObject);
    procedure btnGenRearrangementClick(Sender: TObject);
    procedure btnEncryptMessageClick(Sender: TObject);
    procedure btnDecpyptMessageClick(Sender: TObject);
    private
    { Private declarations }
    RusDstAlphabet: TRusDstAlphabet;
    procedure GenRearrangment;
    function ValidateRearrangement: Boolean;
    function UpCaseRus(Ch: Char): Char;
    function LowCaseRus(Ch: Char): Char;
    procedure RecalcAlphabet(nKey: Integer);
    function EncryptDecryptString(strMsg: String): String;
    public
    { Public declarations }
    end;
    В нашем приложении для удобства и простоты работы будет реализована возможность задания случайной автоматической перестановки. Первым рассматриваемым методом является функция, реализующая алгоритм генерации случайной перестановки заданной длины из букв русского алфавита. Принцип работы заключается в том, что сначала считается то, что в перестановке нет ни единого символа, о чем свидетельствует установка всех элементов массива WasGen в значении False. Далее в цикле случаным образом генерируются буквы русского алфавита. На очередном шаге цикла буква генерируется до тех пор, пока она будет присутствовать среди уже сгенерированных. как только такая буква получена, то соответствующий элемент массива WasGen устанавливается в значение True, которое свидетельствует о том, что буква больше не может быть сгенерирована. Мы также не забываем добавить ее в перестановку. Код, соответствующий данному описанию представлен ниже:
    Код (Text):
    // функция генерации случайной перестановки
    procedure TfmSubstitution.GenRearrangment;
    var
    Ch, c: char;
    // нужен для определения встречался ли символ ранее
    WasGen: array [Char] of Boolean;
    begin
    // заполняем массив значением False
    FillChar(WasGen, SizeOf(WasGen), False);
    for Ch := 'А' to 'Я' do
    begin
    // генерируем случайный символ до тех пор, пока
    // не будет получен еще не сгенерированный
    repeat
    c := Chr(Ord('А') + random(32));
    until not WasGen[c];
    // помечаем, что символ сгенерирован
    WasGen[c] := True;
    vleSubst.Values[Ch] := c;
    end;
    end;
    В нашем приложении пользователь может сам задавать необходимо перестановку букв алфавита, поэтому стоит учесть тот факт, что он может ошибиться при ее вводе. Для решения данной проблемы реализуем функцию, которая будет отвечать на вопрос о том, является ли введенная перестановка корректной. Определимся с тем, каким критериям должна отвечать перестановка, чтобы считаться допустимой. Во-первых, в каждой ячейке ввода должна присутствовать лишь одна буква - ни больше не меньше. Во-вторых, каждая введенная буква должна принадлежать множеству букв русского алфавита. И в-третьих, ни одна введенная буква не должна повторяться. Проверка первого критерия довольно проста. Для этого достаточно лишь проверить длину строки, введенной в каждой ячейке. Второй критерий также проверяется довольно простой конструкцией принадлежности заданному множеству. Третий критерий проверяется подобно тому, как в предыдущем реализованном методе проверялось, сгенерирована дання буква или нет.
    Код (Text):
    // проверяет корректность перестановки введенной пользователем
    function TfmSubstitution.ValidateRearrangement: Boolean;
    var
    i: Integer;
    s: String;
    Used: array [Char] of Boolean;
    begin
    Result := False;
    FillChar(Used, SizeOf(Used), False);
    for i := 1 to vleSubst.RowCount - 1 do
    Begin
    // символ единственный в строчке?
    s := vleSubst.Cells[1, i];
    if (Length(s) <> 1) then
    Exit;
    // символ - буква русского языка?
    s[1] := UpCaseRus(s[1]);
    if not (s[1] in ['А'..'Я']) then
    Exit;
    // уже встречался ранее?
    if Used[s[1]] then Exit;
    Used[s[1]] := True;
    End;
    Result := True;
    end;
    Далее мы реализуем две вспомогательные функции, которые позволят преобразовать буквы верхнего регистра к нижнему и наоборот. Их реализация довольно специфична и основывается на используемой кодировке. Отдельная проверка буквы "Ё" производится на основании иного расположения в таблице кодировки, чем у остальных букв. Буквы русского алфавита верхнего регистра расположены начиная с "А" по порядку следования в алфавите, а сразу после них аналогично расположены буквы нижнего регистра. Этим объясняется увеличение кода буквы на фиксированное число.
    Код (Text):
    function TfmSubstitution.UpCaseRus(Ch: Char): Char;
    begin
    if Ch = 'ё' then Ch := 'Е';
    if Ch in ['а'..'я'] then Dec(Ch, 32);
    Result := Ch;
    end;
    Код (Text):
    function TfmSubstitution.LowCaseRus(Ch: Char): Char;
    begin
    if Ch = 'Ё' then Ch := 'е';
    if Ch in ['А'..'Я'] then Inc(Ch, 32);
    Result := Ch;
    end;
    Следующим объектом нашего рассмотрения является функция предварительной подготовки алфавита преобразования для шифрования либо дешифрование сообщения. У метода RecalcAlphabet есть параметр nKey, который в зависимости от своего значения показывает, что является ключом. Возможными значениями nKey являются 0 и 1. Значение 0 указывает на то, что будет производиться шифрование сообщения и требуется поставить в соответствие буквам открытого текста буквы перестановки. Значение 1, напротив, указывает на то, что будет производиться дешифрование и требуется поставить в соответствии буквам перестановки буквы открытого текста. Для этого массив сопоставления символов изначально заполняется таким образом, чтобы каждый символ соответствовал самому себе. Это происходит в следующих строках метода:
    Код (Text):
     for Ch := Low(RusDstAlphabet) to High(RusDstAlphabet) do
    RusDstAlphabet[Ch] := Ch;
    После чего требуется подкорректировать даный массив таким образом, чтобы выполнялось требуемое соответствие. Для этого мы проходим по всем элементам редактора значений vleSubst и поправляем массив, указывая в качестве индекса элемента то, чему ставятся соответствие, а в качестве значения элемента массива - то, что является соответствием.
    Код (Text):
     for i := 1 to vleSubst.RowCount - 1 do
    RusDstAlphabet[vleSubst.Cells[nKey, i][1]] := vleSubst.Cells[1 - nKey, i][1];
    Редактор значений vleSubst предназначен для сопоставления букв верхнего регистра. Нам же требуется избавиться от различия между буквами верхнего и нижнего регистров. Для этого мы дополнительно производим следующие действия:
    Код (Text):
     for i := 1 to vleSubst.RowCount - 1 do
    RusDstAlphabet[LowCaseRus(vleSubst.Cells[nKey, i][1])] :=
    LowCaseRus(vleSubst.Cells[1 - nKey, i][1]);
    Мы рассмотрели работу данного метода по частям. Как видите, все относительно просто. Здесь мы используем вспомогательную функцию LowCaseRus. Полный код приведен ниже.
    Код (Text):
    procedure TfmSubstitution.RecalcAlphabet(nKey: Integer);
    var
    Ch: Char;
    i: Integer;
    begin
    // предварительно все символы в алфавите шифрования
    // соответствуют символам из незашифрованного алфавита
    for Ch := Low(RusDstAlphabet) to High(RusDstAlphabet) do
    RusDstAlphabet[Ch] := Ch;
    // формируем алфавит отдельно для каждого из регистров букв
    // здесь для верхнего
    for i := 1 to vleSubst.RowCount - 1 do
    RusDstAlphabet[vleSubst.Cells[nKey, i][1]] := vleSubst.Cells[1 - nKey, i][1];
    // здесь для нижнего
    for i := 1 to vleSubst.RowCount - 1 do
    RusDstAlphabet[LowCaseRus(vleSubst.Cells[nKey, i][1])] :=
    LowCaseRus(vleSubst.Cells[1 - nKey, i][1]);
    end;
    Ещё одной вспомогательной функцией является функция преобразования строки символов с помощью алфавита преобразования в соответствии с указанной операцией. Работа ее довольно проста. В цикле осуществляется прямой проход по строке, и каждый символ, принадлежащий ей, заменяется соответствующим символом алфавита преобразования. В итоге мы получаем зашифрованную либо дешифрованную строку.
    Код (Text):
    function TfmSubstitution.EncryptDecryptString(strMsg: String): String;
    var
    i: Integer;
    begin
    // преобразуем строчку посимвольно
    for i := 1 to Length(strMsg) do
    strMsg[i] := RusDstAlphabet[strMsg[i]];
    Result := strMsg;
    end;
    Теперь, использую все описанные функции, мы без труда можем зашифровать либо дешифровать сообщение. Например, чтобы зашифровать его, мы подготавливаем массив соответствия букв вызовом функции RecalcAlphabet с параметром 0. После чего для каждой строки открытого текста вызываем функцию EncryptDecryptString и в качестве результата получаем зашифрованную строку.
    Основная идея каждого из методов заключается в том, чтобы проверить корректность заданной перестановки, после чего производится предварительная подготовка алфавита сопоставления, и далее сообщение преобразуется. (см. код ниже)
    Код (Text):
    procedure TfmSubstitution.btnEncryptMessageClick(Sender: TObject);
    var
    i: Integer;
    begin
    // проверяем корректность ввода перестановки
    if ValidateRearrangement then
    begin
    // создаем алфавит преобразования открытого текста
    RecalcAlphabet(0);
    // предотвращаем перерисовку компонента до тех пор, пока не
    // зашифруем все строчки сообщения
    mmEncryptMessage.Lines.BeginUpdate;
    // очищаем текстовый редактор
    mmEncryptMessage.Clear;
    // шифруем открытый текст построчно
    for i := 0 to mmDecryptMessage.Lines.Count - 1 do
    mmEncryptMessage.Lines.Add(EncryptDecryptString(mmDecryptMessage.Lines[i]));
    // разрешаем перерисовку компонента
    mmEncryptMessage.Lines.EndUpdate;
    end
    else
    MessageDlg('Ошибка: символы подстановки заданы не верно', mtError, [mbOk], 0);
    end;
    Код (Text):
    procedure TfmSubstitution.btnDecpyptMessageClick(Sender: TObject);
    var
    i: Integer;
    begin
    // проверяем корректность ввода перестановки
    if ValidateRearrangement then
    begin
    // создаем алфавит преобразования шифрованного текста
    RecalcAlphabet(1);
    mmDecryptMessage.Lines.BeginUpdate;
    mmDecryptMessage.Clear;
    // дешифруем шифрованный текст построчно
    for i := 0 to mmEncryptMessage.Lines.Count - 1 do
    mmDecryptMessage.Lines.Add(EncryptDecryptString(mmEncryptMessage.Lines[i]));
    mmDecryptMessage.Lines.EndUpdate;
    end
    else
    MessageDlg('Ошибка: символы подстановки заданы не верно', mtError, [mbOk], 0);
    end;
    Пример работы программы. Исходное сообщение -> зашифрованное.

    [​IMG]

    В итоге мы получили вполне рабочий вариант приложения, способного без особого труда шифровать и дешифровать сообщения. В аттаче находится исходный код программы, работа которой была описана выше.
    &copy; onyx
     
  2. Black horse

    Black horse Гость

    Если в целом
    Простое интересное приложение с замечательными комментариями.
    Я бы функцию генерации случайной перестановки делал по другому...
    сначала было бы а=а, б=б и т.д., а потом поменял бы коды случайных букв определённое количество раз, чтобы всегда знать адекватное время работы алгоритма.
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей