4 ms·
About 1/4 down the page the author summarizes a sequence of optimizations of the basic ElGamal scheme. I don't quite understand the "Eliminate divisions" step,
by tromp 13y ago
About 1/4 down the page the author summarizes a sequence of optimizations of the basic ElGamal scheme.
I don't quite understand the "Eliminate divisions" step, which transforms
B^H(R,M) = A R^S
into
B^S = R A^H(R,M)
How are these two related?
- fryguy 13y agoI don't think they are related per se. Given A = B^a and R = B^r (not explicitly said in the first paragraph about El-Gamal, S is calculated by S = (H(R,M) - a)/r at the "Merge the hashes" step. At the next step, he's giving a completely new formula that looks similar: B^S = R * A^H(R,M) = B^r * B^a^H(R,M). However, this one is solved by S = r+a*H(R,M), which is a much easier thing to calculate, since there are no divisions.