How does this libgcrypt elgamal decryption work?

Question

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);

It is from this commit: https://github.com/gpg/libgcrypt/blob/410d70bad9a650e3837055e36f157894ae49a57d/cipher/elgamal.c

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);

Answer 1

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.