static int? GetInverse(int value, int modulo) {
var x1 = 0;
var x2 = 1;
var y1 = 1;
var y2 = 0;
var m = modulo;
while (m > 0) {
var q = value / m;
var r = value % m;
var x = x2 - q*x1;
var y = y2 - q*y1;
value = m;
m = r;
x2 = x1;
x1 = x;
y2 = y1;
y1 = y;
}
if (value == 1) {
return x2 < 0 ? modulo + x2 : x2;
}
return null;
}
DSA - Алгоритм
Доброго времени суток.
Никак не могу разобраться в создании электронной подписи алгоритмом DSA.
В Шнайере и на вики алгоритм расписан весьма размыто. Пробовал разбираться в исходнике Bouncy Castle, так себе.... Может кто-нибудь может доступно объяснить алгоритм по пунктам или хотя бы псевдокодом?
Пишу на C#...
Никак не могу разобраться в создании электронной подписи алгоритмом DSA.
В Шнайере и на вики алгоритм расписан весьма размыто. Пробовал разбираться в исходнике Bouncy Castle, так себе.... Может кто-нибудь может доступно объяснить алгоритм по пунктам или хотя бы псевдокодом?
Пишу на C#...
Да нет, на вики алгоритм написан достаточно понятно, нескольких мелких объяснений только не хватает.
Из всей статьи нужны только разделы parameter generation, preuser-key и signing.
Всё сводится к тому, что сначала нужно выбрать несколько параметров, которые можно шарить между пользователями, они являются открытыми, хэш функцию, и два закрытых параметра.
На основе выбранных параметров и хэша, проделать, как написано в разделе signing. Там простые операции с числами, строка с данными тоже представляется числом.
В этой специификации очень хорошо всё написано, тебе должны быть интересны главы 2.3; 4.1; 4.2; 4.5; 4.6.
А вот тут можно сравнивать правильные значения с теми, что получились у тебя.
На domain_parameter_seed и counter можно забить. Сразу бери p,q ну и чего там ещё нужно будет основного для генерации последующих чисел и сравнивай с тем, что в документе написано.
Полностью алгоритм в псевдокоде расписывать не буду. Если будут вопросы по каким-то частям, - генерации параметра x или k, например, - отвечу.
Из всей статьи нужны только разделы parameter generation, preuser-key и signing.
Всё сводится к тому, что сначала нужно выбрать несколько параметров, которые можно шарить между пользователями, они являются открытыми, хэш функцию, и два закрытых параметра.
На основе выбранных параметров и хэша, проделать, как написано в разделе signing. Там простые операции с числами, строка с данными тоже представляется числом.
В этой специификации очень хорошо всё написано, тебе должны быть интересны главы 2.3; 4.1; 4.2; 4.5; 4.6.
А вот тут можно сравнивать правильные значения с теми, что получились у тебя.
На domain_parameter_seed и counter можно забить. Сразу бери p,q ну и чего там ещё нужно будет основного для генерации последующих чисел и сравнивай с тем, что в документе написано.
Полностью алгоритм в псевдокоде расписывать не буду. Если будут вопросы по каким-то частям, - генерации параметра x или k, например, - отвечу.
Я использовал алгоритм отсюда
Не знаю на сколько верные тут формулы. Если верные, то я уже практически сделал - нам преподаватель разрешил для ускорения процесса использовать числа в пределах int32 или int64. Все-таки работа с возведенными в степень числами с битовым размером 512, 576, 640, 704, 768, 832, 896, 960 или 1024 связана с большими затратами ресурсов.
В этом алгоритме меня смущает проверка подписи.
w = ((s)^-1) mod q
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...
Не знаю на сколько верные тут формулы. Если верные, то я уже практически сделал - нам преподаватель разрешил для ускорения процесса использовать числа в пределах int32 или int64. Все-таки работа с возведенными в степень числами с битовым размером 512, 576, 640, 704, 768, 832, 896, 960 или 1024 связана с большими затратами ресурсов.
В этом алгоритме меня смущает проверка подписи.
w = ((s)^-1) mod q
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...
Цитата: LawManiak
w = ((s)^-1) mod q
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...
В теории чисел обратное число - такое, которое при произведении на обратное даст единицу в остатке. Например, обратным к 11 по модулю 25 будет число 16: 11*16 (mod 25) = 1.
так... а как мне записать подобное вычисление кодом C#?
Обратное число есть только тогда, когда s и q взаимно просты, то есть НОД(s, q) = 1. Находится расширенным алгоритмом Евклида (логарифмическая сложность, зависящая от модуля), либо через теорему Эйлера.
Код:
Спасибо. Получается что этот метод возвращает значение w = ((s)^-1) mod q ?
В целом числа s и q всегда взаимно простые. q - простое по условию, а s всегда меньше q...
Честно не до конца понял все это, поэтому возник вопрос, а как нам получить
u1 = H(m) * w(mod q)
u2 = r * w(mod q)
H(m) - уже получил. интересует именно w(mod q)
В целом числа s и q всегда взаимно простые. q - простое по условию, а s всегда меньше q...
Честно не до конца понял все это, поэтому возник вопрос, а как нам получить
u1 = H(m) * w(mod q)
u2 = r * w(mod q)
H(m) - уже получил. интересует именно w(mod q)
Цитата: LawManiak
Получается что этот метод возвращает значение w = ((s)^-1) mod q ?
Это - реализация расширенного алгоритма Евклида; метод возвращает обратное значение, если оно есть.
Цитата: LawManiak
Честно не до конца понял все это, поэтому возник вопрос, а как нам получить
u1 = H(m) * w(mod q)
u2 = r * w(mod q)
H(m) - уже получил. интересует именно w(mod q)
u1 = H(m) * w(mod q)
u2 = r * w(mod q)
H(m) - уже получил. интересует именно w(mod q)
По модулю здесь берётся произведение, а не множитель.
4й год учусь, два из которых изучал математику и все-равно чувствую себя каким-то недоученым когда читаю что-то подобное :)
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?
Для получения u1 и u2 нам нужно использовать описанный выше вами метод,
только value=H(m) * w; modulo=q для u1
value=r*w; modulo=q для u2
Правильно я понял или нет? Никак не могу разобраться....
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?
Для получения u1 и u2 нам нужно использовать описанный выше вами метод,
только value=H(m) * w; modulo=q для u1
value=r*w; modulo=q для u2
Правильно я понял или нет? Никак не могу разобраться....
Цитата: LawManiak
4й год учусь, два из которых изучал математику и все-равно чувствую себя каким-то недоученым когда читаю что-то подобное :)
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?
Именно.
Цитата: LawManiak
Для получения u1 и u2 нам нужно использовать описанный выше вами метод,
только value=H(m) * w; modulo=q для u1
value=r*w; modulo=q для u2
Правильно я понял или нет? Никак не могу разобраться....
только value=H(m) * w; modulo=q для u1
value=r*w; modulo=q для u2
Правильно я понял или нет? Никак не могу разобраться....
Код:
var w = GetInverse(s, q);
var u1 = (H(m) * w) % q;
var u2 = (r * w) % q;
var u1 = (H(m) * w) % q;
var u2 = (r * w) % q;
А, всего-то :) Запутался в словах, решил что u1 и u2 что-то большее чем остаток...
Спасибо. Очень помогли!
Спасибо. Очень помогли!
Возможно я все-таки что-то намутил, но мне постоянно выдает что подпись не верная...
Вот так получаю численное значение хеша
BigInteger has = BigInteger.Parse(hash,NumberStyles.HexNumber);
Вот так w
var w = GetInverse(s, q);
Вот так u1
var u1 = Convert.ToInt32(((has * w) % q).ToString());
Костыль, но ничего лучше придумать не смог...
Вот так u2
var u2 = Convert.ToInt32(((r * w) % q).ToString());
Тот же костыль...
Вот так v
BigInteger v = ((BigInteger.Pow(g, u1) * BigInteger.Pow(y, u2)) % p) % q;
Где закралась ошибка?
Вот так получаю численное значение хеша
BigInteger has = BigInteger.Parse(hash,NumberStyles.HexNumber);
Вот так w
var w = GetInverse(s, q);
Вот так u1
var u1 = Convert.ToInt32(((has * w) % q).ToString());
Костыль, но ничего лучше придумать не смог...
Вот так u2
var u2 = Convert.ToInt32(((r * w) % q).ToString());
Тот же костыль...
Вот так v
BigInteger v = ((BigInteger.Pow(g, u1) * BigInteger.Pow(y, u2)) % p) % q;
Где закралась ошибка?