# Is this Bignum multiplication of 2048 RSA number a Montgomery multiplication?

The below code snippets are some kind of `bignum` multiplications involving 2048bit numbers, possibly in the context of RSA decryption.

• Does any one recognize this pattern?
• Is it maybe some kind of `Montgomery` multiplication (unlikely) ?
• Or some RSA obfuscation that someone recognizes?

There are 2 multiplication loops. I marked them with `loop1` and `loop2`. `loop1` does the partial multiplication and addition I would expect. But how does the second loop make sense mathematically? It uses a seperate vector to multiply with. Does this accumulate into a modulo operation?

I converted the IDA compilation to a more readable representation below, the original is at the end. Can anyone recognize a pattern?

``````struct mod {
int len;
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;
}
``````

Here is the original IDA decompile:

`````` int64 fastcall sub_BC46730(_DWORD *a1, int64 a2, int64 a3, int64 a4)
{
_DWORD *v4; // r9@1
signed __int64 v5; // rdi@1
__int64 v6; // rbp@1
__int64 result; // rax@1
unsigned int v8; // ecx@1
unsigned int v9; // er13@1
__int64 v10; // r10@2
unsigned __int64 v11; // rdi@3
__int64 v12; // r8@3
unsigned __int64 v13; // rax@4
unsigned __int64 v14; // rax@4
__int64 v15; // r14@5
unsigned __int64 v16; // r11@5
__int64 v17; // rax@5
unsigned __int64 v18; // r11@5
__int64 v19; // r8@5
unsigned __int64 v20; // r15@5
signed __int64 v21; // rdi@6
_DWORD *v22; // rcx@6
__int64 v23; // rax@7
unsigned __int64 v24; // rax@7
unsigned __int64 v25; // rax@7
__int64 v26; // rsi@9
unsigned __int64 v27; // rcx@11
unsigned int *v28; // rdi@14
unsigned int v29; // ebx@14
__int64 v30; // [sp+0h] [bp-40h]@2
int v31; // [sp+8h] [bp-38h]@2
int v32; // [sp+Ch] [bp-34h]@2
v4 = a1;
v5 = (signed __int64)(a1 + 2);
v6 = a4;
*(_QWORD *)(v5 - 8) = 0LL;
*(_QWORD *)(v5 + 240) = 0LL;
result = 0LL;
memset(
(void *)(v5 & 0xFFFFFFFFFFFFFFF8LL),
0,
8 * ((unsigned __int64)((unsigned int)v4 - (v5 & 0xFFFFFFF8) + 256) >> 3));
v8 = 0;
v9 = *(_DWORD *)v6;
if ( *(_DWORD *)v6 )
{
v10 = 0LL;
v31 = *(_DWORD *)(v6 + 1284);
v32 = v9 - 1;
v30 = v9 - 1;
do {
v11 = 0LL;
v12 = 0LL;
/* loop1: */
do {
v13 = *(_DWORD *)(a2 + v11) * (unsigned __int64)*(_DWORD *)(a3 + 4 * v10) + v4[v11 / 4] + v12;
v4[v11 / 4] = v13;
v11 += 4LL;
v14 = v13 >> 32;
v12 = (unsigned int)v14;
} while ( v11 != 4 * v30 + 4 );
v15 = (unsigned int)v14 + v8;
v16 = v14 + v8;
v17 = *v4;
v18 = v16 >> 32;
v19 = (unsigned int)(v17 * v31);
v20 = (v19 * (unsigned __int64)*(_DWORD *)(v6 + 260) + v17) >> 32;
if ( v9 <= 1 )
goto LABEL_16;
v21 = v6 + 264;
v22 = v4;
/* loop2: */
do
{
v23 = v22[1];
v21 += 4LL;
++v22;
v24 = v23 + v20 + v19 * *(_DWORD *)(v21 - 4);
*(v22 - 1) = v24;
v25 = v24 >> 32;
v20 = (unsigned int)v25;
}
while ( v21 != v6 + 4LL * (v9 - 2) + 268 );
++v10;
v4[v30] = v15 + v25;
v8 = v18 + ((v15 + v25) >> 32);
}
while ( v9 > (unsigned int)v10 );
v26 = 0LL;
if ( !v8 && v32 >= 0 )
{
result = v32;
v28 = &v4[v32];
v29 = *(_DWORD *)(4LL * v32 + v6 + 260);
if ( *v28 < v29 )
return result;
if ( *v28 <= v29 )
LABEL_16:
JUMPOUT(loc_BC46E10);
}
LODWORD(result) = 0;
do
{
v27 = v4[v26] - (unsigned __int64)*(_DWORD *)(v6 + 4 * v26 + 260) - (unsigned int)result;
v4[v26++] = v27;
result = (unsigned int)-HIDWORD(v27);
}
while ( v9 > (unsigned int)v26 );
}
return result;
}
``````
• The way I'd go about solving this would be by thoroughly reverse engineering this attached code. I know, we're in RE.SO so that ought to be a weird answer. I could do that for you, but where's the fun in that?! Voting to close, please ask specific questions showing your effort and describe specific challenged you've encountered. Commented Jun 8, 2018 at 3:18
• @NirIzr: I rephrased it a bit. Commented Jun 8, 2018 at 7:32
• Thanks, it does look better but still feels like "here's a chunk of code, please RE it for me". Decompilation output isn't too good in this case and it may be confusing you. I honestly suggest you go through the process of writing this as C code. You'll see this is hardly as complex as it currently seem. Commented Jun 8, 2018 at 17:45
• @NirIzr: Did like you suggested. Can you spot some mathematical construct? Commented Jun 8, 2018 at 21:29
• @NirIzr: I think I found what it is (see posted answer). It is a CIOS Montgomery implementation. Commented Jun 9, 2018 at 7:10