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
Montgomerymultiplication (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 _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;
}
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;
}
