Hillova šifra

Jedná se o polygrafickou šifru. Představena byla v roce 1929 kryptografem Lesterem S. Hillem. Pro její úspěšné nasazení je potřeba znát základy lineární algebry a diskrétní matematiky, především počítání inverzních matic nad okruhem Z_n, což představuje mírně pokročilou látku. Pro získání potřebných znalostí je nejdříve potřeba prostudovat základy lineární algebry.

Šifrování

Zprávu je nejdříve potřeba zakódovat tak, aby každý znak byl reprezentován číslem 0 až n - 1, kde n vyjadřuje počet znaků kódové abecedy (a dále se využívá při výpočtech). Standardně je n = 26, protože anglická abeceda má právě 26 písmen. Následně se čísla vkládají do čtvercové matice (pro jednoduchost třeba velikosti 3 krát 3), označme ji například X. Při šifrování se používá další čtvercová regulární matice, sice matice klíče, označme ji například H - ta má specifickou vlastnost, musí k ní existovat inverzní matice, což není snadné zaručit. Šifrování pak proběhne vynásobením matice se zakódovanými daty s maticí klíče.

H =

8	23	11
15	0	13
10	20	17

KÓDUJ("krasohled")

→

X =

10	17	0
18	14	7
11	4	3

Vlastní šifrování:

X·H

10	17	0
18	14	7
11	4	3

8	23	11
15	0	13
10	20	17

23	22	19
8	8	5
22	1	16

Po dekódování je zašifrované slovo KRASOHLED rovno: TLXLRBIUU.

Dešifrování

Probíhá obdobně jako šifrování, zakódovaná matice C složená ze zakódovaných znaků šifry, se vynásobí inverzní maticí klíče H^-1. Nejsložitější proces je nalezení inverzní matice mod n. K tomu se využívá Gaussova eliminační metoda a základní vlastnosti modulární aritmetiky. Možné je také využít některé dostupné nástroje online.

H^-1 =

0	7	13
15	0	1
16	2	5

Dešifrování pak probíhá prostým vypočtením:

C·H^-1

23	22	19
8	8	5
22	1	16

0	7	13
15	0	1
16	2	5

10	17	0
18	17	7
11	4	3

Což je po dekódování hledané slovo KRASOHLED.

Programování

Napište algoritmus pro vynásobení dvou matic modulo 26.