Làm thế nào để tìm một tổng kiểm tra của cùng một tổng kiểm tra? (câu hỏi phỏng vấn xin việc)

Question

Xây dựng một thuật toán đơn giản tạo ra một tệp không chứa gì ngoài kiểm tra của chính nó.

Giả sử đó là CRC-32, vì vậy tệp này phải dài 4 byte.

Answer 1

Có thể có một số cách toán học thông minh để tìm ra (hoặc chứng minh rằng không tồn tại), nếu bạn biết cách hoạt động của thuật toán.

Nhưng vì tôi lười biếng và CRC32 chỉ có 2^32 giá trị, tôi sẽ bạo lực. Trong khi chờ thuật toán đi qua tất cả 2^32 giá trị, tôi sẽ sử dụng Google và Stack Overflow để tìm xem liệu ai đó có giải pháp cho nó hay không.

Trong trường hợp SHA-1, MD5 và các thuật toán bảo mật mã hóa khác ít hơn, tôi sẽ bị đe dọa bởi các nhà toán học đã thiết kế các thuật toán đó và từ bỏ.

CHỈNH SỬA 1: Đay buộc ... Điều này đến nay tôi đã tìm thấy một; CC4FBB6A trong mã hóa lớn. Có thể vẫn còn nhiều hơn nữa. Tôi đang kiểm tra 4 mã hóa khác nhau: chữ hoa và chữ thường ASCII, và nhị phân lớn và cuối nhỏ.

CHỈNH SỬA 2: Hoàn thành lực lượng vũ phu. Dưới đây là kết quả:

CC4FBB6A (lớn-endian)
FFFFFFFF (lớn-endian & ít về cuối nhỏ)
32F3B737 (chữ hoa ASCII)

Mã này là here. Trên C2Q6600 ép xung của tôi mất khoảng 1,5 giờ để chạy. Bây giờ chương trình đó là đơn luồng, nhưng nó sẽ dễ dàng để làm cho nó đa luồng, mà sẽ cung cấp cho một khả năng mở rộng tuyến tính tốt đẹp.

Answer 2

Thiếu bất kỳ hướng dẫn cụ thể nào, tôi xác định tổng kiểm tra dữ liệu không tồn tại dưới dạng kiểm tra không tồn tại, vì vậy việc tạo tệp trống sẽ đáp ứng yêu cầu.

Một phương pháp điển hình khác là kiểm tra âm - tức là sau khi dữ liệu bạn viết một giá trị làm cho tổng kiểm tra của toàn bộ tệp (bao gồm cả tổng kiểm tra) xuất hiện bằng không. Trong trường hợp này, bạn viết tổng kiểm tra là 0 và tất cả đều hoạt động.

Answer 3

Ngoài Jerry Coffin và câu trả lời tốt Esko Luontola của một vấn đề không bình thường, tôi muốn thêm:

Về mặt toán học, chúng tôi đang tìm kiếm X như vậy F (X) = X, trong đó F là chức năng kiểm tra, và X là chính dữ liệu. Vì đầu ra của tổng kiểm tra có kích thước cố định và đầu vào chúng tôi đang tìm kiếm có cùng kích thước, không có gì đảm bảo rằng X thậm chí tồn tại! Rất có thể là mọi giá trị đầu vào của kích thước cố định đều tương quan với một giá trị khác của kích thước đó.

CHỈNH SỬA: Câu hỏi của bạn không chỉ định chính xác cách kiểm tra được định dạng trong tệp, vì vậy tôi cho rằng bạn có nghĩa là biểu diễn byte của tổng kiểm tra. Khi các chuỗi và mã hóa và chuỗi định dạng đến để chơi, mọi thứ trở nên phức tạp hơn.

Answer 4

Đậy sức mạnh. CRC-32 cung cấp cho bạn một chuỗi có chiều dài 8 chứa chữ số và chữ cái của A-F (nói cách khác, đó là một số thập lục phân). Hãy thử mọi kết hợp, cung cấp cho bạn 16 = nhiều khả năng.Sau đó, băm từng khả năng và xem nó có cung cấp cho bạn chuỗi gốc hay không.

Bạn có thể thử tối ưu hóa bằng cách giả sử giải pháp sẽ sử dụng từng ký tự không quá hai hoặc ba lần, điều này có thể làm cho nó hoàn thành nhanh hơn.

Nếu bạn có quyền truy cập vào triển khai CRC32, bạn cũng có thể thử giải thuật toán và tìm giải pháp nhanh hơn nhiều, nhưng tôi không biết bạn sẽ làm như thế nào.

Answer 5

Lực lượng vũ phu. Đây là Adler32, mà tôi chưa từng thực hiện trước đây, và không bận tâm thử nghiệm, vì vậy nó khá có khả năng tôi đã làm hỏng nó lên. Tôi sẽ không mong đợi một phiên bản sửa chữa để chạy chậm hơn đáng kể, mặc dù, trừ khi tôi đã làm một cái gì đó khổng lồ sai.

này giả định rằng giá trị 32bit checksum được ghi vào tập tin ít về cuối nhỏ (tôi không tìm thấy một điểm cố định với nó lớn-endian):

#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); 
} 

Output:

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

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

[Chỉnh sửa: một số lỗi đã được sửa, tôi không có sự tự tin gì về tính chính xác của mã này ;-) Dù sao, bạn có ý tưởng: một kiểm tra 32 bit sử dụng mỗi byte đầu vào chỉ một lần rất rẻ. Checksums thường được thiết kế để nhanh chóng tính toán, trong khi băm thường chậm hơn nhiều, mặc dù chúng có tác dụng tương tự bề ngoài. Nếu checksum của bạn là "2 vòng của Adler32" (có nghĩa là tổng kiểm tra đích là kết quả của việc tính toán tổng kiểm tra và sau đó tính toán tổng kiểm tra của checksum đó) thì cách tiếp cận đệ quy của tôi sẽ không giúp được gì nhiều, phổ biến giữa các đầu vào với tiền tố chung. MD5 có 4 vòng, SHA-512 có 80.]