Реверсинг И Побит

Question

Вот следующий алгоритм:

int encryption(int a, int b) {
    short int c, c2;
    uint8_t d;

    c = a ^ b;
    c2 = c;

    d = 0;
    while(c) {
        c &= c - 1;
        d++;
    }

    return d;
}

Как найти переменные a и b, которые я должен отправить в эту функцию, чтобы определить выходное значение d?

Другими словами, как я могу изменить алгоритм, скажем, если я хочу d = 11?

Answer 1

Это:

while(c) {
    c &= c - 1;
    d++;
}

подсчитывает количество 1-бит в c. Так, например, если c = 10110, d будет 3.

Это:

c = a ^ b;

Делает эксклюзивным или между a и b. Это означает, что все 1-биты, которые совместно используют одну и ту же позицию в a и b, будут равны нулю, а все позиции, имеющие разные значения в a и b, станут равными 1. Например:

101110 ^
011010
========
110100

Таким образом, в основном алгоритм находит число 1-бит в a ^ b. Чтобы заставить его выводить определенное значение, просто наберите a = 0, а затем b = number with d 1-bits.

Чтобы получить число с d 1-битами, рассмотрим b = (2 to the power of d) - 1.

Так что если вы хотите d = 11, то a = 0 и b = (2 to the power of 11) - 1 = 2048 - 1 = 2047.

Для эффективного вычисления 2 до определенной мощности программно используйте следующую формулу:

2 to the power of k == 1 << k

Итак, в основном: encryption(a, b) == d if a = 0 and b = (1 << d) - 1.

Answer 2

d - это просто число «1» битов в c, см. http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan.

Следовательно, вам просто нужно найти a и b, чтобы их значение побитового XOR имело ровно 11 битов, например, a = 0 и b = 2047.

(Это не шифрование. Это очень слабое одностороннее хеширование. Шифрование должно обеспечивать способ возврата к исходному значению (дешифрование).)

Answer 3

Я вижу, что он считает SET бит в XOR b?

Хорошо, тогда, скажем, a == 0, b == 4095.