Основи програмування

Якби ми хотіли надіслати комусь повідомлення, ми б, можливо, захотіли його зашифрувати, тобто певним чином змінити повідомлення, щоб іншим було важко його прочитати. Оригінальний текст тоді ми назвемо звичайний текст, а текст після шифрування - зашифрований текст.

Таке повідомлення, як HI! може бути перетворене в ASCII, 72 73 33. Проте, кожен може з легкістю виконати цю дію і в зворотному порядку.

Розглянемо приклади шифрів з історії, починаючи ще з Першої світової війни, до поеми про поїздку Пола Рівера.

Загалом шифрування потребує не тільки самого тексту на вхід, а й додаткової інформації. Потрібен ключ, іноді це просто секретне число. Відкритий текст може бути зашифрований та розшифрований за допомогою ключа за певним алгоритмом.

Наприклад, якщо ми хочемо надіслати текст I L O V E Y O U, ми спочатку можемо його перетворити на ASCII: 73 76 79 86 69 89 79 85. Тоді, ми можемо зашифрувати його ключем 1 простим алгоритмом, де ми лише додаємо ключ до значення кожного елемента: 74 77 80 87 70 90 80 86. Після цього, якщо хтось перетворить ASCII назад в текст, то отримає J M P W F Z P V. Для розшифровки потрібно буде здогадатися значення кожної букви, методом спроб та поразок, але напевне знати без ключа неможливо. Цей алгоритм відомий під назвою шифр Цезаря.

1. Шифр Цезаря

Шифр Цезаря – симетричний алгоритм шифрування підстановками. Використовувався римським імператором Юлієм Цезарем для приватного листування.

Принцип дії полягає в тому, щоб циклічно зсунути алфавіт, а ключ – це кількість літер, на які робиться зсув.

Таємність цієї "криптосистеми" спиралася лише на Цезаря та на одержувачів, що знали ключ, кількість позицій, на яку Цезар змістив свої літери (наприклад, 1). Не особливо безпечно за сучасними стандартами, але як для одного з перших у світі методів шифрування – цілком достатньо!

Незашифрований текст зазвичай називається відкритим текстом. Зашифрований текст зазвичай називається шифрованим текстом. І використовується ключ, який називається ключем.

Таблиця 1 – Шифрування HELLO з ключем 1 дає IFMMP.

У загальному випадку, алгоритм Цезаря (тобто шифр) кодує повідомлення, "провертаючи" кожну літеру на k позицій. Більш офіційно, якщо p - це якийсь відкритий текст (тобто незашифроване повідомлення), pi – це i-й символом у p, а k - секретний ключ (тобто невід’ємне ціле число), тоді кожна літера ci у зашифрованому тексті c, обчислюється як

ci = (pi + k) mod 26

де mod 26 означає "залишок від ділення на 26". Ця формула, здається, робить шифр більш складним, ніж він є насправді, але в дійсності - це лише стислий спосіб представлення алгоритму.

2. Шифр Віженера

Шифр Віженера покращує шифр Цезаря шляхом шифрування повідомлень за допомогою послідовності ключів (або, по-іншому, ключовим словом). Іншими словами, якщо p - це деякий простий текст і k - це ключове слово (тобто алфавітний рядок, в якому A являє собою 0, B позначає 1, C являє собою 2, ..., а Z представляє 25), тоді кожна літера ci в шифрованому тексті c, обчислюється як:

 ci = (pi + kj) mod 26

Зверніть увагу на використання для цього шифру kj, а не просто k. І якщо k коротше, ніж p, то літери в k повинні бути повторно використані циклічно стільки разів, скільки потрібно для шифрування р.

Іншими словами, якщо сам Віженер захоче сказати комусь конфіденційно HELLO, використовуючи ключове слово, наприклад, ABC, він буде шифрувати H за допомогою ключа від 0 (тобто A), E з ключем 1 (тобто B), а перше L з ключем 2 (тобто C), після чого він залишиться за межами літер в ключовому слову, і тому він повторно використовує його (частину) для шифрування другого L з ключем 0 (тобто A) знову, а O з ключем 1 (тобто B) знову. І так він написав HELLO як HFNLP.

Таблиця 2 – Шифрування HELLO з ключовим словом ABC (повторно використовується циклічно як ABCAB) дає HFNLP.