Шифрование с открытым ключом

← →
Shredder © (2005-05-10 05:59) [0]

Здравствуйте, уважаемые мастера! Суть проблемы: нужно реализовать шифрование, в ходе которого используется операция (^-возведение в степень):
(a^b) mod p

Все бы ничего, когда числа маленькие, а когда выражение типа:

(17844^578) mod 549

-проблема.
Если вычислять эту строку в лоб, ничего не выйдет - сильно большие числа. Может существует обходной путь вычисления? Реализованы ведь алгоритмы Эль-Гамаля, Диффи-Хелмана.

← →
Erik1 © (2005-05-10 11:58) [1]

Лучше использовать готорые библиотеки, например SSL3.

← →
nikkie © (2005-05-10 13:09) [2]

>(17844^578) mod 549
если a=b(mod n), то a^m=b^m(mod n)
не надо возводить число в степень, а потом брать остаток.
надо сразу умножать по модулю n.
вместо 17844 берем 276 = остаток от деления на 549.
276^2 = 76176 = 414 (mod 549)
276^3 = 276 * 414 = 114264 = 72 (mod 549)
и т.д.

можно обойтись обычным integer, если n невелико. но для шифрования с открытым ключом обычно используются простые числа длиной в несколько десятков десятичных цифр. тут потребуется реализовывать длинную арифметику. но и с длинной арифметикой считать степени по модулю n надо так, как написано выше.

← →
Shredder © (2005-05-10 17:05) [3]

2Erik1: требуется реализация вручную.

2nikkie: Благодарю, суть уловил. Только в ваших примерах и формулах со знаками равенства немного не то. Насчет формулы:
76 mod 7 = 6
76^10 mod 7 = 1 и не равно 6^10 - это как пример.

Всё, топик можно считать закрытым.

← →
nikkie © (2005-05-10 19:05) [4]

если уж вопрос об обозначениях.

есть такой математический знак - как знак равенства, но с тремя черточками.
воспроизвести его здесь я не могу.
используют его, например, когда говорят
"функция f тождественно равна 0": "f=0"
(вместо знака равенства - те три черточки).

также его используют для записи сравнений по модулю.
"а сравнимо с b по модулю n": "a=b(mod n)"
(вместо знака равенства - те три черточки).

может быть такая запись
76 mod 7 = 6
более привычна программисту на паскале, поскольку есть такой оператор mod.
но в математике такая запись не используется.

← →
KilkennyCat © (2005-05-10 19:21) [5]

≡

← →
Shredder © (2005-05-17 05:53) [6]

Вот возник еще вопрос по алгоритму Эль-Гамаля:

m - сообщение, которое нужно зашифровать;
p - модуль (простое число);
g,k - целые числа в пределах p-1;

x - секретный ключ;
y = (g^x) mod p - открытый ключ;

Шифрование:

a = (g^k) mod p;
b = (y^k)*m mod p;

Вопрос в дешифровании: как, имея a,b,x, получить исходное сообщение m?

← →
Reindeer Moss Eater © (2005-05-17 11:05) [7]

А зачем изобретать велосипед?
MSCryptoAPI 2.0.

← →
nikkie © (2005-05-17 23:34) [8]

>как, имея a,b,x, получить исходное сообщение m?
m=b*(a^x)^(-1) (mod p)
надо уметь находить обратные элементы (делить по модулю p).
для этого есть расширенный алгоритм Евклида.

если НОД(A,B)=d, то существуют такие целые u и v, что uA + vB = d.
алгоритм Евклида вычисляет d, а если аккуратно его провести -
то попутно вычисляет u и v. в нашем случае возьмем A=a^x и B=p.
они взаимнопросты (потому что p - просто). значит алгоритм Евклида
даст нам u и v такие, что uA+vp=1, т.е. uA=1 (mod p).
u - искомый обратный элемент. умножим его на b - получим исходное сообщение.

2nikkie: Большое спасибо!

Только я использовал функцию Эйлера:
Ф(x)=p-1, где p - модуль(простое число).

В результате выражение дешифрования преобразовалось:

b/a^x mod p = [(b mod p)*(a^[x*(p-2)] mod p)] mod p

{т.к. a^(-1) mod p = a^(Ф(x)-1) mod p}

либо b*a^(x*(p-2)) mod p (но приведенное выше более длинное выражение удобней для вычисления в Делфи в случае использования отдельной функции дискретного возведения в степень [если a^b mod p, то на входе функции - a,b,p].

да, это я чего-то стормозил. с помощью малой теоремы Ферма (это которая a^(p-1)=1 (mod p)) проще посчитать обратный. хотя быть может с алгоритмом Евклида быстрее будет - при перемножении чисел надо на p делить все время, а в алгоритме Евклида делим на меньшие числа. глубоко в это не погружался, не знаю.

>>Shredder © (10.05.05 05:59)

>(a^b) mod p

Буквально на днях перебирал тетради, видел в конспекте по безопасности алгоритм.

Шифрование с открытым ключом Найти похожие ветки