CS50: S2 | Шифр подстановки — часть 2

Рифф замещения

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

• Вводим числовой ключ
• Эта клавиша поворачивается на сколько мест вперед будет следующая буква
• Добавляет соответствующую букву к шифрованному тексту
• Отображает текст

Теперь мы будем делать это по-другому.

Введем ключ, соответствующий 26 буквам, где положение каждой буквы соответствует буквам латинского алфавита.

• Ключ: NQXPOMAFTRHLZGECYJIUWSKDVB
• Римский алфавит: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Таким образом:

• A соответствует N
• F обозначает M
• Z означает B

И так далее.

Далее я настоятельно рекомендую прочитать прошлую статью, поскольку используемая логика одинакова.

Взлом кода

1) Код на C

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

void doCipher(string text, string key);

int main(int argc, string argv[])
{
    if(argc != 2) {
        printf("Usage: ./substitution keyn");
        return 1;
    }
    if (strlen(argv[1]) != 26) {
        printf("Key must contain 26 charactersn");
        return 1;
    }

    string key = argv[1];
    string plaintext = get_string("plaintext: ");

    doCipher(plaintext, key);
}

void doCipher(string text, string key) {
    char cipher[strlen(text)];

    for(int i = 0; i < strlen(text); i++) {
        if(isalpha(text[i])) {

            if(islower(text[i])) {
                int position = text[i] - 97;
                cipher[i] = tolower(key[position]);
            } else {
                int position = text[i] - 65;
                cipher[i] = key[position];
            }

        } else {
            cipher[i] = text[i];
        }
    }

    printf("ciphertext: %sn", cipher);
}

2) Псевдокод

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

3) Чего мы ожидаем в конце?

Это!

Получение ключа пользователя

В классе 2 мы узнали об интерфейсе командной строки (CLI) и о том, как пользователь может передавать аргументы при запуске нашей программы через терминал.

Здесь мы используем argv[], который представляет собой массив символов. Таким образом, используя это, мы будем хранить в переменной этот аргумент, который передаст пользователь и который будет нашим ключом.

string key = argv[1];

В упражнении Сезара мы использовали atoi() для преобразования этой строки в int, что здесь не понадобится, поскольку нам нужна полная строка.

Зачем нам нужна струна?
Строка представляет собой массив символов. И через массив мы можем манипулировать им с помощью скобочной нотации, чтобы найти элементы в соответствии с их позициями.

Запрашивает у пользователя сообщение

Здесь ничего не отличается от того, что было сделано и на 1-й, и на 2-й неделе. Мы используем библиотеку, предоставленную CS50.h, для доступа к функции get_string().

string plaintext = get_string("plaintext: ");

Мы запрашиваем у пользователя сообщение и храним его в переменной, называемой открытым текстом.

Вот и все.

У нас есть доступ к нашему ключу.

У нас есть доступ к исходному сообщению.

Время для волшебства

1) Создадим функцию, которая будет принимать два аргумента

void doCipher(string text, string key) {
    //TODO
}

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

2) Мы создаем массив char[] для нашего зашифрованного сообщения

void doCipher(string text, string key) {
    char cipher[strlen(text)];
    //TODO
}

Поскольку каждый массив должен иметь определенный размер, чтобы программа знала, сколько места в памяти будет выделено. И мы понятия не имеем, какой объем текста введет пользователь. Я использую strlen(), который возвращает длину строки.

Таким образом, этот вновь созданный массив всегда будет того же размера, что и исходное сообщение.

3) Итерация над исходным сообщением

void doCipher(string text, string key) {
    char cipher[strlen(text)];

    for(int i = 0; i < strlen(text); i++) {
       //TODO
    }

}

Мы создаем команду for(), которая представляет собой команду повтора для итерации по всей длине исходного сообщения. Мы используем начальную точку как значение 0, потому что в вычислениях массивы имеют нулевую базу, то есть начальный элемент начинается с 0, а не с 1, как мы делаем в повседневной жизни.

4) Проверка, является ли символ в позиции i буквой алфавита

void doCipher(string text, string key) {
    char cipher[strlen(text)];

    for(int i = 0; i < strlen(text); i++) {
        if(isalpha(text[i])) {

            //TODO

        } else {
            cipher[i] = text[i];
        }
    }

    printf("ciphertext: %sn", cipher);
}

Функция isalpha() является частью библиотеки ctype.h, всю эту информацию вы можете найти в документации CS50 Docs. Эта функция проверяет, является ли символ буквой алфавита.

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

5) Проверка, является ли буква строчной

void doCipher(string text, string key) {
    char cipher[strlen(text)];

    for(int i = 0; i < strlen(text); i++) {
        if(isalpha(text[i])) {

            if(islower(text[i])) {
                int position = text[i] - 97;
                cipher[i] = tolower(key[position]);
            } else {
                int position = text[i] - 65;
                cipher[i] = key[position];
            }

        } else {
            cipher[i] = text[i];
        }
    }
}

Теперь, когда мы знаем, что буква принадлежит к алфавиту, она может быть только в верхнем или нижнем регистре.

Поэтому я проверяю, является ли он строчным, используя функцию islower(), которая также принадлежит библиотеке ctype.h.

Отсюда нам снова понадобится таблица символов ASCII.

Зная, что наша ключевая строка представляет собой массив символов из 26 букв, нам нужно найти ее позицию. А наш алфавит всегда начинается с буквы A, мы можем быть уверены, что буква A — это 0 позиция нашего римского алфавита.

• Римский алфавит[26] = «ABCDEFGHIJKLMNOPQRSTUVWXYZ»
  • Римский алфавит[0] => «A»
  • Римский алфавит[5] => «F»
  • Римский алфавит[25] => «Z»

С момента вычитания в соответствии со значением из таблицы ASCII, я также найду отношение для ключа

• key[26] = «NQXPOMAFTRHLZZGECYJIUWSKDVB»
  • key[0] => «N»
  • key[5] => «M»
  • key[25] => «B»

И так, для каждой позиции в итерации *i* будет добавлена соответствующая буква в наш массив cipher[].

Я использую функцию tolower(), которая преобразует букву из прописной в строчную, потому что ключ, как в примере выше, может быть весь прописным, но если буква строчная, я хочу, чтобы она оставалась строчной.

6) Вывод шифрованного текста на экран

• Мы выполняем printf, используя код формата строки для char

void doCipher(string text, string key) {
    char cipher[strlen(text)];

    for(int i = 0; i < strlen(text); i++) {
        if(isalpha(text[i])) {

            if(islower(text[i])) {
                int position = text[i] - 97;
                cipher[i] = tolower(key[position]);
            } else {
                int position = text[i] - 65;
                cipher[i] = key[position];
            }

        } else {
            cipher[i] = text[i];
        }
    }

    printf("ciphertext: %sn", cipher);
}

• Окончательный результат!

Заключение

Поздравляю!
Вы решили все задачи из недели 2.
На следующей неделе мы вернемся к третьей неделе, нам предстоит узнать еще много нового в следующих задачах.

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

Увидимся в следующий раз!