Afinní šifra - Affine cipher
Afinní šifra je typ monoalfabetická substituční šifra, kde je každé písmeno v abecedě mapováno na jeho číselný ekvivalent, šifrováno pomocí jednoduché matematické funkce a převedeno zpět na písmeno. Použitý vzorec znamená, že každé písmeno šifruje na jedno další písmeno a zpět, což znamená, že šifra je v podstatě standardní substituční šifra s pravidlem, které určuje, ke kterému písmenu jde. Jako takový má slabosti všech substitučních šifer. Každé písmeno je zašifrováno funkcí (sekera + b) mod 26, kde b je velikost posunu.
Popis
V afinní šifře písmena velikosti abecedy m jsou nejprve mapována na celá čísla v rozsahu 0 … m − 1. To pak používá modulární aritmetika transformovat celé číslo, kterému odpovídá každé písmeno v holém textu, na jiné celé číslo, které odpovídá písmenu v šifrovaném textu. Šifrovací funkce pro jedno písmeno je
kde modul m je velikost abecedy a A a b jsou klíče šifry. Hodnota A musí být zvolen tak, aby A a m jsou coprime. Funkce dešifrování je
kde A−1 je modulární multiplikativní inverzní z A modulo m. Tj. Splňuje rovnici
Multiplikativní inverzní z A existuje pouze pokud A a m jsou coprime. Proto bez omezení na A, dešifrování nemusí být možné. lze ukázat, že dešifrovací funkce je inverzní k šifrovací funkci,
Slabé stránky
Vzhledem k tomu, že afinní šifra je stále monoalfabetická substituční šifra, dědí slabosti této třídy šifer. The Caesarova šifra je afinní šifra s A = 1 protože funkce šifrování se jednoduše redukuje na lineární posun. The Atbash šifra používá A = -1.
Vzhledem ke specifickému případu šifrování zpráv v angličtině (tj. m = 26), existuje celkem 286 netriviálních afinních šifer, nepočítaje 26 triviálních Caesarových šifer. Toto číslo pochází ze skutečnosti, že existuje 12 čísel coprime s 26, které jsou menší než 26 (to jsou možné hodnoty A). Každá hodnota A může mít 26 různých směn sčítání ( b hodnota); proto existuje 12 × 26 nebo 312 možných kláves. Tento nedostatek rozmanitosti způsobí, že je systém vysoce nezabezpečený, když se vezme v úvahu Kerckhoffův princip.
Primární slabost šifry pochází ze skutečnosti, že pokud dešifrovaný může objevit (pomocí frekvenční analýza, hrubou silou, hádám nebo jinak) prostý text dvou znaků šifrovacího textu, pak lze klíč získat řešením a simultánní rovnice. Protože víme A a m jsou relativně špičkové, lze je použít k rychlému vyřazení mnoha „falešných“ klíčů v automatizovaném systému.
Stejný typ transformace použitý v afinních šiferách se používá v lineární shodné generátory, typ generátor pseudonáhodných čísel. Tento generátor není a kryptograficky bezpečný generátor pseudonáhodných čísel ze stejného důvodu, že afinní šifra není zabezpečená.
Příklady
V těchto dvou příkladech, jednom šifrování a jednom dešifrování, budou abeceda písmena A až Z a bude mít odpovídající hodnoty nalezené v následující tabulce.
A | B | C | D | E | F | G | H | Já | J | K. | L | M | N | Ó | P | Q | R | S | T | U | PROTI | Ž | X | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Šifrování
V tomto příkladu šifrování[1] holý text, který se má zašifrovat, je „AFFINE CIPHER“ pomocí výše uvedené tabulky pro číselné hodnoty každého písmene, přičemž A být 5, b být 8, a m být 26, protože v abecedě je použito 26 znaků. Pouze hodnota A má omezení, protože musí být coprime s 26. Možné hodnoty, které A může být 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 a 25. Hodnota pro b může být libovolný, pokud A se nerovná 1, protože se jedná o posun šifry. Šifrovací funkce pro tento příklad tedy bude y = E(X) = (5X + 8) mod 26. Prvním krokem při šifrování zprávy je napsat číselné hodnoty každého písmene.
prostý text | A | F | F | Já | N | E | C | Já | P | H | E | R |
---|---|---|---|---|---|---|---|---|---|---|---|---|
X | 0 | 5 | 5 | 8 | 13 | 4 | 2 | 8 | 15 | 7 | 4 | 17 |
Nyní vezměte každou hodnotu X, a vyřešit první část rovnice, (5X + 8). Po zjištění hodnoty (5X + 8) u každé postavy vezměte zbytek při dělení výsledku (5X + 8) 26. Následující tabulka ukazuje první čtyři kroky procesu šifrování.
prostý text | A | F | F | Já | N | E | C | Já | P | H | E | R |
---|---|---|---|---|---|---|---|---|---|---|---|---|
X | 0 | 5 | 5 | 8 | 13 | 4 | 2 | 8 | 15 | 7 | 4 | 17 |
(5X + 8) | 8 | 33 | 33 | 48 | 73 | 28 | 18 | 48 | 83 | 43 | 28 | 93 |
(5X + 8) mod 26 | 8 | 7 | 7 | 22 | 21 | 2 | 18 | 22 | 5 | 17 | 2 | 15 |
Posledním krokem při šifrování zprávy je vyhledat každou číselnou hodnotu v tabulce pro odpovídající písmena. V tomto příkladu by šifrovaný text byl IHHWVCSWFRCP. Níže uvedená tabulka ukazuje vyplněnou tabulku pro šifrování zprávy v Affine šifře.
prostý text | A | F | F | Já | N | E | C | Já | P | H | E | R |
---|---|---|---|---|---|---|---|---|---|---|---|---|
X | 0 | 5 | 5 | 8 | 13 | 4 | 2 | 8 | 15 | 7 | 4 | 17 |
(5X + 8) | 8 | 33 | 33 | 48 | 73 | 28 | 18 | 48 | 83 | 43 | 28 | 93 |
(5X + 8) mod 26 | 8 | 7 | 7 | 22 | 21 | 2 | 18 | 22 | 5 | 17 | 2 | 15 |
šifrový text | Já | H | H | Ž | PROTI | C | S | Ž | F | R | C | P |
Dešifrování
V tomto příkladu dešifrování je šifrovací text, který bude dešifrován, šifrovací text z příkladu šifrování. Odpovídající dešifrovací funkce je D(y) = 21(y - 8) mod 26, kde A−1 se vypočítá na 21 a b je 8. Chcete-li začít, zapište číselné ekvivalenty ke každému písmenu v šifrovacím textu, jak je uvedeno v tabulce níže.
šifrový text | Já | H | H | Ž | PROTI | C | S | Ž | F | R | C | P |
---|---|---|---|---|---|---|---|---|---|---|---|---|
y | 8 | 7 | 7 | 22 | 21 | 2 | 18 | 22 | 5 | 17 | 2 | 15 |
Dalším krokem je výpočet 21(y − 8), a poté zbytek vezměte, když je výsledek vydělen 26. Následující tabulka ukazuje výsledky obou výpočtů.
šifrový text | Já | H | H | Ž | PROTI | C | S | Ž | F | R | C | P |
---|---|---|---|---|---|---|---|---|---|---|---|---|
y | 8 | 7 | 7 | 22 | 21 | 2 | 18 | 22 | 5 | 17 | 2 | 15 |
21(y − 8) | 0 | −21 | −21 | 294 | 273 | −126 | 210 | 294 | −63 | 189 | −126 | 147 |
21(y - 8) mod 26 | 0 | 5 | 5 | 8 | 13 | 4 | 2 | 8 | 15 | 7 | 4 | 17 |
Posledním krokem při dešifrování ciphertextu je použití tabulky k převodu číselných hodnot zpět na písmena. Prostý text v této dešifrování je AFFINECIPHER. Níže je tabulka s dokončeným posledním krokem.
šifrový text | Já | H | H | Ž | PROTI | C | S | Ž | F | R | C | P |
---|---|---|---|---|---|---|---|---|---|---|---|---|
y | 8 | 7 | 7 | 22 | 21 | 2 | 18 | 22 | 5 | 17 | 2 | 15 |
21(y − 8) | 0 | −21 | −21 | 294 | 273 | −126 | 210 | 294 | −63 | 189 | −126 | 147 |
21(y - 8) mod 26 | 0 | 5 | 5 | 8 | 13 | 4 | 2 | 8 | 15 | 7 | 4 | 17 |
prostý text | A | F | F | Já | N | E | C | Já | P | H | E | R |
Celá abeceda kódována
Aby bylo šifrování a dešifrování rychlejší, lze zašifrovat celou abecedu a vytvořit tak mapu mezi dvěma písmeny čistého textu a šifrovacího textu. V tomto příkladu by byla individuální mapa následující:
dopis v čistém textu | A | B | C | D | E | F | G | H | Já | J | K. | L | M | N | Ó | P | Q | R | S | T | U | PROTI | Ž | X | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
číslo v čistém textu | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
(5X + 8) mod 26 | 8 | 13 | 18 | 23 | 2 | 7 | 12 | 17 | 22 | 1 | 6 | 11 | 16 | 21 | 0 | 5 | 10 | 15 | 20 | 25 | 4 | 9 | 14 | 19 | 24 | 3 |
šifrovací dopis | Já | N | S | X | C | H | M | R | Ž | B | G | L | Q | PROTI | A | F | K. | P | U | Z | E | J | Ó | T | Y | D |
Příklady programování
Následující Krajta kód lze použít k šifrování textu pomocí afinní šifry:
# Vytiskne transpoziční tabulku pro afinní šifru.# a musí být coprime na m = 26.def afinní(A: int, b: int) -> Žádný: pro i v rozsah(26): tisk(chr(i+ord('A')) + ": " + chr(((A*i+b)%26)+ord('A')))# Příklad hovoruafinní(5, 8)