Решение задач из книги Страуструпа (шифрование/дешифрование)

@ADnD · Регистрация: 05.12.2024

Студворк — интернет-сервис помощи студентам

Доброго времени суток,

Решаю задачки из книги Б.Страуструпа "Язык программирования С++. Специальное издание.", Бином, 2019.
Заинтересовали две: упр.9 и 10 из Пар.7.10. В упр. 9 предлагается написать программу шифрования по алгоритму c^key[i]. А в упр. 10 - написать программу, помогающую без знания ключа дешифровать текст, закодированный программой из упр. 9.
Весь смак в том, что предлагается воспользоваться алгоритмом из другой удивительной книги: "David Kahn: The Codebreakers". Т.е. это не переборы ключей, а другой алгоритм, определяющий длину ключа по повторам в тексте и далее угадывающий отдельные символы исходя из частоты их употребления в английском языке.

Я написал обе программы: и шифрующую, и дешифрующую. НО: алгоритм из книги рассчитан на работу с английским алфавитом - из шифрованного английского текста получаем открытый английский же текст. А при шифрования по алгоритму c^key[i] из латиницы всегда получается большой процент непечатаемых символов. Соответственно, при расшифровке строго по алгоритму на экран "выводятся" эти непечатаемые символы. (если расшифровывать примеры из книги "David Kahn: The Codebreakers" то программа работает, но там шифровалось подменой одних латинских букв другими, а не через c^key[i])

Вопрос: кто-нибудь вообще решал эту задачу 10 именно с этим алгоритмом из книги? решение есть или сама постановка задачи некорректна???

@TheCalligrapher · 05.05.2025, 06:17

Сообщение от ADnD

НО: алгоритм из книги рассчитан на работу с английским алфавитом - из шифрованного английского текста получаем открытый английский же текст. А при шифрования по алгоритму c^key[i] из латиницы всегда получается большой процент непечатаемых символов.

В смысле, в зашифрованном тексте получается большой процент непечатаемых символов? Это нормально.

Сообщение от ADnD

Соответственно, при расшифровке строго по алгоритму на экран "выводятся" эти непечатаемые символы.

Ничего не понял. Как это при расшифровке могли получиться непечатаемые символы? При расшифровке, если все сделано правильно, должно было получится исходное сообщение. А там, как я понимаю, никаких непечатаемых символов быть не должно.

Verevkin · 05.05.2025, 09:43

Сообщение от ADnD

Вопрос: кто-нибудь вообще решал эту задачу 10 именно с этим алгоритмом из книги? решение есть или сама постановка задачи некорректна???

Покаж кот.
Это вот это, штоли?

Verevkin · 05.05.2025, 09:55

Решение задач из книги Страуструпа (шифрование/дешифрование)

Verevkin · 05.05.2025, 10:00

Сообщение от ADnD

при расшифровке строго по алгоритму на экран "выводятся" эти непечатаемые символы.

Если при расшифровке получаются непечатные символы, значит ключ подобран неверно.

@ADnD · 05.05.2025, 11:41 **[ТС]**

Verevkin, да это те самые задачки. Там сама метода из книжке Codebreakers подразумевает ручной подбор ключа путем сопоставления символов зашифрованного и открытого текстов, с учетом частоты букв в английском алфавите. Я понял задачу так, что программа должна повторять алгоритм из книги, т.е.:
- прочитать зашифрованный текст из cin
- проанализировать текст на повторы групп символов
- расчитать положения повторов в тексте и дистанцию между ними в символах (считать каждый повтор одинаковых групп как новый?)
- разделить дистанции между символами на множители
- вывести таблицу повторов со множителями
- сформировать и вывести таблицу частоты повторов НОД-ов, например 4, или 2 * 2, встречается в 5 из 8 интервалов
- запросить пользователя выбрать "период повторения, вызанного ключом"
- сформировать строку, состояющую из букв зашифрованного текста, начиная с первой и с шагом в период повторения (не вкл 1-ю)
- сформировать строку ciphertext (буквы зашифрованного текста, начиная со второй с шагом в дистанцию ключа)
- для каждой буквы в ciphertext сформировать таблицу plaintext (весь алфавит циклически начиная с буквы ciphertext)
- вывести таблицу сiphertext | possible plaintexts
- высокочастотные буквы проще сделать заглавными (или низкочастотные в зависимости от выбранного способа)
- определить и вывести рекомендованные колонки (где меньше низкочастотных букв)
- вывести на экран таблицу соответствия: зашифрованный текст в колонку шириной в размер ключа, под каждой строкой поле для заполнения, включая символы рекомендуемой колонки из предыдущего пункта

Соответственно, ключ подбирается не полностью автоматически, а с участием человека, а на экран выводятся результаты расчетов, которые помогают оператору в подборе ключа. Отсюда и вопрос о применимости данной методы к расшифровке сообщения, зашифрованного при помощи c^key[i].

Текст программы во вложении. За стиль, код, используемые примитивные конструкции прошу не ругаться )))) Я сосредоточился на самом алгоритме, а средства старался использовать те, которые соответствует главе 7 в изучаемой мною книжке )))

@KSergey9 · 05.05.2025, 12:23

Сообщение от ADnD

Текст программы во вложении. За стиль, код, используемые примитивные конструкции прошу не ругаться )))) Я сосредоточился на самом алгоритме, а средства старался использовать те, которые соответствует главе 7 в изучаемой мною книжке )))

Так а в чем всё же проблема-то? так и осталось не понятным.

Предположу, что в этом:

Сообщение от ADnD

- прочитать зашифрованный текст из cin

?

Verevkin · 05.05.2025, 13:00

Сообщение от ADnD

, с учетом частоты букв в английском алфавите.

Разве этот метод подходит для шифрования по многобайтному ключу? Причём тут частота букв, если в одинаковые буквы в исходном тексте будут шифроваться разными xor-масками?

Я не понимать...

@ADnD · 05.05.2025, 13:08 **[ТС]**

Сообщение от Verevkin

Разве этот метод подходит для шифрования по многобайтному ключу? Причём тут частота букв, если в одинаковые буквы в исходном тексте будут шифроваться разными xor-масками?
Я не понимать...

Логично. Но это означает, что сама постановка задачи в книги не корректна и расшифровать c^key[i] предложенным методом невозможно!!!

ЗЫ. Проблема в том, что я честно старался следовать условию задачи и пришел к выводу, что задача именно этим методом нерешаема. Стало интересно спросить у более опытных людей.

Verevkin · 05.05.2025, 13:12

Сообщение от ADnD

предложенным методом невозможно!!!

Ну, есть другие способы. Например, терморектальный криптоанализ.

@ADnD · 05.05.2025, 13:23 **[ТС]**

Сообщение от Verevkin

Ну, есть другие способы. Например, терморектальный криптоанализ.

ЗЫ. Но книжки иногда тоже наебывают

@SmallEvil · 05.05.2025, 13:42

ADnD,

C++
1
2
3
4
5
6
7
    for (;;) {
        for (int k = k_begin; k < k_end; k++) {
            *it_enc++ = *it_txt++ ^ key[k];
            if (it_txt == txt.end()) break;
        }
        if (it_txt == txt.end()) break;
    }

Вам явно не помешает увидеть как работать циклически с буфером :

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstring>
 
int main(){
   const char buf[] = "Hello World!";
   unsigned count = 100; // количество доступов к элементам буфера
   unsigned size = strlen(buf);
   for(unsigned i = 0; i != count; ++i )
      std::cout << buf[i%size];
   std::cout << std::endl;
}

Code
1
Hello World!Hello World!Hello World!Hello World!Hello World!Hello World!Hello World!Hello World!Hell

Сообщение от ADnD

ЗЫ. Но книжки иногда тоже "обманывают"

Ссылка на книгу "David Kahn: The Codebreakers" дана как подсказка, а не призыв к буквальному использованию алгоритма.

@ADnD · 05.05.2025, 14:00 **[ТС]**

Сообщение от SmallEvil

Вам явно не помешает увидеть как работать циклически с буфером :

Смущает, что C-строку неизвестной длины надо проходить два раза:
1) для определения размера буфера по положению терминального нуля
2) непосредственно при исполнении алгоритма

Какие преимущества будут в вашем варианте? Какие за / против есть в "противостоянии" между char* vs std::string?
Я для себя выбрал string, т.к. изначально в задаче 9 вместо:

C++
1
std::string txt = "THIS TEXT IS CIPHERED BY SIMPLE XOR ALGORITHM.THIS TEXT IS MY FIRST CRYPTO PROGRAMMING.";

было

C++
1
std::getline(std::cin, txt);

А заморачиваться с буферами непонятной длины не хотел, предпочел string

@Royal_X · 05.05.2025, 16:01

Сообщение от ADnD

в "противостоянии" между char* vs std::string

какое, блет, противостояние? ты даже не понял, что хотел сказать SmallEvil

Сообщение от ADnD

Я для себя выбрал string

ну вот и молодец, только зачем такое говно писать, тем более, если взял std::string?

C++
1
2
3
4
5
6
7
for (;;) {
        for (int k = k_begin; k < k_end; k++) {
            *it_enc++ = *it_txt++ ^ key[k];
            if (it_txt == txt.end()) break;
        }
        if (it_txt == txt.end()) break;
    }

@ADnD · 05.05.2025, 18:07 **[ТС]**

Сообщение от Royal_X

какое, блет, противостояние? ты даже не понял, что хотел сказать SmallEvil

Чтобы реализовать алгоритм с буфером, сначала надо определить размер этого буфера. Изначально источник данных cin,
ввод может быть и 10 символов, и 10000. Для чего заморачиваться с буфером, если можно просто читать из cin в string? Для обработки string буфер не нужен, там же есть итераторы. Или я чего то не понимаю? (я думал что буфер нужен для избежания выхода за границы массива при чтении из cin в char*)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::string encrypt(std::string& txt,char* key) {
    std::string enc = txt;
    std::string::const_iterator it_txt = txt.begin();
    std::string::iterator it_enc = enc.begin();
    int k_begin = 0;
    int k_end = static_cast<int>(strlen(key));
    for (;;) {
        for (int k = k_begin; k < k_end; k++) {
            *it_enc++ = *it_txt++ ^ key[k];
            if (it_txt == txt.end()) break;
        }
        if (it_txt == txt.end()) break;
    }
    return enc;
}

Чем плох этот код? выхода за границы массива не вижу, неопределенного поведения нет, все работает.
Честно я Вас не понимаю.

@Royal_X · 05.05.2025, 19:06

Сообщение от ADnD

C++
1
2
3
4
5
6
7
for (;;) {
        for (int k = k_begin; k < k_end; k++) {
            *it_enc++ = *it_txt++ ^ key[k];
            if (it_txt == txt.end()) break;
        }
        if (it_txt == txt.end()) break;
    }

типа так, вроде, вместо процитированного куска

C++
1
2
3
4
for (auto& c : enc) {
        c ^= key[k];
        if (++k == key_len) k = 0;
    }

@SmallEvil · 05.05.2025, 21:33

Сообщение от ADnD

сначала надо определить размер этого буфера.

Странный у вас на счет этого пунктик...

C++
1
2
3
auto key_length = key.size();
for (auto& c : enc)
        c ^= key[k++%key_length];

Добавлено через 7 минут

Сообщение от ADnD

Чем плох этот код?

Много букоф, много ифов, много лишнего.
Я же не говорю что у вас неправильно что-то.

Добавлено через 56 секунд

Сообщение от ADnD

char* key

И что мешает уме стать std::string с размером?

Добавлено через 12 минут
Как то так, что ли.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
#include <iomanip>
 
std::string process(const std::string& in, const std::string key){
   if (!key.size() || !in.size())
      return {};
   std::string res;
   res.reserve(in.size());
   std::size_t key_size = key.size();
   std::size_t k = 0;
   for(const auto& c : in)
      res += c ^ key[k++%key_size];
   return res;
}
 
int main(){
    auto enc = process("Hello World", "key");
    for(const auto& c : enc)
      std::cout << std::hex << std::setw(2) << std::setfill('0') << unsigned((unsigned char)c) << ' ';
}

@ADnD · 05.05.2025, 22:34 **[ТС]**

Сообщение от SmallEvil

res += c ^ key[k++%key_size];

для чего деление по модулю при расчете индекса? я проверил дает ту же последовательность индексов что и простое k++

@SmallEvil · 05.05.2025, 23:28

Сообщение от ADnD

для чего деление по модулю при расчете индекса?

Это вместо сбрасывания счетчика на ноль, как в вашем коде.
Простой операцией.
Вместо доп. условия на каждой итерации.
Именно об этом я и хотел поведать. Но пора закругляться.

@Royal_X · 06.05.2025, 00:58

Сообщение от SmallEvil

Вместо доп. условия на каждой итерации.

а чем деление по модулю на каждой итерации лучше условия на каждой итерации? Наоборот, % всегда накладнее, чем проверка if, можешь сам проверить. У ТС, конечно, там беспорядок в коде и я с самого начала согласился с тобой, что нужно менять... Но я сейчас сравниваю не его код, а твой и мой.

Новые блоги и статьи Все статьи Все блоги /
50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .	C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .	Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .	Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .	Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .
SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .	Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .

@ADnD 0 / 0 / 0 Регистрация: 05.12.2024 Сообщений: 17

	Решение задач из книги Страуструпа (шифрование/дешифрование) 04.05.2025, 10:50. Показов 6109. Ответов 40 Метки алгоритмы (Все метки) Доброго времени суток, Решаю задачки из книги Б.Страуструпа "Язык программирования С++. Специальное издание.", Бином, 2019. Заинтересовали две: упр.9 и 10 из Пар.7.10. В упр. 9 предлагается написать программу шифрования по алгоритму c^key[i]. А в упр. 10 - написать программу, помогающую без знания ключа дешифровать текст, закодированный программой из упр. 9. Весь смак в том, что предлагается воспользоваться алгоритмом из другой удивительной книги: "David Kahn: The Codebreakers". Т.е. это не переборы ключей, а другой алгоритм, определяющий длину ключа по повторам в тексте и далее угадывающий отдельные символы исходя из частоты их употребления в английском языке. Я написал обе программы: и шифрующую, и дешифрующую. НО: алгоритм из книги рассчитан на работу с английским алфавитом - из шифрованного английского текста получаем открытый английский же текст. А при шифрования по алгоритму c^key[i] из латиницы всегда получается большой процент непечатаемых символов. Соответственно, при расшифровке строго по алгоритму на экран "выводятся" эти непечатаемые символы. (если расшифровывать примеры из книги "David Kahn: The Codebreakers" то программа работает, но там шифровалось подменой одних латинских букв другими, а не через c^key[i]) Вопрос: кто-нибудь вообще решал эту задачу 10 именно с этим алгоритмом из книги? решение есть или сама постановка задачи некорректна??? 0

Verevkin Злостный нарушитель 10022 / 5488 / 1241 Регистрация: 12.03.2015 Сообщений: 25,567
	05.05.2025, 09:55
	0