16.2: Заміна шифрів
- Page ID
- 66162
Один простий метод шифрування називається шифром підстановки.
Шифр підміни замінює кожну букву в повідомленні іншою літерою, слідуючи деякому встановленому відображенню.
Простий приклад шифру підстановки називається шифром Цезаря, іноді його називають шифром зсуву. При такому підході кожна буква замінюється на якусь фіксовану кількість позицій пізніше в алфавіті. Наприклад, якщо ми використовуємо зсув 3, то буква А буде замінена на D, буква 3 позиції пізніше в алфавіті. Все відображення виглядало б так: [1]
Оригінал:\(\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}\)
Карти до:\(\mathrm{DEFGHIJKLMNOPQRSTUVWXYZABC}\)
Використовуйте шифр Цезаря зі зрушенням 3, щоб зашифрувати повідомлення: «Їдемо опівдні»
Рішення
Ми використовуємо відображення вище, щоб замінити кожну букву. W замінюється на Z, і так далі, даючи зашифроване повідомлення: ZH ULGH DW QRRQ.
Зверніть увагу, що довжина слів може дати важливу підказку до використовуваного зсуву шифру. Якби ми побачили одну букву в зашифрованому повідомленні, ми б припустили, що вона повинна бути зашифрованою A або I, оскільки це єдині окремі літери, ніж утворюють дійсні англійські слова.
Щоб затемнити повідомлення, літери часто переставляють в блоки рівного розміру. Повідомлення ZH ULGH DW QRRQ можна було записати блоками по три символи як
ЧЖУ ЛГХ РРВ.
Розшифрувати повідомлення GZD KNK YDX MFW JXA, якщо воно було зашифровано за допомогою шифру зсуву зі зсувом 5.
Рішення
Ми починаємо з написання відображення символів, зміщуючи алфавіт, з відображенням A до F, п'ять символів пізніше в алфавіті.
Оригінал:\(\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}\)
Карти до:\(\mathrm{FGHIJKLMNOPQRSTUVWXYZABCDE}\)
Тепер ми працюємо назад, щоб розшифрувати повідомлення. Перша буква G зіставляється на B, тому B є першим символом вихідного повідомлення. Продовжуючи, наше розшифроване повідомлення
КУПИТИ М'ЯКІ ІГРАШКИ ЖОРСТКІ МОРСЬКІ.
Видаляючи пробіли, отримуємо BUYFTIFTYSHARES. У цьому випадку, здається, додатковий символ був доданий в кінці, щоб групи з трьох вийшли рівномірними, і що оригінальне повідомлення було «Купуйте п'ятдесят акцій».
Розшифруйте повідомлення BNW MVX WNH, якщо воно було зашифровано за допомогою шифру зсуву зі зрушенням 9 (відображення A до J).
- Відповідь
-
ВІДПРАВИТИ ГРОШІ
Зверніть увагу, що в обох шифрах вище зайва частина алфавіту обертається навколо початку. Через це зручною версією шифру shift є шифрований диск, такий як шифрований диск Альберті, показаний тут [2] з 1400-х років. У шифрованому диску внутрішнє колесо можна було повернути, щоб змінити зсув шифру. Цей же підхід використовується для «секретних кілець декодера».
Безпека криптографічного методу дуже важлива для людини, яка спирається на те, що їх повідомлення зберігається в таємниці. Безпека залежить від двох факторів:
- Безпека використовуваного методу
- Безпека використовуваного ключа шифрування
У разі шифру зсуву метод - «використовується шифр зсуву». Ключ шифрування - це конкретна кількість використовуваного зсуву.
Припустимо, армія використовує шифр зсуву для надсилання своїх повідомлень, а один із їхніх офіцерів захоплений їхнім ворогом. Цілком ймовірно, що метод та ключ шифрування можуть стати скомпрометованими. Змінити методи шифрування відносно важко, але відносно легко змінити ключі шифрування.
Під час Другої світової війни німецькі машини шифрування Enigma були захоплені, але наявність деталей про метод шифрування лише трохи допомогло союзникам, оскільки ключі шифрування все ще були невідомими і важко виявити. Зрештою, безпека повідомлення не може покладатися на метод, який зберігається в таємниці; він повинен покладатися на ключ, який зберігається в таємниці.
Безпека будь-якого методу шифрування повинна залежати лише від того, який ключ шифрування важко виявити. Небезпечно покладатися на те, що метод шифрування (алгоритм) зберігається в таємниці.
Маючи це на увазі, давайте проаналізуємо безпеку шифру Цезаря.
Припустимо, ви перехоплюєте повідомлення, і ви знаєте, що відправник використовує шифр Цезаря, але не знаєте, який зрушення використовується. Починається повідомлення EQZP. Наскільки важко було б розшифрувати це повідомлення?
Рішення
Оскільки існує лише 25 можливих зрушень, нам доведеться лише спробувати 25 різних можливостей, щоб побачити, який з них дає результати, які мають сенс. Хоча це було б нудно, одна людина може легко зробити це вручну за кілька хвилин. Сучасний комп'ютер міг би спробувати всі можливості менш ніж за секунду.
\ (\ почати {масив} {|l|l|l|l|l|l|l|l|l|}
\ hline\ textbf {Shift} &\ textbf {Повідомлення} &\ textbf {Зсув} &\ textbf {Повідомлення} &\ textbf {Повідомлення} &\ textbf {Повідомлення}
\ рядок 1 &\ текст {DPYO} & 7 &\ текст {XJSI} & 13 &\ текст {RDMC} & 19 &\ текст {LXGW}\
\ рядок 2 &\ текст {COXN} & 8 &\ текст {WIG} & 14 &\ текст {QCLB} & 20 &\ текст {KWFV}
\\ рядок 3 &\ текст {BNWM} & 9 &\ текст {VHQG} & 15\ текст { PBKA} & 21 &\ текст {JVEU}
\\ рядок 4 &\ текст {AMVL} & 10 &\ текст {UGPF} & 16 &\ текст {OAJZ} & 22 &\ текст {IUDT}
\\ рядок 5 &\ текст {ZLUK} & 11 &\ текст {TFOE} & 17 & текст {NZIY} & 23\ текст HTCS}\ \
\ рядок 6 &\ текст {YKTJ} &\ mathbf {1 2} &\ textbf {ВІДПРАВИТИ} & 18 &\ текст {MYHX} & 24 &\ текст {GSBR}\
\ hline & & & & & & 25 &\ текст {FRAQ}\
\ hline
\ кінець {масив}\)
У цьому випадку зсув 12 (відображення A до M) розшифровує EQZP до SEND. Через таку простоту спроби всіх можливих ключів шифрування, шифр Цезаря не є дуже безпечним методом шифрування.
Атака грубою силою - це метод злому шифрування шляхом спроби всіх можливих ключів шифрування.
Щоб зробити атаку грубою силою важче, ми могли б зробити більш складний шифр заміни, використовуючи щось інше, ніж зсув алфавіту. Вибравши випадкове відображення, ми могли б отримати більш безпечний шифр, з компромісом, який ключ шифрування важче описати; ключ тепер буде цілим відображенням, а не просто сумою зсуву.
Використовуйте наведене нижче відображення підстановки для шифрування повідомлення «12 березня 03:00»
Оригінал:\(mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}\)
Карти до:\(\mathrm{2BQF5WRTD8IJ6HLCOSUVK3A0X9YZN1G4ME7P}\)
Рішення
Використовуючи відображення, повідомлення буде шифрувати 62SQT ZN Y1YY
Використовуйте відображення підстановки з Прикладу 4 для розшифрування повідомлення C2SVX2VP
- Відповідь
-
ВЕЧІРКА В 9
Хоча було лише 25 можливих ключів шифру зсуву (35, якби ми включили цифри), існує близько 10 40 можливих шифрів підміни [3]. Це набагато більше трильйона трильйонів. Було б по суті неможливо, навіть з суперкомп'ютерами, спробувати всі
можливі комбінації. Наявність величезної кількості можливих ключів шифрування - одна з важливих частин безпеки ключів.
На жаль, цей шифр все ще не захищений, через методику під назвою частотний аналіз, виявленої арабським математиком Аль-Кінді в 9 столітті. Англійська та інші мови мають певні літери, ніж з'являються частіше в письмовій формі, ніж інші. [4] Наприклад, буква Е найчастіше відображається англійською мовою. На графіку праворуч показано типовий розподіл символів.
Діаграма праворуч показує частоту різних символів в деякому зашифрованому тексті. Що ви можете зробити висновок про картографування?
Рішення
Через високу частоту літери S у зашифрованому тексті, дуже ймовірно, що карти заміни E до S. Оскільки W є другим найпоширенішим символом, ймовірно, що T або A карти W. Оскільки C, A, D та J рідко з'являються у зашифрованому тексті, ймовірно, вони відображені з J, Q, X та Z.
Окрім перегляду окремих букв, частіше з'являються певні пари букв, наприклад, пара «го». Аналізуючи, як часто різні букви та пари літер показують зашифроване повідомлення, можна вивести використане відображення заміни [5].
[1] uk.wikipedia.org/w/індекс. phptitle=файл: caesar3.svg&сторінка = 1. ПД
[2] uk.wikipedia.org/Вікі/Файл: Alberti_cipher_disk.jpg
[3] Є 35 варіантів для того, що A карти, потім 34 варіанти для того, що B карти, і так далі, тому загальна кількість можливостей 35* 34* 33*... * 2* 1 = 35! = близько 10 40
[4] uk.wikipedia.org/w/index. phptitle=file:English_letter_Frequency_ (за алфавітом) .svg&page=1 PD
[5] Приклад того, як це робиться, див. uk.wikipedia.org/wiki/Frequency_analysis