以下代码段是涉及2048位数字的某种bignum乘法，可能是在RSA解密的情况下。


有人能识别这种模式吗？
（不是）可能是某种Montgomery乘法吗？
还是有人认识到一些RSA混淆？

有2个乘法循环。我用loop1和loop2标记了它们。 loop1做我期望的部分乘法和加法。但是第二个循环在数学上如何有意义？它使用单独的向量与之相乘。这会累加成模运算吗？

我将IDA汇编转换为下面更易读的表示，
在最后。任何人都可以识别出一个模式吗？

struct mod {
  int len;
  uint32_t _pad0[64]; /* 4 */
  uint32_t r[64];     /* 4 + (256*1) :offset-260  */
  uint32_t _pad2[64]; /* 4 + (256*2) :offset-516  */
  uint32_t _pad3[64]; /* 4 + (256*3) :offset-772  */
  uint32_t _pad4[64]; /* 4 + (256*4) :offset-1028 */
  int fac;            /* 4 + (256*5) :offset-1284 */
};

#define align8(c) (((uint64_t)(c)) & (~0x7ULL))

int64_t some_kind_of_mult(int32_t *acc , int32_t *a , int32_t *b, struct mod *n)
{
  int i0, i1, i2, j0 ;
  uint32_t top;
  uint64_t c0 = 0, c1 = 0, v0, v1, v2, v3, c01, c01_h;
  intt64_t m1, res, topc0 = 0;

  memset(acc,0,256);
  res = 0;
  l = n->len;

  if ( !l )
    return res;

  top = topc0 = 0;

  for (i0 = 0; i0 < l; i0++)
  {
      /* loop1: multiply a[0..l] with partial b[i0], accumulate resule in acc[0..l] */
      for (c1=0, i1=0; i1 < l; i1++)
      {
          v1 = ((uint64_t)a[i1] * (uint64_t)b[i0]) + acc[i1] + c1;
          acc[i1] = v1;
          c1 = v1 >> 32;
      }

      top = (uint32_t)c1 + topc0;
      c01 = c1 + topc0;

      m1 = (uint32_t)(acc[0] * n->fac);
      c2 = (m1 * (uint64_t)(n->r[0]) + acc[0]) >> 32;

      /* loop2: do some acc[0..l] postprocessing involving some acc[i2-1] = .. acc[i2] ... calculcation */
      for (i2 = 1; i2 < l; i2++)
      {
          v2 = acc[i2] + c2 + (m1 * n->r[i2]);
          acc[i2-1] = v2;
          c2 = (v2 >> 32);
      }

      acc[l-1] = top + c2;
      topc0 = (c01 >> 32) + ((top + c2) >> 32);
  }

  if ( !topc0 && l-1 >= 0 )
  {
      res = l-1;
      if ( acc[l-1] < n->r[l-1] )
        /* possible error in IDA function */
        return res;
      if ( *v28 <= v29 )
        /* possible error in IDA function */
        JUMPOUT(loc_BC46E10);
  }

  res &= 0xffffffff00000000ULL;;
  /* loop3: some final substraction on acc[0-l] */
  for (j0 = 0; j0 < l; j0++)
  {
      v3 = acc[j0] - (uint64_t)n->r[j0] - (uint32_t)res;
      acc[j0] = v3;
      res = -(v3 >> 32);
  }

  return res;
}


这是原始的IDA反编译：

评论

我要解决此问题的方法将是对随附的代码进行完全反向工程。我知道，我们在RE.SO中，所以应该是一个奇怪的答案。我可以为您做到这一点，但是那有什么乐趣呢？投票结束，请问一些具体问题以显示您的努力并描述遇到的具体挑战。
@NirIzr：我改了一下。
谢谢，它看起来确实更好，但是仍然感觉像“这里有很多代码，请帮我”。在这种情况下，反编译输出效果不是很好，这可能会使您感到困惑。老实说，我建议您完成将其编写为C代码的过程。您会发现这几乎不像现在看起来那么复杂。
@NirIzr：像你建议的那样。你能发现一些数学构造吗？
@NirIzr：我想我找到了它（请参阅发布的答案）。这是CIOS Montgomery的实现。

#1 楼

该结构似乎类似于Montgomery CIOS实现。



来自Researchgate的文章：粗集成操作数扫描
https://www.microsoft.com/zh-cn/research/wp-content/uploads/1996/01/j37acmon.pdf

评论

您可以添加一些链接/参考吗？例如屏幕截图来自哪里？

–伊戈尔·斯科钦斯基♦
18年6月9日13:45
@IgorSkochinsky：添加了参考。

– Konrad Eisele
18年6月9日14:45