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

Полный текст

Введение В середине прошлого века Шеннон предложил измерять энтропию букв и их сочетаний в форме фрагментов текстов, опираясь на теорию информации. Формально информативность некоторого символа заданного алфавита можно определить следующим образом: /('V) = iog2 №,")), (1) где "х;" - кодировка i-го символа, P("jc,") - вероятность появление в тексте i-го символа, i - номер символа в алфавите. При таких обозначениях энтропия одиночных символов заданного алфавита определяется как математическое ожидание их информативности: tf('V) = £(/('V))- (2) Вычислить энтропию одиночных символов русского языка (как и любого иного языка) технически несложно. Несложно вычислить энтропию пары рядом стоящих символов, встреченных в анализируемом тексте: H(''xi,xj") = E(ICxi,xJ'')), (3) где /("xI.,x,") = log2(P("xi.,x,")). (4) По индукции можно ввести понятие k-мерной энтропии Н("х1,х2,...,хк") для последователь ности из k рядом стоящих символов, которая будет определяться через к-мерную информацию 1("х1,х2,...,хк") и через вероятности появления вариантов кодовых строк Р(''х1, х2хк "). Реальные вычислительные возможности современной техники позволяют оценить энтропию только относительно коротких кодировок до 9 знаков русскоязычного текста. Далее возникают технические проблемы, не позволяющие осуществлять прямую оценку энтропии по Шеннону. В [1] предложен метод обхода создавшихся проблем через переход в пространство расстояний Хэмминга. К сожалению, упрощения, на которых построен метод моделирования [1], вносят в вычисления существенную методическую ошибку. Заметим, что проблема оценки энтропии длинных кодов возникает только в том случае, если коды зависимы. Если коды независимы («белый» шум), то их высокоразмерная энтропия легко вычисляется через биномиальный закон (закон испытаний Бернулли), являясь одномерной функцией вида НС’х,, х2хк")« log2 (1/32) к*5к, (5) где Р("х!') = Р(!'х1") = РС'х2") = ... = 1/32 - вероятность появления каждого из кодов символов букв языка. В случае «белого» шума (5) энтропия кодов будет почти совпадать с длиной кодовой последовательности. То есть для случайных паролей, набранных в кириллической 8-битной кодировке, энтропия составит величину, близкую 8k бит. Однако такая оценка неприемлема для понимаемых людьми текстов на русском языке. Во-первых, длинные коды из 8k бинарных разрядов оказываются коррелированными, во-вторых, появление каждого из k символов не является равновероятным. Прямые попытки учета этих факторов делают задачу вычисления энтропии как минимум k-мерной. Экспоненциальная связь энтропии зависимых биокодов от их длины Положение усложняется тем, что мы стоим на пороге появления специализированных искусственных языков с произвольной энтропией символов (слов) и произвольной длиной их кодов. «Инфокоммуникационные технологии» Том 12, № 2, 2014 Малыгина Е.А., Иванов А.И., Язов Ю.К., Надеев Д.Н. 13 Речь идет о системах мультибиометрии [2], где каждому биометрическому образу конкретного человека ставится в соответствие его новое конфиденциальное имя или код его нового личного ключа. При этом слабый биометрический образ будет иметь низкую энтропию, а сильный биометрический образ будет иметь высокую энтропию. Заранее нельзя указать энтропию того или иного биометрического образа, кроме того, появляется возможность менять длину кода, получаемого из этого биометрического образа. Ситуация в естественных языках такова, что каждый из нас имеет только открытое всем имя. Так было далеко не всегда, древние славяне и иные народы практиковали использование наряду с открытым именем человека (семьи) их тайное имя, известное только очень узкому кругу людей. Фактически тайное родовое имя играло роль родового пароля, знание этого имени позволяло подтвердить свою принадлежность к роду (семье). На новом технологическом витке второе (третье, четвертое и т.д.) тайное имя становится очень длинным и играет роль личного криптографического ключа, которому может соответствовать сертификат открытого ключа, а может его не быть (открытый ключ передают кому следует, не публикуя). Видимо, язык множества длинных тайных имен человека будет поддерживаться относительно слабой технологией «нечетких экстракторов» [3] или более сильной технологией нейросетевых преобразователей биометрия-код [4]. Особенностью выходных кодов биометрии является то, что их разряды не упорядочены по их значимости. Каждый разряд кода доступа является главным, достаточно одного неверного разряда, чтобы протокол аутентификации перестал работать. Еще одной особенностью биокодов является сильная коррелированность состояний их разрядов. Биокод длиной 256 бит, соответствующий ключу аутентификации будет иметь энтропию порядка 50 бит из-за того, что разряды этого биокода коррелированы (зависимы). Очень важной особенностью биокодов является то, что изготовитель нейросетевого преобразователя биометрия-код может менять длину выходного кода так, как посчитает необходимым. В России принято иметь длину выходного кода - 256 бит, так как отечественные стандарты по шифрованию и формированию электронной цифровой подписи ориентированы именно на такую длину криптографического ключа. Практика создания нейросетевых преобразователей биометрия-код [5] показала, что энтропия биокода зависит как от его длины, так и от информативности биометрического образа «Свой». На рис. 1 приведены кривые роста энтропии двух биокодов, соответствующих двум биометрическим образам разной информативности. Рис. 1. Рост энтропии выходного биокода нейросети как функция от его длины Из рис. 1 видно, что сильный биообраз позволяет получить энтропию выходного биокода порядка 38 бит при длине кода 244 бита. Дальнейшее увеличение числа выходов искусственной нейронной сети не приносит каких-либо результатов, энтропия кодов не увеличивается. Слабый биообраз дает предельное значение энтропии 26 бит уже при длине кода 160 бит, дальнейшее наращивание числа выходов нейронной сети смысла не имеет. Установлено, что кривая роста энтропии точно описывается экспонентой: HC'Xl,x2,...,xk") = £(//("х,."))+Д1-е?ф{-^}), (6) где - среднее значение энтропии вы ходных состояний каждого из выходов искусственной нейронной сети, т - постоянная замедления роста энтропии, А-амплитуда потенциала роста энтропии. Очевидно, что применение прямых оценок энтропии биокодов длиной 256 бит по Шеннону бесперспективно. События, которые приходится ждать при проведении численного эксперимента, не появляются в обозримые интервалы времени. Однако никто не мешает пойти иным путем. Нетрудно вычислить среднее значение энтропии одиночных решений, принимаемых на выходе каждого из нейронов. Нет технических ограничений для того, чтобы вычислить среднюю энтропию для нескольких вариантов 8-битных кодовых комбинаций - e(H("x1,x2,...,xs")). Если далее найти среднюю энтропию 16-битных кодов «Инфокоммуникационные технологии» Том 12, № 2, 2014 14 Малыгина Е.А., Иванов А.И., Язов Ю.К., Надеев Д.Н. то будет достаточно информации для того, чтобы найти два неизвестных параметра A и т. Априорная информация об экспоненциальной связи энтропии и длины кода (6) настолько значительна, что достаточно достоверно знать три точки кривой роста энтропии для прогнозирования значений зависимых биокодов любой длины. Обобщение результатов для прогноза энтропии длинных кодов любых языков Простая экспоненциальная связь (6) энтропии зависимых биокодов с их длиной обусловлена тем, что информативность каждого биообраза конечна. Искусственная нейронная сеть по мере роста числа ее выходов все больше и больше извлекает информации из фиксированного числа входов (из фиксированного числа биометрических параметров). При этом растет общая коррелирован-ность выходных состояний нейронной сети. В итоге рост энтропии прекращается при некотором числе выходов преобразователя биометрия-код. В языках (естественных и искусственных) все обстоит иначе. Информативность сообщений должна монотонно расти по мере роста длины кода (по мере роста длины текста). Язык не выкачивает информацию из одного объекта, он описывает множество объектов и их взаимосвязи. Это означает, что энтропия длинных кодов любого языка должна описываться следующим уравнением: Н("х1,х2,...,хк") = Н("х j ") + ^4(1-ехр{-2- к}) + (1-а)к’ где Н("хj") - энтропия одного символа алфавита языка, a - коэффициент избыточности языка, позволяющий устранять неоднозначности. В уравнение (7) входит четыре неизвестных. Необходимо найти четыре точки, принадлежащие кривой роста энтропии. Численный эксперимент, проведенный для русского литературного языка (использовались четыре тома классического романа «Война и мир» Л.Н. Толстого), дал значения tf('V) = 2,64 бита; х1,х2'') = 5,12 бита; HQ'х1,х2,хъ") = 7,46 бита; Щ'х1гх2,х3,хА") = 9,94 бита; А = 80,1; т = 0,047; а = 0,906. То есть избыточность русского языка достигает 90%, что позволяет эффективно править ошибки и искажения в сказанном и услышанном. Графическая интерпретация полученных результатов Вышеприведенные данные численного эксперимента позволяют утверждать, что энтропия всех естественных и искусственных языков изменяется по одному и тому же закону, соответствующая кривая роста энтропии фраз русского языка приведена на рис. 2. Энтропия Идеальный / "белый" шум s' энтропии длинных русских фраз /*\ -Переходный процесс энтропии коротких русских фраз !S 50 100 150 200 Число букв Рис. 2. Две предельные линейные функции изменения энтропии текстов на русском языке Из данных, приведенных на рис. 2, видно, что каждый язык должен иметь линейный рост энтропии для длинных фраз. Для русского языка первоначальный быстрый экспоненциальный рост энтропии коротких фраз прекращается для текстов длиной порядка 100 букв. Далее начинается очень медленный линейный рост энтропии. Как следствие, даже очень длинные и легко запоминаемые людьми парольные фразы из 200 букв, набранные в одном регистре, будут иметь энтропию порядка 100 бит. Для того чтобы иметь энтропию парольной фразы более 100 бит, необходимо набирать на клавиатуре осмысленный текст парольных фраз в двух регистрах. При этом заглавные буквы в парольных осмысленных фразах русского языка встречаются намного реже, чем прописные буквы. Переход к текстам парольных фраз, набранных в двух регистрах, незначительно увеличивает их энтропию. Вывод Энтропия естественных и искусственных языков описывается суперпозицией экспоненты и линейной функции. Эта априорная информация позволяет уйти от «проклятия» размерности и отказаться от сложных вычислений, и ожидания редких событий. Появляется возможность предсказывать значение энтропии длинных зависимых кодов по значениям энтропии четырех коротких кодов. Для синтетического языка безопасного применения множества тайных биометрических образов человека (синтетического языка мультибиометрии) линейный рост энтропии длинных парольных фраз отсутствует. Объединение k-би «Инфокоммуникационные технологии» Том 12, № 2, 2014 15 ометрических образов приводит к появлению k последовательных переходных процессов (сглаженные экспонентой ступеньки). И в том, и в другом случае методики оценки значений энтропии длинных кодов оказываются похожими.

Об авторах

Елена Александровна Малыгина

Пензенский государственный университет

Email: mal890@yandex.ru
аспирант Кафедры информационной безопасности систем и технологий

Александр Иванович Иванов

Пензенский научно-исследовательский электротехнический институт

Email: ivan@pniei.penza.ru
д.т.н., доцент, начальник Лаборатории биометрических и нейросетевых технологий (ЛБНТ)

Юрий Константинович Язов

ФАУ «Государственный научно-исследовательский, испытательный институт проблем технической защиты информации Федеральной службы по техническому и экспортному контролю»

Email: gniii@fstec.ru
д.т.н., профессор, начальник отдела г. Воронеж

Дамир Наилевич Надеев

Пензенский научно-исследовательский электротехнический институт

Email: ivan@pniei.penza.ru
к.т.н., младший научный сотрудник ЛБНТ ПНИЭИ

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

Дополнительные файлы