2.5: Застосування матриць у криптографії
- Page ID
- 67174
У цьому розділі ми навчимося знаходити зворотну матрицю, якщо вона існує. Пізніше ми будемо використовувати матричні інверси для вирішення лінійних систем. У цьому розділі ви навчитеся
- кодувати повідомлення за допомогою множення матриці.
- декодувати закодоване повідомлення за допомогою зворотної матриці та множення матриці
Шифрування датується приблизно 4000 роками. Історичні звіти свідчать про те, що китайці, єгиптяни, індіанці та греки певним чином зашифровували повідомлення для різних цілей. Одна відома схема шифрування називається шифром Цезаря, також називається шифром заміщення, використовується Юлієм Цезарем, передбачає зміщення букв в алфавіті, наприклад, заміна A на C, B на D, C на E і т.д., для кодування повідомлення. Шифри підміни занадто прості в конструкції, щоб їх можна було вважати безпечними сьогодні.
У середні віки європейські народи стали використовувати шифрування. Різноманітні методи шифрування були використані в США від Революційної війни, до Громадянської війни, і до сучасності.
Застосування математичної теорії та методів шифрування набуло широкого поширення у військовому застосуванні у ХХ столітті. Військові кодували повідомлення перед відправкою, а одержувач розшифрував повідомлення, щоб надсилати інформацію про військові дії таким чином, щоб зберегти інформацію в безпеці, якщо повідомлення було перехоплено. У Другій світовій війні шифрування відігравало важливу роль, оскільки як союзники, так і сили осі надсилали зашифровані повідомлення та виділяли значні ресурси для зміцнення власного шифрування, намагаючись зламати шифрування опозиції.
У цьому розділі ми розглянемо метод шифрування, який використовує множення матриць та зворотні матриці. Цей метод, відомий як Алгоритм Хілла, був створений Лестер Хілл, професор математики, який викладав у кількох коледжах США, а також займався військовим шифруванням. Алгоритм Хілла знаменує впровадження сучасної математичної теорії та методів в область криптографії.
У наші дні алгоритм Хілла не вважається безпечним методом шифрування; його відносно легко зламати з сучасними технологіями. Однак в 1929 році, коли вона була розроблена, сучасної обчислювальної техніки не існувало. Цей метод, з яким ми можемо легко впоратися за допомогою сьогоднішньої технології, був занадто громіздким, щоб використовувати при ручних розрахунках. Хілл розробив машину механічного шифрування, щоб допомогти з математикою; його машина покладалася на шестерні та важелі, але так і не отримала широкого застосування. Метод Хілла вважався складним і потужним у свій час і є одним з багатьох методів впливу на методи, що використовуються сьогодні. Інші методи шифрування в той час також використовували спеціальні машини кодування. Алан Тьюринг, піонер інформатики в області штучного інтелекту, винайшов машину, яка змогла розшифрувати повідомлення, зашифровані німецькою машиною Enigma, допомагаючи переломити хід Другої світової війни.
З появою комп'ютерної епохи та спілкування в Інтернеті використання шифрування набуло широкого поширення в спілкуванні та захищенні приватних даних; це більше не обмежується військовим використанням. Сучасні методи шифрування є більш складними, часто поєднуючи кілька кроків або методів шифрування даних, щоб зберегти їх більш безпечним і важче зламати. Деякі сучасні методи використовують матриці як частину процесу шифрування та дешифрування; інші галузі математики, такі як теорія чисел, відіграють велику роль у сучасній криптографії.
Щоб використовувати матриці в кодуванні і декодуванні секретних повідомлень, наша процедура наступна.
Ми спочатку перетворюємо секретне повідомлення в рядок чисел, довільно привласнюючи число кожній букві повідомлення. Далі ми перетворюємо цей рядок чисел у новий набір чисел шляхом множення рядка на квадратну матрицю нашого вибору, яка має зворотну. Цей новий набір чисел представляє закодоване повідомлення.
Для декодування повідомлення беремо рядок закодованих чисел і множимо її на зворотну матрицю, щоб отримати вихідний рядок чисел. Нарешті, зв'язавши цифри з відповідними літерами, ми отримуємо оригінальне повідомлення.
У цьому розділі ми будемо використовувати відповідність, показану нижче, де букви A до Z відповідають цифрам від 1 до 26, пробіл представлений цифрою 27, а пунктуація ігнорується.
\ [\ begin {масив} {ccccccccccc}\ математика {A} &\ математика {B} &\ математика {C} &\ математика {D} &\ математика {R} &\ математика {G} &\ математика {H} &\ mathrm {N} &\ mathrm {I}} &\ математика {K} &\ математика {L} &\ mathrm {M}\\
1 & 2 & 3 & 4 & 5
& 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\
\\ рядок\\ математика {N} &\ математика {O} &\ математика {P} &\ математика {Q} &\ математика {R} &\ математика {S} &\ математика {T} &\ mathrm {U} &\ mathrm {V}\ математика {W} &\ математика {X} &\ mathrm {Y} &\ mathrm {A}\\
14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26
\ кінець {масив}\ nonumber\]
Використовуйте матрицю\ (A=\ left [\ begin {array} {ll}
1 & 2\\
1 & 3
\ end {array}\ right]\) для кодування повідомлення: АТАКА ЗАРАЗ!
Рішення
Поділяємо букви повідомлення на групи по дві.
\[\begin{array}{lllll}\text { AT } & \text { TA } & \text { CK } & \text { -N } & \text { OW }\end{array} \nonumber \]
Цифри привласнюємо цим буквам з наведеної вище таблиці, і кожну пару чисел перетворюємо в\(2 \times 1\) матриці. У випадку, коли одна буква залишається на кінці, додається пробіл, щоб перетворити її в пару.
\ [\ left [\ begin {масив} {c}
\ mathrm {A}\
\ mathrm {T}
\ кінець {масив}\ справа] =\ лівий [\ початок {масив} {c}
\
20
\ end {масив}\ правий]\ quad\ лівий [\ begin {масив} {л}
\ mathrm {T}\
\ mathrm {A}
\ кінець { масив}\ праворуч] =\ лівий [\ почати {масив} {c}
20\\
1
\ кінець {масив}\ праворуч]\ квадратний\ лівий [\ початок {масив} {l}
\ mathrm {C}
\\ mathrm {K}
\ кінець {масив}\ справа] =\ лівий [\ почати {масив} {l}
3\
11
\ кінець {масив}\ право]\ nonumber\]
\ [\ left [\ begin {масив} {c}
-\
\ mathrm {N}
\ кінець {масив}\ справа] =\ лівий [\ початок {масив} {l}
27\
14\ кінець {масив}
\ справа]\ quad\ ліворуч [\ begin {масив} {l}
\ mathrm {O}\ mathrm {W}
\ кінець {масив}
\ кінець {масив}\ праворуч] =\ ліворуч [\ begin {масив} {l}
15\\
23
\ end {масив}\ праворуч]\ nonumber\]
Отже, на цьому етапі наше повідомлення, виражене у вигляді\(2 \times 1\) матриць, виглядає наступним чином.
\ [\ left [\ begin {масив} {c}
1\\
20
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
20
\
1\ end {масив}\ справа]\ лівий [\ begin {масив} {c}
3
\
11\ end {масив}\ праворуч [\ почати {масив} {c}
27\\
14
\ кінець {масив}\ справа]\ лівий [\ begin {масив} {c}
15\\
23
\ кінець {масив}\ право]\ quad\ bf {(I)}\ nonumber\]
Тепер для кодування множимо, зліва, кожну матрицю нашого повідомлення на матрицю\(A\). Наприклад, добуток нашої першої матриці:\ (\ left [\ begin {масив} {ll}
1 & 2\
1 & 3\ end {масив}
\ право]\ left [\ begin {масив} {c}
1\\
20
\ end {масив}\ право] =\ left [\ begin {масив} {l}
41\(A\) \\
61
\ end {масив}\ право]\)
І добуток нашої другої матриці:\ (\ left [\ begin {масив} {ll}
1 & 2\
1 & 3
\ end {масив}\ право]\ left [\ begin {масив} {l}
20\\
1
\ end {масив}\ право] =\ left [\ begin {масив} {l}
22\\\(A\)
23
\ end {масив}\ право]\)
Множення кожної матриці\(\bf{(I)}\) на матрицю\(A\), в свою чергу, дає потрібне закодоване повідомлення:
\ [\ left [\ begin {масив} {l}
41\
61
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {l}
22
\
23\ кінець {масив}\ право]\ лівий [\ begin {масив} {l}
25
\
36\ end {масив}\ праворуч [\ почати {масив} {l}
55\\
69
\ end {масив}\ справа]\ лівий [\ begin {масив} {l}
61\\
84
\ end {масив}\ праворуч]\ nonumber\]
Розшифруйте наступне повідомлення, яке було закодовано за допомогою матриці\ (A=\ left [\ begin {array} {ll}
1 & 2\
1 & 3
\ end {array}\ right]\).
\ [\ left [\ begin {масив} {l}
21\
\
26\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {l}
37
\
53\ end {масив}\ справа]\ лівий [\ begin {масив} {l}
45
\
54\ кінець {масив}\ праворуч [\ почати {масив} {c}
74\\
101
\ кінець {масив}\ справа]\ лівий [\ begin {масив} {l}
53\
69
\ кінець {масив}\ справа]\ quad (\ bf {II})\ nonumber\]
Рішення
Оскільки це повідомлення було закодовано множенням на матрицю\(A\) в прикладі\(\PageIndex{1}\), ми декодуємо це повідомлення, спочатку множивши кожну матрицю, зліва, на зворотну матрицю,\(A\) наведену нижче.
\ [A^ {-1} =\ left [\ begin {масив} {cc}
3 & -2\\
-1 & 1
\ end {масив}\ праворуч]\ nonumber\]
Наприклад:\ (\ left [\ begin {масив} {cc}
3 & -2\\
-1 & 1
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
21\
26
\ end {масив}\ право] =\ left [\ begin {масив} {c}
11\\
5
\ end {масив}\ праворуч]\)
Помноживши кожну з матриць в\(\bf{(II)}\) на матрицю\(A^{-1}\), отримуємо наступне.
\ [\ left [\ begin {масив} {c}
11\\
5
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
5
\
16\ end {масив}\ праворуч]\ left [\ begin {масив} {c}
27
\
9\ end {масив}\ праворуч [\ почати {масив} {c}
20\\
27
\ end {масив}\ справа]\ лівий [\ begin {масив} {c}
21\\
16
\ end {масив}\ праворуч]\ nonumber\]
Нарешті, зв'язавши цифри з відповідними їм літерами, отримаємо:
\ [\ лівий [\ початок {масив} {l}
\ mathrm {K}\
\ mathrm {E}
\ кінець {масив}\ справа]\ лівий [\ початок {масив} {l}
\ mathrm {E}\
\ mathrm {P}
\ кінець {масив}\ вправо]\ лівий [\ почати {масив} {l}
-
\\ mathrm {I}
кінець { масив}\ праворуч]\ лівий [\ початок {масив} {l}
\ mathrm {T}\
-
\ кінець {масив}\ справа]\ лівий [\ початок {масив} {л}
\ mathrm {U}\
\ mathrm {P}
\ кінець {масив}\ праворуч]\ nonumber\]
І повідомлення говорить: ТРИМАЙТЕ ЦЕ.
Тепер припустимо, ми хотіли використовувати\(3 \times 3\) матрицю для кодування повідомлення, то замість того, щоб розділити літери на групи по два, ми б розділити їх на групи по три.
Використовуючи матрицю\ (B=\ left [\ begin {масив} {ccc}
1 & 1 &
1\\ 1 & 1\\
2 & 1\ 1 & 1
\ end {масив}\ право]\ nonumber\), закодуйте повідомлення: АТАКА ЗАРАЗ!
Рішення
Поділяємо букви повідомлення на групи по три.
МАТОВИЙ НАЗАД -НІ Ш-
Зауважте, що так як одна буква «W» залишилася на кінці, ми додали два пробіли, щоб перетворити її в триплет.
Тепер привласнюємо цифрам відповідні їм літери з таблиці, і кожну трійку чисел перетворюємо в\(3 \times 1\) матриці. Ми отримуємо
\ [\ left [\ begin {масив} {l}
\ mathrm {A}
\\ mathrm {T}\
\ mathrm {T}
\ кінець {масив}\ справа] =\ лівий [\ begin {масив} {c}
1\\
20
\ кінець {масив}\ праворуч]\ лівий [\ початок {масив} {l}
\ mathrm {A}\\
\ mathrm {C}\
\ mathrm {K}
\ кінець {масив}\ справа] =\ лівий [\ почати {масив} {l}
1\
3\\
11
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {l}
-
\\ mathrm {N}\
\ mathrm {O}
\ end {масив}\ праворуч] =\ лівий [\ почати {масив} {l}
27\\
14\
\
15\ кінець {масив}\ справа]\ лівий [\ початок {масив} {l}
\ mathrm {W}\
-\\
-
\ кінець {масив}\ справа] =\ лівий [\ почати {масив} {l}
23\\
27\
27
\ кінець {масив}\ право]\ nonumber\]
Поки що у нас є,
\ [\ лівий [\ begin {масив} {c}
1\\
20\
20
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
1\
3\
11
\ end {масив}\ праворуч]\ left [\ begin {масив} {c}
27\\
14\\
15
\ end {масив}\ справа]\ лівий [\ begin {масив} {c}
23\\
27\
27
\ кінець {масив}\ право]\ quad\ bf {(III)}\ nonumber\]
Множимо, зліва, кожну матрицю нашого повідомлення на матрицю\(B\). Наприклад,
\ [\ left [\ begin {масив} {ccc}
1 & 1 & -1\
1 & 0 & 1\\
2 & 1 & 1
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
1\
20\
20
\ end {масив}\ праворуч] =\ left [\ begin {масив} {c}
1\\
21\\
42
\ кінець {масив}\ право]\ nonumber\]
Помноживши кожну з матриць в\(\bf{(III)}\) на матрицю\(B\), отримуємо потрібне закодоване повідомлення наступним чином:
\ [\ лівий [\ begin {масив} {c}
1\
21\\
42
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
-7\
12\\
16
\ end {масив}\ справа]\ лівий [\ begin {масив} {c}
26\\
42\\
83
\ end {масив}\ праворуч]\ лівий [\ begin {масив} {c}
23\\
50\
100
\ end {масив}\ право]\ nonumber\]
Якщо нам потрібно розшифрувати це повідомлення, ми просто множимо закодоване повідомлення на\(B^{-1}\), і пов'язуємо цифри з відповідними буквами алфавіту.
У прикладі\(\PageIndex{4}\) ми продемонструємо, як використовувати матрицю\(B^{-1}\) для декодування зашифрованого повідомлення.
Розшифруйте наступне повідомлення, яке було закодовано за допомогою матриці\ (B=\ left [\ begin {array} {lll}
1 &
1\\ 1 & 0 & 1\\
2 & 1 & 1
\ end {масив}\ право]\).
\ [\ лівий [\ begin {масив} {l}
11\\
20\\
43
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {l}
25\\
10\
41
\ end {масив}\ праворуч]\ left [\ begin {масив} {l}
22\\
14\\
41
\ кінець {масив}\ право]\ квад\ bf {(IV)}\ nonumber\]
Рішення
Так як це повідомлення було закодовано множенням на матрицю\(B\). Спочатку визначаємо зворотне\(B\).
\ [\ mathrm {B} ^ {-1} =\ лівий [\ begin {масив} {ccc}
1 & 2\
-1 & -3 & 2\ -1 & 1\
-1 & 1
\ end {масив}\ праворуч]\ nonumber\]
Для декодування повідомлення множимо кожну матрицю, зліва, на\(B^{-1}\). Наприклад,
\ [\ лівий [\ початок {масив} {ccc}
1 & 2 & -1\
-1 & -3 & 2\\
-1 & -1 & 1\ кінець {масив}
\ справа]\ лівий [\ begin {масив} {c}
11\
20\\
43
\ end {масив}\ праворуч] =\ left [\ begin {масив} {c}
8\\
15\\
12
\ кінець {масив}\ право]\ nonumber\]
Множення кожної з матриць\(\bf{(IV)}\) на матрицю\(B^{-1}\) дає наступне.
\ [\ лівий [\ begin {масив} {c}
8\\
15\
12
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {c}
4\\
27\
6
\ end {масив}\ праворуч]\ left [\ begin {масив} {c}
9\\
18\\
5
\ end {масив}\ право]\ nonumber\]
Нарешті, пов'язуючи цифри з відповідними літерами, отримуємо
\ [\ лівий [\ початок {масив} {l}
\ mathrm {H}
\\ mathrm {O}\
\ mathrm {L}
\ кінець {масив}\ вправо]\ лівий [\ початок {масив} {l}
\ mathrm {D}
\
-\\ mathrm {F}
\ кінець {масив}\ праворуч [\ почати {масив}}
\ mathrm {I}\
\ mathrm {R}\
\ mathrm {E}
\ end {масив}\ право]\ квадратний\ текст {Повідомлення читає:}\ mathrm {HOLD}\ текст {FIRE}\ nonumber\]
У повідомленні йдеться: ТРИМАЙТЕ ВОГОНЬ.
Підсумовуємо:
КОДУВАННЯ ПОВІДОМЛЕННЯ
1. Розділіть букви повідомлення на групи по дві або три.
2. Перетворіть кожну групу в рядок чисел, призначивши число кожній букві повідомлення. Не забудьте призначити літери порожнім пробілам.
3. Перетворіть кожну групу чисел у матриці стовпців.
3. Перетворіть ці матриці стовпців у новий набір матриць стовпців шляхом множення їх на сумісну квадратну матрицю на ваш вибір, яка має зворотну. Цей новий набір чисел або матриць представляє закодоване повідомлення.
РОЗШИФРУВАННЯ ПОВІДОМЛЕННЯ
1. Візьміть рядок закодованих чисел і помножте її на зворотну матрицю, яка використовувалася для кодування повідомлення.
2. Пов'яжіть цифри з відповідними їм літерами.