A ^ ( (A >> 2) + (A << 5) + C ) == B
BがconstでCが変数の場合、Aを見つける方法は? (C で解決策がない場合は変更できます)
A は DWORD、B は DWORD、C は BYTE != 0
Edit1: GalacticJello の回答の後、別の質問があります:ループなしでそれを行う方法はありますか (式を単純化します)?
なぜこれが必要なのですか?
unsigned int X(const char* const in) { //strlen(in) is always < 127
unsigned int result = 0x12345678; //just for an example
for(int i = 0; in[i] != 0; ++i)
result ^= (result >> 2) + (result << 5) + in[i];
return result;
}
現在、ランダムな C を生成してから A を検索するループがあります ([A の] ランダムな値を生成するループを使用して A を検索し、上記の式が true かどうかを確認します)。
Edit2:これは、衝突を検索するための現在のコードであり、現在テストしています..
#include <stdio.h>
#include <conio.h>
using namespace std;
unsigned int originalHash(const char* const in) {
unsigned int result = 0x12345678;
for(int i = 0; in[i] != 0; ++i) {
result = result ^ ((result >> 2) + (result << 5) + in[i]);
}
return result;
}
//A ^ ( (A >> 2) + (A << 5) + C ) == B
bool findSolutions(unsigned int inHash, char* _C, unsigned int* _A) { //Starts searching from *A and *C and writes there values on success.
unsigned int C = *_C;
if(C == 0) ++C;
unsigned int A = *_A;
for(C; C < 256; ++C) {
for(A; A < 0xFFFFFFFF; ++A) {
if((A ^ ( (A >> 2) + (A << 5) + C )) == inHash) {
*_C = C;
*_A = A;
return true;
}
}
A = 0;
}
return false;
}
bool findCollisions(unsigned int inHash, char* szOutStr) {
const unsigned int REQ_HASH = 0x12345678;
unsigned int prevHash = 0;
int curChar = 0;
do {
printf("Loop Begin:\tI = %i | H = %08x | rH = %08x\n", curChar, inHash, REQ_HASH);
if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) {
printf("Unable to find solutions for %08x\n", inHash);
if(curChar == 0) return false;
--curChar;
continue;
}
if(prevHash == REQ_HASH) {
szOutStr[curChar] = 0;
return true;
}
printf("Found solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash);
char firstSolutionC = szOutStr[curChar];
unsigned int firstSolutionA = prevHash;
printf("Trying to find alternative solutions..\n");
do {
if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) {
printf("Alternative solution not found!\n");
break;
}
printf("Alternative solution found [%s valid]:\tC = %02x (%c) | A = %08x\n", prevHash == REQ_HASH ? "" : "not", szOutStr[curChar], szOutStr[curChar], prevHash);
if(prevHash == REQ_HASH) {
szOutStr[curChar] = 0;
return true;
}
++prevHash;
} while(true);
szOutStr[curChar] = firstSolutionC;
prevHash = firstSolutionA;
printf("Using first solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash);
++curChar;
inHash = prevHash;
} while(curChar < 127);
return false;
}
int main(void) {
char mask[] = "hQh";
DWORD original = originalHash(mask);
printf("%s == %08x\n", mask, original);
char out[128];
memset(out, 0, sizeof out);
if(findCollisions(original, out))
printf("%08x == %s\n", original, out);
else
printf("Unable to find collisions\n");
getch();
return 0;
}