Математические основы криптологии и криптографические методы и средс

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

2. ECDSA

ECDSA-это вариант алгоритма DSA {Digital Signature Algo­ rithm) на эллиптических кривых. Перед тем как рассмотреть ECDSA, разберем оригинальный алгоритм DSA, так как это может послужить хорошей иллюстрацией.

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

♦(р -1) делится на q\

♦задача нахождения дискретного логарифма в подгруппе Fp

порядка q нерешаема.

Размерность р задает криптостойкость системы. Ранее рекомен­ довалась длина в 1024 бита. В данный момент для систем, которые должны быть стойкими до 2010 (2030) года, рекомендуется длина в 2048 (3072) бита. Также, для того чтобы избежать birthday-атак на хэш-функцию, рекомендуется выбирать т >160 .

Далее необходимо вычислить генератор g для подгруппы по­ рядка q в . Для этого генерируются случайные элементы h е F'*

и вычисляется g =h^p~])/ct(modр ) , пока не получится значение g, от­ личное от единицы. Вероятность того, что это не выйдет с первым

выбранным А, равняется —, поэтому найти g несложно.

Ч

Обычно в DSA в качестве хэш-функции используют SHA-1, но с появлением SHA-256, SHA-384 и SHA-512 стало возможным вы­ бирать большие значения т.

Эти четыре элемента {H,p,q,g) называют набором параметров системы, так как часто они используются большим количеством пользователей.

DSA использует функцию

f \ FP ^ F<

* [xi-> x(mod^) ’

где X B F* рассматривается как целое при выполнении приведения

(редукции) по модулю q. Эта функция часто называется функцией преобразования. В качестве пары открытый/закрытый ключ исполь­ зуется (yjc), где у = g*(mod/?) .

Подпись сообщения с помощью DSA: Input: сообщение т, закрытый ключ х. Output: подпись (r,s) к сообщению т.

1.Выбирается к еЛ{l,...,<7 - l}.

2.t <—g*(mod p).

3.r <— f{t).

4.If r = 0 then goto Step 1

5.e <—H(m).

6.s <—(e + xr)/k(modq).

7.If s = 0 then goto Step 1.

8.Return (r,s).

Проверка подписи:

Input: сообщение m, открытый ключ у, подпись (r,s). Output: Reject/Accept.

1. Reject if r,s «£ {l,...,^-l}.

2 . e <—H(m).

3. M, <—e/ s(modq),u2 <- r/s(modq).

4./ <—g"' y u' (modp).

5.Accept if and only if r —J{t).

Для ECDSA параметрами являются (Я, К, Е, q, G), где Я -хэш - функция, Е - эллиптическая кривая над конечным полем К, G - точка на кривой простого порядка q. Вместе с параметрами системы часто

хранят целое число А, называемое адъюнктом, такое, что UE(K) = hq.

Обычно выбирают кривую такую, чтобы h < 4.

Пара открытый/закрытый ключ задается (К,х), где Y = [x]G, а роль функции/ выполняет

E -+ F

Р I—> xfTXmod q),

где х(Р) указывает на х-координату точки Р, при выполнении приве­ дения (редукции) по модулю q оно считается целым.

Подпись сообщения с помощью ECDSA: Input: сообщение т, закрытый ключ х. Output: подпись (г,5 ) сообщения т.

1.Выбирается k e R

2.T<-[k]G.

3 . r ^ f ( T ) .

4.If r = 0 then goto Step I.

5.e<-H(m).

6.s<r-(e +xr)/k(modq).

7.If s = 0 then goto Step 1.

8.Return (r,s).

Проверка подписи:

Input: сообщение m, открытый ключ Y, подпись (r,s). Output: Reject/Accept.

1.Reject if r,s

2.e <r- H{m).

3.щ <—e/.s(mod<7), u2 < -r/s(m odq).

4.T <—[M,]G + [M2 ]X

5.Accept if and only if r -J{T)

Ксожалению, в процессе адаптации стандарта ANSI Х.9-62 ECDSA не были полностью учтены все особенности операций с эл­ липтическими кривыми, что и дало возможность имитировать под­

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

В матаппарате ECDSA существует серьезная ошибка, позво­ ляющая выбрать такое значение секретного ключа, чтобы получить одинаковые подписи для разных документов. Описанная ошибка от­ личается от уже известных и сходных по последствиям тем, что не требует участия злоумышленника в выборе параметров подписи. Та­ ким образом, она доступна практически любому пользователю ЭЦП, а не только самим разработчиками программ ЭЦП. Эта ошибка вы­ звана равенством х-координат противоположных точек эллиптиче­ ской кривой. Исправить эту ошибку несложно. Нужно всего лишь обеспечить доказательную генерацию секретного ключа х. Например, выбирается случайное значение SeedO. Личный ключ вычисляем как х: = SHA - l(SeedO). Сохраняются оба значения. В этой схеме же­ лаемое значение х выбрать не получится. Время генерации ключа увеличится, но это не критично в большинстве случаев. Еще один вариант: передавать в качестве подписи не (у,г), a (s,R), где R - [£]G.

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

торый представляет собой случайную последовательность из нулей и единиц той же длины, что и само послание. Шифрование и дешиф­ рование сводятся к побитовому сложению ключа и текста. Однако надо предварительно снабдить обе стороны комплектом идентичных ключей такого вида, а это очень непросто сделать. Подобные трудно­ сти привели к тому, что с развитием компьютерных сетей крипто­ графия с секретным ключом перестала справляться со своими обя­ занностями. Предположим, что пользователь хочет шифровать свою переписку. Значит, сначала нужно договориться о секретном ключе. Как это сделать? Пересылать ключ в открытом виде, мягко говоря, не лучшее решение. Сперва его надо шифровать. Но как? Получается замкнутый круг. Криптография с открытым ключом разрывает этот круг. В криптосистеме уже не один ключ, а два - открытый и секрет­ ный. Преимущество в том, что пользователю не нужно ни с кем де­ литься своим ключом. Только он один должен иметь возможность дешифровать сообщение от другого пользователя, а чтобы шифро­ вать его, секретный ключ не нужен. Криптография с открытым клю­ чом уязвима по отношению к некоторым очевидным атакам. Алго­ ритм, который гарантированно взломает любую такую криптосисте­ му: перебирать всевозможные сообщения, шифруя их при помощи открытого ключа, до тех пор пока результат не совпадет с шифром, который мы хотим разгадать. Однако никто никогда не переберет даже все возможные комбинации ста битов входа; что уж говорить о ключах длиной 512 или 1024 бит. Главное-чтобы у злоумышлен­ ника не было возможности сделать что-нибудь поумнее. Это и есть главная задача построения стойких криптосистем.

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

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

2.3.7. Вопросы и задачи для самоконтроля

1. Укажите основную область применения ассиметричного шифрования.

2.Назовите основные отличия симметричных и ассиметричных систем шифрования.

3.Определите шифрование и дешифрование в системе RSA при p = 3;q= U ;d = l ;M=5.

4.Определите шифрование и дешифрование в системе RSA при

р= 5; q = 11; е = 3; М - 9.

5.Определите шифрование и дешифрование в системе RSA при p - 7 ; q = 11;е= 17;Л/=8.

6.Определите шифрование и дешифрование в системе RSA при

p = U ; q = U ; e = 11;Л/=7.

7.Определите шифрование и дешифрование в системе RSA при р= 17;$ = 31;е = 7;Л/=2.

8.В криптосистеме с открытым ключом, использующей RSA,

вы перехватили шифрованный текст С = 10, пересылаемый пользова­ телю, открытым ключом которого является е = 5, п = 35. Что в дан­ ном случае является открытым текстом?

9. В использующей RSA системе открытым ключом некоторого пользователя является е = 31, л = 3599. Что будет личным ключом этого пользователя?

10.Предложите вариант слепой подписи с использованием сис­ темы ЭЦП Эль-Гамаля.

11.Опишите систему вероятностного шифрования.

12.Дайте определение эллиптической кривой над полем

13.Опишите алгоритмы подписи сообщения и проверки подпи­ си сообщения с помощью ECDSA.

2.4. КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ

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

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

У протоколов есть также и другие отличительные черты:

♦каждый участник протокола должен быть заранее оповещен

ошагах, которые ему предстоит предпринять;

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

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

ине допускали возможности их неправильного понимания;

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

соответствующее действие.

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

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

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

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

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

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

Чтобы описание протоколов было более наглядным, их участ­ ники будут носить имена, которые однозначно определяют роли, им уготованные (см. таблицу). Алиса и Боб принимают участие во всех двухсторонних протоколах. Как правило, начинает выполнение ша­ гов, предусмотренных протоколом, Алиса, а ответные действия предпринимает Боб. Если протокол является трехили четырехсто­ ронним, исполнение соответствующих ролей берут на себя Влади­ мир и Георгий. Об остальных персонажах подробнее будет рассказа­ но несколько позже.

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

Во многих криптографических системах возникает задача одной стороне A (iдоказывающая сторона) доказать знание секрета другой стороне В {проверяющая сторона), причем сделать это необходимо таким образом, чтобы сторона В после этого не знала сам секрет, т.е. А демонстрирует знание какой-то информации без разглашения ка­ кой-либо части этой информации. Впервые понятие протоколов с нулевым разглашением было введено в работе Гольдвассера, Микали и Ракоффа в 1985 году. Такие протоколы позволяют решить проблемы, которыми обладают все методы авторизации по паролю:

1)необходимость хранить пароль на сервере;

2)простота отслеживания пароля третьей стороной, подслуши­ вающей процесс авторизации.

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

Итак, протоколом доказательства с нулевым разглашением

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

Полнота: доказывающий всегда сможет доказать знание секре­ та, если он им действительно обладает.

Корректность: доказывающий не может продемонстрировать знание секрета, если он в действительности не владеет таким знанием.

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

Необходимо заметить, что многие протоколы, призванные обес­ печивать аутентификацию пользователя, проверяя знание им пароля (или секретного ключа в системах с открытым ключом), не передавая

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

лительно нулевым разглашением.

2.4.1. Доказательства с нулевым разглашением

Предположим, что Алиса знает доказательство некоторой тео­ ремы и желает убедить Боба в том, что теорема верна. Конечно, Али­ са может просто передать доказательство Бобу на проверку. Но тогда впоследствии Боб сможет сам, без помощи Алисы, доказывать треть­