Новости олимпиады по математике и криптографии

Клод Элвуд Шеннон. 100 лет со дня рождения



Шеннон.jpg

   Выдающиеся результаты в применении математических методов в криптографии получил американский ученый Клод Шеннон. Он учился в Мичиганском университете и стал специалистом в области электроники и математики. Клод Шеннон – знаменитый учёный прошлого столетия. Он стоял у истоков развития такой науки, как математическая теория информации, внёс неоспоримый вклад в развитие теории кодирования и, конечно же, криптографии. До Клода Шеннона криптография представляла собой область знаний, лишь отдалённо похожую на науку. После его знаменитых работ “Теория связи в секретных системах” и “Математическая теория связи” криптография наконец-то приобрела статус науки. 
   Клод Элвуд Шеннон родился в городе Петоски, штат Мичиган (Petoskey, Michigan), 30 апреля 1916 года. Его отец, потомок первых поселенцев Нью-Джерси, был бизнесменом, впоследствии адвокатом и, наконец, в течение некоторого времени судьей в городе Гэйлорде (Gaylord). Его мать - дочь эмигрантов из Германии, была учителем и в течение ряда лет - директором школы в Гэйлорде. Стоит обратить внимание на деда Шеннона, фермера и изобретателя. Среди его конструкций – посудомоечная машина и ряд механизмов сельскохозяйственного назначения. 
   Первые 16 лет своей жизни Клод провел в Гэйлорде, окончив местную школу в 1932 году и показав при этом склонность к механике. Его любимыми предметами в школе были физика и математика, дома же он занимался конструированием моделей самолетов, радиоуправляемых корабликов и телеграфа для связи с жившим в полумиле другом. Телеграф этот использовал колючую проволоку, огораживающую местное пастбище. Необходимые для этих занятий деньги Клод зарабатывал, разнося газеты и телеграммы, в юношестве он работал курьером службы Western Union, а также ремонтируя радиоаппаратуру в том числе для местного универмага. Героем его детства был Эдисон, оказавшийся, как он потом узнал, дальним родственником - они оба были потомками Джона Огдена, одного из руководителей колонизации. Кроме того, Клод интересовался деятельностью множества ученых, таких как Ньютон, Дарвин, Эйнштейн и Фон Нейман. 
   В 1932 Шеннон поступил в университет Мичигана, следуя по стопам своей сестры Катерины, только что получившей там степень магистра по математике. Именно там у него впервые проявился интерес к теории связи и криптографии. Шеннон выбрал курс, посещая который познакомился с работами Джорджа Буля. В 1936 Шеннон стал бакалавром по электротехнике и математике; этот параллельный интерес к математике и инженерным специальностям он сохранил и в дальнейшем. В том же году он получил должность лаборанта на отделении электротехники в Массачусетском Технологическом Институте (Massachusetts Institute of Technology, знаменитый M.I.T.). Эта должность давала Клоду возможность продолжать обучение, работая лишь часть времени. Деканом тамошнего инженерного факультета был В. Буш (Vannevar Bush, 1890-1974). В то время как некоторые исследователи уже активно вели разработки цифрового компьютера, Буш занимался воплощением в жизнь классической идеи дифференциальной машины Чарльза Бэббиджа. 
   Конечно, с современной точки зрения, аналоговая машина, обеспечению функционирования которой Шеннон посвящал свое рабочее время под руководством Буша, выглядит эдаким монстром. За исключением электромоторов, все остальные узлы были механическими. Тем не менее, сия шумно бряцающая шестернями и приводами конструкция, получившая известность под именем «дифференциального анализатора», успешно справлялась с решением обыкновенных дифференциальных уравнений высоких порядков. Ввод параметров очередного уравнения занимал от двух до трех дней, процесс решения – не менее того. Если же менялась постановка задачи, то машину следовало разобрать на части и вновь собрать в новой конфигурации. Не для того ли нужна была «рабочая сила» в лице будущего создателя теории информации? Какова роль зубчатых колес? Их сочленения воспроизводят передаточные числа, необходимые при вычислениях в десятичной нумерации. В двоичной системе счисления «зубьев» понадобится меньше, правда шестеренок – гораздо больше. Но можно обойтись и другими составляющими конструкции! Эта работа идеально соответствовала способностям и интересам молодого К. Шеннона - он работал на дифференциальном вычислителе Буша, наиболее совершенной вычислительной машине того времени, способной аналоговым образом решать дифференциальные уравнения вплоть до шестого порядка. Работа его заключалась в переводе уравнений в "механические термины", подготовка и запуск машины для различных начальных условий. Иногда этот процесс требовал совместной работы до пяти человек. Изучая сложные, узкоспециальные электросхемы дифференциального анализатора, Шэннон увидел, что концепции Буля могут получить достойное применение. Интересной была также и электрическая цепь, управлявшая этим вычислителем, которая включала в себя более сотни реле. Работая с ней, Шеннон заинтересовался теорией построения таких цепей. Он изучал символическую логику и булеву алгебру на математических курсах в Мичигане и понимал, что это именно то, что требуется для описания таких бинарных систем. 
   Шеннон развил эти идеи в 1937 году, будучи в Нью-Йорке, в Лабораториях Белла (Bell Telephone Laboratories), и затем, вернувшись, в своей дипломной работе в Массачусетсе. Статья, написанная с его магистерской работы 1937 года «Символический анализ реле и коммутаторов» («A Symbolic Analysis of Relay and Switching Circuits»), была опубликована в 1938 году в издании Американского института инженеров-электриков (AIEE). В этой работе, положившей начало современной теории переключательных схем, он продемонстрировал, как применение аппарата булевой алгебры помогает их оптимизировать. Нужно ли добавлять, что рабочий алфавит включает лишь два символа – 0 и 1? Много позднее профессор Говард Гарднер (H. Gardner) из Гарвардского университета отозвался об этой работе как о «возможно самой важной и, одновременно, самой знаменитой магистерской диссертации столетия». Но и тогда ее значимость была высоко оценена научным сообществом: автору присудили престижную премию для молодых ученых (до 30 лет) за лучшую работу года в области инженерных дисциплин. 
   Летом 1938 года он занимался исследовательской работой в Массачусетсе, и осенью был переведен с отделения электротехники на отделение математики, где начал работу над докторской диссертацией. Примерно в это же время Шеннон занимался разработкой идей в области вычислительных машин и систем связи. В письме от 16 февраля 1939 года он писал В. Бушу о зависимости между временем, пропускной способностью, шумом и искажениями в системах связи, а также о разработке вычислительных систем для выполнения символических математических операций. По совету Буша Шеннон решил работать над докторской диссертацией по математике в MIT. Идея будущей работы Шеннона родилась у Буша летом 1939 года, когда он работал в одном из подразделений этого института, находящегося в Колд Спринг Харбор в Нью-Йорке (Cold Spring Harbor, N.Y.), которое тогда занималось генетикой. Вскоре В. Буш был назначен президентом Carnegie Institution в округе Вашингтон и предложил Шеннону принять участие в работе, которую делала Барбара Баркс (Barbara Burks) по генетике, он посоветовал Шеннону заняться с точки зрения алгебры проблемой хранения генетической информации. Шеннон провел там лето 1939 года, работая с Барбарой Баркс над диссертацией, которую он назвал «Алгебра в теоретической генетике». Руководителем диссертации со стороны MIT был профессор Фрэнк Л. Хичкок (Frank L. Hitchcock), занимавшийся алгеброй. Именно генетика, по мнению Буша, могла послужить предметом приложения усилий Шеннона. Докторская диссертация Шеннона была завершена весной 1940 года. Шеннон получает Докторскую степень по математике и степень магистра по электротехнике. Так случилось, что для специалистов в этой области тогда работа осталась неизвестной, опубликовали ее лишь в 1993 году, в сборнике избранных трудов Шеннона. Сам он больше к вопросам генетики не обращался. Диссертация также стала причиной вручения Шэннону премии Американского института инженерии имени Альфреда Нобеля в 1940 году. Цифровые цепи — это основа современной вычислительной техники, таким образом, результаты его работ являются одними из наиболее важных научных результатов ХХ столетия. Летом 1940 года Шеннон занимался дальнейшими исследованиями в области коммутирующих электрических цепей в Лабораториях Белла, разработав новый метод их проектирования, позволявший существенно сократить число контактов в них. Результаты этой работы были опубликованы в статье "Разработка двухконечных коммутирующих цепей ("The Synthesis of Two-Terminal Switching Circuits"). 
   В качестве национального стипендиата Шеннон провел академический 1940-41 год в Принстоне, работая под руководством известного математика Германа Вейля (Hermann Weyl). После чего на долгие годы, вплоть до 1972, обосновался в Bell Telephone Laboratories в штате Нью-Джерси. Там его давно знали, ведь летние месяцы, свободные от учебы в MIT, молодой ученый стажировался у них. Группа, в которую он попал, занималась разработкой эффективных методов передачи информации и повышения надежности протяженных телефонных и телеграфных линий. Да и, собственно, сама Bell Labs возникла в связи с подобными техническими задачами, выделившись в 1925 году из AT&T в качестве исследовательского подразделения. Шеннон провел 15 лет в Лабораториях Белла в достаточно хорошем окружении - в это время там работали многие первоклассные математики, такие как Джон Пирс (John Pierce), известный своей работой в области спутниковой связи, Гарри Найквист (Harry Nyquist), много сделавший в теории обнаружения сигналов, Хендрик Бод (Hendrik Bode), занимавшийся обратной связью, создатели транзистора Браттин, Бардин и Шокли (Brattain, Bardeen и Shockley), Джордж Стибиц (George Stibitz), создавший первый (1938 год) релейный компьютер; Барни Оливер (Barney Oliver), выдающийся инженер, и другие. 
   В военное время появились специфические задачи, в частности, обнаружение и анализ возможных целей вражеских самолетов и ракет. Результаты этой работы оказались особенно актуальными в связи с массированными бомбардировками Англии. Торнтон С. Фрай (Thornton C. Fry), глава отделения математики в Bell Labs, был в это время членом комитета по разработке систем управления зенитным огнем – Америка вооружалась в связи с европейской войной; он предложил Шеннону также поработать на оборону. Вернувшись в Bell Labs, Шеннон присоединился к группе, разрабатывающей устройства для обнаружения самолетов и ракет противника и наведения зенитных орудий; задача эта была актуальной в связи с созданием в Германии ракет Фау-1 и Фау-2. Без этих систем наведения потери Англии в войне были бы существенно большими. 
   Самого же Клода в то время заинтересовали возможности защиты передаваемой информации от несанкционированного чтения. «Во время Второй мировой войны, — рассказывал Шеннон, — компания «Белл» работала над засекречиванием информации. Я тогда занимался системами связи и был назначен в несколько комиссий, изучавших криптоаналитические методы. Начиная примерно с 1941 г., исследования в области математической теории связи и теории шифров велись мной одновременно. Я трудился в обеих областях сразу, и кое-какие идеи в одной из них возникали у меня, когда я работал в другой. Я не хочу сказать, что одна из этих областей доминирует над другой. Просто они настолько тесно связаны, что их невозможно разделить». 
   Клод Шеннон был первым, кто подошел к криптографии с подлинно научной точки зрения. Он впервые сформулировал теоретические основы криптографии и ввел в рассмотрение многие понятия, без которых эта наука немыслима в наши дни. Одной из главных заслуг Шеннона считается исчерпывающее исследование понятия абсолютной секретности систем - он доказал существование абсолютно стойких, невскрываемых шифров, и сформулировал условия, необходимые для этого. Кроме того, Шеннон определил основные принципы, которым должны соответствовать надежные шифры. Именно он ввел в рассмотрение понятия перемешивания и рассеивания, и предложил строить стойкие криптографические системы из относительно несложных преобразований. 
   В 1945 году Шеннон подготовил закрытый отчет, посвященный математическим аспектам криптографии «Теория связи в секретных системах». В открытой печати переработанную версию стало возможным опубликовать лишь после войны, в 1949 году Журнал «Bell System Technical Journal» (BSTJ) поместил на своих страницах статью «Communication theory of secrecy systems». Принято считать, что именно эта работа послужила началом обширных исследований в теории кодирования и передачи информации, и, по всеобщему мнению, придала криптографии статус науки. В этой статье, Шеннон определил основополагающие понятия теории криптографии, без которых эта наука уже немыслима. Шеннон связал криптографию с проблемой передачи информации по зашумленному каналу (роль шума в этом случае играет ключ криптосистемы). Эта работа привела в дальнейшем к тому, что Шеннон был назначен консультантом правительства США по вопросам криптографии. 
   Сила ума Шеннона, его огромный вклад в теорию шифровального дела выразились в открытии избыточности как основы криптоанализа: «Вскрытие большинства шифров становится возможным только благодаря существованию избыточности в открытых текстах». Шеннон первым сумел объяснить постоянство частот встречаемости букв, а тем самым и такое зависящее от него явление, как криптоанализ, дав возможность глубоко понять процесс аналитического вскрытия шифров. Понимание этого процесса позволяет сделать ряд выводов. Получается, что чем меньше избыточность, тем труднее аналитическим путем прочесть криптограмму. 
   Перед зашифрованием Шеннон рекомендует обязательно проделывать над открытым текстом операцию, которая убирает все излишества. То обстоятельство, что из текста можно без особого вреда убрать гласные буквы, дает простейший способ существенного усовершенствования почти любой шифрсистемы. Следующий вывод состоит в том, что для прочтения криптограммы, открытый текст которой обладает низкой избыточностью, требуется, чтобы она была более длинной, чем в случае криптограммы с высокой избыточностью. Шеннону удалось определить количество шифртекста, необходимого для получения единственного правильного решения задачи вскрытия шифра при условии, что соответствующий открытый текст имеет известную степень избыточности. Необходимое для этого количество букв он назвал «расстоянием единственности» и описал, как вычислить его с помощью довольно сложной формулы. Эта формула, естественно, видоизменяется для различных шифров, но непременным ее членом всегда остается избыточность. 
   В одной из своих ранних работ, в которой Шеннон исходил из 50-процентной избыточности английского языка, он установил, что расстояние единственности для шифра однобуквенной замены составляет 27 букв, для многоалфавитных шифров с известными алфавитами — двойную длину периода, а с неизвестными алфавитами — 53 длины периода. Наиболее интересное применение шенноновской формулы расчета расстояния единственности связано с определением правильности решения задачи аналитического вскрытия шифра. Шеннон писал: «Вообще можно утверждать, что если ключ и предложенный метод позволяют прочитать криптограмму при наличии шифртекста, длина которого значительно превосходит расстояние единственности, то решение надежно. Если же длина шифртекста имеет тот же порядок, что и расстояние единственности, или короче его, значит, решение весьма сомнительно. 
   Одновременно Клод Элвуд Шеннон начал развивать идеи, которые впоследствии легли в основу прославившей его Теории информации. Целью Шеннона была оптимизация передачи информации по телефонным и телеграфным линиям. В 1956 г. Шеннон становится приглашенным профессором, с 1958 г. - постоянным профессором МТИ, а в 1978 г. - заслуженным профессором в отставке. В 1966 г. в возрасте 50 лет Шеннон ушел на пенсию, оставаясь до 1972 г. консультантом Bell Labs. В 1985 году Клод Шеннон неожиданно посетил Международный симпозиум по теории информации. Клод Шеннон использовал в криптографии уже найденные результаты и собственные достижения в теории вероятностей весьма активно в собственном же изложении теории связи и информации. Ему были присуждены почетные степени университетов Уэйла (магистр, 1954), Мичигана (1961), Принстона (1962), Эдинбурга (1964), Питтсбурга (1964), Оксфорда (1970), а также ряда других, а кроме того - множество научных наград и медалей. Клод Шеннон умер 24 февраля 2001 года в возрасте 84 лет после многолетней борьбы с болезнью Альцгеймера.
Ларин Д.А.
к.т.н.



Возврат к списку