Меню
Поиск



рефераты скачать Исторические основы криптологии

С "Энигмой" теснейшим образом связан ход многих событий периода второй мировой войны. Дело в том, что она являлась источником ценнейших сведений для английских спецслужб, читавших переписку "Энигмы" (в рамках операции "Ультра"). Эта информация стоила так дорого, что У. Черчилль пожертвовал городом Ковентри, когда ему стал известен план германской бомбардировки этого английского города. С "Энигмой" связано также появление первой в исто­рии вычислительной машины, сконструированной в 1942 г. для перебора ключевых элементов группой специалистов-криптографов под руководством известного математика А. Тьюринга.

Еще один патент на дисковую машину был выдан А. Г. Дамму в 1919 г. Устройство этой машины было настоль ко сложным, что никогда не было реализовано. Но его автор основал компанию по производству шифрмашин, которая впоследствии стала прибыльной. Среди вкладчиков капитала были Э. Нобель, племянник знаменитого А. Нобеля, и Ц. Хагелин, управляющий нефтедобывающей компанией братьев Нобелей в России и некоторое время бывший гене­ральным консулом Швеции в Санкт-Петербурге. До 1927 г. эта компания не имела больших успехов. Их появление было связано с именем сына Ц. Хагелина — Б. Хагелина, родивше­гося на Кавказе, проучившегося несколько лет в Петербургском университете и получившего позже диплом инженера-механика в Швеции.

В 1925 г. Б. Хагелину удалось модернизировать одну из машин Дамма, снабдив ее клавиатурой и индикаторными лампочками, как у "Энигмы". Это была также колесная машина, работающая, однако, по иному, чем дисковые машины, принципу. Она получила название В-21. Ее работа была осно­вана на матричном коммутаторе, в котором электрически изменялось соединение строк и столбцов для преобразования буквы открытого текста в букву шифртекста. Эти изменения определялись группой ключевых колес, каждое из которых имело по ободу выдвинутые или вдвинутые штифты. Колеса имели различные числа штифтов, так что период многоалфа­витного шифра, реализуемого машиной, был равен произве­дению чисел штифтов на всех колесах. В 1926 г. Б. Хагелин предложил В 21 шведской армии, которая сделала на нее большой заказ.

В 1927 г. Б. Хагелин возглавил фирму, выкупленную семьей Хагелин. Свою следующую машину В-211 он снабдил печатающим устройством, работавшим со скоростью около 200 знаков в минуту. Она была самой портативной печатающей шифрмашиной в 1934 г.

В том же году французский генштаб заказал Б. Хагелину карманную печатающую машину, которая могла бы обслуживаться одним человеком. Через некоторое время такая машина была изготовлена. Она реализовывала шифр гаммирования, причем для выработки гаммы была использована идея сумми­рующего устройства, состоящего из комбинационных линеек, расположенных в цилиндрическом барабане. На линейках рядами были расположены так называемые рейтеры. При повороте барабана на 360° рейтеры, вступая во взаимодейст­вие с другими элементами схемы, могли выдвигать некоторые линейки влево, причем число выдвинутых линеек и определя­ло значение знака гаммы (от 0 до 25) в данный такт шифрова­ния. Во взаимодействие с рейтерами вступали штифты, рас­положенные на колесах блока дисков, составляющего вторую основную часть машины. Размеры и схема движения дисков

обеспечивали период, приблизительно равный. Как расположение рейтеров, так и расположение штифтов могло легко меняться, они являлись ключевыми элементами. Это была машина С-36, ставшая впоследствии знаменитой. По размерам она была меньше телефонного аппарата, весила вместе с футляром около двух с половиной килограммов. Французы сразу же сделали заказ на 5000 машин. Позднее машина была существенно усовершенствована, ею заинтере­совались в США. В 1939 г. она была взята на вооружение ар­мии США. Под военным наименованием М-209 она использо­валась в качестве полевого шифра на протяжении всей вто­рой мировой войны. Всего было произведено около 140 000 таких машин. Позже фирма Хагелин стала производить широ­ко известные машины С-48, С-52, Т-55 и многие другие.

Среди заметных фигур в криптографии первой половины XX в. выделяется У. Фридман, получивший серьезные теоре­тические результаты в криптоанализе и ставший известным благодаря своим заслугам по вскрытию военных шифров Японии и Германии.

У.Фридман родился в 1891 г. в Кишиневе, в семье пере­водчика, работавшего в русском почтовом ведомстве. В 1892 г. его семья эмигрировала в США, где отец стал зани­маться швейными машинами. У.Фридман в 1914 г. Окончил Корнельский университет по специальности генетика. В городе Итака, где проживала семья Фридмана, крупный бизнесмен Д. Фабиан имел собственные лаборатории по акустике, гене­тике и криптографии. Любопытно, что криптографией Д. Фабиан увлекся, пытаясь доказать, что автором пьес У. Шекспира являлся Ф. Бэкон.

В 1915 г. Д. Фабиан нанял на работу в свое поместье Ривербэнк специалиста по генетике. Им стал У. Фридман. Вско­ре он увлекся криптографией и проявил себя в этом деле. Че­рез некоторое время У. Фридман уже возглавлял в Ривербэнкских лабораториях два отдела — генетики и шифров.

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

Наибольший интерес с точки зрения современной криптографии представляют лекции "Методы раскрытия шифров с длинной связной гаммой" и "Индекс совпадения и его приме­нения в криптографии". В первой из них предлагается бесключевой метод чтения при использовании неравноверо­ятной гаммы. Во второй излагается так называемый к-тест, позволяющий выяснить, можно ли подписать друг под другом две (или более) криптограммы (или отрезки криптограмм) так, чтобы буквы в каждой колонке оказались бы зашифрованы одинаковыми знаками гаммы.

Поступив в 1921 г. на службу в войска связи, У. Фридман успешно применял свои методы для вскрытия машинных шифров. Когда была создана служба радиоразведки, У.Фридман стал ее главой и продолжил свои разработки, самой значимой из которых было вскрытие японской пурпурной шифрмашины.  В  1929 г. он стал широко известен как один из ведущих криптографов мира, когда "Британская энциклопедия" поместила его статью "О кодах и шифрах". С основными результатами У. Фридмана можно познакомиться в четырехтомнике "Военная криптогра­фия".

Выдающиеся результаты в применении математических методов в криптографии принадлежат Клоду Шеннону. К. Шеннон получил образование по электронике и математике в Мичиганском университете, где и начал проявлять интерес к теории связи и теории шифров. В 1940 г. он получил степень доктора по математике, в течение года обучался в Принстонском институте усовершенствования, после чего был принят на службу в лабораторию компании "Bell Telephone".

К 1944 г. К. Шеннон завершил разработку теории секретной связи. В 1945 г. им был подготовлен секретный доклад "Матема­тическая теория криптографии", который был рассекречен в 1949 г. и издан.

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

Разработанные К. Шенноном концепции теоретической и практической секретности (или стойкости) позволяют количе­ственно оценивать криптографические качества шифров и пы­таться строить в некотором смысле идеальные или совершенные шифры. Моделируется также и язык открытых сообщений. А именно, предлагается рассматривать язык как вероятностный процесс, который создает дискретную последовательность сим­волов в соответствии с некоторой вероятностной схемой.

Центральной в работах К. Шеннона является концепция из­быточной информации, содержащейся в текстовых сообщениях. Избыточность означает, что в сообщении содержится больше символов, чем в действительности требуется для передачи со­держащейся в нем информации. Например, всего лишь десять английских слов — the, of, and, to, a, in, that, it, is, i — состав­ляют более 25% любого (английского) текста. Легко понять, что их можно изъять из текста без потери информации, так как их легко восстановить по смыслу (или по контексту). Фактически К.Шеннон показал, что успех криптоанализа определяется тем, насколько избыточность, имеющаяся в сообщении, "переносит­ся" в шифрованный текст. Если шифрование "стирает" избыточ­ность, то восстановить текст сообщения по криптограмме стано­вится принципиально невозможно.

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

Пусть для зашифрования нормативного английского языка применяется шифр простой замены, в котором каждый из 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 секунд. Слабость используемой криптографии компенсирова­лась регулярным изменением частот передачи.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9




Новости
Мои настройки


   рефераты скачать  Наверх  рефераты скачать  

© 2009 Все права защищены.