एक ही चेकसम के चेकसम को कैसे ढूंढें? (नौकरी साक्षात्कार प्रश्न)

Question

एक साधारण एल्गोरिदम तैयार करें जो एक फ़ाइल बनाता है जिसमें इसके स्वयं के चेकसम के अलावा कुछ भी नहीं है।

मान लें कि यह सीआरसी -32 है, इसलिए यह फ़ाइल 4 बाइट लंबी होनी चाहिए।

Answer 1

अगर आप जानते हैं कि एल्गोरिदम कैसे काम करता है तो इसे खोजने का कुछ स्मार्ट गणितीय तरीका हो सकता है (या यह साबित कर रहा है कि कोई भी मौजूद नहीं है)।

लेकिन चूंकि मैं आलसी हूं और सीआरसी 32 में केवल 2^32 मूल्य हैं, मैं इसे बल दूंगा। एल्गोरिदम को सभी 2^32 मानों के माध्यम से जाने का इंतजार करते समय, मैं यह जानने के लिए Google और स्टैक ओवरफ़्लो का उपयोग करूंगा कि किसी के पास इसका समाधान है या नहीं।

एसएचए -1, एमडी 5 और अन्य कम या कम क्रिप्टोग्राफिक रूप से सुरक्षित एल्गोरिदम के मामले में, मैं उन गणितज्ञों से डरता हूं जिन्होंने उन एल्गोरिदम तैयार किए और बस छोड़ दिया।

संपादित करें 1: ब्रूट फोर्सिंग ... अब तक मुझे एक मिला है; बड़े-एंडियन एन्कोडिंग में सीसी 4 एफबीबी 6 ए। अभी भी और भी हो सकता है। मैं 4 अलग-अलग एन्कोडिंग की जांच कर रहा हूं: एएससीआईआई अपरकेस और लोअरकेस, और बाइनरी बिग एंडियन और थोड़ा-एंडियन।

संपादित 2: ब्रूट फोर्स किया गया।

CC4FBB6A (बड़े endian)
FFFFFFFF (बड़े endian & थोड़ा-endian)
32F3B737 (अपरकेस ASCII)

कोड here है: यहाँ के परिणाम हैं। मेरे overclocked C2Q6600 पर चलाने के लिए लगभग 1.5 घंटे लगते हैं। अब वह प्रोग्राम सिंगल-थ्रेडेड है, लेकिन इसे बहु-थ्रेडेड बनाना आसान होगा, जो एक अच्छी रैखिक स्केलेबिलिटी देगा।

Answer 2

इसके विपरीत किसी भी विशिष्ट मार्गदर्शन की कमी, मैं बिना किसी जांच वाले डेटा के चेकसम को परिभाषित करता हूं, इसलिए एक खाली फ़ाइल बनाने से आवश्यकता पूरी हो जाएगी। जो कि डेटा के बाद आप शून्य करने के लिए बाहर आ एक मूल्य है कि (चेकसम सहित) पूरी फ़ाइल के चेकसम बनाता बारे में -

एक और ठेठ विधि एक नकारात्मक चेकसम है। इस मामले में, आप 0 का चेकसम लिखते हैं, और यह सब काम करता है।

Answer 3

जेरी ताबूत और एक असामान्य समस्या का Esko Luontola के अच्छे जवाब के अलावा, मैं जोड़ना चाहते हैं:

गणित के अनुसार, हम एक्स के लिए देख रहे हैं इस तरह के एफ (एक्स) = एक्स, जहां एफ है कि चेकसम फ़ंक्शन, और एक्स डेटा ही है। चूंकि चेकसम का आउटपुट निश्चित आकार का है, और जिस इनपुट को हम ढूंढ रहे हैं वह उसी आकार का है, इस बात की कोई गारंटी नहीं है कि ऐसा एक्स भी मौजूद है! यह बहुत अच्छी तरह से हो सकता है कि निश्चित आकार के प्रत्येक इनपुट मूल्य उस आकार के एक अलग मूल्य से संबंधित है।

संपादित करें: आपके प्रश्न ने फ़ाइल के भीतर चेकसम को स्वरूपित करने का सटीक तरीका निर्दिष्ट नहीं किया है, इसलिए मुझे लगता है कि आप चेकसम के बाइट-प्रस्तुति का मतलब मानते हैं। जब तार और एन्कोडिंग और स्वरूपित-तार खेलेंगे, चीजें अधिक जटिल हो जाएंगी।

Answer 4

बलपूर्वक बल दें। सीआरसी -32 आपको लंबाई 8 की एक स्ट्रिंग देता है जिसमें ए-एफ के अंक और अक्षर होते हैं (दूसरे शब्दों में, यह एक हेक्साडेसिमल संख्या है)। प्रत्येक संयोजन का प्रयास करें, आपको 16 = कई संभावनाएं दें।फिर प्रत्येक संभावना हैश देखें और देखें कि क्या यह आपको मूल स्ट्रिंग देता है।

आप यह मानकर इसे अनुकूलित करने का प्रयास कर सकते हैं कि समाधान प्रत्येक चरित्र का उपयोग दो या तीन बार से अधिक नहीं करेगा, इससे यह तेज़ी से खत्म हो सकता है।

यदि आपके पास सीआरसी 32 कार्यान्वयन की पहुंच है, तो आप एल्गोरिदम को तोड़ने और समाधान को तेज़ी से ढूंढने का प्रयास कर सकते हैं, लेकिन मुझे नहीं पता कि आप यह कैसे करेंगे।

Answer 5

ब्रूट फोर्स। यह एडलर 32 है, जिसे मैंने पहले लागू नहीं किया है, और परीक्षण को परेशान नहीं किया है, इसलिए यह काफी संभावना है कि मैंने इसे गड़बड़ कर दिया है। मैं एक सही संस्करण को धीमा चलाने की अपेक्षा नहीं करता, हालांकि, जब तक मैंने कुछ गलत गलत नहीं किया है।

मतलब यह है कि 32 बिट चेकसम मान फ़ाइल थोड़ा-endian करने के लिए लिखा है (मैं नहीं एक नियत बिन्दु इसके साथ बड़े 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); 
} 

आउटपुट:

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

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

[संपादित करें: पहले से तय की गई कई बग, मुझे इस कोड की शुद्धता में जो कुछ भी विश्वास नहीं है ;-) वैसे भी, आपको यह विचार मिलता है: 32 बिट चेकसम जो इनपुट के प्रत्येक बाइट का उपयोग करता है केवल एक बार ब्रूट फोर्स के लिए बहुत सस्ता है। चेकसम आमतौर पर गणना करने के लिए तेज़ होने के लिए डिज़ाइन किए जाते हैं, जबकि हैश आमतौर पर बहुत धीमे होते हैं, भले ही उनके पास सतही रूप से समान प्रभाव हों। यदि आपका चेकसम "एडलर 32 के 2 राउंड" था (जिसका अर्थ है कि लक्ष्य चेकसम चेकसम की गणना करने और फिर उस चेकसम के चेकसम की गणना करने का परिणाम था) तो मेरा रिकर्सिव दृष्टिकोण इतना मदद नहीं करेगा, वहां आनुपातिक रूप से कम होगा एक सामान्य उपसर्ग के साथ इनपुट के बीच आम है। एमडी 5 में 4 राउंड हैं, एसएचए -512 में 80 है।]