Граючи чесно з криптографією

Шифрування — це процес перетворення відкритого тексту у відповідний шифротекст. Один із методів для цього — шифр Плейфера. Цей шифр був винайдений Чарльзом Вітстоном у 1850-х роках, але названий на честь одного з його найпалкіших прихильників, шотландського вченого Лайона Плейфера. На відміну від багатьох шифрів заміни, шифр Плейфера не шифрує окремі літери, а групи з двох літер, які називаються діграфами. Процес шифрування використовує 5 \times 5 сітку, згенеровану за допомогою секретного ключа, відомого лише двом сторонам, що використовують шифр. Сітка генерується наступним чином: ви записуєте літери ключа, по одній літері на квадрат по рядку в сітці, починаючи з верху. Будь-які повторювані літери в ключі пропускаються. Після цього невикористані літери алфавіту розміщуються в порядку в решті квадратів, причому I та J ділять один квадрат. Наприклад, якщо ключ був "ECNA PROGRAMMING CONTEST", згенерована сітка виглядала б так:

Ви шифруєте діграф, використовуючи наступні правила:

1. Якщо обидві літери знаходяться в одному рядку, замініть кожну на літеру, що знаходиться безпосередньо праворуч (з обгортанням в кінці). Наприклад, використовуючи вищезгадану сітку, діграф відкритого тексту DS шифрується як FB, а AP шифрується як PE.

2. Якщо обидві літери знаходяться в одному стовпці, замініть кожну на літеру, що знаходиться безпосередньо нижче (знову ж таки з обгортанням внизу). Наприклад, PF шифрується як IU (або JU), а WO шифрується як CS.

3. В іншому випадку "пересуньте" перший символ по його рядку, поки він не опиниться в тому ж стовпці, що і другий символ, і зробіть те ж саме для другого символу. Два символи, на яких ви зупинитесь, є зашифрованими символами діграфа. Якщо ви розглядаєте початковий діграф як кути прямокутника в сітці, ви замінюєте їх символами в інших двох кутах. Наприклад, TU шифрується як FH, UT шифрується як HF, а ZC шифрується як WP.

Що відбувається, коли діграф містить одну й ту ж літеру двічі? У початковому шифрі Плейфера ви вставляєте літеру 'X' між двома літерами і продовжуєте шифрування. Ви також використовуєте додаткову 'X' в кінці відкритого тексту, якщо у вас непарна кількість літер. Таким чином, відкритий текст "OOPS" спочатку змінюється на діграфи "OX", "OP" і "SX", а потім шифрується як "GWICBW" (використовуючи сітку вище). Зверніть увагу, що відкритий текст "POOS" не потребує додаткових літер, оскільки дві 'O' не з'являються в одному діграфі.

Ми модифікуємо шифр Плейфера одним простим способом: замість того, щоб завжди використовувати 'X' як вставлену літеру, використовуйте 'A' перший раз, коли потрібна вставка, потім 'B' наступного разу і так далі (хоча ви ніколи не повинні використовувати 'J' як вставлену літеру; просто переходьте від 'I' до 'K'). Коли ви досягнете 'Z', ви повертаєтеся до використання 'A'. Якщо вставлена літера призведе до діграфа з однаковими двома літерами, просто переходьте до наступної вставленої літери. Наприклад, "OOPS" тепер стане потоком діграфів "OA", "OP", "SB" перед шифруванням, а відкритий текст "AABCC" стане потоком діграфів "AB", "AB", "CD", "CE".

Маючи ключ і відкритий текст, ви повинні згенерувати відповідний шифротекст.