मैं एक String को एक हैशेड ऑब्जेक्ट में हैश करना चाहता हूं जिसमें अल्फा-न्यूमेरिक मानों के बजाय आउटपुट के रूप में कुछ संख्यात्मक मान NSNumber/Int हैं।

समस्या यह है कि स्विफ्ट और कुछ तृतीय पक्ष पुस्तकालय के माध्यम से खुदाई करने के बाद, मुझे कोई पुस्तकालय नहीं मिल रहा है जो हमारी आवश्यकता को पूरा करता है।

मैं एक चैट एसडीके पर काम कर रहा हूं और यह NSNumber/Int को चैट संदेश और वार्तालाप संदेश को सह-संबंधित करने के लिए अद्वितीय पहचानकर्ता के रूप में लेता है।

मेरी कंपनी की मांग डेटाबेस पर किसी भी अतिरिक्त फ़ील्ड को स्टोर करने या स्कीमा को बदलने की नहीं है जो हमारे पास जटिल चीज है।

मेरी टीम के साथ आया एक साफ समाधान किसी प्रकार का हैशेड फ़ंक्शन था जो संख्या उत्पन्न करता है।

func userIdToConversationNumber(id:String) -> NSNumber

हम उस फ़ंक्शन का उपयोग String को NSNumber/Int में बदलने के लिए कर सकते हैं। यह Int उस फलन द्वारा उत्पन्न होना चाहिए और टकराने की संभावना नगण्य होनी चाहिए। किसी भी दृष्टिकोण पर कोई सुझाव।

-1
user256419 28 फरवरी 2019, 19:55

2 जवाब

सबसे बढ़िया उत्तर

आपको जो महत्वपूर्ण गणना करने की आवश्यकता है वह जन्मदिन बाध्य है। मेरी पसंदीदा तालिका विकिपीडिया में से एक है, और जब मैं इस तरह के सिस्टम डिजाइन करना।

तालिका व्यक्त करती है कि टक्कर की एक निश्चित अपेक्षा होने से पहले आप किसी दिए गए हैश आकार के लिए कितने आइटम हैश कर सकते हैं। यह पूरी तरह से एकसमान हैश पर आधारित है, जिसका एक क्रिप्टोग्राफिक हैश एक निकट सन्निकटन है।

तो एक 64-बिट पूर्णांक के लिए, 6M तत्वों को हैश करने के बाद, इस सूची में कहीं भी एकल टक्कर होने की एक लाख संभावना है। 20M तत्वों को हैश करने के बाद, एक-एक-हजार मौका है कि एक ही टक्कर थी। और 5 अरब तत्वों के बाद, आपको टक्कर (50% मौका) पर दांव लगाना चाहिए।

तो यह सब नीचे आता है कि आप कितने तत्वों को हैश करने की योजना बना रहे हैं और टक्कर होने पर यह कितना बुरा है (क्या यह सुरक्षा समस्या पैदा करेगा? क्या आप इसका पता लगा सकते हैं? क्या आप इसके बारे में कुछ भी कर सकते हैं जैसे इनपुट डेटा बदलना?), और निश्चित रूप से दी गई समस्या के लिए आप कितना जोखिम उठाने को तैयार हैं।

व्यक्तिगत रूप से, मैं इन चीजों के लिए 1 लाख में एक प्रकार का व्यक्ति हूं, हालांकि मुझे कई बार एक हजार में नीचे जाने के लिए आश्वस्त किया गया है। (फिर से, यह किसी दिए गए तत्व के टकराने का 1:1000 मौका नहीं है; यह भयानक होगा। हैशिंग के बाद बिल्कुल टक्कर होने की यह 1:1000 संभावना है कुछ तत्वों की संख्या।) मैं उन स्थितियों में 1 मिलियन में स्वीकार नहीं करूंगा जहां एक हमलावर आपके लिए हैश करने के लिए मनमानी चीजें (मनमानी आकार की) तैयार कर सकता है। लेकिन मैं सीमित लंबाई के संरचित डेटा (ईमेल पते, यूआरएल) के लिए इसके साथ बहुत सहज हूं।

यदि ये नंबर आपके लिए काम करते हैं, तो आप जो चाहते हैं वह हैश है जो अपने सभी बिट्स में अत्यधिक समान है। और वह एक SHA हैश है। मैं एक SHA-2 (जैसे SHA-256) का उपयोग करूंगा क्योंकि आपको हमेशा SHA-2 का उपयोग करना चाहिए जब तक कि आपके पास कोई अच्छा कारण न हो। चूंकि SHA-2 के सभी बिट एक-दूसरे से स्वतंत्र हैं (या कम से कम यही इसका इरादा है), आप इसके किसी भी बिट को बनाने के लिए चुन सकते हैं एक छोटा हैश। तो आप एक SHA-256 की गणना करें, और सबसे ऊपर लें (या नीचे) 64-बिट पूर्णांक के रूप में, और वह आपका हैश है।

एक नियम के रूप में, मामूली आकार की चीजों के लिए, आप इसे 64 बिट्स में दूर कर सकते हैं। आप इसे 32 बिट्स में दूर नहीं कर सकते। तो जब आप "NSNumber/Int" कहते हैं, तो मैं चाहता हूं कि आप स्पष्ट रूप से "64-बिट पूर्णांक" का अर्थ लें। उदाहरण के लिए, 32-बिट प्लेटफॉर्म पर, स्विफ्ट का इंट केवल 32 बिट्स है, इसलिए मैं UInt64 या uint64_t का उपयोग करूंगा, न कि Int या NSInteger का। मैं यहां अहस्ताक्षरित पूर्णांकों की अनुशंसा करता हूं क्योंकि ये वास्तव में अद्वितीय बिट पैटर्न हैं, न कि "संख्याएं" (यानी उन्हें जोड़ना या गुणा करना सार्थक नहीं है) और नकारात्मक मान होने पर पहचानकर्ताओं में भ्रमित हो जाता है जब तक कि इसका कुछ अर्थपूर्ण अर्थ न हो।

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

यह मेरा सामान्य समाधान है, लेकिन यदि आपका इनपुट स्थान सीमित है तो और भी बेहतर समाधान है। यदि आपका इनपुट स्थान 2^64 से छोटा है, तो आपको हैशिंग की बिल्कुल भी आवश्यकता नहीं है। जाहिर है, किसी भी लैटिन -1 स्ट्रिंग को 8 वर्णों तक 64-बिट मान में संग्रहीत किया जा सकता है। लेकिन अगर आपका इनपुट और भी सीमित है, तो आप डेटा को कंप्रेस कर सकते हैं और थोड़ी लंबी स्ट्रिंग प्राप्त कर सकते हैं। 26 प्रतीकों को एन्कोड करने में केवल 5 बिट लगते हैं, इसलिए यदि आप गणित करने के इच्छुक हैं तो आप UInt64 में एक 12 अक्षर स्ट्रिंग (एक लैटिन केस का) स्टोर कर सकते हैं। यह बहुत दुर्लभ है कि आप इसका उपयोग करने के लिए पर्याप्त भाग्यशाली हों, लेकिन जब अंतरिक्ष प्रीमियम पर हो तो यह आपके दिमाग के पीछे ध्यान देने योग्य है।

मैंने इस प्रकार के बहुत से सिस्टम बनाए हैं, और मैं कहूंगा कि आखिरकार, हम लगभग हमेशा एक लंबी पहचान बनाने के लिए समाप्त हो जाते हैं। आप इसे एक छोटे से पहचानकर्ता पर काम कर सकते हैं, लेकिन यह हमेशा थोड़ा जटिल होता है, और अधिक बिट्स होने के समान प्रभावी कुछ भी नहीं होता है... आपके पहुंचने तक शुभकामनाएँ।

2
Rob Napier 1 मार्च 2019, 17:21

हां, आप क्रिप्टोग्राफ़िक हैश फ़ंक्शन का उपयोग करके टकराव प्रतिरोधी हैश बना सकते हैं। यदि आप एल्गोरिदम विनिर्देशों का पालन करते हैं तो ऐसे हैश फ़ंक्शन का आउटपुट बिट्स में होता है। हालांकि, कार्यान्वयन आम तौर पर केवल बाइट या बाइट मानों का एक एन्कोडिंग लौटाएगा। एक हैश किसी संख्या को नहीं लौटाता है, जैसा कि अन्य ने टिप्पणियों में दर्शाया है।

इस तरह के हैश को कई 32 बाइट्स जैसे Int या Int32 में बदलना अपेक्षाकृत आसान है। आप केवल हैश के सबसे बाएं बाइट लेते हैं और उनको एक हस्ताक्षरित पूर्णांक मानते हैं।

हालांकि, एक क्रिप्टोग्राफ़िक हैश का अपेक्षाकृत बड़ा आउटपुट आकार होता है ताकि यह सुनिश्चित किया जा सके कि टकराव की संभावना कम है। टकराव जन्मदिन की समस्या के लिए प्रवण होते हैं, जिसका अर्थ है कि आपको उत्पन्न सेट के भीतर टकराव पैदा करने के लिए केवल 2 इनपुट से विभाजित hLen की शक्ति के बारे में 2 प्रयास करने होंगे। उदा. आपको RIPEMD-160 हैश की टक्कर बनाने के लिए 2^80 प्रयासों की आवश्यकता होगी।

अब अधिकांश क्रिप्टोग्राफ़िक हैश के लिए, निश्चित रूप से सामान्य वाले, वही नियम मायने रखता है। इसका मतलब है कि 32 बिट हैश के लिए आपको केवल 2^16 हैश की आवश्यकता होगी ताकि यह सुनिश्चित हो सके कि आपके पास टकराव है। यह अच्छा नहीं है, 65536 प्रयास करना बहुत आसान है। और कोई भाग्यशाली हो सकता है, उदा। 256 प्रयासों के बाद आपके पास टकराव की 256 में से 1 संभावना होगी। यह अच्छा नहीं है।

तो आईडी के रूप में इसका उपयोग करने के लिए हैश मान की गणना करना ठीक है, लेकिन आपको हैश फ़ंक्शन के पूर्ण आउटपुट की आवश्यकता होगी, उदा। SHA-2 के 256 बिट्स यह सुनिश्चित करने के लिए कि आपके पास कोई टक्कर नहीं है। अन्यथा आपको इसके बजाय एक सीरियल नंबर की कुछ पंक्ति का उपयोग करने की आवश्यकता हो सकती है।

0
Maarten Bodewes 28 फरवरी 2019, 22:00