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

وصف موجز للشفرات

GOST 28147-89 - المعيار السوفيتي والروسي للتشفير المتماثل ، الذي تم تقديمه في عام 1990 ، هو أيضًا معيار CIS. الاسم الكامل - “GOST 28147-89 نظم معالجة المعلومات. حماية التشفير. خوارزمية تحويل التشفير ". كتلة خوارزمية التشفير. عند استخدام طريقة التشفير مع جاما ، يمكن أن تؤدي وظائف خوارزمية تشفير التدفق.

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

كيف تعمل الخوارزمية

لا تختلف الخوارزمية اختلافًا جوهريًا عن DES. يحتوي أيضًا على دورات تشفير (هناك 32 دورة) وفقًا لمخطط Feistel (الشكل 2.9.).

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

لإنشاء مفاتيح فرعية ، يتم تقسيم مفتاح 256 بت الأصلي إلى ثماني كتل 32 بت: k 1… k 8. المفاتيح k 9 ... k 24 هي تكرار دوري للمفاتيح k 1 ... k 8 (مرقمة من البتات الأقل أهمية إلى البتات الأكثر أهمية). المفاتيح k 25 ... k 32 هي المفاتيح k 1 ... k 8 تسير بترتيب عكسي.

بعد اكتمال جميع جولات الخوارزمية البالغ عددها 32 جولة ، يتم لصق الكتل A 33 و B 33 معًا (لاحظ أن A 33 يصبح البت الأكثر أهمية ، ويصبح B 33 هو البت الأقل أهمية) - والنتيجة هي نتيجة الخوارزمية.

وظيفة F(أ أنا ,ك أنا) على النحو التالي: يتم إضافة A i و K i للوضع 2 32 ، ثم يتم تقسيم النتيجة إلى ثمانية تتابعات 4 بت ، يتم تغذية كل منها إلى المدخلات الخاصة بها عقدة جدول الاستبدال(بترتيب تصاعدي لأسبقية البت) ، المسمى أدناه S- بلوك. إجمالي عدد كتل GOST S هو ثمانية ، أي نفس عدد التكرارات اللاحقة. كل S- بلوكيمثل تبديل الأرقام من 0 إلى 15. يقع أول 4 بتات اللاحقة على مدخلات S-box الأول ، والثاني - على مدخلات الثانية ، وما إلى ذلك. يتم دمج مخرجات جميع الصناديق S الثمانية في كلمة 32 بت ، ثم يتم نقل الكلمة بأكملها بشكل دوري إلى اليسار (إلى البتات الأكثر أهمية) بمقدار 11 بت. يمكن أن تكون جميع الصناديق S الثمانية مختلفة. في الواقع ، يمكن أن تكون مادة أساسية إضافية ، ولكنها في الغالب تكون معلمة مخطط شائعة لمجموعة معينة من المستخدمين. يشير نص المعيار إلى أن تسليم ملء وحدات الاستبدال (كتل S) يتم بالطريقة المحددة ، أي مطور الخوارزمية. وافق مجتمع مطوري CIPF الروس على العقد البديلة المستخدمة على الإنترنت.

يتم تنفيذ فك التشفير بنفس طريقة التشفير ، ولكن يتم عكس ترتيب المفاتيح الفرعية k i.

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

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

1. وضعاستبدال بسيطيقبل البيانات كمدخلات ، وحجمها مضاعف 64 بت. نتيجة التشفير هي إدخال النص ، وتحويله في كتل من 64 بت في حالة التشفير مع دورة "32-3" ، وفي حالة فك التشفير - مع دورة "32-P".

2. وضعالتحجيميقبل البيانات من أي حجم كمدخلات ، بالإضافة إلى معلمة 64 بت إضافية - رسالة المزامنة. أثناء العملية ، يتم تحويل رسالة المزامنة في دورة "32-Z" ، وتنقسم النتيجة إلى جزأين. يضاف الجزء الأول المقياس 2 32 بقيمة ثابتة تبلغ 1010101 16. إذا كان الجزء الثاني يساوي 2 32-1 ، فلن تتغير قيمته ، وإلا فإنه يضاف المقياس 2 32-1 بقيمة ثابتة 1010104 16. القيمة التي يتم الحصول عليها من خلال الجمع بين كلا الجزأين المحولين ، المسماة جاما المشفرة ، تدخل الحلقة "32-3" ، وتكون نتيجتها عبارة عن وحدة ثنائية مضافة مع كتلة 64 بت من بيانات الإدخال. إذا كانت الأخيرة أقل من 64 بت ، فسيتم تجاهل البتات الإضافية للقيمة المستلمة. يتم إرسال القيمة الناتجة إلى الإخراج. في حالة استمرار وجود بيانات واردة ، يتم تكرار الإجراء: يتم تحويل الكتلة المكونة من أجزاء 32 بت إلى أجزاء ، وهكذا.

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

4. وضع الإنتاجإدراج التقليديأخذ بيانات الإدخال التي لا يقل حجمها عن كتلتين كاملتين 64 بت ، ويعيد كتلة 64 بت من البيانات ، تسمى إدراج انتحال. يتم تعيين قيمة 64 بت المؤقتة على 0 ، ثم ، بينما توجد بيانات إدخال ، يتم إضافة modulo 2 إلى مستوى البت مع نتيجة تنفيذ دورة "16-3" ، والتي يكون إدخالها هو كتلة بيانات الإدخال . بعد نهاية الإدخال ، يتم إرجاع القيمة المؤقتة كنتيجة.

تحليل الشفرات

يستخدم تشفير GOST 28147-89 مفتاح 256 بت وحجم مساحة المفتاح هو 2256. لا يوجد جهاز كمبيوتر للأغراض العامة موجود حاليًا يمكنه تخمين مفتاح في أقل من عدة مئات من السنين. تم تصميم المعيار الروسي GOST 28147-89 بهامش كبير ويتجاوز معيار DES الأمريكي بعدة أوامر من حيث الحجم مع حجم مفتاحه الحقيقي 56 بت وحجم المساحة الرئيسية 2 56 فقط.

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

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

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

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

خوارزمية التشفير GOST 28147-89. طريقة الاستبدال البسيطة. - أرشيف WASM.RU

"بينما أنت على قيد الحياة ، لا تمت ، انظر إلى هذا العالم.
كثيرون هنا لديهم روح ميتة - لقد ماتوا في الداخل.
لكنهم يمشون ويضحكون غير مدركين أنهم غير موجودين ،
قالت لي لا تتسرع في الموت.
أريا ، "فوق هناك"
2.1 شبكات Feistel.
2.2 كتلة التشفير GOST 28147-89

3.1 معلومات أساسية
3.2 الخطوة الرئيسية في تحويل العملات المشفرة
3.3 الدورات الأساسية:“ 32-З” , “ 32 ر” .

4.1 تنفيذ الخطوة الرئيسية لتحويل العملات المشفرة
4.2 زيادة سرعة الخوارزمية
5. متطلبات المعلومات الأساسية
6. قائمة الأدب المستخدم
7. شكرًا.

مقدمة.

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

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

مقدمة لكتلة الأصفار.

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

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

ترأس د. هورست فيستل.

2.1 شبكات Feistel

كانت بنية طريقة التشفير الجديدة التي اقترحها Feistel في الأدب الكلاسيكي تسمى "معمارية Feistel" ، ولكن على هذه اللحظةفي الأدب الروسي والأجنبي ، يتم استخدام مصطلح أكثر رسوخًا - "شبكة Feistel" أو Feistel`s NetWork. بعد ذلك ، وفقًا لهذه البنية ، تم إنشاء شفرة "Lucifer" - والتي تم نشرها لاحقًا وتسببت في موجة جديدة من الاهتمام بالتشفير بشكل عام.

فكرة بنية شبكة Feistel هي كما يلي: ينقسم تدفق معلومات الإدخال إلى كتل من n بت في الحجم ، حيث n هو رقم زوجي. تنقسم كل كتلة إلى جزأين - L و R ، ثم يتم إدخال هذه الأجزاء في تشفير كتلة تكراري ، حيث يتم تحديد نتيجة المرحلة j-th من خلال نتيجة المرحلة السابقة j-1! يمكن توضيح ذلك بمثال:

أرز. 1

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

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

لكي تكون فكرة شبكات Feistel واضحة تمامًا ، ضع في اعتبارك أبسط حالة موضحة في الشكل. أرز. 1، حيث في الوظيفة A - سيتم تنفيذ العمليات "mod 2" ("xor") ، ولكن هذا بروتوزوانفي حالة أكثر خطورة ، على سبيل المثال ، إخفاء المعلومات ذات الأهمية الوطنية ، يمكن أن تكون الوظيفة A أكثر تعقيدًا (بقدر ما رأيت ، يمكن أن تكون الوظيفة A معقدة للغاية بالفعل):

البيانات الأولية:

L = 1110 ب ، R = 0101 ، K = 1111 ب

احصل على نص مشفر

1. (R + K) mod 2 4 = Smod، Smod = 0100b

2. (Smod + L) mod 2 = Sxor، Sxor = 1010b

3. L = R ، R = Sxor

L = 0101b ، R = 1010b

دعونا نشرح خطواتنا:

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

أرز. 2

أشرت هنا إلى الأسس بسهم ، كما ترون ، كان ينبغي أن تكون النتيجة 10100 ، ولكن نظرًا لتجاهل الحمل أثناء عملية mod 2 4 ، نحصل على 0100.

2. تسمى هذه العملية في الأدب mod 2 ، في لغة التجميع يتم تنفيذها بواسطة الأمر XOR. لكن لها أكثر الاسم الصحيحوزارة الدفاع 2 1. بدون هذه العملية الفريدة ، من الصعب إنشاء خوارزمية تشفير سريعة وسهلة التنفيذ ، وفي نفس الوقت ، تكون مقاومة تمامًا للتشفير. تفرد هذه العملية يكمن في حقيقة أنها عكس نفسها! على سبيل المثال ، إذا كان الرقم A هو XORed بالرقم B ، فستكون النتيجة C ، في المستقبل يكفي إعادة XOR الأرقام B و C معًا للحصول على القيمة السابقة لـ A!

في هذه العملية حصلنا على 1010 بالأرقام 1110 و 0100 ، لنعود 1110 ، يكفي XOR الأرقام 0100 و 1010 معًا! يمكن العثور على مزيد من التفاصيل حول هذه العملية في المقالة المضمنة في الموقع. www.wasm.ru, « دليل الابتدائية لCRC_ خوارزميات الكشف عن الخطأ»الكاتب الذي روس إن وليامز. هناك فقرة في هذا العمل - " 5. الحساب الثنائيباستثناء التحويلات". يتم وصف العملية في هذه المقالة إكسور!أصرخ لأنه في هذا المقال يتم وصف هذه العملية بطريقة تجعل القارئ لا يفهم فقط كيفية عمل هذه العملية ، بل يبدأها انظر ، اسمع واشعر!

3. يعد هذا الإجراء ضروريًا حتى تتمكن من الحصول على القيم الأصلية عند فك التشفير من النص المشفر.

2.2 كتلة التشفير GOST 28147-89

تنتمي خوارزمية التشفير GOST 28147 - 89 إلى فئة الأصفار الكتلية التي تعمل على بنية شبكة Feistel المتوازنة ، حيث يكون جزءان من كتلة المعلومات المحددة متساويين في الحجم. تم تطوير الخوارزمية في أعماق القسم الثامن من KGB ، وتحولت الآن إلى FAPSI ، وتم إصلاحها كمعيار تشفير. الاتحاد الروسيمرة أخرى في عام 1989 تحت الاتحاد السوفياتي.

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

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

الحد الأدنى النظري.

3.1 المعلومات الأساسية

كما قلت أعلاه ، يشارك ما يلي بنشاط في تشفير البيانات:

3.1.1. المفتاح هو سلسلة من ثمانية عناصر كل منها 32 بت. علاوة على ذلك ، سوف نشير إلى الرمز K والعناصر التي يتكون منها - k1، k2، k3، k4، k5، k6، k7، k8.

3.1.2 جدول الاستبدال عبارة عن مصفوفة من ثمانية صفوف وستة عشر عمودًا ، يشار إليها فيما بعد باسم Hij. كل عنصر عند تقاطع الصف i والعمود j يأخذ 4 بتات.

3.2 الخطوة الرئيسية لتحويل التشفير

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

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

يضاف جزء الإضافة من الكتلة R إلى العنصر الأساسي K mod 2 32. لقد وصفت عملية مماثلة أعلاه ، هنا الشيء نفسه هو فقط الأس ليس "4" ، ولكن "32" - سيتم الإشارة إلى نتيجة هذه العملية بواسطة Smod في المستقبل.

نقسم النتيجة التي تم الحصول عليها مسبقًا Smod إلى أربعة عناصر بت s7 و s6 و s5 و s4 و s3 و s2 و s1 و s0 وإدخالها في وظيفة الاستبدال. الاستبدال على النحو التالي: يتم تحديد عنصر Smod - s i ، من البداية نبدأ من أدنى عنصر ، ونستبدلها بالقيمة من جدول الاستبدال للصف الأول والعمود المشار إليه بقيمة العنصر s i. نمرر إلى عنصر s i +1 ونفعل الشيء نفسه ونستمر حتى نستبدل قيمة العنصر الأخير Smod - ستتم الإشارة إلى نتيجة هذه العملية على أنها Ssimple.

في هذه العملية ، يتم إزاحة قيمة Ssimple بشكل دوري إلى اليسار بمقدار 11 بتًا ونحصل على Srol.

نختار الجزء الثاني من الكتلة L ونضيف mod 2 مع Srol ، ونتيجة لذلك لدينا Sxor.

في هذه المرحلة ، يصبح الجزء L من الكتلة مساويًا لقيمة الجزء R ، ويتم تهيئة الجزء R بدوره بنتيجة Sxor ، وهذا يكمل وظيفة الخطوة الرئيسية!

3.3 الدورات الأساسية: "32-Z" ، "32-R".

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

بعد تقسيم المعلومات إلى كتل ، يجب تقسيم المفتاح إلى عناصر:

K = k1، k2، k3، k4، k5، k6، k7، k8

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

الدورات الأساسية ، كيف أقول ، معلمة: n - m. حيث n هو عدد خطوات تحويل التشفير الأساسية في الحلقة الأساسية ، و m هو "نوع" الحلقة الأساسية ، أي ما الذي يدور حوله ، تشفير "Z" أو تشفير "R" للبيانات.

تتكون دورة التشفير الأساسية 32-3 من 32 خطوة تشفير أساسية. يتم إدخال الكتلة N وعنصر المفتاح K في الوظيفة التي تنفذ إجراءات الخطوة ، وتحدث الخطوة الأولى مع k1 ، والثانية فوق النتيجة بالعنصر k2 ، إلخ. وفق المخطط التالي:

k1، k2، k3، k4، k5، k6، k7، k8، k1، k2، k3، k4، k5، k6، k7، k8، k1، k2، k3، k4، k5، k6، k7، k8k8، k7، k6، k5، k4، k3، k2، k1

تستمر عملية فك التشفير 32-P بطريقة مماثلة ، ولكن يتم تغذية العناصر الأساسية بترتيب عكسي:

k1، k2، k3، k4، k5، k6، k7، k8، k8، k7، k6، k5، k4، k3، k2، k1، k8، k7، k6، k5، k4، k3، k2، k1، k8، k7، k6، k5، k4، k3، k2، k1

يمارس.

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

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

البيانات الأولية:

لنأخذ كتلة من المعلومات N = 0102030405060708h ، هنا الأجزاء L و R متساوية:

L = 01020304h ، R = 05060708h ، خذ المفتاح:

ك = ' مثل 28 zw37 q839 7342واجهة مستخدم 23 8e2t wqm2 ewp1 '(هذه رموز ASCII ، لعرض التمثيل السداسي العشري ، يمكنك فتح هذا الملف في وضع العرض في القائد الكليالضغط على المفتاح " F3"ثم المفتاح" 3 "). في هذا المفتاح ، ستكون قيم العنصر:

k1 = 'as28' ، k2 = 'zw37' ، k3 = 'q839' ، k4 = '7342'

k5 = 'ui23' ، k6 = '8e2t' ، k7 = 'wqm2' ، k8 = 'ewp1'

خذ أيضًا جدول الاستبدال التالي:

أرز. 3

هنا يتم ترقيم الصفوف من 0 إلى 7 ، والأعمدة من 0 إلى F.

تحذير:يتم أخذ جميع المعلومات ، بما في ذلك المفتاح مع جدول الاستبدال ، كمثال للنظر في الخوارزمية!

باستخدام "البيانات الأولية" ، تحتاج إلى الحصول على نتيجة إجراء الخطوة الرئيسية لتحويل التشفير.

1. حدد الجزء R = 05060708h والعنصر الرئيسي k1 = "as28" ، في الشكل السداسي العشري ، سيبدو العنصر الرئيسي كما يلي: 61733238h. الآن نقوم بعملية الجمع 2 32:

أرز. 4

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

أقوم بمثل هذه العملية بأمر المجمع يضيف:

؛ eax = R ، ebx = 'as28'

نتيجة هذه العملية هي Smod = 66793940h

2. الآن العملية الأكثر تعقيدًا ، ولكن إذا نظرت عن كثب ، لم تعد مخيفة كما تبدو للوهلة الأولى. دعنا نتخيل Smod بالشكل التالي:

أرز. 5

حاولت تخيل عناصر Smod في الشكل ، لكنني سأشرح على أي حال:

s0 = 0 ، s1 = 4 ، s2 = 9 ، إلخ.

الآن ، بدءًا من أدنى عنصر s0 ، نقوم باستبداله. تذكر الفقرة 3.2 الخطوة الرئيسية لتحويل التشفير»أنا صف ، و s i عمود ، ونحن نبحث عن قيمة في صف الصفر وعمود الصفر:

الشكل 6

لذا فإن القيمة الحالية لـ Smod ليست 6679394 0 ح و 6679394 5 ح.

ننتقل إلى استبدال s1 ، أي أربعة. باستخدام الصف الأول والعمود الرابع (s1 = 4!). لنلق نظرة على الصورة:

أرز. 7

الآن القيمة هي Smod ، وليس 667939 4 5 ح ، 667939 2 5 ح. أفترض أن خوارزمية الاستبدال أصبحت الآن واضحة للقارئ ، ويمكنني القول أنه بعد النتيجة النهائية لـ Ssimple سيكون لها القيمة التالية - 11e10325h.

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

يجب علينا تحويل Ssimple الناتج 11 بت إلى اليسار.

أرز. 8

كما ترى ، هذا الإجراء بسيط للغاية ، ويتم تنفيذه بواسطة أمر لغة تجميع واحد - لفافةوكانت نتيجة عملية Srol هذه 0819288Fh.

4. الآن يبقى الجزء L من كتلة المعلومات الخاصة بنا إلى XOR مع القيمة Srol. آخذ الآلة الحاسبة من w2k sp4 وأحصل على Sxor = 091b2b8bh.

5. هذا الإجراء نهائي ونقوم ببساطة بتعيين وتنظيف R قيمة الجزء L ، وتهيئة الجزء L بقيمة Sxor.

النتيجة النهائية:

L = 091b2b8bh ، R = 01020304h

4.2 زيادة سرعة الخوارزمية

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

عندما قمت بتطبيق خوارزمية التشفير في برنامجي ، قمت بما يلي:

1. جزء محدد من الكتلة L في سجل eax ، و R في edx.

2. تمت التهيئة في سجل esi مع عنوان المفتاح الموسع ، والمزيد حول ذلك أدناه.

3. لقد قمت بتعيين قيمة عنوان جدول الاستبدال الموسع إلى سجل ebx ، والمزيد حول هذا أدناه

4. مرت معلومات النقاط 1 ، 2 ، 3 إلى وظيفة الدورة الأساسية 32 - Z أو 32 - R ، حسب الحالة.

إذا نظرت إلى مخطط توفير العناصر الأساسية في الفقرة " الدورات الأساسية: "32-Z" ، "32-R""، ثم يمكن تمثيل مفتاحنا للدورة الأساسية 32 - Z على النحو التالي:

K 32-Z =

'as28'، 'zw37'، 'q839'، '7342'، 'ui23'، '8e2t'، 'wqm2'، 'ewp1'،

'as28'، 'zw37'، 'q839'، '7342'، 'ui23'، '8e2t'، 'wqm2'، 'ewp1'،

'ewp1'، 'wqm2'، '8e2t'، 'ui23'، '7342'، 'q839'، 'zw37'، 'as28'

أولئك. من البداية ، انتقل k1 ، k2 ، k3 ، k4 ، k5 ، k6 ، k7 ، k8 - ‘ as28 '،'zw37 '،'q839 '،' 7342 '،'ui23 '،' 8ه 2ر "،"wqm2 '،'ewp1 'هذا التسلسل يتكرر ثلاث مرات. ثم تنتقل العناصر بترتيب عكسي ، أي: k8، k7، k6، k5، k4، k3، k2، k1 - 'ewp1'، 'wqm2'، '8e2t'، 'ui23'، '7342'، 'q839'، 'zw37'، 'as28'.

لقد قمت بترتيب العناصر في المصفوفة مسبقًا بالترتيب الذي يجب تقديمها به في 32 - Z. وهكذا ، قمت بزيادة الذاكرة المطلوبة لكل مفتاح ، لكنني أنقذت نفسي من بعض عمليات التفكير التي لم أكن بحاجة إليها ، وزدت من سرعة خوارزمية لتقليل وقت الوصول إلى الذاكرة! هنا وصفت فقط المفتاح لـ 32 - Z ، للدورة 32 - R فعلت الشيء نفسه ، لكن باستخدام مخطط مختلف لتزويد العناصر ، والذي وصفته أيضًا في الفقرة " الدورات الأساسية: "32-Z" ، "32-R».

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

لذا ، لفهم ماهية جدول الاستبدال الممتد ، نحتاج إلى جدول تعويض ، على سبيل المثال ، سآخذ الجدول الموضح في الشكل. 3.

على سبيل المثال ، نحتاج إلى استبدال الرقم 66793940h. سأقدمها بالشكل التالي:

أرز. 9

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

إذن ، حول المصفوفة:

لنأخذ أول سطرين ، صفر وأول سطرين ، وننشئ مصفوفة من 256 بايت. نلاحظ الآن ميزة واحدة أنه إذا كنت بحاجة إلى تحويل 00h ، فستكون النتيجة 75 ساعة (بناءً على الشكل 3) - ضع هذه القيمة في المصفوفة عند الإزاحة 00h. نأخذ القيمة 01h ، نتيجة دالة الاستبدال هي 79h ، نضعها في المصفوفة عند الإزاحة 01 وهكذا حتى 0FFh ، والتي ستعطينا 0FCh ، والتي سنضعها في المصفوفة عند الإزاحة 0FFh. لذلك حصلنا على جدول ممتد من الاستبدالات للمجموعة الأولى من السلاسل: الأولى والصفر. لكن لا تزال هناك ثلاث مجموعات: الصفحة الثانية 2 ، الصفحة 3 ، الصفحة الثالثة 4 ، الصفحة 5 ، الصفحة الرابعة 6 ، الصفحة 7. مع هذه المجموعات الثلاث ، نتقدم بنفس الطريقة كما في المجموعة الأولى. والنتيجة هي جدول استبدال موسع!

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

lea ebx، stretched_table_simple

mov eax ، [ضع الرقم ليحل محله]

أضف ebx ، 100h ؛ انتقل إلى العقدتين التاليتين

sub ebx ، 300 ساعة ؛ بحيث يشير ebx في المستقبل إلى الجدول

الآن ميزة أخرى ، لم نستبدل الإجراءات السابقة فحسب ، بل قمنا أيضًا بتحويل الرقم بمقدار 8 بتات إلى اليسار! علينا فقط تحويل الرقم 3 بتات أخرى إلى اليسار:

ونحصل على نتيجة العملية rol eax ، 11!

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

متطلبات المعلومات الأساسية.

كما هو مذكور في مقال Andrey Vinokurov ، يتم اختيار المفتاح وفقًا لمعيارين:

معيار التوزيع المتساوي للبتات بين القيمتين 1 و 0. عادةً ما يكون معيار التوزيع المتساوي للبتات هو معيار بيرسون ("مربع كاي").

هذا يعني أن المفتاح ، من حيث المبدأ ، يمكن لأي رقم. أي عند تكوين الجزء التالي من المفتاح ، فإن احتمال تهيئته بواحد أو صفر هو 50/50!

يرجى ملاحظة أن المفتاح يحتوي على ثمانية عناصر ، كل 32 بتة ، لذلك هناك 32 * 8 = 256 بت في المجموع في المفتاح والرقم مفاتيح ممكنة 2256! ألا تصدمك؟

معايير السلسلة.

إذا نظرنا إلى مفتاحنا ، الذي ذكرته في الفقرة " 4.1 تنفيذ الخطوة الرئيسية لتحويل العملة المشفرة"، ثم ستلاحظ أن الإدخال التالي صحيح:

أرز. 10

في إحدى العبارات ، لا ينبغي تكرار قيمة k 1 ليس في k 2 ، وليس في أي عنصر آخر من عناصر المفتاح.

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

الآن حول اختيار جدول الاستبدال:

الآن دعنا نتحدث عن كيفية اختيار جدول الاستبدال الصحيح. الشرط الرئيسي لاختيار جداول الاستبدال هو ظاهرة "عدم التكرار" للعناصر ، كل منها بحجم 4 بتات. كما رأيت أعلاه ، يتكون كل صف من جدول الاستبدال من القيم 0h ، 1h ، 2h ، 3h ، ... ، 0fh. لذا فإن المطلب الرئيسي هو أن كل سطر يحتوي على القيم 0h ، 1h ، 2h ، ... ، 0fh وكل قيمة من هذا القبيل في حالة واحدة. على سبيل المثال ، التسلسل:

1 2 3 4 5 6 7 8 9 أ ب ج د هـ و

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

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

كيف تبدو أسهل؟ وإليك كيف ، على سبيل المثال ، اخترنا العنصر s0 = 0Fh ، 01111b من الرقم أعلاه. احتمال استبدال البتة الأولى بواحد أو صفر هو 0.5! احتمالية استبدال البتات الثانية والثالثة والرابعة ، كل بت ، معتبرة بشكل منفصل ، بواسطة الآحاد أو الأصفار هي أيضًا 0.5. عند اختيار s1 = 0Eh ، سنستبدل احتمال أننا صفر بت ، وهذا هو "0" ، بصفر أو واحد يساوي - 0.5! وبالتالي ، وفقًا لهذا المعيار ، لا يوجد انتظام بين استبدال بتات الصفر من العناصر s0 ، s1! نعم ، يمكنك استبدال الآحاد ، ولكن يمكنك أيضًا وضع الأصفار.

لتقييم الجدول وفقًا لهذا المعيار ، يمكنك إنشاء جدول معاملات الارتباط المحسوبة بواسطة الصيغة:

إذا كانت p = 1 ، فإن قيمة البتة j عند الإخراج تساوي قيمة البتة i عند الإدخال لأي مجموعة من البتات عند الإدخال ؛

إذا كانت p = -1 ، فإن قيمة البت j عند الإخراج تكون دائمًا معكوس بتة الإدخال i ؛

إذا كانت p = 0 ، فإن بتة الخرج j تأخذ القيمتين 0 و 1 باحتمالية متساوية لأي قيمة ثابتة لبتة الإدخال i.

لنأخذ مثالاً من سطر واحد:

دعنا نقسمها إلى مكونات:

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

نأخذ البتة 0 من الرقم 0 (0) عند الإدخال والبت 0 من الرقم 0 عند الإخراج (1) ونقوم بتنفيذ العملية 0 XOR 1 = 1.

نأخذ البتة 0 من الرقم الأول (1) عند الإدخال والبت 0 من الرقم الأول عند الإخراج (1) ونقوم بتنفيذ العملية 1 XOR 1 = 0.

نأخذ البتة 0 من الرقم الثاني (0) عند الإدخال والبت 0 من الرقم الثاني عند الإخراج (0) ونقوم بتنفيذ العملية 0 XOR 0 = 0.

نأخذ البتة 0 من الرقم الثالث (1) عند الإدخال والبت 0 من الرقم الثالث عند الإخراج (1) ونقوم بتنفيذ العملية 1 XOR 1 = 0.

بعد إجراء عمليات XOR بالتتابع في مثل هذا التسلسل ، نحسب عدد جميع القيم غير الصفرية ، ونحصل على القيمة 6. ومن ثم P 00 = 1- (6/2 4-1) = 0.25. لذلك ، اتضح أن قيمة البتة 0 عند الإخراج تساوي قيمة البتة 0 عند الإدخال في 4 حالات من أصل 16 ؛

جدول الاحتمالات النهائي:

كما يتضح من جدول معاملات الارتباط ، فإن البتة 3 عند الإدخال مقلوبة بالنسبة إلى البتة 0 عند الخرج في 14 حالة من أصل 16 ، وهي نسبة 87.5٪ ، ولم يعد هذا مقبولاً لأنظمة التشفير العادية. من أجل التغيير ، لنأخذ مثالًا آخر:

سيكون جدول المعاملات على النحو التالي (من ليس كسولًا لإعادة الحساب)

حسنًا ، الأمور أسوأ في هذا الجدول - تبقى البتتان 1 و 2 من المجموعة دون تغيير! محلل التشفير لديه مكان للالتفاف حوله مع الأخذ في الاعتبار كل هذه المتطلبات ، وجد تعداد بسيط ("وجهاً لوجه") جداول تبديل تتوافق مع النظرية المحددة (اليوم - مجموعات 1276) وإليك بعضًا منها:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

قائمة الأدب المستخدم.

مقال بقلم أندريه فينوكوروف:

خوارزمية التشفير GOST 28147-89 واستخدامها وتنفيذها

لأجهزة الكمبيوتر منصات إنتلإلى x86.

فيما يلي رموز المصدر لتنفيذ خوارزمية التشفير.

مقال بقلم هورست فيستل:

التشفير وأمن الكمبيوتر.

(يمكن العثور عليها في نفس عنوان المقالة السابقة)

روس إن. ويليامز:

دليل أولي لخوارزميات اكتشاف الأخطاء CRC
منشور على الموقع www.كان م.en.

شكرًا.

أود أن أعرب عن امتناني لجميع زوار منتدى www.wasm.ru. لكن أود أن أشكر بشكل خاص ChS ، التي تُعرف حاليًا باسم SteelRat ، لقد ساعدني في فهم الأشياء التي ربما لن أفهمها أبدًا ، بالإضافة إلى مساعدتي في كتابة الفقرة: " متطلبات المعلومات الأساسية"، الجزء الرئيسي من هذه الفقرة كتبه. كما أنني ممتن للغاية لموظف KSTU. أ. Tupolev Anikin Igor Vyacheslavovich وسيكون من الخطيئة عدم ذكر كريس كاسبيرسكي ، لكونه كذلك ، وفولوديا / wasm.ru لتعليماته. أوه ، وأنا أخرج منه. أريد أيضًا أن أشير إلى Sega-Zero / Callipso لإحضار بعض الغابة الرياضية إلى ذهني.

ربما كان هذا كل ما أود أن أخبرك به.

سأكون ممتنا للنقد أو الأسئلة المتعلقة بهذه المقالة أو مجرد نصيحة. بيانات الاتصال بي: [بريد إلكتروني محمي]، ICQ - 337310594.

مع خالص التقدير ، يقطع الشر.

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

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

أريا ، "فوق هناك"

مقدمة

مقدمة لكتلة الأصفار

2.1 شبكات Feistel.
2.2 كتلة التشفير GOST 28147-89

الحد الأدنى النظري

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

3.3 الدورات الأساسية:“ 32-З” , “ 32 ر” .

يمارس

4.1 تنفيذ الخطوة الرئيسية لتحويل العملات المشفرة
4.2 زيادة سرعة الخوارزمية
5.
6. قائمة الأدب المستخدم
7. شكرًا.

مقدمة.

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

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

مقدمة لكتلة الأصفار.

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

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

ترأس د. هورست فيستل.

2.1 شبكات Feistel

كانت بنية طريقة التشفير الجديدة التي اقترحها Feistel في الأدب الكلاسيكي تسمى "معمارية Feistel" ، ولكن في الوقت الحالي في الأدب الروسي والأجنبي ، يتم استخدام مصطلح أكثر رسوخًا - "شبكة Feistel" أو Feistel's NetWork. بعد ذلك ، وفقًا لهذه البنية ، تم بناء تشفير Lucifer - والذي تم نشره لاحقًا وتسبب في موجة جديدة من الاهتمام بالتشفير بشكل عام.

فكرة بنية شبكة Feistel هي كما يلي: ينقسم تدفق معلومات الإدخال إلى كتل من n بت في الحجم ، حيث n هو رقم زوجي. تنقسم كل كتلة إلى جزأين - L و R ، ثم يتم إدخال هذه الأجزاء في تشفير كتلة تكراري ، حيث يتم تحديد نتيجة المرحلة j-th من خلال نتيجة المرحلة السابقة j-1! يمكن توضيح ذلك بمثال:

أرز. 1

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

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

لكي تكون فكرة شبكات Feistel واضحة تمامًا ، ضع في اعتبارك أبسط حالة موضحة في الشكل. أرز. 1، حيث في الوظيفة A - سيتم تنفيذ العمليات "mod 2" ("xor") ، ولكن هذا بروتوزوانفي حالة أكثر خطورة ، على سبيل المثال ، إخفاء المعلومات ذات الأهمية الوطنية ، يمكن أن تكون الوظيفة A أكثر تعقيدًا (بقدر ما رأيت ، يمكن أن تكون الوظيفة A معقدة للغاية بالفعل):

البيانات الأولية:

L = 1110 ب ، R = 0101 ، K = 1111 ب

احصل على نص مشفر

(R + K) mod 2 4 = Smod ، Smod = 0100b
(Smod + L) mod 2 = Sxor ، Sxor = 1010b
L = R ، R = Sxor

L = 0101b ، R = 1010b

دعونا نشرح خطواتنا:

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

أرز. 2

أشرت هنا إلى الأسس بسهم ، كما ترون ، كان ينبغي أن تكون النتيجة 10100 ، ولكن نظرًا لتجاهل الحمل أثناء عملية mod 2 4 ، نحصل على 0100.

تسمى هذه العملية في الأدب mod 2 ، في لغة التجميع يتم تنفيذها بواسطة الأمر XOR. لكن اسمه الأكثر صحة هو mod 2 1. بدون هذه العملية الفريدة ، من الصعب إنشاء خوارزمية تشفير سريعة وسهلة التنفيذ ، وفي نفس الوقت ، تكون مقاومة تمامًا للتشفير. تفرد هذه العملية يكمن في حقيقة أنها عكس نفسها! على سبيل المثال ، إذا كان الرقم A هو XORed بالرقم B ، فستكون النتيجة C ، في المستقبل يكفي إعادة XOR الأرقام B و C معًا للحصول على القيمة السابقة لـ A!

في هذه العملية حصلنا على 1010 بالأرقام 1110 و 0100 ، لنعود 1110 ، يكفي XOR الأرقام 0100 و 1010 معًا! يمكن العثور على مزيد من التفاصيل حول هذه العملية في المقالة المضمنة في الموقع. www.wasm.ru, « دليل الابتدائية لCRC_ خوارزميات الكشف عن الخطأ»الكاتب الذي روس إن وليامز. هناك فقرة في هذا العمل - 5. ثنائي الحساب بدون حمل". يتم وصف العملية في هذه المقالة إكسور!أصرخ لأنه في هذا المقال يتم وصف هذه العملية بطريقة تجعل القارئ لا يفهم فقط كيفية عمل هذه العملية ، بل يبدأها انظر ، اسمع واشعر!

يعد هذا الإجراء ضروريًا حتى تتمكن من الحصول على القيم الأصلية عند فك التشفير من النص المشفر.

2.2 كتلة التشفير GOST 28147-89

تنتمي خوارزمية التشفير GOST 28147 - 89 إلى فئة الأصفار الكتلية التي تعمل على بنية شبكة Feistel المتوازنة ، حيث يكون جزءان من كتلة المعلومات المحددة متساويين في الحجم. تم تطوير الخوارزمية في أحشاء القسم الثامن من KGB ، وتحولت الآن إلى FAPSI ، وتم تكريسها كمعيار تشفير للاتحاد الروسي في عام 1989 تحت الاتحاد السوفيتي.

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

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

الحد الأدنى النظري.

3.1 المعلومات الأساسية

كما قلت أعلاه ، يشارك ما يلي بنشاط في تشفير البيانات:

3.1.1. المفتاح هو سلسلة من ثمانية عناصر كل منها 32 بت. علاوة على ذلك ، سوف نشير إلى الرمز K والعناصر التي يتكون منها - k1، k2، k3، k4، k5، k6، k7، k8.

3.1.2 جدول الاستبدال عبارة عن مصفوفة من ثمانية صفوف وستة عشر عمودًا ، يشار إليها فيما بعد باسم Hij. كل عنصر عند تقاطع الصف i والعمود j يأخذ 4 بتات.

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

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

يضاف جزء الإضافة من الكتلة R إلى العنصر الأساسي K mod 2 32. لقد وصفت عملية مماثلة أعلاه ، هنا نفس الشيء ، الأس فقط ليس "4" ، ولكن "32" - سيتم الإشارة إلى نتيجة هذه العملية بواسطة Smod في المستقبل.
نقسم النتيجة التي تم الحصول عليها مسبقًا Smod إلى أربعة عناصر بت s7 و s6 و s5 و s4 و s3 و s2 و s1 و s0 وإدخالها في وظيفة الاستبدال. الاستبدال على النحو التالي: يتم تحديد عنصر Smod - s i ، من البداية نبدأ من أصغر عنصر ، ونستبدلها بالقيمة من جدول الاستبدالات بواسطة i - الصف والعمود المشار إليه بقيمة العنصر s i . نمرر إلى عنصر s i +1 ونفعل الشيء نفسه ونستمر حتى نستبدل قيمة العنصر الأخير Smod - ستتم الإشارة إلى نتيجة هذه العملية على أنها Ssimple.
في هذه العملية ، يتم إزاحة قيمة Ssimple بشكل دوري إلى اليسار بمقدار 11 بتًا ونحصل على Srol.
نختار الجزء الثاني من الكتلة L ونضيف mod 2 مع Srol ، ونتيجة لذلك لدينا Sxor.
في هذه المرحلة ، يصبح الجزء L من الكتلة مساويًا لقيمة الجزء R ، ويتم تهيئة الجزء R بدوره بنتيجة Sxor ، وهذا يكمل وظيفة الخطوة الرئيسية!

3.3 الدورات الأساسية: "32-Z" ، "32-R".

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

بعد تقسيم المعلومات إلى كتل ، يجب تقسيم المفتاح إلى عناصر:

K = k1، k2، k3، k4، k5، k6، k7، k8

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

الدورات الأساسية ، كيف أقول ، معلمة: n - m. حيث n هو عدد خطوات تحويل التشفير الأساسية في الحلقة الأساسية ، و m هو "نوع" الحلقة الأساسية ، أي ما الذي يدور حوله ، تشفير "Z" أو تشفير "R" للبيانات.

تتكون دورة التشفير الأساسية 32-3 من 32 خطوة تشفير أساسية. يتم إدخال الكتلة N وعنصر المفتاح K في الوظيفة التي تنفذ إجراءات الخطوة ، وتحدث الخطوة الأولى مع k1 ، والثانية فوق النتيجة بالعنصر k2 ، إلخ. وفق المخطط التالي:

k1، k2، k3، k4، k5، k6، k7، k8، k1، k2، k3، k4، k5، k6، k7، k8، k1، k2، k3، k4، k5، k6، k7، k8k8، k7، k6، k5، k4، k3، k2، k1

تستمر عملية فك التشفير 32-P بطريقة مماثلة ، ولكن يتم تغذية العناصر الأساسية بترتيب عكسي:

k1، k2، k3، k4، k5، k6، k7، k8، k8، k7، k6، k5، k4، k3، k2، k1، k8، k7، k6، k5، k4، k3، k2، k1، k8، k7، k6، k5، k4، k3، k2، k1

يمارس.

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

البيانات الأولية:

لنأخذ كتلة من المعلومات N = 0102030405060708h ، هنا الأجزاء L و R متساوية:

L = 01020304h ، R = 05060708h ، خذ المفتاح:

ك = ' مثل 28 zw37 q839 7342واجهة مستخدم 23 8e2t wqm2 ewp1 '(هذه رموز ASCII ، لعرض التمثيل السداسي العشري ، يمكنك فتح هذا الملف في وضع العرض في Total Commander بالضغط على " F3"ثم المفتاح" 3 "). في هذا المفتاح ، ستكون قيم العنصر:

k1 = 'as28' ، k2 = 'zw37' ، k3 = 'q839' ، k4 = '7342'

k5 = 'ui23' ، k6 = '8e2t' ، k7 = 'wqm2' ، k8 = 'ewp1'

خذ أيضًا جدول الاستبدال التالي:

أرز. 3

هنا يتم ترقيم الصفوف من 0 إلى 7 ، والأعمدة من 0 إلى F.

تحذير:يتم أخذ جميع المعلومات ، بما في ذلك المفتاح مع جدول الاستبدال ، كمثال للنظر في الخوارزمية!

باستخدام "البيانات الأولية" ، تحتاج إلى الحصول على نتيجة إجراء الخطوة الرئيسية لتحويل التشفير.

نختار الجزء R = 05060708h والعنصر الرئيسي k1 = "as28" ، في الشكل السداسي العشري ، سيبدو العنصر الرئيسي كما يلي: 61733238h. الآن نقوم بعملية الجمع 2 32:

أرز. 4

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

أقوم بمثل هذه العملية بأمر المجمع يضيف:

؛ eax = R ، ebx = 'as28'

نتيجة هذه العملية هي Smod = 66793940h

الآن العملية الأكثر تعقيدًا ، ولكن إذا نظرت عن كثب ، لم تعد مخيفة كما تبدو للوهلة الأولى. دعنا نتخيل Smod بالشكل التالي:

النقش لا تحفظ

أرز. 5

حاولت تخيل عناصر Smod في الشكل ، لكنني سأشرح على أي حال:

s0 = 0 ، s1 = 4 ، s2 = 9 ، إلخ.

الآن ، بدءًا من أدنى عنصر s0 ، نقوم باستبداله. تذكر الفقرة 3.2 الخطوة الرئيسية لتحويل التشفير»أنا صف ، و s i عمود ، ونحن نبحث عن قيمة في صف الصفر وعمود الصفر:

الشكل 6

لذا فإن القيمة الحالية لـ Smod ليست 6679394 0 ح و 6679394 5 ح.

ننتقل إلى استبدال s1 ، أي أربعة. باستخدام الصف الأول والعمود الرابع (s1 = 4!). لنلق نظرة على الصورة:

أرز. 7

الآن القيمة هي Smod ، وليس 667939 4 5 ح ، 667939 2 5 ح. أفترض أن خوارزمية الاستبدال أصبحت الآن واضحة للقارئ ، ويمكنني القول أنه بعد النتيجة النهائية لـ Ssimple سيكون لها القيمة التالية - 11e10325h.

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

يجب علينا تحويل Ssimple الناتج 11 بت إلى اليسار.

أرز. 8

كما ترى ، هذا الإجراء بسيط للغاية ، ويتم تنفيذه بواسطة أمر لغة تجميع واحد - لفافةوكانت نتيجة عملية Srol هذه 0819288Fh.

الآن يبقى الجزء L من كتلة المعلومات الخاصة بنا إلى XOR بالقيمة Srol. آخذ الآلة الحاسبة من w2k sp4 وأحصل على Sxor = 091b2b8bh.
هذا الإجراء نهائي ونقوم ببساطة بتعيين R قيمة الجزء L وتنظيفها وتهيئة الجزء L بقيمة Sxor.

النتيجة النهائية:

L = 091b2b8bh ، R = 01020304h

4.2 زيادة سرعة الخوارزمية

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

عندما قمت بتطبيق خوارزمية التشفير في برنامجي ، قمت بما يلي:

اختر جزءًا من الكتلة L في سجل eax ، و R في edx.
تمت التهيئة في سجل esi بعنوان المفتاح الموسع ، والمزيد حول ذلك أدناه.
لقد قمت بتعيين قيمة عنوان جدول الاستبدال الموسع إلى سجل ebx ، والمزيد حول هذا أدناه
مرت معلومات النقاط 1 ، 2 ، 3 إلى وظيفة الدورة الأساسية 32 - Z أو 32 - R ، حسب الحالة.

إذا نظرت إلى مخطط توفير العناصر الأساسية في الفقرة " الدورات الأساسية: "32-Z" ، "32-R""، ثم يمكن تمثيل مفتاحنا للدورة الأساسية 32 - Z على النحو التالي:

K 32-Z =

'as28'، 'zw37'، 'q839'، '7342'، 'ui23'، '8e2t'، 'wqm2'، 'ewp1'،

'ewp1'، 'wqm2'، '8e2t'، 'ui23'، '7342'، 'q839'، 'zw37'، 'as28'

أولئك. من البداية ، انتقل k1 ، k2 ، k3 ، k4 ، k5 ، k6 ، k7 ، k8 - ‘ as28 '،'zw37 '،'q839 '،' 7342 '،'ui23 '،' 8ه 2ر "،"wqm2 '،'ewp1 'هذا التسلسل يتكرر ثلاث مرات. ثم تنتقل العناصر بترتيب عكسي ، أي: k8، k7، k6، k5، k4، k3، k2، k1 - 'ewp1'، 'wqm2'، '8e2t'، 'ui23'، '7342'، 'q839'، 'zw37'، 'as28'.

لقد قمت بترتيب العناصر في المصفوفة مسبقًا بالترتيب الذي يجب تقديمها به في 32 - Z. وهكذا ، قمت بزيادة الذاكرة المطلوبة لكل مفتاح ، لكنني أنقذت نفسي من بعض عمليات التفكير التي لم أكن بحاجة إليها ، وزدت من سرعة خوارزمية لتقليل وقت الوصول إلى الذاكرة! هنا وصفت فقط المفتاح لـ 32 - Z ، للدورة 32 - R فعلت الشيء نفسه ، لكن باستخدام مخطط مختلف لتزويد العناصر ، والذي وصفته أيضًا في الفقرة " الدورات الأساسية: "32-Z" ، "32-R».

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

لذا ، لفهم ماهية جدول الاستبدال الممتد ، نحتاج إلى جدول تعويض ، على سبيل المثال ، سآخذ الجدول الموضح في الشكل. 3.

على سبيل المثال ، نحتاج إلى استبدال الرقم 66793940h. سأقدمها بالشكل التالي:

النقش لا تحفظ

أرز. 9

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

إذن ، حول المصفوفة:

لنأخذ أول سطرين ، صفر وأول سطرين ، وننشئ مصفوفة من 256 بايت. نلاحظ الآن ميزة واحدة أنه إذا كنت بحاجة إلى تحويل 00h ، فستكون النتيجة 75 ساعة (بناءً على الشكل 3) - ضع هذه القيمة في المصفوفة عند الإزاحة 00h. نأخذ القيمة 01h ، نتيجة دالة الاستبدال هي 79h ، نضعها في المصفوفة عند الإزاحة 01 وهكذا حتى 0FFh ، والتي ستعطينا 0FCh ، والتي سنضعها في المصفوفة عند الإزاحة 0FFh. لذلك حصلنا على جدول ممتد من الاستبدالات للمجموعة الأولى من السلاسل: الأولى والصفر. لكن لا تزال هناك ثلاث مجموعات: الصفحة الثانية 2 ، الصفحة 3 ، الصفحة الثالثة 4 ، الصفحة 5 ، الصفحة الرابعة 6 ، الصفحة 7. مع هذه المجموعات الثلاث ، نتقدم بنفس الطريقة كما في المجموعة الأولى. والنتيجة هي جدول استبدال موسع!

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

lea ebx، stretched_table_simple

mov eax ، [ضع الرقم ليحل محله]

أضف ebx ، 100h ؛ انتقل إلى العقدتين التاليتين

sub ebx ، 300 ساعة ؛ بحيث يشير ebx في المستقبل إلى الجدول

الآن ميزة أخرى ، لم نستبدل الإجراءات السابقة فحسب ، بل قمنا أيضًا بتحويل الرقم بمقدار 8 بتات إلى اليسار! علينا فقط تحويل الرقم 3 بتات أخرى إلى اليسار:

ونحصل على نتيجة العملية rol eax ، 11!

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

متطلبات المعلومات الأساسية.

كما هو مذكور في مقال Andrey Vinokurov ، يتم اختيار المفتاح وفقًا لمعيارين:

- معيار التوزيع المتكافئ للبتات بين القيمتين 1 و 0. عادةً ما يعمل معيار بيرسون ("مربع كاي") كمعيار للتوزيع المتساوي للبتات.

هذا يعني أن المفتاح ، من حيث المبدأ ، يمكن لأي رقم. أي عند تكوين الجزء التالي من المفتاح ، فإن احتمال تهيئته بواحد أو صفر هو 50/50!

يرجى ملاحظة أن المفتاح يحتوي على ثمانية عناصر ، كل 32 بتة ، لذلك هناك 32 * 8 = 256 بت في المجموع وعدد المفاتيح الممكنة هو 2256! ألا تصدمك؟ 🙂

- معيار السلسلة.

إذا نظرنا إلى مفتاحنا ، الذي ذكرته في الفقرة " 4.1 تنفيذ الخطوة الرئيسية لتحويل العملة المشفرة"، ثم ستلاحظ أن الإدخال التالي صحيح:

أرز. 10

في إحدى العبارات ، لا ينبغي تكرار قيمة k 1 ليس في k 2 ، وليس في أي عنصر آخر من عناصر المفتاح.

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

الآن حول اختيار جدول الاستبدال:

الآن دعنا نتحدث عن كيفية اختيار جدول الاستبدال الصحيح. الشرط الرئيسي لاختيار جداول الاستبدال هو ظاهرة "عدم التكرار" للعناصر ، كل منها بحجم 4 بتات. كما رأيت أعلاه ، يتكون كل صف من جدول الاستبدال من القيم 0h ، 1h ، 2h ، 3h ، ... ، 0fh. لذا فإن المطلب الرئيسي هو أن كل سطر يحتوي على القيم 0h ، 1h ، 2h ، ... ، 0fh وكل قيمة من هذا القبيل في حالة واحدة. على سبيل المثال ، التسلسل:

1 2 3 4 5 6 7 8 9 أ ب ج د هـ و

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

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

كيف تبدو أسهل؟ وإليك كيف ، على سبيل المثال ، اخترنا العنصر s0 = 0Fh ، 01111b من الرقم أعلاه. احتمال استبدال البتة الأولى بواحد أو صفر هو 0.5! احتمالية استبدال البتات الثانية والثالثة والرابعة ، كل بت ، معتبرة بشكل منفصل ، بواسطة الآحاد أو الأصفار هي أيضًا 0.5. عند اختيار s1 = 0Eh ، سنستبدل احتمال أننا صفر بت ، وهذا هو "0" ، بصفر أو واحد يساوي - 0.5! وبالتالي ، وفقًا لهذا المعيار ، لا يوجد انتظام بين استبدال بتات الصفر من العناصر s0 ، s1! نعم ، يمكنك استبدال الآحاد ، ولكن يمكنك أيضًا وضع الأصفار. 🙂

لتقييم الجدول وفقًا لهذا المعيار ، يمكنك إنشاء جدول معاملات الارتباط المحسوبة بواسطة الصيغة:

- إذا كانت p = 1 ، فإن قيمة البتة j عند الخرج تساوي قيمة البتة i عند الإدخال لأي مجموعة من البتات عند الإدخال ؛

- إذا كانت p = -1 ، فإن قيمة البتة j عند الإخراج هي دائمًا انعكاس بتة الإدخال i ؛

- إذا كانت p = 0 ، فإن بتة الخرج j تأخذ القيمتين 0 و 1 مع احتمال متساوٍ لأي قيمة ثابتة لبتة الإدخال i.

لنأخذ مثالاً من سطر واحد:

د	ب	4	1	3	F	5	9	0	أ	ه	7	6	8	2	ج

دعنا نقسمها إلى مكونات:

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

- نأخذ البتة 0 من الرقم 0 (0) عند الإدخال والبت 0 من الرقم 0 عند الإخراج (1) نقوم بإجراء العملية 0 XOR 1 = 1.

- نأخذ البتة 0 من الرقم الأول (1) عند الإدخال والبتة 0 من الرقم الأول عند الإخراج (1) نقوم بإجراء العملية 1 XOR 1 = 0.

- نأخذ البتة 0 من الرقم الثاني (0) عند الإدخال والبتة 0 من الرقم الثاني عند الإخراج (0) نقوم بإجراء العملية 0 XOR 0 = 0.

- نأخذ البتة 0 من الرقم الثالث (1) عند الإدخال والبت 0 من الرقم الثالث عند الإخراج (1) نقوم بإجراء العملية 1 XOR 1 = 0.

بعد إجراء عمليات XOR بالتتابع في مثل هذا التسلسل ، نحسب عدد جميع القيم غير الصفرية ، ونحصل على القيمة 6. ومن ثم P 00 = 1- (6/2 4-1) = 0.25. لذلك ، اتضح أن قيمة البتة 0 عند الإخراج تساوي قيمة البتة 0 عند الإدخال في 4 حالات من أصل 16 ؛

جدول الاحتمالات النهائي:

سيكون جدول المعاملات على النحو التالي (من ليس كسولًا لإعادة الحساب)

	مدخل
مخرج		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

حسنًا ، الأمور أسوأ في هذا الجدول - تبقى البتتان 1 و 2 من المجموعة دون تغيير! محلل التشفير لديه مكان للالتفاف حوله مع الأخذ في الاعتبار كل هذه المتطلبات ، وجد تعداد بسيط ("وجهاً لوجه") جداول تبديل تتوافق مع النظرية المحددة (اليوم - مجموعات 1276) وإليك بعضًا منها:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

قائمة الأدب المستخدم.

مقال بقلم أندريه فينوكوروف:

خوارزمية التشفير GOST 28147-89 واستخدامها وتنفيذها

لأجهزة كمبيوتر منصة Intel x86.

(يمكن العثور عليها في: http://www.enlight.ru/crypto/frame.htm).

فيما يلي رموز المصدر لتنفيذ خوارزمية التشفير.

مقال بقلم هورست فيستل:

التشفير وأمن الكمبيوتر.

(يمكن العثور عليها في نفس عنوان المقالة السابقة)

روس إن. ويليامز:

دليل أولي لخوارزميات اكتشاف الأخطاء CRC

منشور على الموقع www.كان م.en.

شكرًا.

أود أن أعرب عن امتناني لجميع زوار المنتدى www.wasm.ru. لكن أود أن أشكر بشكل خاص ChS ، التي تُعرف حاليًا باسم SteelRat ، لقد ساعدني في فهم الأشياء التي ربما لن أفهمها أبدًا ، بالإضافة إلى مساعدتي في كتابة الفقرة: " متطلبات المعلومات الأساسية"، الجزء الرئيسي من هذه الفقرة كتبه. كما أنني ممتن للغاية لموظف KSTU. أ. Tupolev Anikin Igor Vyacheslavovich وسيكون من الخطيئة عدم ذكر كريس كاسبيرسكي ، لكونه كذلك ، وفولوديا / wasm.ru لتعليماته. اوه وانا اخرج منه :). أريد أيضًا أن أشير إلى Sega-Zero / Callipso لإحضار بعض الغابة الرياضية إلى ذهني.

ربما كان هذا كل ما أود أن أخبرك به.

سأكون ممتنا للنقد أو الأسئلة المتعلقة بهذه المقالة أو مجرد نصيحة. بيانات الاتصال بي: [بريد إلكتروني محمي]، ICQ - 337310594.

مع خالص التقدير ، يقطع الشر.

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

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

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

كيف يتم قياس أداء الكود؟ منذ أن كنت أول من تحدث عن هذا ، ثم بحق المكتشف سأقيسه في مقاييس 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 من tetrads ، يتم استخدام محولات البايت متعددة المدخلات المتوفرة في FPUs. تسمح هذه المفاتيح بالتحويل من أي بايت من المصدر إلى أي بايت للوجهة ، بواسطة فهارس موجودة في سجل فهرس 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 العالمية المتاحة في كل من معالجات إنتلوفي معالجات 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 ، وهي خطيئة عدم الحصول على براءة اختراع. وقد تم بالفعل إعداد وتقديم طلبات الحصول على براءات الاختراع (ما يصل إلى ثلاثة) ، لذلك ، اصطف السادة ورجال الأعمال - النساء والأطفال لديهم خصم.

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

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

يظهر مخطط الخوارزمية في الشكل. 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 ضد التحليل الخطي والتفاضلي للتشفير باستخدام جداول إحلال أقوى ؛ هذه الجداول ، التي هي بالفعل أكثر استقرارًا ، تم اقتراحها ، على سبيل المثال ، في خوارزمية 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 عملية تشفير. كما تبدو، هذا الهجوم، غير مجدية عمليا للفتح الحقيقي للخوارزمية.