Алгоритм Диффи-Хелмана

← →
R2D2 (2006-04-14 22:22) [0]

Помогите пожалуйста реализовать этот самый алгоритм.
http://book.itep.ru/6/difi_646.htm
а то у меня с математическими операциями в делфи никогда нормально не получалось дружить....

← →
palva © (2006-04-14 22:42) [1]

А модульное возведение в степень вам тоже надо реализовывать?

← →
Std © (2006-04-14 22:58) [2]

вот оно как раз у меня и не получается :(
var x,y,a,b,n,q,k1,k2:integer; begin n:=12345; q:=98765; x:=Random(1000); y:=Random(1000); a:=(power(x,q))mod n; b:=(power(y,q))mod n;
ошибка в последних двух строчка:
[Pascal Error] : E2015 Operator not applicable to this operand type

← →
palva © (2006-04-14 23:27) [3]

Функция power возвращает тип extended, а операция mod применима только к целым значениям. Поэтому ошибка компиляции. В добавок вы указали аргументы функции power не в том порядке.

Но проблема не в этом. Вам нужно возвести большое число в большую степень, а потом взять остаток от деления. При этом нельзя переходить к типу extended, поскольку при округлениях вы потеряете информацию, а целые типы не позволяют хранить такие большие числа, которые получаются при промежуточных вычислениях.

Чтобы уменьшить промежуточные результаты остаток берется после каждого умножения. Т. е. пусть у вас промежуточный результат будет t: LongInt; Тогда для вычисления power(q, x) mod n мы делаем t:=1; а потом x раз выполняем оператор t := t*q mod n; При этом операцию mod приходится делать многократно, зато промежуточный результат не выйдет за пределы LongInt.

← →
Eraser © (2006-04-15 00:53) [4]

> R2D2 (14.04.06 22:22)

зачем реализовывать? всё давно реализовано, например в CryptoAPI, начиная с win95.
http://kladovka.net.ru/index.cgi?pid=list&rid=347

← →
R2D2 (2006-04-15 18:12) [5]

palva
а как ключ потом находить второму пользователю имея t?
Вот вычислили А
x:=123456;
y:=8765436;
for i:=1 to x do
begin
A:=(A*q)mod n;
end;
Ключ ищется: K= A^y mod n

как вычислять теперь К? а то шото не соображе никак...
k:=1;
for j:=1 to y do
begin
k:=(k*A)mod n;
end;
вот так если делать то ключи не совпадают...

Там, куда вы дали ссылку, по-моему, все хорошо описано.
x:=123456; // x вырабатывает первый партнер как случайное число
y:=8765436; // а вот это не надо, y вырабатывает второй партнер
A:=1; // а вот это вы пропустили
Далее полученное A пересылается второму партнеру, а он вычисляет K по приведенному вами алгоритму. Этот ключ оказался у партнера K

Параллельно ведутся те же вычисления с перестановкой партнеров, т. е. Второй вычисляет случайным образом y, пересылает первому A (уже другое, вычисленное по y), а первый вычисляет ключ. Ключи должны совпасть.

Алгоритм Диффи-Хелмана Найти похожие ветки