تنشأ مهمة في بعض الأحيان لحماية سلسلة المعرف من الأخطاء العرضية التي يرتكبها شخص ما. على سبيل المثال ، رقم بطاقة الدفع. للقيام بذلك ، تتم إضافة رقم التحقق المحسوب بطريقة خاصة إلى السطر ، وعندما يقوم شخص ما بإدخال هذا الرقم ، يمكنك إجراء فحص أولي للخطأ دون الوصول إلى قاعدة البيانات. الخيار الأسهل هو إضافة ما تبقى من تقسيم مجموع جميع الأرقام على 10 ، وفي هذه الحالة سيكون من السهل اكتشاف تشويه أي رقم واحد (بما في ذلك عنصر التحكم) ، ولن يجتاز هذا الخط الاختبار. لكن بعض الأخطاء الأخرى مثل المجموع الاختباري سوف تفوت ، على سبيل المثال ، التقليب المكون من رقمين في الأماكن ، وهذا أيضًا خطأ شائع إلى حد ما.
لحماية أرقام البطاقات المصرفية ، تم اختيار خوارزمية أكثر تعقيدًا وهي خوارزمية
القمر . تمت إضافة تعديل واحد فيه: يتم ضرب الأرقام الموجودة في الأماكن الزوجية بمقدار 2 قبل الجمع (وإذا تبين أن أكثر من تسعة ، فسيتم طرح 9). يسمح لك هذا بالقبض ، بالإضافة إلى تشويه أي رقم ، على معظم (ولكن ليس كل) التباديل من الأرقام المجاورة.
هل هناك خوارزميات يمكنها اكتشاف أي تباديل للأرقام المجاورة (بالإضافة إلى تشويه أي رقم مفرد)؟ نعم ، موجودة ، على الرغم من أنها ليست شائعة جدًا لسبب ما. هذه هي
خوارزمية Verhuff استنادًا إلى مجموعات
dihedral ،
وخوارزمية Damm ، والتي تستند إلى المجموعات شبه دام. هذا يبدو مخيفًا ، لكن في الواقع لا يوجد شيء معقد (بالنسبة لأولئك الذين يعرفون مفهوم "المجموعة").
اقترح جاكوبس فيرهوف ، عالم الرياضيات والنحات الهولندي (أحد تماثيله في الصورة) ، خوارزمية قائمة على
مجموعات ثنائية السطوح . مجموعة dihedral هي مجموعة من التماثلات في N-gon العادية ، بما في ذلك كل من التناوب والتماثلات المحورية. هذه المجموعة ليست تبادلية: إذا تم عرض مضلع منتظم برؤوس مرقمة لأول مرة بشكل متماثل ثم تم تدويره ، فإنه في معظم الحالات لن يكون هو نفسه كما لو قمت بالتدوير أولاً ثم عرضه. وبالتالي ، عند "ضرب" أرقام السلسلة الأصلية بشكل متتابع باستخدام تشغيل مجموعة dihedral ، أي عند تطبيق عمليات التناوب ورسم الخرائط المتناظرة على N-gon العادي ، نحصل على حماية ضد معظم التباديل. من الأغلبية ، ولكن لا يزال ليس من الجميع مرة أخرى. اقترح Verkhuff تحسين هذه الخوارزمية ، وقبل ضرب كل رقم لاستبداله بأخرى وفقًا لجدول خاص ، اعتمادًا على مكان الرقم في السطر. يتم الحصول على الجدول من التقليب واحد عن طريق تطبيقه بالتتابع على النتيجة السابقة ، وبعد 8 تطبيقات من هذا القبيل وصلنا إلى الترتيب الأصلي ، حتى تتمكن من إنشاء جدول 8x10 مسبقًا والاستيلاء على القيمة من هناك. تسمح لنا بعض هذه التباديل بتحديد جميع الأخطاء المحتملة بنسبة 100٪ بترتيب الأرقام المجاورة لسلسلة المصدر ، وهذا هو الحل الكامل والصحيح لمشكلة العثور على رقم التحقق الذي يحمي ضد هذين النوعين من الأخطاء. على ما يبدو ، وجدت Verkhuff التقليب الناجح عن طريق اختيار عشوائي ، وهناك عدد غير قليل منهم.
ظلت مسألة ما إذا كانت هناك مجموعات تسمح للفرد بالعثور على أي تباين للأرقام المجاورة دون تعديلات إضافية مفتوحة لفترة طويلة. وبالفعل في القرن الحادي والعشرين ، في عام 2004 ، أثبت عالم الرياضيات الألماني مايكل دام وجود مثل هذه المجموعات ، ويطلق عليها مجموعات ضعيفة للغاية مضادة للتماثل. لم أكن قد اكتشفت تمامًا كيفية بنائها ؛ يمكن لأولئك الذين يرغبون في محاولة القيام بذلك بأنفسهم عن طريق
نشره . على الرغم من أنه لا يبدو معقدًا للغاية خلال نظرة سريعة (من الغريب أن السؤال ظل مفتوحًا لفترة طويلة) ، إلا أن هناك طريقة أسهل للتنفيذ العملي: استخدام
الجداول الجاهزة .
الآن ، دعنا ننتقل إلى السؤال التالي والرابع: ماذا لو احتجت إلى حماية ليس سلسلة من الأرقام العشرية ، ولكن سلسلة من الأحرف التعسفية ، على سبيل المثال ، ست عشري أو base64 أو base58؟ هذا هو ، لحل المشكلة ليس في حالة معينة من نظام الأرقام العشرية ، ولكن بشكل عام.
تمتد خوارزمية القمر إلى هذه الحالة دون مشاكل ، ولكنها ليست مثيرة للاهتمام للغاية ، لأنها لا تجد جميع التباديل للأرقام المجاورة. طريقة إنشاء مجموعة شبه متجانسة من الحجم التعسفي ليست واضحة تمامًا. بالنسبة لخوارزمية Verhuff ، من السهل إنشاء مجموعة dihedral من الحجم N ، لكنك لا تزال بحاجة إلى جدول التقليب ، والذي من غير الواضح أيضًا من أين يمكن الحصول عليه (وليس من الواضح ما إذا كان موجودًا). هذه هي دراسة السؤال الأخير ، وبدأت.
غوغلينغ لم تسفر إلا عن محاولات منفصلة واستخدام حلول "جيدة إلى حد ما" (أي اكتشاف تقريبًا جميع التباديل) لـ N = 64.
ربما لن أصف كل الطرق التي تم اختبارها واختبارها للعثور على التقليب المطلوب ، والذي لم يعط نتيجة. حاولت حل مشكلة معينة: العثور على التقليب لـ base64 و base58 ، والذي يوفر الحماية من تغيير ترتيب الأرقام المجاورة. لا يمكنني إلا أن أقول إن محاولات العثور على مثل هذا التقليب عن طريق البحث العشوائي أو المتسلسل مع خيارات تحسين مختلفة قد فشلت. ولكن في النهاية ، وجدت حلاً عامًا لأي حتى n.
التقليب هو كما يلي:
0, N-1 .. N/2+1, 1 .. N/2
على سبيل المثال ، بالنسبة إلى N = 10 ، سيكون هذا:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
يحتوي هذا التقليب على خاصية رائعة أخرى: دائمًا ما تحتوي على فترة (لـ N> = 8) من 12 ، والتي تتيح لك إنشاء جدول 12xN مسبقًا وأخذ رقم من هناك.
فيما يلي مثال لتطبيق الامتداد المقترح لخوارزمية Verhuff لـ base58 (بالمعنى الدقيق للكلمة ، هذه ليست خوارزمية
Verkhuff ، ولكن تعميمها). ليس ليب كامل ، ولكن مجرد فائدة ، إذا جاز التعبير ، دليل على المفهوم.
إثبات أن هذا التقليب لديه الخاصية اللازمة ، وأنه يحتوي على فترة 12 ، وسأقدم في وقت ما في وقت لاحق. هناك مساحة صغيرة للغاية في الهامش لتناسبها هنا.