Задачу дешифрования К. Шеннон рассматривает как задачу вычисления апостериорных знаний противника о шифре после перехвата криптограммы. Дело в том, что вероятности сообще-ний и ключей составляют априорные знания противника, кото-рыми он располагает в соответствии с правилом Керкгоффса. После перехвата криптограммы он может (по крайней мере, в принципе, поскольку множества сообщений и ключей конечны) вычислить апостериорные вероятности возможных ключей и сообщений, которые могли быть использованы при составлении данной криптограммы. Вот эти вероятности и составляют апо-стериорные знания противника. С этой точки зрения показателен следующий пример.
Пусть для зашифрования нормативного английского языка применяется шифр простой замены, в котором каждый из 26! ключей может быть выбран с равной вероятностью. Пусть про-тивник знает об источнике сообщений лишь то, что он создает английский текст. Тогда априорными вероятностями различных сообщений из N букв являются их относительные частоты в нормативном тексте. Если же противник перехватил крипто грамму из N букв, то он может вычислить условные вероятно-сти открытых текстов и ключей, которые могут создать такую криптограмму. Если N достаточно велико, скажем N = 50, то обычно имеется единственное сообщение (и единственный ключ) с условной вероятностью, близкой к единице (это -- само сообщение, подвергнутое шифрованию), в то время как все дру-гие сообщения имеют суммарную вероятность, близкую к нулю. Таким образом, имеется, по существу, единственное "решение" такой криптограммы. Для меньших значений N, скажем N = 10, обычно найдется несколько пар сообщений и ключей, вероятности которых сравнимы друг с другом, то есть, нет ни одного сообщения (и ключа) с вероятностью, близкой к единице. В этом случае "решение" криптограммы неоднозначно.
Понятие совершенной секретности К. Шеннон определяет требованием, чтобы апостериорные знания противника в точно-сти совпадали бы с априорными знаниями. Он приводит пример совершенного шифра, которым является шифр Вернама (со слу-чайной равновероятной гаммой). Следует подчеркнуть, что все рассуждения о стойкости шифров К. Шеннон проводит лишь для одной постановки задачи криптоанализа: когда противник располагает лишь одной криптограммой и требуется найти текст сообщения. Для других постановок задач требуются отдельные исследования.
Теоретической мерой секретности (или стойкости) по К.Шеннону является энтропийная характеристика -- неопреде-ленность шифра по открытому сообщению, которая измеряет (в статистическом смысле), насколько "близка" средняя крип-тограмма из N букв к единственному "решению". Он выводит формулу для приближенного вычисления минимального N, при котором находится единственное "решение". Такая вели-чина получила название расстояния единственности. Форму-ла для расстояния единственности связывает между собой не-определенность шифра по открытому тексту и избыточность текста. Чем большим оказывается расстояние единственности, тем более шифр приближается к совершенному шифру, для которого формально расстояние единственности равно .
Наконец, К. Шеннон вводит понятие рабочей характери-стики шифра, подходя к практической оценке стойкости. Он формулирует также основные критерии оценки качества секрет-ных систем с позиций практики их использования.
Как видим, К. Шеннону удалось решить фундаментальные проблемы в теоретической криптографии. Его работы стимули-ровали бурный рост научных исследований по теории информа-ции и криптографии.
В работах К. Шеннона по исследованию свойств языка важ-ную роль играет величина удельной энтропии Н на букву тек-ста, другими словами, среднее количество информации, переда-ваемой буквой открытого текста. Предложенный им метод экс-периментов с угадыванием очередной буквы английского текста по предыдущим буквам оказался неэффективным при получе-нии оценок величины Н для других языков. Метод "отгадыва-ния" развил в своих работах А. Н. Колмогоров. Достаточно точ-ные приближения параметра Н для русского и французского языков получил Б. Б. Пиотровский. Он указал на существенную разницу между значениями Н для текстов различного характе-ра (литературных, деловых, разговорной речи).
Понятие "количества информации", содержащейся в тексте, базировалось, по К. Шеннону, лишь на частотных характеристи-ках. В своих фундаментальных работах 60-х годов А. Н. Колмо-горов подошел к определению количества информации с учетом смыслового содержания текста, что позволило уточнить при-ближение величины Н для литературных текстов. Необходимо также отметить, что еще задолго до К. Шеннона частотные ха-рактеристики языка изучал выдающийся русский ученый А. А. Марков. Сегодня часто используются так называемые марковские модели открытых текстов, учитывающие зависимости букв текста от предыдущих букв.
Следующая страница в истории криптографии XX в. посвя-щена телефонным шифраторам, которые были разработаны в 30-х годах и стали широко использоваться во время второй мировой войны. В России разработка телефонного шифратора велась под руководством В.А.Котельникова, ставшего впоследствии акаде-миком, ученым с мировым именем. Ему принадлежит знамени-тая теорема дискретизации (или теорема отсчетов), лежащая в основе теории цифровой обработки сигналов.
Согласно, идея телефонного шифратора была запа-тентована Д. Х. Роджерсом еще в 1881 г., спустя пять лет после изобретения Беллом телефона. Идея состояла в передаче теле-фонного сообщения по нескольким (в простейшем случае -- по двум) цепям поочередными импульсами в некоторой быстро изменяющейся последовательности. Предлагалось разнести та-кие линии на значительное расстояние друг от друга с тем, что-бы устранить возможность подключения сразу ко всем одновре-менно. Подключение же к одной из них позволяло бы слышать лишь отдельные неразборчивые сигналы.
В более поздних разработках предлагались различные пре-образования непосредственно самой речи. Звуки речи преобра-зуются телефоном в непрерывный электрический сигнал, кото-рый с помощью соответствующих устройств изменяется шифра-тором по законам электричества. К числу возможных изменений относятся: инверсия, смещение, или деление диапазона частот, шумовые маскировки, временные перестановки частей сигнала, а также различные комбинации перечисленных преобразований. Естественно, каждое из указанных преобразований производит-ся под управлением ключа, который имеется у отправителя и получателя. Наиболее просто реализуемым являлось преобразо-вание инверсии. Сложнее реализовались временные перестанов-ки. Для их осуществления речевой сигнал в некоторый проме-жуток времени предварительно записывался на магнитофонной ленте. Запись делилась на отрезки длительностью в доли секунд. Отрезки с помощью нескольких магнитных головок разносились и перемешивались, в результате чего в канале слышалась хаоти-ческая последовательность звуков. Использовалась также дви-жущаяся магнитная головка, которая в зависимости от направления движения считывала сигналы быстрее или медленнее, чем они были записаны на ленте. В результате тон сигналов становился выше или ниже обычного, в канале быстро чередовались высокие и низкие звуки, не воспринимаемые ухом. Следует от-метить, что одной из самых сложных проблем, которые возника-ли при разработке телефонных шифраторов, была проблема узнавания восстановленной после расшифрования речи.
В США первый телефонный шифратор, под названием A3, был принят в эксплуатацию в 1937 г. Именно он доставил президенту Рузвельту известие о начале второй мировой войны утром 1 сентября 1939 г. по вызову американского посла в Па-риже. A3 осуществлял инверсию и перестановку 5 поддиапазонов частот. Из 3840 возможных комбинаций () фактически использовались лишь 6, которые менялись 36 раз за каждые 20 секунд. Слабость используемой криптографии компенсирова-лась регулярным изменением частот передачи.
В настоящее время аналоговая телефония уступает место цифровой телефонии. Тем самым и многие технические проблемы, связанные с криптографическими преобразованиями анало-говых сигналов, отпадают за ненадобностью. Дело в том, что оцифрованный сигнал является дискретным и, следовательно, к нему можно применить хорошо разработанную надежную "дис-кретную криптографию".
Во второй половине XX в., вслед за развитием элементной базы вычислительной техники, появились электронные шифраторы, разработка которых потребовала серьезных теоретиче-ских исследований во многих областях прикладной и фундамен-тальной математики, в первую очередь алгебре, теории вероят-ностей и математической статистике. Сегодня именно электрон-ные шифраторы составляют подавляющую долю средств шиф-рования. Они удовлетворяют все возрастающим требованиям по надежности и скорости шифрования. Прогресс в развитии вы-числительной техники сделал возможными программные реали-зации криптографических алгоритмов, которые все увереннее вытесняют во многих сферах традиционные аппаратные средства.
В семидесятых годах произошло два события, серьезно повлиявших на дальнейшее развитие криптографии. Во-первых, был принят (и опубликован!) первый стандарт шифрования данных (DES), "легализовавший" принцип Керкгоффса в криптографии. Во-вторых, после работы американ-ских математиков У. Диффи и М. Хеллмана родилась "новая криптография"-- криптография с открытым клю-чом. Оба этих события были рождены потребностями бурно развивающихся средств коммуникаций, в том числе локаль-ных и глобальных компьютерных сетей, для защиты которых потребовались легко доступные и достаточно надежные крип-тографические средства. Криптография стала широко востребоваться не только в военной, дипломатической, государст-венной сферах, но также в коммерческой, банковской и дру-гих сферах.
Вслед за идеей Диффи и Хеллмана, связанной с гипотетическим понятием однонаправленной (или односторонней) функции с секретом, появились "кандидат" на такую функ-цию и реально осуществленная шифрсистема RSA с откры-тым ключом. Такая система была предложена в 1978 г. Райвестом, Шамиром и Адлеманом. Парадоксальным казалось то, что в RSA для зашифрования и расшифрования используются разные ключи, причем ключ зашифрования может быть от-крытым, то есть всем известным. Вслед за RSA появился целый ряд других систем. В связи с несимметричным исполь-зованием ключей стал использоваться термин асимметричная шифрсистема, в то время как традиционные шифрсистемы стали называться симметричными.
Наряду с идеей открытого шифрования Диффи и Хеллман предложили идею открытого распределения ключей, позво-ляющую избавиться от защищенного канала связи при рас-сылке криптографических ключей. Их идея основывалась на сложности решения задачи дискретного логарифмировании, то есть задачи, являющейся обратной для задачи возведения в степень в конечном поле большого порядка.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
