# Tag Info

4

This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain. For prime $p$, we know that $g^{p-1} \equiv 1 \pmod{p}$. Therefore, $y = g^{p-2} \equiv 1/g \pmod {p}$. Therefore, $(xg).y \equiv x \pmod{p}$, revealing the secret key. If modulus is not ...

4

With addition and $\mathbb{Z}_n$, each party chooses a secret $x$ and sends $xg \pmod n$ over the wire, for an agreed upon generator $g$. Division by $g$ modulo $n$ is easily computable, and reveals $x$. In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With $\mathbb{Z}_n$ and ...

3

Given the additive group $(G, +)$ with $|G| = p$ and generator $P$, what are the computations and exchanged messages for Diffie-Hellman? I use order $p$ and assuming $p$ to be prime and the generator as $P$ (as it is used in context of elliptic curve groups - since you need additive groups where the DLP and the CDHP are hard - which is not the case for ...

3

To decrypt with this system, the decryptor first computes $g^{ab}$ (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of $g^{ab}$; that is written as $(g^{ab})^{-1}$. The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is ...

Only top voted, non community-wiki answers of a minimum length are eligible