مسافة الوحدة

في التشفير، مسافة الوحدة وهي طول النص المشفر الأصلي المطلوب لكسر التشفير عن طريق تقليل عدد المفاتيح الزائفة المحتملة إلى الصفر في هجوم القوة الغاشمة. أي بعد تجربة كل مفتاح ممكن، يجب أن يكون هناك فك تشفير واحد يكون منطقيًا، أي المقدار المتوقع من النص المشفر اللازم لتحديد المفتاح تمامًا، على افتراض أن الرسالة الأساسية بها تكرار.

نبذة

حدد كلود شانون مسافة الوحدة في ورقته البحثية التي صدرت في عام 1949 والتي تحمل عنوان «نظرية الاتصال لأنظمة السرية». ضع في اعتبارك هجومًا على سلسلة النص المشفر "WNAIW" المشفرة باستخدام تشفير Vigenère من خمسة أحرف. من المتصور، يمكن فك تشفير هذه السلسلة إلى أي سلسلة أخرى — RIVER و WATER كلاهما احتمالان لمفاتيح معينة. هذه قاعدة عامة لتحليل الشفرات بدون معلومات إضافية يستحيل فك شفرة هذه الرسالة.

وبالطبع، حتى في هذه الحالة، سينتج عن الكلمات الإنجليزية عدد معين من مفاتيح الأحرف الخمسة فقط. بتجربة جميع المفاتيح الممكنة، لن نحصل فقط على RIVER و WATER ، ولكن SXOOS و KHDOP أيضًا. من المحتمل أن يكون عدد المفاتيح «العاملة» أصغر بكثير من مجموعة جميع المفاتيح الممكنة. المشكلة هي معرفة أي من هذه المفاتيح «العاملة» هو الصحيح. البقية زائفة.

العلاقة مع حجم المفتاح والنصوص الصريحة المحتملة

وبشكل عام، نظرًا لافتراضات معينة حول حجم المفتاح وعدد الرسائل المحتملة، يوجد متوسط طول النص المشفر حيث يوجد مفتاح واحد فقط (في المتوسط) سيولد رسالة يمكن قراءتها. في المثال أعلاه نرى سوى حالة العلوي الأحرف الإنجليزية، حتى إذا افترضنا أن نص عادي له هذا النموذج، ثم هناك 26 حرفا المحتملة لكل موقف في السلسلة. وبالمثل، إذا افترضنا مفاتيح الأحرف الكبيرة المكونة من خمسة أحرف، فهناك K = 26 ⁵ مفاتيح محتملة، ومعظمها لن «يعمل».

ويمكن إنشاء عدد هائل من الرسائل المحتملة، N ، باستخدام حتى هذه المجموعة المحدودة من الأحرف: N = 26 ^L ، حيث L هو طول الرسالة. ومع ذلك، فإن مجموعة أصغر منها فقط هي نص عادي يمكن قراءته بسبب قواعد اللغة، ربما M منها، حيث من المحتمل أن تكون M أصغر بكثير من N. علاوة على ذلك، تمتلك M علاقة رأس برقم مع الرقم من المفاتيح التي تعمل، ولذلك مع وجود مفاتيح K الممكنة، فقط K × (M / N) منهم سوف «يعمل» واحد من هؤلاء هو المفتاح الصحيح، والباقي زائف.

ونظرًا لأن M / N يصبح صغيرًا بشكل تعسفي مع زيادة طول L للرسالة، فهناك في النهاية بعض L كبير بما يكفي لجعل عدد المفاتيح الزائفة يساوي صفرًا. بشكل تقريبي، هذا هو L الذي يجعل KM / N = 1. هذه L هي مسافة الوحدة.

العلاقة مع الانتروبيا الرئيسية وتكرار النص الصريح

ويمكن تعريف مسافة الوحدة على أنها الحد الأدنى من النص المشفر المطلوب للسماح لخصم غير محدود من الناحية الحسابية باستعادة مفتاح التشفير الفريد.

ويمكن بعد ذلك إظهار مسافة الوحدة المتوقعة على النحو التالي:

$U=H(k)/D$

وحيث U هي المسافة حدانية، H (ك) هو الكون من الفضاء الرئيسي (على سبيل المثال 128 لمدة 2 ¹²⁸ مفاتيح equiprobable، بدلا أقل إذا كان المفتاح هو يحفظون تمرير العبارة). يتم تعريف D على أنه تكرار النص العادي في وحدات البت لكل حرف.

والآن يمكن أن تحمل الأبجدية المكونة من 32 حرفًا 5 بتات من المعلومات لكل حرف (مثل 32 = 2 ⁵). بشكل عام، عدد بتات المعلومات لكل حرف هو log₂(N) ، حيث N هو عدد الأحرف في الأبجدية log₂ هو اللوغاريتم الثنائي. لذلك بالنسبة للغة الإنجليزية، يمكن لكل حرف نقل log₂(26) = 4.7 بت من المعلومات.

ومع ذلك، فإن متوسط كمية المعلومات الفعلية المنقولة لكل حرف في نص إنجليزي ذو معنى هو فقط حوالي 1.5 بت لكل حرف. لذا فإن تكرار النص العادي هو D = 4.7 − 1.5 = 3.2

وفي الأساس، كلما كانت مسافة الوحدة أكبر كلما كان ذلك أفضل. بالنسبة إلى لوحة زمنية واحدة ذات حجم غير محدود، بالنظر إلى الانتروبيا غير المحدودة لمساحة المفتاح، لدينا $U=\infty$ ، وهو ما يتفق مع عدم إمكانية كسر الوسادة أحادية الاستخدام.

مسافة الوحدة لشفرات الاستبدال

ولشفرة استبدال بسيطة، فإن عدد المفاتيح الممكنة هو 26! = 4.0329 × 10²⁶ = 2^88.4 ، وعدد الطرق التي يمكن بها تبديل الأبجدية. بافتراض أن جميع المفاتيح متساوية الاحتمال، H(k) = log₂(26!) = 88.4 بت. للنص الإنجليزي D = 3.2 ، وبالتالي U = 88.4/3.2 = 28 .

ولذلك، بالنظر إلى 28 حرفًا من النص المشفر، يجب أن يكون من الممكن نظريًا عمل نص عادي باللغة الإنجليزية ومن ثم المفتاح.

تطبيق عملي

وتعد مسافة الوحدة مقياسًا نظريًا مفيدًا، ولكنها لا تخبرنا كثيرًا عن أمان تشفير الكتلة عند مهاجمتها من قبل خصم بموارد حقيقية (محدودة). ضع في اعتبارك كتلة تشفير بمسافة أحادية مكونة من ثلاث كتل نص مشفر. على الرغم من أنه من الواضح أن هناك معلومات كافية لخصم غير محدود حسابيًا للعثور على المفتاح الصحيح (بحث شامل بسيط)، فقد يكون هذا غير عملي من الناحية الحسابية.

ويمكن زيادة مسافة الوحدة عن طريق تقليل تكرار النص العادي. تتمثل إحدى طرق القيام بذلك في نشر تقنيات ضغط البيانات قبل التشفير، على سبيل المثال عن طريق إزالة أحرف العلة الزائدة مع الاحتفاظ بقابلية القراءة. هذه فكرة جيدة على أي حال، لأنها تقلل من كمية البيانات المراد تشفيرها.

ويمكن افتراض أن النصوص المشفرة الأكبر من مسافة الوحدة تحتوي على فك تشفير واحد ذي معنى. قد تحتوي النصوص المشفرة الأقصر من مسافة الوحدة على العديد من عمليات فك التشفير المعقولة. مسافة الوحدة ليست مقياسًا لمقدار النص المشفر المطلوب لتحليل التشفير، ولكن ما هو مقدار النص المشفر المطلوب ليكون هناك حل واحد معقول لتحليل التشفير.

روابط خارجية

• بروس شناير: كيفية التعرف على النص العادي (النشرة الإخبارية Crypto-Gram 15 ديسمبر 1998)
• تم حساب مسافة الوحدة للأصفار الشائعة