Квадрат Полібія – метод шифрування текстових даних з заміною символів, вперше запропонований грецьким істориком і полководцем Полібієм.
Опис алгоритму
Для шифрування використовується квадратна таблиця в яку вписані всі літери алфавіту. Якщо букв більше за кількість клітинок, то їх можна об’єднувати, або додавати клітинки з довільними знаками.
Для англійського алфавіту квадрат може мати вигляд:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | A | B | C | D | E |
| 2 | F | G | H | I/J | K |
| 3 | L | M | N | O | P |
| 4 | Q | R | S | T | U |
| 5 | V | W | X | Y | Z |
Для українського:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | А | Б | В | Г | Ґ | Д |
| 2 | Е | Є | Ж | З | И | І |
| 3 | Ї | Й | К | Л | М | Н |
| 4 | О | П | Р | С | Т | У |
| 5 | Ф | Х | Ц | Ч | Ш | Щ |
| 6 | Ю | Я | Ь | — | — | — |
Використання ключа
Квадрат можна заповнювати символами в довільному, а не строго алфавітному порядку. Однак таке заповнення важко запам’ятати, тому краще використовувати ключ, який не містить повторень символів(повторення можна ігнорувати програмно), а всі інші – записувати в таблицю в порядку зростання. До прикладу ми використаємо слово-пароль PASSWORD, видалимо з нього повторення і впишемо в таблицю, потім додамо всі інші значення, і отримаємо:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | P | A | S | W | O |
| 2 | R | D | B | C | E |
| 3 | F | G | H | I/J | K |
| 4 | L | M | N | Q | T |
| 5 | U | V | X | Y | Z |
Методи шифрування
Існує декілька варіантів шифрування даних за допомогою квадрата Полібія. Розглянемо найбільш відомі з них на прикладі шифрування латинського тексту з квадратом без використання ключа.
Метод 1. Використання сусіднього знизу символу
В цьому методі для шифрування знаходять вхідну літеру, а в якості коду беруть нижню від неї, розташовану в тому ж стовпчику, або верхню, якщо шуканий символ розміщений в останньому рядку.
| Вхідний текст: | P | O | L | Y | B | I | U | S |
| Шифротекст: | U | T | Q | D | G | O | Z | X |
Метод 2. Перетворення координат
Для початку необхідно виписати координати символів вхідного тексту:
| Літера: | P | O | L | Y | B | I | U | S |
| Вертикальна координата: | 5 | 4 | 1 | 4 | 2 | 4 | 5 | 3 |
| Горизонтальна координата: | 3 | 3 | 3 | 5 | 1 | 2 | 4 | 4 |
Після цього координати зчитуються підряд і перетворюються в текст:
54 ⇨ U, 14 ⇨ Q, 24 ⇨ R, 53 ⇨ P, 33 ⇨ N, 35 ⇨ X, 12 ⇨ F, 44 ⇨ T
UQRPNXFT
Реалізація шифру Полібія
using System;
//метод шифрування з розглянутих вище
public enum Method
{
Method1,
Method2
}
class PolybiusSquare
{
char[,] square;
string alphabet;
Method encryptMethod;
public PolybiusSquare(string alphabet = null, Method cipherMethod = Method.Method1)
{
this.alphabet = alphabet ?? "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
encryptMethod = cipherMethod;
}
//повертає квадрат Полібія
char[,] GetSquare(string key)
{
var newAlphabet = alphabet;
//видаляємо з алфавіту всі символи які містяться в ключі
for (int i = 0; i < key.Length; i++)
{
newAlphabet = newAlphabet.Replace(key[i].ToString(), "");
}
//додаємо пароль на початок алфавіту, а в кінець додаткові знаки
//щоб уникнути пустих комірок
newAlphabet = key + newAlphabet + "0123456789!@#$%^&*)_+-=<>?,.";
//отримуємо розмір сторони квадрату
//округленням квадратного кореню в сторону більшого цілого числа
var n = (int)Math.Ceiling(Math.Sqrt(alphabet.Length));
//створюємо і заповнюємо масив
square = new char[n, n];
var index = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (index < newAlphabet.Length)
{
square[i, j] = newAlphabet[index];
index++;
}
}
}
return square;
}
//пошук символа в двовимірному масиві
bool FindSymbol(char[,] symbolsTable, char symbol, out int column, out int row)
{
var l = symbolsTable.GetUpperBound(0) + 1;
for (int i = 0; i < l; i++)
{
for (int j = 0; j < l; j++)
{
if (symbolsTable[i, j] == symbol)
{
//значення знайдено
row = i;
column = j;
return true;
}
}
}
//якщо нічого не знайшли
row = -1;
column = -1;
return false;
}
public string PolibiusEncrypt(string text, string password)
{
var outputText = "";
var square = GetSquare(password);
var m = text.Length;
switch (encryptMethod)
{
case Method.Method1:
for (int i = 0; i < m; i++)
{
if (FindSymbol(square, text[i], out int columnIndex, out int rowIndex))
{
var newRowIndex = rowIndex == square.GetUpperBound(1)
? 0
: rowIndex + 1;
outputText += square[newRowIndex, columnIndex].ToString();
}
}
break;
case Method.Method2:
var coordinates = new int[m * 2];
for (int i = 0; i < m; i++)
{
if (FindSymbol(square, text[i], out int columnIndex, out int rowIndex))
{
coordinates[i] = columnIndex;
coordinates[i + m] = rowIndex;
}
}
for (int i = 0; i < m * 2; i += 2)
{
outputText += square[coordinates[i + 1], coordinates[i]];
}
break;
}
return outputText;
}
public string PolybiusDecrypt(string text, string password)
{
var outputText = "";
var square = GetSquare(password);
switch (encryptMethod)
{
case Method.Method1:
for (int i = 0; i < text.Length; i++)
{
if (FindSymbol(square, text[i], out int columnIndex, out int rowIndex))
{
var newRowIndex = rowIndex == 0
? square.GetUpperBound(1)
: rowIndex - 1;
outputText += square[newRowIndex, columnIndex].ToString();
}
}
break;
case Method.Method2:
var m = text.Length;
var coordinates = new int[m * 2];
var j = 0;
for (int i = 0; i < m; i++)
{
if (FindSymbol(square, text[i], out int columnIndex, out int rowIndex))
{
coordinates[j] = columnIndex;
coordinates[j + 1] = rowIndex;
j += 2;
}
}
for (int i = 0; i < m; i++)
{
outputText += square[coordinates[i + m], coordinates[i]];
}
break;
}
return outputText;
}
}
Програма для шифрування та розшифрування тексту
using System;
class Program
{
static void Main(string[] args)
{
var polybius = new PolybiusSquare();
Console.Write("Введіть текст: ");
var message = Console.ReadLine().ToUpper();
Console.Write("Введіть пароль(без повторення символів): ");
var pass = Console.ReadLine().ToUpper();
var cipherText = polybius.PolibiusEncrypt(message, pass);
Console.WriteLine("Зашифрований текст: {0}", cipherText);
Console.WriteLine("Розшифрований текст: {0}",
polybius.PolybiusDecrypt(cipherText, pass));
Console.ReadLine();
}
}
Результат роботи програми: