WisFaq!

Diffie-Hellman

Ik denk dat ik daarstraks een aantal parameters vergeten ben, ik moet iets bewijzen:

P is een priemgetal groter dan 1
Y is kleiner dan P maar groter dan 1, dit hoeft geen priemgetal te zijn
A en B zijn groter dan 1 maar kleiner dan P

a = mod(Y^A,P)
b = mod(Y^B,P)
a = mod(b^A,P)
b = mod(a^B,P)

Nu moet er bewezen worden dat a = b
aan de hand van reeksontwikkeling

(x+y)^n = x^n + nx^(n-1)y + ((n(n-1))/2!) x^(n-2)y² + ...

Bij voorbaat dank

Stefanie
25-4-2005

Antwoord

Hallo,

Bedoel je met "a = mod(Y^A,P)" wat ik denk dat je bedoelt, namelijk: a en Y^A hebben dezelfde rest bij deling door P, en 0 a P ? Dat wordt dan ook genoteerd met a º Y^A (mod P).

Indien ja, dan is:
a-b º b^A - a^B (mod P)
º (Y^A)^B - (Y^B)^A
º Y^(AB) - Y^(AB)
º 0 (alles mod P)

De overgang bij het tweedeº-teken zou je vreemd kunnen vinden, immers b is niet gelijk aan Y^A, ze hebben enkel een gelijke rest bij deling door P, dus ze zijn gelijk modulo P. Maar bedenk dan:
als xºy (mod P) dan x = y + kP met k geheel.
Dus xⁿ
= (y+kP)ⁿ
= yⁿ + ny^n-1kP + n(n-1)/2 y^n-2k²P² + ...
Nu zijn al die termen, behalve de eerste, veelvouden van P, dus hier staat eigenlijk
= yⁿ + lP met l geheel.

Vandaar dat als xºy (mod P) dan xⁿ º yⁿ (mod P). En die eigenschap werd gebruikt in de tweede overgang.

Groeten,
Christophe.

Christophe
25-4-2005