Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

DSA - Алгоритм

32K
14 мая 2012 года
LawManiak
76 / / 24.10.2011
Доброго времени суток.
Никак не могу разобраться в создании электронной подписи алгоритмом DSA.
В Шнайере и на вики алгоритм расписан весьма размыто. Пробовал разбираться в исходнике Bouncy Castle, так себе.... Может кто-нибудь может доступно объяснить алгоритм по пунктам или хотя бы псевдокодом?
Пишу на C#...
316
15 мая 2012 года
Alm3n
889 / / 29.05.2009
Да нет, на вики алгоритм написан достаточно понятно, нескольких мелких объяснений только не хватает.
Из всей статьи нужны только разделы parameter generation, preuser-key и signing.
Всё сводится к тому, что сначала нужно выбрать несколько параметров, которые можно шарить между пользователями, они являются открытыми, хэш функцию, и два закрытых параметра.
На основе выбранных параметров и хэша, проделать, как написано в разделе signing. Там простые операции с числами, строка с данными тоже представляется числом.
В этой специификации очень хорошо всё написано, тебе должны быть интересны главы 2.3; 4.1; 4.2; 4.5; 4.6.
А вот тут можно сравнивать правильные значения с теми, что получились у тебя.
На domain_parameter_seed и counter можно забить. Сразу бери p,q ну и чего там ещё нужно будет основного для генерации последующих чисел и сравнивай с тем, что в документе написано.
Полностью алгоритм в псевдокоде расписывать не буду. Если будут вопросы по каким-то частям, - генерации параметра x или k, например, - отвечу.
32K
15 мая 2012 года
LawManiak
76 / / 24.10.2011
Я использовал алгоритм отсюда
Не знаю на сколько верные тут формулы. Если верные, то я уже практически сделал - нам преподаватель разрешил для ускорения процесса использовать числа в пределах int32 или int64. Все-таки работа с возведенными в степень числами с битовым размером 512, 576, 640, 704, 768, 832, 896, 960 или 1024 связана с большими затратами ресурсов.

В этом алгоритме меня смущает проверка подписи.
w = ((s)^-1) mod q
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...
341
16 мая 2012 года
Der Meister
874 / / 21.12.2007
Цитата: LawManiak
w = ((s)^-1) mod q
число (s)^-1 будет заведомо очень малым и при операции mod q мы получим его же, тогда к чему это...

В теории чисел обратное число - такое, которое при произведении на обратное даст единицу в остатке. Например, обратным к 11 по модулю 25 будет число 16: 11*16 (mod 25) = 1.

32K
16 мая 2012 года
LawManiak
76 / / 24.10.2011
так... а как мне записать подобное вычисление кодом C#?
341
16 мая 2012 года
Der Meister
874 / / 21.12.2007
Обратное число есть только тогда, когда s и q взаимно просты, то есть НОД(s, q) = 1. Находится расширенным алгоритмом Евклида (логарифмическая сложность, зависящая от модуля), либо через теорему Эйлера.
Код:
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;
}
32K
16 мая 2012 года
LawManiak
76 / / 24.10.2011
Спасибо. Получается что этот метод возвращает значение 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)
341
16 мая 2012 года
Der Meister
874 / / 21.12.2007
Цитата: LawManiak
Получается что этот метод возвращает значение w = ((s)^-1) mod q ?

Это - реализация расширенного алгоритма Евклида; метод возвращает обратное значение, если оно есть.

Цитата: LawManiak
Честно не до конца понял все это, поэтому возник вопрос, а как нам получить
u1 = H(m) * w(mod q)
u2 = r * w(mod q)

H(m) - уже получил. интересует именно w(mod q)

По модулю здесь берётся произведение, а не множитель.

32K
16 мая 2012 года
LawManiak
76 / / 24.10.2011
4й год учусь, два из которых изучал математику и все-равно чувствую себя каким-то недоученым когда читаю что-то подобное :)
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?

Для получения u1 и u2 нам нужно использовать описанный выше вами метод,
только value=H(m) * w; modulo=q для u1
value=r*w; modulo=q для u2
Правильно я понял или нет? Никак не могу разобраться....
341
16 мая 2012 года
Der Meister
874 / / 21.12.2007
Цитата: LawManiak
4й год учусь, два из которых изучал математику и все-равно чувствую себя каким-то недоученым когда читаю что-то подобное :)
Можно конкретней? Метод, который вы написали возвращает (s)^-1(mod q) если он есть?

Именно.

Цитата: LawManiak
Для получения u1 и 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;
32K
16 мая 2012 года
LawManiak
76 / / 24.10.2011
А, всего-то :) Запутался в словах, решил что u1 и u2 что-то большее чем остаток...
Спасибо. Очень помогли!
32K
16 мая 2012 года
LawManiak
76 / / 24.10.2011
Возможно я все-таки что-то намутил, но мне постоянно выдает что подпись не верная...

Вот так получаю численное значение хеша
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;

Где закралась ошибка?

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог