Tag Info

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] ...

2

The standard solution is to generate $g$ and $p$ once during application development, then hardcode $g$ and $p$ in your code. There are standard choices for $p$ and $g$, e.g., documented by NIST in their FIPS series. I suggest using one of those. There is no need to re-generate $g$ or $p$ each time. You can use the same $g$ and $p$ for everyone. See ...

1

I hope you understand your question. Your question is that given generator $g$ of a prime order $q$ group and some element $g^y$ of that group and another element $x_1 \in Z_q$ you want to check if there is such an $x_2$ or find $x_2\in Z_q$ such that $y\equiv x_1+x_2 \pmod q$? I assume that in this setting the discrete logarithm problem is hard, right? ...

1

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable. Let $p = 2p_1 + 1$ where both ...

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