Роль лингвистики в развитии криптографии

Кроме того, вклад Колмогорова в лингвистику сложно переоценить. Колмогоров при помощи методов математической статистики и теории информации давал направления, подходы для решения вопросов, которые были принципиально важными для понимания устройства языка.Решения этих вопросов помогают разбить количество содержащейся в тексте информации на отдельные слагаемые, даваемые грамматикой, семантикой, поэтикой. Если считать текстом любую цепочку, составленную из букв и пробелов, то каков процент грамматически правильных текстов? А каков процент текстов осмысленных? Сколькими способами можно выразить одно и то же содержание? Как изменятся ответы на эти вопросы, если к требованию осмысленности добавить ограничения, диктуемые художественной, в частности стихотворной, формой? На все эти вопросы пытались ответить путем интенсивных исследований молодые сотрудники, которых объединил под своим началом Колмогоров. Примечательно, что в своих трудах Колмогоров указывал на эти вопросы и проблемы вскользь, не акцентируя на этом внимание, а просто указывая итоговые математические ответы. Например, в своей знаменитой статье 1965 года «Три подхода к определению понятия «количество информации'» Колмогоров лишь указывает результаты подсчётов, полученные двумя его лаборантками:Для двоичного логарифма числа N русских печатных текстов, составленных из слов, включённых в Словарь русского языка С.И. Ожегова и подчинённых лишь требованиям «грамматической правильности» длины n, выраженной в «числе знаков» (включая «пробелы»), М. Ратнер1 и Н. Светлова2 получили оценку h = (log2 N)/n = 1,9±0,1. Это значительно больше, чем оценки сверху для «энтропии литературных текстов», получаемые при помощи различных методов «угадывания продолжений». Такое расхождение вполне естественно, так как литературные тексты подчинены не только требованию «грамматической правильности».Уже после кончины Колмогорова обнаружилось несколько машинописных страниц, содержащих его неопубликованную заметку «О возможном применении простейших представлений теории информации к исследованию стиха, художественной прозы, техники перевода». Энтропия открытого текстаИнформационная энтропия – это мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа алфавита. Например, в последовательности букв некоторого предложения разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые буквенные n-граммы встречаются крайне редко, то неопределённость уменьшается еще сильнее.До расшифрования и для законного получателя, и для злоумышленника отправленное сообщение является, естественно, неопределенным. Пусть возможна отправка сообщений х1, х2…хп с вероятностями р1,р2…рп соответственно, т.е. задано распределение вероятностей P (Х) открытых текстов. Если какой-либо другой информации о шифровании нет, то остается неопределенность в ответе на вопрос, какой именно из открытых текстов х1, х2…хп шифровался. Мерой такой неопределенности служит энтропия открытых текстовОна определяет количество битов информации, которое необходимо в среднем передать, чтобы полностью устранить неопределенность в задании сообщения с помощью распределения вероятностей P (X). Другими словами, через эту энтропию определяется количество информации, необходимое для точного указания сообщения. Если все открытые тексты равновероятны, то по свойству 2 энтропия достигает максимального значенияПри этом если нет никакой априорной информации о сообщении, кроме его длины в N бит, то все возможные из сообщений считаются равновероятными и тогда энтропия открытого текста равна его длине, поскольку Если же количество информации о сообщении увеличивается, то распределение вероятностей открытых текстов начинает отличаться от равновероятного, энтропия уменьшается и становится равной нулю, когда есть сообщение, вероятность которого, то есть . А если об исходном тексте неизвестно вообще ничего, даже его длина? В этом случае все равно необходимо принять за основу какую-либо модель распределения. Как правило, в реальности подобных трудностей не возникает, поскольку большинство шифров не скрывают размер шифруемого сообщения (учитывая принцип Кирхгоффса). Там же, где этот размер текста необходимо скрыть, все сообщения перед зашифрованием преобразуются в массивы данных одной и той же длины. Таким образом, энтропия открытого текста измеряет его неопределенность в числе бит информации, которая должна быть восстановлена, когда сообщение было скрыто от криптоаналитика в шифротексте. После перехвата шифротекста энтропия открытого текста может измениться, теперь она становится апостериорной условной энтропией – условием здесь является перехваченное шифрованное сообщение y :Где – вероятность того, что исходное сообщение есть при условии, что результат его зашифрования есть y . Одной из важнейших характеристик шифра служит количество информации об исходном тексте, которое злоумышленник может извлечь из перехваченного шифротекста – оно находится как разность между априорной и апостериорной энтропией открытого текста:Эта величина всегда неотрицательна и показывает, насколько уменьшится неопределенность открытого текста при получении соответствующего шифротекста по сравнению с априорной неопределенностью. Для совершенно стойкого шифраи злоумышленник не может извлечь никакой информации об открытом тексте из перехваченного шифротекста:. Иными словами, знание шифротекста не позволяет уменьшить неопределенность зашифрованного открытого текста и увеличить вероятность его правильного определения. Аналогично мерами неопределенности шифротекстов и ключей служат энтропииСтатистические критерии открытого текстаЗаменив реальный открытый текст его моделью, мы можем теперь построить критерий распознавания открытого текста. При этом можно воспользоваться либо стандартными методами различения статистических гипотез, либо наличием в открытых текстах некоторых запретов, таких, например, как биграмма ЪЪ в русском тексте. Проиллюстрируем первый подход при распознавании позначной модели открытого текста.Итак, согласно нашей договоренности, открытый текст представляет собой реализацию независимых испытаний случайной величины, значениями которой являются буквы алфавита, появляющиеся в соответствии с распределением вероятностей Требуется определить, является ли случайная последовательность; букв алфавита А открытым текстом или нет.Пусть Но — гипотеза, состоящая в том, что данная последовательность — открытый текст, Н, — альтернативная гипотеза. В простейшем случае последовательность можно рассматривать при гипотезе Н, как случайную и равновероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается “бессмысленная” последовательность знаков. В более общем случае можно считать, что при гипотезе Н, последовательность , представляет собой реализацию независимых испытаний некоторой случайной величины, значениями которой являются буквы алфавита , появляющиеся в соответствии с распределением вероятностей При таких договоренностях можно применить, например, наиболее мощный критерий различения двух простых гипотез, который дает лемма Неймана—Пирсона [Кра75] В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может принять открытый текст за случайный набор знаков. Такая ошибка обычно называется ошибкой первого рода, ее вероятность равна. Аналогично вводится ошибка второго рода и ее вероятность . Эти ошибки определяют качество работы критерия. В криптографических исследованиях, естественно, минимизировать вероятность ошибки первого рода, чтобы не “пропустить” открытый текст. Лемма Неймана—Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.Критерии на открытый текст, использующие запретные сочетания знаков, например к -граммы подряд идущих букв, будем называть критериями запретных к-грамм. Они устроены чрезвычайно просто. Отбирается некоторое число 5 редких к -грамм, которые объявляются запретными. Теперь, просматривая последовательно к -грамму за к -граммой анализируемой последовательности, мы объявляем ее случайной, как только в ней встретится одна из запретных к -грамм, и открытым текстом в противном случае. Такие критерии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных к -грамм являются весьма эффективными.Глава 3. Пример криптоанализа шифрсистемы RSAПостановка задачиШифр RSA (Rivest, Shamir, Adelman) был представлен общественности в 1977 году криптографими – американцами Ривестом, Шамиром и Адлеманом.Основой асимметричного шифра RSA является односторонняя функция, основанная на вычислениях в целых числах по некоторому натуральному модулю N. Чтобы зашифровать текст с помощью метода RSA, необходимо:Взять большое число N = pq, являющееся произведением только двух различных простых чисел p и q. Взять целое число е, которое называется открытым ключом или ключом зашифрования. Важный момент, что е не имеющее общих делителей с (р - 1)(q - 1) и с самим числом N. Для расшифрования текста, зашифрованного по методу RSA, понадобится определить еще одно число d.Отыскать целое число d, называемое секретным ключом или ключом расшифрования, которое удовлетворяет условию ed 1(mod(p – 1)(q -1))Если р и q известны, существует метод нахождения d, но если p и q неизвестны, найти d очень сложно. Именно этот факт обеспечивает стойкость системы RSA. Если p и q очень велики и неизвестны (например, более 10200), то найти их за приемлемое время (т. е. факторизовать число N) не под силу даже наибыстрейшим компьютерам.По открытому ключу (N; e) системы шифрования RSA вычислить секретный ключ (N; d).Вычисление секретного ключа d по открытому ключу eНайдем ключ расшифрования d, если N = 10403, а ключ зашифрования е = 6277.Для решения поставленной задачи необходимо число 10403 разложить на простые множители. В случае алгоритма RSA стойкость держится на том, что перемножить два больших числа сравнительно просто, но, если дано только произведение этих двух больших чисел, то найти их крайне трудно. Тем на менее, осуществив почти 101 пробных делений 10379 на всевозможные числа от 2 до 101, находим, что 10403 = 101 × 103.Причем и 101 = p, и 103 = q — простые числа. Следовательно, значение N годится в качестве модуля для системы RSA, а значение функции Эйлера от 101 × 103 равно φ(101 × 103) = (р - 1)(q - 1) = 100 × 102 = 10200. Далее, поскольку число e = 6277 не имеет общих делителей ни с 10403, ни с 10200, то оно годится в качестве открытого ключа. Чтобы найти соответствующий секретный ключ d, необходимо решить следующее сравнение 6277d1(mod 10200).относительно неизвестного d. Для чего может быть применим алгоритм Евклида. В результате получаем, что секретный ключ d = 13. Вычисление открытого текста TДля зашифрования сообщения по методу RSA предполагаемому пользователю необходимо знать значение модуля N и открытый ключ е - эти величины общедоступны. Значения чисел p и q и ключа расшифрования d известны только «хозяину» используемой криптографической системы. Чтобы зашифровать сообщение, посылаемое «хозяину», и которое только он один и сможет прочесть, пользователь должен:Преобразовать некоторым фиксированным способом буквы сообщения в числа. Например, в соответствии с кодом ASCII, либо воспользоваться уже готовым представлением сообщения в виде последовательности числ. Если в записи модуля N не более М цифр, разбить числовое представление сообщения на блоки, в каждом из которых не более М цифр; эти блоки обозначим T1, T2, T3, Т4Последовательно зашифровать блоки независимо друг от друга, вычислив(Ti)е (modN), i = 1, 2, ... — в результате получаются блоки шифрованного текста S1, S2, S3, S4.Шифрованное сообщение записывается S1, S2, S3, S4 - в виде последовательности чисел, а не букв. В данной работе эта последовательность определяется как исходные данные (S1, S2, S3, S4) = (1830, 3701, 7029, 4145)Процедура расшифрования сообщения в точности та же самая, как и при зашифровании, за исключением того, что теперь преобразуются блоки шифрованного текста Si, а на шаге (4) вместо ключа зашифрования е используется ключ расшифрования d. Из способа получения d следует, что(Si)d(modN) = Ti, или, другими словами, происходит восстановление исходного сообщения. Таким образом, для решения поставленной в работе задачи необходимо произвести следующие вычисления: (Si)13(mod10403), где .Осуществим теперь процесс расшифрования по системе RSA заданного шифрованного сообщения: (S1, S2, S3, S4) = (1830, 3701, 7029, 4145).В качестве секретного ключа используем числа, полученные выше: N = 10403 и d= 13. Теперь необходимо вычислить значения, получаемые при возведении каждого из этих четырех исходных четырехзначных чисел в 13-ю степень по модулю 10403. Итак, наша задача состоит в том, чтобы вычислить значение (1830)13(mod10403). Везде, где это возможно в модульных вычислениях такого типа, имеет смысл для нахождения степеней исходного числа последовательно возводить его в квадрат, а затем перемножать значения соответствующих степеней. Поскольку 13 = 23+22+20 , то потребуется число 1830 возвести в каждую из степеней: 20, 21, 22, 23 путем последовательного возведения в квадрат с дальнейшим перемножением нужных нам чисел. Окончательно получаемT1 = (1830)137527 (mod 10403)= 7527.Итак, 1830при расшифровании переходит в 7527.Остальные блоки текста сообщения расшифровываются аналогично, то есть возведением каждого четырехзначного числа Siв степень 13 с приведением по модулю 10403. В результате получается расшифрованный текст: 7527, 5258, 4180,8403.Для того чтобы убедиться в обратимости процедур шифрования и расшифрования криптосистемы RSAснова зашифруем фрагмент открытого текста T1 на открытом ключе. Для этого потребуется вычислить значение (7527)6277(mod 10403)=1830.Как и следовало ожидать в результате получаем число 1830, равное исходному значению S1.ЗАКЛЮЧЕНИЕВ результате проделанной работы была дана характеристика и роль лингвистики в развитии криптографии на протяжении всей ее истории. Были выполнены все поставленные задачи. В настоящее время большинство встречаются с алгоритмами шифрования и криптографией повсеместно. Это и электронная цифровая подпись, электронная почта и т.д. Вместе с тем возрастает необходимость комплексного подхода к решению проблем защиты информации. Для защиты должны применяться как криптографические методы, включая криптоанализ, так и организационные, технические и другие средства, которые смогут обеспечить защиту конфиденциальности, целостности и доступности информации.СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫАлферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2005.Лось А. Б., Нестеренко А. Ю., Рожков М. И. Криптографические методы защиты информации. Москва: Издательство Юрайт, 2019. Сингх С. Книга шифров. М.: АСТ-Астрель, 2006.Кириллов И.А. Криптографическая защита информации. – М.: ИПК МГЛУ Рема, 2010.Шеннон К. Теория связи в секретных системах.// В кн.: Работы по теории информации и кибернетике. – М.:ИЛ, 1963. Пиотровский. Статистика речи.