Декомпозиция сомнительных утвержденийна более мелкие составляющие дает возможностьсоздания коллоидного раствора, в мути которого легкоуйти от прямого ответа.
(Из моих не отредактированных премудростей)
Мы физически практически полностью состоим из своих предков. Более того, мы ментально тоже из них состоим. Ну а ежели это так, то вопрос о том, а зачем моим предкам был нужен язык Си, совсем даже не праздный. Предки мои Си не знали и вполне без него обходились, а вот ныне живущими поколениями программирование на Си все еще востребовано, поэтому на эту тему я здесь мягко и философски выскажусь.
У издательства Manning есть такой маркетинговый ход, который называется MEAP. Это чем-то напоминает укладку рельсов перед летящим вперед паровозом: вам предлагают читать новую книгу глава за главой, пока сама книга находится в процессе написания, а потом получить ее экземпляр еще до того, как она появится в магазинах. Мне такой издательский ход показался интересным, и я решил выложить здесь отдельные главы своей книги. На самом деле моя книга уже написана, но она пока еще свет не увидела и барахтается где-то в бюрократическом омуте всяких-разных методических советов и прочих университетских инстанций, дабы милостиво быть допущенной до изучения ее студентами. О чем книга? Несложно догадаться. Она о программировании. Вот тут вам вполне уместно было бы произнести уже ставшую крылатой фразу: «Шо, опять?». Ну да, опять о программировании.
Как нынче студенты обучаются языку программирования? О синтаксисе языка им рассказывают и короткие примеры показывают, упражнения на дом задают и суету с лабораторными работами устраивают. А живое программирование где? То самое, твое, авторское, которому ты учишь, показывающее то, как ты сам решаешь задачу и создаешь код, о котором хотелось бы рассказать, а главное еще и показать студентам, изучающим основы языка Си, дать возможность им "допилить", сделанную тобой заготовку, подхватывая твой собственный стиль. Вот оно-то никак не помещается в отведенные учебные часы. (Здесь цитата, приписываемая Деду Панасу, опущена из эстетических соображений.) Сие несоответствие повлекло за собой написание книги и попытку предложить ее неискушенным неофитам для самостоятельного изучения.
Это была прелюдия. Теперь - непосредственно сама "людия" и будет она звучать на украинском языке.
Глава 1. Решітка Кардано
1.1. Постановка задачі
Перш ніж поринути у таємничий світ бібліотек та інструментів мови С, давайте спробуємо уявити собі реальність, у якій ще майже нічого не створено: світ тільки народжується, а навколо лише безмежна і холодна пустеля, якою у ранкових багряних сутінках інколи промайне поодиноке програмне створіння на мові асемблера…
Все це більше схоже на сюжет для науково-фантастичного роману, тому будемо вважати, що в цій реальності ми непогано озброєні, бо в нашому розпорядженні є компілятор і стандартна бібліотека мови С, а також непереборне бажання впоратися із завданням, суть якого полягає в наступному. Необхідно розробити програму, яка реалізує алгоритм шифрування "Решітка Кардано".
Для ведення зашифрованого листування призначена спеціальна решітка – маска із заданими елементами, які використовуються для введення символів повідомлення, що шифрується або розшифровується. За допомогою решітки розміром 8х8 можна зашифрувати повідомлення максимальної довжини 64 символи. Алгоритм передбачає наявність однакових решіток у розпорядженні як відправника повідомлення, так і його одержувача. Детальний опис ідеї використання цього методу шифрування наведено у книзі Яківа Перельмана “Жива математика”, у розділі 6 “Математичні оповідання та головоломки”. Історія створення цього методу шифрування та загальна ідея описані в Cardan Grille. Друга частина цього завдання – зворотна задача, тобто відновлення втраченої решітки, спираючись на наявність зашифрованого та розшифрованого повідомлень.
1.2. Генерація решітки Кардано
Перше, що слід зробити, – створити функцію генерації решітки. Очевидно, що може існувати безліч варіантів решіток розміром 8х8. Кількість можливих варіантів перевищує 4 мільярди.
Для створення решітки необхідна базова матриця, яка має вигляд:
1 2 3 4 13 9 5 15 6 7 8 14 10 6 29 10 11 12 15 11 7 313 14 15 16 16 12 8 44 8 12 16 16 15 14 133 7 11 15 12 11 10 92 6 10 14 8 7 6 51 5 9 13 4 3 2 1
У коді програми можна описати таку матрицю наступним чином:
const int matrix[][8] = {
{ 1, 2, 3, 4, 13, 9, 5, 1},
{ 5, 6, 7, 8, 14, 10, 6, 2},
{ 9, 10, 11, 12, 15, 11, 7, 3},
{13, 14, 15, 16, 16, 12, 8, 4},
{ 4, 8, 12, 16, 16, 15, 14, 13},
{ 3, 7, 11, 15, 12, 11, 10, 9},
{ 2, 6, 10, 14, 8, 7, 6, 5},
{ 1, 5, 9, 13, 4, 3, 2, 1}
};
Якщо уважно придивитися до структури базової матриці, можна помітити певну закономірність – матриця складається з 4 окремих матриць, кожна з яких повернена за годинниковою стрілкою на фіксоване число градусів, починаючи з 90 градусів. Помічену особливість можна проігнорувати та ініціалізувати матрицю так, як було показано вище, але цього разу обійдемося без спрощувань і все-таки скористаємося знайденою особливістю. Функція для заповнення базової матриці:
void init_quarters(int (*arr)[SIDE]) {
const int dim = SIDE/2;
int x = 1;
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
arr[i][j] = x; // 1 quarter
arr[j][SIDE-1-i] = x; // 2 quarter
arr[SIDE-1-j][i] = x; // 3 quarter
arr[SIDE-1-i][SIDE-1-j] = x; // 4 quarter
x++;
}
}
}
Виведення на екран вмісту матриці буде корисним для візуальної перевірки правильності роботи функції заповнення базової матриці:
void print_matrix(const int (*arr)[SIDE]) {
for (int i = 0; i < SIDE; i++) {
for (int j = 0; j < SIDE; j++) {
printf("%2d ", arr[i][j]);
}
putchar('\n');
}
}
Щоб упевнитися у правильності роботи функції заповнення базової матриці, додаємо в тіло функції main наступний код:
int matrix[SIDE][SIDE] = {0};
init_quarters(matrix);
print_matrix(matrix);
В результаті виконання цього коду на екрані з'явиться вже знайома матриця:
1 2 3 4 13 9 5 15 6 7 8 14 10 6 29 10 11 12 15 11 7 313 14 15 16 16 12 8 44 8 12 16 16 15 14 133 7 11 15 12 11 10 92 6 10 14 8 7 6 51 5 9 13 4 3 2 1
Базову матрицю отримано і тепер можна створити функцію генерації решітки.
Як було зазначено вище, існує понад 4 мільярди можливих варіантів таких решіток. Для створення решітки доречно використовувати генератор випадкових чисел.
Функція генерації решітки може бути реалізована наступним чином:
const int QUARTER = SIDE * 2;
void gen_rand_cells(const int (*arr)[SIDE], int (*cells)[2],
const int length, const int lower, const int upper) {
const int *ptr = &arr[0][0];
int uniq[QUARTER] = {0};
int count = 0;
time_t t;
srand((unsigned) time(&t));
while (count < length) {
int rand_idx = (rand() % (upper - lower + 1)) + lower;
bool found = false;
for (int i = 0; i < length; i++) {
if (uniq[i] == *(ptr + rand_idx)) {
found = true;
break;
}
}
if (!found) {
uniq[count] = *(ptr + rand_idx);
div_t output = div(rand_idx, SIDE);
cells[count][0] = output.quot;
cells[count][1] = output.rem;
count++;
}
}
}
Зверніть увагу, що крім
#include <stdio.h>
потрібно також додати заголовки:
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>
Додаткова функція, яка виводить на екран результати роботи генератора решіток, буде корисною для візуалізації роботи процесу генерації решітки:
void print_cells(const int (*arr)[SIDE], const int (*cell)[2]) {
for (int i = 0; i < QUARTER; i++) {
int row = cell[i][0];
int col = cell[i][1];
printf("matrix[%d][%d] = %2d\n", row, col, arr[row][col]);
}
}
Додаємо в тіло функції main виклик функції генерації решіток:
int matrix[SIDE][SIDE] = {0};
int cells[QUARTER][2] = {0};
init_quarters(matrix);
print_matrix(matrix);
gen_rand_cells(matrix, cells, QUARTER, 0, SIDE*SIDE-1);
print_cells(matrix, cells);
Після виконання цього коду на екрані отримаємо один з можливих варіантів решітки:
matrix[2][5] = 11
matrix[4][0] = 4
matrix[3][5] = 12
matrix[6][1] = 6
matrix[4][6] = 14
matrix[6][0] = 2
matrix[0][5] = 9
matrix[3][0] = 13
matrix[5][0] = 3
matrix[4][4] = 16
matrix[5][6] = 10
matrix[7][7] = 1
matrix[6][5] = 7
matrix[5][3] = 15
matrix[6][7] = 5
matrix[4][1] = 8
Результат роботи функції print_matrix(matrix) тут не показано. Такий варіант візуалізації решітки може здатися незручним, тому створимо функцію, яка покаже решітку у вигляді матриці, в якій віконця представлені символом '1':
void print_grid(const int (*cell)[2]) {
int grid[SIDE][SIDE] = {0};
for (int i = 0; i < QUARTER; i++) {
int row = cell[i][0];
int col = cell[i][1];
grid[row][col] = 1;
}
print_matrix(grid);
}
Результат виконання цієї функції:
0 0 0 0 0 1 0 00 0 0 0 0 0 0 00 0 0 0 0 1 0 01 0 0 0 0 1 0 01 1 0 0 1 0 1 01 0 0 1 0 0 1 01 1 0 0 0 1 0 10 0 0 0 0 0 0 1
Слід взяти до уваги те, що в коді використовується генератор випадкових чисел, тому при кожному запуску програми будуть створюватися нові решітки.
Така особливість створює певну проблему для подальшої розробки: потрібен один зафіксований результат виконання функції генерації решіток. Це можна зробити за допомогою спеціальної функції, яка створить решітку у вигляді вихідного коду мовою С. Згенерований код решітки можна включити у вихідний код і тимчасово використовувати для подальшої розробки:
void int_cells(const int (*arr)[2]) {
printf("const int cells[][2] = {\n");
for (int i = 0; i < QUARTER; i++) {
printf("\t{%2d,%2d}", arr[i][0], arr[i][1]);
if (i < QUARTER-1) {
putchar(',');
}
putchar('\n');
}
printf("};\n");
}
Результат виконання цієї функції виглядає так:
const int cells[][2] = {
{ 2, 5},
{ 4, 0},
{ 3, 5},
{ 6, 1},
{ 4, 6},
{ 6, 0},
{ 0, 5},
{ 3, 0},
{ 5, 0},
{ 4, 4},
{ 5, 6},
{ 7, 7},
{ 6, 5},
{ 5, 3},
{ 6, 7},
{ 4, 1}
};
Перша частина завдання на цьому закінчена.
1.3. Шифрування та дешифрування за допомогою решітки Кардано
Тепер необхідно створити функції шифрування та дешифрування повідомлення за допомогою решітки. Для цього скористаємося наступним варіантом решітки:
const int cells[][2] = {
{ 5, 6},
{ 0, 5},
{ 2, 3},
{ 0, 6},
{ 4, 3},
{ 3, 2},
{ 7, 0},
{ 1, 7},
{ 3, 6},
{ 2, 2},
{ 2, 6},
{ 4, 6},
{ 7, 3},
{ 0, 3},
{ 7, 5},
{ 6, 1}
};
Повідомлення, яке потрібно зашифрувати чи розшифрувати, можна передати програмі різними способами. Наприклад, прочитати з файлу або передати через аргумент командного рядка. В даному випадку це не принципово, тому для спрощення завдання представимо повідомлення у вигляді рядка символів у вихідному коді:
const char *message =
"Hey dude, do not let me down. Take a bad code and make it better.";
Згідно з описом алгоритму, тут знадобиться функція повороту решітки (матриці) за годинниковою стрілкою на 90 градусів.
Функція повороту матриці може бути реалізована так:
void rotate_clockwise(int (*arr)[SIDE]) {
for (int i = 0; i < SIDE; i++){
for (int j = 0; j < SIDE-i; j++) {
int x = arr[i][j];
arr[i][j] = arr[SIDE-1-j][SIDE-1-i];
arr[SIDE-1-j][SIDE-1-i] = x;
}
}
for (int i = 0; i < SIDE/2; i++) {
for (int j = 0; j < SIDE; j++) {
int x = arr[i][j];
arr[i][j] = arr[SIDE-1-i][j];
arr[SIDE-1-i][j] = x;
}
}
}
Крім того, потрібна функція запису символів повідомлення в вікна решітки. Реалізація такої функції має передбачати ситуацію, коли довжина повідомлення буде меншою за 64 символи. Іншими словами, якщо довжина повідомлення коротше 64 символів, то в цьому випадку залишаються вільні вікна. Якщо ці вікна залишити порожніми, це значно спростить процес злому шифру. Тому необхідно передбачити можливість заповнення вікон, що залишаються порожніми, випадковими символами.
Це ще не все. У повідомленні можуть бути пробіли між словами, розділові знаки і великі літери. Якщо залишити їх у зашифрованому повідомленні, це теж знизить стійкість зашифрованого повідомлення до злому. Отже, необхідно виключити із зашифрованого повідомлення такі символи. Великі літери слід замінити малими.
Функція заповнення решітки може бути реалізована так:
void fill_side(const char *message, int *count, int (*grid)[SIDE],
char (*encrypted)[SIDE]) {
srand(time(0));
const char *ptr = &message[0];
const size_t len = strlen(ptr);
printf("[%2zu] \"%s\"\n", strlen(ptr + *count), ptr + *count);
for (int i = 0; i < SIDE; i++) {
for (int j = 0; j < SIDE; j++) {
if (grid[i][j] == 1) {
while ( (ispunct(message[*count])
|| isspace(message[*count])) && *count < len) {
(*count)++;
}
if (*count < len) {
encrypted[i][j] = tolower(message[*count]);
} else {
char lower = 'a', upper = 'z';
encrypted[i][j] = (rand() % (upper - lower + 1)) + lower;
}
(*count)++;
}
}
}
}
Для контролю результатів роботи цієї функції скористаємось додатковою функцією виведення:
void print_symb(const char (*arr)[SIDE]) {
for (int i = 0; i < SIDE; i++) {
for (int j = 0; j < SIDE; j++) {
printf("%2c ", arr[i][j] ? arr[i][j] : '.');
}
putchar('\n');
}
}
Функція заповнення решітки має бути викликана 4 рази за кількістю сторін решітки всередині функції шифрування. Заповнюємо та повертаємо решітку 4 рази:
void encryptor(const char *message, char (*encrypted)[SIDE]) {
int grid[SIDE][SIDE] = {0};
init_grid(cells, grid);
//print_matrix(grid);
int count = 0; // counter of symbols in message
for (int side = 0; side < 4; side++) {
fill_side(message, &count, grid, encrypted);
rotate_clockwise(grid);
//print_symb(encrypted);
}
}
Для перевірки роботи функції шифрування додамо до тіла функції main наступні рядки:
char encrypted[SIDE][SIDE] = {0};
const char *message =
"Hey dude, do not let me down. Take a bad code and make it better.";
encryptor(message, encrypted);
В результаті виконання отримаємо на екрані:
[65] "Hey dude, do not let me down. Take a bad code and make it better."
. . . h . e y .
. . . . . . . d
. . u d . . e .
. . d . . . o .
. . . n . . o .
. . . . . . t .
. l . . . . . .
e . . t . m . .
[43] "e down. Take a bad code and make it better."
e . . h . e y .
. d . . . . . d
. . u d o w e .
n . d t . a o k
. . . n . . o .
e . . . . . t a
. l b a d c . o
e . . t . m d .
[21] "e and make it better."
e . e h a e y n
. d . . . . d d
. m u d o w e .
n a d t k a o k
. e . n . i o .
e t . . b e t a
t l b a d c . o
e t e t r m d .
[ 1] "."
e r e h a e y n
m d h s p u d d
l m u d o w e n
n a d t k a o k
y e c n c i o v
e t a p b e t a
t l b a d c r o
e t e t r m d j
Останній етап – дешифрування повідомлення. Дешифрування значно простіше, ніж процес шифрування і здійснюється за допомогою функції:
void decryptor(char *readme, const char (*encrypted)[SIDE]) {
int grid[SIDE][SIDE] = {0};
int count = 0;
init_grid(cells, grid);
//print_matrix(grid);
for (int side = 1; side <= 4; side++) {
printf("Side #%d : ", side);
for (int i = 0; i < SIDE; i++) {
for (int j = 0; j < SIDE; j++) {
if (grid[i][j] == 1) {
putchar(encrypted[i][j]);
readme[count] = encrypted[i][j];
count++;
}
}
}
putchar('\n');
rotate_clockwise(grid);
}
}
При дешифруванні використовується та сама решітка, що і при шифруванні!
Зберемо все разом. Додамо до тіла функції main рядки:
char readme[SIDE*SIDE+1] = {0};
decryptor(readme, encrypted);
printf("readme=%s\n", readme);
Тут readme – символьний масив для збереження розшифрованого повідомлення.
Після виконання функції дешифрування отримаємо:
Side #1 : heydudedonotletm
Side #2 : edowntakeabadcod
Side #3 : eandmakeitbetter
Side #4 : ovsgpgtjmfcarytz
readme=heydudedonotletmedowntakeabadcodeandmakeitbetterovsgpgtjmfcarytz
Зверніть увагу на те, що з міркувань збільшення криптостійкості, описаних вище, вихідне повідомлення доповнено в кінці випадковими символами “ovsgpgtjmfcarytz”. Через те, що розділові знаки та пробіли прибрані, а також великі літери замінені малими, вихідний вигляд повідомлення змінився, але саме повідомлення цілком читаємо.
Візьмемо в якості теста повідомлення, довжина якого з урахуванням видалення розділових знаків і пропусків перевищує допустимі 64 символи:
const char *message =
"Hey dude, don't let me down. Take a bad soft and make it better. "
"Remember to let it under your skin. Then you'll begin to make it better.";
Результат виконання програми:
[137] "Hey dude, don't let me down. Take a bad soft and make it better. Remember to let it under your skin. Then you'll begin to make it better."
. . . h . e y .
. . . . . . . d
. . u d . . e .
. . d . . . o .
. . . n . . t .
. . . . . . l .
. e . . . . . .
t . . m . e . .
[115] " down. Take a bad soft and make it better. Remember to let it under your skin. Then you'll begin to make it better."
d . . h . e y .
. o . . . . . d
. . u d w n e .
t . d a . k o e
. . . n . . t .
a . . . . . l b
. e a d s o . f
t . . m . e t .
[93] " and make it better. Remember to let it under your skin. Then you'll begin to make it better."
d . a h n e y d
. o . . . . m d
. a u d w n e .
t k d a e k o e
. i . n . t t .
a b . . e t l b
t e a d s o . f
t e r m r e t .
[71] "emember to let it under your skin. Then you'll begin to make it better."
d e a h n e y d
m o e m b e m d
r a u d w n e t
t k d a e k o e
o i l n e t t t
a b i t e t l b
t e a d s o u f
t e r m r e t n
Side #1 : heydudedontletme
Side #2 : downtakeabadsoft
Side #3 : andmakeitbetterr
Side #4 : emembertoletitun
readme=heydudedontletmedowntakeabadsoftandmakeitbetterremembertoletitun
Очевидно, що вихідне повідомлення не помістилося повністю у відведені позиції решітки. Це цілком очікуваний результат.
1.4. Відновлення решітки
Перейдемо тепер до зворотного завдання, яке нагадує злом шифру. Вважаємо, що нам до рук потрапив текст зашифрованого та розшифрованого повідомлень. Для зручності подальшого розгляду зашифрований текст подаємо у вигляді двовимірного масиву:
const char encrypted[][8] = {
{'e' , 'a' , 'e' , 'n' , 'd' , 'u' , 'f' , 'k' },
{'m' , 'a' , 'd' , 'k' , 'e' , 'i' , 'q' , 'e' },
{'t' , 'o' , 'w' , 'n' , 'b' , 'e' , 't' , 't' },
{'t' , 'a' , 'k' , 'e' , 'k' , 'r' , 'b' , 'r' },
{'e' , 'a' , 'h' , 'b' , 'e' , 'x' , 'g' , 'u' },
{'y' , 'd' , 'u' , 'd' , 'f' , 'm' , 'c' , 'e' },
{'a' , 'd' , 'd' , 'o' , 'n' , 'g' , 'o' , 't' },
{'c' , 'o' , 'd' , 'l' , 'e' , 'r' , 't' , 'm' }
};
Розшифрований текст подаємо у вигляді фрагмента повідомлення:
const char *message = "heydudedonotletm";
Наше завдання полягає тепер у пошуку решітки, яка використовувалася для отримання зашифрованого повідомлення.
Ми не будемо розглядати будь-які витончені схеми злому, а спробуємо написати розв'язання задачі методом "грубої сили", тобто спираючись більшою мірою на обчислювальну міць сучасного комп'ютера.
Для вирішення цього завдання немає потреби обертати матрицю. Достатньо мати тільки текст, отриманий за допомогою першої сторони решітки, щоб прийняти рішення, що шифр зламаний. Завдання зводиться до послідовної генерації варіантів решіток. Кожну згенеровану решітку слід “прикладати” до зашифрованого повідомлення, читати символи та порівнювати їх із фрагментом розшифрованого повідомлення.
Основна складність полягає у послідовному переборі варіантів решіток. Відомо, що решітка – це 16 унікальних “віконець” у базовій матриці. Базову матрицю було розглянуто у першій частині завдання:
1 2 3 4 13 9 5 15 6 7 8 14 10 6 29 10 11 12 15 11 7 313 14 15 16 16 12 8 44 8 12 16 16 15 14 133 7 11 15 12 11 10 92 6 10 14 8 7 6 51 5 9 13 4 3 2 1
Нагадую, базова матриця складається з 4-х субматриць, отриманих шляхом послідовного повороту матриці 4х4 за годинниковою стрілкою. Якщо розглядати кожну з 4 матриць як 16-розрядне ціле число без знака і використовувати його розряди для того, щоб забезпечити унікальність віконців у кожній решітці, то тоді можна використати бітову арифметику для перевірки унікальності віконців у кожній із згенерованих решіток.
Іншими словами, для вирішення цього завдання найбільш очевидним способом, знадобиться чотири цикли (за кількістю матриць 4х4):
typedef unsigned int UINT;
const int SIDE = 8;
const UINT top = 65536; // 65536 = 2^(SIDE*2)
for (UINT i = 0; i < top; i++) {
. . .
for (UINT j = 0; j < top; j++) {
. . .
for (UINT k = 0; k < top; k++) {
. . .
for (UINT m = 0; m < top; m++) {
. . .
Крім того, цікавить час, витрачений програмою на пошук відповідних решіток. Для цього помістимо код пошуку решітки всередину наступного фрагмента коду:
#include <time.h>
const clock_t before = clock();
. . . // код пошуку варіанта решітки
const clock_t difference = clock() - before;
const int msec = difference * 1000 / CLOCKS_PER_SEC;
printf(":( Time taken %d seconds %d milliseconds\n", msec/1000, msec%1000);
Спираючись на всі вищеописані міркування, отримаємо такий код:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
const int matrix[][SIDE] = {
{ 1, 2, 3, 4, 13, 9, 5, 1},
{ 5, 6, 7, 8, 14, 10, 6, 2},
{ 9, 10, 11, 12, 15, 11, 7, 3},
{13, 14, 15, 16, 16, 12, 8, 4},
{ 4, 8, 12, 16, 16, 15, 14, 13},
{ 3, 7, 11, 15, 12, 11, 10, 9},
{ 2, 6, 10, 14, 8, 7, 6, 5},
{ 1, 5, 9, 13, 4, 3, 2, 1}
};
const clock_t before = clock();
const UINT top = 65536; // 65536 = 2^(SIDE*2)
int grid[SIDE][SIDE] = {0};
const size_t area = sizeof(grid[0][0]) * SIDE * SIDE;
unsigned long int iter = 0;
...
for (UINT i = 0; i < top; i++) {
UINT uniq_i = i;
for (UINT j = 0; j < top; j++) {
if (uniq_i & j)
continue;
UINT uniq_j = uniq_i | j;
for (UINT k = 0; k < top; k++) {
if (uniq_j & k)
continue;
UINT uniq_k = uniq_j | k;
int base[SIDE][SIDE] = {0};
make_grid_quarter(base, i, 1);
make_grid_quarter(base, j, 2);
make_grid_quarter(base, k, 3);
for (UINT m = 0; m < top; m++) {
if ((uniq_k ^ m) == 65535) {
printf("%5d %5d %5d %5d\n", i, j, k, m);
memcpy(grid, base, area);
make_grid_quarter(grid, m, 4);
char readme[DIGITS + 1] = {'\0'};
decryptor(grid, encrypted, readme);
if (strcmp(readme, message) == 0) {
printf("Bingo!\n");
printf("%5d %5d %5d %5d\n", i, j, k, m);
print_grid(matrix, grid);
const clock_t difference = clock() - before;
const int msec = difference * 1000 / CLOCKS_PER_SEC;
printf("Time taken %d seconds %d milliseconds\n", msec / 1000,
msec % 1000);
return 0;
}
iter++;
}
}
}
}
}
...
У коді використано деякі додаткові функції. Код цих функцій наведено нижче:
const int DIGITS = SIDE * 2;
void int_to_bin_digit(UINT in, int count, int *out) {
UINT mask = 1U << (count-1);
for (int i = 0; i < count; i++) {
out[i] = (in & mask) ? 1 : 0;
in <<= 1;
}
}
void get_coords(const int quarter, const int index, int *x, int *y) {
const div_t t = div(index, SIDE/2);
const int row = t.quot;
const int col = t.rem;
switch (quarter) {
case 1:
*x = row;
*y = col;
break;
case 2:
*x = col;
*y = SIDE-1-row;
break;
case 3:
*x = SIDE-1-col;
*y = row;
break;
case 4:
*x = SIDE-1-row;
*y = SIDE-1-col;
break;
}
}
void make_grid_quarter(int (*grid)[SIDE], const UINT value, const int quarter) {
int digit[DIGITS];
int_to_bin_digit(value, DIGITS, digit);
for (int i = 0; i < DIGITS; i++) {
if (digit[i] == 0) {
continue;
}
int x, y;
get_coords(quarter, i, &x, &y);
grid[x][y] = 1;
}
}
Результат виконання цієї програми для заданих умов завдання:
Bingo!
0 0 8830 56705
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . 12 . 16 . . .
3 7 11 15 . . . 9
. . 10 14 8 . 6 5
. . . 13 4 . 2 1
Time taken 0 seconds 917 milliseconds
Злом такого шифру не слід вважати тривіальним завданням. Візьміть до уваги те, що тут продемонстровано прямолінійний варіант вирішення завдання – злом методом грубої сили. Метод послідовного перебору варіантів решіток має ряд недоліків, які нескладно помітити при спробі задіяти запропоноване вище рішення для визначення решітки, яка була використана в прикладі першої частини завдання. Ви також мабуть звернете увагу на те, що час вирішення завдання може бути значно більшим, ніж показано у наведеному вище прикладі. Подібний підхід, що спирається на метод грубої сили, зовсім не виключає необхідності створювати більш витончений код, який виконуватиметься швидше. Тут є достатній простір для творчості, який залишається вам. Моє завдання полягало в тому, щоб пройти разом з вами весь шлях від постановки задачі, її аналізу та пошуку відповідного варіанта рішення до отримання кінцевого результату, тим самим показавши вам на конкретному прикладі можливий підхід до вирішення подібних завдань.
Вихідний код рішення цього завдання – це наступні чотири файли:
$ ls -l
total 56
-rw-r--r-- 1 vadim staff 5058 31 лип 13:38 brute.c
-rw-r--r-- 1 vadim staff 4152 31 лип 13:38 encrypt.c
-rw-r--r-- 1 vadim staff 2854 31 лип 13:39 grid.c
-rw-r--r-- 1 vadim staff 4486 31 лип 13:39 solver.c
У цій главі продемонстровано покроковий процес розв'язання класичної задачі використання решітки Кардано для шифрування і дешифрування коротких повідомлень, а також відновлення втраченої решітки методом грубої сили. На прикладі розв'язання цієї задачі показані базові етапи розробки програмного забезпечення: аналіз, декомпозиція на окремі функції та перевірка працездатності створеного коду. Від вас було потрібно, як кажуть у цьому випадку фокусники, стежити за руками, тобто стежити за тим, як на ваших очах народжується код, розмірковуючи, сумніваючись, відчуваючи осяяння власними ідеями.
Тепер саме час завантажити на свій комп'ютер вихідний код за адресою на GitHub: https://github.com/iamvadimov/grille та почати з ним роботу. Код свідомо було написано так, щоб залишити достатній простір для вашої самостійної творчості. Особливо це стосується відновлення втраченої решітки.
Продолжение "Послевкусие Си: распространение сигнала в нейронной сети".
Комментариев нет:
Отправить комментарий