Google+
Журнал Плас Плас Журнал http://www.plusworld.ru/
ул. Кржижановского, д. 29, корп. 5 Москва, 117218 Россия
+7 495 961 1065 http://www.plusworld.ru/upload/templates/logo_plus_ru.png
RSS RSS RSS RSS

"Эллиптические" карточки, или откуда в банках и финансовых компаниях пошла мода на алгебраические числа

(Нет голосов)

23.07.1998 Количество просмотров 833 просмотра

А. Н. Лебедев, Президент ЛАН Крипто

 

Новые принципы оформления документов

Начиная с конца 60-х гг. XX в. международное банковское сообщество все более активно использует в своем обороте электронные документы для оформления сделок, заключения соглашений и, конечно же, для электронного перевода платежных средств - быстрого, надежного, удобного как для банков, так и для клиентов. Эта практика получила настолько широкое распространение, что не нуждается в пространных объяснениях; однако даже современная ситуация является результатом лишь самых первых робких шагов человечества в новую «безбумажную» эру.

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

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

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

·        возможность удостовериться в подлинности содержания и авторстве документа,

·        возможность надежно защитить его при пересылке по каналам связи и при хранении от посторонних глаз, а также

·        возможность предъявить его в качестве наиболее убедительного прямого доказательства при судебном разрешении споров.

Первым шагом на пути практического решения этой проблемы было изобретение так называемой «цифровой» или «электронной» подписи.

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

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

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

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

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

О терминологии

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

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

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

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

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

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

Новый подход к аутентификации электронных документов

Теоретические принципы нового подхода были впервые изложены в 1976 г. в статье действительно молодых тогда ученых из Стэнфордского университета в Калифорнии Уитфилда Диффи и Мартина Хеллмана.

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

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

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

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

Что такое «сложная задача». Один пример: вы можете взять два больших целых числа, например, по 30 десятичных знаков каждое, и легко перемножить их даже без компьютера или калькулятора, а только при помощи карандаша и бумаги, «столбиком». Но если вы дадите своим знакомым только запись результата такого перемножения в виде целого числа из 60 (или 61) десятичных знаков и попросите их найти те два числа, из которых вы его получили, то можете быть уверены, что никто из них этого сделать не сможет. Если, конечно, вы не очень старались выбрать «плохие» для себя исходные два числа.

А если исходные целые числа выбирать достаточно аккуратно, и каждое из них взять состоящим не из 30, а, скажем, из 100 или более десятичных знаков, то можете быть уверены, что восстановить вашу пару чисел – «ваше цифровое перо», исходя только из их произведения, не сможет ни одна спецслужба мира.

Чтобы не быть совсем голословным, приведу здесь несколько более подробных математических выкладок. Сложность решения вычислительной задачи разложения на множители целого числа из 200 цифр самым эффективным среди известных современной науке методов оценивается величиной 10**24, арифметических операций (операций сложения/вычитания и умножения/деления) с большими целыми числами. Сколько же времени необходимо для выполнения такой задачи?

Предположим, что в нашем полном распоряжении имеется 1 миллион (1 000 000 = 10**6) современных суперкомпьютеров, мощность каждого из которых составляет 1 миллиард (1 000 000 000 = 10**9) арифметических операций с большими целыми числами в секунду. Предположим далее, что все эти компьютеры могут быть одновременно пущены в действие и направлены на решение одной задачи по нахождению разложения нужного числа и будут работать без сбоев и перерывов, решая каждый независимо от другого свою часть задачи (это так называемое «полное распараллеливание», чего реально достичь нелегко). Даже в этих предположениях, для решения задачи нам потребуется ждать 10**24 / (10**6)*(10**9) = 10**9 сек., или примерно 33 года (учитывая, что в году 31 536 000 секунд). Подчеркнем, что при этом все суперкомпьютеры сети (а их миллион) должны все время работать непрерывно и с полной нагрузкой.

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

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

Телекомпания CNN распространила 17 июля 1998 г. по своим каналам сообщение, что небольшая, но очень активная американская общественная организация под названием «Центр Электронной Приватности Информации»[1]профинансировала успешно завершенный проект построения специального компьютера для «взламывания» алгоритма шифрования данных DES[2]. По сообщению CNN, построенный на деньги «Центра Электронной Приватности Информации» компьютер состоит из 1728 процессоров (27 плат по 64 процессора на каждой) и способен перебирать и отбраковывать 88 000 000 000 = 8.8*(10**10) = 88 миллиардов вариантов ключа в секунду.

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

Действительно, те, кто заботится о надежной защите своих конфиденциальных или даже просто важных данных, давно уже защищают их при помощи новых надежных алгоритмов с ключами длиной не менее чем 500 бит. И только американцы все еще воюют со своим правительством за право свободно вывозить и использовать за пределами США надежные алгоритмы с ключами более чем 56 бит.

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

8.8*(10**10)*56*3600 = 1.77*(10**16) вариантов ключа,

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

Эти два примера наглядно показывают, что такое практически разрешимые и практически неразрешимые в настоящее время вычислительные задачи.

Арифметика как источник сложных задач

Еще один пример. Если вам сложно производить вычисления с целыми числами из 200 цифр, то можно, воспользовавшись другой математической конструкцией, для получения того же результата, ограничиться целыми числами всего из 150 цифр.

В основе этой конструкции лежит другая сложная вычислительная задача, так называемая задача Дискретного Логарифмирования (для удобства обозначим ее сокращенно ДЛОГ или DLOG). Суть задачи Дискретного Логарифмирования состоит в том, что по заданным целым числам a, x, p можно легко вычислить целое число

B = a**x

то есть возвести число a в степень x, а затем и число

b = a**x mod p

то есть найти остаток от деления нацело числа B на число p, но по заданному целому числу b восстановить исходное число x – “дискретный логарифм числа b по основанию числа a”, даже заранее зная целые числа a, p (состоящие из 150 цифр каждое) не легче, чем найти разложение на множители целого числа из 200 цифр.

Для популярных сейчас персональных компьютеров на основе процессоров Pentium нетрудно написать программу, которая будет легко выполнять такие вычисления даже с целыми числами из 150 десятичных знаков за доли секунды. Но выполнить обратную операцию – восстановить x по числам a, b, состоящим из 150 цифр каждое, - задача не менее трудоемкая, чем задача разложения на множители произвольного целого числа из 200 цифр. А последнее, как мы уже говорили выше, не под силу в настоящее время даже самой мощной дешифровальной службе мира.

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

Из приведенных выше примеров читатель может сам легко заключить, что если у пользователя есть в распоряжении самый обычный персональный компьютер с самым заурядным процессором Pentium, Intel486 или даже Intel386, то вычисление образцов цифровой подписи (или «открытых ключей») по персональным цифровым перьям («секретным ключам») пользователей не представляет большой сложности. Это соответствует возведению в большую степень большого целого числа и вычислению остатка от деления результата нацело на другое целое число. Восстановление же персонального цифрового пера пользователя по образцу его цифровой подписи («открытому ключу») легко может быть сделано практически неразрешимой вычислительной задачей даже для того, кто располагает самыми мощными в настоящее время компьютерами. Для этого достаточно использовать правильно подобранные целые числа из 150 – 200 цифр. Именно на этом парадоксе и построена вся современная «гражданская» индустрия защиты информации.

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

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

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

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

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

Пусть Е обозначает некоторую эллиптическую кривую и a – некоторую точку на этой кривой. Тогда для целого числа x выражение

b = a*x

обозначает точку на кривой Е, полученную в результате x-кратного сложения точки a самой с собой. В этом случае задача, аналогичная задаче Дискретного Логарифмирования для больших целых чисел (т.е., задача нахождения числа x по числам а и b), может быть сформулирована как задача определения кратности точки а, с которой она входит в точку b.

В отличие от задачи Дискретного Логарифмирования для целых чисел, на эллиптических кривых эта задача не имеет сейчас более изощренных методов решения, чем просто разные способы перебора всех возможных вариантов числа x до получения истинного, с записью в памяти результатов промежуточных вычислений. Более того, в силу сложности самой конструкции эллиптических кривых даже такие простые в идейном смысле алгоритмы ее решения трудно оценить с вычислительной точки зрения. Поэтому современные оценки надежности систем цифровой подписи и кодирования данных на основе эллиптических кривых до последнего времени считались большинством аналитиков существенно менее обоснованными, чем аналогичные оценки для задачи разложения на множители или задачи ДЛОГ с большими целыми числами. И только в последние 2-3 года доверие аналитиков к таким конструкциям заметно возросло.

Так или иначе, но по современным оценкам сложности при уровне надежности алгоритмов цифровой подписи на эллиптических кривых, соответствующем 512-битным целым числам, в алгоритмах на основе задачи ДЛОГ, можно ограничиться использованием эллиптической кривой, точки которой записываются парами целых чисел, каждое всего из 160-ти бит. Это позволяет сократить общую длину записи чисел, с которыми производятся вычисления с 512 до 320 бит. А это, в свою очередь, позволяет уменьшить сложность вычислений арифметических операций с такими числами в 1.6 раза для операций типа сложения/вычитания, в 2.5 раза для операций типа умножения/деления и почти в 4 раза для операций типа возведения в степень.

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

Надежность таких алгоритмов пока не возникает серьезных опасений, поскольку с момента их изобретения в 1982 г. оценки сложности определения персональных «цифровых перьев» не изменились. За прошедшие 16 лет активных научных исследований не появилось ни одного нового методаn.



[1]Центр Электронной Приватности Информации (авторский перевод оригинального названия “ElectronicPrivacyInformationCenter), - организация, широко известная своей борьбой с правительством США за свободное распространение криптографических технологий защиты информации.

[2]Алгоритм шифрования DES является первым открыто опубликованным общедоступным национальным стандартом США для шифрования конфиденциальных данных, не содержащих государственных секретов. Был разработан в США в 1973 году, принят в качестве национального стандарта в 1977 г. Стойкость алгоритма DESравна сложности перебора не более чем 32 000 000 000 000 000 = 3.2*(10**16) возможных вариантов ключа шифрования, состоящего из 56 бит.


Комментарии (0):

Добавлять комментарии могут только зарегистрированные Пользователи


Читайте в этом номере:
обновить

а вы знаете, что...

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