# Need to identify cryptographic algorithm [closed]

I have a binary code which decrypts some 64-byte data chunks.

There is a decryption key which is always static, and there is a code which does actual decryption. What I need is to find out which algorihtm does it use (probably it is something common enough which I just failed to identify) and find how to encrypt data for this code to decrypt.

The code treats both data chunks (512-bit data and 512-bit key) as series of 32 little-endian 16-bit integers, with least significant being the first one, and handles them as such. There are functions which perform addition, substraction, comparison, division and multiplication on those numbers; I named these functions superlong_add, superlong_sub etc.

Actually, both data and key are byte-inversed before processing, and then the result is byte-reversed back. So they are probably stored as big-endian, but converted to little-endian for processing. Not sure if it is useful.

Here is the actual decryption code. It is in C, but might be somewhat incorrect because it is just hand-written after disassembling binary code:

// Substract value from target, result is left in target.
void superlong_sub(uint16_t target[0x20], uint16_t value[0x20]);

// Return 1 if a > b, -1 if a < b, 0 if they are equal
int8_t superlong_compare(uint16_t a[0x20], uint16_t b[0x20]);

// Add other to target, place result in target.
// Return 1 if there was overflow, 0 otherwise

// Multiply other by small, and substract the result from target.
// Return 1 if overflow happened, 0 otherwise.
uint8_t superlong_mulsub(uint16_t target[0x20], uint16_t other[0x20], uint16_t small);

// Multiply a by b, place result to target
void superlong_multiply(uint16_t target[0x40], uint16_t a[0x20], uint16_t b[0x20]);

// This is some "complex" operation which forms the main body of algorithm.
// It takes a buffer and a key, and applies some calculations to the buffer,
// without changing key in any way.
void decode5(uint16_t buf[0x40], uint16_t secret[0x20]) {
// pointer starts from the middle of the big buffer,
// and then is moved back by one position on each iteration
// until it reaches the beginning of the big buffer.
uint16_t* current = buf + (0x40/2); // middle
bool flag = false;

for(uint8_t i = 0x21; i>0; i--) {
if(!flag) {
if(current[31] != 0) {
if(superlong_compare(current, secret) >= 0) {
superlong_sub(current, secret);
flag = current[31] != 0;
} else {
flag = true;
}
}
} else {
// Take two most significant values from current buffer
// to form one 32-bit number.
// It is safe to access current[32], because this code will only be achieved
// after we advanced the pointer at least once.
uint32_t fc = current[32] << 16 | current[31];
// divide by secret's most significant value (it is always 0xd015 in my case)
fc = fc / secret[31];
if(fc > 0xffff) {
fc = 0xffff;
}
if(superlong_mulsub(current, secret, fc) == 0) {
// no overflow in mulsub
uint32_t tmp = superlong_add(current, secret); // 1 if overflow else 0
tmp += current[32];
current[32] = tmp;
if(tmp & (1<<16) != 0) {
// most likely "superlong_add gave overflow and f10[32] was 0xffff"
current[32] += tmp;
}
}
flag = current[31] != 0;
}

current --;
}
}

// data is the encrypted data, secret is the decryption key.
// After this function exits, data buffer contains decrypted data.
void decrypt(uint16_t data[32], const uint16_t secret[32]) {
uint16_t buffer[32];
uint16_t bigbuf[64];

memcpy(buffer, data, sizeof(data));

for(int i=0x10; i>0; i--) {
superlong_multiply(bigbuf, buffer, buffer);
decode5(bigbuf, secret);
memcpy(buffer, bigbuf, sizeof(buffer));
}
superlong_multiply(bigbuf, buffer, data);
decode5(bigbuf, secret);
memcpy(data, bigbuf, sizeof(data));
}


So my questions are:

1. Is this some commonly known algorithm or something "home-made"?
2. Does it look like a symmetric or asymmetric encryption? I.e. can I use the same key for encryption or shall it be some different key?
3. How would I encrypt data for this algorithm to decrypt?

Thanks.

UPD This turned out to be a plain good old RSA.

The decode5 function is a modulus calculation (aka superlong_mod).

The decrypt function can look like this in Python:

def decrypt(message, N):
tmp = message
# calculate message ** 65536 mod N
for _ in range(16):
tmp = (tmp ** 2) % N
# or: tmp = pow(tmp, 2, N)
# and convert it to message ** 65537 mod N
return tmp * message % N


And this is absolutely equivalent to the well known

return pow(c, 65537, N)


It looks homemade, like it does a minimum of transposition of characters and a lot of math to obfuscate the buffers.

This: for(int i=0x10; i>0; i++) { ... }

I do not believe that will do what you think it will do.

• Huh, you're right regarding ++. Obviously that is --, this is just a typo of mine. Will edit. – MarSoft Nov 14 '20 at 23:13
• Just a good old RSA with e value of 65537, as it turned out... – MarSoft Nov 16 '20 at 22:49