Анти-дайджест операция над строкой всегда возвращает одно и то же значение
Я ищу какой-нибудь способ «переварить» строку, но всегда возвращаю одно и то же 32 (или 64) байтовое длинное значение (в виде шестнадцатеричной строки или простых символов). Что-то вроде следующего кода делает:
std::string digest(const std::string& input)
{
std::string result = "";
// do something with the input string, update result accordingly
return result;
}
и немного больше деталей: я хочу в точности противоположность тому, что делает классическая дайджест-функция, а именно то, что для каждой отдельной строки она возвращает различное, но всегда одинаковое (от 1 до 1) значение. Мне нужна функция, которая для каждой строки каждый раз возвращает одно и то же значение (от n до 1).
Очевидно, что «простые» решения так же возвращают одну и ту же константу result каждый раз не считается решением 🙂 Код должен на самом деле переварить входную строку и создать result в результате операции.
И пример:
digest ("fox") == digest ("whale")
должно быть правдой.
Или математически говоря:
для ∀ a и b, если a! = b => digest (a) == digest (b). Вот почему я назвал это анти-дайджест.
Решение
Длинная математическая демонстрация
Ваше требование:
a!=b => digest(a)==digest(b)
Давайте возьмем другое сообщение, любое другое сообщение c, и предположим, что оно отличается от a и b:
a!=c => digest(a)==digest(c)
b!=c => digest(b)==digest(c)
Из этого вы видите, что дайджест будет постоянным для любого c, если он не равен a или b.
Теперь возьмите другое сообщение x, каким бы оно ни было:
c!=x => digest(c)==digest(x)
В отличие от этого, это эквивалентно:
digest(x)!=digest(c) => c==x
Итак, предположим, что будет х с дайджестом, отличным от постоянного дайджеста (с). У нас есть:
digest(x)!=digest(c) and digest(x)!=digest(a)
=> x==c and x==a
=> c==a
=> digest(c)!=digest(a)
Но это противоречит первоначальной гипотезе о a, c, digest (a) и digest (c), поэтому такого x не может быть. Таким образом, вы можете сделать вывод что ваш дайджест ДОЛЖЕН БЫТЬ строго постоянной функцией.
Теперь предположим, что ваша функция не будет постоянной:
digest(x)!=digest(a) => x==a
но если digest является функцией, она всегда будет возвращать один и тот же результат для одного и того же ввода, что означает, что x == a => digest (x) == digest (a). Это показывает, что есть нет другого решения, чем постоянная функция.
Короче и на С ++
Функция возвратит тот же результат для того же параметра, если только нет побочного эффекта (статическая переменная или что-то еще). Ваше требование иметь одинаковый результат для разных значений, но разный результат для одинаковых значений просто невозможно в функции с одним параметром.
Другие решения
Кажется, мне было как-то неясно, чего я хочу добиться …
Во всяком случае, я придумал следующее:
static const size_t DIGEST_SIZE = 32;
std::string antiDigest(const std::string& a)
{
if(a.empty()) { throw "cannot digest empty string"; }
char r[DIGEST_SIZE ] = {0};
int block_size = std::min(DIGEST_SIZE, a.length());
int block_count = 1 + DIGEST_SIZE / a.length();
for(int i=0; i<block_size; i++)
{
int hlp = 0, bc = 0;
while(bc < block_count)
{
int idx = i + bc * block_size;
if(idx >= a.length()) break;
hlp += a[idx];
bc ++;
}
hlp = (int)(hlp << 3) + hlp;
unsigned int hlp2 = 0;
while(hlp)
{
int t = hlp - ((hlp/10) * 10);
hlp2 += t;
hlp /= 10;
}
bc = 0;
while(bc < block_count)
{
int idx = i + bc * block_size;
if(idx >= DIGEST_SIZE) break;
r[idx] = ( (hlp2 / 10) + (hlp2-(hlp2/10)*10)) ;
bc++;
}
}
std::stringstream result;
for(int i=0; i<DIGEST_SIZE; i++)
{
result << int_to_hex(r[i]) ;
}
return result.str();
}
На идеоне: http://ideone.com/t4dibL
Очевидно, что это может быть еще более запутано с заменой математических операций с побитовыми операциями, но для доказательства концепции это делает.
detector