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
uint8_t superlong_add(uint16_t target[0x20], uint16_t other[0x20]);
// 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"
tmp = superlong_add(current, secret);
current[32] += tmp;
}
}
flag = current[31] != 0;
}
// advance pointer
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:
- Is this some commonly known algorithm or something "home-made"?
- 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?
- 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)