لماذا رموز التجزئة التي تم إنشاؤها بواسطة هذه الوظيفة ليست فريدة من نوعها؟
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أقوم باختبار وظيفة VB أدناه التي حصلت عليها من بحث Google.أخطط لاستخدامه لإنشاء رموز التجزئة لمقارنة السلسلة السريعة.ومع ذلك، هناك مناسبات يكون فيها لسلسلتين مختلفتين نفس رمز التجزئة.على سبيل المثال، هذه السلاسل
"حجم الكومة 122Gen 1 (ذاكرة NET CLR w3wp):mccsmtpteweb025.20833333333333E-02"
"حجم الكومة 122Gen 2 (ذاكرة NET CLR w3wp):mccsmtpteweb015.20833333333333E-02"
لها نفس رمز التجزئة 237117279.
أرجوك قل لي:- ما هو الخطأ في الوظيفة؟- كيف يمكنني إصلاح ذلك؟
شكرًا لك
مارتن
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
المحلول
أراهن أن هناك أكثر من مجرد "مناسبات" عندما تقوم سلسلتان بإنشاء نفس التجزئة باستخدام وظيفتك.في الواقع، ربما يحدث هذا في كثير من الأحيان أكثر مما تعتقد.
بعض الأشياء التي يجب إدراكها:
أولا، سيكون هناك تصادمات التجزئة.يحدث ذلك.حتى مع وجود مسافات كبيرة جدًا مثل MD5 (128 بت)، لا يزال هناك سلسلتين يمكنهما إنشاء نفس التجزئة الناتجة.عليك التعامل مع تلك الاصطدامات عن طريق إنشاء مجموعات.
ثانيًا، العدد الصحيح الطويل ليس في الواقع مساحة تجزئة كبيرة.سوف تحصل على عدد أكبر من الاصطدامات مما لو استخدمت المزيد من البتات.
ثالثًا، هناك مكتبات متاحة لك في Visual Basic (مثل .NET's System.Security.Cryptography مساحة الاسم) التي ستقوم بعمل تجزئة أفضل بكثير من معظم البشر العاديين.
نصائح أخرى
السلسلتان لهما نفس الأحرف.(لاحظ "2" و"1" المقلوبين)
هذا هو السبب في أن قيمة التجزئة هي نفسها.
تأكد من أن وظيفة التجزئة تأخذ في الاعتبار ترتيب الأحرف.
لا تضمن وظائف التجزئة تفرد قيم التجزئة.إذا كان نطاق قيمة الإدخال (الحكم على سلاسل العينة الخاصة بك) أكبر من نطاق قيمة الإخراج (على سبيل المثال، عدد صحيح 32 بت)، فإن التفرد مستحيل ماديًا.
إذا كانت المشكلة الأكبر هي أنها لا تأخذ في الاعتبار موضع البايتات، فيمكنك إصلاحها على النحو التالي:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
والفرق الوحيد هو أنه يضيف موضع الأحرف إلى قيمة البايت الخاصة به قبل XOR.
لا توجد وظيفة تجزئة يمكن أن تضمن التفرد.هناك ما يقرب من 4 مليار عدد صحيح 32 بت، لذلك حتى أفضل دالة تجزئة ستولد نسخًا مكررة عند تقديمها مع ما يقرب من 4 مليارات وسلسلة واحدة (وعلى الأغلب قبل فترة طويلة).
لا يعد الانتقال إلى تجزئات 64 بت أو حتى تجزئات 128 بت هو الحل حقًا، على الرغم من أنه يقلل من احتمالية حدوث تصادم.
إذا كنت تريد وظيفة تجزئة أفضل، فيمكنك إلقاء نظرة على تجزئات التشفير، ولكن سيكون من الأفضل إعادة النظر في الخوارزمية الخاصة بك وتحديد ما إذا كان بإمكانك التعامل مع التصادمات بطريقة أخرى.
ال النظام.الأمن.التشفير تحتوي مساحة الاسم على فئات متعددة يمكنها إجراء التجزئة نيابةً عنك (مثل MD5) والتي من المحتمل أن تقوم بتجزئتها بشكل أفضل مما تستطيع أن تفعله بنفسك وسوف تتطلب جهدًا أقل بكثير.
ليس عليك دائمًا إعادة اختراع العجلة.
XOR البسيط هو تجزئة سيئة:ستجد الكثير من الخيوط التي تتصادم.لا يعتمد التجزئة على ترتيب الحروف في السلسلة، لسبب واحد.
حاول استخدام تجزئة FNV http://isthe.com/chongo/tech/comp/fnv/
هذا حقا سهل التنفيذ.يقوم بتغيير رمز التجزئة بعد كل XOR، وبالتالي فإن نفس الحروف بترتيب مختلف ستنتج تجزئة مختلفة.
ليس المقصود من وظائف التجزئة إرجاع قيم مميزة لسلاسل مميزة.ومع ذلك، يجب أن تقوم دالة التجزئة الجيدة بإرجاع قيم مختلفة للسلاسل المتشابهة.تُستخدم وظائف التجزئة للبحث لأسباب عديدة، بما في ذلك البحث في مجموعة كبيرة.إذا كانت دالة التجزئة جيدة وإذا كانت ترجع قيمًا من النطاق [0,N-1]، فسيتم تقسيم مجموعة كبيرة من الكائنات M إلى مجموعات N، تحتوي كل منها على عناصر M/N تقريبًا.بهذه الطريقة، تحتاج إلى البحث فقط في مصفوفة من عناصر M/N بدلاً من البحث في مصفوفة من عناصر M.
ولكن، إذا كان لديك سلسلتين فقط، فهو كذلك لا أسرع لحساب قيمة التجزئة لهؤلاء!إنها أحسن فقط لمقارنة السلسلتين.
يمكن أن تكون وظيفة التجزئة المتداخلة:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
لقد أصلحت تسليط الضوء على بناء الجملة بالنسبة له.
أيضًا، بالنسبة لأولئك الذين لم يكونوا متأكدين من البيئة أو كانوا يقترحون تجزئة أكثر أمانًا:إنه VB كلاسيكي (ما قبل .Net)، لأن .Net سيتطلب أقواسًا لاستدعاء CopyMemory.
IIRC، لا توجد أي تجزئات آمنة مدمجة في Classic VB.لا يوجد الكثير على الويب أيضًا، لذلك قد يكون هذا هو أفضل رهان له.
لا أرى البيئة التي تعمل فيها تمامًا.هل هذا كود .Net؟إذا كنت تريد حقًا رموز تجزئة جيدة، فإنني أوصي بالبحث في تجزئة التشفير (خوارزميات مثبتة) بدلاً من محاولة كتابة تجزئة خاصة بك.
راجع للشغل، هل يمكنك تعديل منشورك ولصق الكود كنموذج كود (انظر شريط الأدوات)؟وهذا من شأنه أن يسهل القراءة.
"لا تفعل ذلك."
تعد كتابة دالة التجزئة الخاصة بك خطأً كبيرًا، لأن لغتك بالتأكيد تحتوي بالفعل على تطبيق SHA-1، وهي وظيفة تجزئة جيدة تمامًا.إذا كنت تحتاج فقط إلى 32 بت (بدلاً من 160 بت التي يوفرها SHA-1)، فما عليك سوى استخدام آخر 32 بت من SHA-1.
تعمل وظيفة التجزئة هذه على XORs لجميع الأحرف الموجودة في السلسلة.لسوء الحظ XOR ترابطي:
(a XOR b) XOR c = a XOR (b XOR c)
لذا فإن أي سلاسل تحتوي على نفس أحرف الإدخال ستؤدي إلى نفس رمز التجزئة.السلسلتان المقدمتان متماثلتان، باستثناء موقع حرفين، وبالتالي يجب أن يكون لهما نفس رمز التجزئة.
قد تحتاج إلى العثور على خوارزمية أفضل، وسيكون MD5 خيارًا جيدًا.
عملية XOR تبادلية؛أي أنه عند إجراء عملية XORing لجميع الأحرف في سلسلة ما، لا يهم ترتيب الأحرف.ستنتج جميع الجناس الناقصة لسلسلة ما نفس تجزئة XOR.
في المثال الخاص بك، يمكن إنشاء السلسلة الثانية من السلسلة الأولى عن طريق تبديل "1" بعد "...Gen " مع السلسلة "2" الأولى التي تليها.
لا يوجد شيء خاطئ في وظيفتك.قد تؤدي جميع وظائف التجزئة المفيدة في بعض الأحيان إلى حدوث تصادمات، ويجب أن يكون برنامجك مستعدًا لحلها.
يحدث التصادم عندما يتم تجزئة أحد المدخلات إلى قيمة تم تحديدها بالفعل باستخدام إدخال سابق.إذا لم تتمكن خوارزمية التجزئة من توليد تصادمات، فيجب أن تكون قيم التجزئة كبيرة مثل قيم الإدخال.ستكون خوارزمية التجزئة هذه ذات استخدام محدود مقارنةً فقط بتخزين قيم الإدخال.
-آل.
يوجد تطبيق أساسي مرئي لتجزئة MD5 هنا
