 |
Год 1917 — революция в шифровании
|
|
|
|
В то время для передачи сообщений все шире и шире использовались телетайпы. Поэтому требовались методы, позволяющие шифровать текст не до того, как он попадает к телеграфисту, а непосредственно в момент передачи, и, соответственно, расшифровывать в момент приема. Очень хотелось поручить это дело машине. Как оказалось, колебания тока в линии передачи можно легко записать с помощью осциллографа и затем преобразовать в буквы передаваемого сообщения. Изменив соединения проводов телетайпа, телеграфисты получали сообщение, зашифрованное методом одноалфавитной замены.
Все понимали, что такая защита чересчур слаба, но, не сумев придумать ничего другого, пользовались ей до тех самых пор, пока Вернам не предложил использовать для кодирования сообщений особенности телетайпного кода, в котором кодируемый знак выражается в виде пяти элементов. 
Каждый из этих элементов символизирует наличие («плюс») или отсутствие («минус») электрического тока в линии связи. Например, букве «А» соответствует комбинация «+ – – – –». Подготовленное к отправке сообщение набивается на перфоленте: отверстие соответствует «плюсу» кода, его отсутствие — «минусу». В процессе передачи металлические щупы телетайпа проходят через отверстия, замыкая цепь, и посылают импульсы тока («+»). Там, где отверстия нет, и бумага не позволяет щупам замкнуть цепь, импульс не передается («–»).
Для шифрования Вернам предложил заранее готовить «гамму» — перфоленту со случайными знаками — и затем электромеханически складывать ее импульсы с импульсами знаков открытого текста. Полученная сумма представляла собой шифртекст. На приемном конце импульсы, полученные по каналу связи, складывались с импульсами той же самой «гаммы», в результате чего восстанавливались исходные импульсы сообщения. А если сообщение перехватывалось, то без «гаммы» расшифровать его было невозможно, противник видел только ничего не значащую последовательность «плюсов» и «минусов».
|
|
|
Дальнейшее усовершенствование метода, предложенного Вернамом, принадлежит будущему начальнику связи войск США Джозефу Моборну, объединившему хаотичность «гаммы», на которую опирался Вернам в своей системе «автоматического шифрования», с используемым в то время в войсках правилом «одноразового шифрблокнота». Идея Моборна заключалась в том, что каждая случайная «гамма» должна использоваться один, и только один раз. 
При этом для шифрования каждого знака всех текстов, которые уже переданы или будут переданы в обозримом будущем, должен применяться абсолютно новый и не поддающийся предсказанию знак «гаммы».
В период между двумя мировыми войнами в большинстве стран появляются электромеханические шифраторы. Они были двух типов. Первый — устройство, состоящее из коммутационных дисков и механизма изменения их угловых положений. По обеим сторонам коммутационного диска размещены контакты, соответствующие алфавитам открытого и шифрованного текста. Контакты эти соединяются между собой согласно некоторому правилу подстановки, называемому коммутацией диска. Эта коммутация определяет замену букв в начальном угловом положении. При изменении углового положения диска изменяется и правило подстановки. Таким образом, ключ шифрования содержит пару неизвестных: схему соединения контактов и начальное угловое положение. Если после шифрования каждой буквы менять угловое положение диска — получим многоалфавитное шифрование. Еще более сложное устройство получим, соединив последовательно несколько дисков, угловые положения которых меняются с различной скоростью.
|
|
|
Широко известная шифрмашина «Энигма», которой были оснащены германские войска времен Второй мировой войны, является типичным примером устройства на коммутационных дисках. Конструктивно «Энигма» походила на обычную пишущую машинку, только нажатие клавиши приводило не к удару молоточка по бумаге, а создавало электрический импульс, поступавший в схему криптопреобразования. Американская шифрмашина М-209 — типичный пример второго типа шифратора, — шифратора на цевочных дисках.
Интересно, что Советский Союз производил шифрмашины обоих названных типов.
Таким образом, перед Второй мировой войной все ведущие страны имели на вооружении электромеханические шифрсистемы, обладающие высокой скоростью обработки информации и высокой стойкостью. Считалось, что применяемые системы недешифруемы, и криптоанализу больше делать абсолютно нечего. Как часто бывает, это мнение было впоследствии опровергнуто, и дешифровщики были непосредственными участниками военных действий.
Прежде чем перейти ко второй части и к рассказу о современных системах шифрования, упомянем теоретическое открытие, во многом предопределившее дальнейший путь развития криптографии. Речь идет о двух работах, написанных в начале сороковых годов прошлого века и существенно расширивших научные основы криптографии, — статье американца Клода Шеннона «Теория связи в секретных системах» и статье советского ученого В. А. Котельникова «Основные положения автоматической шифровки». Эти статьи полностью уничтожили радужные надежды и предубеждения, развеяли мифы и разрушили вековые легенды, сняли с криптографии покров тайны.
Шеннон доказал, что предложенный Вернамом в 1917 году метод шифрования с применением случайной комбинации знаков («гаммы»), объединенный с одноразовым шифрблокнотом, — единственная абсолютно стойкая система шифрования, при условии, что длина ключа равняется длине самого сообщения.
Подавляющее большинство систем шифрования являются лишь разумно стойкими, поскольку криптоаналитик, имея в своем распоряжении большой объем шифрованного текста и достаточно времени, может найти пути расшифровки сообщений. Одноразовый же шифрблокнот — абсолютно стойкий как в теории, так и на практике. Каким бы длинным ни был перехваченный текст, сколько бы времени ни отводилось на его исследование, криптоаналитик никогда не сможет вскрыть одноразовый шифрблокнот, использованный для получения этого шифртекста. И вот почему.
|
|
|
У криптоаналитика нет отправной точки для исследований, ведь «гамма» не содержит повторений, не используется дважды, не является связным текстом и не имеет структурных закономерностей. Криптоанализ бессилен. Остается только метод прямого перебора всех возможных ключей, который, по идее, в конечном счете обязательно приведет к открытому тексту. Однако успех, приобретенный этим путем, иллюзорен. И дело не только в том, что затраты времени колоссальны. Тотальное опробование действительно позволяет получить исходный текст. Но оно также даст и еще множество связных текстов той же длины. Кто возьмется определить, какой из них является истинным?
Говорят, что такой метод шифрования использовался не только в тайных операциях советской разведки и ЦРУ, но и при проведении правительственных переговоров по «горячей линии» Москва — Вашингтон. Однако в обмен на абсолютную стойкость метод этот требует чересчур больших вычислений, что не всегда оправданно. Иногда достаточно обеспечить криптостойкость на некоторое время (помните доктрину Россиньоля?). Как говорил Остап Бендер: «Мне не нужна вечная игла для примуса, я не собираюсь жить вечно».
Стойкость криптосистемы сегодня оценивается объемами вычислений, которые требуются для ее вскрытия. Считается, что ключ шифрования достаточно стоек, если все известные способы его отыскать настолько сложны, что требуют больше времени, чем простой перебор всех возможных ключей.
Все мы сегодня, иногда даже не подозревая об этом, применяем средства защиты информации. Мы шифруем сообщения электронной почты, пользуемся интеллектуальными банковскими карточками, ведем разговоры по закрытым каналам связи и т. д. Всякий раз возникает вопрос — надежна ли защита? Но и этот элементарный вопрос не так просто правильно сформулировать. Кто наш противник? Каковы его возможности? Какие он преследует цели? Как измерить стойкость защиты? Чего мы хотим от нее — скрыть факт переписки? зашифровать содержание? засекретить имена адресатов? не позволить противнику исказить информацию?
|
|
|
Над этими и многими другими проблемами работает современная криптография, новейшая история которой началась в 1978 г. с суммы в 100 долларов и числа
«968613754622061477140922254355882905759991124574319874695120930816298225145708 356931476622883989628013391990551829945157815154».
Ключи от тайны
| Основы криптографии. Шифрование с помощью ключа |
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.
|
|
|
