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

والسبب هو أنني لم أقم بذلك إلا مؤخرًا ولم أخبر أي شخص عنه بعد. ومع ذلك ، فإن أداء الكود ، مثل أداء المعالج ، له خصائص موضوعية يمكن قياسها. تتناول هذه المقالة تحديدًا أداء الكود الذي ينفذه نواة المعالج.

كيف يتم قياس أداء الكود؟ منذ أن كنت أول من تحدث عن هذا ، ثم بحق المكتشف سأقيسه في مقاييس RTT ؛).

الآن بجدية. في المعالجات الحديثة ، تكون التحولات الرئيسية هي العمليات على أرقام 32 بت ، وكل شيء آخر ، إلى حد كبير ، غريب. لذلك ، سنأخذ في الاعتبار الشيء الرئيسي - العمليات بأرقام 32 بت. كم عدد عمليات 32 بت التي تعتقد أن جوهر المعالج الحديث يمكنه تنفيذها في وقت واحد؟

سيجيب الطالب - واحدًا ، سيفكر معلمه ويقول أن أربعة ، المحترف - أنه لا يوجد سوى اثنتي عشرة عملية حتى الآن.

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

سأثبت أن الكود مع التنفيذ المتزامن لاثنتي عشرة عملية 32 بت ممكن

رمز البرنامج الذي يستخدم وحدة تنفيذ واحدة في قلب المعالج سيكون له أداء 1 RTT بشكل طبيعي. يمكن للبرامج التي تم إنشاؤها بواسطة مترجمي اللغة رفيعي المستوى ومترجمي الآلة الافتراضية "التباهي" بأداء الكود. لا ينبغي افتراض أن مؤشر استخدام وحدة المعالجة المركزية ، والذي يمكن رؤيته في مدير مهام نظام التشغيل ، يمكن أن يكون بمثابة معيار موضوعي لفعالية الكود. يمكن أن يكون الحمل الأساسي للمعالج 100٪ ، لكن كود البرنامج سيستخدم جهاز تنفيذ واحد فيه (الأداء 1 RTT). في هذه الحالة ، عند تحميل 100٪ ، سيعمل نواة المعالج عند 1/12 من أقصى أداء له. بمعنى آخر ، عندما يعرض Windows Task Manager الحد الأقصى لاستخدام وحدة المعالجة المركزية ، يمكن أن يختلف أدائه الفعلي من 1 إلى 12 RTT. بالنظر إلى تحميل نافذة الأداء بنسبة 100٪ على أي نواة معالج ، فمن الخطأ افتراض أن جميع الأجهزة التنفيذية تعمل في هذا النواة ، بأي حال من الأحوال!

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

التنفيذ التقليدي لـ GOST 28147-89

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

يستخدم التحويل المشفر وفقًا لـ GOST 28147-89 لتدفق تشفير المعلومات في قنوات الاتصال وعلى محركات الأقراص.

حاليًا ، يتم استخدام تطبيق برنامج GOST هذا على RON للمعالج المركزي على نطاق واسع. في الطرق المعروفة لتنفيذ GOST ، يتم وضع جميع المعلومات السرية (مفاتيح التشفير ، كتل الاستبدال) في ذاكرة الوصول العشوائي. هذا يقلل من موثوقية التشفير ، لأنه بوجود تفريغ ذاكرة الوصول العشوائي ، من الممكن الكشف تمامًا عن جميع العناصر السرية لتحويل التشفير. بالإضافة إلى ذلك ، فإن الطريقة لها قيود على السرعة بسبب موقع الكائنات الرئيسية لتحويل التشفير في OP والتحميل غير الكامل للأجهزة التنفيذية ALU. يمكن للمعالجات الحديثة ، التي تنفذ معالجة التشفير باستخدام طريقة معروفة ، أن توفر سرعة تشفير تتراوح بين 40 و 60 ميغا بايت في الثانية. وإذا كنت تفهمها حقًا حتى النهاية ، فإن سبب الأداء المنخفض والأمان الضعيف لتحويل العملة المشفرة هو تنفيذ برنامج كتلة الاستبدال. انظر وصفه في GOST في الشكل. 1.

وفقًا للفقرة 1.2 من GOST ، تنفذ هذه الكتلة تباديل رباعي (أربعة بتات) في كلمة 32 بت ، لكن بنية المعالج x86 / 64 ومجموعة التعليمات الخاصة به ليست قادرة على معالجة التتراد بشكل فعال.

لتنفيذ برنامج كتلة الاستبدال ، يتم استخدام جداول خاصة في ذاكرة الوصول العشوائي ، والتي يتم إعدادها في مرحلة تهيئة وظيفة التشفير. تجمع هذه الجداول بين عقد الاستبدال لرباعيات متجاورة في جداول بايت 8 × 8 بت ، لذلك هناك أربعة جداول 256 بايت في ذاكرة الوصول العشوائي.

في عمليات التنفيذ الأكثر تقدمًا ، يبلغ حجم هذه الجداول 1024 بايت (256 كلمة من أربعة بايت). يتم ذلك من أجل تنفيذ تحول دوري إضافي في الجداول بمقدار 11 موضعًا للكلمة ذات 32 بت التي تم الحصول عليها نتيجة للاستبدال (العملية التالية لخوارزمية التحويل وفقًا لـ GOST). يظهر مثال على تنفيذ GOST وفقًا لهذه الطريقة في الملحق 1 (على القرص).

تعتبر معلومات كتلة الاستبدال مكونًا سريًا لوظيفة التشفير (كما تمت صياغتها في GOST ، انظر الشكل 2).

يتعارض وضع هذه الجداول مع مفاتيح كتلة الاستبدال في OP مع متطلبات GOST (البند 1.7) ، حيث تصبح المعلومات السرية متاحة لبرامج الجهات الخارجية التي تعمل على تثبيت الكمبيوتر. إن FSB ، التي تصدق أيضًا على تطبيقات التشفير وفقًا لـ GOST ، تنظر في هذا الانتهاك ، بعبارة ملطفة ، بتنازل. إذا تم وضع المفاتيح في OP ، فلا يزال FSB يتطلب "ورقة تين" - إخفاء المفاتيح باستخدام عملية XOR ، فلا شيء مطلوب لاستبدال الكتل في OP ، حيث يتم تخزينها في نص واضح.

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

سنعود إلى مسألة تخزين المفاتيح وكتل الاستبدال في السجلات الداخلية للمعالج بعد قليل (يوجد حل جميل وسريع) ، ولكن في الوقت الحالي سنقوم فقط بتخزين مفاتيح التشفير في سجلات MMX ، وهذا أكثر موثوقية.

لكن يكفي من الكلمات ، من المهم في إطار الموضوع قيد الدراسة أن يكون أداء كود البرنامج هذا 1 RTT-shku. لنكتب الآن رمزًا بأداء 2 RTT.

تنفيذ متعدد مؤشرات الترابط لـ GOST 28147-89

الطريقة الوحيدة لتسريع إجراءات التشفير في الخوارزمية المعروفة هي إدخال تعدد مؤشرات الترابط. معنى هذا التغيير في تنفيذ الخوارزمية هو حساب عدة كتل من البيانات على التوازي في وقت واحد.

يقصد معظم المبرمجين بالمعالجة المتوازية فقط عمل العديد من نوى المعالج ، المتزامنة من خلال المقاطعات والإشارات في الذاكرة.

ومع ذلك ، هناك نوع آخر من المعالجة المتوازية للبيانات على نواة معالج واحد. اسمحوا لي أن أشرح هذه الفكرة غير الواضحة.

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

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

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

لا يمكن للمجمّعين ، حتى الأكثر تحسينًا ، وأكثر من ذلك - محركات الآلة الافتراضية ، إنشاء تعليمات برمجية محسّنة من حيث الأداء. يمكن فقط للمبرمج الذي لديه معرفة هندسية أن يكتب مثل هذا الكود المحسن ، وأداة كتابته عبارة عن مُجمِّع حصري.

من الأمثلة التوضيحية المميزة لإمكانية تنفيذ عدة سلاسل برامج مستقلة على نواة معالج واحدة ، تنفيذ GOST ، والذي يتم تنفيذه في خيطين على نواة معالج واحد. فكرة الكود بسيطة: هناك مجموعتان من البيانات للتشفير / فك التشفير ، لكن معالج واحد يقوم بالتحويل. من الممكن إجراء التحويل لهاتين الكتلتين من البيانات بالتتابع ، وقد تم ذلك حتى الآن. في هذه الحالة ، يتم مضاعفة الوقت اللازم لإجراء التحويلات.

ولكن يمكنك القيام بخلاف ذلك: أوامر بديلة تتعلق بمعالجة كتل مختلفة من البيانات. بيانيا ، هذه الخيارات موضحة في الشكل. 3.

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

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

لكي يعمل رمز البرنامج هذا بدون وقت خمول ALU ، من الضروري أن يعمل كل مؤشر ترابط للبرنامج مع مجموعة التسجيلات الخاصة به. تصبح ذاكرة التخزين المؤقت في هذا المخطط عنق زجاجة (لها منفذا إخراج بيانات فقط) ، لذلك نقوم بتخزين المفاتيح في سجلات MMX. نظرًا لأنه في هذه الحالة ، تكون العقدان البديلة (والإزاحة) للقراءة فقط في الذاكرة ، فيمكن مشاركتها بواسطة كل من مؤشرات الترابط الخاصة بالبرنامج.

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

يتم تنفيذ طريقة التشفير المتوازي بشكل فعال فقط لوضع تشغيل المعالج 64 بت ، حيث يوجد في هذا الوضع كمية كافية من RON (ما يصل إلى 16 قطعة!). يظهر مثال على تنفيذ GOST وفقًا لهذه الطريقة في الملحق 2 (على القرص).

من الواضح أن تنفيذ GOST هذا له أداء كود يبلغ 2 RTTs. الآن دعونا نرى كيف يؤثر ذلك على وقت التنفيذ.

دورة التشفير لتيار واحد (الملحق 1) هي 352 دورة ، وخلال هذا الوقت يتم حساب 8 بايت من البيانات ، لتنفيذ ثنائي الدفق لـ GOST (الملحق 2) 416 دورة معالج مطلوبة ، ولكن يتم حساب 16 بايت. وبالتالي ، تزداد سرعة التحويل الناتجة من 80 إلى 144 ميجابايت لمعالج 3.6 جيجاهرتز.

تم الحصول على صورة مثيرة للاهتمام: يحتوي الكود بالضبط على ضعف عدد التعليمات ، ويستغرق وقتًا أطول بنسبة 15 ٪ فقط ، لكنني أعتقد أن القراء قد فهموا بالفعل سبب هذه الظاهرة ...

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

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

استخدام سجلات SSE وأوامر AVX للمعالجات الحديثة لتنفيذ GOST 28147-89

تتضمن معالجات الهندسة المعمارية الحديثة x86 / 64 مجموعة من سجلات SSE ذات 16 بايت ووحدات FPU متخصصة (اثنان على الأقل) لإجراء عمليات مختلفة على هذه السجلات. من الممكن تنفيذ GOST على هذا الجهاز ، وفي هذه الحالة ، لا يمكن وضع العقد البديلة في شكل جداول في ذاكرة الوصول العشوائي ، ولكن مباشرة على سجلات SSE المخصصة.

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

يتم تحديد هذه المتطلبات من خلال التحسين لمجموعة أوامر AVX الحالية. وبالتالي ، سيحتوي كل بايت من سجل SSE على اثنين من tetrads يقابلان بايتات مختلفة من سجل الإدخال لكتلة الاستبدال ، بينما يتوافق موضع البايت في سجل SSE بشكل فريد مع الفهرس في جدول الاستبدال لكتلة الاستبدال.

يظهر رسم تخطيطي لأحد المواضع المحتملة للعقد البديلة في سجلات SSE في الشكل. 4.

يؤدي وضع معلومات سرية لعقد الاستبدال في سجلات SSE إلى زيادة أمان المعالجة المشفرة ، ولكن يمكن عزل هذه المعلومات السرية تمامًا في ظل الظروف التالية:

• تم وضع نواة المعالج في وضع مضيف برنامج Hypervisor وتم تعطيل كتلة المقاطعة (APIC) بالقوة. في هذه الحالة ، يتم عزل نواة المعالج تمامًا عن نظام التشغيل والتطبيقات التي تعمل على تثبيت الحوسبة.
• يتم تحميل سجلات SSE وعزل النواة الحاسوبية قبل بدء نظام التشغيل ؛ من الأفضل تنفيذ هذه الإجراءات من وحدة التمهيد الموثوقة (TDM).
• يتم وضع برامج الإجراءات المشفرة وفقًا لـ GOST في منطقة الذاكرة غير القابلة للتعديل لوحدة الحوسبة (إما BIOS أو ذاكرة فلاش MDZ).

سيضمن الامتثال لهذه المتطلبات عزلًا تامًا وثباتًا لرمز إجراءات التشفير والمعلومات السرية المستخدمة فيها.

لأخذ العينات بشكل فعال من سجلات SSE للرباعيات ، يتم استخدام محولات البايت متعددة المدخلات المتوفرة في وحدات FPU. تسمح هذه المفاتيح بالتحويل من أي بايت من المصدر إلى أي بايت للوجهة ، بواسطة فهارس موجودة في سجل فهرس SSE خاص. علاوة على ذلك ، يتم إجراء النقل بالتوازي لجميع البايتات الـ 16 الخاصة بجهاز استقبال التسجيل SSE.

بوجود عقد تخزين بديلة على سجلات SSE ومفتاح متعدد المدخلات في وحدات FPU ، من الممكن تنظيم التحويل التالي في وحدة الاستبدال (الشكل 5).

في هذا المخطط ، يقوم سجل الإدخال في كل tetrad بتعيين عنوان المحول المقابل ، والذي ينقل المعلومات من محركات العقدة البديلة إلى سجل الإخراج عبر ناقل البيانات. يمكن تنظيم مثل هذا المخطط بثلاث طرق:

• قم بإنشاء تصميم رقاقة مناسب ، لكن هذا رائع بالنسبة لنا.
• لم تعد إعادة برمجة الرمز الصغير وإنشاء تعليمات المعالج الخاصة بك لتنفيذ هذه الوظيفة على المعالجات الحالية خيالًا ، ولكنها ، للأسف ، غير واقعية في الظروف الحالية.
• اكتب برنامجًا باستخدام أوامر AVX الرسمية. الخيار وإن لم يكن فعالا للغاية ، ولكن يمكننا تنفيذه "هنا والآن". إذن هذا ما سنفعله بعد ذلك.

يتم التحكم في المفاتيح بواسطة أمر خاص ثلاثي العناوين AVX VPSHUFB. معاملها الأول هو مستقبل المعلومات من المفاتيح ، والثاني هو المصدر الذي تتصل به مدخلات المفاتيح. المعامل الثالث هو سجل تحكم للمفاتيح ، يرتبط كل بايت منها بمفتاح مناظر ؛ تحدد القيمة الموجودة فيه رقم الاتجاه الذي يقرأ منه المفتاح المعلومات. للحصول على وصف لهذا الأمر من وثائق Intel الرسمية ، انظر الشكل. 5. في التين. يوضح الشكل 6 تشغيل هذا الأمر - يتم عرض نصف سجلات SSE فقط ، في النصف الثاني كل شيء متشابه.

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

تمت كتابة برنامج به مجموعة مختارة من دفاتر الملاحظات من خلال مفاتيح FPU ، لكنني لم أضعه في التطبيق - إنه رديء للغاية. إن وجود سجل 128 بت واستخدام 32 بت فقط فيه أمر غير احترافي.

كما يقولون ، "نهايتنا هي الأفق" ، لذا نضغط عليها بهذه الطريقة ... سنضغط عليها ونضعها في أكياس!

هذا ليس تلاعبًا بالكلمات ، ولكنه واقع قاسي لـ FPU - يمكن تقسيم سجلات SSE إلى أجزاء متساوية ويمكن إجراء نفس التحويلات على هذه الأجزاء بأمر واحد. لكي يفهم المعالج هذا ، هناك حرف سحري "P" - حزمة يتم وضعها قبل الأمر ذاكري ، ولا تقل عن الأحرف السحرية "Q" ، "D" ، "W" ، "B" ، والتي يتم وضعها في النهاية والإعلان عن الأجزاء التي يتم تقسيم سجلات SSE إليها في هذا الأمر.

نحن مهتمون بوضع الاندفاع مع تسجيل SSE مقسم إلى أربع كتل 32 بت ؛ وفقًا لذلك ، ستبدأ جميع الأوامر بـ "P" وتنتهي برمز "D". هذا يجعل من الممكن معالجة أربع كتل من 32 بت بالتوازي مع تعليمات معالج واحد ، أي لحساب أربع مجموعات من البيانات على التوازي.

البرنامج الذي يطبق هذه الطريقة متاح في الملحق 3 ، وهناك جميع التفسيرات.

ومع ذلك ، اضغط حتى اضغط! تحتوي المعالجات الحديثة على وحدتي FPU على الأقل ، ويمكن استخدام دفقتي تعليمات مستقلين لتحميلهما بالكامل. إذا قمت بإدخال أوامر متداخلة بشكل صحيح من تدفقات مستقلة ، فيمكنك تحميل كل من وحدات FPU بالكامل والحصول على ثمانية تدفقات بيانات معالجة متوازية في وقت واحد. تمت كتابة مثل هذا البرنامج ، ويمكنك رؤيته في الملحق 4 ، لكن عليك أن تنظر بعناية - يمكنك أن تصاب بالجنون. وهذا ما يسمى "الكود ليس للجميع ...".

سعر الإصدار

يعد استخدام سجلات SSE لتخزين العقد البديلة أمرًا مفهومًا - فهو يوفر ضمانًا معينًا لعزل المعلومات السرية ، ولكن معنى حساب وظيفة التشفير نفسها على FPU ليس واضحًا. لذلك ، تم أخذ قياسات وقت تنفيذ الإجراءات القياسية باستخدام طريقة الاستبدال المباشر وفقًا لـ GOST لأربعة وثمانية تدفقات.

لأربعة خيوط ، تم الحصول على سرعة تنفيذ 472 دورة معالج. وبالتالي ، بالنسبة للمعالج بتردد 3.6 جيجاهرتز ، يتم اعتبار خيط واحد بسرعة 59 ميجابايت في الثانية ، وأربعة خيوط على التوالي ، بسرعة 236 ميجابايت في الثانية.

بالنسبة لثمانية خيوط ، تم الحصول على سرعة تنفيذ 580 دورة معالج. وبالتالي ، بالنسبة لمعالج 3.6 جيجاهرتز ، يتم اعتبار خيط واحد بسرعة 49 ميجابايت في الثانية ، وثمانية خيوط بسرعة 392 ميجابايت في الثانية.

كما قد يلاحظ القارئ ، فإن الكود في المثال رقم 3 لديه معدل نقل قدره 4 RTT ، بينما الكود في المثال رقم 4 لديه معدل نقل 8 RTT. في هذه الأمثلة ، في سجلات SSE ، تكون الأنماط هي نفسها عند استخدام RON ، فقط المجدول هو الذي قلل من كفاءته. يوفر الآن زيادة بنسبة 20٪ في المدة لزيادة 2x في طول الشفرة.

علاوة على ذلك ، تم الحصول على هذه النتائج باستخدام أوامر AVX العالمية المتاحة في كل من معالجات Intel و AMD. إذا قمت بالتحسين من أجل معالج AMD ، فستكون النتيجة أفضل بكثير. يبدو مخالفاً للاتجاه ، ولكنه مع ذلك صحيح ، وإليكم السبب: تحتوي معالجات AMD على مجموعة إضافية من التعليمات ، ما يسمى بامتداد XOP ، وفي هذه المجموعة الإضافية من التعليمات ، هناك تلك التي تبسط بشكل كبير تنفيذ خوارزمية GOST.

يشير هذا إلى أوامر إزاحة الحزمة المنطقية للبايت والتحول الدوري للحزم للكلمات المزدوجة. تستخدم الأمثلة الواردة في الملحقين 3 و 4 متواليات من الأوامر العامة التي تنفذ التحويل الضروري: في الحالة الأولى ، أمر "إضافي" واحد ، وفي الحالة الأخرى ، أربعة أوامر إضافية في وقت واحد. لذلك هناك احتياطيات التحسين ، واحتياطيات كبيرة.

إذا كنا نتحدث عن مزيد من التحسين ، فمن الجدير أن نتذكر وجود سجلات 256 بت (سجلات YMM) ، والتي يمكنك نظريًا من خلالها مضاعفة سرعة العمليات الحسابية. لكن في الوقت الحالي ، هذا مجرد احتمال ، في الوقت الحالي ، تتباطأ المعالجات كثيرًا عند تنفيذ تعليمات 256 بت (FPUs لها مسار عرض 128 بت). أظهرت التجارب أنه في المعالجات الحديثة ، لا يعطي عدد 16 مؤشر ترابط في سجلات YMM أي مكاسب. ولكن هذا فقط في الوقت الحالي ، في طرز المعالجات الجديدة ، ستزداد سرعة تعليمات 256 بت بلا شك ، وبعد ذلك سيصبح استخدام 16 خيطًا متوازيًا مناسبًا وسيؤدي إلى زيادة أكبر في سرعة المعالجة المشفرة.

من الناحية النظرية ، يمكنك الاعتماد على سرعة 600-700 ميجابايت في الثانية إذا كان المعالج يحتوي على وحدتي FPU بعرض مسار عمل يبلغ 256 بت لكل منهما. في هذه الحالة ، يمكننا التحدث عن كتابة كود بكفاءة 16 RTT ، وهذا ليس خيالًا ، بل المستقبل القريب.

وضع مختلط

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

لا يمكنك الاعتماد على زيادة بنسبة 50٪ هنا ، عنق الزجاجة هو ذاكرة التخزين المؤقت حيث يتم تخزين الأقنعة التكنولوجية ، ولكن لا يزال بإمكانك الحصول على زيادة قدرها 100 ميغا بايت إضافية. هذا الخيار غير مدرج في الملاحق (وحدات الماكرو هي نفسها المستخدمة في كود 8 RTT) ، لكنها متوفرة في ملفات البرنامج. لذلك إذا كان أي شخص لا يؤمن بإمكانية التشفير بسرعة 500 ميغا بايت في الثانية على نواة معالج واحد ، دعه يقوم بتشغيل ملفات الاختبار. هناك أيضًا نصوص بها تعليقات حتى لا يظن أحد أنني مكر.

هذا التركيز ممكن فقط على معالجات Intel ، AMD لديها وحدتا FPU فقط لكل وحدتي معالج (مشابه لوضع التداول المفرط). ولكن هناك أربع وحدات ALU أخرى ، وهي خطيئة لا ينبغي استخدامها.

يمكنك تشغيل وحدات المعالج الخاصة بالبلدوزر في وضع مشابه لوضع التداول المفرط ، ولكن يمكنك تشغيل التحويل إلى RON على وحدات مختلفة في مؤشر ترابط واحد ، وإلى سجلات SSE في مؤشر ترابط آخر والحصول على نفس 12 RTT. لم أختبر هذا الخيار ، لكنني أعتقد أن الكود في 12 RTT سيعمل بكفاءة أكبر على AMD. أولئك الذين يرغبون في المحاولة ، يمكن تعديل برامج الاختبار للعمل على "الجرافات" بسهولة تامة.

من يحتاجها؟

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

علاوة على ذلك ، من الغريب أن تشفير خوارزمية AES المضمنة في المعالجات تبين أنه أبطأ بكثير ، وتظهر الاختبارات سرعة 100-150 ميغا بايت في الثانية ، وهذا مع تنفيذ الأجهزة للخوارزمية! تكمن المشكلة في العد أحادي الخيط وكتلة الاستبدال ، التي تعمل على بايت (جدول من 256 صفاً). لذلك تبين أن GOST أكثر كفاءة في التنفيذ على بنية x86 / 64 ، من كان يظن ...

هذا إذا تحدثنا عن المستوى الذي تم تحقيقه من سرعة التشفير. وإذا أخذنا في الاعتبار التحسينات النظرية في مجال تحسين كفاءة الكود ، فعلى الأرجح لن يحتاجها أحد. لا يوجد عمليًا متخصصون من المستوى 3-6 RTT ، يقوم المترجمون عمومًا بإنشاء رمز على مستوى 1-2.5 RTT ، ولا يعرف غالبية المبرمجين المجمّع ، وإذا كانوا يعرفون تهجئته ، فهم لا يفهمون جهاز معالج حديث. وبدون هذه المعرفة ، ما هو المجمع ، ما هو نوع من SI-sharp - لا يهم.

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

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

نيكولا كورتوا - "عظيم ورهيب"

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

في أكتوبر 2010 ، بدأت عملية النظر في إدراج خوارزمية GOST 28147-89 في المعيار الدولي ISO / IEC 18033-3. بالفعل في مايو 2011 ، ظهر مقال بقلم عالم التشفير الشهير نيكولاس كورتوا على الأرشيف الإلكتروني ePrint ، تميز بموقف غامض للغاية تجاهه من مجتمع التشفير العالمي. منشورات كورتوا هي مثال حزين على التلاعب بالمفاهيم ، والذي لا يكشف عن أي خصائص جديدة للموضوع المعني ، ولكن مع ادعاء الإحساس يثير انتشار الآراء الخاطئة حول خصائصه الحقيقية في بيئة غير كفؤة.

الطريقة الجبرية

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

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

يمكن وصف الطريقة الجبرية التي استغلها كورتوا بإيجاز على النحو التالي. في المرحلة الأولى ، يتم استخدام خصائص GOST 28147-89 هذه باعتبارها وجود نقطة ثابتة لجزء من تحويل التشفير ، وكذلك ما يسمى بنقطة الانعكاس. بسبب هذه الخصائص ، يتم اختيار عدة أزواج من عدد كبير بما فيه الكفاية من أزواج النص المشفر المفتوح ، مما يسمح لنا بالنظر في التحويلات ليس في 32 ، ولكن فقط في 8 جولات. تتكون المرحلة الثانية من حقيقة أنه ، بناءً على نتائج التحولات ذات الثماني جولات التي تم الحصول عليها في المرحلة الأولى ، يتم إنشاء نظام من المعادلات غير الخطية ، حيث يكون المجهول هو البتات الرئيسية. ثم يتم حل هذا النظام (يبدو هذا بسيطًا ، ولكنه في الواقع الجزء الأكثر استهلاكا للوقت من الطريقة ، لأن النظام يتكون من معادلات غير خطية).

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

الطريقة التفاضلية

فكر في طريقة كورتوا الثانية ، والتي تقوم على تحليل التعمية التفاضلي.

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

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

يستخدم كورتوا نسخة معدلة قليلاً من الطريقة التفاضلية. على الفور ، نلاحظ أن كورتوا يجري تحليله لـ S-box التي تختلف عن تلك الحالية عن تلك المقترحة في ISO. تقدم الورقة خصائص تفاضلية (الأرقام ذاتها التي يجب أن تختلف فيها الكتل) لعدد صغير من الجولات. الأساس المنطقي لتمديد الإحصائيات لمزيد من الجولات هو ، كالعادة ، على أساس "الحقائق". يعبر كورتوا ، مرة أخرى ، بدون أي شيء سوى سلطته ، عن افتراض لا أساس له من أن تغيير صناديق S لن يؤثر على مقاومة GOST 28147-89 ضد هجومها (في نفس الوقت ، لأسباب غير معروفة ، صناديق S من العمل الأول لم يتم النظر في مسودة الملحق للمعيار ISO / IEC 18033-3). يُظهر التحليل الذي أجراه مؤلفو المقال أنه حتى لو أخذنا "حقائق" كورتوا التي لا أساس لها من الصحة حول الإيمان وقمنا بتحليل GOST 28147-89 مع صناديق S أخرى ، فإن الهجوم مرة أخرى لن يكون أفضل من تعداد كامل.

تم إجراء تحليل مفصل لأعمال كورتوا مع تبرير مفصل لعدم وجود أساس لجميع التصريحات حول انخفاض استقرار المعيار الروسي في [،].

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

وتجدر الإشارة إلى أن أعمال كورتوا تعرضت لانتقادات متكررة من قبل الباحثين الأجانب أيضًا. على سبيل المثال ، احتوى عمله على بناء الهجمات على خوارزمية تشفير كتلة AES باستخدام طريقة XSL على نفس العيوب الأساسية مثل العمل في تحليل المعيار الروسي: تظهر معظم تقديرات كثافة اليد العاملة في النص لا أساس لها تمامًا ولا أساس لها - يمكن العثور على نقد مفصل ، على سبيل المثال ، في العمل. بالإضافة إلى ذلك ، يعترف كورتوا نفسه برفض واسع النطاق لنشر عمله في مؤتمرات التشفير الكبرى وفي المجلات الراسخة التي راجعها الأقران ، مما يترك له في كثير من الأحيان فرصة التحدث فقط في قسم الإعلان القصير. هذا ، على سبيل المثال ، يمكن قراءته في القسم 3 من العمل. فيما يلي بعض الاقتباسات التي اقتبسها كورتوا نفسه والمتعلقة بعمله:

• "أعتقد أن جمهور Asiacrypt لن يشعر أنه مثير للاهتمام." مراجع Asiacrypt 2011.
• "... هناك مشكلة كبيرة ، كبيرة ، كبيرة: هذا الهجوم ، وهو المساهمة الرئيسية للورقة ، تم نشره بالفعل في FSE’11 (كان حتى أفضل ورقة) ، ...". المراجع المشفر 2011.

وبالتالي ، فإن الجزء المهني من مجتمع التشفير الدولي يتعامل مع جودة عمل كورتوا دون أدنى شك من ، على سبيل المثال ، تصريحات بعض المتخصصين الروس حول قدرتهم على اختراق AES لـ 2100 ، أو "الإثباتات" التالية لصفحتين من الفرضية ، التي لم تؤكدها أي حسابات متسقة.على عدم المساواة في فئتي التعقيد P و NP.

هجمات Isobe و Dinur-Dunkelman-Shamir

الفكرة العامة لهجمات Isobe () و Dinur-Dankelman-Shamir (المشار إليها فيما يلي: DDSH attack) () هي إنشاء مجموعة ضيقة معينة (تعتمد على المفتاح) من النصوص الصريحة المكافئة للتحويل على هذه المجموعة ، والتي لها أبسط من تحويل التشفير نفسه. في حالة طريقة Isobe ، هذه هي مجموعة كتل 64 بت x بحيث أن F 8-1 (Swap (F 8 (z))) = z ، حيث z = F 16 (x) ، عبر F 8 ( x) و F 16 (x) هي أول 8 جولات وأول 16 جولة من التشفير GOST 28147-89 ، على التوالي ، من خلال Swap - عملية تبديل نصفي كلمة 64 بايت. عندما يدخل النص العادي في هذه المجموعة ، تتزامن نتيجة التحويل الكامل المكون من 32 جولة لـ GOST 28147-89 مع نتيجة الجولة الـ16 ، التي استغلها مؤلف الهجوم. في حالة طريقة DDS ، هذه هي مجموعة x بحيث أن F 8 (x) = x (النقطة الثابتة للتحويل F 8). بالنسبة إلى أي نص عادي من هذه المجموعة ، يعمل تحويل GOST 28147-89 تمامًا مثل آخر 8 جولات ، مما يبسط التحليل.

تعقيد هجوم Isobe هو 2224 عملية تشفير ، هجوم LDS هو 2192. ومع ذلك ، تتم إزالة جميع الأسئلة حول ما إذا كان يتبع ذلك أن هجمات Isobe و DDSH تفرض قيودًا جديدة على شروط استخدام الخوارزمية الخاصة بنا من خلال تقييم متطلبات كمية المواد اللازمة لتنفيذ كل هجوم: تتطلب طريقة Isobe 32 زوجًا من النص العادي والنص المشفر ، ولأسلوب DDSH - 2 64. تعتبر معالجة مثل هذه الأحجام من المواد دون تغيير المفتاح أمرًا غير مقبول مسبقًا لأي تشفير كتلة بطول الكتلة 64: على مادة بحجم 2 32 ، مع مراعاة مشكلة أعياد الميلاد (انظر ، على سبيل المثال ، إلى الدخيل القدرة على استخلاص استنتاجات معينة حول النصوص العادية من النصوص المشفرة دون تحديد المفتاح. إن وجود 264 زوجًا من النصوص المفتوحة والمشفرة التي تم الحصول عليها على نفس المفتاح يسمح بالفعل للخصم بإجراء عمليات التشفير وفك التشفير دون معرفة هذا المفتاح على الإطلاق. يرجع هذا إلى خاصية اندماجية بحتة: يمتلك الخصم في هذه الحالة جدول تحويل التشفير بالكامل. هذا الوضع غير مقبول على الإطلاق في ظل أي متطلبات تشغيلية معقولة. على سبيل المثال ، في CryptoPro CSP ، هناك قيود فنية على كمية المواد المشفرة (بدون تحويل المفتاح) البالغة 4 ميجا بايت (انظر). وبالتالي ، فإن الحظر الصارم على استخدام مفتاح على مادة بهذا الحجم متأصل في أي تشفير كتلة بطول كتلة 64 بت ، وبالتالي ، فإن هجمات Isobe و DDSH لا تضيق بأي حال من الأحوال منطقة الاستخدام من خوارزمية GOST 28147-89 مع الحفاظ على أقصى قدر ممكن من الأمان 2256.

بالطبع ، تجدر الإشارة إلى أن الباحثين (Isobe و Dinur-Dankelman-Shamir) أظهروا أن بعض خصائص خوارزمية GOST 28147-89 تجعل من الممكن العثور على مسارات التحليل التي لم يتم أخذها في الاعتبار من قبل مبتكري الخوارزمية. يسمح الشكل البسيط للجدول الرئيسي ، الذي يبسط إلى حد كبير مهمة إنشاء تطبيقات فعالة ، أيضًا ببناء أوصاف أبسط للتحولات التي تقوم بها الخوارزمية لبعض الحالات النادرة للمفاتيح والنصوص الصريحة.

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

نلاحظ أن بعض الإهمال في تقديرات متوسط ​​مدخلات العمل موجود أيضًا في عمل Dinur و Dankelman و Shamir. وبالتالي ، عند إنشاء هجوم ، لا يتم إيلاء الاهتمام الواجب للنقطة التالية: بالنسبة لنسبة كبيرة من المفاتيح ، فإن مجموعة النصوص العادية x ، بحيث تكون F 8 (x) = x ، فارغة: 8 جولات من التحويل قد لا تكون ببساطة لديك نقاط ثابتة. يعتمد وجود النقاط الثابتة أيضًا على اختيار العقد البديلة. وبالتالي ، فإن الهجوم لا ينطبق إلا على بعض العقد والمفاتيح البديلة.

تجدر الإشارة أيضًا إلى عمل آخر بهجوم على GOST 28147-89. في فبراير 2012 ، ظهرت نسخة محدثة من المقالة (بتاريخ نوفمبر 2011) على الأرشيف الإلكتروني ePrint لجمعية التشفير الدولية ، والتي احتوت على هجوم جديد على GOST 28147-89. خصائص الهجوم المقدم هي كما يلي: حجم المادة 232 (كما هو الحال مع Isobe) ، وكثافة العمالة 2192 (كما هو الحال مع DDSh). وبالتالي ، أدى هذا الهجوم إلى تحسين هجوم LDS الذي حطم الرقم القياسي من حيث حجم المواد من 264 إلى 2 32. نلاحظ بشكل منفصل أن المؤلفين قدموا بصدق جميع الحسابات مع تبرير تعقيد وحجم المادة. بعد 9 أشهر ، تم العثور على خطأ جوهري في الحسابات المذكورة أعلاه ، ومنذ نوفمبر 2012 ، لم تعد النسخة المحدثة من المقال في الأرشيف الإلكتروني تحتوي على أي نتائج تتعلق بالخوارزمية المحلية.

تعتمد الهجمات على افتراض أن المهاجم يعرف "شيئًا" عن المفاتيح

أخيرًا ، نلاحظ أن هناك أيضًا عددًا من الأعمال في الأدبيات (انظر ، على سبيل المثال ، و) مخصصة للهجمات على GOST 28147-89 في ما يسمى بالنموذج مع المفاتيح المرتبطة. يحتوي هذا النموذج أساسًا على افتراض حول إمكانية وصول متطفل إلى التحليل ليس فقط لأزواج من النصوص المفتوحة والمشفرة باستخدام المفتاح المطلوب ، ولكن أيضًا لأزواج من النصوص المفتوحة والمشفرة التي تم الحصول عليها باستخدام مفاتيح (غير معروفة أيضًا) تختلف عن الطريقة المعتادة المعروفة (على سبيل المثال ، في مواضع البت الثابتة). في هذا النموذج ، من الممكن بالفعل الحصول على نتائج مثيرة للاهتمام حول GOST 28147-89 ، ومع ذلك ، في هذا النموذج ، لا يمكن الحصول على نتائج أقل قوة حول ، على سبيل المثال ، معيار AES الذي أصبح أكثر انتشارًا في الشبكات العامة الحديثة (انظر ، على سبيل المثال،). لاحظ أن شروط تنفيذ مثل هذه الهجمات تنشأ عند استخدام تشفير في بروتوكول معين. وتجدر الإشارة إلى أن النتائج من هذا النوع ، على الرغم من أنها ذات أهمية أكاديمية لا شك فيها من وجهة نظر دراسة خصائص تحويلات التشفير ، إلا أنها في الواقع لا تنطبق على الممارسة. على سبيل المثال ، جميع أدوات حماية المعلومات المشفرة المعتمدة من قبل FSB في روسيا تفي بالمتطلبات الأكثر صرامة لأنظمة توليد مفتاح التشفير (انظر ، على سبيل المثال ،). كما هو موضح في نتائج التحليل ، في ظل وجود 18 مفتاحًا مرتبطًا و 2 10 أزواج من الكتل النصية المفتوحة والمشفرة ، فإن تعقيد فتح المفتاح الخاص بالكامل ، مع احتمال نجاح 1-10-4 ، هو بالفعل 2 26. ومع ذلك ، إذا تم استيفاء المتطلبات المذكورة أعلاه لتطوير المواد الرئيسية ، فإن احتمال العثور على هذه المفاتيح هو 2-4352 ، أي 24096 مرة أقل مما لو حاولت فقط تخمين المفتاح السري في المحاولة الأولى.

تشمل الأعمال المتعلقة بالنموذج مع المفاتيح المرتبطة أيضًا العمل الذي أحدث ضجة كبيرة في عام 2010 في المنشورات الإلكترونية الروسية التي لا تعاني من عادة التحقق بعناية من المواد في عملية مطاردة الأحاسيس. النتائج الواردة فيه لم تكن مدعومة بأي تبرير صارم ، لكنها احتوت على تصريحات صاخبة حول إمكانية اختراق معيار الدولة للاتحاد الروسي على جهاز كمبيوتر محمول ضعيف في غضون ثوانٍ - بشكل عام ، تمت كتابة المقال بأفضل التقاليد نيكولا كورتوا. ولكن ، على الرغم مما هو واضح تمامًا للقارئ ، فهو أكثر أو أقل دراية بالمبادئ الأساسية للمنشورات العلمية ، وعدم وجود أي أساس للمقالة ، إلا أنه كان على وجه التحديد طمأنة الجمهور الروسي بأن رودسكي كتب نصًا مفصلاً ومفصلاً بعد العمل ، يحتوي على تحليل شامل لهذا النقص. المقالة التي تحمل عنوانًا معبرًا "حول الأهمية العملية الصفرية للعمل" هجوم استرداد المفتاح على تشفير كتلة GOST الكامل بدون وقت وذاكرة "" يبرر حقيقة أن متوسط ​​تعقيد الطريقة المعطاة في الطريقة لا يقل عن تعقيد التعداد الكامل.

المخلفات الجافة: ما هي المقاومة عمليًا؟

في الختام ، نقدم جدولًا يحتوي على بيانات حول جميع نتائج الهجمات الموصوفة والمبررة بدقة على GOST 28147-89 المعروفة لمجتمع التشفير الدولي. لاحظ أنه يتم إعطاء التعقيد في عمليات التشفير لخوارزمية GOST 28147-89 ، والذاكرة والمواد محددة في كتل الخوارزمية (64 بت = 8 بايت).

هجوم	كثافة اليد العاملة	ذاكرة	المواد المطلوبة
إيزوبي	2 224	2 64	2 32
Dinur-Dunkelman-Shamir، FP، 2DMitM	2 192	2 36	2 64
Dinur-Dunkelman-Shamir ، FP ، ذاكرة منخفضة	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dunkelman-Shamir ، انعكاس ، 2DMitM	2 236	2 19	2 32
القوة الغاشمة	2 256	1	4
عدد النانوثانية منذ بداية الكون	2 89

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

في بلدنا ، توجد خوارزمية موحدة للتمثيل المشفر للبيانات لأنظمة معالجة المعلومات في شبكات الكمبيوتر وأنظمة الكمبيوتر الفردية وأجهزة الكمبيوتر ، والتي يتم تحديدها بواسطة GOST 28147-89.

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

عند وصف الخوارزمية ، يتم استخدام الترميز التالي:

L و R هي متواليات بت ؛
LR هو تسلسل التسلسل L و R ، حيث تتبع بتات التسلسل R بتات التسلسل L ؛
(+) - طريقة إضافة bitwise 2 (عملية "OR" حصرية) ؛
[+] - إضافة أرقام 32 بت المقياس 2 32 ؛
(+) - إضافة أرقام 32 بت ، المقياس 2 32-1.

يتم تلخيص الأرقام وفقًا للقاعدة التالية:

A [+] B = A + B إذا كان A + B< 2 32 ,
A [+] B = A + B - 2 32 إذا كان A + B> = 32 2. أ (+) ب = أ + ب إذا أ + ب< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

توفر الخوارزمية أربعة أوضاع للتشغيل:

على أي حال ، يتم استخدام مفتاح 256 بت K لتشفير البيانات ، والتي يتم تمثيلها على شكل ثمانية مفاتيح فرعية 32 بت K i:

ك = ك 7 ك 6 ك 5 ك 4 ك 3 ك 2 ك 1 ك 0.

يتم تنفيذ فك التشفير بنفس مفتاح التشفير ، ولكن هذه العملية هي عكس عملية تشفير البيانات.

وضع المبادلة السهل

الوضع الأول والأسهل - إستبدال. البيانات المراد تشفيرها مقسمة إلى كتل 64 بت. يتضمن إجراء التشفير الخاص بفدرة البيانات المفتوحة T 0 32 دورة (j = 1 ... 32).

يتم تقسيم الكتلة T 0 إلى متتابعين من 32 بت: B (0) A (0) ، حيث B (0) هي البتات اليسرى أو الأكثر أهمية ، A (0) هي البتات اليمنى أو الأقل أهمية.

يتم إدخال هذه التسلسلات في محركات الأقراص N 1 و N 2 قبل بدء دورة التشفير الأولى.

يتم وصف الدورة الأولى (j = 1) من إجراء التشفير لكتلة بيانات 64 بت بالصيغ التالية:

هنا أشير إلى رقم التكرار (أنا = 1 ، 2 ، ... ، 32).

تسمى الوظيفة f وظيفة التشفير. وسيطتها هي مقياس المجموع 2 32 للرقم A (i) الذي تم الحصول عليه في خطوة التكرار السابقة والرقم X (j) للمفتاح (أبعاد كل من هذه الأرقام هي 32 رقمًا).

تتضمن وظيفة التشفير عمليتين على مجموع 32 بت الناتج. العملية الأولى تسمى الاستبدال K. تتكون كتلة الاستبدال K من 8 عقد استبدال K (1) ... K (8) بذاكرة 64 بت لكل منها. يتم تقسيم متجه 32 بت الذي يصل إلى كتلة الاستبدال إلى 8 متجهات متتالية 4 بت ، يتم تحويل كل منها إلى متجه 4 بت بواسطة العقدة البديلة المقابلة ، وهو جدول مكون من 16 عددًا صحيحًا في النطاق 0 .. .15.

يحدد متجه الإدخال عنوان الصف في الجدول الذي يكون رقمه هو متجه الإخراج. يتم بعد ذلك دمج متجهات الإخراج ذات 4 بتات بشكل تسلسلي في متجه 32 بت. يحتوي جدول كتلة الاستبدال K على عناصر أساسية مشتركة في شبكة الكمبيوتر ونادرًا ما يتم تغييرها.

العملية الثانية هي التحول الدوري الأيسر لمتجه 32 بت الذي تم الحصول عليه عن طريق استبدال K. يتم تمثيل كتلة البيانات المشفرة 64 بت T w على أنها T w = A (32) B (32).

يتم تشفير باقي كتل البيانات المفتوحة في وضع الاستبدال البسيط بنفس الطريقة.

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

وضع جاما

البيانات المفتوحة ، مقسمة إلى كتل 64 بت T (i) (i = 1 ، 2 ، ... ، m ، حيث يتم تحديد m بمقدار البيانات المشفرة) ، يتم تشفيرها في وضع جاما عن طريق إضافة نمط 2 باستخدام جاما المشفرة Гw ، والتي يتم إنتاجها في كتل من 64 بت ، أي Гw = (Г (1) ، Г (2) ، ... ، Г (i) ، ... ، Г (م)).

يمكن تمثيل معادلة تشفير البيانات في وضع جاما على النحو التالي:

W (i) = A (Y (i-1) [+] C2، Z (i-1) (+) C1) (+) T (i) = G (i) (+) T (i).
هنا W (i) عبارة عن كتلة نص مشفر 64 بت ،
أ - وظيفة التشفير في وضع الاستبدال البسيط (الوسيطات لهذه الوظيفة هي رقمان 32 بت) ،
C1 و C2 - الثوابت المحددة في GOST 28147-89 ،
Y (i) و Z (i) عبارة عن كميات يتم تحديدها بشكل متكرر حيث يتم تكوين جاما على النحو التالي:
(Y (0) ، Z (0)) = A (S) ، حيث S عبارة عن تسلسل ثنائي 64 بت (رسالة مزامنة) ؛
(Y (i)، Z (i)) = (Y (i-1) [+] C2، Z (i-1) (+) C1) لـ i = 1، 2، ...، m.

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

وضع غاما ردود الفعل

وضع التحجيممع الملاحظات يشبه إلى حد بعيد وضع جاما. كما هو الحال في وضع جاما ، يتم تشفير البيانات المفتوحة المقسمة إلى كتل من 64 بت T (i) (i = 1 ، 2 ، ... ، m ، حيث يتم تحديد m من خلال كمية البيانات المشفرة) ، يتم تشفيرها بواسطة وحدة إضافة ثنائية البت باستخدام تشفير gamma G sh ، والذي يتم إنتاجه في كتل من 64 بت:

Гw = (Г (1) ، Г (2) ، ... ، Г (i) ، ... ، Г (م)).

قد يكون عدد البتات في الكتلة T (m) أقل من 64 ، بينما يتم تجاهل جزء غاما المشفر من الكتلة G (m) الذي لا يستخدم للتشفير.

يمكن تمثيل معادلة تشفير البيانات في وضع جاما مع التغذية الراجعة على النحو التالي:

هنا W (i) عبارة عن كتلة نص مشفر 64 بت ،
أ - وظيفة التشفير في وضع الاستبدال البسيط. وسيطة الوظيفة في الخطوة الأولى من الخوارزمية التكرارية هي رسالة مزامنة 64 بت ، وفي جميع الخطوات اللاحقة - الكتلة السابقة للبيانات المشفرة W (i-1).

إدراجات التقليد

عمليات التطوير أكوام التقليدموحد لأي من أوضاع تشفير البيانات.

إدراج التقليد عبارة عن كتلة من بتات p (إدخال تقليد Ip) ، والتي يتم إنتاجها إما قبل تشفير الرسالة بأكملها ، أو بالتوازي مع تشفير كتلة تلو كتلة. قد تحتوي الكتل الأولى من البيانات المفتوحة التي تشارك في تطوير محاكاة الإدراج على معلومات الخدمة (على سبيل المثال ، جزء العنوان والوقت ورسالة المزامنة) ولا يتم تشفيرها. يتم تحديد قيمة المعلمة p (عدد الأرقام الثنائية في الإدخال المحاكي) من خلال متطلبات التشفير ، مع الأخذ في الاعتبار حقيقة أن احتمال فرض تداخل خاطئ هو 1/2 ^ p.

للحصول على محاكاة الإدراج ، يتم تمثيل البيانات المفتوحة على أنها كتل من 64 بت T (i) (i = 1 ، 2 ، ... ، m ، حيث يتم تحديد m بكمية البيانات المشفرة). تخضع الكتلة الأولى من البيانات المفتوحة T (1) لعملية تحويل تقابل أول 16 دورة من خوارزمية التشفير في وضع الاستبدال البسيط. علاوة على ذلك ، يتم استخدام المفتاح المستخدم لتشفير البيانات كمفتاح لتوليد إدراج التقليد.

يتم جمع رقم 64 بت الذي تم الحصول عليه بعد 16 دورة عمل بوحدة 2 مع فدرة البيانات المفتوحة الثانية T (2). تخضع نتيجة الجمع مرة أخرى للتحول المقابل لأول 16 دورة من خوارزمية التشفير في وضع الاستبدال البسيط. تمت إضافة رقم 64 بت الناتج إلى النموذج 2 إلى فدرة البيانات المفتوحة الثالثة T (3) ، وهكذا. الكتلة الأخيرة T (m) ، إذا لزم الأمر ، مبطن إلى كتلة كاملة 64 بت مع أصفار ، يتم جمعها بالمقياس 2 نتيجة العمل في الخطوة m-1 ، وبعد ذلك يتم تشفيرها في وضع الاستبدال البسيط على الأول 16 دورة من الخوارزمية. من رقم 64 بت المستلم ، يتم تحديد مقطع Ip بطول p بتات.

يتم إرسال Ip المقلد عبر قناة اتصال أو إلى ذاكرة الكمبيوتر بعد البيانات المشفرة. يتم فك تشفير البيانات الواردة المشفرة ، ومن الكتل المتلقاة من البيانات المفتوحة T (i) يتم إنشاء إدراج Ip التقليد ، والذي تتم مقارنته بعد ذلك بإدخال IR المتلقى من قناة الاتصال أو من ذاكرة الكمبيوتر. إذا تم إدراج التقليد لا تتطابق ، جميع البيانات التي تم فك تشفيرها تعتبر خاطئة.

خوارزمية التشفير GOST 28147-89 ، واستخدامها وتنفيذ البرامج لأجهزة الكمبيوتر الخاصة بمنصة Intel x86.

أندريه فينوكوروف

وصف الخوارزمية.

الشروط والتعيينات.

يرد وصف معيار التشفير الخاص بالاتحاد الروسي في وثيقة مثيرة جدًا للاهتمام بعنوان "GOST 28147-89 Cryptographic Transformation Algorithm". حقيقة أنه في عنوانه ، بدلاً من مصطلح "تشفير" ، مفهوم أكثر عمومية " تحويل التشفير ليس من قبيل الصدفة. بالإضافة إلى العديد من إجراءات التشفير وثيقة الصلة ، تصف الوثيقة خوارزمية واحدة للإنشاء إدراج التقليد . هذا الأخير ليس أكثر من مجموعة تحكم تشفير ، أي رمز تم إنشاؤه من البيانات الأصلية باستخدام مفتاح سري من أجل حماية التقليد ، أو حماية البيانات من التغييرات غير المصرح بها.

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

يُشار إلى عناصر البيانات في هذه المقالة بأحرف لاتينية كبيرة بخط مائل (على سبيل المثال ، X). من خلال | X| يشير إلى حجم عنصر البيانات Xفي بت. وبالتالي ، إذا فسرنا عنصر البيانات Xفي صورة عدد صحيح غير سالب ، يمكننا كتابة المتباينة التالية:

إذا كان عنصر البيانات يتكون من عدة عناصر ذات حجم أصغر ، فسيتم الإشارة إلى هذه الحقيقة على النحو التالي: X=(X 0 ,X 1 ,…,X ن –1)=X 0 ||X 1 ||…||X ن-1. يسمى الإجراء الخاص بدمج العديد من عناصر البيانات في عنصر واحد سلسلة البيانات ويشار إليها بالرمز "||". بطبيعة الحال ، يجب أن تكون العلاقة التالية مناسبة لأحجام عناصر البيانات: | X|=|X 0 |+|X 1 |+…+|X ن-1 |. عند تحديد عناصر البيانات المعقدة وعملية التسلسل ، يتم سرد عناصر البيانات المكونة بترتيب تصاعدي للأولوية. بمعنى آخر ، إذا فسرنا العنصر المركب وجميع عناصر البيانات المضمنة فيه على أنها أعداد صحيحة بدون إشارة ، فيمكننا كتابة المساواة التالية:

في الخوارزمية ، يمكن تفسير عنصر البيانات على أنه مصفوفة من البتات الفردية ، وفي هذه الحالة يتم الإشارة إلى البتات بنفس الحرف مثل المصفوفة ، ولكن في الحالة الصغيرة ، كما هو موضح في المثال التالي:

X=(x 0 ,x 1 ,…,x ن –1)=x 0 +2 1 x 1 +…+2 ن-1 · x ن –1 .

وهكذا ، إذا انتبهت ، فإن ما يسمى ب. ترقيم الأرقام "الصغير" ، أي ضمن كلمات البيانات متعددة البتات ، تكون الأرقام الثنائية الفردية ومجموعاتها ذات الأرقام الأصغر أقل أهمية. هذا مذكور صراحة في الفقرة 1.3 من المعيار: "عند إضافة متجهات ثنائية وتحويلها دوريًا ، فإن البتات الأعلى هي بتات المجمعات ذات الأعداد الكبيرة." علاوة على ذلك ، تنص فقرات المعيار 1.4 و 2.1.1 وغيرها على البدء في ملء سجلات التخزين لجهاز التشفير الافتراضي ببيانات من السجلات السفلية ، أي الرتب الأقل أهمية. تم اعتماد نفس ترتيب الترقيم بالضبط في بنية المعالجات الدقيقة Intel x86 ، وهذا هو السبب في أن تنفيذ البرنامج للتشفير في هذه البنية لا يتطلب أي تباديل إضافي للبتات داخل كلمات البيانات.

إذا تم تنفيذ بعض العمليات على عناصر بيانات لها معنى منطقي ، فمن المفترض أن يتم تنفيذ هذه العملية على وحدات البت المقابلة للعناصر. بعبارة أخرى أ ب=(أ 0 ب 0 ,أ 1 ب 1 ,…,أ –1 ب ن–1) ، أين ن=|أ|=|ب| ، والرمز "" يشير إلى عملية منطقية ثنائية عشوائية؛ عادة ما يشير إلى العملية حصري أو ، وهي أيضًا عملية الجمع 2:

منطق بناء التشفير وهيكل المعلومات الأساسية لـ GOST.

إذا كنت تدرس بعناية GOST 28147–89 الأصلي ، فستلاحظ أنه يحتوي على وصف لخوارزميات عدة مستويات. في الجزء العلوي توجد خوارزميات عملية مصممة لتشفير مصفوفات البيانات وتطوير إدخالات مزيفة لها. تستند جميعها إلى ثلاث خوارزميات منخفضة المستوى تسمى GOST في النص دورات . يشار إلى هذه الخوارزميات الأساسية في هذه المقالة باسم الدورات الأساسية لتمييزها عن جميع الحلقات الأخرى. لديهم الأسماء والتسميات التالية ، والأخيرة ترد بين قوسين وسيتم شرح معناها لاحقًا:

• دورة التشفير (32-3) ؛
• دورة فك التشفير (32 ف) ؛
• دورة توليد ملحق مقلد (16-З).

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

وبالتالي ، من أجل فهم GOST ، تحتاج إلى فهم الأشياء الثلاثة التالية:

• ماذا حدث خطوة أساسية تحويلات التشفير
• كيف تتكون الدورات الأساسية من الخطوات الرئيسية ؛
• مثل من أصل ثلاثة الدورات الأساسية اجمع كل الخوارزميات العملية لـ GOST.

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

الخطوة الرئيسية في تحويل العملات المشفرة.

خطوة تحويل التشفير الرئيسية هي في الأساس عامل يحدد تحويل كتلة بيانات 64 بت. معلمة إضافية لهذا المشغل هي كتلة 32 بت ، والتي تستخدم أي عنصر من عناصر المفتاح. يظهر مخطط خوارزمية الخطوة الرئيسية في الشكل 1.

الشكل 1. مخطط للخطوة الرئيسية للتحويل المشفر لخوارزمية GOST 28147-89.

فيما يلي تفسيرات لخوارزمية الخطوة الرئيسية:

الخطوة 0

• ن- كتلة بيانات 64 بت ليتم تحويلها ، أثناء تنفيذ الخطوة الأقل أهمية ( ن 1) وما فوق ( ن 2) يتم التعامل مع الأجزاء كأعداد صحيحة منفصلة 32 بت بدون إشارة. وهكذا ، يمكن للمرء أن يكتب N =(ن 1 ,ن 2).
• X- عنصر أساسي 32 بت ؛

الخطوة 1

الإضافة بمفتاح. يضاف النصف السفلي من الكتلة المحولة إلى modulo 2 32 مع العنصر الرئيسي المستخدم في الخطوة ، ويتم تمرير النتيجة إلى الخطوة التالية ؛

الخطوة 2

استبدال الكتلة. يتم تفسير القيمة 32 بت التي تم الحصول عليها في الخطوة السابقة على أنها مصفوفة من ثماني فدرات شفرة 4 بت: S =(س 0 , س 1 , س 2 , س 3 , س 4 , س 5 , س 6 , س 7) و س 0 يحتوي على 4 أصغر منها ، و س 7 - 4 بتات الأكثر أهمية س.

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

الخطوه 3

استدر لليسار بمقدار 11 بت. يتم إزاحة نتيجة الخطوة السابقة دوريًا بمقدار 11 بت نحو البتات الأعلى ويتم نقلها إلى الخطوة التالية. في مخطط الخوارزمية ، يشير الرمز إلى وظيفة التحول الدوري لحجته بمقدار 11 بتًا إلى اليسار ، أي نحو المستويات الأعلى.

الخطوة 4

إضافة Bitwise: تضاف القيمة التي تم الحصول عليها في الخطوة 3 إلى الوضع 2 بتًا فشيئًا إلى النصف الأعلى من الكتلة التي يتم تحويلها.

الخطوة الخامسة

التحول على طول السلسلة: يتم نقل الجزء السفلي من الكتلة المحولة إلى مكان الجزء الأقدم ، ويتم وضع نتيجة الخطوة السابقة في مكانها.

الخطوة 6

يتم إرجاع القيمة الناتجة للكتلة المراد تحويلها نتيجة لتنفيذ خوارزمية خطوة تحويل التشفير الرئيسية.

الدورات الأساسية لتحولات التشفير.

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

الدورات الأساسية مبنية من الخطوات الأساسية تمت مناقشة تحويل التشفير في القسم السابق. أثناء تنفيذ الخطوة الرئيسية ، يتم استخدام عنصر رئيسي واحد فقط 32 بت ، بينما يحتوي مفتاح GOST على ثمانية من هذه العناصر. لذلك ، من أجل استخدام المفتاح بالكامل ، يجب أن تؤدي كل حلقة أساسية بشكل متكرر الخطوة الرئيسية بعناصرها المختلفة. في الوقت نفسه ، يبدو من الطبيعي تمامًا أنه في كل دورة أساسية ، يجب استخدام جميع عناصر المفتاح بنفس عدد المرات ؛ لأسباب تتعلق بأمان التشفير ، يجب أن يكون هذا الرقم أكثر من واحد.

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

دورة التشفير 32-Z:

ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 ,ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 ,ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 ,ك 7 ,ك 6 ,ك 5 ,ك 4 ,ك 3 ,ك 2 ,ك 1 ,ك 0 .

الشكل 2 أ. مخطط دورة التشفير 32-3

دورة فك التشفير 32-P:

ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 ,ك 7 ,ك 6 ,ك 5 ,ك 4 ,ك 3 ,ك 2 ,ك 1 ,ك 0 ,ك 7 ,ك 6 ,ك 5 ,ك 4 ,ك 3 ,ك 2 ,ك 1 ,ك 0 ,ك 7 ,ك 6 ,ك 5 ,ك 4 ,ك 3 ,ك 2 ,ك 1 ,ك 0 .

الشكل 2 ب. 32-P مخطط حلقة فك التشفير

دورة إنتاج التقليد ، ملحق 16-З:

ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 ,ك 0 ,ك 1 ,ك 2 ,ك 3 ,ك 4 ,ك 5 ,ك 6 ,ك 7 .

الشكل 2 ج. مخطط دورة إنتاج التقليد إدراج 16-З.

كل دورة لها تصنيف أبجدي رقمي خاص بها ، يتوافق مع النمط " n-X "، حيث العنصر الأول من التعيين ( ن) ، يحدد عدد مرات تكرار الخطوة الرئيسية في الدورة ، والعنصر الثاني من التدوين ( X) ، حرف ، يحدد ترتيب التشفير ("З") أو فك التشفير ("Р") في استخدام العناصر الأساسية. يحتاج هذا الطلب إلى مزيد من التوضيح:

يجب أن تكون دورة فك التشفير هي عكس دورة التشفير ، أي أن التطبيق المتسلسل لهاتين الدورتين على كتلة عشوائية يجب أن يؤدي إلى الكتلة الأصلية ، والتي تنعكس في العلاقة التالية: ج 32-ص ( ج 32-З ( تي))= ت، أين تي- كتلة بيانات تعسفية 64 بت ، ج X ( تي) هي نتيجة الحلقة Xفوق كتلة البيانات تي. للوفاء بهذا الشرط للخوارزميات المشابهة لـ GOST ، من الضروري والكافي أن يكون الترتيب الذي يتم به استخدام العناصر الرئيسية من خلال الدورات المقابلة معكوسًا بشكل متبادل. من السهل التحقق من صحة الشرط المكتوب للحالة قيد النظر من خلال مقارنة التسلسلات المذكورة أعلاه للدورات 32-3 و 32-P. نتيجة واحدة مثيرة للاهتمام تتبع مما سبق: خاصية الدورة لتكون معكوس دورة أخرى متبادلة ، أي أن الدورة 32-3 معكوسة فيما يتعلق بالدورة 32-P. بعبارة أخرى ، يمكن نظريًا إجراء تشفير كتلة البيانات باستخدام حلقة فك التشفير ، وفي هذه الحالة يجب أن يتم فك تشفير كتلة البيانات بحلقة تشفير. من بين الدورتين العكسيتين ، يمكن استخدام إحداهما للتشفير ، ثم يجب استخدام الثانية لفك تشفير البيانات ، ومع ذلك ، فإن معيار GOST28147-89 يخصص أدوارًا للدورات ولا يمنح المستخدم الحق في الاختيار في هذا الشأن .

دورة توليد محاكاة الإدراج هي نصف ما دامت دورات التشفير ، وترتيب استخدام العناصر الرئيسية فيه هو نفسه كما في أول 16 خطوة من دورة التشفير ، والتي يسهل رؤيتها من خلال النظر في التسلسلات المذكورة أعلاه ، لذلك يتم ترميز هذا الترتيب في تسمية الدورة بنفس الحرف "Z".

تظهر مخططات الدورات الأساسية في الأشكال 2 أ-ج. يأخذ كل منهم كوسيطة ويعود نتيجة لذلك كتلة 64 بت من البيانات ، المشار إليها في المخططات ن. خطوة الرمز ( ن,X) يشير إلى تنفيذ خطوة تحويل التشفير الرئيسية لكتلة البيانات نباستخدام العنصر الأساسي X. هناك اختلاف واحد آخر بين دورات التشفير وحساب انتحال الهوية للإدخال ، غير مذكور أعلاه: في نهاية الدورات الأساسية للتشفير ، يتم تبديل الأجزاء العالية والمنخفضة من الكتلة الناتجة ، وهذا ضروري لعكسهما المتبادل .

أوضاع التشفير الأساسية.

يوفر GOST 28147-89 أوضاع تشفير البيانات الثلاثة التالية:

• استبدال بسيط ،
• ألعاب
• غاما ردود الفعل ،

وطريقة إضافية لتوليد الإدراج المقلد.

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

قبل الشروع في النظر في خوارزميات محددة لعمليات التحويل المشفرة ، من الضروري توضيح الترميز المستخدم في الرسوم البيانية في الأقسام التالية:

تييا تي w هي صفيفات من البيانات المفتوحة والمشفرة ، على التوالي ؛

, – أنا- كتل 64 بت من البيانات المفتوحة والمشفرة ، على التوالي: , ، قد تكون الكتلة الأخيرة غير مكتملة: ؛

ن- عدد الكتل 64 بت في مصفوفة البيانات ؛

ج X هي وظيفة تحويل كتلة بيانات 64 بت وفقًا لخوارزمية الدورة الأساسية "X".

الآن دعنا نصف أوضاع التشفير الرئيسية:

استبدال بسيط.

يتكون التشفير في هذا الوضع من تطبيق دورة 32-3 لفتح كتل البيانات ، وفك التشفير - دورة 32-P لكتل ​​البيانات المشفرة. هذا هو أبسط الأوضاع ، تتم معالجة كتل البيانات 64 بت فيه بشكل مستقل عن بعضها البعض. تظهر مخططات خوارزميات التشفير وفك التشفير في وضع الاستبدال البسيط في الشكلين 3 أ و ب ، على التوالي ؛ فهي تافهة ولا تحتاج إلى تعليقات.

رسم. 3 أ. خوارزمية تشفير البيانات في وضع الاستبدال البسيط

رسم. 3 ب. خوارزمية فك تشفير البيانات في وضع الاستبدال البسيط

يجب أن يكون حجم مصفوفة البيانات المفتوحة أو المشفرة ، الخاضعة للتشفير أو فك التشفير ، على التوالي ، من مضاعفات 64 بت: | تي س | = | تي ث | = 64 ن بعد تنفيذ العملية ، لا يتغير حجم صفيف البيانات المستلمة.

يحتوي وضع التشفير البديل البسيط على الميزات التالية:

• نظرًا لأن كتل البيانات يتم تشفيرها بشكل مستقل عن بعضها البعض وعن موقعها في مصفوفة البيانات ، عند تشفير كتلتين متطابقتين من النص العادي ، يتم الحصول على كتل نص مشفر متطابقة والعكس صحيح. ستسمح الخاصية المذكورة لمحلل التشفير باستنتاج أن كتل البيانات الأصلية متطابقة إذا واجه كتلًا متطابقة في مجموعة البيانات المشفرة ، وهو أمر غير مقبول بالنسبة إلى التشفير الجاد.
• إذا لم يكن طول مصفوفة البيانات المشفرة مضاعفًا لـ 8 بايت أو 64 بت ، فإن المشكلة تنشأ حول كيفية وكيفية حشو آخر كتلة بيانات غير مكتملة من المصفوفة إلى 64 بت كامل. هذه المهمة ليست بسيطة كما تبدو للوهلة الأولى. الحلول الواضحة مثل "حشو كتلة غير مكتملة مع بتات صفرية" أو بشكل عام ، "حشو كتلة غير مكتملة بمزيج ثابت من صفر وبت واحد" يمكن ، في ظل ظروف معينة ، منح محلل التشفير الفرصة لتحديد محتويات هذا كتلة غير مكتملة من خلال طرق العد ، وهذه الحقيقة تعني انخفاض في التشفير الأمني. بالإضافة إلى ذلك ، سيتغير طول النص المشفر ، بحيث يزداد إلى أقرب عدد صحيح مضاعف لـ 64 بت ، وهو غالبًا ما يكون غير مرغوب فيه.

للوهلة الأولى ، تجعل الميزات المذكورة أعلاه من المستحيل عمليًا استخدام وضع الاستبدال البسيط ، لأنه لا يمكن استخدامه إلا لتشفير مصفوفات البيانات بحجم مضاعف لـ 64 بت ولا يحتوي على كتل 64 بت متكررة. يبدو أنه من المستحيل ضمان استيفاء هذه الشروط لأي بيانات حقيقية. هذا صحيح تقريبًا ، ولكن هناك استثناء واحد مهم جدًا: تذكر أن حجم المفتاح هو 32 بايت ، وأن حجم جدول الاستبدال هو 64 بايت. بالإضافة إلى ذلك ، فإن وجود كتل متكررة مكونة من 8 بايت في جدول رئيسي أو جدول بديل سيشير إلى جودتها الرديئة للغاية ، لذلك لا يمكن أن يكون هناك مثل هذا التكرار في العناصر الأساسية الحقيقية. وبالتالي ، اكتشفنا أن وضع الاستبدال البسيط مناسب تمامًا لتشفير المعلومات الأساسية ، خاصة وأن الأوضاع الأخرى أقل ملاءمة لهذا الغرض ، لأنها تتطلب عنصر بيانات مزامنة إضافي - رسالة مزامنة (انظر القسم التالي). تخميننا صحيح ، ويوصي GOST باستخدام وضع الاستبدال البسيط حصريًا لتشفير البيانات الرئيسية.

القمار.

كيف يمكنك التخلص من عيوب وضع الاستبدال البسيط؟ للقيام بذلك ، من الضروري جعل من الممكن تشفير الكتل بحجم أقل من 64 بت والتأكد من أن كتلة النص المشفر تعتمد على عددها ، بمعنى آخر ، عشوائيا عملية التشفير. في GOST ، يتم تحقيق ذلك بطريقتين مختلفتين في وضعين للتشفير ، توفير التحجيم . القمار - هذا هو فرض (إزالة) نطاق تشفير على بيانات مفتوحة (مشفرة) ، أي سلسلة من عناصر البيانات التي تم إنشاؤها باستخدام بعض خوارزمية التشفير للحصول على بيانات مشفرة (مفتوحة). يجب استخدام العمليات الثنائية العكسية التبادلية لتراكب جاما أثناء التشفير وإزالتها أثناء فك التشفير ، على سبيل المثال ، نموذج الجمع والطرح 2 64 لكتل ​​بيانات 64 بت. في GOST ، لهذا الغرض ، يتم استخدام عملية إضافة bitwise modulo 2 ، نظرًا لأنها عكس نفسها ، علاوة على ذلك ، يتم تنفيذها ببساطة في الأجهزة. تعمل الألعاب على حل كلتا المشكلتين المذكورتين: أولاً ، تختلف جميع عناصر جاما عن المصفوفات المشفرة الحقيقية ، وبالتالي ، ستكون نتيجة تشفير حتى كتلتين متطابقتين في مصفوفة بيانات واحدة مختلفة. ثانيًا ، على الرغم من إنتاج عناصر جاما في أجزاء متساوية من 64 بت ، يمكن أيضًا استخدام جزء من هذه الكتلة بحجم يساوي حجم الكتلة المشفرة.

الآن دعنا ننتقل مباشرة إلى وصف وضع جاما. يتم الحصول على جاما لهذا الوضع على النحو التالي: باستخدام بعض خوارزمية مولد تسلسل رقمي متكرر (RGCH) ، يتم إنشاء كتل بيانات 64 بت ، والتي تخضع بعد ذلك لتحويل 32-3 ، أي التشفير في وضع الاستبدال البسيط ، مما ينتج عنه في كتل جاما. نظرًا لحقيقة أن تراكب وإزالة جاما تتم باستخدام نفس عملية XOR الخاصة بالبت ، فإن خوارزميات التشفير وفك التشفير في وضع جاما متطابقة ، ويظهر مخططها العام في الشكل 4.

RGHR المستخدمة لإنشاء المقياس هي وظيفة متكررة: - عناصر التسلسل المتكرر ، Fهي وظيفة التحويل. لذلك ، فإن السؤال الذي يطرح نفسه حتمًا حول تهيئته ، أي حول العنصر. في الواقع ، يعد عنصر البيانات هذا معلمة خوارزمية لأوضاع جاما ، ويشار إليه في المخططات على أنه س، ويسمى في التشفير رسالة المزامنة ، وفي GOST لدينا - التعبئة الأولية أحد مسجلات برنامج التشفير. لأسباب معينة ، قرر مطورو GOST استخدام لتهيئة RGHR ليس رسالة مزامنة مباشرة ، ولكن نتيجة تحولها وفقًا لدورة 32-3: . يعتمد تسلسل العناصر التي تم إنشاؤها بواسطة RGHR كليًا على ملئه الأولي ، أي أن عناصر هذا التسلسل هي دالة لعددهم والتعبئة الأولية لـ RGHR: حيث فاي(X)=F(فاي –1 (X)), F 0 (X)=X. مع الأخذ في الاعتبار التحول وفقًا لخوارزمية الاستبدال البسيطة ، تتم أيضًا إضافة اعتماد على المفتاح:

أين G i– أنا-العنصر الثالث من المقياس ، ك- مفتاح.

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

الآن دعنا نلقي نظرة فاحصة على RGHR المستخدم في GOST لتوليد عناصر جاما. بادئ ذي بدء ، تجدر الإشارة إلى أنه ليس مطلوبًا تقديم أي خصائص إحصائية لتسلسل الأرقام الذي تم إنشاؤه. تم تصميم RGHR بواسطة مطوري GOST بناءً على الحاجة إلى استيفاء الشروط التالية:

• يجب ألا تختلف فترة التكرار لتسلسل الأرقام التي تم إنشاؤها بواسطة RGHR اختلافًا كبيرًا (من حيث النسبة المئوية) عن أقصى قيمة ممكنة تبلغ 2 64 لحجم كتلة معين ؛
• يجب أن تختلف القيم المجاورة التي تنتجها RGHR عن بعضها البعض في كل بايت ، وإلا فسيتم تبسيط مهمة محلل التشفير ؛
• يجب أن يكون تطبيق RGHR سهلًا إلى حد ما في كل من الأجهزة والبرامج على أكثر أنواع المعالجات شيوعًا ، ومعظمها ، كما تعلم ، لديه سعة 32 بت.

بناءً على هذه المبادئ ، صمم مبتكرو GOST RGHR ناجحًا للغاية ، والذي يتميز بالخصائص التالية:

أين ج 0 =1010101 16 ;

أين ج 1 =1010104 16 ;

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

يحتاج التعبير الثاني إلى تعليقات ، نظرًا لوجود شيء آخر في نص GOST: بنفس قيمة الثابت ج 1. ولكن في نص المعيار ، يتم إعطاء تعليق ، كما اتضح ، في ظل عملية أخذ الباقي من الوحدة 2 32-1 هناكيفهم ليس هو نفسه كما في الرياضيات. يكمن الاختلاف في حقيقة أنه وفقًا لـ GOST (2 32 -1) عصري(2 32 –1) = (2 32 –1) ، وليس 0. في الواقع ، هذا يبسط تنفيذ الصيغة ، والتعبير الصحيح عنها رياضياً معطى أعلاه.

• فترة تكرار التسلسل للجزء الأصغر هي 32 2 ، بالنسبة للجزء الأقدم 2 32-1 ، بالنسبة للتسلسل بأكمله ، تكون الفترة 2 32 (2 32 -1) ، والدليل على هذه الحقيقة ، بسيط للغاية ، جهز نفسك. يتم تنفيذ الصيغة الأولى من الاثنين في تعليمة واحدة ، والثانية ، على الرغم من إرهاقها الواضح ، في تعليمتين على جميع المعالجات الحديثة 32 بت - التعليمات الأولى هي نموذج الإضافة المعتاد 2 32 مع تخزين لقمة الحمل ، و تضيف التعليمة الثانية بتة الحمل إلى القيمة المستلمة.

يظهر مخطط خوارزمية التشفير في وضع جاما في الشكل 4 ، فيما يلي تفسيرات للمخطط:

الشكل 4. خوارزمية تشفير البيانات (فك التشفير) في وضع جاما.

الخطوة 0

يحدد البيانات الأولية لخطوة تحويل التشفير الرئيسية:

• تي o (w) - مجموعة من البيانات المفتوحة (المشفرة) ذات الحجم التعسفي ، تخضع لإجراء التشفير (فك التشفير) ، أثناء الإجراء ، يتم تحويل المصفوفة في أجزاء من 64 بت ؛
• س – رسالة المزامنة ، عنصر بيانات 64 بت مطلوب لتهيئة مولد جاما ؛

الخطوة 1

التحويل الأولي لرسالة المزامنة ، الذي يتم إجراؤه "بطريقة عشوائية" ، أي لإزالة الأنماط الإحصائية الموجودة فيها ، يتم استخدام النتيجة كملء أولي لـ RGHR ؛

الخطوة 2

خطوة واحدة من عمل RGHR ، والتي تنفذ الخوارزمية المتكررة. خلال هذه الخطوة ، أقدم ( س 1) وأصغر ( س 0) يتم إنشاء أجزاء من تسلسل البيانات بشكل مستقل عن بعضها البعض ؛

الخطوه 3

القمار. يخضع عنصر 64 بت التالي الذي تنتجه RGHR لإجراء التشفير في دورة 32-3 ، ويتم استخدام النتيجة كعنصر جاما لتشفير (فك تشفير) الكتلة التالية من البيانات المفتوحة (المشفرة) من نفس الحجم.

الخطوة 4

نتيجة الخوارزمية هي مصفوفة بيانات مشفرة (غير مشفرة).

فيما يلي ميزات جاما كوضع تشفير:

1. ستعطي الكتل المتطابقة في مصفوفة البيانات المفتوحة كتل نص مشفر مختلفة عند تشفيرها ، مما يجعل من الممكن إخفاء حقيقة هويتها.
2. نظرًا لأنه يتم تنفيذ جاما شيئًا فشيئًا ، فإن تشفير كتلة البيانات غير الكاملة يتم بسهولة كتشفير بتات هذه الكتلة غير المكتملة ، والتي يتم استخدام البتات المقابلة لها من كتلة جاما. لذلك ، لتشفير كتلة غير كاملة من 1 بت ، وفقًا للمعيار ، يجب استخدام البت الأقل أهمية من كتلة جاما.
3. يجب إرسال رسالة المزامنة المستخدمة في التشفير بطريقة ما لاستخدامها في فك التشفير. يمكن تحقيق ذلك بالطرق التالية:

• تخزين أو نقل رسالة المزامنة مع مصفوفة البيانات المشفرة ، مما سيزيد من حجم مصفوفة البيانات أثناء التشفير بحجم رسالة المزامنة ، أي بمقدار 8 بايت ؛
• استخدام قيمة محددة مسبقًا لرسالة المزامنة أو إنشائها بشكل متزامن من قبل المصدر والمستقبل وفقًا لقانون معين ، وفي هذه الحالة لا يوجد تغيير في حجم مجموعة البيانات المرسلة أو المخزنة ؛

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

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

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

حيث تشير إلى معكوس فيما يتعلق رقيمة بت ().

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

القمار مع ردود الفعل.

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

يظهر مخطط الخوارزميات لفك التشفير وفك التشفير في وضع غاما التغذية المرتدة في الشكل 5 ، وبسبب بساطته ، لا يحتاج إلى تعليقات.

الشكل 5. خوارزمية لتشفير البيانات (فك التشفير) في وضع جاما مع التغذية الراجعة.

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

ألعاب

اللعب مع ردود الفعل ؛

بينما في وضع القياس العادي ، فإن التغييرات في أجزاء معينة من النص المشفر تؤثر فقط على البتات المقابلة من النص العادي ، في وضع قياس التغذية المرتدة ، تكون الصورة أكثر تعقيدًا إلى حد ما. كما يتضح من المعادلة المقابلة ، عند فك تشفير كتلة بيانات في وضع غاما الحلقة المغلقة ، تعتمد كتلة البيانات المفتوحة على كتل البيانات المشفرة المقابلة والسابقة. لذلك ، إذا أدخلنا تشوهات في الكتلة المشفرة ، فبعد فك التشفير ، سيتم تشويه كتلتين من البيانات المفتوحة - الكتلة المقابلة والأخرى التي تليها ، وستكون التشوهات في الحالة الأولى من نفس الطبيعة كما في جاما الوضع ، وفي الحالة الثانية - كما هو الحال في وضع الاستبدال البسيط. بمعنى آخر ، في كتلة البيانات المفتوحة المقابلة ، سيتم إتلاف نفس البتات كما في كتلة البيانات المشفرة ، وفي كتلة البيانات المفتوحة التالية ، ستكون جميع البتات مستقلة عن بعضها البعض مع احتمال 1 / 2 سيغير قيمهم.

تطوير محاكاة الإدراج لمجموعة من البيانات.

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

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

• حساب محاكاة الإدراج لمجموعة مفتوحة معينة من المعلومات ؛
• اختيار البيانات المفتوحة لإدراج محاكاة معين ؛

يظهر مخطط الخوارزمية لتوليد إدراج محاكى في الشكل 6.

الشكل 6. خوارزمية لتوليد إدراج محاكاة لصفيف البيانات.

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

مناقشة خوارزميات التشفير GOST.

قوة التشفير لـ GOST.

عند اختيار خوارزمية تشفير لاستخدامها في تطوير معين ، فإن أحد العوامل المحددة هو قوتها ، أي مقاومة محاولات الخصم للكشف عنها. تتلخص مسألة قوة التشفير ، عند الفحص الدقيق ، في سؤالين مترابطين:

• هل من الممكن فتح هذا التشفير على الإطلاق ؛
• إذا كان الأمر كذلك ، ما مدى صعوبة ذلك من الناحية العملية ؛

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

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

يستخدم GOST مفتاح 256 بت وحجم مساحة المفتاح هو 2256. لا يمكن لأي من الأجهزة الإلكترونية الموجودة حاليًا أو من المتوقع أن يتم تنفيذها في المستقبل القريب التقاط مفتاح في أقل من عدة مئات من السنين. أصبحت هذه القيمة هي المعيار الفعلي لحجم المفتاح لخوارزميات التشفير المتماثل هذه الأيام ، كما يدعمها معيار التشفير الأمريكي الجديد. المعيار الأمريكي السابق ، DES ، بحجم مفتاحه الحقيقي 56 بت وحجم مساحة المفتاح 256 فقط ، لم يعد قوياً بما يكفي في ضوء قدرات أدوات الحوسبة الحديثة. وقد تجلى ذلك في أواخر التسعينيات من خلال العديد من هجمات القوة الغاشمة الناجحة على DES. بالإضافة إلى ذلك ، خضع DES لطرق خاصة لتحليل الشفرات ، مثل التفاضلية والخطية. في هذا الصدد ، قد تكون DES ذات أهمية بحثية أو علمية أكثر من الفائدة العملية. في عام 1998 ، تم الاعتراف رسميًا بضعف التشفير - أوصى المعهد الوطني الأمريكي للمعايير باستخدام تشفير DES الثلاثي. وفي نهاية عام 2001 ، تمت الموافقة رسميًا على معيار تشفير أمريكي جديد ، AES ، مبني على مبادئ مختلفة وخالٍ من عيوب سابقتها.

ملاحظات حول بنية GOST.

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

تم إنشاء خوارزميات "الخطوات الأساسية لتحويل التشفير" للأصفار مثل GOST بطريقة متطابقة ، وتسمى هذه البنية شبكة Feistel المتوازنة (شبكة Feistel المتوازنة) سميت على اسم الشخص الذي اقترحها لأول مرة. مخطط تحويل البيانات في دورة واحدة ، أو كما يطلق عليه عادة ، دائري ، كما هو موضح في الشكل 7.

الشكل 7. محتوى خطوة تحويل التشفير الرئيسية لأصفار الكتلة المشابهة لـ GOST.

يتم تغذية كتلة متساوية الحجم إلى مدخلات الخطوة الرئيسية ، حيث تتم معالجة النصفين العلوي والسفلي بشكل منفصل عن بعضهما البعض. أثناء التحويل ، يتم وضع النصف السفلي من الكتلة بدلاً من النصف الأقدم ، والأقدم ، معًا باستخدام طريقة البت " حصري أو »نتيجة حساب بعض الدوال بدلاً من الأصغر. هذه الوظيفة ، التي تأخذ النصف السفلي من الكتلة وعنصر المعلومات الأساسية كوسيطة ( X) ، هو جزء المحتوى من التشفير ويسمى ذلك وظيفة التشفير . لأسباب مختلفة ، اتضح أنه من المفيد تقسيم الكتلة المشفرة إلى جزأين من نفس الحجم: | ن 1 |=|ن 2 | - هذه الحقيقة هي التي تعكس كلمة "متوازن" في اسم العمارة. ومع ذلك ، تُستخدم شبكات التشفير غير المتوازنة أيضًا من وقت لآخر ، وإن لم يكن كثيرًا مثل الشبكات المتوازنة. بالإضافة إلى ذلك ، تتطلب اعتبارات قوة التشفير ألا يقل حجم العنصر الرئيسي عن حجم نصف الكتلة: في GOST ، جميع الأحجام الثلاثة هي 32 بت. .

إذا طبقنا ما سبق على مخطط الخطوة الرئيسية لخوارزمية GOST ، يصبح من الواضح أن الكتل 1،2،3 من الخوارزمية (انظر الشكل 1) تحدد حساب وظيفة التشفير الخاصة بها ، ومجموعة الكتل 4 و 5 تشكيل كتلة الإخراج للخطوة الرئيسية بناءً على محتويات كتلة الإدخال وقيمة وظيفة التشفير. يمكن العثور على مزيد من التفاصيل حول معماريات الأصفار الحديثة ذات المفتاح السري في الأعمال الكلاسيكية ، أو في شكل مُعدّل ، في أعمالي.

في القسم السابق ، قمنا بالفعل بمقارنة DES و GOST من حيث المتانة ، والآن سنقارنهما من حيث المحتوى الوظيفي وسهولة التنفيذ. في دورات تشفير GOST ، تتكرر الخطوة الرئيسية 32 مرة ، بالنسبة لـ DES هذه القيمة هي 16. ومع ذلك ، فإن وظيفة تشفير GOST نفسها أبسط بكثير من وظيفة DES المماثلة ، حيث يوجد العديد من تباديل البتات غير المنتظمة. يتم تنفيذ هذه العمليات بشكل غير فعال للغاية على المعالجات الحديثة غير المتخصصة. لا يحتوي GOST على مثل هذه العمليات ، لذلك فهو أكثر ملاءمة لتنفيذ البرامج.

لم تحقق أي من تطبيقات DES التي نظر فيها المؤلف لمنصة Intel x86 حتى نصف أداء تطبيق GOST المعروض على انتباهك في هذه المقالة ، على الرغم من دورة أقصر مرتين. يشير كل ما سبق إلى أن مطوري GOST أخذوا في الحسبان الجوانب الإيجابية والسلبية لـ DES ، وقاموا أيضًا بتقييم أكثر واقعية للإمكانيات الحالية والمستقبلية لتحليل التشفير. ومع ذلك ، فإن أخذ DES كأساس عند مقارنة أداء تطبيقات التشفير لم يعد ذا صلة. يعمل معيار التشفير الأمريكي الجديد بشكل أفضل بكثير مع الكفاءة - بنفس حجم مفتاح GOST البالغ 256 بت ، يعمل AES أسرع منه بحوالي 14٪ - وهذا عند مقارنته بعدد "العمليات الأولية". بالإضافة إلى ذلك ، من المستحيل عمليًا موازاة GOST ، بينما تتمتع AES بفرص أكثر بكثير في هذا الصدد. في بعض الأبنية ، قد تكون فائدة AES أقل ، وقد تكون أكثر في البعض الآخر. لذا في معالج Intel Pentium يصل إلى 28٪. يمكن العثور على التفاصيل في.

متطلبات جودة المعلومات الرئيسية والمصادر الرئيسية.

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

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

كما هو مذكور أعلاه ، لا تتوفر معايير لتقييم المعلومات الأساسية ، ولكن لا يزال من الممكن مراعاة بعض الاعتبارات العامة بشأنها.

مفتاح

يجب أن يكون المفتاح عبارة عن مصفوفة من وحدات البت المستقلة إحصائيًا والتي تأخذ القيمتين 0 و 1 باحتمالية متساوية. ولا يمكن استبعاد أن تكون بعض القيم الأساسية المحددة "ضعيفة" ، أي قد لا يوفر التشفير مستوى معينًا من الأمان إذا تم استخدامه. ومع ذلك ، من المفترض أن حصة هذه القيم في الكتلة الإجمالية لجميع المفاتيح الممكنة لا تكاد تذكر. على الأقل ، لم يكشف بحث التشفير المكثف عن أي مفتاح من هذا القبيل لأي من جداول الاستبدال المعروفة (أي المقترحة من قبل FAPSI). لذلك ، فإن المفاتيح التي يتم إنشاؤها بمساعدة منشئ معين لأرقام عشوائية حقيقية ستكون ذات جودة عالية مع احتمال يختلف عن الوحدة بمقدار ضئيل للغاية. إذا تم إنشاء المفاتيح باستخدام مولد أرقام شبه عشوائي ، فيجب أن يوفر المولد المستخدم الخصائص الإحصائية المذكورة أعلاه ، بالإضافة إلى قوة تشفير عالية ، لا تقل عن قوة GOST نفسها. بمعنى آخر ، يجب ألا تكون مهمة تحديد الأعضاء المفقودين في تسلسل العناصر التي تم إنشاؤها بواسطة المولد أسهل من مهمة كسر التشفير. بالإضافة إلى ذلك ، يمكن استخدام معايير إحصائية مختلفة لرفض المفاتيح ذات الأداء الإحصائي الضعيف. من الناحية العملية ، عادة ما يكون هناك معياران كافيان - للتحقق من التوزيع المتساوي للبتات الرئيسية بين القيمتين 0 و 1 ، عادةً ما يتم استخدام معيار بيرسون ("مربع كاي") ، وللتحقق من استقلالية بتات المفاتيح ، يكون معيار السلسلة هو مستخدم. يمكنك أن تقرأ عن المعايير المذكورة في الكتب المدرسية أو الكتب المرجعية حول الإحصاء الرياضي.

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

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

جدول الاستبدال

يعد جدول الاستبدال عنصرًا رئيسيًا طويل الأجل ، أي أنه صالح لفترة أطول بكثير من مفتاح واحد. من المفترض أنه مشترك لجميع عقد التشفير داخل نظام حماية تشفير واحد. حتى في حالة انتهاك سرية جدول الاستبدال ، تظل قوة التشفير عالية للغاية ولا تقل عن الحد المسموح به. لذلك ، ليست هناك حاجة خاصة للحفاظ على سرية الجدول ، وفي معظم التطبيقات التجارية لـ GOST ، هذه هي الطريقة التي يتم بها ذلك. من ناحية أخرى ، يعد جدول الاستبدال عنصرًا حاسمًا لضمان قوة التشفير بالكامل. يمكن أن يؤدي اختيار الجدول الخاطئ إلى كسر الشفرات بسهولة من خلال طرق تحليل التشفير المعروفة. تعتبر معايير تطوير العقد البديلة سرًا مع سبعة أختام ومن غير المرجح أن تشاركها FAPSI مع الجمهور في المستقبل القريب. في النهاية ، من أجل تحديد ما إذا كان جدول الاستبدال هذا جيدًا أم سيئًا ، تحتاج إلى قضاء قدر كبير من العمل - عدة آلاف من ساعات العمل والآلة. بمجرد تحديده واستخدامه ، يخضع الجدول للاستبدال إذا وفقط إذا تبين أن التشفير باستخدامه عرضة لنوع أو آخر من تحليل التشفير. لذلك ، فإن أفضل خيار للمستخدم العادي للتشفير هو أن يأخذ أحد الجداول العديدة التي أصبحت عامة. على سبيل المثال ، من معيار دالة التجزئة ، فهي أيضًا "مصرفية مركزية" ؛ يمكن العثور على معلومات حول هذه الجداول في الصحافة المفتوحة وحتى على الإنترنت ، إذا بحثت جيدًا.

بالنسبة لأولئك الذين لم يعتادوا على اتخاذ الطريق السهل ، يوجد أدناه مخطط عام للحصول على جداول الجودة:

1. باستخدام طريقة أو بأخرى ، يمكنك تطوير مجموعة من ثماني عقد بديلة بخصائص غير خطية مضمونة. هناك العديد من هذه الطرق ، أحدها هو استخدام ما يسمى بوظائف الانحناء.
2. تتحقق من تنفيذ أبسط "معايير الجودة" - على سبيل المثال ، تلك المنشورة لعقد استبدال DES. فيما يلي بعض الاعتبارات العامة حول هذه النتيجة: يمكن وصف كل عقدة استبدال بأربع وظائف منطقية من أربع وسيطات منطقية. إذا كانت هذه الوظائف ، مكتوبة في شكل مبسط(على سبيل المثال ، مع الحد الأدنى لطول التعبير الممكن) ليست معقدة بما يكفي ، مثل هذه العقدة البديلة مرفوضة. بالإضافة إلى ذلك ، يجب أن تختلف الوظائف الفردية داخل جدول الاستبدال بأكمله عن بعضها البعض إلى حد كاف. في هذه المرحلة ، يتم التخلص من العديد من الجداول منخفضة الجودة عن عمد.
3. للحصول على تشفير بجداول من اختيارك ، قم ببناء نماذج دائرية مختلفة تتوافق مع أنواع مختلفة من تحليل التشفير ، وقياس خصائص "الملف الشخصي" المقابلة. لذلك ، لتحليل التشفير الخطي ، قم ببناء نظير إحصائي خطي لجولة التشفير وحساب خاصية "الملف الشخصي" - مؤشر عدم الخطية. إذا اتضح أنه غير كافٍ ، فسيتم رفض جدول الاستبدال.
4. أخيرًا ، باستخدام نتائج الفقرة السابقة ، قم بإخضاع الشفرة بالجدول الذي تختاره لبحث مكثف - محاولة لتحليل الشفرات بكل الطرق المعروفة. هذه المرحلة هي الأصعب والأكثر استهلاكا للوقت. ولكن إذا تم ذلك بجودة عالية ، فعندئذٍ بدرجة عالية من الاحتمالية ، يمكن القول أن التشفير مع الجداول التي اخترتها لن يتم فتحه بواسطة بشر فقط ، ومن الممكن أن يكون ذلك صعبًا للغاية بالنسبة لـ خدمات خاصة.

ومع ذلك ، من الممكن القيام بذلك بشكل أسهل. الشيء هو أنه كلما زاد عدد الجولات في التشفير ، كلما قل التأثير على أمان التشفير بالكامل هو خصائص الأمان لجولة واحدة. يوجد في GOST ما يصل إلى 32 جولة - أكثر من جميع الأصفار تقريبًا ذات الهندسة المعمارية المماثلة. لذلك ، بالنسبة لمعظم التطبيقات المحلية والتجارية ، يكفي الحصول على عقد بديلة كتباديل عشوائي مستقل للأرقام من 0 إلى 15. ويمكن تنفيذ ذلك عمليًا ، على سبيل المثال ، عن طريق خلط مجموعة من ستة عشر بطاقة ، يتم تخصيص بطاقة واحدة لكل منها من قيم النطاق المحدد.

فيما يتعلق بجدول البدائل ، من الضروري ملاحظة حقيقة واحدة أخرى مثيرة للاهتمام. لا تتطلب قابلية عكس دورات التشفير 32-3 و 32-R أن تكون العقد البديلة عبارة عن تباديل للأرقام من 0 إلى 15. كل شيء يعمل حتى إذا كانت هناك عناصر مكررة في العقدة البديلة ، والاستبدال الذي تحدده هذه العقدة ، لا رجوع فيه - ومع ذلك ، في هذه الحالة ، تقل قوة التشفير. لم يتم النظر في سبب ذلك في هذه المقالة ، ولكن ليس من الصعب التحقق من الحقيقة نفسها. للقيام بذلك ، يكفي محاولة تشفير كتلة البيانات أولاً ثم فك تشفيرها باستخدام جدول بديل "أدنى" ، تحتوي عقده على قيم مكررة.

الاختلافات حول موضوع GOST

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

كيف يتم المضي قدما في هذه الحالات وما شابهها من أجل زيادة سرعة التشفير؟ تكمن الإجابة على السطح - استخدم تعديلًا للشفرة بخطوات أساسية أقل (جولات) في الدورات الأساسية. كم مرة نقوم بتقليل عدد جولات التشفير ، يزداد الأداء بنفس المقدار. يمكن تحقيق هذا التغيير بطريقتين - بتقليل طول المفتاح وتقليل عدد "دورات البحث" للمفتاح. تذكر أن عدد الخطوات الأساسية في دورات التشفير الأساسية هو ن=ن م، أين نهو عدد عناصر 32 بت في المفتاح ، م- عدد دورات استخدام العناصر الرئيسية في المواصفة ن=8, م= 4. يمكنك تقليل أي من هذه الأرقام ، ولكن الخيار الأبسط هو تقليل طول المفتاح دون التأثير على مخطط استخدامه.

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

بالنسبة إلى مقاومة التشفير للتصدع بالطرق "الواسعة" ، أي هجوم "القوة الغاشمة" ، كل شيء واضح إلى حد ما هنا: مفتاح 64 بت على وشك الوصول إلى هذا النوع للهجوم ، يعد التشفير بمفتاح 96 بت وأعلى (تذكر أن المفتاح يجب أن يحتوي على عدد صحيح من عناصر 32 بت) قوي جدًا ضده. في الواقع ، قبل بضع سنوات ، تم اختراق معيار التشفير الأمريكي السابق ، DES ، مرارًا وتكرارًا بواسطة القوة الغاشمة - تم اختراقه أولاً بواسطة شبكة كمبيوتر منظمة على أساس الإنترنت العالمي ، ثم بواسطة شبكة متخصصة ، أي. كمبيوتر مصمم خصيصًا لهذا الغرض. لنفترض أن الإصدار القياسي من GOST ، عند تنفيذه في برنامج على معالجات حديثة ، يعمل أسرع أربع مرات من DES. ثم سيعمل "GOST المخفض" المكون من 8 جولات أسرع 16 مرة من DES. لنفترض أيضًا أنه بمرور الوقت منذ اختراق DES ، تضاعف أداء تقنية الحوسبة ، وفقًا لقانون مور ، أربع مرات. نتيجة لذلك ، حصلنا الآن على أن التحقق من مفتاح 64 بت واحد لـ "GOST المخفض" بثماني دورات أسرع بـ 64 مرة من التحقق من مفتاح DES مرة واحدة. وبالتالي ، يتم تقليل ميزة هذا الإصدار من GOST على DES من حيث تعقيد هجوم القوة الغاشمة من 2 64-56 = 2 8 = 256 إلى 256 / 64 = 4 مرات. موافق ، هذا فرق خادع للغاية ، لا شيء تقريبًا.

من الأصعب بكثير تقييم مقاومة التعديلات الضعيفة لـ GOST للطرق "المكثفة" لتحليل الشفرات. ومع ذلك ، يمكن تتبع النمط العام هنا أيضًا. الحقيقة هي أن خصائص "الملف الشخصي" للعديد من أقوى أنواع تحليل التشفير حاليًا تعتمد بشكل كبير على عدد جولات التشفير. لذلك ، بالنسبة لتحليل التشفير الخطي (LCA) ، ستكون هذه هي الخاصية الخطية إل :

أين ج وهي ثوابت ، R هو عدد الجولات. توجد علاقة مماثلة لتحليل الشفرات التفاضلي. وفقًا لـ "المعنى المادي" ، تعتبر جميع خصائص هذا النوع احتمالات. عادةً ما تتناسب كمية البيانات الأولية المطلوبة لتحليل التشفير وتعقيدها عكسياً مع هذه الخصائص. ويترتب على ذلك أن مؤشرات كثافة العمالة هذه تنمو بشكل كبير مع نمو عدد خطوات التشفير الأساسية. لذلك ، عندما يتم تقليل عدد الجولات عدة مرات ، فإن تعقيد أنواع التحليل الأكثر شهرة سيتغير ، بشكل تقريبي وتقريبي ، جذر هذه القوة من المقدار الأولي. هذا هو انخفاض كبير جدا في القدرة على التحمل.

من ناحية أخرى ، تم تصميم GOST بهامش أمان كبير وهو اليوم مقاوم لجميع أنواع تحليل الشفرات المعروفة ، بما في ذلك التفاضلية والخطية. فيما يتعلق بـ LCA ، هذا يعني أنه من أجل تنفيذه الناجح ، يلزم المزيد من أزواج "الكتلة المفتوحة - الكتلة المشفرة" أكثر من أزواج "الموجودة في الطبيعة" ، أي أكثر من 2 64. في ضوء ما سبق ، يعني هذا أنه من أجل LCA ناجح لـ GOST من 16 جولة ، ستكون هناك حاجة على الأقل كتل أو 2 35 بايت أو 32 جيجابايت من البيانات ، وبالنسبة لـ GOST من 8 جولات ، على الأقل كتل أو 2 19 بايت أو 0.5 ميغا بايت.

يتم تقديم الاستنتاجات من كل ما قيل أعلاه في الجدول التالي ، الذي يلخص خصائص الإصدارات المخفضة من GOST.

عدد الجولات	حجم المفتاح ، بت	فهرس العمل السريع	الخصائص المحتملة للشفرات (تقدير تقريبي للغاية)
24	192	1,33	مقاومة لمعظم أنواع KA المعروفة ، أو تكون على وشك المقاومة. التنفيذ العملي لـ CA مستحيل بسبب المتطلبات العالية للبيانات الأولية وكثافة العمالة.
16	128	2	من الناحية النظرية ، فإنه غير مستقر لبعض أنواع تحليل الشفرات ، ولكن تنفيذها العملي في معظم الحالات يكون صعبًا بسبب المتطلبات العالية للبيانات الأولية وكثافة العمالة.
12	95	2,67	إنه لا يقاوم بعض الأنواع المعروفة من تحليل التشفير ، ومع ذلك ، فهو مناسب لضمان سرية كميات صغيرة من البيانات (تصل إلى عشرات أو مئات كيلو بايت) لفترة قصيرة.
8	64	4	إنه لا يقاوم بعض أنواع تحليل التشفير المعروفة ، ولكنه مناسب لضمان سرية كميات صغيرة من البيانات (تصل إلى عشرات الكيلو بايت) لفترة قصيرة.

الخياران الأخيران ، مع 12 و 8 جولات ، قادران على توفير حماية محدودة للغاية في الوقت المناسب. يتم تبرير استخدامها فقط في المهام التي تتطلب فقط سرية البيانات المغلقة على المدى القصير ، في حدود عدة ساعات. أحد المجالات الممكنة للتطبيق لهذه الأصفار الضعيفة هو إغلاق حركة UDP لأنظمة تداول العملات الإلكترونية. في هذه الحالة ، يتم تشفير كل حزمة بيانات (مخطط بيانات ، حرف "D" الأوسط من اختصار UDP) بمفتاح 64 بت منفصل ، ويتم تشفير المفتاح نفسه بمفتاح جلسة (مفتاح نطاقه هو جلسة اتصال واحدة بين جهازي كمبيوتر ) ونقلها مع البيانات.

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

القضية المطروحة لها جانب سلبي أيضا. ماذا لو لم تكن سرعة التشفير حرجة ، وكانت متطلبات القوة صارمة للغاية؟ هناك طريقتان لزيادة مقاومة GOST - سنسميها بشكل مشروط "واسعة" و "مكثفة". أولها ليس أكثر من مجرد زيادة بسيطة في عدد جولات التشفير. ليس من الواضح تمامًا بالنسبة لي سبب الحاجة إلى ذلك حقًا ، لأن المعيار المحلي يوفر بالفعل الاستقرار اللازم بدونه. ومع ذلك ، إذا كنت تعاني من جنون العظمة أعلى من المستوى المطلوب (وكل "المدافعين عن المعلومات" ملزمون بالمعاناة منه ، فهذا شرط للملاءمة المهنية ، والسؤال الوحيد هو مدى خطورة الحالة :) ، فهذا سيساعدك اهدأ قليلا. إذا لم تكن متأكدًا من تشفير KGB هذا أو جدول الاستبدال الذي تستخدمه ، فما عليك سوى مضاعفة ، ورباعية ، وما إلى ذلك. عدد الجولات - حدد التعددية بناءً على خطورة حالتك. يتيح لك هذا النهج زيادة قوة التشفير حقًا - إذا كان تحليل الشفرات السابق مستحيلًا ، أصبح الآن مستحيلًا في المربع!

الأمر الأكثر تعقيدًا وإثارة للاهتمام هو السؤال عما إذا كان من الممكن زيادة قوة التشفير دون تغيير عدد وهيكل خطوات التشفير الرئيسية. والمثير للدهشة أن الإجابة على هذا السؤال هي نعم ، على الرغم من أننا نسير مرة أخرى على أرض المضاربة الهشة. الحقيقة هي أنه في GOST ، في خطوة التحويل الرئيسية ، من المفترض أن تحل محل 4 في 4 بتات ، ولكن من الناحية العملية (سنتحدث عن هذا لاحقًا) ، تؤدي جميع تطبيقات البرامج استبدال البايت بالبايت ، أي 8 في 8 بت - يتم ذلك لأسباب تتعلق بالكفاءة. إذا قمنا على الفور بتصميم مثل هذا البديل كبديل 8 بت ، فسنعمل على تحسين خصائص جولة واحدة بشكل كبير. أولاً ، ستزداد خاصية "الانتشار" أو مؤشر "الانهيار الجليدي" - ستؤثر بتة واحدة من بيانات المصدر و / أو المفتاح على المزيد من بتات النتيجة. ثانيًا ، بالنسبة لعقد الاستبدال الأكبر ، يمكن الحصول على خصائص تفاضلية وخطية أقل ، وبالتالي تقليل قابلية التشفير لأنواع مماثلة من تحليل التشفير. ينطبق هذا بشكل خاص على دورات GOST المخفضة ، وبالنسبة لخيارات 8 و 12 جولة ، فإن هذه الخطوة ضرورية ببساطة. هذا يعوض إلى حد ما عن فقدان القدرة على التحمل فيها من انخفاض في عدد الجولات. ما يجعل من الصعب استخدام هذه التقنية هو أنه سيتعين عليك تصميم هذه العقد البديلة "المتزايدة" بنفسك. وأيضًا حقيقة أن العقد الأكبر حجمًا بشكل عام أكثر صعوبة في التصميم من العقد الأصغر.

الاستخدام غير القياسي للمعيار.

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

1. للتشفير في وضع جاما ، يوفر GOST توليد جاما مشفرة - سلسلة من البتات ذات خصائص إحصائية جيدة وقوة تشفير عالية. علاوة على ذلك ، يتم استخدام جاما لتعديل البيانات المفتوحة ، مما ينتج عنه بيانات مشفرة. ومع ذلك ، ليس هذا هو التطبيق الوحيد الممكن لجاما التشفير. الحقيقة هي أن الخوارزمية الخاصة بتطويرها عبارة عن مولد تسلسل رقمي شبه عشوائي (PRNG) بخصائص ممتازة. بالطبع ، ليس من المعقول جدًا استخدام مثل هذا PRNG حيث يكون الحصول على الخصائص الإحصائية للتسلسل الذي تم إنشاؤه فقط مطلوبًا ، ولا تكون هناك حاجة إلى قوة التشفير ، فهي ليست معقولة جدًا - في هذه الحالات ، هناك مولدات أكثر كفاءة. ولكن بالنسبة للتطبيقات المختلفة المتعلقة بأمن المعلومات ، سيكون هذا المصدر مفيدًا جدًا:

• كما هو مذكور أعلاه ، يمكن استخدام جاما "كمادة خام" لتوليد المفاتيح. للقيام بذلك ، تحتاج فقط إلى الحصول على جزء جاما بالطول المطلوب - 32 بايت. بهذه الطريقة ، يمكن عمل المفاتيح حسب الحاجة ولا يلزم تخزينها - إذا كانت هناك حاجة لمثل هذا المفتاح مرة أخرى ، فسيكون من السهل إنشاءه مرة أخرى. سيكون من الضروري فقط تذكر المفتاح الذي تم إنشاؤه في الأصل ، ورسالة المزامنة التي تم استخدامها ، ومن أي بايت من جاما المتولدة بدأ المفتاح. جميع المعلومات ، باستثناء المفتاح المستخدم ، ليست سرية. سيسهل هذا الأسلوب التحكم في نظام مفاتيح معقد ومتفرّع إلى حد ما ، باستخدام "مفتاح رئيسي" واحد فقط.
• على غرار سابقتها ، يمكن استخدام جاما كـ "مادة خام" أولية لتوليد كلمات المرور. هنا قد يطرح السؤال لماذا من الضروري توليدهم على الإطلاق ، أليس من الأسهل اختراعهم ببساطة حسب الحاجة. وقد تجلى فشل هذا النهج بشكل واضح في سلسلة من الحوادث في شبكات الكمبيوتر ، وكان أكبرها الشلل النهاري للإنترنت في نوفمبر 1988 ، بسبب "دودة موريس". كان تخمين كلمة المرور إحدى الطرق التي اخترق بها برنامج ضار جهاز الكمبيوتر: حاول البرنامج الدخول إلى النظام عن طريق الفرز المتتالي لعدة مئات من كلمات المرور من قائمته الداخلية ، وفي نسبة كبيرة من الحالات تمكن من القيام بذلك. تبين أن خيال الرجل في اختراع كلمات المرور سيئ للغاية. هذا هو السبب في تلك المؤسسات حيث يتم إيلاء الاهتمام الواجب للأمان ، يتم إنشاء كلمات المرور وتوزيعها على المستخدمين بواسطة مسؤول نظام الأمان. يعد إنشاء كلمة المرور أكثر تعقيدًا قليلاً من إنشاء المفاتيح ، لأنه في هذه الحالة يجب تحويل جاما الثنائية "الخام" إلى شكل حرف ، وليس مجرد "تقطيعها" إلى أجزاء. بالإضافة إلى ذلك ، قد يلزم تجاهل القيم الفردية للتأكد من أن جميع أحرف الأبجدية من المرجح أن تظهر في كلمة المرور بشكل متساوٍ.
• هناك طريقة أخرى لاستخدام سلسلة التشفير وهي مضمونة محو البيانات الموجودة على الوسائط المغناطيسية. الحقيقة هي أنه حتى عند الكتابة فوق المعلومات على وسيط مغناطيسي ، تبقى آثار البيانات السابقة ، والتي يمكن استعادتها عن طريق الفحص المناسب. لتدمير هذه الآثار ، يجب إجراء مثل هذا الكتابة عدة مرات. اتضح أنه سيكون من الضروري إعادة كتابة المعلومات إلى الوسائط مرات أقل إذا كان هذا الإجراء يستخدم بيانات عشوائية أو شبه عشوائية ستبقى غير معروفة للخبراء الذين يحاولون استعادة المعلومات المكتوبة. سيكون تشفير جاما مفيدًا هنا.

2. لا يمكن استخدام جاما المشفرة فحسب ، بل أيضًا التحويل المشفر نفسه ، لتلبية احتياجات لا تتعلق مباشرة بالتشفير:

• نحن نعلم أن أحد هذه الخيارات لاستخدام GOST هو تطوير إدراج محاكاة لمصفوفات البيانات. ومع ذلك ، على أساس أي تشفير كتلة ، بما في ذلك GOST ، من السهل جدًا إنشاء مخطط لحساب دالة تجزئة أحادية الاتجاه ، تسمى أيضًا MDC في الأدبيات ، والتي تمثل في مصادر مختلفة تغيير كود الكشف / تلاعب (متعديل/ م anipulation د etection جقصيدة) أو ملخص الرسالة (ممقال د igest جقصيدة). ظهر فك التشفير الأول في الأدب قبل ذلك بكثير ، والثاني ، الأقصر ، على ما أعتقد ، اخترعه أولئك الذين لم يتمكنوا من تذكر الأول :) - لقد كانت مزحة. يمكن استخدام MDC مباشرة في أنظمة الحماية المقلدة كنظير لإدخال التقليد ، والذي ، مع ذلك ، لا يعتمد على المفتاح السري. بالإضافة إلى ذلك ، يتم استخدام MDC على نطاق واسع في مخططات التوقيع الرقمي الإلكتروني (EDS) ، لأن معظم هذه المخططات مصممة بطريقة تجعل توقيع كتلة بيانات ذات حجم ثابت مناسبًا. كما تعلم ، على أساس المعيار GOST 28147-89 الذي تمت مناقشته ، تم بناء معيار الاتحاد الروسي لحساب وظيفة التجزئة أحادية الاتجاه GOST R34.11-94.
• من غير المعروف أنه على أساس أي تشفير كتلة ، بما في ذلك GOST ، يمكن بناء مخطط EDS يعمل بكامل طاقته ، باستخدام مفتاح توقيع سري ومجموعة تحقق مفتوحة. لعدد من الأسباب ، لم يتلق هذا المخطط توزيعًا عمليًا واسعًا ، ولكن في بعض الحالات لا يزال من الممكن اعتباره بديلاً جذابًا للغاية لمخططات EDS "الرياضية" السائدة حاليًا في العالم.

الأدب

نظم معالجة المعلومات. حماية التشفير. خوارزمية تحويل التشفير GOST 28147-89. ولاية. كوم. اتحاد الجمهوريات الاشتراكية السوفياتية وفقًا للمعايير ، M. ، 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
شانون كلود. النظرية الرياضية للأنظمة السرية. في مجموعة "Works on information Theory and cybernetics"، M.، IL، 1963، p. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
الإعلان عن الموافقة على معيار معالجة المعلومات الفيدرالية (FIPS) 197 ، معيار التشفير المتقدم (AES) ، مجلد السجل الفيدرالي. 66 ، لا. 235 / الخميس 6 ديسمبر 2001 / إشعارات ، ص 63369-63371. http://csrc.nist.gov/encryption/aes/
فيستل هورست. التشفير وأمن الكمبيوتر. ترجمة أ. فينوكوروف ، نشرها هورست فيستل. التشفير وخصوصية الكمبيوتر ، Scientific American ، مايو 1973 ، المجلد. 228 ، لا. 5 ، ص. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
شناير بروس. التشفير التطبيقي. الطبعة الثانية. البروتوكولات والخوارزميات والنصوص المصدر في لغة C. ، M. ، "Triumph" ، 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
مينيزيس ألفريد ، فان أورشوت بول ، فانستون سكوت. كتيب التشفير التطبيقي. http://www.cacr.math.uwaterloo.ca/hac/
فينوكوروف أندريه. كيف يتم بناء كتلة التشفير؟ مخطوطة. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
فينوكوروف أندريه. قضايا حول التشفير للمجلة الإلكترونية iNFUSED BYTES عبر الإنترنت. http://www.enlight.ru/crypto/articles/ib/ib.htm
فينوكوروف أندري ، بريمينكو إدوارد. نص تقرير "حول تنفيذ برمجيات معايير التشفير للاتحاد الروسي والولايات المتحدة الأمريكية" ، مؤتمر المعلوماتية ، موسكو ، MEPhI ، 28-29 يناير 2001. نشرت في وقائع المؤتمر.
تكنولوجيا المعلومات. حماية المعلومات المشفرة. وظيفة التجزئة GOST R34.11-94، Gosstandart RF، M.، 1994.

هذه الخوارزمية إلزامية للاستخدام كخوارزمية تشفير في مؤسسات الدولة في الاتحاد الروسي وعدد من المؤسسات التجارية.

وصف الخوارزمية

يظهر مخطط الخوارزمية في الشكل. 3.1. كما ترون ، مخطط هذه الخوارزمية بسيط للغاية ، مما يبسط بشكل لا لبس فيه برمجياتها أو أجهزتها.

تقوم خوارزمية GOST 28147-89 بتشفير المعلومات في كتل من 64 بت ، والتي تنقسم إلى كتلتين فرعيتين من 32 بت (N1 و N2). تتم معالجة Subblock N1 بطريقة معينة ، وبعد ذلك يتم إضافة قيمته

مع قيمة الكتلة الفرعية N2 (يتم تنفيذ الإضافة بالمقياس 2) ، ثم يتم تبديل الكتل الفرعية. يتم إجراء مثل هذا التحويل لعدد معين من الجولات: 16 أو 32 ، اعتمادًا على طريقة تشغيل الخوارزمية (الموصوفة أدناه). يتم تنفيذ العمليات التالية في كل جولة:

1. مفتاح تراكب. تمت إضافة محتوى الكتلة الفرعية / VI بالوحدة 2 32 إلى جزء Kx من المفتاح.

يحتوي مفتاح تشفير خوارزمية GOST 28147-89 على بُعد 256 بت ، و Kx هو جزء 32 بت ، أي أن مفتاح تشفير 256 بت يتم تمثيله كتسلسل مفاتيح فرعية 32 بت (الشكل 3.2):

SH ATI، AG2، Yu، AG4، K5، Kb، K7.

أثناء عملية التشفير ، يتم استخدام أحد هذه المفاتيح الفرعية ، اعتمادًا على رقم الجولة وطريقة تشغيل الخوارزمية.

أرز. 3.1. مخطط خوارزمية GOST 28147-

أرز. 3.2 مفتاح التشفير لخوارزمية GOST 28147-89

2. استبدال جدولي. بعد تراكب المفتاح ، يتم تقسيم الكتلة الفرعية / VI إلى 8 أجزاء من 4 بتات ، يتم استبدال قيمة كل منها على حدة وفقًا لجدول الاستبدال لهذا الجزء من الكتلة الفرعية. غالبًا ما تُستخدم بدائل الجدول (مربع الاستبدال ، S-box) في خوارزميات التشفير الحديثة ، لذلك يجدر النظر فيها بمزيد من التفصيل.

يتم استخدام استبدال الجدول بهذه الطريقة: يتم إدخال كتلة بيانات ذات بُعد معين (في هذه الحالة ، 4 بت) إلى المدخلات ، والتي يحدد التمثيل الرقمي لها عدد قيمة المخرجات. على سبيل المثال ، لدينا S-box بالشكل التالي:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

دع الكتلة المكونة من 4 بتات "0100" تأتي إلى الإدخال ، أي أن القيمة هي 4. وفقًا للجدول ، ستكون قيمة الإخراج 15 ، أي "1111" (يتم استبدال 0 بـ 4 ، يتم استبدال 1 بـ 11 ، قيمة 2 لا تتغير ، إلخ).

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. إزاحة دورية لليسار على مستوى البت بمقدار 11 بت.

أوضاع الخوارزمية

تحتوي خوارزمية GOST 28147-89 على 4 أوضاع للتشغيل:

□ وضع الاستبدال البسيط ؛

□ وضع جاما.

وضع اللعب P مع ردود الفعل ؛

□ وضع إنتاج المرفقات المقلدة.

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

هذه الأوضاع لها أغراض مختلفة ، ولكنها تستخدم نفس تحويل التشفير الموضح أعلاه.

وضع المبادلة السهل

في وضع الاستبدال البسيط ، يتم تنفيذ الجولات الـ 32 الموضحة أعلاه ببساطة لتشفير كل كتلة 64 بت من المعلومات. يتم استخدام المفاتيح الفرعية 32 بت في التسلسل التالي:

□ KO و Kl و K2 و K3 و K4 و K5 و Kb و AG7 و KO و ATI وما إلى ذلك - في الجولات من 1 إلى 24 ؛

□ K1 و Kb و K5 و K4 و K3 و K2 و K \ و KO - في الجولات من 25 إلى 32.

يتم فك التشفير في وضع الاستبدال البسيط بنفس الطريقة تمامًا ، ولكن مع تسلسل مختلف قليلاً لاستخدام المفاتيح الفرعية:

□ KO، K \، K2، KZ، K4، K5، Kb، KP - في الجولات من 1 إلى 8 ؛

□ KP و Kb و K5 و K4 و K3 و K2 و K \ و KO و K1 و Kb وما إلى ذلك - في الجولات من 9 إلى 32.

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

وضع جاما

في أسلوب جاما (الشكل 3.3) ، تتم إضافة كل فدرة من النص الصريح شيئًا فشيئًا إلى وحدة جاما للتشفير بحجم 64 بت. جاما المشفرة عبارة عن تسلسل خاص يتم إنشاؤه باستخدام التحويلات الموضحة أعلاه على النحو التالي:

1. في السجلات N1 و N2 ، تتم كتابة التعبئة الأولية - قيمة 64 بت ، تسمى "رسالة المزامنة" (رسالة المزامنة ، في الواقع ، هي تناظرية لمتجه التهيئة في أوضاع CBC و CFB و OFB ).

2. يتم تشفير محتويات سجلات / VI و N2 (في هذه الحالة ، رسائل المزامنة) في وضع الاستبدال البسيط.

3. تمت إضافة محتويات N1 إلى modulo (2 32 - 1) مع CI الثابت = 2 24 + 2 16 + 2 8 + 4 ، تتم كتابة نتيجة الإضافة في سجل / VI.

4. يضاف محتوى N2 بالمقياس 2 مع الثابت C2 = 2 24 + 2 16 + 2 8 +1 ، يتم كتابة نتيجة الإضافة لتسجيل N2.

5. يتم إخراج محتويات مسجلي / VI و N2 ككتلة جاما مشفرة 64 بت (على سبيل المثال ، في هذه الحالة ، تشكل / VI و N2 أول كتلة جاما).

6. إذا كانت هناك حاجة إلى كتلة جاما التالية (أي يلزم استمرار التشفير أو فك التشفير) ، فارجع إلى الخطوة 2.

لفك التشفير ، يتم إنشاء جاما بنفس الطريقة ، ثم يتم تطبيق عملية XOR مرة أخرى على النص المشفر وبتات جاما.

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

في معظم تطبيقات خوارزمية GOST 28147-89 ، لا تعد رسالة المزامنة عنصرًا سريًا ، ولكن يمكن أن تكون رسالة المزامنة سرية مثل مفتاح التشفير. في هذه الحالة ، يمكننا اعتبار أن الطول الفعال لمفتاح الخوارزمية (256 بت) قد زاد بمقدار 64 بتًا أخرى من رسالة المزامنة ، والتي يمكن اعتبارها عنصرًا أساسيًا إضافيًا.

وضع غاما ردود الفعل

في وضع غاما ردود الفعل ، بدءًا من الكتلة الثانية ، لا يتم ملء سجلات / VI و L / 2 بكتلة جاما السابقة ، ولكن نتيجة تشفير كتلة النص العادي السابقة (الشكل 3.4). يتم إنشاء الكتلة الأولى في هذا الوضع بنفس الطريقة تمامًا مثل الكتلة السابقة.

أرز. 3.4. توليد غاما المشفرة في وضع جاما مع التغذية الراجعة

وضع توليد المقلد

الانتحال عبارة عن مجموع اختباري للتشفير يتم حسابه باستخدام مفتاح تشفير ومصمم للتحقق من سلامة الرسائل. لحسابها ، هناك وضع خاص لخوارزمية GOST 28147-89.

يتم إنشاء بادئة التقليد على النحو التالي:

1. يتم كتابة أول كتلة معلومات من 64 بت ، والتي يتم حساب المقلد من أجلها ، في السجلات N1 و N2 وتشفيرها في وضع الاستبدال البسيط المصغر ، حيث يتم تنفيذ أول 16 جولة من أصل 32 جولة.

2. يتم تجميع النتيجة التي تم الحصول عليها بالمقياس 2 مع المجموعة التالية من المعلومات ، مع حفظ النتيجة في N1 و N2.

3. يتم تشفير M و N2 مرة أخرى في الوضع المصغر للاستبدال البسيط ، وهكذا حتى آخر كتلة من المعلومات.

تعتبر البادئة هي المحتويات الناتجة عن 64 بت للسجلات N1 و N2 أو جزء منها. في أغلب الأحيان ، يتم استخدام بادئة تقليد 32 بت ، أي نصف محتويات السجلات. هذا كافٍ ، لأنه ، مثل أي مجموع اختباري ، تهدف بادئة التقليد في المقام الأول إلى الحماية من التشويه العرضي للمعلومات. للحماية من التعديل المتعمد للبيانات ، يتم استخدام طرق تشفير أخرى - في المقام الأول توقيع رقمي إلكتروني (انظر القسم 1.1).

يتم استخدام بادئة التقليد على النحو التالي:

1. عند تشفير أي معلومات ، يتم حساب مقلد النص العادي وإرساله مع النص المشفر.

2. بعد فك التشفير ، يتم حساب بادئة التقليد مرة أخرى ومقارنتها بالبادئة المرسلة.

3. إذا لم تتطابق البادئات المقلدة المحسوبة والمرسلة ، فإن النص المشفر قد تم تشويهه أثناء الإرسال أو تم استخدام مفاتيح غير صحيحة أثناء فك التشفير.

تعد بادئة التقليد مفيدة بشكل خاص للتحقق من فك التشفير الصحيح للمعلومات الأساسية عند استخدام أنظمة متعددة المفاتيح.

بادئة التقليد هي بعض التناظرية من رمز مصادقة رسالة MAC المحسوبة في وضع CBC ؛ الاختلاف هو أن حساب البادئة لا يستخدم رسالة مزامنة ، بينما يستخدم حساب MAC متجه التهيئة.

قوة التشفير للخوارزمية

في عام 1994 ، تمت ترجمة وصف خوارزمية GOST 28147-89 إلى اللغة الإنجليزية ونشرها ؛ بعد ذلك بدأت تظهر نتائج تحليله الذي أجراه خبراء أجانب ؛ ومع ذلك ، لم يتم العثور على هجمات تقترب من الناحية العملية لفترة طويلة من الوقت.

□ طول مفتاح كبير - 256 بت ؛ مع رسالة المزامنة السرية ، يزيد طول المفتاح الفعال إلى 320 بت ؛

□ 32 جولة من التحولات. بالفعل بعد 8 جولات ، يتم تحقيق التأثير الكامل لتشتت بيانات الإدخال: تغيير بت واحد من كتلة النص العادي سيؤثر على جميع بتات كتلة النص المشفر ، والعكس صحيح ، أي أن هناك هامش أمان متعدد.

ضع في اعتبارك نتائج تحليل الشفرات لخوارزمية GOST 28147-89.

تحليل جداول الاستبدال

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

تستخدم الهجمات باستخدام التحليل الخطي والتفاضلي للتشفير لخوارزمية DES ميزات محددة لجداول الاستبدال ؛ عند استخدام جداول أخرى ، يجب أن يبدأ تحليل الشفرات من جديد ؛

بذلت محاولات لتقوية DES ضد التحليل الخطي والتفاضلي للتشفير باستخدام جداول إحلال أقوى ؛ تم اقتراح مثل هذه الجداول ، التي هي بالفعل أكثر استقرارًا ، على سبيل المثال ، في خوارزمية s 5 DES ؛ ولكن ، للأسف ، كان من المستحيل استبدال DES بـ s 5 DES ، نظرًا لأن جداول الاستبدال محددة بشكل صارم في المعيار ، على التوالي ، ربما لا تدعم تطبيقات الخوارزمية القدرة على تغيير الجداول إلى جداول أخرى.

في عدد من الأعمال (على سبيل المثال ، و) خلص خطأً إلى أن جداول الاستبدال السرية لخوارزمية GOST 28147-89 يمكن أن تكون جزءًا من المفتاح وتزيد من طوله الفعال (وهو أمر غير مهم ، نظرًا لأن الخوارزمية تحتوي على مفتاح 256 بت كبير جدًا). ومع ذلك ، يثبت العمل أنه يمكن حساب جداول الاستبدال السرية باستخدام الهجوم التالي ، والذي يمكن تطبيقه عمليًا:

1. عيّن المفتاح الفارغ وابحث عن "المتجه الفارغ" ، أي القيمة z = / (0) ، حيث / () هي دالة دائرية للخوارزمية. تستغرق هذه المرحلة عمليتي تشفير تقريبًا.

2. باستخدام المتجه الصفري ، يتم حساب قيم جداول الاستبدال ، والتي لا تتطلب أكثر من 2 11 عملية.

تعديلات الخوارزمية وتحليلها

في العمل ، تم إجراء تحليل تشفير لتعديلات خوارزمية GOST 28147-89:

□ خوارزمية GOST-H ، والتي ، بالنسبة للخوارزمية الأصلية ، يتم تغيير ترتيب استخدام المفاتيح الفرعية ، أي في جولات من 25 إلى 32 يتم استخدام المفاتيح الفرعية بالترتيب المباشر ، أي بنفس الطريقة كما في السابق جولات الخوارزمية ؛

□ خوارزمية GOST® من 20 جولة تستخدم XOR بدلاً من modulo 2 32 لتراكب المفاتيح.

بناءً على نتائج التحليل ، استنتج أن GOST-H و GOST © أضعف من خوارزمية GOST 28147-89 الأصلية ، نظرًا لأن كلاهما يحتوي على فئات من المفاتيح الضعيفة. تجدر الإشارة إلى أنه فيما يتعلق بتحليل التشفير GOST © ، فإن العمل يكرر كلمة بكلمة القسم الخاص بتحليل الشفرات لخوارزمية GOST 28147-89 ، المنشور في عام 2000 في عمل مشهور (دون أي إشارة إلى الأصل). هذا يدعو إلى التشكيك في مهنية مؤلفي العمل ونتائجها الأخرى.

تم اقتراح تعديل مثير جدًا للخوارزمية في العمل: يجب أن تكون الجداول S \ ... Ss مختلفة بالضرورة ؛ في كل جولة من الخوارزمية ، يجب أن يتم تبديلها وفقًا لقانون معين. قد يعتمد هذا التبديل على مفتاح التشفير ، أو قد يكون سرًا (على سبيل المثال ، يكون جزءًا من مفتاح تشفير أكبر من مفتاح 256 بت الأصلي). كلا الخيارين ، وفقًا لمؤلفيهم ، يزيدان بشكل كبير من مقاومة الخوارزمية ضد تحليل التشفير الخطي والتفاضلي.

وتم تقديم تعديل آخر متعلق بجداول الاستبدال في العمل ، حيث يتم تحليل إحدى الطرق الممكنة لحساب جداول الاستبدال بناءً على مفتاح التشفير. استنتج مؤلفو العمل أن مثل هذا الاعتماد يضعف الخوارزمية ، لأنه يؤدي إلى وجود مفاتيح ضعيفة وإلى بعض نقاط الضعف المحتملة للخوارزمية.

تحليل الخوارزمية الشامل

هناك أيضًا هجمات على GOST 28147-89 الكامل بدون أي تعديلات. أحد الأعمال المفتوحة الأولى التي تم فيها تحليل الخوارزمية ، وهو عمل معروف ، مكرس للهجمات التي تستغل نقاط الضعف في إجراء توسيع المفتاح لعدد من خوارزميات التشفير المعروفة. على وجه الخصوص ، يمكن كسر الخوارزمية الكاملة GOST 28147-89 باستخدام تحليل التشفير التفاضلي على المفاتيح المرتبطة ، ولكن فقط في حالة استخدام جداول الاستبدال الضعيفة. يتم فتح الإصدار المكون من 24 جولة من الخوارزمية (الذي يفتقر إلى الجولات الثماني الأولى) بنفس الطريقة لأي جداول استبدال ، ولكن جداول الاستبدال القوية (على سبيل المثال ، الواردة في) تجعل مثل هذا الهجوم غير عملي على الإطلاق.

اقترح العلماء المحليون A.G Rostovtsev و E.B Makhovenko في عام 2001 طريقة جديدة تمامًا لتحليل الشفرات (وفقًا للمؤلفين ، فهي أكثر فعالية بشكل ملحوظ من تحليل الشفرات الخطي والتفاضلي) من خلال تكوين وظيفة موضوعية من نص عادي معروف يتوافق مع النص المشفر والقيمة المطلوبة المفتاح والعثور على أقصى حد له يتوافق مع القيمة الحقيقية للمفتاح. وجدوا أيضًا فئة كبيرة من المفاتيح الضعيفة لخوارزمية GOST 28147-89 ، والتي تسمح لك بفتح الخوارزمية باستخدام 4 نصوص عادية محددة ونصوص مشفرة مقابلة لها بدرجة تعقيد منخفضة إلى حد ما. يستمر تحليل الشفرات للخوارزمية في العمل.

في عام 2004 ، اقترحت مجموعة من الخبراء من كوريا هجومًا باستخدام التحليل التفاضلي للتشفير على المفاتيح المرتبطة ، يمكن الحصول عليه باحتمالية 91.7٪ 12 بتًا من المفتاح السري. يتطلب الهجوم 235 نصًا عاديًا مختارًا و 236 عملية تشفير. كما ترون ، هذا الهجوم غير مفيد عمليًا للفتح الحقيقي للخوارزمية.