Секей Г. Парадоксы в теории вероятностей и математической статистике (1990) (1151962), страница 48

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 48)

Первый перелом в истории криптографии наступил в двадцатые годы, когда были открыты «одноразовые шифры». Такие одноразовые шифры были впервые использованы в Германии и употреблялись повсюду на протяжении полувека. Различные типы одноразовых шифров считаются очень эффективными и сегодня постоянно используются во многих странах для специальных посланий.

В знаменитой «горячей линии» между Вашингтоном и Москвой также применяются одноразовые шифры. Эти шифры действительно неразгадываемы в принципе, так как различные шифры-сдвиги кодируют каждый символ в исходном тексте, при этом всякий раз сдвиг выбирается случайным образом. Если букву «е» всегда кодировать как «1», то это был бы простой подстановочный шифр, который легко разгадать с помощью статистического анализа (так как «е» вЂ” наиболее часто употребляемая буква во многих языках).

Однако, если «е» кодировать иногда как «а», иногда как «с», а порой как «чг», и выбор замены осуществлять случайно, то такой одноразовый шифр нельзя разгадать даже в принципе. Шифрованный текст ничем не обнаруживает закодированное содержание. Недостаток подобной процедуры заключается в том, что одноразовые шифры можно использовать лишь однажды для единственного послания. Замечательное открытие специалистов по электронике из Станфордского университета Уитфилда Диффи и Мартина Хеллмана революционизировало всю область секретной связи. Под влиянием математической теории сложности они предложили в 1975 г. новый тип шифра, который разгадываем в принципе, но абсолютно не разгадываем на практике.

Точнее, эти новые шифры можно разгадать, но лишь с помощью программ на ЭВМ, которые будут выполняться миллионы лет. Интересно, что процедура шифровки и расшифровки, предложенная Диффн и Хеллманом, несимметрична, т. е. если известен лишь метод шифровки, то с помощью вычислений нереально обнаружить способ расшифровки, а это обеспечивает абсолютную секретность. (Такой метод передачи шифрованных сообщений позволяет добиться того, что Диффи и Хеллман назвали функцией-ловушкой с односторонним входом.) Секрет может быть закодирован и раскрыт разными способами (и для расшифровки требуется более тонкий метод). Основная идея одностороннего шифрования очень проста: два числа легко перемножить, например, произведение чисел 101 и 211 вычисляется просто и оно равно 21311, но если нам нужно найти два числа, которые больше единицы и их произведение равно 21311, то для того, чтобы установить, что единственно возможное решение— это 101 и 211, потребуется значительно больше времени.

Естественно, существуют вычислительные алгоритмы для разложения чисел на множители, но в случае, когда число состоит из 40 — 50 цифр, время, необходимое для нахождения множителей, составило бы миллионы лет. На основе теории простых чисел была найдена простая функция-ловушка: ключ для шифровки зависит лишь от произведения двух простых чисел, в то время как для расшифровки текста необходимо знать сами простые числа. Остановимся подробнее на этой функции-ловушке! Пусть р и д — два больших случайных простых числа. Произведение и этих двух чисел и еще одно случайное число Е являются ключом шифра (Е, п) для пользователя, при этом ключ не обязательно держать в секрете, его можно поместить в какой-либо общий файл, например, в телефонный справочник. Для использования ключа отправитель сначала преобразует свое послание в цепочку цифр, которую он затем разбивает на блоки Вь Вь ....

Каждое число В, в исходном тексте должно быть между 0 и и — 1. Для каждого числа в исходном тексте В~ отправитель вычисляет число в шифрованном тексте С~=В~ по в модулю л (т. е. С~ — остаток при делении Е-й степени числа В~ на и). Такой общедоступный способ шифровки основан на том факте, что хотя нахождение больших простых чисел (р и ч) с вычислительной точки зрения просто, однако разложение произведения двух таких чисел на множители с помощью вычислений в настоящее время нереально, так что, зная лишь (Е, и) и С» безнадежно пытаться найти В» Для расшифровки текста Сь Сь ...

пользователю нужны и и секретный ключ для расшифровки О, получаемый из простых сомножителей р и д числа и. В есть мультипликативно обратное к Е число по модулю (Р— 1) (д — 1), т. е. произведение Е0 по модулю (р — 1) (д — 1) равно 1. (Произведение (р — 1) (г) — 1) дает количество целых чисел между 1 и и, не имеющих с л общих делителей.) После всего этого получатель легко находит Вп С! =(Ва!) = В, по модулю и. Этот метод разработали Ривест, Шамир и Адлеман и он называется системой НЬА. (Лнтс Неигпап М. И. "ТЬе спейс!паиса о1 рпо!!с-Леу сгур1оигарьу", Яс!.

Апгег., 241, 130 — 139, (1979). $!пгпюпв б. Д "Сгур(о!оиу, Ше пгв(иепгацсз о( весите сопггппп1саиоп", ТЛе Ма!Л уи!е!!!яепсег, 1, 233 — 246, (1979). 3Ьапг)г А. "А ро!!попг!а! Игле а!Кот!1Ьпг (ог Ьгеампи Мегые — Ней!пап сгур(овуз(ел!в", )гевеегсЛ Алпоиисегпеи(, 1932.) з) Парадокс поэзии и теории информации В качестве последнего парадокса в этой книге приведу слова моего покойного учителя профессора Альфреда Реньи! «С тех пор, как я начал заниматься теорией информации, я часто размышляю над краткостью стихотворений; почему одна строка стихотворения содержит значительно больше «информации», чем очень короткая телеграмма такой же длины.

Удивительное богатство значений в литературных трудах кажется противоречит законам теории информации. Ключом к этому парадоксу, я думаю, является понятие «резонанса». Писатель не только сообщает нам информацию, но и играет на струнах языка с таким мастерством, что наш разум и даже само подсознание резонируют. Поэт с помощью удачного слова может вызвать цепочку идей, эмоций и воспоминаний. В этом смысле труд писателя — волшебство.» гпдвд ч ПаьраьДОКСОЛОГИЯ В глубине души мы верим в реальность математини, но когда философы указывают нам на парадоксы в математике, мы, конечно, спешим спрятаться за абстракциями н говорим: математнка— зто лишь комбинация бессмысленных символов... Ж.

А. Э. Дьедомяе, 1970 Как и большинство разделов науки, математика — это также и история парадоксов. Величайшие открытия, как правило, разрешали величайшие парадоксы (вспомните Дарвина и Эйнштейна) и в то же время они в свою очередь были источником новых парадоксов. Метод обучения Сократа, по которому о новых идеях надо узнавать через парадоксы, является самым фундаментальным, так как процесс научного познания сам опирается на парадоксы. Для развития дедуктивной математики огромную роль сыграло то, что (несмотря на мнение пифагорийцев, что «все есть число», т. е.

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

Величайший парадокс математики средних веков состоял в том, что «ничто», т. е. нуль, следовало рассматривать как нечто и как-то его обозначать. В результате, благодаря индоарабскому способу записи чисел, вычисления в значительной степени облегчились. Позднее возникли парадоксы, связанные с отрицательными и затем комплексными числами. Например, один из парадоксов утверждал, что равенство ( — 1):1=1: ( — 1) невозможно, так как отношение меньшего числа к большему не может равняться отношению большего числа к меньшему.

В наше время во всех разделах математики появилось несколько новых парадоксов, начиная от разрешимости алгебраического уравнения и кончая геометрией Бойаи. Ин- тересно, что уже в первой половине прошлого века чешский математик из Праги Б. Больцано посвятил целую книгу парадоксам бесконечного («Рагабохеп с)ез Опепб))с)теп»), хотя наиболее любопытные парадоксы бесконечного появились лишь после опубликования в 1872 г.

труда Г. Кантора по теории множеств. Ведущие математики прошлого века такие, как Гаусс, Коши, Кронекер, Пуанкаре и другие, отвергали понятие актуальной бесконечности и приписывали бесконечности лишь символическое значение. Однако теория Кантора, в которой используется понятие актуальной бесконечности, является краеугольным камнем современной математики, хотя следует подчеркнуть, что «ужас перед бесконечным» все еще не исчез. На самом деле новые парадоксы увеличивают число приверженцев «финитизма».

Характеристики

Список файлов книги