Ростовцев - Подпись вслепую на элептической кривой для электронных денег
Предлагаются протоколы подписи вслепую на эллиптической кривой над конечным полем, основанные на протоколах Эль-Гамаля, Шнорра, RSA. Протоколы используют существование категорного морфизма для схем подписи Эль-Гамаля и Шнорра и гомоморфизма групп для схемы подписи RSA.
Проведен оценочный анализ безопасности протоколов с учетом специфики эллиптических кривых.
Введение
Подпись вслепую (blind signature) используется в протоколах электронных платежей, основанных на использовании электронной монеты (electronic coin) информации, не имеющей трудно подделываемого физического воплощения в отличие от обычных денег [1, 2]. Подпись вслепую выполняется банком для уникального номера монеты, известного только ее владельцу.
Таким образом, протокол подписи вслепую должен обеспечивать возможность подписи для сообщения, текст которого не известен подписывающему.
Практически, если стоимость монеты не фиксирована, подпись вслепую выглядит следующим образом.
1. Пользователь генерирует n случайных номеров монеты mi, содержащих ее денежное выражение, накладывает на них случайную маску аі, вычисляя функцию F(mi, аг), и посылает в банк. Функция должна быть такой, что по данному значению трудно подобрать пару аргументов (mi, ai) и трудно вычислить коллизию, т. е. найти две пары аргументов, дающих одно значение функции.
2. Банк выбирает наугад n - 1 замаскированных монет и просит раскрыть их аргументы.
3. Пользователь раскрывает значения (mi, ai) для каждой из n - 1 выбранных монет.
4. Банк убеждается, что все они имеют одинаковое денежное значение, например, 100 рублей. Если число n достаточно велико, то банк может быть убежден с достаточной вероятностью, что и оставшаяся монета тоже имеет достоинство в 1 00 рублей.
5. Банк генерирует подпись s для оставшейся нераскрытой монеты и отправляет пользователю.
6. Пользователь проверяет, что замаскированная монета подписана банком правильно. Затем он снимает с монеты маску, вычисляя функцию G(s, ai) так, что подпись остается верной и для открытого номера монеты.
Проблемы информационной безопасности. Компьютерные системы, СПб., 2000. 1. С. 40-45
В случае монет фиксированной стоимости первые четыре этапа не нужны. Отличие подписи вслепую от обычной цифровой подписи состоит в возможности вычисления маски и ее последующего снятия так, что подпись остается верной.
Кроме того, наложение и снятие маски должно выполняться без знания ключа подписи. Снятие маски должно исключать возможность изменения сообщения.
Таким образом, необходима вычислимость функций F и G в одну сторону.
Таким образом, для подписи вслепую требуется наличие вычислимых функций Fi, Gi таких, что для операции подписи S оказывается справедливым выражение GiSFi(m) = S(m) или GiSFi = S. Это свойство можно интерпретировать как существование вычислимого гомоморфизма схемы подписи, не требующего знания ключа. Известно [3], что популярные протоколы подписи (RSA, Эль-Гамаля), не использующие хэш-функцию, обладают гомоморфизмами.
Эти гомоморфизмы являются кате-горными морфизмами. Здесь объектами категории являются пары сообщение/подпись, выдерживающие проверку.
Морфизмами категории являются вычислимые отображения одной пары в другую.
Существование вычислимых гомоморфизмов позволяет на основе одной правильной пары сообщение/подпись создавать множество других формально правильных пар для (возможно, бессмысленных) сообщений. Однако, если тексты лишены избыточности, то все сообщения являются осмысленными.
Подпись вслепую использует такие гомоморфизмы во благо.
На безопасность протоколов вслепую влияет то обстоятельство, что в создании подписи участвуют две стороны, которые не могут абсолютно доверять друг другу. В частности, пользователь может предлагать такие сообщения, которые позволят вскрыть ключ (атака на основе подобранных сообщений и адаптивно подобранных сообщений).
С другой стороны, банк может быть заинтересован в раскрытии замаскированного сообщения пользователя.
Известны протоколы подписи вслепую на основе группы вычислимого и трудно вычислимого порядка [1, 2]. Эллиптические кривые позволяют реализовать подпись для обоих вариантов групп.
Эллиптическая кривая E(Fq) над конечным полем Fq, q = pm, характеристики p 3 представляет собой множество решений уравнения
у2 = .х3 + Ax + B,
дополненное точкой "бесконечность". При этом кривая не должна иметь особых точек, т. е. удовлетворять условию 4A3 + 27B2 Ф 0. Точки кривой образуют абелеву группу по сложению.
Закон сложения точек описан во многих книгах, например в [3]. Для данного уравнения кривой над полем Fq число точек может быть вычислено алгоритмом Чуфа с полиномиальной сложностью.
Повторное использование монеты исключается тем, что при погашении банк запоминает персональный номер монеты. Однако защита от повторного использования предполагает также распознавание виновника повторного использования. В этом случае номер монеты должен содержать разовый открытый ключ подписи пользователя. Протокол покупки должен включать в себя процедуру доказательства того, что покупатель знает секретный ключ, парный к открытому ключу в номере монеты.
В этом случае при погашении монеты продавец предъявляет в банк запись протокола покупки, включая указанное доказательство. Если доказательство повторное, то обманывает продавец, в противном случае обманывает покупатель.
Группа вычислимого порядка
В основу протокола положена задача логарифмирования в группе точек эллиптической кривой: для данных точек P, Q эллиптической кривой найти показатель l такой, что P = IQ. Очевидно, что для этого точки должны лежать в одной циклической группе. Если порядок группы точек свободен от квадратов, то группа является циклической. Для того, чтобы задача логарифмирования на кривой была сложной, необходимо, чтобы порядок группы был простым или имел большой простой делитель р'.
Кроме того, требуется, чтобы р Ф р' и чтобы число р' не делило бы ни один из порядков мультипликативных групп для нескольких последовательных расширений поля F9 степени не более 20. Тогда сложность логарифмирования имеет оценку O(yfp') (единица измерения сложность сложения точек на эллиптической кривой).
Подпись вслепую на основе протокола Эль-Гамаля
Этот протокол требует диалога, который позволяет придать гомоморфизму подписи требуемые свойства. Открытым ключом банка является уравнение эллиптической кривой, образующая точка Q, точка P, простой порядок группы р' . Оба участника протокола умеют вычислять хэш-функцию h.
Секретным ключом банка является показатель l такой, что P = IQ. Подпись вырабатывается для сообщения т, 0 т р'.
Протокол Эль-Гамаля для обычной подписи на эллиптической кривой заключается в следующем. Подписывающий вырабатывает случайный показатель к, вычисляет точку R = kQ и решает относительно s сравнение по модулю порядка группы т = lh(R) + ks.
Подписью является пара (R, s). Для проверки подписи следует проверить равенство mQ = h(R)P + sR.
Тогда, используя гомоморфизм схемы подписи, можно сконструировать другое правильно подписанное сообщение следующим образом.
1. Выбрать произвольный показатель а, положить к = ак (поскольку к неизвестно, то и к' тоже неизвестно). Этому показателю будет соответствовать точка R = akQ = aR.
2. Вычислить показатель в = h(R')h(R)~l по модулю порядка группы.
3. Вычислить новое сообщение и подпись W = вт, S = a-1ps.
Здесь существует односторонняя вычислимость коэффициента P из показателя а и, следовательно, односторонняя вычислимость нового сообщения т' из сообщения т. Это можно рассматривать как маску, накладываемую на сообщение. Однако маска накладывается банком, тогда как для подписи вслепую требуется, чтобы маска накладывалась пользователем.
Для получения возможности подписи вслепую изменим протокол Эль-Гамаля следующим образом.
1. Банк выбирает случайный показатель к, 0 к р, вычисляет точку
R = kQ, проверяет, что h(R) Ф 0, и посылает точку R пользователю. Если h( R) = 0, то заменяется случайный показатель.
2. Пользователь проверяет, что точка R лежит на кривой, выбирает случайный показатель а, 0 а р', вычисляет точку R = aR , проверяет, что h(R) Ф 0 (в противном случае нужно повторить п. 2), вычисляет коэффициент P = Щ (mod р), вычисляет замаскированное сообщение т = ав W(mod р) для открытого сообщения т и посылает т банку. Если точка R не лежит на кривой, то это может быть расценено как попытка банка узнать некоторую информацию о содержании сообщения т.
3. Банк проверяет, что т Ф 0, вычисляет подпись
s = l ¦ h(R) + к ¦ т(modр)
для сообщения под маской и посылает ее пользователю. Если W = 0, то создание подписи немедленно ведет к раскрытию ключа, в этом случае протокол прерывается.
4. Пользователь проверяет выполнение равенства sQ = h(R)P + WR для сообщения под маской. Если равенство выполняется, то подпись верна. Затем пользователь снимает маску, вычисляя подпись для исходного сообщения: s = sв (modр).
Подписанное сообщение, как и в оригинальном протоколе Эль-Гамаля, представляет собой тройку (т, R, s).
Проверка подписи проводится следующим образом.
1. Для точки R вычисляется хэш-функция. Если h(R) = 0 или т = 0, то подпись считается недействительной.
2. Если h(R) Ф 0, т Ф 0, то проверяется выполнение равенства sQ = h(R)P + wR. Если равенство выполняется, то подпись верна.
Покажем действие протокола на примере одного из n подготовленных пользователем сообщений. Для подписи вслепую сообщения т, 0 т p , пользователь и банк выполняют п. 1 и 2 протокола. Затем банк просит раскрыть содержание сообщения под маской т или подписывает это сообщение. В первом случае пользователь предъявляет показатель а. Банк проверяет выполнение условия т Ф 0, и если оно выполняется, то вычисляет точку aR, вычисляет коэффициент в, вычисляет значение т. Если т = 0, то пользователь нарушает протокол и пытается раскрыть ключ подписи банка.
Во втором случае выполняются п. 3, 4 протокола.
Поскольку отечественный стандарт подписи ГОСТ Р34.10-94 построен на основе протокола Эль-Гамаля, подпись вслепую очевидным образом может быть адаптирована и к стандарту подписи.
Рассмотрим кратко безопасность этого протокола. В этом протоколе может быть несколько направлений атак. Во-первых, это раскрытие ключа подписи. Во-вторых, подделка подписи без раскрытия ключа, например, подменой сообщения.
В-третьих, это раскрытие подлинного текста сообщения (такая атака может быть предпринята со стороны банка).
В основу безопасности протокола положена задача логарифмирования в группе точек кривой. Для раскрытия ключа подписи банка достаточно найти логарифм l. Однако могут быть предприняты и другие варианты атаки. Например, использование банком дважды одного и того же показателя к или использование хоть однажды предсказуемого показателя к позволяет раскрыть ключ подписи решением линейных сравнений.
При этом введение в состав к неповторяющегося порядкового номера или времени приводит к уменьшению допустимого количества подписей на одном ключе. Таким образом, к генератору случайного числа предъявляются требования столь же жесткие, как и к генератору ключей.
Если h( R) = 0, то подпись не зависит от ключа l. В этом случае пользователю достаточно было бы найти точку, которая дает нулевое значение хэш-функции.
Подделка подписи без знания ключа, в отличие от протокола, основанного на логарифмировании в конечном поле, представляется не менее сложной, чем логарифмирование в группе точек эллиптической кривой при условии, что ключ выбран правильно. Неправильный выбор ключа (например, использование не поля из q элементов, а кольца с делителями нуля из q элементов, использование группы составного порядка p и т. п.) может быть легко выявлен с помощью известных тестов проверки на простоту. Варианты нарушения протокола, связанные с тем, что точка R может не лежать на кривой, выявляются в ходе протокола. Возможны атаки, связанные с неправильным выбором точки R, например, так, что она не лежит в группе (Q).
Если число точек на кривой равно N = p't, то для исключения такой атаки следует проверить, что tR Ф Р^ и tR Ф Р^.
Изменение значения подписанного сообщения под маской может быть предпринято пользователем на основе указанного гомоморфизма подписи. Этот недостаток неустраним, так как наличие гомоморфизма основа подписи вслепую.
Поэтому индивидуальный номер монеты должен содержать достаточно большой избыточный отрезок, априорно известный магазину и банку. Если сложность подмены положить равной сложности раскрытия ключа, то длина избыточного отрезка должна быть
Избыточность может быть введена, например, заменой со
равна
lg2 p
общения m на конкатенацию m\\g(m) с соответствующим сокращением длины m для некоторой хэш-функции g, стойкой в части обращения и в части вычисления коллизий.
Подпись вслепую на основе протокола Шнорра
Открытый ключ подписи содержит уравнение эллиптической кривой E(Fq), образующую точку Q, точку P и порядок группы p . Секретный ключ содержит показатель l такой, что P = IQ.
Для подписи вслепую сообщения m участники протокола действуют следующим образом.
1. Банк генерирует случайное число к, 0 к p, вычисляет точку R = kQ такую, что h(R) Ф 0, и посылает эту точку пользователю.
2. Пользователь генерирует случайное число а, 0 а p, и полагает к = ак (mod p'). Затем он вычисляет точку R = aR , проверяет, что h(R) Ф 0. В противном случае генерируется другое число а. Пользователь вычисляет коэффициент в = h(R) (mod p'), вычисляет сообщение
по маской m = a-1pm(mod p') и посылает это сообщение банку.
3. Банк вычисляет подпись для сообщения под маской:
s = к + lm h( R )(mod p')
и посылает ее пользователю.
4. Пользователь проверяет правильность подписи: если выполняется равенство sQ = R + mh(R)P. Затем он снимает маску с подписи и вычисляет s = as (mod p').
Подписанное сообщение представляет собой тройку (m, s, R).
Для проверки подписи достаточно проверить равенство sQ = R + mh(R)P. При этом должно выполняться неравенство h(R) Ф 0. Если равенство выполняется, то подпись верна.
В основу безопасности этого протокола также положена задача логарифмирования в группе точек кривой. Для раскрытия ключа подписи банка достаточно найти логарифм l. Здесь также использование банком дважды одного и того же показателя к (или использование хоть однажды предсказуемого показателя к) позволяет раскрыть ключ подписи решением системы из двух линейных сравнений.
Подделка подписи без знания ключа требует вычисления точки, координаты которой находятся в требуемом соотношении с ее логарифмом. Эта задача представляется такой же сложной, как логарифмирование.
Для того, чтобы защититься от подмены сообщения, в него следует внести избыточность, как и в протоколе Эль-Гамаля.
Подпись вслепую на основе группы трудно вычислимого порядка
Этот протокол подписи аналогичен известному протоколу подписи вслепую Шаума [2] и основан на том, что функция шифрования RSA является мультипликативной, то есть если sb s2 подписи для сообщений m1, m2, то s1s2 подпись для m1m2. Если S функция, вычисляющая подпись s для сообщения m, и множество подписей совпадает с множеством сообщений, то S является эндоморфизмом группы (Z/nZ) .
Открытый ключ представляет собой эллиптическую кривую E(Z/nZ) над кольцом классов вычетов по модулю где n = pq, и p, q различные простые числа, #E(Z/nZ) = N. Кроме того, открытый ключ содержит показатель е, обратимый по модулю N. Секретный ключ содержит показатель d такой, что ed = 1 (mod N). Сообщение Mпредставлено точкой кривой.
По китайской теореме об остатках кривая E изоморфна прямой сумме E(Z/nZ) = E(Fp) 0 E(Fq), следовательно, число N не может быть простым. Кольцо Z/nZ имеет делители нуля, поэтому точки кривой E(Z/nZ) не образуют группу относительно обычной операции сложения точек. Это обусловлено тем, что каждая точка кривой E(Z/nZ) имеет две составляющих по модулю p и по модулю q. Поэтому, если две точки кривой E(Z/nZ) S и T имеют составляющие Sp, Sq и Tp, Tq, и Sp = Tp, Sq Ф Tq, то по модулю p нужно применять формулы для удвоения, а по модулю q формулы для сложения разных точек.
Поэтому существующие формулы сложения могут давать ошибку. Однако вероятность такого события при
сложении двух точек пренебрежимо мала и имеет порядок O -1-
^ min( p, q)
Порядки групп E(Fp) и E(Fq) должны иметь большие простые делители. Подпись RSA на эллиптической кривой является автоморфизмом группы E(Z/NZ).
Подпись вслепую использует это свойство.
Протокол предусматривает следующие действия.
1. Пользователь генерирует случайную точку кривой R, вычисляет для сообщения M е E(Z/nZ) точку M = M + eR и посылает банку.
2. Банк вычисляет подпись для точки M : S = dM = d(M + eR) = dM + R.
3. Пользователь проверяет правильность подписи (если M = eS, то подпись верна) и снимает маску с подписи, вычисляя S = S - R = dM.
Подписью для точки M является точка S. Проверка подписи выполняется вычислением eS и сравнением с точкой M. В случае равенства подпись верна.
Для снятия маски с сообщения M предъявляется точка R. Безопасность протокола в части раскрытия ключа подписи основана на сложности разложения составного числа n и на сложности нахождения порядка группы N. Поэтому размер задачи в этом случае оказывается в несколько раз больше, чем, например, в протоколе Эль-Гамаля. Следовательно, использование эллиптических кривых в таком протоколе приводит к снижению скорости вычислений в десятки раз по сравнению с протоколом, использующим группу вычислимого порядка.
В силу гомоморфизма схемы подписи теоретически возможна подмена пользователем подписанного персонального номера монеты (например, на больший номинал). Использование вместо M обычной хэш-функции, стойкой в части вычисления коллизий и в части обращения, устранит указанный гомоморфизм, и сделает невозможным подписи вслепую.
Действительно, замена сообщения m на значение хэш-функции h(m) в уравнении шифрования приведет к тому, что снятие маски станет невозможным.
Для исключения этого можно, например, ввести избыточность в текст сообщения. Отметим, что в случае обычной подписи RSA недопустимо вводить избыточность путем использования нулевых младших или старших разрядов. В первом случае это можно обойти, используя гомоморфное вложение кольца Z/nZ в кольцо Z. Во втором случае указанный обход основан на гомоморфном вложении Z/nZ в кольцо целых алгебраического расширения поля рациональных чисел и на использовании алгоритма LLL для минимизации базиса решетки.
Однако в случае эллиптических кривых этот недостаток исключен.
Литература
1. A. Menezes, P. van Oorchot, S. Vanstone. Handbook of applied cryptography.
CRC press, 1997.
2. B. Schneier. Applied Glyptography: Protocols, Algorithms, and Source Code in C, second edition.
J. Wiley Sons, New York, 1996.
3. А. Г. Ростовцев, В. А. Матвеев. Элементы криптологии.
Под ред. П. Д. Зегжды.
Изд-во СПбГТУ, 1993.
