Всем добрый вечер!
Прежде чем сделать выводы из того, что r = 1, попробуем разобраться
с "плохими" ключами.
Еще одно определение. Назовем ключ y "честным", если он может быть
представлен как y = a^x mod p для некоторого x. По сути это обозначает,
что он может являться открытым ключом в ГОСТе. Действительно, если
y = a^x mod p, то y = ( a^{x mod q} ) mod p, т.е. y - открытый ключ
для секретного ключа x' = x mod q (в ГОСТе требуется, чтобы секретный ключ
не превосходил q).
Соответственно, ключ, не являющийся "честным", назовем "нечестным".
Реально в схеме в качестве открытых ключей могут участвовать только
"честные" ключи. Таким образом, если существует алгоритм, показывающий,
что ключ "нечестный", то такой ключ неприменим (он будет отвергнут при
регистрации, либо при разрешении конфликта).
Утверждение: Ключ "честный" тогда и только тогда, когда он "хороший".
Действительно, если y = a^x, то y^q = a^{xq} = (a^q)^x = 1 mod p, т.е.
y - "хороший".
Обратно, пусть y^q = 1 mod p. Все числа вида a^x mod p (x = 0, 1, ..., q-1)
различны, их ровно q, и они являются корнями стерени q из 1 в поле F_p.
Стало быть, других корней нет, а y является корнем. Значит y = a^x mod p при
некотором x. Очевидно также, что такой x единственен в отрезке [0, q-1].
Зачем нужно это утверждение? Во-первых, чтобы не рассматривать "плохие"
ключи. Они не могут быть открытыми ключами, и их бессмысленно
использовать в схемах подписи - поскольку можно эффективно доказать, что парного
секретного ключа к ним не существует. Во-вторых, существование x,
соответствующего y, пригодится в последующих рассуждениях.
Детали - в следующем сообщении.
С уважением,
Алексей Чиликов.
> Всем добрый вечер!
>
> В порядке дальнейшего исследования схемы Komlin'а
> рассмотрим некоторое ее обобщение.
>
> Во-первых, разобъем процедуру проверки подписи на два этапа
>
> 1. Вычисление u'( s,r', M ) = a^{z1} y^{z2} mod p
> 2. Вычисление u ( s,r', M ) = u' mod q и сравение u со
> значением r'
>
> Назовем подпись (s,r') универсальной для набора сообщений
> M_1, ... M_n, если u( s,r', M_i ) = r' mod q.
> Соответственно, назовем подпись (s,r') сверхуниверсальной
> для набора сообщений M_1, ... M_n, если u'( s,r', M_i ) = r
> mod p
> и r = r' mod q. (r < p).
>
> Очевидно, что универсальная подпись подходит ко всем
> сообщениям M_i.
> Также очевидно, что сверхуниверсальная подпись является
> универсальной
> для того же набора (и тоже подходит ко всем M_i).
>
> Схема Komlin'а позволяет строить сверхуниверсальные подписи
> для
> некоторых классов сообщений. Ни один из предложенных
> вариантов не
> позволяет строить универсальные подписи, не являющиеся
> сверхуниверсальными. Поэтому я полагаю, что будет корректно
> рассматривать сверхуниверсальные подписи в целом, как
> некоторое
> обобщение идеи Komlin'а (в предыдущем сообщении я приводил
> еще пример
> сверхуниверсальной подписи).
>
> Теперь рассмотрим, какие вообще бывают сверхуниверсальные
> подписи.
>
> Имеет смысл сразу оговориться, что все h(M_i) различны,
> поскольку в
> противном случае сообщения полностью эквивалентны с точких
> зрения
> процедуры формирования подписи (тогда речь идет о коллизиях
> в хеш-функции). Также естественно полагать, что подпись
> сверхуниверсальна хотя бы для двух различных сообщений.
>
> Рассмотрим пару сообщений M_1, M_2 и обозначим
> соответствующие значения
> хеш-функций через h_1, h_2. Рассмотрим систему уравнений:
>
> a^{z1_1} y^{z2_1} = a^{z1_2} y^{z2_2} = r mod p
> z1_i = s v_i mod q
> z2_i = (q-r) v_i mod q
> v_i = h_i^{q-2} mod q
>
> Далее имеем
>
> a^{z1_1-z1_2} y^{z2_1-z2_2} = 1 mod p
>
> Теперь возникает естественное желание избавиться от
> редукции по
> модулю q в формулах для z. Поскольку a^q = 1 mod p, то с
> z1_i проблем не
> возникает. Для работы с z2_i сделаем следующее. Назовем y
> "хорошим" ключом,
> если y^q = 1 mod p и "плохим" в противном случае.
> Рассмотрим сначала случай "хороших" ключей.
> В этом случае можно записать такое уравнение
>
> a^{ s (v_1-v_2) } y^{ (q-r) (v_2-v_1) } = 1 mod p
>
> или же такое
>
> ( a^{s} y^{-r} ) ^ {v_2-v_1} = 1 mod p
>
> Отметим, что v_2 != v_1 поскольку h_2 != h_1, а возведение
> в степень q-2
> по модулю q - обратимая операция. Таким образом имеем
>
> t^v = 1 mod p, где 0 <v< q-1 , t = ( a^{s} y^{-r}
> ).
>
> Однако t^q = 1 mod p.
>
> Действительно, t^q = ( a^{qs} y^{-qr} ) = (a^q)^s
> (y^q)^{-r} = 1 mod q
>
> поскольку y - "хороший" ключ.
>
> Но тогда t = 1 mod p, так как v и q взаимно просты.
> А значение r = t^{v_1} mod p.
>
> Следовательно r = 1 mod p для любой сверхуниверсальной
> подписи, если ключ
> y - хороший.
>
> Что из этого следует и как разобраться с "плохими" ключами
> -
> в следующем сообщении.
>
> С уважением,
> Алексей Чиликов.
>
> > Всем добрый вечер!
> >
> > Хотелось бы добавить небольшой комментарий по поводу
> > приведенной схемы
> > универсальной подписи.
> >
> > Рассмотренный вариант сводится к вычислению на базе
> числа
> > x0 значения
> > y1 = p - a^{x0} mod p и позиционировании его как
> открытого
> > ключа.
> > При этом утверждается невозможность нахожения
> > соответствующего ему
> > x1 (a^{x1} = y1 mod p). Но, как утверждает автор, это
> и не
> > требуется.
> >
> > Далее, участники дискуссии (в частности, Сергей
> Леонтьев)
> > достаточно
> > убедительно продемонстрировали, что такого x1 вообще
> не
> > существует.
> > Но при этом все же осталось неясным, как можно
> эффективно
> > распознать
> > мошенничество (при знании x0 можно доказать, что x1
> не
> > существует,
> > но x0 известен лишь злоумышленнику, а он вряд ли его
> > выдаст).
> >
> > Тем не менее, есть простой и эффективный алгоритм для
> > распознания данной
> > схемы, с использованием лишь открытой информации (а
> именно,
> > ключа y1).
> > Для этого достаточно вычислить y1^q mod p. Легко
> видеть,
> > что
> > для любого "честного" открытого ключа это число будет
> равно
> > 1, а
> > для "подставного" (в схеме Komlin'а) - равно p-1.
> >
> > В самом деле,
> >
> > y^{q} = (a^{x})^{q} = (a^{q}^){x} = 1 mod p
> ("честный"
> > ключ)
> >
> > y1^{q} = (-y)^{q} = (-1)^{q} ( a^{x}^{q} ) = (-1)^{q}
> = -1
> > mod p ("подставной" ключ)
> >
> > Второе равенство следует из того, что q нечетно.
> >
> > Таким образом, ключ y1 может быть отвергнут при
> регистрации
> > (либо на стадии
> > разбора конфликта), поскольку не может быть
> сформирован
> > корректной
> > реализацией ГОСТ.
> >
> > Таким образом, "чистая" схема Komlin'а неприменима
> (может
> > быть распознана
> > при попытке применения).
> >
> > Тем не менее, это рассуждение не является полным
> решением
> > вопроса,
> > поскольку потенциально возможны различные модификации
> > схемы. Например,
> > вместо y1 = p - y0 mod p можно положить y1 = t*y0 mod
> p,
> > где t^3 = 1 и
> > потребовать выполнения условия z2 = 3n вместо z2 = 2n
> (в
> > обозначениях
> > статьи Komlin'а).
> >
> > Дальнейшие рассуждения на эту тему - в следующем
> сообщении.
> >
> > С уважением,
> > Алексей Чиликов.
> >
> > > Механизм мошеничества с цифровой
> подписью на
> > базе
> > > российского стандарта ГОСТ Р 34.10-94
> > >
> > >
> > >
> > > Вступление. <p>
> > > В настоящее время банковские ( и
> многие
> > другие
> > > деловые операции) практически немыслимы без
> > привлечения
> > > методов цифровых подписей.
> > > В мире негласным стандартом стали
> > алгоритмы,
> > > основанные на методе Эль-Гамаля (El Gamal), в
> > частности -
> > > американском стандарте DSA. В Российской
> Федерации,
> > > разумеется не сочли возможным слепо следовать
> > зарубежным
> > > разработкам и применили свой метод, незначительно
> > > отличающийся формулой вычисления
> > > цифровой подписи. Главным результатом этого
> > нововведения
> > > стала возможность произвести махинацию с цифровой
> > подписью
> > > заключающуюся в отправке неверно подписанного
> > документа, с
> > > последующим отказом от него.
> > > Примерная механика мошенничества
> такова:
> > вначале
> > > используется 1-я уязвимость ГОСТа позволяющая
> вполне
> > > легально сформировать "слабую подпись", т.е.
> подпись,
> > из
> > > которой может быть легко вычислен секретный ключ.
> В
> > > принципе, после этого можно отказаться уже от
> любого
> > > документа, но и с другой стороны нельзя доказать,
> что
> > он не
> > > был послан Вами.
> > > Конечно, подобная ситуация уже приемлема, когда
> Вы
> > > распоряжаетесь не своими деньгами, а
> государственными,
> > но
> > > ГОСТ позволяет и большее.
> > > После того как вы "засветили" свой
> ключ,
> > можно
> > > сформировать платёжку на ООО- "однодневоку" с
> > подписью,
> > > которая успешно пройдёт все требуемые стандартом
> > проверки,
> > > но не будет являться корректной, по отношению к
> > данному
> > > документу. После этого уже можно смело идти и
> заявлять
> > о
> > > хищении денежных средств.
> > > Чтобы не судиться с банком (т.к.
> > последний
> > > может долго и успешно защищаться, переадресовывая
> Ваши
> > > претензии к государственным органам сертификации,
> > > навязавшим ему подобную схему проверок) проще
> > застраховать
> > > финансовые операции и получить страховку спустя
> два
> > месяца,
> > > по окончании предварительного следствия.
> > > Этой ошибке подвержен только
> Российский
> > ГОСТ Р
> > > 34.10-94.
> > >
> > > 2. Общие положения
> > >
> > > Напомним вкратце суть предлагаемого ГОСТ Р
> 34.10-94
> > > метода.
> > >
> > > р- простое число, 2^509 < р <
> 2^512
> > либо 2^1020
> > > < р < 2^1024 .
> > > q- простое число, 2^254 < q <
> 2^256 и q
> > > является делителем для (p-1)
> > > а- целое число, 1 < а < р-1, при
> этом а^q
> > (mod
> > > p)=1.
> > > ...
> > > х- секретный ключ пользователя для формирования
> > подписи.
> > > 0 < х < q.
> > > у - открытый ключ пользователя для проверки
> подписи.
> > > у = а^x (mod p).
> > > ...
> > > Процедура подписи сообщения включает в себя
> следующие
> > > этапы:
> > >
> > > 1. Вычислить h(M) (далее- H)-значение хеш-функции
> h от
> > > сообщения М.
> > > Если h(M)(mod q)=0, присвоить h(M) значение 0255
> 1.
> > >
> > > 2. Выработать целое число k, 0 < k
> < q.
> > > 3. Вычислить два значения :
> > > r=a^k (mod p) и r' = r (mod q).
> > > Если r' =0, перейти к этапу 2 и выработать другое
> > значение
> > > числа k.
> > > 4. С использованием секретного ключа х
> пользователя
> > > (отправителя
> > > сообщения) вычислить значение
> > > ...
> > > ГОСТ:
> > >
> > > s= (xr' + kh(M))(mod q).
> > > ...
> > > DSA:
> > >
> > > ( k' * k ) mod q=1; (А1)
> > > 0 < k' < q, -
> фактически , k'
> > не может
> > > принять значение =1 согласно (А1)
> > > s= (k'(xr+H)) mod q. (А2)
> > > ...
> > > Процедура проверки :
> > >
> > > 1. Проверить условие: 0 < s < q и
>
> > 0
> > > < r' < q.
> > > Если хотя бы одно из этих условий не выполнено,
> то
> > подпись
> > > считается недействительной.
> > > 2. Вычислять h(M1 )-значение хеш-функции h от
> > полученного
> > > сообщения М1 .
> > > 3. Вычислить значение v= (h(M1 ))^q-2 (mod q)
> > > 4. Вычислить значения:z1 = sv (mod q) и
> z2 =
> > (q-r' ) v
> > > (mod q)
> > > 5. Вычислить значение u = (a^z1 y^z2
> (mod p))
> > (mod q)
> > > 6. Проверить условие: r' = u.
> > >
> > >
> > >
> > > 3. Первая ошибка ГОСТА
> > >
> > >
> > >
> > > Представим себе ситуацию когда генерируется
> значение
> > k=1
> > > (r= a ). Нетрудно заметить, что
> > >
> > > s = (H+rx) mod q
> > >
> > > отсюда, для любого H2=H+N можно легко
> вычислить
> > подпись
> > > s2=(S2+N) (mod q)
> > >
> > >
> > >
> > > И, самое главное , уравнение (h+ax) mod q =s, при
> > известных
> > > h,q,s решается за несколько секунд.
> > >
> > >
> > > На первый взгляд ничего особо
> страшного -
> > > вероятность наступления подобного события
> чрезвычайно
> > мала
> > > - порядка ( 10^-78), хотя, например, при
> тотальной
> > проверке
> > > неким недобросовестным сотрудником банка (или,
> при
> > передаче
> > > по открытым сетям, хакером) всех входящих
> подписей на
> > > предмет r=a (согласно ГОСТУ программа подписи
> может
> > иметь
> > > общее a для всех своих пользователей, что и
> делает,
> > > например, ЦБ РФ), от коллапса не гарантирован
> никто!
> > > Впрочем, куда вероятнее теперь другая
> > ситуация,
> > > когда будет умышленно формироваться нестойкая
> подпись,
> > с
> > > целью опротестования последующих платёжек- ведь
> > доказать,
> > > что подобная подпись была сформированна
> неслучайно
> > > невозможно, учитывая требование п. 4.7. ГОСТа
> ("Целое
> > > число k, которое генерируется в процедуре подписи
> > сообщения
> > > , должно быть секретным и должно быть уничтожено
> сразу
> > > после выработки подписи." (Зачем?!!! Если уж
> > злоумышленник
> > > доберётся до компьютера отправителя, то он не
> > мудрствуя,
> > > сам секретный ключ заберёт...) .
> > > К "сожалению", непосредственно
> > использовать
> > > применять известный ключ ещё рановато, т.к. Вы
> всё же
> > не
> > > сможете убедительно доказать, что платёжку
> посылали
> > другие
> > > лица. (Хотя для бухгалтера гос. учреждения и
> такая
> > схема
> > > вполне приемлема, ибо доказать что отсылал их
> именно
> > он
> > > также невозможно.). Но не стоит радоваться так,
> как
> > давно
> > > известно, жулика российский закон не обидит :)
> > >
> > > 4. Вторая ошибка. (Универсальная
> подпись,
> > > утверждённая ГОСТОМ).
> > > Давайте повнимательнее посмотрим на
> фразу
> > > "k- целое число, 0 < k < q."
> > > В "DSA", этот диапазон задан
> требованием о
> > > мультипликативной инверсии и s=0 при k=iq,
> i>=0
> > > А чем в нашем случае обоснованно это
> требование?
> > > ГОСТом ?!
> > > При внимательном изучении метода,
> > > выясняется, что существуют, многочисленные
> частные
> > случаи,
> > > наборов (x,p,q) в которых это требование не имеет
> > > математической основы. Фактически, его
> поддержание
> > лежит на
> > > добросовестности генератора подписи, т.е. вещи,
> > отвергаемой
> > > по определению:) (В самом деле, зачем тогда
> вообще
> > цифровая
> > > подпись нужна?).
> > >
> > > Впрочем, мы забежали вперёд. Итак,
> чем
> > грозит
> > > методу отсутствие "физических" ограничений на
> значение
> > k.
> > > Рассмотрим ситуацию с k = 0 (или k кратным q);
> > > r=k^0 =1;
> > > s=(xr+kH) (mod q) = x (mod q).
> > >
> > > Нетрудно видеть, что в этом случае
> > цифровая
> > > подпись не зависит от значений H. Т. е.
> теоретически,
> > > может служить подписью к любому сообщению!!!
> > > Возникает логичный вопрос: как же
> так,
> > ведь
> > > значение h входит в формулу проверки подписи.
> > Вообще-то
> > > этим вопросом можно и не задаваться, а проверить
> приём
> > для
> > > своего набора (p,q,x) экспериментально, но я всё
> же
> > приведу
> > > доказательство сокращения h.
> > >
> > >
> > > Рассмотрим случай с секретной подписью
> x=1.
> > > Открытая подпись y=a;
> > > Для удостоверения подписи проверяется
> равенство
> > > r= (a^ s1 y^s2 (mod p)) (mod q), где
> > > s1= sv (mod q); s2=(q-r)v (mod q); v=
> H^(q-2) (mod
> > > q);
> > > В нашем случае ситуация выглядит чуть проще
> (
> > > учитывая, что x,s,r=1, y=a и v < q):
> > > 1=(a^v a^((q-1)v (mod p)) ( mod p)) mod q.
> > > (q-1)v mod q - можно представить как
> (q-1)v - iq,
> > > где i результат целочисленного деления i=[(q-1)*v
> / q]
> > > =v-[v/q]=v, т.к. v < q по определению. Отсюда
> > > (a^v*a^(qv)*a^(-v)*a^(-qv)) =1. Что и
> требовалось
> > > доказать.
> > >
> > > Аналогичные принципы применяются при
> нахождении
> > > доказательства ( области применимости) для прочих
> x,
> > > следует только учесть, что:
> > > 1)y=a^x (mod p) = a^x - ip. y^v= a^v^x +
> ipva^x^(v-1)
> > +
> > > ... pi= a^(xv) + p*(...);
> > > y^v (mod p)= a^xv (mod p).
> > > 2) a^q (modp)=1 => a^(qz) (mod p)=1.
> > >
> > > Т.е, для любого открытого ключа y=a ,
> мы
> > > можем в качестве подписи любого сообщения
> прислать
> > (1,1). В
> > > более общем случае (x,1)
> > >
> > >
> > > Разумеется, саму по себе это подпись
> > > использовать нельзя, т.к. объяснить знание
> посторонним
> > > злоумышленником x невозможно. Но вот в сочетании
> с
> > > предварительной отсылкой "слабой подписи"
> подобный
> > вариант
> > > вполне объясним.
> > >
> > > Кроме того, что данная подпись
> подходит к
> > любому
> > > документу она имеет ещё одно замечательное
> достоинство
> > ,
> > > очевидно, что подобный набор значений не может
> быть
> > выдана
> > > Вашей программой ни при каких условиях ( это
> легко
> > доказать
> > > исходя из простоты q и требований к
> значениям
> > случайного
> > > ключа и хэша ). Это значит, что выждав сутки,
> можно
> > > "просмотреть выписки", и бежать в банк, потом,
> ещё
> > сутки с
> > > непонимающим видом искать "специалиста", и
> наконец не
> > > торопясь, бежать в милицию с заявлением о
> хищении.
> > Пока они
> > > вообще поймут, о чём идёт речь, деньги станут уже
> > > недосягаемы для правоохранительных органов.
> Скорее
> > всего,
> > > потрепав пару дней нервы работникам банка,
> следователь
> > > сложит дело в сейф к другим "глухарям". Дальше
> суд (а
> > > лучше страховка) и за вычетом небольших накладных
> > расходов
> > > Вы удваиваете свой капитал. Разумеется эта схема
> может
> > > успешно применяться и банками по отношению друг к
> > другу, и
> > > вообще всеми, кто использует ГОСТ по цифровой
> > подписи.
> > >
> > >
> > >
> > > 5. Дополнения и комментарии.
> > > Как такое могло случиться?
> >
> > >
> > > Конечно, первопричиной подобной
> проблемы
> > > стало странная позиция разрабочиков госта,
> решивших,
> > что
> > > мат. ограничения можно вооить законадательно?!
> > > Но есть ещё одна причина исключительно точно
> > изложенная
> > > Игорем Камоловым (www.firebox.ru), очень точно
> > описавшему
> > > ещё одну проблему ГОСТа
> > > > > > любой специалист в области криптографии вам
> совершенно
> > > обоснованно заявит, что стоикость криптосистемы в
> > первую
> > > очередь
> > > зависит от качества ключевой информации (
> в
> > том
> > > числе и случайного ключа - прим авт.).
> > > Все остальное есть второстепенно. Можно
> использовать
> > любой
> > > наворочанный алгоритм
> > > преобразования данных при нулевом ключе. И самое
> > смешное,
> > > что
> > > сертификат от ФАПСИ вы получите. Ибо нет ни одной
> > бумаги на
> > > то, как, из чего
> > > и каким образом должна генерироваться ключевая
> > информация.
> > >
---
> > >
> > >
> > > Вообще-то причина, по которой
> Россия
> > решила
> > > отказаться от общепринятого стандарта
> малопонятны. (В
> > > DSA(DSS) и классическом алгоритме Эль-Гамаля,
> такой
> > приём
> > > невозможен, т.к. универсальная подпись будет
> иметь
> > вид
> > > (0,1), что запрещено по определению.) Ссылки на
> более
> > > удобный для расчёта алгоритм бессмысленны, т.к.
> все
> > > вычисления выполняются компьютером. В вариант,
> что
> > > разрабатывавшие ГОСТ математики (и проверявшие
> его
> > > криптоаналитики ), решили, что математические
> > ограничения
> > > можно вводить законодательно как-то не верится...
> Что
> > нам
> > > остаётся думать???
> > > Благодарности
> >
> > > Я очень благодарен Д. Леонову, за
> > то, что
> > > он рискнул репутацией bugtraq.ru и выкладывал,
> > содержащие
> > > ошибки черновые варианты этой статьи до того, как
> они
> > > прошли широкую проверку, и без регулярно
> мешявшего их
> > на
> > > всё новые и новые версии.
> > >
> > > Также большое спасибо Волчкову А.
> > А.
> > > (www.gsmrus.ru), указавшему на серьёзные
> недоработки
> > > предыдущих публикаций), а так же Маркову Н. А.,
> Олегу
> > Ф.,
> > > Радовцеву Д. , Макаровой О. и всем кто
> присылал
> > замечания
> > > и предложения по опубликованным методам.
> > >
> > >
> > >
> > >
> > > С Уважением
> > >
> > >
> > >
> > > <A HREF="mailto:tcsvarka@marine.su">А. В.
> Кобец
> > > (Komlin), avkvladru@mail.ru </A>
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
