Криптография и шифрование

Криптография > Криптоанализ > Формула Маркова

Формула Маркова

Подобным образом, Марков стал рассматривать не столько вероятности Pj проявления в сообщении символа i, а теоретической возможности Pij проявления символа j при том условии, что перед ним находится символ i. Теория марковских цепочек в дальнейшем оказалась невероятно продуктивной для шифрования, и к ее отдельным способам применения мы еще будем возвращаться чуть позже.

В данный же момент вполне достаточно заметить, что первое свое боевое крещение она имела во время анализа текстов поэмы "Евгений Онегин" самим Андреем Андреевичем Марковым. Объем информации в одном знаке марковской цепочки обычно рассчитывается по следующей формуле:

H= См. Pi(См. Pij*Ld(Pij))

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

Справа в этой таблице будут представлены вероятности встречи отдельных знаков. Таким образом, из нее следует, что биграмма АЙ попадается довольно-таки часто (класс 7), а биграмма ЙА практически не попадается вообще (класс 0). Усредненный объем информации, приходящийся на один знак, определяемый по такой таблице равен 3.5 бит, что является эквивалентом приблизительно 2 буквам русского алфавита или теоретической возможности сжатия текстов ориентировочно на 57% при их оптимальной шифрации.