Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Шифрование с открытым ключом [D7, WinXP]

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

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

(17844^578) mod 549

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

VMcL (2005-05-19 16:45:00) [1]
>> Shredder © (10.05.05 05:59)

> (a^b) mod p

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

nikkie (2005-05-19 15:46:00) [2]
да, это я чего-то стормозил. с помощью малой теоремы Ферма (это которая a^(p-1)=1 (mod p)) проще посчитать обратный. хотя быть может с алгоритмом Евклида быстрее будет - при перемножении чисел надо на p делить все время, а в алгоритме Евклида делим на меньшие числа. глубоко в это не погружался, не знаю.

Shredder (2005-05-19 15:05:00) [3]
Только я использовал функцию Эйлера:
Ф(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].

Shredder (2005-05-19 14:37:00) [4]
2nikkie: Большое спасибо!

nikkie (2005-05-17 23:34:00) [5]
>как, имея 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 - получим исходное сообщение.

Reindeer Moss Eater (2005-05-17 11:05:00) [6]
А зачем изобретать велосипед?
MSCryptoAPI 2.0.

Shredder (2005-05-17 05:53:00) [7]
Вот возник еще вопрос по алгоритму Эль-Гамаля:

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?

KilkennyCat (2005-05-10 19:21:00) [8]
≡

nikkie (2005-05-10 19:05:00) [9]
если уж вопрос об обозначениях.

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

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

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

Shredder (2005-05-10 17:05:00) [10]
2Erik1: требуется реализация вручную.

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

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

nikkie (2005-05-10 13:09:00) [11]
>(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 надо так, как написано выше.

Erik1 (2005-05-10 11:58:00) [12]
Лучше использовать готорые библиотеки, например SSL3.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »