这个libgcrypt elgamal解密是如何工作的？

Question

更新:下面的问题是在我意识到这样做是为了防止侧通道攻击之前提出的：https://github.com/advisories/GHSA-5p8v-2xvp-pwmc

我仍然好奇的是，为什么这个解决方案仍然可以解密Elgamal密文。

原始问题：

libgcrypt elgamal解密引入一个随机数来执行解密。有人能向我解释一下这是怎么回事吗？我已经张贴了编辑的源代码，只显示了相关的操作。skey->p是素模，skey->x是接收者的密钥，加密消息是(a,b)。我不明白在这里引入r来执行解密。我本以为t1=a^x mod p就足够了。然后，可以将消息计算为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);

它来自于以下提交：https://github.com/gpg/libgcrypt/blob/410d70bad9a650e3837055e36f157894ae49a57d/cipher/elgamal.c

源代码从第523行开始。

更新：

该文件的最新1.9版本如下：https://github.com/gpg/libgcrypt/blob/LIBGCRYPT-1.9-BRANCH/cipher/elgamal.c

从第511行开始，我现在可以看到还有额外的行来提供指数盲。什么是致盲，它是如何工作的，为什么这仍然是一个有效的解决方案？

  /* 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

收件人拥有私钥x和相应的公钥Y=G^x。若要加密收件人的M，请选择统一随机的私钥k，并计算密文(A,B) = (G^k, Y^k\cdot M)。

规则(非盲)解密计算M=\frac{B}{A^x}=\frac{(G^x)^k\cdot M}{(G^k)^x}。这起作用是因为(G^x)^k = (G^k)^x。

但是，存在一个侧通道攻击，其中来自指数A^x的电磁辐射可以泄漏关于私钥x的信息。

为了避免直接执行A^x指数运算，解密的盲变量首先选择一个一致随机值R。

现在，我们计算M=\frac{B\cdot R^x}{(A\cdot R)^x}=\frac{B\cdot R^x}{A^x\cdot R^x}=\frac{B}{A^x}。

请注意，我们现在只使用私钥x对盲值进行指数运算。由于R对攻击者来说是未知的，因此通过监视电磁辐射很难提取有用的信息。

在您链接到的代码的更新版本中，我们使用了x的盲版本。它计算为x'=x+(p-1)r'，其中r'是一个一致随机值。

这意味着我们最终将计算M=\frac{B}{A^{x'}}而不是M=\frac{B}{A^{x}}。

这是因为(p-1)是由组元素(如A )指数生成的组的大小。由于组的循环性质，添加到标量中的组大小的任何倍数(例如私钥x)在幂后都会产生相同的组元素值。

如果我们定义\ell=(p-1)，那么A^x=A^{(x+\ell)}=A^{(x+\ell r')}用于x、A和r'的任何值。(注:这个答案中的所有指数都是\operatorname{mod} p)。

因此，当使用盲值x'而不是x时，结果是相同的，尽管由CPU执行的计算(以及由此产生的电磁辐射)将是不同的。