Afinní šifra

Afinní šifra je substituční šifra, která částečně eliminuje zásadní nevýhodu Caesarovy šifry - málo možností transformace a tím i velmi primitivní kryptoanalýzu.

Šifrování

Základem afinní šifry je následující transformace:

$C_{i} = a \\cdot T_{i} + b \\pmod{m}$

C_i – i-té písmeno šifrovaného textu
T_i – i-té písmeno otevřeného textu
a – parametr a, gcd(a,m) = 1
b – parametr b
m – modulo (jako modulo obvykle volíme prvočíslo, aby bylo předem jasné, že gcd(a, m) = 1, a zároveň abychom útočníkovi nezjednodušovali práci (pokud modulo není prvočíslo, tak je méně možností, jak se text dá šifrovat - je tedy snazší šifru prolomit)).

Příklad

Zašifrujte daný otevřený text pomocí afinní transformace.

Otevřený text: THEINITIAL
a = 5
b = 9
m = 26

T ⇒ 19 ⇒ 5*19 + 9 mod(26) = 0  ⇒ A
H ⇒ 7  ⇒ 5*7  + 9 mod(26) = 18 ⇒ S
E ⇒ 4  ⇒ 5*4  + 9 mod(26) = 3  ⇒ D
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
N ⇒ 13 ⇒ 5*13 + 9 mod(26) = 22 ⇒ W
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
T ⇒ 19 ⇒ 5*19 + 9 mod(26) = 0  ⇒ A
I ⇒ 8  ⇒ 5*8  + 9 mod(26) = 23 ⇒ X
A ⇒ 0  ⇒ 5*0  + 9 mod(26) = 9  ⇒ J
L ⇒ 11 ⇒ 5*11 + 9 mod(26) = 12 ⇒ M

Dešifrování

Při dešifrování musíme eliminovat transformaci vzniklou šifrováním. Provedeme proto takovouto transformaci:

$T_{i} = (C_{i} \\; - \\; b) \\cdot a^{-1} \\pmod{m}$

a^-1 – multiplikativní inverze a v Z_m

Příklad

Dešifrujte šifrovaný text pomocí afinní transfromace.

Šifrovaný text: ASDXWXAXJM
a = 5
b = 9
m = 26

Rozšířeným Euklidovým algoritmem zjistíme:

$a^{-1} = 21$

A ⇒ 0  ⇒ (0  – 9) * 21 mod(26) = 19 ⇒ T
S ⇒ 18 ⇒ (18 – 9) * 21 mod(26) = 7  ⇒ H
D ⇒ 3  ⇒ (3  – 9) * 21 mod(26) = 4  ⇒ E
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
W ⇒ 22 ⇒ (22 – 9) * 21 mod(26) = 13 ⇒ N
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
A ⇒ 0  ⇒ (0  – 9) * 21 mod(26) = 19 ⇒ T
X ⇒ 23 ⇒ (23 – 9) * 21 mod(26) = 8  ⇒ I
J ⇒ 9  ⇒ (23 – 9) * 21 mod(26) = 0  ⇒ A
M ⇒ 12 ⇒ (12 – 9) * 21 mod(26) = 11 ⇒ L

Útoky na afinní šifru:

Protože je zde již daleko více kombinací, tak by byl útok hrubou silou poměrně neefektivní (nic méně pořád proveditelný). Skutečnou slabinou afinní šifry je frekvenční analýza.

Příklad

Zachytili jsme následující řetězec a víme, že je šifrován v modulu 26, také jsme si jisti, že protistrana komunikuje anglicky.

ASDXWXAXJMJYKJWTDBIASDVXUASJQRZPJVVBVFTTDVVIFM
ASJASXAMDQXWADQKDWDYJWYBQYDQDYASDIBFQASGJWEDQJ
QRZABCBXWJQRZNQBFGVBFASJABASDVBFASJRJVVXKDAQJI
IXTCJRQDVFMADYPSDWASDIBFQASGJWEDQJWYASDVXUASOB
ASQDLFXQDYASDIDPQBJYVXWASDJQDJOBASJQRXDVPDQDVA
BGGDYYDJYPSXMDASDZJAADRGADYABTMDJQASDQDVFMAXWN
RDVVBIASBFVJWYVBIKDSXTMDVASDYDMJZPJVMBWNJWYXAX
VASBFNSAASJAXATBVAASDJYKJWTDJAMDJVABWDPDDHPXAS
ASDJYKJWTDWBPVMBPDYSXAMDQTSJWNDYSXVRXWYJWYQDJV
VXNWDYASDIBFQASGJWEDQJQRZOJTHABASDJAAJTHBWVAJM
XWNQJY

Frekvenční analýzou získáme tyto četnosti (v procentech):

A (0): 11.802575107296137
B (1): 6.008583690987124
C (2): 0.4291845493562232
D (3): 12.660944206008583
E (4): 0.6437768240343348
F (5): 2.7896995708154506
G (6): 1.502145922746781
H (7): 0.6437768240343348
I (8): 2.1459227467811157
J (9): 9.656652360515022
K (10): 1.2875536480686696
L (11): 0.2145922746781116
M (12): 3.004291845493562
N (13): 1.502145922746781
O (14): 0.6437768240343348
P (15): 2.1459227467811157
Q (16): 6.008583690987124
R (17): 2.1459227467811157
S (18): 7.939914163090128
T (19): 2.575107296137339
U (20): 0.4291845493562232
V (21): 6.437768240343347
W (22): 5.579399141630901
X (23): 5.36480686695279
Y (24): 5.150214592274678
Z (25): 1.2875536480686696

Protože víme, že v anglickém textu jsou nejčastějšími znaky E (12.702%) a T (9.056%), tak předpokládejme (dle tabulky frekvencí), že byly přetransformovány D a A. Dosaďme pořadí v abecedě těchto písmen do vzorce pro šifrování:

0 = a*19 + b mod(26)
3 = a*4  + b mod(26)

Odečteme první rovnici od druhé, upravíme a vypočítáme multiplikativní inverzi pomocí rozšířeného Euklidova algoritmu a získáme proměnnou a.

3 = -15*a mod(26) // přičteme modulo
3 = 11*a mod(26)
a = 3*11^-1 mod(26)
a = 3*19 mod(26)
a = 5 mod(26)

Nyní dosadíme do první rovnice:

0 = 5*19 + b mod(26)
0 = 17 + b mod(26)
b = -17 mod(26)
b = 9 mod(26)

Nyní již máme k dispozici vše, co pořebujeme, k dešifrování. Dešifrujeme dle příslušného schématu a vychází nám tento text:

THEINITIALADVANCEOFTHESIXTHARMYWASSOSUCCESSFUL
THATHITLERINTERVENEDANDORDEREDTHEFOURTHPANZERA
RMYTOJOINARMYGROUPSOUTHATOTHESOUTHAMASSIVETRAF
FICJAMRESULTEDWHENTHEFOURTHPANZERANDTHESIXTHBO
THREQUIREDTHEFEWROADSINTHEAREABOTHARMIESWEREST
OPPEDDEADWHILETHEYATTEMPTEDTOCLEARTHERESULTING
MESSOFTHOUSANDSOFVEHICLESTHEDELAYWASLONGANDITI
STHOUGHTTHATITCOSTTHEADVANCEATLEASTONEWEEKWITH
THEADVANCENOWSLOWEDHITLERCHANGEDHISMINDANDREAS
SIGNEDTHEFOURTHPANZERARMYBACKTOTHEATTACKONSTAL
INGRAD

Šifrování

Příklad

Dešifrování

Příklad

Útoky na afinní šifru:

Příklad

Doporučujeme