Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Реализация схемы Эль-Гамаля

Автор: Finalist 22.4.2011, 17:35

Привет всем!
Хочу реализовать шифрование по схеме Эль-Гамаля.
Столкнулся с проблемой больших чисел, которые не помещаются в double. Использовать библиотеку больших чисел не охота.. хочу все сам сделать.
Например формула по вычислению открытого ключа Y выглядит следующим образом y = g ^ k MOD p ( остаток от деления (g в степени k) на p )
при использовании стандартных функций pow(); и fmod(); результат выходит неверный.. не хватает точности double.
Я решил эту задачу следующим образом..

Код


// y = g^k mod p
qreal y = 1;
for (i=0; i < k; i++)
{
    y = y * g;
    y = fmod(y, p);
}

на выходе получается все ок..
далее идет вычисление шифротекста a и b
a = g ^ k mod p
тут все просто, так же как с Y

Код


// a = g^k mod p
qreal a = 1;
for (i = 0; i < k; i++)
{
    a = a * g;
    a = fmod(a, p);
}

с b немного сложнее, но тоже решил..
b = y^k * M mod p (где M шифруемое число)

Код


// b = b ^ k * M mod p
qreal b = 1;
for (i = 0; i < k; i++)
{
    b = b * y;
    if (i == 0)
    {
        b *= M;
    }
    b = fmod(b, p);
}

вот теперь эти (a,b) я передаю по сети, на сервере ловлю.. и расшифровываю по формуле..
(b / a^x) mod p
и вот тут загвоздка.. не силен я в математике.. когда вычислял b там просто один раз в цикле умножил b на M..
но тут, нужно разделить b на a^x и только потом вычислить mod p.
как я только не пробовал... ничего не выходит.. числа получаются не те, что я шифрую...

может кто нибудь из математиков будет смотреть.. и знает как сократить дробь?
например такую... 517 / (345^68) mod 809 = 100
у меня ни при каких расчетах не выходит 100.

примеры реализации и формулы брал на википедии, и еще одном сайте ( http://masteroid.ru/content/view/1286/49/ )
только на mesteroid'е мой Y заменен на H... а A и B заменены на C1 и C2 соответственно...
А еще на википедии и mesroid немного разные формулы расшифровывания текста..

Код



// M2 = fmod ( b / pow(a, x), p ); - это на мастероиде
// qreal M2 = fmod ( b * pow( pow(a,x) , -1 ), p ); - это на вики

возможно они одинаковы.. я не математик (а мама говорила учись! пригодится)

P.S. Забыл сказать, что qreal = double ... использую Qt

Автор: bsa 22.4.2011, 19:21

Finalist, без математики больших чисел тебе не обойтись. Возьми http://www.di-mgt.com.au/bigdigits.html.

Цитата(Finalist @ 22.4.2011, 17:35

)

возможно они одинаковы.. я не математик (а мама говорила учись! пригодится)

Правильно говорила. Программировать, не зная математики, очень сложно. Эти формулы одинаковы: x^-n == (1 / x) ^ n == 1 / (x ^ n)

Автор: Finalist 22.4.2011, 19:36

Я почему-то так и думал.. что без них никак.
Придется качать! Спасибо bsa!! буду делать на большоой либе.

Автор: bsa 25.4.2011, 09:47

Цитата(Finalist @ 22.4.2011, 19:36

)

буду делать на большоой либе.

Вообще-то, та либа, что я тебе дал, очень маленькая.