انتقل إلى المحتوى

تحليل التكرار

من ويكيبيديا، الموسوعة الحرة
مبيان يوضح تواتر حروف اللغة العربية حسب نص "ألف ليلة وليلة" من ويكي مصدر.
مبيان يوضح تواتر حروف اللغة العربية حسب نص "ألف ليلة وليلة" من ويكي مصدر.

في علم تحليل الشفرات، تحليل التكرار، أو تواتر الحروف أو مراتب الحروف هو دراسة تكرار الحروف أو تشكيلة من الحروف أو مراتبها في النص المشفر، من أجل الوصول إلى مفتاح لفك الشفرة، وهو أحد طرق هجوم النص المشفر فقط (أو هجوم الاكتفاء بالنص المشفر).
يستند تحليل التكرار على واقع كون توزيع حروف اللغة لا يتبع توزيعا منتظما (بالإنجليزية: Uniform)، بل يكون له توزيع مميز يميز كل لغة عن نظيرتها. بعبارة أخرى، فإنه لأي لغة تتكرر حروف أو تركيبة من الحروف بشكل متفرد، وتأخذ بعض الحروف توزيعاً مميزاً يكاد يكون غالبا لمعظم العينات من تلك اللغة.[1] على سبيل المثال لأي مقطوعة من نص عربي نجد أن الحروف: «ا»، «ل»، «ي»، «م» هي الأكثر تكراراً؛ بينما الحروف: «ظ»، «غ»، «ط» هي الأقل شيوعاً، وكذلك يظهر النمط ألف ولام متتاليين بشكل متكرر في النصوص العربية. ويمكن تعميم هذا التحليل أيضا باعتبار ثلاثة أحرف أو أربعة.

طور العرب هذا العلم واستخدموه بغرض تحليل شفرات كانت شائعة الاستخدام حينئذ وكسرها.[2][3] وقد أدى بزوغ هذا النوع من التحليل إلى ظهور شفرات جد متطورة على ما كانت عليه في ذلك الوقت، ولذلك يعتبر العديد من المؤرخون العرب كمؤسسي علم التشفير.[3]

تاريخ

[عدل]

اقترن تأسيس علم استخراج المعمى (بالإنجليزية: cryptanalysis) بتطور علوم الرياضيات وخصوصا علمي الحساب و الجبر و المقابة لدى العرب.[2] فكما جاء على لسان المؤرخ الأمريكي ديفيد كهن في كتابه المرجعي the codebreakers : "لقد نشأ علم الكريبطولوجيا بين ظهراني العرب، لقد كان العرب أول من طوروا ودونوا علم استخراج المعمى ".[3] ولعل أبرز ما أبدع فيه العرب من طرق استخراج المعمى هو حساب التواتر أو تحليل التكرار.[4] فقد وصف الكِندي المتوفى سنة 260 هجرية في مؤلفه "رسالة في استخراج المعمى" عملية إحصاء تواتر الحروف بالاعتماد على عينة كافية من الكلام المنثور في تلك اللغة تسمح بالقيام بالعمليات الإحصائية عليه.[2] يقول الكِندي واصفا هذه العملية الفريدة:

فمما نحتال به لاستنباط الكتاب المعمى، [...]، أن يوجد من ذلك اللسان كتاب قدر ما يقع في جلد أو ما أشبهه، فنعد ما فيه من كل نوع من أنواع حروفه، فنكتب على أكثرها عددا الأول، والذي يليه في الكثرة الثاني، [...]، ثم ننظر في الكتاب الذي نريد استخراجه، [...]، فننظر إلى أكثرها عددا فنسمه بسمة الحرف الأول، والذي يليه في الكثرة نسمه بسمة الحرف الثاني، [...]، حتى تنفد أنواع صور حروف الكتاب المعماة.[2]

ويعد هذا النص أقدم ما دون في استخدام حيلة حساب التواتر لاستخراج المعمى.[2] وفيم يلي نعرض جدول تحليل التكرار وفقا لما يعزى إلى الكندي، وهو مرتب حسب مراتب الكثرة. وقد استخدم لهذا الغرض نضا مؤلفا من 3667 حرف.[2]

جدول تحليل تواتر الحروف وفق ما نسب إلى الكندي
الحرف ا ل م ه و ي ن ر ع ف ت ب ك د س ق ح ج ذ ص ش ض خ ث ز ط غ ظ المجموع
تواتره 600 437 320 273 262 252 221 155 131 122 120 112 112 92 91 63 57 46 35 32 23 20 20 17 16 15 15 8 3667

وقد أورد علي بن عدلان المتوفى سنة 666 هجرية إحصاء لتواتر الحروف على غرار ما فعله الكِندي، وقد تميز بتعيينه لطول أدنى للنص المشفر حتى تنجح عملية الاستخراج بهذه الطريقة الإحصائية. يقول ابن عدلان في رسالته "المؤلف للملك الأشرف في حل التراجم":

الكلام المطلوب حله ينبغي أن يكون تسعين حرفا، [...]، لأن الحروف تكون قد دارت حينئد ثلاث دورات.[2]

أبدع العرب بعدها في كسر شفرات عديدة تحت طلبات من سلاطنة وملوك دول أخرى. وبالإضافة لعلم استخراج المعمى، أبدع العرب أيضا في تطوير شفرات عُرفت بتميزها عن باقي الشفرات المعاصرة لها يومئذ.[3] يستخدم حاليا مؤشر التطابق (بالإنجليزية: index of coincidence) الذي طوره وليام فريدمان عام 1922م، والذي يعتمد على تحليل تواتر حروف اللغة بشكل أساسي لأجل كشف و كسر بعض الشفرات التقليدية.[5]

تحليل التكرار في شفرات الاستبدال

[عدل]

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

مبدأ تحليل التكرار

[عدل]

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

جدول ترتيب الحروف حسب الكثرة وفق تحليل كتاب ألف ليلة وليلة من ويكي مصدر
الحرف ا ل ي م و ن ت ر ه ب ف ع د ك ق س ح ج خ ذ ش ص ز ث ط ض غ ظ
النسبة المئوية 17.7 11.6 7.0 6.4 6.1 5.8 5.4 4.4 4.4 3.7 3.5 3.4 2.8 2.8 2.5 1.9 1.8 1.5 1.0 1.0 1.0 1.0 0.7 0.6 0.6 0.5 0.4 0.2

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

تحليل التكرار في اللغة الإنجليزية

[عدل]
تحليل تكرار حروف اللغة الإنجليزية
تحليل تكرار حروف اللغة الإنجليزية

يمكن تطبيق نفس المبدأ المذكور أعلاه على أية لغة لأجل استخراج الخواص الإحصائية لهذه اللغة و خصوصا خاصية توزيع حروف اللغة باعتبار مصدر (نصوص، كتب، الخ) كافي للقيام بهاته العملية. ومما لاشك فيه، فإن اللغة الإنجليزية تعتبر من أكثر اللغات انتشارا في العالم، وبالتالي فالعديد من النصوص المشفرة مؤهلة مبدئيا لتكون شفرات باللغة الإنجليزية، لذلك يعتبر تحليل تواتر حروف اللغة الإنجليزية من أهم التحليلات التي ينبغي التوفر عليها قبل القيام بإجراء محاولة استخراج النصوص الأصلية و كسر الشفرات. يوضح المبيان جانبه توزيع حروف اللغة الإنجليزية.[7] ويمكن ملاحظة أن أكثر الحروف شيوعا في اللغة الإنجليزية هي الحروف E , T , A. في حين أن أقل الحرف شيوعا هي الحروف Z , Q , X.

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

تحليل التكرار في الواقع

[عدل]

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

بطائق بريدية مشفرة

[عدل]

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

قضية كارلي بروسيا

[عدل]

في شهر فبراير من العام 2004، استيقضت الولايات المتحدة على حادثة خطف و اغتصاب و قتل طفلة في الحادي عشر من عمرها تدعى كارلي بروسيا (Carlie Brucia) من طرف شخص مجهول تبين لاحقا من خلال كامرات الفيديو أنه يدعى جوزيف سميث (Joseph Smith). قبل نطق الحكم على سميث، قام بكتابة رسالة مشفرة (موضحة جانبه) لأخيه يخبره عن مكان بعض ملابس الفتاة و محفظتها.[9] قام مكتب التحقيقات الفيدرالي بكسر هذه الرسالة بسرعة، وكونها رسالة تعتمد على استبدال أحادي كان من السهل كسرها باستخدام تحليل التكرار.

استخدم سميث سمات مكونة من أرقام ورموز رياضية لأجل وسم كل حرف انجليزي بسمة معينة سرية. كان عدد هذه السمات هو 25 ( الأرقام من 1 إلى 5 ورموز حسابية +, ×, ÷, −) بينما عدد حروف اللغة الإنجليزية هو 26. في هذه الحالة يتم غالبا دمج الحرفين I و J بنفس الخانة.

بالقيام بتحليل التكرار على سمات هذا النص المشفر نجد أن أكثر السمات تواترا هي الرموز 1+, 5-, 2% و . هذه السمات تقابل الحروف الإنجليزية الأكثر تواترا و هي t, e, i, o. يمكن بعد إيجاد تقابل مجموعة من الحروف (الأكثر و الأقل شيوعا على حدة) تخمين الكلمات بعد ذلك وبالتالي إيجاد المقابلة اللازمة لكسر الشفرة.

تحليل التكرار في الخيال

[عدل]

تناولت بعض روايات الخيال تحليل التكرار، مثل شارلوك هولمز في «مغامرة الرجال الراقصون» أحد القصص القصيرة لـ آرثر كونان دويل.

المصادر

[عدل]
  1. ^ Frequency analysis - Wikipedia, the free encyclopedia
  2. ^ ا ب ج د ه و ز د. محمد مراياتى, يحى مير علم, محمد حسان الطيان (1988). علم التعمية واستخراج المعمى عند العرب. مجمع اللغة العربية بدمشق. ج. الأول.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link)
  3. ^ ا ب ج د Kahn David (1996). The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. Simon and Schuster.
  4. ^ [Cryptologia "ORIGINS OF CRYPTOLOGY: THE ARAB CONTRIBUTIONS"]. tandfonline. 1992. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدةالوسيط |الأول= يفتقد |الأخير= (مساعدة)، وتحقق من قيمة |مسار= (مساعدة)
  5. ^ William F. Friedman (1922). The index of coincidence and its applications in cryptography. L. Fournier, Paris et 1922.
  6. ^ Forouzan, Behrouz A. 2008. Introduction to cryptography and network security. page 59
  7. ^ "Frequency analysis". https://en.wikipedia.org. مؤرشف من الأصل في 2023-02-11. {{استشهاد ويب}}: روابط خارجية في |موقع= (مساعدة)
  8. ^ "an encrypted postcard from india". مؤرشف من الأصل في 2023-02-16.
  9. ^ "Smith Convicted in Carlie Brucia Murder". مؤرشف من الأصل في 2023-02-20.