Jak znaleźć sumę kontrolną tej samej sumy kontrolnej? (pytanie o przesłuchanie w sprawie pracy)

Question

Wymyśl prosty algorytm, który tworzy plik, który zawiera jedynie własną sumę kontrolną.

Załóżmy, że jest to CRC-32, więc ten plik musi mieć 4 bajty.

Answer 1

Może istnieć jakiś inteligentny matematyczny sposób znalezienia go (lub udowodnienia, że ​​nie istnieje), jeśli wiesz, jak działa algorytm.

Ale ponieważ jestem leniwy, a CRC32 ma tylko 2^32 wartości, zmusiłbym go do brutalnej przemocy. Czekając, aż algorytm przejdzie przez wszystkie wartości 2^32, skorzystam z Google i przepełnienia stosu, aby sprawdzić, czy ktoś ma na to rozwiązanie.

W przypadku SHA-1, MD5 i innych mniej lub bardziej bezpiecznych kryptograficznie algorytmów, zostałbym zastraszony przez matematyków, którzy zaprojektowali te algorytmy i po prostu się poddali.

EDYTUJ 1: Brute forsowanie ... Do tej pory znalazłem jeden; CC4FBB6A w kodowaniu big-endian. Wciąż może być ich więcej. Sprawdzam 4 różne kodowania: wielkie litery ASCII i małe litery oraz binarne big-endian i little-endian.

EDYCJA 2: Brutalna siła. Oto wyniki:

CC4FBB6A (big-endian)
FFFFFFFF (big-endian & little-endian)
32F3B737 (wielkie litery ASCII)

kod jest here. Na moim przetaktowanym C2Q6600, który trwa około 1,5 godziny. Teraz program jest jednowątkowy, ale łatwo byłoby go utworzyć wielowątkowo, co dałoby ładną liniową skalowalność.

Answer 2

pozbawiona konkretnych wskazówek Wręcz przeciwnie, będę określić sumę kontrolną danych nieistniejących jako nieistniejącego kontrolnej, więc utworzenie pustego pliku by spełnić ten wymóg.

Inną typową metodą jest ujemna suma kontrolna - tj. Po zapisaniu danych wartość, która powoduje, że suma kontrolna całego pliku (łącznie z sumą kontrolną) wychodzi do zera. W takim przypadku wypiszesz sumę kontrolną równą 0 i wszystko się ułoży.

Answer 3

Oprócz Jerry Coffin i dobrych odpowiedzi Esko Luontola do nietypowego problemu, chciałbym dodać:

Matematycznie szukamy X takie, że f (x) = X, gdzie F jest funkcja sumy kontrolnej, a X to same dane. Ponieważ suma kontrolna ma stały rozmiar, a dane wejściowe, których szukamy, są tego samego rozmiaru, , nie ma gwarancji, że taki X nawet istnieje! Może równie dobrze być, że każda wartość wejściowa o stałym rozmiarze jest skorelowana z inną wartością tego rozmiaru.

EDYCJA: Twoje pytanie nie określa dokładnego sposobu, w jaki suma kontrolna ma być sformatowana w pliku, więc założyłem, że masz na myśli reprezentację bajtową sumy kontrolnej. Kiedy pojawiają się łańcuchy i kodowania oraz sformatowane łańcuchy, wszystko staje się bardziej złożone.

Answer 4

Brutalnie wymuszaj to. CRC-32 podaje ciąg długości 8 zawierający cyfry i litery A-F (innymi słowy, jest to liczba szesnastkowa). Wypróbuj każdą kombinację, dając 16 = wiele możliwości.Następnie skopiuj każdą opcję i zobacz, czy daje ci oryginalny ciąg znaków.

Możesz spróbować zoptymalizować go, zakładając, że rozwiązanie wykorzysta każdą postać nie więcej niż dwa lub trzy razy, co może spowodować szybsze zakończenie.

Jeśli masz dostęp do implementacji CRC32, możesz spróbować złamać algorytm i znaleźć rozwiązanie znacznie szybciej, ale nie mam pojęcia, jak to zrobić.

Answer 5

Brutalna siła. To jest Adler32, którego nie wdrożyłem wcześniej, i nie zawracałem sobie głowy testowaniem, więc jest całkiem prawdopodobne, że go pomieszałem. Nie spodziewałbym się jednak, że poprawiona wersja będzie działać znacznie wolniej, chyba że zrobię coś kolosalnie nie tak.

ta zakłada, że ​​wartość sumy kontrolnej 32bit są zapisywane w pliku little-endian (nie mogę znaleźć punkt stały z nim grubokońcej):

#include <iostream> 
#include <stdint.h> 
#include <iomanip> 

const int modulus = 65521; 

void checkAllAdlers(uint32_t sofar, int depth, uint32_t a, uint32_t b) { 
    if (depth == 4) { 
     if ((b << 16) + a == sofar) { 
      std::cout << "Got a fixed point: 0x" << 
       std::hex << std::setw(8) << std::setfill('0') << 
       sofar << "\n"; 
     } 
     return; 
    } 
    for (uint32_t i = 0; i < 256; ++i) { 
     uint32_t newa = a + i; 
     if (newa >= modulus) newa -= modulus; 
     uint32_t newb = b + a; 
     if (newb >= modulus) newb -= modulus; 

     checkAllAdlers(sofar + (i << (depth*8)), depth + 1, newa, newb); 
    } 
    return; 
} 

int main() { 
    checkAllAdlers(0, 0, 1, 0); 
} 

wyjściowa:

$ g++  adler32fp.cpp -o adler32fp -O3 && time ./adler32fp 
Got a fixed point: 0x03fb01fe 

real 0m31.215s 
user 0m30.326s 
sys  0m0.015s 

[Edytuj: naprawiono już kilka błędów, nie mam pewności co do poprawności tego kodu ;-) W każdym razie, masz pomysł: 32-bitowa suma kontrolna, która wykorzystuje każdy bajt danych wejściowych tylko raz, jest bardzo tania w przypadku brutalnej siły. Sumy kontrolne są zwykle zaprojektowane do szybkiego obliczania, podczas gdy skróty są zwykle znacznie wolniejsze, chociaż mają powierzchownie podobne efekty. Jeśli twoja suma kontrolna to "2 rundy Adler32" (co oznacza, że ​​docelowa suma kontrolna była wynikiem obliczenia sumy kontrolnej, a następnie obliczenia sumy kontrolnej tej sumy kontrolnej) to moje rekursywne podejście nie pomogłoby tak bardzo, że proporcjonalnie mniej w wspólne między wejściami z wspólnym przedrostkiem. MD5 ma 4 rundy, SHA-512 ma 80.]