# How does this libgcrypt elgamal decryption work?

Update: The question below was asked before I realized that this is being done to prevent a side channel attack: https://github.com/advisories/GHSA-5p8v-2xvp-pwmc

What I am still curious about, is the math behind why this solution still works to decrypt Elgamal ciphertext.

Original Question:

libgcrypt elgamal decryption introduces a random number to perform decryption. Can anyone explain to my how this is working? I have posted the edited source code showing just the relevant operations. skey->p is the prime modulus, skey->x is the secret key of the receiver, and the encrypted message is (a,b). I don't understand the introduction of r to perform the decryption here. I would have thought t1=a^x mod p would have been sufficient. then the message could be calculated as b*t1^-1 mod p

/* We need a random number of about the prime size.  The random
number merely needs to be unpredictable; thus we use level 0.  */
_gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);

/* t1 = r^x mod p */
mpi_powm (t1, r, skey->x, skey->p);

/* t2 = (a * r)^-x mod p */
mpi_mulm (t2, a, r, skey->p);

mpi_powm (t2, t2, skey->x, skey->p);

mpi_invm (t2, t2, skey->p);

/* t1 = (t1 * t2) mod p*/
mpi_mulm (t1, t1, t2, skey->p);

mpi_mulm (output, b, t1, skey->p);


The source code starts at line 523

Update:

The most recent 1.9 release version of the file is here: https://github.com/gpg/libgcrypt/blob/LIBGCRYPT-1.9-BRANCH/cipher/elgamal.c

Starting at line 511, I can now see that there are additional lines to provide exponent blinding. What is blinding, how does it work, and why does this still provide a valid solution?

  /* We need a random number of about the prime size.  The random
number merely needs to be unpredictable; thus we use level 0.  */
_gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);

/* Also, exponent blinding: x_blind = x + (p-1)*r1 */
_gcry_mpi_randomize (r1, nbits, GCRY_WEAK_RANDOM);
mpi_set_highbit (r1, nbits - 1);
mpi_sub_ui (h, skey->p, 1);
mpi_mul (x_blind, h, r1);
mpi_add (x_blind, skey->x, x_blind);

/* t1 = r^x mod p */
mpi_powm (t1, r, x_blind, skey->p);
/* t2 = (a * r)^-x mod p */
mpi_mulm (t2, a, r, skey->p);
mpi_powm (t2, t2, x_blind, skey->p);
mpi_invm (t2, t2, skey->p);
/* t1 = (t1 * t2) mod p*/
mpi_mulm (t1, t1, t2, skey->p);

mpi_free (x_blind);
mpi_free (h);
mpi_free (r1);
mpi_free (r);
mpi_free (t2);

#else /*!USE_BLINDING*/

/* output = b/(a^x) mod p */
mpi_powm (t1, a, skey->x, skey->p);
mpi_invm (t1, t1, skey->p);

#endif /*!USE_BLINDING*/

mpi_mulm (output, b, t1, skey->p);

• Deleted my previous comment because the source I linked doesnt match my pulled version. Let me track that down and I'll add to the question. Sep 23 at 18:53
• Added the specific commit. Your comment actually made me look at the git commit notes, and I see that they appear to have been trying to address an attack vector github.com/advisories/GHSA-5p8v-2xvp-pwmc but I would still like to understand how it works Sep 23 at 18:57
• It explains on line 36: "Blinding is used to mitigate side-channel attacks. You may undef this to speed up the operation in case the system is secured against physical and network mounted side-channel attacks." Sep 23 at 18:57
• Yes, I guess I am more referring to the math that is being performed and showing why this works when there is a random r value being chosen Sep 23 at 18:59
• It's easy to see that in the blinding block of code, the $r$ value cancels out. There is a side-channel attack possible when raising $a$ to the private key $x$ which may help disclose something about $x$. Introducing a random value $r$ which is unknown to the attacker will mitigate this attack. The attack is explained here: cs.tau.ac.il/~tromer/radioexp Sep 23 at 19:20

The recipient has private key $$x$$ with the corresponding public key $$Y=G^x$$. To encrypt $$M$$ for the recipient, pick a uniformly random private key $$k$$, and calculate the ciphertext $$(A,B) = (G^k, Y^k\cdot M)$$.

Regular (non-blinded) decryption calculates $$M=\frac{B}{A^x}=\frac{(G^x)^k\cdot M}{(G^k)^x}$$. This works because $$(G^x)^k = (G^k)^x$$.

However, a side-channel attack exists where electromagnetic emanations from the exponentiation $$A^x$$ can leak information about the private key $$x$$.

In order to avoid directly performing the $$A^x$$ exponentiation, the blinded variant of the decryption first picks a uniformly random value $$R$$.

Now, we calculate $$M=\frac{B\cdot R^x}{(A\cdot R)^x}=\frac{B\cdot R^x}{A^x\cdot R^x}=\frac{B}{A^x}$$.

Note that we are now only ever exponentiating blinded values with our private key $$x$$. Since $$R$$ is unknown to an attacker, useful information is harder to extract by monitoring the electromagnetic emanations.

In the newer version of the code you've linked to, we use a blinded version of $$x$$. It is calculated as $$x'=x+(p-1)r'$$, where $$r'$$ is a uniformly random value.

This means that we end up calculating $$M=\frac{B}{A^{x'}}$$ instead of $$M=\frac{B}{A^{x}}$$ .

This works because $$(p-1)$$ is the size of the group generated by exponentiating group elements such as $$A$$. Due to the cyclic nature of the group, any multiple of the group size added to scalars (such as the private key $$x$$) will result in the same resulting group element value after exponentiation.

If we define $$\ell=(p-1)$$, then $$A^x=A^{(x+\ell)}=A^{(x+\ell r')}$$ for any values of $$x$$, $$A$$ and $$r'$$. (Note: all exponentiations in this answer are $$\operatorname{mod} p$$).

Therefore, when using the blinded value $$x'$$ instead of $$x$$, the result is the same even though the calculations performed by the CPU (and the resulting electromagnetic emanations) will be different.

• Thank you very much for the thorough explanation. I understand it now. Sep 26 at 19:58