Современная электронная библиотека ModernLib.Net

Компьютерра (№255) - Журнал «Компьютерра» № 31 от 29 августа 2006 года

ModernLib.Net / Компьютеры / Компьютерра / Журнал «Компьютерра» № 31 от 29 августа 2006 года - Чтение (стр. 8)
Автор: Компьютерра
Жанр: Компьютеры
Серия: Компьютерра

 

 


Компакты же (электронные) давно все движение свели к приводу объектива/диафрагмы (заметим, более простому, чем в ЗФК) и недозатвору-заслонке для съемки теневого кадра [Он потом вычитается из сделанного кадра — таким образом устраняется значительная часть шумов]. Кроме того, сборка электронной начинки лучше автоматизирована и вообще менее критична к квалификации трудолюбивых китайских девушек, следовательно, дешевле. Поэтому рано или поздно и затвор (имеющий, к слову, ограниченный ресурс, см. врезку), и зеркало просто канут в воды Стикса, оставив о себе приятные воспоминания седых дядек с кофрами и, возможно, название класса камер («зеркалки»): история знает множество примеров подобных рудиментов — «флэш-диск», «картовод», «электронная бумага», «автомагнитола», «встроенная видеокарта» и т. п.

Зеркало и затвор надежно закрывают матрицу, продлевая ее ресурс и защищая от перегрева, но одновременно они не дают осуществлять визирование по экрану, что облегчило бы съемку из нестандартных положений: от бедра, над головой, «от пуза»… Да и «макрушники» смогли бы перестать, уподобляясь своим фотомоделям, ползать среди травы. К тому же, экран — это залог простоты управления для тех, кто просто хочет получать снимки хорошего качества, не задумываясь о разрешении объектива. Безусловно, полнофункциональный LCD привлек бы внимание этой немалой части целевой аудитории и помог бы преодолеть страх перед «сложностью» SLR-камер. Не углубляясь в совсем куцые возможности Fujifilm S3 Pro и Canon EOS 20Da, отмечу, что шаг в нужном направлении уже сделан — это Olympus E-330 (рис. 9) и Panasonic L1 (рис. 5), но первый блин, как известно… Первая ЦЗФК позволяет видеть «картинку» в двух режимах: A (работает вторая матрица, которая заметно меньше и хуже основной) и B (работает основная матрица, но не работает автофокус); у Панасоника и того меньше — только B. Мало кто сомневается, что когда-нибудь эту «фичу» доведут до ума, но вот как и до чьего ума — «наука пока не в курсе дела»…

Один из выходов придуман лет сорок назад и называется «полупрозрачное зеркало». В этой схеме зеркало (а точнее, делительная призма со специальным покрытием) постоянно разделяет падающий на него свет на два потока, один из которых идет на пентапризму, а второй — на затвор/пленку или матрицу. К великому сожалению, приходится забыть о светлом видоискателе — именно это обстоятельство похоронило неплохую, в целом, идею. Среди D-SLR она успела отметиться в замечательных для своего времени (хоть и с несъемными объективами) камерах Olympus E-10/E-20.

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

Кстати, при съемке особо пугливых объектов вышеупомянутый сочный звук тоже может стать помехой, так что для промышленного (и не только) шпионажа зеркалка вряд ли подойдет.

И еще одна проблема, связанная на сей раз не только с зеркальным видоискателем, но и с системой TTL-автофокуса. Дело в том, что для наиболее качественной фокусировки (автоматической ли, ручной ли) на сенсор (глаз) должно попадать как можно больше света, поэтому диафрагму нужно держать открытой. Но в этом случае невозможно воспользоваться одним из главных преимуществ SLR — управлением ГРИП. Как водится, для обхода пришлось городить целый огород: в камерах с ручной фокусировкой диафрагма прыгающая и закрывается при половинном (и полном тоже) нажатии на спуск, в АФ-зеркалках же появилась специальная кнопка DOF (просмотр ГРИП или репетир диафрагмы, см. начало статьи). То есть проблемы-то и нет, однако методы все равно какие-то неизящные.

Зеркало, пентапризма / пентазеркало и все сопутствующие механические системы занимают в корпусе немало места и фактически ограничивают (наряду с объективом и матрицей) минимальные размеры и вес камеры. И это — еще одно обстоятельство, мешающее всемирному успеху этого вида фотоаппаратов среди «обычных» потребителей. Увы, зеркалка никогда не станет размером с Nikon S6, как автомобиль не может быть размером с мопед. И хотя с объективами все не так уж плохо — камера с одним из «блинчиков» Pentax помещается в боковой карман куртки — «тушки» по-прежнему тормозят прогресс. Все, что можно выжать из отсутствия механизма протяжки пленки, уже выжали, на очереди пентапризма: Olympus E-300/330 — лишь первые ласточки. Когда же дело дойдет-таки до зеркала, аббревиатура SLR станет условностью и зеркалки в современном понимании этого слова умрут.

К счастью, вместе с ними уйдет в прошлое и большой рабочий отрезок, который уже полвека мешает фотоконструкторам использовать простые и эффективные оптические схемы объективов. В большей степени это касается широкоугольников — зеркало не дает расположить заднюю линзу как можно ближе к пленке/матрице, именно поэтому себестоимость «маломиллиметровой» зеркальной оптики всегда будет превышать таковую у дальномерок и компактов. Специалисты Sony неплохо воспользовались этой ситуацией — действительно хороший объектив R1 (Zeiss Vario-Sonnar T* ~24—120/2.8—4.8) нельзя «отпилить и приставить» к SLR-камере, ведь зазор между ним и матрицей не должен превышать 2 мм. А оптикам компании Cosina при проектировании своего уникального фикса Voigtlander UltraWide Heliar 12/5.6 пришлось требовать у «тушек» наличия системы предварительного поднятия и блокирования зеркала: иначе оно просто не сможет нормально двигаться. Да уж, как бы было проще совсем без этой капризной детали!

Следующий подводный камень, о котором, потирая руки, молчат маркетологи, связан с конструкцией ЗФК лишь косвенно. Любая зеркальная система отличается тем, что в нее нужно вкладывать деньги, а точнее — Деньги. Ну что может приобрести владелец Canon Pro1? Ну, чехольчик. Ну вспышку, ну ПДУ для внезапной съемки внезапных бурундуков, ну на крайняк — макронасадку. Владелец же Canon EOS 350 имеет счастливую возможность утопить даже весьма устойчивый семейный бюджет: проделать брешь в четырех-пятизначную сумму запрещенных к произношению денежных единиц совсем не сложно… А все потому, что доступна главная статья расходов любого фотографа — оптика. Вагон EF-оптики, маленькая тележка EF-S-оптики, с переходниками уже подгоняют железнодорожный состав FD-объективов и целый флот сухогрузов с M42 и K. Многие из них дешевы, но многие потребуют длительного накопления средств только на поездку в ту страну, где они продаются. Факты упрямы — для раскрытия возможностей своей зеркальной камеры нужно выложить раза в четыре больше денег, чем на сам аппарат.

И тут снимающие всех стран должны в едином порыве поблагодарить компанию Olympus за ее гениальную идею — double kit [Sony уже подхватила (SONY A100), на очереди остальные]. Покупая аппарат, за сравнительно небольшую доплату пользователь получает сразу два зум-объектива, покрывающие фокусные расстояния от 14 до 150 мм (в пересчете на 35-мм кадр 28—300), что, в свою очередь, охватывает 95% потребностей «обычного человека». Замечательно, что «Оля» решила не останавливаться на полдороге и уже анонсировала концепцию наборов для различных сфер применения: архитектурной, подводной, пейзажной, макросъемки и съемки в путешествиях. Разумеется, максималистам такие вещи не подойдут, но привлечь внимание тех, кто до сих пор не обзавелся SLR-камерой, опасаясь неумеренных трат, уже получилось. А чем больше аппаратов будет продано, тем больше их будет произведено, следовательно, тем ниже упадет цена [Представители Nikon уже говорят о возможности снижения цены на D-SLR начального уровня до 300 зеленых енотов]. Один кит — хорошо, а даблкит — лучше!

Кстати, о сменных объективах. Цифра принесла еще одну неприятную (хотя и преувеличенную) проблему: пыль. В любой ЦЗФК есть, по крайней мере, одно разъемное соединение — байонет, открывающее дорогу к святая святых — матрице аппарата. Пока весь мир снимал на пленку, проблема пыли вообще не стояла: если осядет на кадре, то уже на следующем ее не будет. А вот если светочувствительный элемент постоянен… В результате форумы пестрят страшными историями о том, как племянник однокурсника жены брата приятеля шурина (по другим данным — зятя), стремясь избавиться от назойливой проблемы, поцарапал матрицу и отдал за замену в сервис-центре Бешеные Деньги. Допугались — Sony одним из главных преимуществ первой камеры своей системы Alpha (в девичестве Minolta A) называет двойную защиту от злобных частиц: антистатическое покрытие плюс ультразвуковое стряхивание (почти как в олимпусах). Причем многие уважаемые завсегдатаи форумов уже ставят «пылестрях» на третье место по «вкусности», сразу после мегапикселов и стабилизатора.

И наконец, последнее: зеркальные аппараты не умеют снимать видео. В основном, по тем же причинам, что неоднократно указывались прежде — в нормальном состоянии матрица надежно прикрыта зеркалом и затвором; ее нельзя перегревать, постоянно снимая сигнал. И вообще, считается, что для этих целей есть видеокамеры; фотоаппарат должен делать фотографии, а не служить фонариком, секундомером, калькулятором калорий и массой других вещей, встраиваемых ныне в сотовые телефоны. Вот свежий пример из мира компактов — Fujifilm V10 (рис. 11) с тремя встроенными играми. Большинство техноапологетов SLR, думаю, предадут немедленной анафеме первую же компанию [Многие думают, что таким ниспровергателем устоев будет вечный enfant terrible околокомпьютерной индустрии — Samsung. Впрочем, применяемый при таких прогнозах тезис «какие сотовые, такие и зеркалки будут», кажется автору малообоснованным], позволившую себе внести элементы развлекаловки в Храм Искусства.


Некоторым утешением для ЦФК-энтузиастов (слабым) может послужить тот факт, что любителям дальномерок тоже несладко: Leica для системы M выпускает лишь один объектив стоимостью меньше килобакса. Купи себе легенду, ага. Зато почти на любую 35-мм RF-камеру можно (опять же, через переходник) нацепить оптику под резьбу M39, а таковой до сих пор немало — хорошей и разной.

Итого

Теперь вы знаете не только преимущества той и другой схемы, но и недостатки. Как ни странно, вывод будет банальным: никто, кроме самого покупателя, не в состоянии решить, нужна ли ему зеркальная камера или достаточно ограничиться компактом (дальномерки и тому подобное все-таки следует покупать лишь тем, кто твердо знает, зачем ему влезать на эти галеры). Могу лишь посоветовать:

— Уважаемый, хотя и незнакомый читатель! Если ты считаешь (планируешь сделать) фотографию своим настоящим хобби, которому не жаль отдать значительный кусок свободного времени, массу места под сведения в голове и фотокарточки в доме, а также нехилый кусок заработанных дензнаков, то свой выбор ты уже сделал. И пусть в твоей душе не екает что-то при виде полностью механических аппаратов, пусть фокусировка вручную надолго останется для тебя пережитком старины, а разница между EF-S 18—55/3.5—5.6 и EF 35/1.4L USM кажется пренебрежимо малой, пусть печатать форматами 20х30 и 30х45 ты будешь два-три кадра в год, лучше первой камеры, чем недорогая зеркалка, тебе не найти. Удачи!

P.S.

Это карма — как ни начну писать статью, вечно новая зеркалка выходит. Вот и сейчас — Canon EOS 400D уже практически анонсирован.

Наука: Эллиптическая криптография

Автор: Сергей Николенко

But the security of cryptosystems based on elliptic curves is not well understood, due in large part to the abstruse nature of elliptic curves. Few cryptographers understand elliptic curves, so there is not the same widespread understanding and consensus concerning the security of elliptic curves that RSA enjoys. Over time, this may change, but for now trying to get an evaluation of the security of an elliptic-curve cryptosystem is a bit like trying to get an evaluation of some recently discovered Chaldean poetry.

«Стойкость криптосистем, основанных на эллиптических кривых, недостаточно изучена, во многом из-за переусложненного взгляда на природу самих эллиптических кривых. Очень немногие криптографы понимают, что такое эллиптические кривые, поэтому, в отличие от RSA, нет широкого понимания и консенсуса относительно стойкости, обеспечиваемой их использованием при шифровании. Со временем ситуация может измениться, но сейчас получить оценку стойкости криптосистемы, основанной на эллиптических кривых, — все равно что получить оценку недавно обнаруженной древневавилонской поэзии»

Рональд Ривест, создатель RSA, комментарии к предлагаемому стандарту FIPS, 1997

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

Как вы уже, наверное, догадались, все изменилось в одночасье, когда мне довелось познакомиться с этими протоколами поближе. Оказалось, что идеи, лежащие в их основе, немногим сложнее классических схем RSA и Диффи-Хеллмана. Во всяком случае, суть «эллиптического шифрования» (будем иногда для краткости использовать этот не вполне корректный термин) я намереваюсь рассказать прямо сейчас, фактически с нуля.

Криптография с открытым ключом

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

Среди систем с секретным ключом есть очень стойкие: пока вы не узнаете или не подберете ключ, расшифровать сообщение невозможно. Более того, дешифровщику придется решать, является ли то, что у него получилось, валидным (проще говоря, «правильным») сообщением. Конечно, если был зашифрован текст на естественном языке, распознавание труда не составит. Кроме того, на помощь в случае естественного языка приходит еще и частотный анализ (вспомните Холмса, с помощью частотно-лингвистического анализа разгадавшего записки, написанные «пляшущими человечками»). Но если сообщение — набор цифр (координаты военной базы или количество самолетов на ней), то дешифровальщику может быть практически невозможно установить, правильно ли оно расшифровано.

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

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

Криптография с открытым ключом разрывает этот круг. В криптосистеме уже не один ключ, а два — открытый и секретный. Алиса публикует свой открытый ключ — он доступен для всех. Боб (эти имена в криптографии используются с незапамятных времен) берет свое сообщение и шифрует его при помощи ключа Алисы (алгоритм шифрования известен). Однако ни Боб, ни кто-либо другой не может расшифровать это сообщение. Для этого нужно знать секретный ключ Алисы. Преимущество в том, что Алисе не нужно ни с кем делиться своим ключом. Только она одна должна иметь возможность расшифровать сообщение Боба, а чтобы зашифровать его, секретный ключ не нужен.

Криптография с открытым ключом уязвима по отношению к некоторым очевидным атакам. Вот алгоритм, который гарантированно взломает любую такую криптосистему: перебирать всевозможные сообщения, шифруя их при помощи открытого ключа, до тех пор пока результат не совпадет с шифром, который мы хотим разгадать. Это на первый взгляд может показаться обескураживающим, но на самом деле ничего страшного нет: никто никогда не переберет даже все возможные комбинации ста битов входа; что уж говорить о ключах длиной 512 или 1024 бит. Главное — чтобы у противника не было возможности сделать что-нибудь поумнее. Это и есть главная задача построения стойких криптосистем.

RSA и криптосистема Диффи-Хеллмана

Как строить криптосистемы с открытым ключом? Мы уже знаем, что Боб должен суметь зашифровать сообщение, но потом никто не должен иметь возможности расшифровать его — кроме Алисы, конечно. Говоря математическим языком, функция шифрования должна легко вычисляться, а вот вычисление обратной к ней должно быть «практически неосуществимым» [Объем вычислений должен расти быстрее полинома любой степени от длины ключа или аналогичного «параметра безопасности» системы]. Одной из первых криптосистем с открытым ключом была система RSA, названная так по именам создателей: Ривеста (Rivest), Шамира (Shamir) и Адлемана (Adleman) [Примечательно, что на самом деле приоритет принадлежит британскому математику Клиффорду Коксу (Clifford Cocks), который придумал эту криптосистему в 1973 году. Однако его работа оставалась неизвестной до 1997 года, так как относилась к разряду top secret (не только в Советском Союзе ученые работали на ВПК)]. Система, созданная в 1977 году, оказалась на редкость жизнеспособной и по сей день успешно применяется в огромном количестве приложений. Успех не в последнюю очередь объясняется простотой и глубиной математической идеи, лежащей в основе RSA. Поскольку для понимания сути эллиптических шифров лучше сначала «потренироваться на кошках», изложим эту идею и мы (это потребует некоторых знаний по элементарной теории чисел, см. врезку внизу справа). В ее основе — предположение о «практической неосуществимости» разложения на множители больших целых чисел.

С другой сложной для решения проблемой — дискретным логарифмированием — связана так называемая криптосистема Диффи-Хеллмана (Diffie-Hellman), которая появилась даже раньше, чем RSA, — в 1976 году [Кстати, сам Мартин Хеллман утверждает, что по справедливости ее нужно было бы называть криптосистемой Диффи-Хеллмана-Меркле; Ральф Меркле (Ralph Merkle) фактически был автором идеи криптографии с открытым ключом. К сожалению, криптосистема, которая все-таки была названа его именем — основанная на «задаче о рюкзаке» система Меркле-Хеллмана, — оказалась криптографически нестойкой и, как следствие, не приобрела популярности]. Ее краткое математическое описание см. во врезке на следующей странице.

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

Эллиптические кривые

Начнем сразу с определения. Эллиптические кривые — это кривые вида y^2 =x^3 +ax+b . [В полях размера 2m («полях характеристики 2»; к ним относится и привычное программистам поле из двух элементов) определения становятся чуть более сложными, а стандартные доказательства и рассуждения перестают работать; в алгебре и алгебраической геометрии случай характеристики 2 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]

Они занимают промежуточную нишу между коническими сечениями и кривыми более высоких порядков — про них известно не все, но многое. О том, что это серьезный объект для исследований, говорит хотя бы то, что именно теория эллиптических кривых привела Эндрю Уайлса к доказательству великой теоремы Ферма. Но нас будут интересовать куда менее эзотеричные материи.

Хотя примеры, изображенные на стр. 58, нарисованы на плоскости, то есть на множестве пар вещественных чисел (x, y), в криптографии все структуры, разумеется, должны быть дискретными. Поэтому решения уравнения ищутся над конечными полями. Чтобы конечное множество могло стать полем, его размер должен иметь вид p^m , где p — простое число. Конечное поле с простым количеством элементов (m=1) можно представлять как множество неотрицательных целых чисел, меньших p, в котором все алгебраические операции производятся «по модулю p» (то есть с переходом к остатку от деления результата на p). В криптографии используются конечные поля двух типов — с простым количеством элементов (m=1) и «поля характеристики два» (у которых 2 m элементов); мы ограничимся первым случаем. Кстати, термин «эллиптическая кривая» над конечным полем в изрядной степени теряет смысл — какая же это кривая, если это конечное множество точек? Но о терминах спорить — последнее дело, особенно в математике, где белая лошадь, в полном соответствии с Гунсунь Лун-цзы, может оказаться вовсе не лошадью.Ранее мы говорили, что сложность криптосистемы Диффи-Хеллмана связана с дискретным логарифмированием. Однако конструкция, аналогичная использованной в этой системе, может быть реализована над любым множеством, где есть похожая на умножение операция (например, сложение), подчиняющаяся своим естественным законам (такое множество называется в математике группой). Суть применения эллиптических кривых в криптографии сводится к тому, что группа чисел по простому модулю (как было в криптосистеме Диффи-Хеллмана) заменяется группой решений уравнения y^2 = x^3+ax+b. Осталось лишь указать, как складывать друг с другом решения такого уравнения.

На плоскости это делается так, как показано на рисунке выше. Чтобы сложить две точки на эллиптической кривой, нужно провести через них прямую. Она пересечет кривую в третьей точке. Эту третью точку мы будем считать суммой первых двух со знаком минус; чтобы получить собственно сумму, отразим полученную точку относительно оси X. Можно проверить, что такое сложение будет ассоциативным. Остается только один вопрос: что делать, когда третьей точки нет? Например, если нужно сложить точку с самой собой, то для этого нужно провести касательную в этой точке. Если мы проведем касательную в точке (0, 0), она будет направлена вертикально вверх; казалось бы, никакой третьей точки уже не получится. Это затруднение решается просто: к множеству решений эллиптического уравнения добавляют еще одну точку O, о которой проще всего думать как о бесконечности (бесконечные значения x и y действительно удовлетворяют уравнению). Сумма двух точек (0, 0) в нашем примере будет равна O. O играет роль нуля в этом своеобразном сложении. Мы уже говорили, что обратный элемент получится, если отразить точку относительно оси X; если теперь соединить прямой точку и ее обратную, прямая будет вертикальной, и третьей точкой как раз будет бесконечность:

P+(—P)=O.

Над конечными полями таких картинок не нарисуешь, но если выразить эти операции алгебраически, то все сойдется.

Вот, собственно, и все. Эллиптический аналог криптосистемы Диффи-Хеллмана выглядит так. Алиса и Боб выбирают (и сообщают всем) эллиптическую кривую, поле и точку B, лежащую на этой кривой. Затем Алиса секретно выбирает число a и подсчитывает точку aB (складывает B с самой собой a раз), а Боб выбирает число b и вычисляет bB. Затем они обмениваются полученными результатами, и их общим секретным ключом становится точка abB. Чтобы взломать этот шифр, нужно научиться по aB и B вычислять a — это в точности аналог дискретного логарифмирования!

В чем же преимущество шифров, основанных на эллиптических кривых? В том, что в них можно использовать меньшие по величине простые числа, чем в классических системах с открытым ключом.

Квантовый взлом

Напоследок поговорим о том, что многим кажется серьезной угрозой для современной криптографии, — квантовых компьютерах и их возможностях. Прежде всего напомню, что квантовая информатика фактически ведет свою историю с того, что Питер Шор (Peter Shor) в 1994 году представил алгоритмы, которые за полиномиальное время раскладывали числа на простые множители и подсчитывали дискретные логарифмы — на квантовом компьютере, разумеется.


Математика системы RSA

Секретный ключ Алисы в RSA — это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, — то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.

Кроме собственно N в открытый ключ входит также число e, которое должно быть меньше числа


Было бы наивно ожидать, что криптосистемы на эллиптических кривых, столь похожие на дискретное логарифмирование, не поддадутся квантовому компьютеру. И действительно, алгоритм Шора можно без особого труда модифицировать так, чтобы он взламывал описанный выше протокол, а равно и другие аналоги классических криптосистем, основанные на эллиптических кривых.

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


Математика криптосистемы Диффи-Хеллмана

Суть криптосистемы Диффи-Хеллмана в том, чтобы перед началом коммуникации с секретным ключом об этом самом ключе договориться (этот процесс в криптографии называют «протоколом key agreement»; кстати, в реальных приложениях криптография с открытым ключом очень часто используется именно для этой цели). Иными словами, цель не в том, чтобы передать сообщение от одного участника к другому, а в том, чтобы у обоих участников в конце концов обнаружилось одно и то же число, которое можно будет использовать как секретный ключ [Есть и «настоящая» криптосистема с открытым ключом, основанная на той же идее — так называемая система ElGamal; она немногим сложнее Диффи-Хеллмана, но описание ее более громоздко, и поэтому для иллюстрации Диффи-Хеллман подходит лучше]. Делается это так: Алиса и Боб выбирают простое число p, по модулю которого будут проводиться все вычисления, и основание g, которое они потом будут возводить в степень. Затем Алиса выбирает число a (никому его не показывая) и передает Бобу (g^a mod p), а Боб выбирает число b и передает Алисе (g^b mod p). Теперь Алисе достаточно возвести полученное число в степень a, а Бобу — в степень b, и у них обоих будет один и тот же ключ, так как, разумеется, g^ab mod p = g^ba mod p. Как видите, ничего сложного. Почему же этот шифр трудно разгадать? Стойкость этой криптосистемы тесно связана с вычислительной трудностью операции дискретного логарифмирования — зная g^a mod p, g и p (все эти числа в принципе доступны противнику), вычислить a. Отметим, что взлом Диффи-Хеллмана вовсе не обязательно решит задачу дискретного логарифмирования — этот вопрос еще остается открытым, но если научатся эффективно вычислять искать дискретные логарифмы, то и Диффи-Хеллман падет тут же.

Редакция благодарит профессора Колледжа Лафайет (Lafayette College) Клиффорда Рейтера (Clifford Reiter) за предоставленные изображения множеств Жюлиа.

ПИСЬМОНОСЕЦ: Прикол в пространстве Лобачевского!

Автор: Леонид Левкович-Маслюк

Живу в глуши, Интернет через дайлап, качаю да читаю «Компьютерру»! Красота! Да, о чем это я? Ах, да! Жил был один англичанин и состряпал сайт на миллион!!! Долларов почему-то, а не фунтов. Ну да ладно, это мелочи, я о своем. О сайте в смысле. Состряпал я сайт www.historyinternet.ru , и вот сижу и думаю, будет у меня миллион рублей или нет? Ну там рублем больше, рублем меньше. Ну почему больше — ответ на сайте. В общем там больше чем 1 000 000. Думаю, программисты меня поймут. Ну вот и все!


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