Hillova šifra a C#
Co je Hillova šifra?
Hillova šifra je polygramová šifra, kterou v roce 1929 vynalezl Lester S. Hill. Na rozdíl od jednoduchých substitučních šifer pracuje s bloky písmen, typicky o délce 2×2, 3×3 nebo více, a využívá lineární algebru pro šifrování a dešifrování. Hillova šifra je založena na maticových operacích nad modulem velikosti abecedy, typicky 26 pro anglickou abecedu.
Princip fungování
- Bloky písmen – text se rozdělí na bloky stejné délky. Například pro blok 2×2: HELLO → HE LL OX (doplňující písmeno X, aby byl blok úplný).
- Matice klíče – šifrovací klíč je čtvercová matice o velikosti n×n, kde n odpovídá velikosti bloku. Pro šifrování musí být matice invertibilní modulo 26, aby šlo provést i dešifrování.
- Šifrovací operace – blok textu se převede na vektor čísel (A=0, B=1, …, Z=25) a vektor se vynásobí maticí klíče modulo 26. Výsledkem je zašifrovaný blok. Matematicky:
C = K * P mod 26kde C = šifrovaný blok, K = matice klíče, P = vektor otevřeného textu. - Dešifrování – provádí se pomocí inverzní matice klíče modulo 26:
P = K^-1 * C mod 26
Bezpečnost Hillovy šifry
Hillova šifra byla na svou dobu velmi silná, protože polygramové bloky komplikují frekvenční analýzu jednotlivých písmen. Přesto není bezpečná proti moderním útokům, zejména při znalosti části otevřeného textu (tzv. known-plaintext attack), protože lineární algebra umožňuje poměrně rychlé prolomení. Hillova šifra je tedy dnes spíše historickým a didaktickým příkladem.
Příklad šifrování slova HELLO
Použijeme 2×2 matici klíče:
K = | 3 3 |
| 2 5 |
Text: HELLO → bloky: HE LL OX → číselné vektory: [7,4], [11,11], [14,23]
Šifrování:
C1 = [3 3 ; 2 5] * [7;4] mod 26 = [7*3+4*3 ; 7*2+4*5] mod 26 = [33;34] mod 26 = [7;8] → HI C2 = [3 3 ; 2 5] * [11;11] mod 26 = [66;77] mod 26 = [14;25] → OZ C3 = [3 3 ; 2 5] * [14;23] mod 26 = [111;143] mod 26 = [7;13] → HN
Výsledek: HIOZHN
Implementace Hillovy šifry v C#
using System;
namespace HillCipher;
internal class Program
{
private static string Encrypt(string plaintext, int[,] key)
{
var size = key.GetLength(0);
ValidateSquareKey(key);
var text = Normalize(plaintext);
var remainder = text.Length % size;
if (remainder != 0)
{
var pad = size - remainder;
text += new string('X', pad);
}
var nums = TextToNumbers(text);
var outNums = new int[nums.Length];
for (var i = 0; i < nums.Length; i += size)
{
for (var r = 0; r < size; r++)
{
var sum = 0;
for (var c = 0; c < size; c++)
sum += key[r, c] * nums[i + c];
outNums[i + r] = Mod(sum, 26);
}
}
return NumbersToText(outNums);
}
private static string Decrypt(string ciphertext, int[,] key)
{
var size = key.GetLength(0);
ValidateSquareKey(key);
if (!TryInverseKey(key, 26, out var invKey, out var error))
throw new InvalidOperationException($"Key not invertible mod 26: {error}");
var text = Normalize(ciphertext);
if (text.Length % size != 0)
throw new ArgumentException("Ciphertext length must be a multiple of key size.");
var nums = TextToNumbers(text);
var outNums = new int[nums.Length];
for (var i = 0; i < nums.Length; i += size)
{
for (var r = 0; r < size; r++)
{
var sum = 0;
for (var c = 0; c < size; c++)
sum += invKey[r, c] * nums[i + c];
outNums[i + r] = Mod(sum, 26);
}
}
var decrypted = NumbersToText(outNums);
if (decrypted.Length > 0 && decrypted[^1] == 'X')
decrypted = decrypted[..^1];
return decrypted;
}
private static void ValidateSquareKey(int[,] key)
{
if (key.GetLength(0) != key.GetLength(1))
throw new ArgumentException("Key matrix must be square (n x n).");
}
private static bool IsValidKey(int[,] key, out string reason)
{
reason = string.Empty;
try
{
ValidateSquareKey(key);
if (!TryInverseKey(key, 26, out _, out reason))
return false;
return true;
}
catch (Exception ex)
{
reason = ex.Message;
return false;
}
}
private static string Normalize(string text)
{
Span<char> buffer = text.ToUpperInvariant().ToCharArray();
var w = 0;
for (var i = 0; i < buffer.Length; i++)
{
var ch = buffer[i];
if (ch >= 'A' && ch <= 'Z')
buffer[w++] = ch;
}
return new string(buffer[..w]);
}
private static int[] TextToNumbers(string text)
{
var numbers = new int[text.Length];
for (var i = 0; i < text.Length; i++)
numbers[i] = text[i] - 'A';
return numbers;
}
private static string NumbersToText(int[] numbers)
{
var chars = new char[numbers.Length];
for (var i = 0; i < numbers.Length; i++)
chars[i] = (char)(Mod(numbers[i], 26) + 'A');
return new string(chars);
}
private static int Mod(int a, int m)
{
var r = a % m;
return r < 0 ? r + m : r;
}
private static bool TryInverseKey(int[,] key, int mod, out int[,] inverse, out string error)
{
inverse = null!;
error = string.Empty;
var n = key.GetLength(0);
if (key.GetLength(1) != n)
{
error = "Key must be square.";
return false;
}
var det = Mod(Determinant(key, mod), mod);
if (!TryModInverse(det, mod, out var detInv))
{
error = $"det={det} has no inverse modulo {mod}. gcd(det, {mod}) != 1.";
return false;
}
var adj = Adjugate(key, mod);
var inv = new int[n, n];
for (var r = 0; r < n; r++)
for (var c = 0; c < n; c++)
inv[r, c] = Mod(detInv * adj[r, c], mod);
inverse = inv;
return true;
}
private static int Determinant(int[,] m, int mod)
{
var n = m.GetLength(0);
if (n == 1) return Mod(m[0, 0], mod);
if (n == 2)
return Mod(m[0, 0] * m[1, 1] - m[0, 1] * m[1, 0], mod);
if (n == 3)
{
var a = m[0, 0] * (m[1, 1] * m[2, 2] - m[1, 2] * m[2, 1]);
var b = m[0, 1] * (m[1, 0] * m[2, 2] - m[1, 2] * m[2, 0]);
var c = m[0, 2] * (m[1, 0] * m[2, 1] - m[1, 1] * m[2, 0]);
return Mod(a - b + c, mod);
}
var det = 0;
for (var c = 0; c < n; c++)
{
var cofactor = Cofactor(m, 0, c, mod);
det = Mod(det + m[0, 0 + c] * cofactor, mod);
}
return det;
}
private static int Cofactor(int[,] m, int row, int col, int mod)
{
var minor = Minor(m, row, col);
var sign = ((row + col) % 2 == 0) ? 1 : -1;
return Mod(sign * Determinant(minor, mod), mod);
}
private static int[,] Minor(int[,] m, int rowToRemove, int colToRemove)
{
var n = m.GetLength(0);
var res = new int[n - 1, n - 1];
for (int r = 0, rr = 0; r < n; r++)
{
if (r == rowToRemove) continue;
for (int c = 0, cc = 0; c < n; c++)
{
if (c == colToRemove) continue;
res[rr, cc++] = m[r, c];
}
rr++;
}
return res;
}
private static int[,] Adjugate(int[,] m, int mod)
{
var n = m.GetLength(0);
var cof = new int[n, n];
for (var r = 0; r < n; r++)
for (var c = 0; c < n; c++)
cof[r, c] = Cofactor(m, r, c, mod);
var adj = new int[n, n];
for (var r = 0; r < n; r++)
for (var c = 0; c < n; c++)
adj[r, c] = Mod(cof[c, r], mod);
return adj;
}
private static bool TryModInverse(int a, int m, out int inv)
{
inv = 0;
int t = 0, newT = 1;
int r = m, newR = Mod(a, m);
while (newR != 0)
{
var q = r / newR;
var tempT = t - q * newT; t = newT; newT = tempT;
var tempR = r - q * newR; r = newR; newR = tempR;
}
if (r != 1)
return false;
if (t < 0)
t += m;
inv = t % m;
return true;
}
private static void Main(string[] args)
{
var original = "HELLO";
int[,] key = { { 3, 3 }, { 2, 5 } };
if (!IsValidKey(key, out var reason))
{
Console.WriteLine($"Invalid key: {reason}");
return;
}
var encrypted = Encrypt(original, key);
var decrypted = Decrypt(encrypted, key);
Console.WriteLine($"Original: {original}");
Console.WriteLine($"Encrypted: {encrypted}");
Console.WriteLine($"Decrypted: {decrypted}");
}
}
Závěr
Hillova šifra je výborným příkladem matematického přístupu ke kryptografii. Díky práci s bloky písmen a maticemi nabízí vyšší bezpečnost než jednoduché substituční šifry, avšak moderní analytické metody ji dokáží prolomit. Hillova šifra je skvělým didaktickým nástrojem pro pochopení lineární algebry v kontextu šifrování a ukazuje, jak matematické principy mohou být aplikovány v kryptografii.
