Реализация шифра Скитала на С++

Главная Форумы Программирование Программирование на С++ Реализация шифра Скитала на С++

В этой теме 1 ответ, 1 участник, последнее обновление  daniil159x 7 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #3542

    В предыдущей теме мы подробно разобрали алгоритм шифра Скитала:

    Теперь реализуем его на языке программирования С++:

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <ctime>
    
    using namespace std;
    
    int main() {
      char *source_text;
      char *ciphertext; // "матрица" Сциталла
      int symbol_amount; // кол-во символов в сообщении
      int string_amount; // кол-во строк
      int colum_amount; // кол-во столбцов
      int index; // индекс буквы зашифрованного сообщения
      
      int file_length; // сколько символов считать из файла
    
      ifstream fin("message.txt");
      if (!fin.is_open()) // если файл не открыт
        cout << "Файл не может быть открыт!\n"; // сообщить об этом
      else {
        cout << "Сколько символов считать из файла?  " << endl;
        cin >> file_length;
        source_text = new char[file_length];
        fin.getline(source_text, file_length); // считали строку из файла
    
        cout << endl << "Сообщение: " << endl;
        for (int i = 0; i < file_length; i++) {
          cout << source_text[i];
        }
        cout << endl;
        fin.close(); // закрываем файл
      }
      
      symbol_amount = file_length;
      ciphertext = new char[symbol_amount];
      cout << endl; cout << "Введите ключ Скиталла: ";
      cin >> string_amount;
      colum_amount = ((symbol_amount - 1) / string_amount) + 1; // вычислили кол-во столбцов  
      cout << "Кол-во символов в сообщении: " << symbol_amount << endl;
      cout << "Кол-во строк: " << string_amount << endl;
      cout << "Кол-во столбцов: " << colum_amount << endl;
    
      for (int i = 0; i < symbol_amount; i++) {
        index = string_amount*(i%colum_amount) + (i / colum_amount);
        ciphertext[index] = source_text[i];
      }
      
      for (int i = 0; i < symbol_amount; i++)
        cout << ciphertext[i];
      cout << endl;
      
      delete []ciphertext;
      delete []source_text;
    }

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

    Программа открывает файл message.txt, запрашивает у пользователя количество символов, которые надо считать с файла и зашифровать, ключ шифра (количество столбцов таблицы Скитала) и выводит на экран зашифрованный текст. Шифрование и расшифрование текста осуществляется по одному и тому же алгоритму, однако если при шифровании используется матрица NxM, то для расшифровки текста нужно использовать матрицу MxN:

  • #3545

    daniil159x
    Участник

    Я представлю немного другую реализацию шифра. И поговорим про ключи.

    Немножко теории:

    • Чтобы прочитать с матрицы зашифрованную строку, надо читать сверху вниз каждый столбец слева направо
    • Пустые ячейки(а они будут) будем обозначать *

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

    Выведем формулу для получения [i][j] индекса матрицы из обычного массива.

    1. i – это порядковый номер строки(счёт идёт с 0), j – это номер столбца или номер элемента в i строке.
    2. строки имеют одинаковую длину(далее переменная width).

    Рассуждаем: по 2 пункту одна строка имеет row элементов, две строки – 2*width, три – 3*width и т д.
    Нам нужно найти i строку и j символ в ней. Значит нам надо пропустить i*width элементов и взять j символ.
    Формула такова: index = i*width + j

    Теперь будем читать и сразу выводить “матрицу”.
    s – искомая строка

    for(size_t j = 0; j < widht; ++j){
        for(size_t i = 0; i < heigth; ++i){
        	std::cout << ((i*widht + j < s.size()) ? s[i*widht + j] : '*');
        }
    }
    

    Для чего нам условие i*widht + j < s.size() ?
    Посмотрим на пример из вики.

    Искомая строка: НАС_АТАКУЮТ – имеет длину 11, таблица(4x3) имеет 12 ячеек, значит, когда циклы запросят [2][3] индекс, программа выйдет за границы строки.

    | Н | А | С |__ |
    | А | Т | А | К |
    | У | Ю | Т | * |
    

    Теперь чуть-чуть о ключах.
    Обычно берут высоту, а длину вычисляют. Для этого есть формула n = [(k-1)/m]+1, где n – количество столбцов, k – длина сообщения, m – количество строк.
    Эта же формула действует и в обратном направлении.
    Если взять m как количество столбцов, то n будет количество строк.

    На этом всё. В другой раз напишу, как дешифровать с помощью такого же метода.

    Исходный код программы полностью:

        
    #include <iostream>
    #include <string>
    
    int main() {
        std::string s;
        size_t heigth, widht;
        
        std::getline(std::cin, s);
        std::cin >> heigth;
        widht = (s.size() - 1) / heigth + 1;
         
        for(size_t j = 0; j < widht; ++j){
            for(size_t i = 0; i < heigth; ++i){
                std::cout << ((i*widht + j < s.size()) ? s[i*widht + j] : '*');
            }
        }
         
        std::cout << std::endl;
         
        return 0;
    }
    

Для ответа в этой теме необходимо авторизоваться.