Решение
Для начала необходимо определиться, какие ключи могут быть использованы для шифрования сообщения. Для этого необходимо найти все числа a, которые будут взаимно простыми с m=30, то есть НОД(a, 30) = 1, a < 30. Напишем функцию, которая возвращает все подходящие числа (листинг 3.1-1). Воспользуемся алгоритмом Евклида по вычислению НОД.
Листинг 3.1-1 – Функция получения массива чисел, взаимнопростых с m, на языке программирования C++
/// Вычисление НОД по алгоритму Евклида
/// (Берем остаток от деления большего на меньшее, пока не будет ноль)
/// PARAMS
/// числа a,b (int)
/// RETURN
/// значение НОД
///
int NOD(int a, int b)
{
// цикл пока все числа не нулевые
while (a > 0 && b > 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a + b;
}
Для получения массива ключей при m = 30 необходимо воспользоваться функцией getKeys() (листинг 3.1-2).
Листинг 3.1-2 – Получение массива ключей для m = 30 на языке программирования C++
/// Получение массива ключей
/// PARAMS
/// число m (int)
/// ключи должны быть взаимно простым с ним
/// RETURN
/// массив ключей (vector)
///
vector<int> getKeys(int m)
{
vector<int> keys;
// цикл от 1 до m
for (int i = 1; i < m; i++)
{
// если НОД(очередное число, m) == 1,
// то добавляем очередное число в массив ключей
if (NOD(i, m) == 1)
keys.push_back(i);
}
// возвращаем результат
return keys;
}
int main()
{
// получение массива ключей для m = 30
vector<int> keys = getKeys(30);
// вывод на экран результата
for (int i = 0; i < keys.size(); i++)
cout << keys[i] << " ";
cout << endl;
}
Результат выполнения программы:
1 7 11 13 17 19 23 29
Всего таких ключей – 8.
Дальше возможно 2 варианта:
1) Перебирать комбинации из 3-х ключей на примере шифрования символа точки ‘.’
2) Перебирать комбинации из 3-х обратных ключей (a-1), которые будут из этого же множества ключей (листинг 3.1-2) и перебирать их комбинации для расшифрования последнего символа сообщения, пока не получим символ точки ‘.’. После этого искать (подбирать или вычислить) используемые ключи шифрования.
Первый вариант проще, поскольку сразу дает комбинацию ключей шифрования. Однако для него все равно потребуется реализация функции расшифрования, чтобы получить исходное сообщение.
Для удобства и наглядности ниже приведен пример реализации второго варианта. Для него необходимо написать программу, которая перебирает все возможные комбинации ключей и расшифровывает последний символ сообщения (‘L’) три раза, пока не получится символ точки ‘.’. Учитывая, что множество ключей шифрования и расшифрования одинаковое (их всего 8), такой перебор можно реализовать достаточно быстро. Всего возможно 8*8*8 = 512 комбинаций. Интересуют только те комбинации ключей, в результате использования которых при расшифровании получится символ точки ‘.’. Дополнительно необходимо реализовать функцию расшифрования одного символа и всего текстового сообщения.
Пример реализации такой программы на языке программирования C++ приведен в листинге 3.1-3.
Листинг 3.1-3 – Пример реализации программы перебора ключей для расшифрования символа ‘L’ до получения символа точки ‘.’ на языке программирования C++
// размер алфавита
const int m = 30;
// АЛФАВИТ
char ALPHA[m] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z', '.', ',', ' ', '-' };
/// Получение индекса символа алфавита ALPHA
/// PARAMS
/// c - символ (char)
/// RETURN
/// индекс символа (int)
/// ИЛИ
/// -1 - если символ не найден
///
int getIndex(char c)
{
for (int i = 0; i < m; i++)
if (ALPHA[i] == c)
return i;
// если ошибка
return -1;
}
/// Расшифрование символа с использованием ключей a,b,m
/// PARAMS
/// index - индекс зашифрованного символа (int)
/// a - ключ расшифрования 1-я часть (int)
/// b - ключ расшифрования 2-я часть (int)
/// m - модуль для расшифрования (int)
/// RETURN
/// индекс расшифрованного символа (int)
///
int decipher(int index, int a, int b, int m)
{
int res = (index * a - b) % m;
return res;
}
/// Расшифрование сообщения (string) с использованием ключей a,b,m
/// PARAMS
/// msg - зашифрованное сообщение (string)
/// a - ключ расшифрования 1-я часть (int)
/// b - ключ расшифрования 2-я часть (int)
/// m - модуль для шифрования (int)
/// RETURN
/// зашифрованное сообщение (string)
///
string decipherText(string msg, int a, int b, int m)
{
string res = "";
int cindex, index;
// цикл по каждому символу зашифрованной строки
for (int i = 0; i < msg.length(); i++)
{
// получение индекса очередного символа
cindex = getIndex(msg[i]);
// если индекс символа найден - расшифровываем его
if (cindex != -1)
{
// расшифрование символа
index = decipher(cindex, a, b, m);
// добавление расшифрованного символа к строке результата
res = res + ALPHA[index];
}
}
return res;
}
int main()
{
const int b = 5; // ключ 2-я часть
// получение массива ключей для m = 30
vector<int> keys = getKeys(30);
char csymbol = 'L'; // зашифрованный символ 'L'
int csymbolIndex = getIndex(csymbol);// индекс зашифрованного символа(11)
char symbol = '.'; // исходный символ '.'
int symbolIndex = getIndex(symbol); // индекс исходного символа (26)
for (int i1 = 0; i1 < keys.size(); i1++)
for (int i2 = 0; i2 < keys.size(); i2++)
for (int i3 = 0; i3 < keys.size(); i3++)
{
csymbolIndex = getIndex(csymbol);
// расшифрование на 3-м ключе (keys[i3])
csymbolIndex = decipher(csymbolIndex, keys[i3], b, m);
// расшифрование на 2-м ключе (keys[i2])
csymbolIndex = decipher(csymbolIndex, keys[i2], b, m);
// расшифрование на 1-м ключе (keys[i1])
csymbolIndex = decipher(csymbolIndex, keys[i1], b, m);
// проверка результата
if (csymbolIndex == symbolIndex)
{
// вывод на экран ключей расшифрования
cout << "keys: " << keys[i3] << "," << keys[i2] << "," <<
keys[i1] << endl;
}
}
Для поиска подходящей комбинации из найденных 40-ка вариантов необходимо расшифровать всё сообщение и посмотреть результат. Для этого необходимо дополнить программу исходным кодом, пример которого приведен на листинге 3.1-4.
Листинг 3.1-4 – Пример реализации программы перебора ключей для расшифрования всего сообщения на языке программирования C++
char csymbol = 'L'; // зашифрованный символ 'L'
int csymbolIndex = getIndex(csymbol);// индекс зашифрованного символа(11)
char symbol = '.'; // исходный символ '.'
int symbolIndex = getIndex(symbol); // индекс исходного символа (26)
string ctext = "YMXNDXNDYMJDJS L"; // зашифрованное сообщение
string text = ""; // исходное сообщение
for (int i1 = 0; i1 < keys.size(); i1++)
for (int i2 = 0; i2 < keys.size(); i2++)
for (int i3 = 0; i3 < keys.size(); i3++)
{
csymbolIndex = getIndex(csymbol);
// расшифрование на 3-м ключе (keys[i3])
csymbolIndex = decipher(csymbolIndex, keys[i3], b, m);
text = decipherText(ctext, keys[i3], b, m);
// расшифрование на 2-м ключе (keys[i2])
csymbolIndex = decipher(csymbolIndex, keys[i2], b, m);
text = decipherText(text, keys[i2], b, m);
// расшифрование на 1-м ключе (keys[i1])
csymbolIndex = decipher(csymbolIndex, keys[i1], b, m);
text = decipherText(text, keys[i1], b, m);
// проверка результата
if (csymbolIndex == symbolIndex)
{
// вывод на экран ключей расшифрования и самого сообщения
cout << "keys: " << keys[i3] << "," << keys[i2] << "," <<
keys[i1] << " - ";
cout << text << endl;
}
}
Результатом выполнения данной программы будет следующее:
keys: 13,1,7 - JI I JYYDN.
keys: 19,7,7 - J,I SI SJ,YSYDN.
keys: 13,11,7 - THIS IS THE END.
keys: 1,13,7 - J,I I J,YYDN.
keys: 19,17,7 - THIS IS THE END.
...
В результате получается 25 комбинаций, дающий фразу «THIS IS THE END.». Эта фраза и есть исходное сообщение. Осталось подобрать исходные ключи, которые использовались для шифрования с учетом правила их выбора. Это возможно решить двумя способами:
1) Подбирать ключи шифрования для фразы «THIS IS THE END.».
2) Вычислить ключи шифрования, зная ключи расшифрования.
Первый способ проще, поскольку известна начальная фраза и известна зашифрованная фраза. Осталось подобрать комбинацию из трех ключей шифрования так, чтобы каждый ключ удовлетворял условию:
«ключ a равен номеру первого зашифрованного символа сообщения, полученного после применения шифрования. Если номер первого зашифрованного символа не является взаимно простым к m, то в качестве ключа a берется ближайшее большее число, удовлетворяющее правилу. Если такого числа нет (например, номер символа равен 30), то в качестве ключа используется значение 1».
Для этого можно реализовать цикл, аналогичный циклу из листинга 3.1-4, но с использованием функции шифрования и дополнительной проверкой ключей на соответствие условию. Пример такой программы на языке программирования С++ приведен на листинге 3.1‑5.
Листинг 3.1-5 – Пример реализации программы перебора ключей для шифрования фразы «THIS IS THE END.» на языке программирования C++
string text_orig = "THIS IS THE END."; // исходное сообщение
string ctext_origin = "YMXNDXNDYMJDJS L"; // полученное шифрованное
// сообщение
string ctext1, ctext2, ctext3;
// перебор 1-го ключа
for (int i1 = 0; i1 < keys.size(); i1++)
{
// шифрование на 1-м ключе (keys[i1])
ctext1 = cipherText(text_orig, keys[i1], b, m);
// поиск 2-го ключа
for (int i2 = 0; i2 < keys.size(); i2++)
{
// пропускаем ключ, если он меньше номера первого зашифрованного символа
if (keys[i2] < getIndex(ctext1[0]))
continue;
// шифрование на 2-м ключе (keys[i2])
ctext2 = cipherText(ctext1, keys[i2], b, m);
// перебор 3-го ключа
for (int i3 = 0; i3 < keys.size(); i3++)
{
// пропускаем ключ, если он меньше номера первого зашифрованного символа
if (keys[i3] < getIndex(ctext2[0]))
continue;
// шифрование на 3-м ключе (keys[i3])
ctext3 = cipherText(ctext2, keys[i3], b, m);
// сравнение с результатом
if (ctext3 == ctext_origin)
{
// вывод на экран
cout << "key1: " << keys[i1] << ", 1st letter - " << ctext1[0] << " (" << getIndex(ctext1[0]) << ")" << endl;
cout << "key2: " << keys[i2] << ", 1st letter - " << ctext2[0] << " (" << getIndex(ctext2[0]) << "), " << endl;
cout << "key3: " << keys[i3] << ", 1st letter - " << ctext3[0] << " (" << getIndex(ctext3[0]) << "), " << endl;
cout << "Result: " << ctext3 << endl;
cout << "--------" << endl;
}
} // for (i3)
} // for (i2)
} // for(i1)
Результат выполнения программы:
key1: 7, 1st letter - S (18)
key2: 19, 1st letter - R (17),
key3: 17, 1st letter - Y (24),
Result: YMXNDXNDYMJDJS L
--------
key1: 13, 1st letter - M (12)
key2: 13, 1st letter - L (11),
key3: 29, 1st letter - Y (24),
Result: YMXNDXNDYMJDJS L
--------
key1: 19, 1st letter - G (6)
key2: 7, 1st letter - R (17),
key3: 17, 1st letter - Y (24),
Result: YMXNDXNDYMJDJS L
--------
Вариант (7,19,17) и (19,7,17) подходят. Остальные – не подходят, поскольку в тройке (13,13,29) третьим ключом должен был быть ключ 13 (первое простое число после 12). Аналогично в тройке (19,13,23) – вторым ключом должен был быть ключ 7 (первое простое число после 6).
