Как закалялась сталь современной симметричной криптографии. Глава 1. Классическая криптография

Введение

Современные симметричные шифры, которыми мы пользуемся неявно, но повсеместно, появились в ходе своей многовековой эволюции, в ходе продолжительных и постоянных этапов собственного совершенствования. Каждый новый шаг улучшения приводил одновременно к разрушению старых уязвимых шифров и к порождению новых, более качественных и безопасных. Тем не менее, само разрушение старых алгоритмов всегда двояко свидетельствовало как об их недостатках, которые необходимо было искоренять, так и об их достоинствах, которые нужно было наследовать. В следствие этого, каждый новый, более качественный шифр, представлял собой количественный синтез старых, менее качественных алгоритмов шифрования.

Таким образом, для того, чтобы узнать как современные симметричные алгоритмы шифрования стали такими, какими мы их сейчас видим, нам необходимо углубиться в историю шифров, а именно — в классическую криптографию. Основной нашей целью будет являться выявление примитивов шифрования на базе классических шифров и реструктуризация современных шифров по их композиции. Это даст понимание того, что современные симметричные шифры появились не просто из пустого места, а из структур ранее созданных алгоритмов шифрования.

Данный материал также может быть полезен коллегам преподавателям по предмету КСЗИ (криптографические средства защиты информации) и непосредственно самим студентам при изучении классической и современной симметричной криптографии. По ходу статьи будут прикладываться программные коды на языке Си некоторых шифров классической криптографии. В конце данной статьи также будет указан список литературы по классической и современной криптографии, с которым вы сможете ознакомиться.

Классическая криптография

Если начать с самого начала, с понимания того, как мы пришли к такой жизни, как люди научились создавать современные блочные/поточные шифры, нам необходимо углубиться в историю, а именно во времена, когда криптография ещё не являлась наукой, а была порождением искусства — в классическую криптографию.

Классическая криптография ныне является частью общей криптографии и представляет собой скорее исторический характер, нежели математический или информатический (современная криптография), относительно базисных наук. Таким образом, это говорит о том, что шифры которые будут описаны по ходу повествования, с большей долей вероятности не будут являться надёжными, и к ним нужно будет относиться исключительно как к экспонатам, играющим роль причины возникновения современных симметричных шифров.

Эпоху классической криптографии можно датировать периодом: 3000 л.д.н.э — первая половина XX в.н.э.. Вторая половина XX века связывает себя с рождением криптографии как науки, где не малую роль сыграли следующие факторы: 1) Работа "Теория связи в секретных системах" (К. Шеннон), где были предложены базовые принципы шифров - конфузия и диффузия, было проведено математическое описание ранее существовавших шифров, доказано существование абсолютной криптостойкости на примере шифра Вернама; 2) Стандартизация шифра DES; 3) Появление нового раздела — асимметричной криптографии; 4) Информация о дешифровании Энигмы; 5) Появление криптографических хеш-функций; 6) Появление концепции ЭЦП; 7) Массовое применение в коммуникациях. Таким образом, всё что было в криптографии до второй половины XX века базировалось исключительно на необходимых мерах конфиденциальности передаваемой/хранимой информации, без признаков применения хеширования, ЭЦП, асимметричного распределения ключей и массового применения в коммуникации.

В классической криптографии, в явном виде, существовало два класса шифров — подстановочные и перестановочные. Суть первых сводится к тому, что один символ или группа символов открытого текста заменяется на один символ или группу символов закрытого текста. Суть вторых сводится к тому, что открытый текст "перемешивается" или "перетасовывается" таким образом, что он становится в конечном счёте закрытым. Вследствие этого, основным отличием перестановочных шифров от подстановочных является использование в закрытом тексте тех же символов открытого текста, в ровно таком же количестве и такой же пропорции. Это можно представить в виде следующей схемы.

Подстановочные и перестановочные шифры также делятся на подклассы. Подстановочные шифры содержат пять подклассов, а именно: 1) коды, 2) моноалфавитные, 3) омофонические, 4) полиалфавитные, 5) полиграммные. Перестановочные содержат всего два подкласса: 1) простые и 2) сложные. Всю эту иерархию можно представить в виде следующей схемы.

1. Коды

Являются самыми первыми методами шифрования в истории. Известно, что применялись в Древнем Египте, хоть и не в целях скрытия информации. Их суть заключается в замене (шифровании) целых слов на другие слова, группу символов или числа. Данный вид шифров можно видеть и в настоящем времени, где шпионы не говорят свои настоящие имена, а заменяют их псевдонимами. Ключевой особенностью кодов является существование кодовой книги по принципу "ключ-значение", например Алиса=Змея, Боб=Черепаха, Ева=Ящерица, а само сообщение может звучать так: "Змея-Змея, Ящерица вызывает Черепаху".

Коды могут также хорошо синтезироваться со стеганографией, то-есть не только шифровать сообщение, но и скрывать сам факт существования оригинального сообщения посредством другого (нейтрального) сообщения. Так например, сообщение "Я отнесу подарок часовщику в полдень" может трактоваться так: "Я положу бомбу у часовни в полночь". Если кодовая книга достаточно большая, то она может очень сильно искажать первоначальный смысл сообщения, "затмевая" истинное ложным. Хоть коды и представляют собой самый древний способ шифрования, тем не менее, при хорошо продуманной кодовой книге, результирующий шифр может оказаться сложно взламываемым даже в текущих реалиях.

При всём этом, стоит сказать, что коды не являлись основополагающими методами шифрования для развития классической криптографии, т.к. их основной проблемой являлась и продолжает являться прямая зависимость криптостойкости от размера кодовой книги. Для того времени это становилось (простите за мой каламбур) ключевой проблемой, потому как необходимо было иметь как минимум две копии одной и той же кодовой книги у двух людей на большой дистанции.

2. Моноалфавитные шифры

Являются отправной и ключевой точкой отчёта развития классической криптографии. Самыми старыми представителями подобного подкласса являются шифр Атбаш (~ 500 л.д.н.э.), шифр Полибия (~ III в.д.н.э.) и шифр Цезаря (~ I в.д.н.э.). В отличие от кодов, шифрующих целые слова, как элементарную единицу, моноалфавитные шифры нацелены исключительно на посимвольное шифрование. Также как и коды, моноалфавитные шифры имеют прямую связь между открытой элементарной единицей (слово/символ) и закрытой (слово/число/символ). Данную связь мы будем называть 1к1, где например, если открытый символ A преобразуется в закрытый символом B, то он не может ещё и преобразовываться в закрытый символ C, D, E и т.д. И наоборот, если закрытый символ B был получен из открытого символа A, то он не может быть расшифрован как-либо иначе кроме этого же символа A.

В качестве примера, часто приводят шифр Цезаря. Думаю вряд-ли кто-то с ним не знаком, если человек хоть когда-нибудь начинал увлекаться криптографией. Основной особенностью шифра Цезаря является его ключ, представленный числом сдвигов оригинального алфавита. Так например, предположим, что у нас присутствует ключ K=1 и сообщение M=HELLO, тогда шифрованный результат будет выглядить как IFMMP. Если ключ K=3, то сообщение становится равным KHOOR. Итого, количество всех возможных ключей в шифре Цезаря выражается мощностью алфавита |A| (количеством символов). Если это английский алфавит, то существует всего |A|=26 ключей, если русский, то |A|=33 ключа и т.д. При этом всегда присутствует ключ равный нулю, в итоге количество "нормальных" ключей равно |A|-1.

Часто те кто начинает изучать классическую криптографию, испытывает путаницу в понимании различия между подстановочными и перестановочными шифрами. Иногда (хоть и редко) можно услышать, что шифр Цезаря — это перестановочный шифр. Путаница возникает на моменте вышепоказанной схемы, где действительно происходит обычная перестановка алфавита. Тем не менее, перестановочным шифром является алгоритм, при котором все символы исходного текста также находятся в шифрованном тексте, в ровно такой же пропорции — постоянно, как бы вы часто не меняли ключ шифрования. В контексте же шифра Цезаря, алфавит — это не открытый текст, а полученный алфавит после сдвига — не шифротекст. Можно сказать, более обще, что алфавит в шифре Цезаря — это есть часть ключа, посредством которой мы шифруем все последующие сообщения.

Тем не менее, если подойти к проблеме с другой точки зрения и представить алфавит как открытый текст, то тут уже действительно применяется перестановочный шифр, результатом которого становится ключ для шифра Цезаря. Но само применение перестановочного шифра при генерации ключа для другого шифра (будь то подстановочного или перестановочного) не свидетельствует о том, что другой шифр становится также перестановочным.

#include "encoder.h"

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct caesar_t {
    encoder_t *encoder;
    int32_t key;
} caesar_t;

extern caesar_t *caesar_new(encoder_t *encoder, int32_t k);
extern void caesar_free(caesar_t *caesar);

extern uint8_t *caesar_encrypt(caesar_t *caesar, uint8_t *output, uint8_t *input);
extern uint8_t *caesar_decrypt(caesar_t *caesar, uint8_t *output, uint8_t *input);

static uint8_t *encrypt_string(caesar_t *caesar, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k);

int main(int argc, char *argv[]) {
    uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    uint8_t size_alph = (uint8_t)strlen((char*)alphabet);

    encoder_t *encoder = encoder_new(size_alph);
    encoder_set_alphabet(encoder, alphabet);

    uint8_t message[BUFSIZ];
    uint32_t key = 3;
    strcpy((char*)message, "HELLOWORLD");

    caesar_t *caesar = caesar_new(encoder, key);

    printf("%sn", (char*)caesar_encrypt(caesar, message, message));
    printf("%sn", (char*)caesar_decrypt(caesar, message, message));

    caesar_free(caesar);
    encoder_free(encoder);
    return 0;
}

extern caesar_t *caesar_new(encoder_t *encoder, int32_t k) {
    caesar_t *caesar = (caesar_t*)malloc(sizeof(caesar_t));
   
    caesar->encoder = encoder;
    caesar->key = k;

    return caesar; 
}

extern void caesar_free(caesar_t *caesar) {
    free(caesar);
}

extern uint8_t *caesar_encrypt(caesar_t *caesar, uint8_t *output, uint8_t *input) {
    return encrypt_string(caesar, MODE_ENC, output, input);
}

extern uint8_t *caesar_decrypt(caesar_t *caesar, uint8_t *output, uint8_t *input) {
    return encrypt_string(caesar, MODE_DEC, output, input);
}

static uint8_t *encrypt_string(caesar_t *caesar, encmode_t m, uint8_t *output, uint8_t *input) {
    size_t input_len = strlen((char*)input);
    int encoded_ch, encrypted, flag;

    for (int i = 0; i < input_len; i++) {
        encoded_ch = encoder_encode(caesar->encoder, input[i], &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined char %c;n", input[i]);
            return NULL;
        }

        encrypted = encrypt_code(caesar->encoder, encoded_ch, m*caesar->key); // m = {-1, 1}

        output[i] = encoder_decode(caesar->encoder, encrypted, &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined code %c;n", encrypted);
            return NULL;
        }
    }

    output[input_len] = '';
    return output;
}

static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k) {
    uint8_t size = encoder_get_size_alphabet(encoder);
    return (c+k+size)%size;
}

#ifndef _H_ENCODER
#define _H_ENCODER

#include <stdint.h>

typedef enum encmode_t {
    MODE_ENC =  1,
    MODE_DEC = -1
} encmode_t;

typedef struct encoder_t encoder_t;

extern encoder_t *encoder_new(uint8_t size_alph);
extern void encoder_free(encoder_t *encoder);

extern uint8_t encoder_get_size_alphabet(encoder_t *encoder);
extern void encoder_set_alphabet(encoder_t *encoder, uint8_t *alphabet);

extern uint8_t encoder_encode(encoder_t *encoder, uint8_t ch, int *found);
extern uint8_t encoder_decode(encoder_t *encoder, uint8_t code, int *valid);

#endif

#include "encoder.h"

#include <stdint.h>
#include <stdlib.h>

typedef struct encoder_t {
    uint8_t size_alph;
    uint8_t *alphabet;
} encoder_t;

extern encoder_t *encoder_new(uint8_t size_alph) {
    encoder_t *encoder = (encoder_t*)malloc(sizeof(encoder_t));
    if (encoder == NULL) {
        return NULL;
    }
    encoder->size_alph = size_alph;
    encoder->alphabet = (uint8_t*)malloc(sizeof(uint8_t)*size_alph);
    return encoder;
}

extern void encoder_free(encoder_t *encoder) {
    free(encoder->alphabet);
    free(encoder);
}

extern uint8_t encoder_get_size_alphabet(encoder_t *encoder) {
    return encoder->size_alph;
}

extern void encoder_set_alphabet(encoder_t *encoder, uint8_t *alphabet) {
    for (int i = 0; i < encoder->size_alph; ++i) {
        encoder->alphabet[i] = alphabet[i];
    }
}

extern uint8_t encoder_encode(encoder_t *encoder, uint8_t ch, int *found) {
    for (int i = 0; i < encoder->size_alph; ++i) {
        if (encoder->alphabet[i] == ch) {
            *found = 1;
            return i; 
        }
    }
    *found = 0;
    return 0;
}

extern uint8_t encoder_decode(encoder_t *encoder, uint8_t code, int *valid) {
    if (code >= encoder->size_alph) {
        *valid = 0;
        return 0;
    }
    *valid = 1;
    return encoder->alphabet[code];
}

gcc -Wall -std=c99 main.c encoder.c

./a.out

KHOORZRUOG
HELLOWORLD

Теперь, хоть мы и рассмотрели шифр Цезаря в подробностях, он всё равно является лишь единичным случаем (реализацией) всех моноалфавитных шифров. Благо моноалфавитные шифры можно обобщить. Так например, наивысшая криптостойкость всех моноалфавитных шифров выражается в лице шифра простой подстановки. Можно также в равной степени сказать, что шифр простой подстановки — это и есть целый подкласс в лице моноалфавитных шифров, потому как посредством него могут быть выражены все другие моноалфавитные шифры, будь то шифр Атбаш, шифр Цезаря, шифр Полибия, шифр Бэкона, Аффинный шифр и т.д. Следовательно, если шифр простой подстановки будет обладать определённым рядом уязвимостей, то все они также будут наследоваться побочными шифрами.

Ключом в шифре простой подстановки является сам алфавит, а точнее его подстановочная версия. Так например, предположим, что имеется подстановка, которая указана на схеме выше и открытое сообщение M=HELLO. Результатом шифрования станет зашифрованное сообщение C=ITSSG. В отличие от шифра Цезаря, здесь нет вообще никакой перестановки даже на уровне алфавита, потому как могут существовать символы в подстановочной алфавите, которых не существует в оригинальном, и наоборот. Так например, символа @ не существует в оригинальном алфавите, а символа B не существует в подстановочном алфавите.

Шифр простой подстановки поражает количеством всевозможных ключей, потому как таковое количество становится равным факториалу мощности алфавита |A|!. Для английского алфавита количество ключей равно |A|!=26!=403291461126605635584000000, для русского |A|!=33!=8683317618811886495518194401280000000. Если очень грубо выражать данное количество ключей через сложность вычисления в битовом представлении современных симметричных шифров, то получится, что для английского алфавита сложность составляет ~=2⁸⁸, а для русского ~=2¹²². Для сравнения с текущими реалиями, считается, что длина ключа в 120 бит является вычислительно надёжной к полному перебору подготовленным криптоаналитиком с огромными вычислительными ресурсами.

Но не нужно быть такими наивными. Вышеописанная сложность будет работать лишь при том условии, когда шифр является идеальным в том простом плане, что у него не существует более никаких других уязвимостей, кроме полного перебора. Тем не менее, шифр простой подстановки имеет ряд уязвимостей. Это можно даже доказать на априорных знаниях, где существуют другие методы шифрования, отличные от моноалфавитных. Если бы моноалфавитный шифр являлся бы надёжным, то другие шифры скорее всего бы даже не разрабатывались и не были бы так знамениты в своих применениях. Но всё же, для лучшего понимания уязвимостей, нужно исходить из апостериорных знаний.

У шифра простой подстановки существует два основных вектора нападения — частотный криптоанализ и атака по маске. Первый вектор базируется на том факте, что у каждого алфавита, т.к. он естественный, существует некая избыточность символов, приводящая к тому, что одни символы в тексте встречаются гораздо чаще чем другие. Под текстом нам лучше понимать совокупность всех открытых текстов на выбранном языке. На практике конечно достаточно знать лишь несколько текстов с большим объёмом символов, чтобы выстроить частоту встречаемости каждого отдельного символа приближенную к частотам суммы всех текстов на данном языке. Второй вектор также базируется на факте избыточности символов в открытом тексте, но уже не на уровне каждого отдельного символа, как это предполагает частотный криптоанализ, а на уровне целой группы символов. Под группой символов могут выступать часто повторяемые слова, часто употребляемые приставки, суффиксы, предлоги, окончания, и т.д.

В любом случае, лучше будет попрактиковаться на примере данных векторов нападения. Предположим, что у нас существует следующий шифротекст. Известно, что таковой закрытый текст был получен посредством моноалфавитного шифра. Значит это говорит о том, что сохраняется связь символов между открытым и закрытым текстами 1к1.

AFD RPKOA PX AFKU AFPEJFA DSRDVKHDOA NZU AP UFPN AFD HZOT ZYDOEDU
PX ZAAZQC ZJZKOUA Z UTUADH, ZOM FPN XDN PX AFDH KOYPIYD AFD QPHREADV-
KLDM RPVAKPO PX AFD RVPQDUU. ND QZO ZAAZQC AFD AZWEIZAKPO UPXANZVD, ZOM
ND QZO HPEOA Z MDOKZI-PX-UDVYKQD ZAAZQC WT HZCKOJ AFD ZEAPHZAKQ UTUADH
XZKI ZOM XPVQKOJ AFD DIDQAKPO BEMJDU AP XZII WZQC PO ZO PIMDV, HPVD KOUDQEVD,
RVPQDMEVD XPV ZQQPHRIKUFKOJ AFD UZHD AZUC. KO AFD DOM, DIDQAKPOU ZVD ZWPEA
AVEUA. KX AFD DIDQAKPO BEMJDU ZVD AVEUANPVAFT ZOM QPHRDADOA, AFD DIDQAKPO
NKII WD XZKV. KX AFD DIDQAKPO BEMJDU ZVD OPA AVEUANPVAFT, AFDVD ZVD UP HZOT
NZTU AP VKJ AFD DIDQAKPO AFZA KA KUO’A DYDO NPVAF NPVVTKOJ ZWPEA NFKQF
POD KU HPUA IKCDIT.
AFD KOADVODA ZMMU ODN ANKUAU AP AFKU ZIVDZMT AZOJIDM UCDKO, ZOM AFD
VKUCU KOQVDZUD UKJOKXKQZOAIT. ZII AFD PIM ZAAZQCU VDHZKO, ZOM AFDVD ZVD ZII
AFD ODN ZAAZQCU ZJZKOUA AFD YPAKOJ QPHREADVU, AFD ODANPVC, ZOM AFD
YPADVU’ QPHREADVU (NFKQF ZVD OPA AVEUADM KO ZOT NZT). ZOM MDOKZI-PX-
UDVYKQD ZAAZQCU AFZA MPO’A DSKUA ZJZKOUA QDOAVZIKLDM UTUADHU. DYDO NPVUD,
HPMDVO DIDQAKPOU FZYD OP JVZQDXEI NZT AP XZKI. AFD 2000 MDHPQVZAKQ RVK-
HZVT KO ZVKLPOZ ZIIPNDM KOADVODA YPAKOJ. KX AFDVD NZU Z RVPWIDH, PV DYDO
UEURKQKPO PX Z RVPWIDH, NFZA QPEIM ZVKLPOZ MP? VDWPPA AFD DIDQAKPO ZOM
AVT ZJZKO AFD XPIIPNKOJ NDDC? AFKU VDZUPO ZIPOD KU DOPEJF AP QPOYKOQD
ZOT RUDRFPIPJKUA AP DUQFDN KOADVODA YPAKOJ.

1) Частотный криптоанализ

Первое, что нам необходимо сделать — это вычислить частоты каждого отдельного символа в шифртексте. Для этого мы можем написать небольшую программу на Си, которая самостоятельно будет вычислять все частоты символов в закрытом тексте.

#include <stdio.h>

// Читаем только английские символы большого регистра
#define ALPHA_SIZE 26

int main(void) {
    FILE *file = fopen("encrypted.txt", "r");
    if (file == NULL) {
        return 1;
    }

    int ch, sum;
    int frequency[ALPHA_SIZE] = {0};

    while ((ch = fgetc(file)) != EOF) {
        if ('A' <= ch && ch <= 'Z') {
            frequency[ch-'A']++;
            ++sum;   
        }
    }

    for (int i = 0; i < ALPHA_SIZE; ++i) {
        printf("%c = %5.2f%%;n", 'A'+i, ((double)frequency[i])/((double)sum)*100);
    }

    fclose(file);
    return 0;
}

Получаем на выходе такие частоты. Здесь стоит помнить, что т.к. наш текст не сказать что большой, то и частоты могут перекрывать друг друга. Поэтому, при таком типе криптоанализа, становится необходимо иметь достаточно обширный текст, чтобы исключить как можно больше неопределённостей.

A = 11.49%;
B =  0.28%;
C =  1.29%;
D = 12.50%;
E =  2.11%;
F =  4.50%;
G =  0.00%;
H =  2.21%;
I =  3.77%;
J =  2.02%;
K =  6.89%;
L =  0.37%;
M =  2.85%;
N =  2.57%;
O =  7.90%;
P =  7.90%;
Q =  3.95%;
R =  1.47%;
S =  0.18%;
T =  1.75%;
U =  5.79%;
V =  5.51%;
W =  0.83%;
X =  1.93%;
Y =  1.29%;
Z =  8.64%;

Теперь, второе, что нам необходимо сделать — это сравнить полученные частоты с оригинальными частотами символов английского алфавита.

Из сравнения мы видим, что (с большей долей вероятности) символ открытого текста E либо равен символу A закрытого текста, либо символу D закрытого текста. Оставшийся символ закрытого текста (A или D) должен будет также принадлежать (с большей долей вероятности) одному из первых оставшихся символов оригинального алфавита, то-есть к T, A, O, N или I.

Делаем предположение, что символ E=D по большей частоте встречаемости. На самом деле мы также могли сделать предположение, что символ E=A), потому как расстояние частот между символами A и D невелико. Оставшийся символ A предполагаем следующему символу оригинального алфавита T, иными словами делаем предположение, что T=A. Теперь заменяем все символы A, D в шифротексте на E и T. Получаем следующий текст.

tFe RPKOt PX tFKU tFPEJFt eSReVKHeOt NZU tP UFPN tFe HZOT ZYeOEeU
PX ZttZQC ZJZKOUt Z UTUteH, ZOM FPN XeN PX tFeH KOYPIYe tFe QPHREteV-
KLeM RPVtKPO PX tFe RVPQeUU. Ne QZO ZttZQC tFe tZWEIZtKPO UPXtNZVe, ZOM
Ne QZO HPEOt Z MeOKZI-PX-UeVYKQe ZttZQC WT HZCKOJ tFe ZEtPHZtKQ UTUteH
XZKI ZOM XPVQKOJ tFe eIeQtKPO BEMJeU tP XZII WZQC PO ZO PIMeV, HPVe KOUeQEVe,
RVPQeMEVe XPV ZQQPHRIKUFKOJ tFe UZHe tZUC. KO tFe eOM, eIeQtKPOU ZVe ZWPEt
tVEUt. KX tFe eIeQtKPO BEMJeU ZVe tVEUtNPVtFT ZOM QPHReteOt, tFe eIeQtKPO
NKII We XZKV. KX tFe eIeQtKPO BEMJeU ZVe OPt tVEUtNPVtFT, tFeVe ZVe UP HZOT
NZTU tP VKJ tFe eIeQtKPO tFZt Kt KUO’t eYeO NPVtF NPVVTKOJ ZWPEt NFKQF
POe KU HPUt IKCeIT.
tFe KOteVOet ZMMU OeN tNKUtU tP tFKU ZIVeZMT tZOJIeM UCeKO, ZOM tFe
VKUCU KOQVeZUe UKJOKXKQZOtIT. ZII tFe PIM ZttZQCU VeHZKO, ZOM tFeVe ZVe ZII
tFe OeN ZttZQCU ZJZKOUt tFe YPtKOJ QPHREteVU, tFe OetNPVC, ZOM tFe
YPteVU’ QPHREteVU (NFKQF ZVe OPt tVEUteM KO ZOT NZT). ZOM MeOKZI-PX-
UeVYKQe ZttZQCU tFZt MPO’t eSKUt ZJZKOUt QeOtVZIKLeM UTUteHU. eYeO NPVUe,
HPMeVO eIeQtKPOU FZYe OP JVZQeXEI NZT tP XZKI. tFe 2000 MeHPQVZtKQ RVK-
HZVT KO ZVKLPOZ ZIIPNeM KOteVOet YPtKOJ. KX tFeVe NZU Z RVPWIeH, PV eYeO
UEURKQKPO PX Z RVPWIeH, NFZt QPEIM ZVKLPOZ MP? VeWPPt tFe eIeQtKPO ZOM
tVT ZJZKO tFe XPIIPNKOJ NeeC? tFKU VeZUPO ZIPOe KU eOPEJF tP QPOYKOQe
ZOT RUeRFPIPJKUt tP eUQFeN KOteVOet YPtKOJ.

Третье, что мы делаем — это пытаемся найти в полученном тексте какие-либо похожие слова. Так например, очень часто попадается комбинация символов равная tFe. В английском алфавите, присутствует схожая комбинация и тоже часто встречаемая равная символам THE. Если наши первоначальные предположения на счёт символов T и E оказались верными, то скорее всего сопоставление H=F тоже окажется верным. Это можно проверить на примере косвенных сопоставлений. Так например, в тексте есть ещё комбинация tFeH которая может быть равна THEN или THEM, также слово tFeVe, которое может быть равно THERE или THESE, и tFZt может быть равно THAT. Таким образом, H=F скорее всего точно является верным, т.к. мы нашли достаточно много косвенных совпадений. Заменяем F на H, параллельно заменяем Z на A, и пытаемся поразмыслить теперь над H = N или M, а также V = R или S. Плюс к этому, в полученном тексте начинает вырисовываться слово attaQCU из которого мы можем предположить ATTACKS. Если это верно, то мы расскрываем дополнительные сразу три символа C, K, S, а также ставим однозначную связь V=R (потому как символ S нам стал известен).

the RPKOt PX thKs thPEJht eSRerKHeOt Nas tP shPN the HaOT aYeOEes
PX attack aJaKOst a sTsteH, aOM hPN XeN PX theH KOYPIYe the cPHREter-
KLeM RPrtKPO PX the RrPcess. Ne caO attack the taWEIatKPO sPXtNare, aOM
Ne caO HPEOt a MeOKaI-PX-serYKce attack WT HakKOJ the aEtPHatKc sTsteH
XaKI aOM XPrcKOJ the eIectKPO BEMJes tP XaII Wack PO aO PIMer, HPre KOsecEre,
RrPceMEre XPr accPHRIKshKOJ the saHe task. KO the eOM, eIectKPOs are aWPEt
trEst. KX the eIectKPO BEMJes are trEstNPrthT aOM cPHReteOt, the eIectKPO
NKII We XaKr. KX the eIectKPO BEMJes are OPt trEstNPrthT, there are sP HaOT
NaTs tP rKJ the eIectKPO that Kt KsO’t eYeO NPrth NPrrTKOJ aWPEt NhKch
POe Ks HPst IKkeIT.
the KOterOet aMMs OeN tNKsts tP thKs aIreaMT taOJIeM skeKO, aOM the
rKsks KOcrease sKJOKXKcaOtIT. aII the PIM attacks reHaKO, aOM there are aII
the OeN attacks aJaKOst the YPtKOJ cPHREters, the OetNPrk, aOM the
YPters’ cPHREters (NhKch are OPt trEsteM KO aOT NaT). aOM MeOKaI-PX-
serYKce attacks that MPO’t eSKst aJaKOst ceOtraIKLeM sTsteHs. eYeO NPrse,
HPMerO eIectKPOs haYe OP JraceXEI NaT tP XaKI. the 2000 MeHPcratKc RrK-
HarT KO arKLPOa aIIPNeM KOterOet YPtKOJ. KX there Nas a RrPWIeH, Pr eYeO
sEsRKcKPO PX a RrPWIeH, Nhat cPEIM arKLPOa MP? reWPPt the eIectKPO aOM
trT aJaKO the XPIIPNKOJ Neek? thKs reasPO aIPOe Ks eOPEJh tP cPOYKOce
aOT RseRhPIPJKst tP escheN KOterOet YPtKOJ.

Из полученного результата мы также начинаем видеть ещё новые слова, например rKsks может быть равно risks (это подкрепляется также thKs => this), Neek может быть равно week (это подкрепляется также Nhat => what и Nas => was), reasPO может быть равно reason (это подкрепляется также RrPcess => process и tP => to, и eYeO => even). Все полученные комбинации также пытаемся заменить. Если будет что-то неверно, может попытаться вернуться назад.

Получаем уже такой текст, где его большая часть читается даже без последующего анализа и сравнения. Мы открыли следующие символы: t, h, e, p, o, i, n, t, o, r, v, w, c, k, s. В сумме 15, что представляет уже большую часть символов английского алфавита, более 50%. Далее, можете продолжить дешифровывать текст самостоятельно.

the point oX this thoEJht eSperiHent was to show the HanT avenEes
oX attack aJainst a sTsteH, anM how Xew oX theH invoIve the coHpEter-
iLeM portion oX the process. we can attack the taWEIation soXtware, anM
we can HoEnt a MeniaI-oX-service attack WT HakinJ the aEtoHatic sTsteH
XaiI anM XorcinJ the eIection BEMJes to XaII Wack on an oIMer, Hore insecEre,
proceMEre Xor accoHpIishinJ the saHe task. in the enM, eIections are aWoEt
trEst. iX the eIection BEMJes are trEstworthT anM coHpetent, the eIection
wiII We Xair. iX the eIection BEMJes are not trEstworthT, there are so HanT
waTs to riJ the eIection that it isn’t even worth worrTinJ aWoEt which
one is Host IikeIT.
the internet aMMs new twists to this aIreaMT tanJIeM skein, anM the
risks increase siJniXicantIT. aII the oIM attacks reHain, anM there are aII
the new attacks aJainst the votinJ coHpEters, the network, anM the
voters’ coHpEters (which are not trEsteM in anT waT). anM MeniaI-oX-
service attacks that Mon’t eSist aJainst centraIiLeM sTsteHs. even worse,
HoMern eIections have no JraceXEI waT to XaiI. the 2000 MeHocratic pri-
HarT in ariLona aIIoweM internet votinJ. iX there was a proWIeH, or even
sEspicion oX a proWIeH, what coEIM ariLona Mo? reWoot the eIection anM
trT aJain the XoIIowinJ week? this reason aIone is enoEJh to convince
anT psephoIoJist to eschew internet votinJ.

P.S. На данном моменте (или даже раньше) могло возникнуть сомнение, что этот текст я уже знал и поэтому так легко его дешифровывал. На самом деле так и было, примерно пол года назад, пока я не удалил все открытые тексты. На моём ПК (а точнее на сервере) остались лишь самостоятельные работы для студентов, но без оригинальных текстов. Так что можно сказать, что это дешифрование было спонтанным.

2) Атака по маске

Данный вид криптоаналитической атаки схож по своему методу на частотный криптоанализ, но лишь с тем отличием, что таковой смотрит не на частоты встречаемости каждого отдельного символа, а на частоты встречаемости целых слов в тексте, или на частоты появления приставок, суффиксов, предлогов, окончаний и т.д. Следовательно, он заменяет два первых этапа частотного криптоанализа на этап сравнивания групп символов. В некой степени данный вид атаки является более простым и быстрым, если вы знакомы с языком, на котором написан текст.

Предположим, что у нас также существует тот самый текст. Забудем о том, что мы его смогли успешно дешифровать.

AFD RPKOA PX AFKU AFPEJFA DSRDVKHDOA NZU AP UFPN AFD HZOT ZYDOEDU
PX ZAAZQC ZJZKOUA Z UTUADH, ZOM FPN XDN PX AFDH KOYPIYD AFD QPHREADV-
KLDM RPVAKPO PX AFD RVPQDUU. ND QZO ZAAZQC AFD AZWEIZAKPO UPXANZVD, ZOM
ND QZO HPEOA Z MDOKZI-PX-UDVYKQD ZAAZQC WT HZCKOJ AFD ZEAPHZAKQ UTUADH
XZKI ZOM XPVQKOJ AFD DIDQAKPO BEMJDU AP XZII WZQC PO ZO PIMDV, HPVD KOUDQEVD,
RVPQDMEVD XPV ZQQPHRIKUFKOJ AFD UZHD AZUC. KO AFD DOM, DIDQAKPOU ZVD ZWPEA
AVEUA. KX AFD DIDQAKPO BEMJDU ZVD AVEUANPVAFT ZOM QPHRDADOA, AFD DIDQAKPO
NKII WD XZKV. KX AFD DIDQAKPO BEMJDU ZVD OPA AVEUANPVAFT, AFDVD ZVD UP HZOT
NZTU AP VKJ AFD DIDQAKPO AFZA KA KUO’A DYDO NPVAF NPVVTKOJ ZWPEA NFKQF
POD KU HPUA IKCDIT.
AFD KOADVODA ZMMU ODN ANKUAU AP AFKU ZIVDZMT AZOJIDM UCDKO, ZOM AFD
VKUCU KOQVDZUD UKJOKXKQZOAIT. ZII AFD PIM ZAAZQCU VDHZKO, ZOM AFDVD ZVD ZII
AFD ODN ZAAZQCU ZJZKOUA AFD YPAKOJ QPHREADVU, AFD ODANPVC, ZOM AFD
YPADVU’ QPHREADVU (NFKQF ZVD OPA AVEUADM KO ZOT NZT). ZOM MDOKZI-PX-
UDVYKQD ZAAZQCU AFZA MPO’A DSKUA ZJZKOUA QDOAVZIKLDM UTUADHU. DYDO NPVUD,
HPMDVO DIDQAKPOU FZYD OP JVZQDXEI NZT AP XZKI. AFD 2000 MDHPQVZAKQ RVK-
HZVT KO ZVKLPOZ ZIIPNDM KOADVODA YPAKOJ. KX AFDVD NZU Z RVPWIDH, PV DYDO
UEURKQKPO PX Z RVPWIDH, NFZA QPEIM ZVKLPOZ MP? VDWPPA AFD DIDQAKPO ZOM
AVT ZJZKO AFD XPIIPNKOJ NDDC? AFKU VDZUPO ZIPOD KU DOPEJF AP QPOYKOQD
ZOT RUDRFPIPJKUA AP DUQFDN KOADVODA YPAKOJ.

Первое, на что наше внимание теперь должно быть приковано, так это к структуре самого текста. Нам нужно найти наибольшее количество закономерностей. Так например, группа символов AFD очень часто встречается в начале предложений, что может быть равно группе символов THE английского алфавита. Если это так, то мы сразу сможем узнать три правильных символа. Далее, моё внимание приковывают предложения с вопросами, потому как в английском языке вопросительные предложения строятся немного по другому в сравнении с обычными, а также имеют вспомогательные слова. Предположим, что в этих предложениях могут существовать слова WHAT, WHY, WHERE, HOW и т.д. Под WHAT может подходить шифртекст NFZA, т.к. никакие четыре символа не совпадают и находятся в вопросительном предложении. Далее очень часто в тексте встречается одиночный символ Z, который может быть равен символу A в английском тексте, который также подкрепляет гипотезу о WHAT=NFZA.

После того, как мы открыли несколько слов, нам будет легче продолжиать взламывать шифртекст, но уже посимвольно, как ранее мы это делали в частотном криптоанализе. На данном этапе, нам известны уже следующие символы: t, h, e, a, w. Если взглянуть вновь на частотный криптоанализ, то нам для этого текста было достаточно всего двух открытых символов для взлома всего текста, а именно T и E. Так что с полученным результатом также вполне реально доломать весь оставшийся шифртекст.

#include "encoder.h"

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct simple_substitution_t {
    encoder_t *orig_encoder;
    encoder_t *encr_encoder;
} simple_substitution_t;

extern simple_substitution_t *simple_substitution_new(encoder_t *orig_encoder, encoder_t *encr_encoder);
extern void simple_substitution_free(simple_substitution_t *simple_substitution);

extern uint8_t *simple_substitution_encrypt(simple_substitution_t *simple_substitution, uint8_t *output, uint8_t *input);
extern uint8_t *simple_substitution_decrypt(simple_substitution_t *simple_substitution, uint8_t *output, uint8_t *input);

static uint8_t *encrypt_string(simple_substitution_t *simple_substitution, encmode_t m, uint8_t *output, uint8_t *input);

int main(int argc, char *argv[]) {
    uint8_t alphabet_orig[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    uint8_t size_alph_orig = (uint8_t)strlen((char*)alphabet_orig);
    encoder_t *encoder_orig = encoder_new(size_alph_orig);
    encoder_set_alphabet(encoder_orig, alphabet_orig);

    uint8_t alphabet_encr[] = "QWERTYUIOPASDFGHJKLZXCVBNM";
    uint8_t size_alph_encr = (uint8_t)strlen((char*)alphabet_encr);
    encoder_t *encoder_encr = encoder_new(size_alph_encr);
    encoder_set_alphabet(encoder_encr, alphabet_encr);

    uint8_t message[BUFSIZ];
    strcpy((char*)message, "HELLOWORLD");

    simple_substitution_t *simple_substitution = simple_substitution_new(encoder_orig, encoder_encr);

    printf("%sn", (char*)simple_substitution_encrypt(simple_substitution, message, message));
    printf("%sn", (char*)simple_substitution_decrypt(simple_substitution, message, message));

    simple_substitution_free(simple_substitution);
    encoder_free(encoder_orig);
    encoder_free(encoder_encr);
    return 0;
}

extern simple_substitution_t *simple_substitution_new(encoder_t *orig_encoder, encoder_t *encr_encoder) {
    simple_substitution_t *simple_substitution = (simple_substitution_t*)malloc(sizeof(simple_substitution_t));
   
    simple_substitution->orig_encoder = orig_encoder;
    simple_substitution->encr_encoder = encr_encoder;

    return simple_substitution; 
}

extern void simple_substitution_free(simple_substitution_t *simple_substitution) {
    free(simple_substitution);
}

extern uint8_t *simple_substitution_encrypt(simple_substitution_t *simple_substitution, uint8_t *output, uint8_t *input) {
    return encrypt_string(simple_substitution, MODE_ENC, output, input);
}

extern uint8_t *simple_substitution_decrypt(simple_substitution_t *simple_substitution, uint8_t *output, uint8_t *input) {
    return encrypt_string(simple_substitution, MODE_DEC, output, input);
}

static uint8_t *encrypt_string(simple_substitution_t *simple_substitution, encmode_t m, uint8_t *output, uint8_t *input) {
    encoder_t *encoder_read, *encoder_write;
    size_t input_len = strlen((char*)input);
    int encoded_ch, flag;

    switch (m) {
        case MODE_ENC:
            encoder_read = simple_substitution->orig_encoder;
            encoder_write = simple_substitution->encr_encoder;
        break;
        case MODE_DEC:
            encoder_read = simple_substitution->encr_encoder;
            encoder_write = simple_substitution->orig_encoder;
        break;
    }

    for (int i = 0; i < input_len; i++) {
        encoded_ch = encoder_encode(encoder_read, input[i], &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined char %c;n", input[i]);
            return NULL;
        }
        output[i] = encoder_decode(encoder_write, encoded_ch, &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined code %c;n", encoded_ch);
            return NULL;
        }
    }

    output[input_len] = '';
    return output;
}

ITSSGVGKSR
HELLOWORLD

В итоге, на заре окончания использования моноалфавитных шифров уже было всем известно, что таковой подкласс шифров ни в коем случае нельзя считать надёжным. Хоть у него и вправду может существовать огромное количество ключей, тем не менее, у него существует и ряд значительных уязвимостей, позволяющих взламывать закрытый текст за считанные минуты. Люди того времени уже понимали на чём зиждется данная уязвимость, а именно на связи 1к1. Если такую связь скрыть, размыть или исключить, то частотный криптоанализ и атака по маске будут уже не такими эффективными орудиями в руках криптоаналитиков.

3. Омофонические шифры

Представляют собой развитие моноалфавитного подкласса, позволяющего шифровать один и тот же символ несколькими способами, тем самым образуя новый тип связи 1кN. Иными словами, теперь становится возможным отождествлять символ A одновременно с несколькими символами, как например B, C и D. При шифровании символа A случайным образом выбирается символ из данного множества, что как следствие, может порождать закрытый текст вида BCDBD из открытого текста AAAAA. Тем не менее, остаётся и в омофоническом шифре "наследие" моноалфавитного, а именно расшифрование становится всегда однозначным относительно множества закрытых символов. Так например, если A способен преобразовываться в B, C или D, то B, C и D не могут расшифровываться никак иначе как символ A. Поэтому связь и является однонаправленной. Представителем подобных шифров является книжный шифр (не путать с книжным шифром из стеганографии).

Главной целью омофонических шифров является сокрытие частот встречаемости каждого отдельного символа посредством их выравнивания. Так предположим, что существует алфавит всего из трёх символов {A, B, C}. Предположим, что в текстах на этом языке, A=X (где X - шифросимвол) встречается в 50% случаев, а символы B=Y и C=Z в 25% случаев каждый. В моноалфавитном шифре частота символа X всегда бы сохранялась и была равна частоте символа A открытого текста, из-за чего могла бы применяться атака частотным криптоанализом. Омофонический же шифр размывает частотную закономерность посредством "деления" символа на несколько символов шифртекста. Так например, если A разделить на два символа Q и W, и при шифровании с равной и случайной вероятностью выбирать один из них, то символы Q и W, вместе с символами Y и Z будут иметь вероятность встречаемости по 25% каждый. Из этого следует, что применять на шифртекст с правильной омофонической заменой атаку частотного криптоанализа более становится невозможно.

Омофонический шифр, искореняя атаку частотным криптоанализом, вдобавок и повышает количество возможных ключей при полном переборе. На первый взгляд кажется, что вот он, идеальный шифр, у которого более не существует уязвимостей, а полный перебор просто неосуществим на практике. Но вы ведь ещё не забыли об атаке по маске? Хоть атака по маске и представляет собой некий частный случай атаки частотного криптоанализа, но за счёт того, что атака по маске анализирует закономерность на уровне групп символов, то и векторы нападения начинают немного отличаться. Эта атака становится губительной для омофонических шифров.

Основная суть атаки сводится к тому, что омофонический шифр (пока не берём в расчёт книжный шифр) имеет тенденцию повторять шифросимволы, хоть и с равной вероятностью. Если открытый текст будет достаточно объёмным, то таким же объёмным будет и шифртекст. Из-за объёмности в тексте будут часто повторяться одни и те же группы символов. Так например, предположим, что существует английский алфавит, где нашей маленькой задачей будет являться сокрытие огромного количества групп символов THE омофоническим шифром. И в чём же заключается проблема? Проблема заключается в том, что количество всех возможных комбинаций омофонических подстановок ограничено, что может приводить рано или поздно к повторам одних и тех же групп. Если T = (# или B), H = (2 или O), E = (& или 5), то в лучшем (именно в лучшем) случае группа символов THE повторит себя спустя 2³=8 раз, т.к. для такой группы символов существует именно 8 разных способов написания: #2&, #25, #O&, #O5, B2&, B25, BO&, BO5. Таким образом, криптоаналитик всё равно будет видеть частоты встречаемости, хоть и не каждого отдельного символа, но именно повторяющихся групп символов.

Но теперь представьте, что если количество омофонических подстановок для каждого отдельного символа растёт очень быстро? Так например, если для каждого символа существует 8 подстановок, то комбинация THE (опять таки в лучшем случае) повторится спустя 8³=512 использований. Если выбрано 32 подстановки, то 32³=32 768 и т.д. Можно сказать, что не словами едины и криптоаналитик начнёт искать также закономерности повторений не только в словах, но и в приставках, суффиках, предлогах, окончаниях и т.п. А теперь предположим, что если каждый отдельный зашифрованный символ будет обладать своей уникальной омофонической заменой? Иными словами, если вы будете шифровать много одинаковых символов AAA...AAA, то всегда будете получать разные символы #$8...0JD. Можно конечно сказать, что количество символов в какой-либо кодировке ограничено, но ничто не мешает шифровать символы числами, подобия (31)(222)(1)...(3123)(4454)(910). В таком случае шифрования, какие бы то ни было атаки окажутся бессмысленными, будь то частотный криптоанализ, т.к. частоты всегда будут априори выравнены из-за неповторяемости каждого отдельного символа, будь то атака по маске, т.к. не будет связей групп между собой.

Но существует ли такой омофонический шифр? Существует — это книжный шифр. Его суть крайне проста и может быть описана следующим алгоритмом действий.

1. Взять случайную книгу, статью или какой-либо массивный текст.

2. Взять открытый символ оригинального текста.

3. Открыть книгу и найти там этот символ.

4. Записать в качестве шифрсимвола (страницу/строку/позицию) этого символа.

5. Зачеркнуть этот символ в книге и никогда больше его не применять.

6. Перейти на пункт 2, если нужно продолжить шифрование.

Таким образом, единственная атака на подобный вид омофонических шифров сводится к нахождению оригинальной книги (ключа) для возможности расшифрования. Иными словами, единственной атакой на книжный шифр становится атака полным перебором всех возможных ключей. С одной стороны действительно можно сказать, что это и есть идеальный шифр, но стоит учесть несколько факторов: 1) книги, статьи, текста нужно как-то уметь передавать, т.к. они могут быть достаточно большими в размерах; 2) если брать теоретически все возможные книги в мире и на основе них высчитывать количество ключей, то получится всего ~=130 000 000 возможных ключей (https://www.vesti.ru/article/2053203), что составляет примерно всего ~=2²⁷ сложности перебора. Что с первым, что со вторым пунктом действительно можно поспорить. Так например, по первому пункту, можно выбирать малую книгу, статью или какой-либо другой текст, но итоговый шифртекст также будет малым. Также со вторым пунктом, можно учитывать не только книги, но и статьи, а также всеразличные другие тексты, но 1) это может непозволить шифровать большие сообщения и 2) оставшиеся большие тексты также будут ограничены в количестве, что не на сильно повысит итоговое количество ключей.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct book_cipher_t {
    FILE *book_key;
    uint32_t msg_size;
} book_cipher_t;

extern book_cipher_t *book_cipher_new(FILE *book_key, uint32_t msg_size);
extern void book_cipher_free(book_cipher_t *book_cipher);

extern uint32_t *book_cipher_encrypt(book_cipher_t *book_cipher, uint32_t *output, uint8_t *input);
extern uint8_t *book_cipher_decrypt(book_cipher_t *book_cipher, uint8_t *output, uint32_t *input);

static int find_position(uint32_t *positions, uint32_t n, uint32_t pos);

int main(int argc, char *argv[]) {
    uint32_t encrypted[BUFSIZ];
    uint8_t message[BUFSIZ];
    
    strcpy((char*)message, "hello, world");

    FILE *book_key = fopen("book_key.txt", "r");
    if (book_key == NULL) {
        return 1;
    }

    book_cipher_t *book_cipher = book_cipher_new(book_key, strlen((char*)message));

    book_cipher_encrypt(book_cipher, encrypted, message);
    for (int i = 0; i < book_cipher->msg_size; ++i) {
        printf("%d ", encrypted[i]);
    }
    printf("n");

    printf("%sn", (char*)book_cipher_decrypt(book_cipher, message, encrypted));

    book_cipher_free(book_cipher);
    fclose(book_key);
    return 0;
}

extern book_cipher_t *book_cipher_new(FILE *book_key, uint32_t msg_size) {
    book_cipher_t *book_cipher = (book_cipher_t*)malloc(sizeof(book_cipher_t));
   
    book_cipher->book_key = book_key;
    book_cipher->msg_size = msg_size;

    return book_cipher; 
}

extern void book_cipher_free(book_cipher_t *book_cipher) {
    free(book_cipher);
}

extern uint32_t *book_cipher_encrypt(book_cipher_t *book_cipher, uint32_t *output, uint8_t *input) {
    uint32_t file_pos, positions[book_cipher->msg_size];
    uint32_t output_i = 0, size_positions = 0;
    int ch;

    for (int i = 0; i < book_cipher->msg_size; ++i) {
        int ch_found = 0;
        while((ch = fgetc(book_cipher->book_key)) != EOF) {
            file_pos = ftell(book_cipher->book_key);
            if (ch == input[i] && !find_position(positions, book_cipher->msg_size, file_pos)) {
                output[output_i++] = file_pos;
                positions[size_positions++] = file_pos;
                fseek(book_cipher->book_key, 0, SEEK_SET);
                ch_found = 1;
                break;
            }
        }
        if (!ch_found) {
            output[output_i++] = 0;
            fprintf(stderr, "char '%c' undefinedn", input[i]);
            fseek(book_cipher->book_key, 0, SEEK_SET);
        }
    }

    return output;
}

extern uint8_t *book_cipher_decrypt(book_cipher_t *book_cipher, uint8_t *output, uint32_t *input) {
    for (int i = 0; i < book_cipher->msg_size; ++i) {
        if (input[i] == 0) {
            fprintf(stderr, "found null charn");
            continue;
        }
        fseek(book_cipher->book_key, input[i]-1, SEEK_SET);
        output[i] = fgetc(book_cipher->book_key);
    }
    return output;
}

static int find_position(uint32_t *positions, uint32_t n, uint32_t pos) {
    for (int i = 0; i < n; ++i) {
        if (positions[i] == pos) {
            return 1;
        }
    }
    return 0;
}

Love is too young to know what conscience is,
Yet who knows not conscience is born of love?
Then, gentle cheater, urge not my amiss,
Lest guilty of my faults thy sweet self prove.
For, thou betraying me, I do betray
My nobler part to my gross body’s treason:
My soul doth tell my body that he may
Triumph in love; flesh stays no farther reason;
But rising at thy name doth point out thee
As his triumphant prize. Proud of this pride,

He is contented thy poor drudge to be,
To stand in thy affairs, fall by thy side.
No want of conscience hold it that I call
Her ‘love’ for whose dear love I rise and fall.

28 4 87 103 2 45 5 25 10 81 142 207 
hello, world

В результате, наивысшая криптостойкость омофонических шифров становится противоречивой сущностью, потому как количественная характеристика ключа начинает идти в открытое противоречие с качеством криптостойкости самого алгоритма шифрования. Таким образом, с одной стороны, появляется уязвимость атаки по маске, но при этом исключается атака перебором, с другой стороны исключается уязвимость атаки по маске, но появляется возможность полного перебора ключей. В конечном счёте приходится выбирать определённые компромиссы.

4. Полиалфавитные шифры

Являются дальнейшим развитием моноалфавитных, а также омофонических шифров, представляя новый тип связи NкN. В отличие от омофонических шифров, способных представлять множественную вариативность исключительно операции шифрования, полиалфавитные шифры способны представлять двунаправленную связь между открытым и закрытым текстом. Так например, становится возможным замена символа A на B или C и одновременно с этим, символ B может расшифровываться как символ A или C (такое же утверждение справедливо для символа C). Примерами подобных шифров являются диск Альберти, шифр Гронсвельда, шифр Виженера, шифр Вернама, шифр Тритемиуса.

Разберём для начала классический полиалфавитный шифр — шифр Виженера. Данный алгоритм шифрования представляет собой более общий случай шифра Цезаря, переводя ключ-число в ключ-строку. Каждый отдельный символ ключ-строки исполняет ту же самую функцию, что и ключ-число в шифре Цезаря для конкретно выбранного символа. Так например, предположим, что у нас существует ключ K=QWE и сообщение M=HELLO. Само шифрование осуществляется таким образом, что ключ начинает кодироваться в числовое представление, где символ ключа становится позицией оригинального алфавита. Так например, если бы ключ был равен ABC...XYZ, то он бы закодировался в 0,1,2,...,23,24,25 соответственно (нумерация начинается с нуля). Таким образом, ключ QWE становится равен 16,22,4. Далее, начинается этап дублирования ключа до тех пор, пока он не станет больше или равен количеству символов в открытом тексте. Следовательно, продублированный ключ станет равен 16,22,4,16,22. В конечном итоге, при шифровании происходит наложение ключа с открытым текстом, а операцией наложения становится сдвиг накладываемого символа на количество позиций накладываемого ключа, иными словами шифр Цезаря. Всё это можно описать следующим образом.

Алфавит = ABCDEFGHIJKLMNOPQRSTUVWXYZ
Открытый текст = HELLO

Шифрование:
H >> 16 = X (применяется шифр Цезаря с K=16)
E >> 22 = A (применяется шифр Цезаря с K=22)
L >> 4  = P (применяется шифр Цезаря с K=4)
L >> 16 = B (применяется шифр Цезаря с K=16)
O >> 22 = K (применяется шифр Цезаря с K=22)

Закрытый текст = XAPBK

Шифр Виженера также может быть представлен таблицей NxN, где N - количество символов алфавита. Так, на примере английского алфавита, это выглядит следующим образом.

Чтобы зашифровать определённый символ с определённым ключом, необходимо будет найти его на пересечении данной матрицы. Если взять наш ключ K=QWE и сообщение M=HELLO, а также предположить, что слева по вертикали будут находиться символы ключа, а сверху по горизонтали символы сообщения, то на пересечении символов мы будем находить те же шифросимволы: Q+H=X, W+E=A, E+L=P, Q+L=B, W+O=K. Итого, XAPBK, что и требовалось ожидать.

Шифр Виженера при этом также является частным случаем более общего описания полиалфавитных шифров. Так например, в более абстрактном виде для полиалфавитного шифра не важен как таковой конкретный моноалфавитный шифр. Наиболее абстрактная, и как следствие, общая версия описания полиалфавитных шифров может быть представлена множественным применением шифров простой подстановки с разными ключами.

Может ложно показаться, что шифр Виженера является надёжным шифром, т.к. относится к типу связи NкN. Тем не менее, полиалфавитные шифры в массе своей наследуют уязвимости моноалфавитных шифров, но не таким явным образом. Так например, если взять вышеописанный случай шифрования с ключом K=QWE и сгруппировать полученный шифртекст C по группам символов типа (C[0], C[3], C[6], ..., C[3k]), (C[1], C[4], C[7], ..., C[3k+1]) и (C[2], C[5], C[8], ..., C[3k+2]), где значение в скобках - это нумерация символа в шифртексте C, то каждая группа будет обладать собственным смещением. Так группа шифросимволов (C[0], C[3], C[6], ..., C[3k]) обладает смещением равным 16, группа (C[1], C[4], C[7], ..., C[3k+1]) обладает смещением равным 22, а группа (C[2], C[5], C[8], ..., C[3k+2]) обладает смещением равным 4. Иными словами, каждая группа символов по отдельности была зашифрована просто шифром Цезаря с определённым ключом. И так, если нам известны все эти группы, то мы становимся способными применить частотный криптоанализ на каждую группу по отдельности, восстанавливая открытые символы. После того, как был применён частотный криптоанализ на каждую группу происходит этап слияния всех групп вновь в собранный текст. Если все или большая часть частот успешно подошла, то можно легко будет прочитать открытый текст.

Также в шифре Виженера остаётся уязвимость к атаке по маске. Так например, если текущая позиция ключа при шифровании открытого текста начинает совпадать с уже продублированным блоком открытого текста, который был зашифрован с точно такой же позицией ключа, то шифрованным результат данного блока будет аналогичным. По такому признаку как раз и становится возможным определять количество групп по шифртексту, или вернее сказать количество непродублированных символов ключа.

#include "encoder.h"

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct vigenere_t {
    encoder_t *encoder;
    uint8_t *key;
    uint32_t key_size;
} vigenere_t;

extern vigenere_t *vigenere_new(encoder_t *encoder, uint8_t *key);
extern void vigenere_free(vigenere_t *vigenere);

extern uint8_t *vigenere_encrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input);
extern uint8_t *vigenere_decrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input);

static uint8_t *encrypt_string(vigenere_t *vigenere, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k);

int main(int argc, char *argv[]) {
    uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    uint8_t size_alph = (uint8_t)strlen((char*)alphabet);

    encoder_t *encoder = encoder_new(size_alph);
    encoder_set_alphabet(encoder, alphabet);

    uint8_t message[BUFSIZ];
    uint8_t key[] = "QWE";
    strcpy((char*)message, "HELLOWORLD");

    vigenere_t *vigenere = vigenere_new(encoder, key);

    printf("%sn", (char*)vigenere_encrypt(vigenere, message, message));
    printf("%sn", (char*)vigenere_decrypt(vigenere, message, message));

    vigenere_free(vigenere);
    encoder_free(encoder);
    return 0;
}

extern vigenere_t *vigenere_new(encoder_t *encoder, uint8_t *key) {
    vigenere_t *vigenere = (vigenere_t*)malloc(sizeof(vigenere_t));
   
    vigenere->encoder = encoder;
    vigenere->key_size = strlen((char*)key);

    vigenere->key = (uint8_t*)malloc(sizeof(uint8_t)*vigenere->key_size+1);
    strcpy((char*)vigenere->key, (char*)key);

    return vigenere; 
}

extern void vigenere_free(vigenere_t *vigenere) {
    free(vigenere->key);
    free(vigenere);
}

extern uint8_t *vigenere_encrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input) {
    return encrypt_string(vigenere, MODE_ENC, output, input);
}

extern uint8_t *vigenere_decrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input) {
    return encrypt_string(vigenere, MODE_DEC, output, input);
}

static uint8_t *encrypt_string(vigenere_t *vigenere, encmode_t m, uint8_t *output, uint8_t *input) {
    size_t input_len = strlen((char*)input);
    int encoded_ch, encrypted, key, flag;

    for (int i = 0; i < input_len; i++) {
        encoded_ch = encoder_encode(vigenere->encoder, input[i], &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined char %c;n", input[i]);
            return NULL;
        }

        key = encoder_encode(vigenere->encoder, vigenere->key[i%vigenere->key_size], &flag);
        if (flag == 0) {
            fprintf(stderr, "encode key char %c;n", vigenere->key[i%vigenere->key_size]);
            return NULL;
        }

        encrypted = encrypt_code(vigenere->encoder, encoded_ch, m*key); // m = {-1, 1}

        output[i] = encoder_decode(vigenere->encoder, encrypted, &flag);
        if (flag == 0) {
            fprintf(stderr, "undefined code %c;n", encrypted);
            return NULL;
        }
    }

    output[input_len] = '';
    return output;
}

static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k) {
    uint8_t size = encoder_get_size_alphabet(encoder);
    return (c+k+size)%size;
}

XAPBKAENPT
HELLOWORLD

Хоть такие уязвимости в шифре Виженера и присутствуют, но они прямолинейно зависят от 1) количества символов ключа; 2) качества ключа. Начнём с количества. Основной проблемой дешифрования (взлома) шифра Виженера является определение количества групп или, иными словами, количество непродублированных символов ключа. Для малой длины ключа и большого открытого текста найти группы не составит труда. Тем не менее, если ключ будет достаточно длинным, то найти повторяющиеся группы может быть проблематичным занятием. Если же длина ключа будет равна длине сообщения, то таковых групп и не будет существовать вовсе, и как следствие будет невозможным применение атаки по маске, для нахождения повторяемых групп символов, и атаки частотного криптоанализа, для дешифрования групп символов. В таком случае криптоаналитик полагается на существование некачественного, предсказуемого ключа, зависимого от контекста определённых событий. Например, началом ключа может быть какая-то дата, стих, прогноз погоды и т.д.

P.S. Некоторые полиалфавитные шифры, подобия шифра Тритемиуса, могли быть также взломаны посредством линейного криптоанализа, анализирующего статистическкую закономерность между открытым и закрытым текстом, на основе каких-либо алгебраический закономерностей. Такая уязвимость возникает из особенности шифра Тритемиуса, где ключом является функция, аргументом которой становится позиция шифруемого символа. Но такой метод криптоанализа появился лишь в современной криптографии, а потому о таковом следует говорить лишь в пределах его зарождения и последующего использования.

На основе всех вышеописанных критериев создаётся шифр Вернама, как определение наивысшей криптостойкости всех полиалфавитных алгоритмов шифрования. Шифр Вернама можно рассматривать как частный случай шифра Виженера с тремя правилами:

1. Необходимо использовать ключ, длина которого будет больше или равна длине сообщения. В данном контексте не позволяется как-либо дублировать или дополнять ключ. Он должен быть цельным.

2. В качестве ключа нужно использовать случайную и равновероятную последовательность символов. Иными словами, если нам необходимо зашифровать какой-либо символ, то под него мы должны сгенерировать случайный символ. Вероятность угадать какой символ будет получен при генерации должна составлять 1/N, где N - количество символов в алфавите.

3. Недопускать использование одного и того же ключа для двух разных сообщений. Иначе, это приведёт к уничтожению фактора случайности, то-есть к ликвидации второго пункта.

Шифр Вернама является не только представителем полиалфавитных шифров, не только их выражением наивысшей криптостойкости, но и шифром с теоретической (абсолютной) криптостойкостью. Иными словами, если в шифре Вернама были соблюдены все три критерия, то порождённый им шифртекст невозможно взломать ни за какое время и никакими вычислительными ресурсами.

5. Полиграммные шифры

Являются представителями развития кодов и моноалфавитных шифров, преобразующих не единичные символы и не целые слова в шифрованный результат, а целые блоки символов открытого текста в блоки закрытого текста. Можно сказать данный подкласс шифров является неким промежуточным или синтезирующим звеном между подклассами моноалфавитных шифров и кодов, усложняющих преобразования посредством стремления к кодам и увеличивающих количество вариантов шифрования в сравнении с моноалфавитными шифрами. В качестве примера, группа символов AB может шифроваться только как группа CD, в ровно такой же степени как и CD может расшифровываться исключительно и только как AB. Тем не менее, если один ранее использованный символ группы будет шифроваться, но уже с другим, то результатом преобразования может стать совершенно другая пара, например AC может быть преобразовано в EZ. В данном контексте сохраняется связь 1к1, но данный подкласс шифров становится более трудным по той лишь простой причине, что для взлома необходимым становится анализ частот не каждого отдельного символа, а целой группы символов. В качестве примера полиграммных шифров можно привести шифр Порты, шифр Плейфера, шифр Хилла.

Разберём полиграммные шифры на примере шифра Плейфера, как наиболее классического представителя полиграммных шифров. Шифр Плейфера является биграммным шифром, то-есть шифрует по два символа за раз, парно. В отличие от шифра Хилла, который может шифровать биграммами, триграммами, ..., N-граммами, шифр Плейфера шифрует исключительно биграммами.

Преобразование открытого текста в закрытый посредством шифра Плейфера происходит посредством выстраивания ключ-матрицы из ключа-строки. Предположим, что у нас существует английский алфавит, количество символов которого равно 26. Чтобы поместить эти 26 символов в матрицу, потребуется либо матрица 5x6, либо матрица 6x6 с дополнительными символами. В исторической же действительности брали матрицу 5x5, заменяя символ J символом I. Иными словами данные символы становились аналогичны друг другу при шифровании. При расшифровании они восстанавливались исходя из контекста самого сообщения. Ключ-строка играла роль первичного заполнения ключ-матрицы, посредством которого перемешивался оригинальный английский алфавит. Так например, предположим что у нас существует ключ-строка K=PARROT. В таком случае нам необходимо сконкатенировать к PARROT весь английский алфавит. Получим на выходе следующую строку: PARROTABCDEFGHIJKLMNOPQRSTUVWXYZ. Теперь нам нужно удалить все повторяющиеся символы начиная с конца данной строки, а также не забыть удалить символ J. В итоге, мы получаем такую строку PAROTBCDEFGHIKLMNQSUVWXYZ. Теперь создаём матрицу 5x5 и вносим туда получившуюся строку слева-направо, сверху-вниз.

Как только была сгенерирована матрица-ключ мы можем приступать к шифрованию сообщений. Предположим, что мы шифруем сообщение M=HELL. У шифр Плейфера существует ряд условностей, которые необходимо выполнить с открытым сообщением ещё до момента шифрования. Первое — разбить текст на биграммы, таким образом HELL преобразуется в (HE, LL). Второе — начиная с первой биграммы идти по порядку и как только появляется биграмма с одинаковыми символами, необходимо вставить между двумя символами нейтральный символ. В истории классической криптографии таким символом являлся X. После вставки нужно вновь выстроить биграммы и продолжить проверку повторяющихся символов в биграммах. Третье — если последняя биграмма неполная, то-есть не имеет парного символа, тогда нужно дополнить её нейтральным символом. В следствие этого, у нас получатся уже такие биграммы (HE, LX, LX).

P.S. В данном алгоритме существует одна погрешность, которая может допустим при программной реализации привести к бесконечному циклу, а именно если биграмма будет состоять из символов XX или если последняя биграмма будет неполной и состоять только из символа X. В таком случае, алгоритм будет всегда пытаться либо вставить между двумя XX ещё X, либо будет добавлять к X ещё X и приведёт вновь к зацикленности вставления X между двумя XX. На практике же (в истории) такой проблемы не встречалось по той лишь простой причине, что два символа XX просто не могут существовать рядом в английских словах. Таким образом, для программных реализаций может сойти использование второго нейтрального символа, допустим Y при таком случае.

Далее, как только мы получили биграммы открытого текста (HE, LX, LX), мы можем приступать к шифрованию. Шифр Плейфера предлагает нам три основных правила для шифрования сообщений.

1. Если два символа одной биграммы находятся на одной строке и на разных столбцах матрицы, то необходимо сдвинуть позицию текущих символов на одну позицию вправо и взять символы стоящие под новыми позициями в качестве шифрованной биграммы. Предположим, если бы мы шифровали биграмму HK, то её результатом по нашей ключ-матрице стала бы биграмма IL (H=>I, K=>L).

2. Если два символа одной биграммы находятся на одном столбце и на разных строках матрицы, то необходимо сдвинуть позицию текущих символов на одну позицию вниз и взять символы стоящие под новыми позициями в качестве шифрованной биграммы. Предположим, если бы мы шифровали биграмму DQ, то её результатом по нашей ключ-матрице стала бы биграмма IX (D=>I, Q=>X).

3. Если два символа одной биграммы находятся на разных строках и столбцах матрицы, то необходимо прочертить прямоугольник, где символы биграммы будут являться его углами, и взять противоположные углы. Символы на противоположных углах прямоугольника будут являться шифром биграммы. Предположим, если бы мы шифровали биграмму AS, то её результатом по нашей ключ-матрице стала бы биграмма NO (A=>N, S=>O) или ON (A=>O, S=>N).

Неоднозначность третьего пункта связана с нестандартизацией шифра Плейфера как такового. Такая же ситуация может происходить со множеством других алгоритмов шифрования классической криптографии (например — шифр вертикальной перестановки). Таким образом, абоненты в лице отправителя и получателя должны были заранее договориться о том, как следует шифровать биграммы находящиеся на разных строках и столбцах — либо по вертикали, либо по горизонтали.

Предположим, что мы будем придерживаться вертикальной шифрования при существовании третьего пункта. Таким образом, наши биграммы (HE, LX, LX) открытого текста будут преобразованы в биграммы (CK, ZI, ZI) закрытого текста.

У шифра Плейфера существует ряд недостатков. Так например, при заполнении ключ-матрицы, последние символы часто находятся в алфавитном порядке и чисто теоретически можно предположить, исходя из частоты использования символов, что X, Y, Z скорее всего в конце как были, так и остались в неизменной позиции. Таким образом, нам становится возможным определение нескольких символов ключ-матрицы сразу на раннем этапе. Также, если будут шифроваться биграммы по первому или второму правилу с использованием одинаковых символов, например биграммы (CE, CF), то в качестве результата мы получим схожее соответствие (DF, DB). Иными словами, на данном примере символ C не зависит от изменения парного ему символа.

Помимо вышеописанных недостатков, на нашем примере также видны ещё классические уязвимости, унаследованные моноалфавитными шифрами. Так например, биграммы LX всегда одинакого будут шифроваться как биграммы ZI. Также на основе атаки по маске мы можем продолжать находить часто повторяемые последовательности групп биграмм в зашифрованном тексте. Эти классические уязвимости всегда присутствуют в полиграммных шифрах и не исчезают при каких-либо частных и более конкретных реализациях.

Ещё одним и наверное самым простым представителем биграммных шифров является шифр Порты. Его можно представить в виде следующей таблицы. Здесь стоит понимать, что сам алфавит может быть перемешан, а потому количество ключей увеличится и будет равно N!, где N - количество символов в алфавите.

#include "encoder.h"

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct porto_t {
    encoder_t *encoder;
    uint8_t neutral_ch;
} porto_t;

extern porto_t *porto_new(encoder_t *encoder, uint8_t neutral_ch);
extern void porto_free(porto_t *porto);

extern uint32_t *porto_encrypt(porto_t *porto, uint32_t *output, uint8_t *input, uint32_t *size);
extern uint8_t *porto_decrypt(porto_t *porto, uint8_t *output, uint32_t *input, uint32_t size);

int main(int argc, char *argv[]) {
    uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
    
    encoder_t *encoder = encoder_new(size_alph);
    encoder_set_alphabet(encoder, alphabet);

    uint8_t message[BUFSIZ];
    strcpy((char*)message, "HELLOWORLD");

    uint32_t message_len = strlen((char*)message);
    uint32_t encrypted[message_len];

    porto_t *porto = porto_new(encoder, 'X');

    uint32_t size;
    porto_encrypt(porto, encrypted, message, &size);
    for (int i = 0; i < size; ++i) {
        printf("%d ", encrypted[i]);
    }
    printf("n");

    printf("%sn", (char*)porto_decrypt(porto, message, encrypted, size));

    porto_free(porto);
    encoder_free(encoder);
    return 0;
}

extern porto_t *porto_new(encoder_t *encoder, uint8_t neutral_ch) {
    porto_t *porto = (porto_t*)malloc(sizeof(porto_t));
   
    porto->encoder = encoder;
    porto->neutral_ch = neutral_ch;

    return porto; 
}

extern void porto_free(porto_t *porto) {
    free(porto);
}

extern uint32_t *porto_encrypt(porto_t *porto, uint32_t *output, uint8_t *input, uint32_t *size) {
    size_t input_len = strlen((char*)input);
    uint8_t first, second;
    int flag;

    int j = 0;
    uint32_t alpha_size = ((uint32_t)encoder_get_size_alphabet(porto->encoder));

    for (int i = 0; i < input_len-1; i += 2) {
        first = encoder_encode(porto->encoder, input[i], &flag);
        if (flag == 0) {
            fprintf(stderr, "failed encode first char '%c'n", input[i]);
            return NULL;
        }

        second = encoder_encode(porto->encoder, input[i+1], &flag);
        if (flag == 0) {
            fprintf(stderr, "failed encode second char '%c'n", input[i+1]);
            return NULL;
        }

        output[j++] = ((uint32_t)first)*alpha_size+((uint32_t)second);
    }

    if (input_len%2 == 1) {
        first = encoder_encode(porto->encoder, input[input_len-1], &flag);
        if (flag == 0) {
            fprintf(stderr, "failed encode first char '%c'n", input[input_len-1]);
            return NULL;
        }

        second = encoder_encode(porto->encoder, porto->neutral_ch, &flag);
        if (flag == 0) {
            fprintf(stderr, "failed encode second char '%c'n", porto->neutral_ch);
            return NULL;
        }

        output[j++] = ((uint32_t)first)*alpha_size+((uint32_t)second);
    }

    *size = j;
    return output;
}

extern uint8_t *porto_decrypt(porto_t *porto, uint8_t *output, uint32_t *input, uint32_t size) {
    uint32_t alpha_size = ((uint32_t)encoder_get_size_alphabet(porto->encoder));
    int flag, j = 0;

    for (int i = 0; i < size; ++i) {
        output[j++] = encoder_decode(porto->encoder, input[i] / alpha_size, &flag);
        if (flag == 0) {
            fprintf(stderr, "failed first second code '%c'n", input[i] / alpha_size);
            return NULL;
        }
        output[j++] = encoder_decode(porto->encoder, input[i] % alpha_size, &flag);
        if (flag == 0) {
            fprintf(stderr, "failed second first code '%c'n", input[i] % alpha_size);
            return NULL;
        }
    }
    return output;
}

186 297 386 381 289 
HELLOWORLD

Криптостойкость полиграммных шифрова прямо пропорционально зависит от количества шифруемых символов за раз в качестве N-граммы. Чем больше символов будет шифроваться одновременно, тем сложнее осуществлять атаки частотного криптоанализа и атаки по маске. Следовательно, наивысшей криптостойкостью полиграммных шифров становится размер равный L-грамме, где L - количество символов в открытом тексте, при условии, что изменение одного символа L-граммы будет приводить к изменению большинства других символов (лавинный эффект).

6. Простая перестановка

Предполагает собой полноценный и монолитный механизм, алгоритм перемешивания символов открытого текста с целью получения закрытого. По большей части это всё определение, а потому к такому подклассу шифров можно относить большинство известных перестановок, подобия маршрутной, вертикальной, решета Кардано, шифра Скитала (шифр Древней Спарты).

Так представим простую перестановку на примере вертикальной перестановки. У таковой перестановки ключом может быть строка или просто набор чисел. Количество символов (или чисел) ключа порождает размер блока, в который будут записываться блоки сообщения такого же размера. Если длина ключа равна длине сообщения, то происходит обычная математическая перестановка.

Предположим, что у нас существует ключ K=KEY и сообщение M=HELLOWORLD. В таком случае, мы создаём матрицу 3x4, где первое число - это размер ключа (количество символов), а второе число - это количество используемых блоков по 3 для вместимости всего сообщения M. Вписывает в матрицу слева-направо, сверху-вниз сообщение. Если остаются пустые ячейки, то заполняем их либо нейтральным символов (подобия того же X), либо случайными символами.

После заполнения всех ячеек, мы сортируем ключ KEY по алфавитному порядку, тем самым получая новый ключ EKY. Вместе с сортировкой символов ключа сортируем и столбцы под ними находящиеся. В итоге получае следующее.

Результат шифрования выписываем снизу-вверх, справа-налево. Получаем на выходе следующий шифртекст C=XLWLDOLHXROE. Вышеописанный алгоритм является лишь одним из возможных вариантов. Так например, можно вписывать/выписывать символы снизу-вверх, слева-направо, а можно также слева-направо, сверху-вниз, также можно сортировать ключ в порядке убывания и т.д. Это шифр классической криптографии, стандартизации как таковой на данном этапе ещё не существует.

При этом стоит заметить, что шифры простой перестановки никак не скрывают частоты символов открытого текста, в отличие от подстановочных шифров. Такое свойство играет двоякую роль, потому как с одной стороны применять частотный криптоанализ, в том привычном виде, становится бессмысленным. Частотный криптоанализ хорошо работает на классе подстановочные шифров, но не перестановочных. С другой стороны, сама перестановка всё же сохраняет в открытой форме символы открытого текста и если хорошо знать язык, на котором текст был написан, то нам становится возможно исключать определённые конструкции, которых просто не может существовать в оригинальном тексте. Так например, в русском тексте Ь не может существовать в начале слова, символ Н часто находится в сумме с другим Н, Й часто находится в конце слова, Ы существовует в массе своей с Й, Е или Н и т.д. Языковые конструкции избыточны, а потому могут приводить к дополнительным способам дешифрования, даже сложных перестановок.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct vertical_permutation_t {
    uint8_t *key;
    uint8_t *sorted_key;
    uint32_t key_size;
} vertical_permutation_t;

extern vertical_permutation_t *vertical_permutation_new(uint8_t *key);
extern void vertical_permutation_free(vertical_permutation_t *vertical_permutation);

extern uint8_t *vertical_permutation_encrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input);
extern uint8_t *vertical_permutation_decrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input);

static int find_index(uint8_t *arr, uint8_t v, int size);
static int comp(const void * elem1, const void * elem2);

int main(int argc, char *argv[]) {
    uint8_t encrypted[BUFSIZ];
    uint8_t message[BUFSIZ];
    strcpy((char*)message, "HELLOWORLDXX");

    uint8_t key[BUFSIZ];
    strcpy((char*)key, "KEY");

    vertical_permutation_t *vertical_permutation = vertical_permutation_new(key);

    printf("%sn", (char*)vertical_permutation_encrypt(vertical_permutation, encrypted, message));
    printf("%sn", (char*)vertical_permutation_decrypt(vertical_permutation, message, encrypted));

    vertical_permutation_free(vertical_permutation);
    return 0;
}

extern vertical_permutation_t *vertical_permutation_new(uint8_t *key) {
    vertical_permutation_t *vertical_permutation = (vertical_permutation_t*)malloc(sizeof(vertical_permutation_t));
   
    vertical_permutation->key_size = strlen((char*)key);
    vertical_permutation->key = (uint8_t*)malloc(sizeof(uint8_t)*vertical_permutation->key_size+1);
    vertical_permutation->sorted_key = (uint8_t*)malloc(sizeof(uint8_t)*vertical_permutation->key_size+1);

    strcpy((char*)vertical_permutation->key, (char*)key);
    strcpy((char*)vertical_permutation->sorted_key, (char*)key);

    qsort(vertical_permutation->sorted_key, sizeof(uint8_t)*vertical_permutation->key_size, sizeof(uint8_t), comp);
    return vertical_permutation; 
}

extern void vertical_permutation_free(vertical_permutation_t *vertical_permutation) {
    free(vertical_permutation->key);
    free(vertical_permutation);
}

extern uint8_t *vertical_permutation_encrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input) {
    size_t input_len = strlen((char*)input);
	int index_key, output_i = 0;

    if (input_len % vertical_permutation->key_size != 0) {
        fprintf(stderr, "input_len %% vertical_permutation->key_size != 0");
        return NULL;
    }

    for (int i = 0; i < vertical_permutation->key_size; ++i) {
        index_key = find_index(vertical_permutation->key, vertical_permutation->sorted_key[i], vertical_permutation->key_size);
        for (int j = index_key; j < input_len; j += vertical_permutation->key_size) {
            output[output_i++] = input[j];
        }
    }

    return output;
}

extern uint8_t *vertical_permutation_decrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input) {
    size_t input_len = strlen((char*)input);
	int index_key, output_i = 0;

    if (input_len % vertical_permutation->key_size != 0) {
        fprintf(stderr, "input_len %% vertical_permutation->key_size != 0");
        return NULL;
    }

   for (int i = 0; i < input_len; i += vertical_permutation->key_size) {
        for (int j = index_key; j < input_len; j += vertical_permutation->key_size) {
            index_key = find_index(vertical_permutation->key, vertical_permutation->sorted_key[j], vertical_permutation->key_size);
            output[output_i++] = input[j];
        }
    }

    return output;
}

static int find_index(uint8_t *arr, uint8_t v, int size) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == v) {
            return i;
        }
    }
    return -1;
}

static int comp(const void * elem1, const void * elem2) {
    uint8_t f = *((uint8_t*)elem1);
    uint8_t s = *((uint8_t*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

EORXHLODLWLX
HELLOWORLDXX

Криптостойкость шифров простой перестановки увеличивается удлинением размера ключа, а соответственно и удлинением блоков перестановки. Таким образом, если шифр простой перестановки зависит от ключа, а длина ключа определяется длиной N входного текста, то количество всевозможных ключей будет равно N!. Так, на примере шифра вертикальной перестановки, количество всевозможных ключей при длине ключа равной 3 составляет 3!=6, а при длине ключа равной 4 составляет 4!=24 и т.д. Исходя из всего этого, наивысшая криптостойкость определяется схожим образом с полиграммными шифрами.

7. Сложная перестановка

Является обычным сочетанием, композицией простых перестановок. Это может быть как вертикальная+вертикальная перестановки с разной длиной ключа (желательно, чтобы НОД(a, b) = 1 (НОД = наибольший общий делитель), где a, b - длины блоков первой и второй перестановок), так и для примера маршрутная+решето Кардано. Всевозможных комбинаций в таком подклассе существует бесконечное множество.

При наилучшей композиции сложная перестановка приводит к произведению количества ключей простых перестановок. Так например, если одна простая перестановка имеет длину ключа равную 7, а другая равную 13, то итоговое количество ключей будет равно 7!*13!=31384184832000 всевозможным перестановкам, что в свою очередь представляет сложность ~=2⁴¹.

P.S. Стоит заметить, что такое свойство композиций существует не у всех шифров. Так например, бессмысленно композировать несколько моноалфавитных шифров, потому как выходом объединения станет обычный моноалфавитный шифр. Также нет смысла комбинировать несколько полиалфавитных шифров с одинаковой длиной ключа, потому как это приведёт ровно также к созданию одного полиалфавитного шифра с такой же длиной ключа. Из этого следует, что сама композиция, комбинирование нескольких шифров должно происходить лишь на основе объединения разных длин ключей.

Тем не менее, полученная длина ключа может быть урезана многократно, если криптоаналитик сможет найти один из делителей сложной перестановки. Иными словами, если он поймёт, что длина одной перестановки равна 7, то длина ключа сложной перестановки упадёт до 13!=6227020800. Таким образом, сложная перестановка продолжает наследовать внутри себя критерий наивысшей криптостойкости простой перестановки, что логично, ведь таковая сложность является лишь комбинацией простоты.

Помимо сложной перестановки, в истории криптографии существовал ещё ряд композиционных шифров, как вид объединения нескольких алгоритмов. Так в качестве примера, таковыми являлись шифр ADFGVX (шифр Полибия+вертикальная перестановка) и шифровальная машина Энигма (парный шифр+полиалфавитный шифр). Тем не менее, их вид композиции в некой степени разный, неоднородный, потому как ADFGVX соединяет одновременно два класса, в то время как Энигма объединяет два подкласса только из одного класса, ровно также как это делает сложная перестановка. В дальнейшем, чтобы понимать о каком конкретно типе объединения идёт речь, введём различие на уровне терминологии, где для сочетания двух классов подстановка+перестановка мы будем использовать термин Композиционный (ADFGVX), а для сочетания двух подклассов одного класса — Комбинированный («Энигма», Сложная перестановка).

Композиционные шифры (в дальнейшем повествовании современных симметричных алгоритмов) играют большую роль чем комбинированные, поэтому на последних мы не будем сильно заострять внимание. Более подробно, в качестве примера комбинированных шифров, вы можете рассмотреть устройство шифровальной машины «Энигма», а также её реализацию на языке программирования Си — тут.

Заключение

Пока что мы рассмотрели лишь классы и подклассы алгоритмов классической криптографии, не затрагивая при этом современную симметричную криптографию. Тем не менее, кто уже знаком с современной криптографией может увидеть достаточно много "деталей", которые были унаследованы современными шифрами.

Список литературы

1. Взломщики кодов. Д. Кан

2. Книга шифров. Тайная история шифров и их расшифровки. С. Сингх

3. Основы классической криптологии. М. Адаменко

4. История криптографии. А. Бабаш, Г. Шанкин

5. История криптографии в Западной Европе в раннее новое время. И. Русецкая