# Tag Info

2

Let $G$ be a group (w.l.o.g. of prime order $p$) generated by $g$. The CDH is given two elements $g^a$ and $g^b$ and to compute $g^{ab}$. What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary (worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an ...

-1

All computations produced by modulo P, where P is prime number. From Euler theorem we know that $g^{P-1} = 1 \bmod P$. Hence, $g^P = g \bmod P$. We know that $b*b^{-1} = 1 \bmod P$ So when you calculate $g^{bb^{-1}} \bmod P$ you will receive $g^{nP+1} \bmod P =g^{n}*g \bmod P$. That is why $g^{(ab)b^{-1}} \bmod P$ =$g^{a(bb^{-1})} \bmod P = g^{a(nP+1)} ... 3 In DH if you want to compute$g^a$from$K$you have to know$b$(which the legitimate receiver of$g^a$clearly knowns, so this does not really make sence). This party can compute the inverse of$b$, namely$b^{-1}$, and then compute$g^a=K^{b^{-1}}$. Note that this is not the same as$(K^b)^{-1}=(g^{ab})^{-1}$(as I will discuss below). But that is not ... 0 Also: given$x$or$y$:$g^{xy} = g^{x^y} = g^{y^x}$. 7$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x$of them]$\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$[$\hspace{.03 in}y$of them]$\ldots \cdot g\cdot g\cdot g)= \;\;\; g\cdot g\cdot g\cdot \ldots$[$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$of them] ... 3 That depends on the groups you are working in. Using a$\Sigma$-protocol If you have a group$G$of prime order$q$where the DDH is hard and you have a DH tuple$(g,g^u,g^v,g^w)$with$w\equiv uv \pmod q$, then if your prover knows one of these values, say$u$, then we can write the DH tuple as$(g,g^u,h,h^u)$and he is able to convince a verifier that ... 0 Each algorithm or technique has its purpose. DH provides a way to generate two numbers, one that can be called the private key another the pub key. The DH algorithm does not cover encryption i.e. how to use the key. As Thomas and poncho point out in elegant detail, one can take inspiration from DH and come up with an encryption scheme. But then once can't ... 0 Firstly, PKI makes use of a private key and a public key. The private key is known only to the user, while the public key is communicated securely via the use of certificates. To provide authentication and non-repudiation, users may sign a message with their private keys and obtain a digital signature. Any other users can verify that the signed signature is ... 1 All this work is done modulo the prime$p$(which is 11 in your toy example); in this field, addition, subtraction and multiplication is done in the usual way (except you do a modulo$p$at the end); however division is defined differently. We define$x = 6/4\ (\bmod 11)$to be that value such that$x \times 4 = 6\ (\bmod 11)$. Now, we see that$7 \times ...

4

$\pi$ is the transcendental number 3.1415926... It's there in the formula to show this specific number was not chosen with a specific cryptographical backdoor in mind; it seems unlikely that anyone was able to select the value of $\pi$ (unless Carl Sagan was correct, of course :-)

Top 50 recent answers are included