пнвтсрчтптсбвс
    123
45678910
11121314151617
18192021222324
25262728293031
       

Реклама


  Технологии/Полигон

Ключи от тайны

Основы криптографии. Шифрование с помощью ключа

Основы криптографии. Шифрование с помощью ключа 26.01.2009
10:20
Юлия Волкова

 

Начало читайте в статье «Тайны тайнописи»

 

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

 

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

 

Откройте ключ

 

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

 

Основы криптографии. Шифрование с помощью ключаИзюминкой новой идеи было предложение применить для шифрования односторонние функции, известные математикам еще со времен фараонов. Они обладают следующим свойством (сосредоточьтесь!): при заданном значении x относительно просто вычислить значение y=f(x), однако нет простого пути для вычисления значения x из известного у, даже если сама функция известна. Но если известен некий «потайной ход», то отыскание х не вызывает затруднений.

 

В схеме шифрования с открытым ключом применяется не один ключ, а пара: открытый (public key), используемый в процессе шифрования, и закрытый (private key), применяемый для дешифрации. Конечно, это не случайная пара случайных чисел, а пара, определенным образом взаимосвязанная. Ваш открытый ключ известен всему миру, а частный хранится в тайне. Любой, даже тот, о ком вы никогда и не слышали, может зашифровать предназначенные вам данные, воспользовавшись копией вашего открытого ключа. А вот прочитать их сможете только вы, поскольку задача выделения частного ключа из открытого нерешаема по определению.

 

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

 

Поэтому чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два важных и очевидных требования. Во-первых, преобразование исходного текста должно быть необратимым и исключать возможность его восстановления на основе открытого ключа. И, во-вторых, невозможным на современном техническом уровне должно быть также и определение закрытого ключа на основе открытого.

 

Все системы, предлагаемые сегодня, опираются на один из следующих типов необратимых преобразований:

-  разложение больших чисел на простые множители;

-  вычисление логарифма в конечном поле;

-  вычисление корней алгебраических уравнений.

 

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

 

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

 

Современная история

 

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

 

1.  Идентификация пользователя. Мы пользуемся современными средствами связи, позволяющими отправителю оставаться неизвестным, но хотим быть уверенными в том, что тот, с кем мы общаемся, — действительно тот, за кого себя выдает. Для этого используется протокол идентификации. Основы криптографии. Шифрование с помощью ключаТаковых существует великое множество, и основаны они, в большинстве своем, на принципах RSA или дискретного логарифмирования.

 

2.  Аутентификация документа. Автор удостоверяет документ при помощи цифровой подписи. Операция подписи добавляет к сообщению несколько бит, которые являются результатом некоей операции над самим документом и сведениями об авторе, биты эти, как правило, хэшируются с использованием одного из известных алгоритмов MD5 или SHA. Более того, любой, кто имеет доступ к документу, должен иметь и возможность проверить, действительно ли подпись под ним поставлена автором. Для этого используются схемы подписи, наиболее известной среди которых является Elgamal, — также построенная на решении задачи дискретного логарифмирования.

 

3.  И, кроме того, как и шифрование с секретным ключом, шифрование с открытым ключом является криптосистемой, гарантирующей конфиденциальность информации.

 

Известно множество криптосистем с открытым ключом — это Elgamal (названная в честь ее изобретателя Тахира Эльгамаля), Diffie-Hellman (названная, правильно, в честь ее создателей), DSA — Digital Signature Algorithm (изобретенный Дэвидом Кравицом).

 

Основы криптографии. Шифрование с помощью ключаНаилучший пример криптосистемы с открытым ключом (и, несомненно, простейший) появился двумя годами позже, в 1978 г. Тогда извилистые коридоры зеркального лабиринта, в которых плелась паутина чистой математики и черной магии криптографического научного искусства, делают новый поворот. Его фирменный знак — статья Роналда Л. Ривеста, Ади Шамира и Леонарда Адлемана об изобретенной ими системе шифрования RSA. Статья подробно описывала алгоритм шифрования, основанный на математической сложности разложения числа на целочисленные множители. Частный ключ создается из тройки чисел (p, q, d), где p и q — простые числа примерно одного размера, а d — простое число, связанное с p–1 и q–1. Открытый ключ создается из пары (n, e), где n=pq, а e — находится из выражения ed=1 mod(p–1)(q–1).

 

Предположим, вам требуется передать некое сообщение, зашифрованное при помощи открытого ключа вашего адресата (n, e). Вы сначала преобразуете исходное сообщение в целое чиcло m, меньшее чем n, затем выполняете вычисления c=me mod n и передаете результат с адресату. Тот, имея частный ключ (p, q, d), выполняет новые вычисления cd mod n=med mod n=m, получив в итоге исходное сообщение.

 

В алгоритме RSA секретной лазейкой является односторонняя функция, которая связывает целое число x<n с величиной xe mod n.

 

Авторы пообещали премию в сто долларов тому, кто первым расшифрует RSA-шифрованную фразу

 

«96861375462206147714092225435588290575999112457431987469512093081629 8225145708356931476622883989628013391990551829945157815154».

 

Единственное, что требовалось для этого, — разложить на два сомножителя 129-значное число, приведенное в той же статье.

 

Это было сделано только через 17 лет. Для того чтобы расшифровать фразу The magic words are squeamish ossifrage, команде из 600 человек потребовалось 220 дней работы и Основы криптографии. Шифрование с помощью ключа1600 компьютеров, связанных через интернет. Я подозреваю, что затраты несколько превысили размер премии.

 

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

 

Не менее известны также криптосистемы на основе эллиптических кривых. Эллиптическая кривая — это множество точек (x, y), описываемое уравнением:

 

y2 = x3 + ax + b,

 

а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля.

 

Основы криптографии. Шифрование с помощью ключаЗадачу дискретного логарифма на эллиптической кривой можно описать так: дана точка G на эллиптической кривой порядка r (r — количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y есть х-я степень G.

 

В каждой избушке — свои погремушки

 

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

 

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

 

Когда игры закончились с незначительным перевесом в пользу государств, началась реальная работа. Все складывалось (точнее, перемножалось) отлично. На бумаге. На практике же обнаружились «овраги» на путях обмена открытыми ключами. Вот тут-то и пришел конец радужным надеждам. Возникла чрезвычайно серьезная проблема защиты открытого ключа. Ведь система работает правильно, только если используемый вами открытый ключ действительно принадлежит тому, кому предназначено сообщение. Основы криптографии. Шифрование с помощью ключаЕсли же ключ подделан, то послания ваши будет читать кто-то другой. В задачке спрашивается, как проверить, какой ключ у вас в руках, — настоящий или поддельный? И вот тут-то чистая математика разложения на сомножители снова запутывается в абсолютно «ненаучной» проблеме, причем не менее сложной, чем в симметричной криптографии. Тамошняя внекриптографическая проблема — нахождение сверхнадежного канала для обмена ключами. Здесь — не менее заковыристая проблема достоверности ключа.

 

Защита информации как защита от подделки

 

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

 

Итак, каков сценарий процесса?

 

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

 

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

 

Единственный способ избежать подобных ситуаций — получать открытые ключи непосредственно от их обладателей, то есть мы возвращаемся к проблеме защищенного канала передачи ключа.

 

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

 

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

 

Новые решения — на стыке старых

 

В ходе единства и борьбы двух направлений криптографической науки родилась новая гибридная криптосистема с нескромным названием Pretty Good Privacy (PGP), объединившая в себе лучшие стороны как традиционной криптографии, так и шифрования открытым ключом. В алгоритме PGP удобство шифрования открытым ключом дополняется скоростью симметричных алгоритмов, которые работают почти в тысячу раз быстрее асимметричных. Шифрование открытым ключом, в свою очередь, снимает проблемы скрытой передачи ключей. Происходит некая синергетика — используемые совместно алгоритмы взаимно дополняются и улучшаются без какого бы то ни было ущерба безопасности.

 

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

 

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

 

Дешифровка выполняется строго в обратном порядке. Сначала PGP-программа получателя «вынимает» из сообщения данные о ключе сеанса, дешифрует его, используя закрытый ключ, и только потом дешифрует само сообщение.

 

Еще раз о ключах

 

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

 

Основы криптографии. Шифрование с помощью ключаОднако размер асимметричного открытого ключа и размер тайного ключа в симметричной криптографии абсолютно несопоставимы. Так, считается, например, что 80-битный секретный ключ эквивалентен по стойкости 1024-битному открытому ключу. Стойкость 128-битного секретного ключа равна стойкости 3000-битного открытого. Несомненно, чем ключ больше, тем безопасность выше, но вряд ли можно сравнивать абсолютно различные алгоритмы, применяемые в каждом из типов криптографии. Все равно, что спрашивать — кто сильнее, кит или слон.

 

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

 

Чем больше ключ, тем больше времени потребуется на его вскрытие. Если вы хотите спрятать государственный секрет на десятилетия, вы, вероятно, остановите свой выбор на очень длинном ключе. Но не обольщайтесь. Кто знает, сколько потребуется времени завтрашним компьютерам, чтобы вскрыть ваш ключ? Не забывайте, что было время, когда чрезвычайно надежным считался 56-битный симметричный ключ. А еще раньше полностью полагались на шифр Цезаря…

 

Цифровой автограф

 

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

 

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

 

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

 

Электронная подпись применяется сегодня гораздо чаще, чем чистое шифрование. Так, например, менеджера интернет-магазина, куда вы только что перевели со своего счета 10 000 долларов, не интересует, что кто-то узнает об этой покупке, но ему надо быть абсолютно уверенным, что он имел дело именно с вами. Равно как и вы желаете доказательств того, что перевели свои денежки в нужное место.

 

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

 

Что дальше?

 

При слове «шифр» многие вспомнят Штирлица или Мату Хари, «пляшущих человечков» Конан Дойла или «Золотого жука» Эдгара По. Но, постойте, достижениями современной криптографии мы пользуемся ежедневно, иногда даже не подозревая об этом. Например, открывая доступ в интернет, программа-навигатор может спросить, нужен ли режим шифрования, и если вы ответите «да», она начнет создавать ключ шифрования. Второй не менее яркий пример — это банковские карточки. Те карточки, что лежат в наших с вами бумажниках, давно уже не магнитные — в них вшит процессор, который выполняет криптографические функции. Основы криптографии. Шифрование с помощью ключаТретий пример — цифровая подпись. Мы пользуемся ее возможностями, зачастую не осознавая, что это такое, и, тем более, не понимая ее математических основ. Но, может, эти основы нам и ни к чему? Достаточно того, что мы признаем исключительное значение ЭЦП всегда, когда речь идет об использовании в бизнесе электронных документов.

 

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

 

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

 

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

 

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

 



<< Предыдущая В начало рубрики Следующая >>



Конкурсы

Реклама