سجل التحول ردود الفعل الخطية. سجل التحول الخطي مع التغذية الراجعة مثال على تسجيل التحول الخطي

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

أرز. 87.

أي دالة رياضية تؤدي عملية على البتات يمكن أن تكون بمثابة تغذية مرتدة. إن أبسط نوع من سجلات تغيير التغذية المرتدة هو سجل تحول التغذية المرتدة الخطي (LFSR). في LFSR ، التغذية المرتدة هي ببساطة عملية إضافة modulo 2 (XOR) على بعض بتات السجل ؛ تسمى قائمة هذه البتات سلسلة من الحنفيات ، أو نقاط الالتقاط ، كما هو موضح في الشكل. 88. في بعض الأحيان يسمى هذا النمط بتكوين فيبوناتشي. نظرًا لبساطة تسلسل التغذية الراجعة ، يمكن استخدام نظرية رياضية مطورة إلى حد ما لتحليل LFSR. على أي حال ، يتم تقييم جودة SRP المنتج من خلال مجموعة خاصة من الاختبارات.

أرز. 88.

تتم كتابة LFSR في شكل كثيرات الحدود. في هذه الحالة ، تشير درجة العنصر الأول من كثير الحدود إلى عدد البتات في سجل الإزاحة ، ويشير الأس الأسي للأعضاء المتبقين في كثير الحدود إلى نقاط الالتقاط التي سيتم استخدامها. لذلك ، على سبيل المثال ، كتابة x 4 + x + 1 تعني أنه سيتم استخدام سجل من أربعة عناصر ، حيث ستشارك بت b و b 0 في تكوين التغذية الراجعة (الشكل 89).

أرز. 89.4

ضع في اعتبارك تشغيل السجل الموضح في الشكل. 89. بدئها ، على سبيل المثال ، بالقيمة 0101 (يمكن إجراء التهيئة الأولية بأي تسلسل من البتات ، باستثناء سلسلة من الأصفار فقط ، حيث إن التغذية المرتدة في هذه الحالة ستشكل دائمًا قيمة صفر وسيفعل السجل لا تنتج PSP المتوقع). لذلك ، يوجد في السجل تحول إلى اليمين بموقف واحد. يتم إجبار البتة الأقل دلالة ، التي تساوي 1 ، على الخروج من السجل وتشكل البتة الأولى من PRS. تتم إضافة وحدات البت التي كانت في الموضعين b و b 0 قبل التحول إلى النموذج 2 وتشكيل وحدة جديدة

بت عالية من السجل. يظهر مثال توضيحي لتشغيل LFSR المدروس في الشكل. 90.

أرز. 90.

كما يظهر في الشكل. 90 ، سوف يمر ملء السجل بوزن 15 من أصل 16 حالة محتملة (لقد قررنا سابقًا أنه لا يمكن اعتبار الحالة السادسة عشرة ، عندما يكون LFSR هو 0000). بعد ذلك ، سيكون ملء السجل مساويًا للقيمة الأولية لـ 0101 ، وسيبدأ إنشاء تسلسل البتات في التكرار. سيكون تسلسل خرج السجل هو سلسلة البتات الأقل دلالة (حتى الخط الأفقي في الشكل 90): 101011110001001. ويطلق على حجم تسلسل البتات قبل تكراره اسم الفترة. لضمان الحد الأقصى لفترة LFSR معينة (على سبيل المثال ، لكي يمر السجل عبر جميع الحالات الداخلية المحتملة) ، يجب أن يكون متعدد الحدود الذي يحدد تشغيل السجل هو النمط البدائي 2. كما هو الحال مع الأعداد الأولية الكبيرة ، لا توجد طريقة توليد مثل هذه كثيرات الحدود. يمكن للمرء فقط أن يأخذ كثير الحدود ويتحقق مما إذا كان المقياس 2 غير قابل للاختزال أم لا. في الحالة العامة ، تعد كثيرة الحدود البدائية من الدرجة n مثل كثيرة الحدود غير القابلة للاختزال والتي هي مقسوم على x 2 "+1 ، ولكنها ليست مقسومًا على xd +1 لجميع d التي تكون قواسمها 2" -1. ب. يقدم Schneier جدولًا لبعض كثيرات الحدود ، والتي لا يمكن اختزالها من النوع 2.

بتلخيص المعرفة التي تم الحصول عليها نتيجة النظر في مثال تشغيل LFSR (الشكل 90) ، يمكننا القول أن n-bit LFSR يمكن أن يكون في إحدى الحالات الداخلية 2 "-1. نظريًا ، يمكن لمثل هذا السجل إنشاء تسلسل شبه عشوائي بفترة 2 ن -1 بت. تسمى هذه السجلات بسجلات LFSR بأقصى فترة. الناتج الناتج يسمى تسلسل t.

وزارة التربية والعلوم

الجامعة الاجتماعية للدولة الروسية

كلية تقنيات المعلومات

قسم حماية المعلومات

طرق التشفير ووسائل ضمان أمن المعلومات

عمل الدورة

"ص سجلات التحول مع ردود الفعل الخطية كمولدات أرقام شبه عشوائية "

مكتمل:

طالب في السنة الثالثة

مجموعة KZOI-D-3

لاريونوف ا.

التحقق:

مساعد. بارانوفا إي.

موسكو 2011
المحتوى

مقدمة ……………………………..…………………………………….3

1. الأسس النظرية للعمل…………………………………………4
   1. معلومات عامة حول سجلات تحويل التغذية الراجعة ………… ..4
      1. حول الأصفار الجارية على أساس RgCsLOS ………………… .. ……… 10
      2. حول التعقيد الخطي للتسلسل العشوائي الزائف المتولد PgCsLOS ………………………………………. …… 12
      3. حول استقلالية الارتباط للتسلسل الذي تم إنشاؤه للأرقام العشوائية الزائفة PrCsLOS ……… ..… .13
      4. حول الطرق الأخرى لفتح التسلسل الذي تم إنشاؤه للأرقام العشوائية الزائفة RgCsLOS …………………………………… .. 14
2. تنفيذ برنامج RgCsLOS كمولد تسلسل عشوائي زائف….…………………………….15
   1. مخطط معمم للخوارزمية ……………………………………… ... 15
   2. وصف وحدات البرنامج والواجهة. ………………… .16
   3. دليل المستخدم ………………………………………… ... 20

استنتاج ………………………………………………………………22

فهرس………………………………………………….....23

المرفق ألف ….………………………………………………………..24

المقدمة

الغرض من هذا العمل هو تطوير تطبيق برمجي ينفذ تشغيل مولد الأرقام العشوائية الزائفة بناءً على سجلات التحول مع التغذية الراجعة. يتم تطوير هذا التطبيق بواجهة رسومية باللغة C ++ لنظام التشغيل Windows.

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

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

1. الأسس النظرية للعمل

1.1 معلومات عامة حول سجلات المناوبة مع التغذية الراجعة الخطية

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

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

سجل التحول في ملاحظات الشكل

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

الشكل PgCsLOS Fibbonacci

بشكل عام ، ن يمكن أن يكون -bit PrCsLOS في أحد ملفاتن = 2 ن -1 الحالات الداخلية. هذا يعني أنه ، من الناحية النظرية ، يمكن لمثل هذا السجل إنشاء تسلسل شبه عشوائي مع فترة T = 2ن -1 بت. (عدد الحالات الداخلية والفترة متساويان N = Tmax = 2n -1 لأن ملء PrCsLOC بالأصفار سيؤدي إلى إخراج سجل الإزاحة سلسلة لا نهائية من الأصفار ، وهو أمر عديم الفائدة تمامًا). فقط مع تسلسلات ضغط معينة ، سوف يمر PrCsLOS دوريًا عبر كل 2ن -1 الحالات الداخلية ، مثل RgCsLOS هيRgSsLOS بأقصى فترة. النتيجة الناتجة تسمىتسلسل M..

مثال . يوضح الشكل أدناه PrCsLOS 4 بت مع نقرة من البتين الأول والرابع. إذا تمت تهيئته بالقيمة 1111 ، فقبل تكرار السجل ، ستأخذ الحالات الداخلية التالية:

رقم علامة التحول (الحالة الداخلية)	حالة التسجيل				بت الإخراج
القيمة البدائية
15 (العودة إلى الحالة الأولية)
16 (حالات التكرار)

سيكون تسلسل الإخراج عبارة عن سلسلة من البتات الأقل أهمية: 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 مع الفترة T = 15 ، العدد الإجمالي للحالات الداخلية المحتملة (باستثناء الصفر) ،ن = 2 4 -1 = 16-1 = 15 = Tmax لذلك ، تسلسل الإخراج هوم -تسلسل.

من أجل أن يكون لـ PgCsLOS معين فترة قصوى ، يجب أن يكون كثير الحدود المكون من تسلسل الضغط والثابت 1 عبارة عن مقياس بدائي 2. يتم تمثيل كثير الحدود كمجموع قوى ، على سبيل المثال ، متعدد الحدود من الدرجةن يبدو كالتالي:

Ann + a n-1 x n-1 +… + a 1 x 1 + a 0 x 0 = القلق + a n-1 x n-1 +… + a 1 x + a 0 ، حيث a i = (0، 1 ) لـ i = 1… n ، axi - يشير إلى البت.

درجة كثير الحدود هي طول سجل التحول. كثير الحدود البدائي من الدرجة n هو كثير حدود غير قابل للاختزال وهو مقسوم على x 2n − 1 +1 لكن ليس قاسمه xد +1 لجميع القواسم d على 2ن -واحد. يمكن العثور على النظرية الرياضية المقابلة في.

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

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

(32 ، 7 ، 5 ، 3 ، 2 ، 1 ، 0) تعني أن كثير الحدود التالي هو المقياس البدائي 2: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

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

استمرارًا للمثال ، الكتابة (32 ، 7 ، 5 ، 3 ، 2 ، 1 ، 0) تعني أنه بالنسبة لسجل إزاحة 32 بت معين ، يتم إنشاء بت جديد بواسطة XORing في الثانية والثلاثين ، والسابع ، والخامس ، والثالث ، والثاني ، والبتات الأولى ، سيكون لـ RgCsLOS الناتج أقصى طول ، مع الدوران حتى يتكرر بعد 2 32-1 القيم.

الشكل 4 PrCsLOS 32 بت مع أقصى طول

ضع في اعتبارك رمز البرنامج PgCsLOS ، حيث يتميز تسلسل النقر بكثير الحدود (32 ، 7 ، 5 ، 3 ، 2 ، 1 ، 0). في لغة C ، يبدو الأمر كما يلي:

int LFSR () (

ShiftRegister طويل ثابت بدون توقيع = 1 ؛

/ * الكل ما عدا 0. * /

ShiftRegister = ((((ShiftRegister >> 31)

^ (ShiftRegister >> 6)

^ (ShiftRegister >> 4)

^ (التحول تسجيل >> 2)

^ (التحول تسجيل >> 1)

^ ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ؛

عودة ShiftRegister & 0 × 00000001 ؛)

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

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

إذا كانت p (x) بدائية ، فإن x كذلكن p (1 / x) ، لذا فإن كل عنصر من عناصر الجدول يحدد في الواقع اثنين من كثيرات الحدود البدائية. على سبيل المثال ، إذا كانت (أ ، ب ، 0) بدائية ، فعندئذ تكون كذلك (أ ، أ ، ب ، 0). إذا كانت (أ ، ب ، ج ، د ، 0) بدائية ، إذن كذلك (أ ، أ ، د ، أ ج ، أ ب ، 0). رياضيا:

إذا كانت x بدائيةأ + إكس ب +1 ، إذن فهو بدائي و xأ + س أ-ب + 1 ،

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

إن توليد كثيرات حدود بدائية كثيفة من النوع 2 ليس بالأمر السهل. في الحالة العامة ، لتوليد كثيرات حدود بدائية من الدرجة k ، يحتاج المرء إلى معرفة عوامل العدد 2ك -1.

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

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

1.2. حول تيار الأصفار على أساس RgCsLOS

النهج الأساسي لتصميم مولد تدفق المفاتيح المستند إلى PrCsLOS بسيط. أولاً ، يتم أخذ PrCsLOS واحد أو أكثر ، عادةً بأطوال مختلفة ومتعددة حدود ردود فعل مختلفة. (إذا كانت الأطوال عبارة عن جريمة مشتركة وكانت جميع كثيرات حدود التغذية المرتدة بدائية ، فسيكون للمولد الناتج حدًا أقصى للطول.) المفتاح هو الحالة الأولية لسجلات PrCcLOC. في كل مرة تكون هناك حاجة إلى بت جديد ، قم بتحويل سجلات PrCsLOS قليلاً (تسمى أحيانًا تسجيل الوقت). إن بتة الخرج هي دالة ، ويفضل أن تكون غير خطية ، لبعض بتات سجلات PrCsLOC. تسمى هذه الوظيفة وظيفة الجمع ، ويسمى المولد ككل بالمولد التوافقي. (إذا كانت بتة الإخراج دالة لـ PgCsLOS واحد ، فإن المذبذب يسمى مرشح مذبذب.) تم تطوير الكثير من النظرية الكامنة وراء هذه الأنواع من الأجهزة بواسطة Selmer و Neal Zierler. يمكنك تقديم عدد من المضاعفات. في بعض المولدات ، تُستخدم ترددات مختلفة على مدار الساعة لمختلف PgCsLOS ، وفي بعض الأحيان يعتمد تردد أحد المولدات على خرج آخر. هذه كلها إصدارات إلكترونية لأفكار آلات التشفير التي كانت موجودة قبل الحرب العالمية الثانية والتي تسمى المذبذبات التي يتم التحكم فيها على مدار الساعة (مولدات يتم التحكم فيها على مدار الساعة ). يمكن أن يكون التحكم على مدار الساعة في التغذية الأمامية ، حيث يتحكم إخراج PgSsLOS في سرعة الساعة الخاصة بـ PgSsLOS آخر ، أو الحلقة المغلقة ، حيث يتحكم خرج PgSsLOS في الساعة الخاصة به. في حين أن كل هذه المولدات حساسة ، على الأقل من الناحية النظرية ، للهجمات المتداخلة والارتباطات المحتملة ، إلا أن العديد منها لا يزال آمنًا.

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

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

ينمو هذا الفرع من التشفير بسرعة ويخضع لسيطرة الحكومة اليقظة منوكالة الأمن القومي . يتم تصنيف معظم التطورات - العديد من أنظمة التشفير العسكرية المستخدمة اليوم تعتمد على PrCsLOS. في الواقع ، تحتوي معظم أجهزة كمبيوتر Cray (Cray 1 و Cray X-MP و Cray Y-MP) على تعليمات شيقة جدًا يشار إليها عادةً باسم "عدد السكان". يحسب عدد 1s في السجل ويمكن استخدامه على حد سواء لحساب مسافة هامينج بين كلمتين ثنائيتين وتنفيذ نسخة متجهية من PrCcLOS. تعتبر هذه التعليمات بمثابة التعليمات الأساسية لوكالة الأمن القومي ، وتظهر في جميع عقود أجهزة الكمبيوتر تقريبًا.

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

1.3 على التعقيد الخطي للتسلسل المتولد من الأرقام العشوائية الزائفة PrCsLOS

غالبًا ما يكون تحليل الأصفار الدفق أسهل من تحليل الأصفار. على سبيل المثال ، المعلمة المهمة المستخدمة لتحليل المولدات القائمة على PgCsLOC هي التعقيد الخطي أو الفاصل الزمني الخطي. يتم تعريفه على أنه الطول n لأقصر PrCsLOS الذي يمكنه محاكاة خرج المولد. أي تسلسل تم إنشاؤه بواسطة أوتوماتيكي محدود على حقل محدود له تعقيد خطي محدود. يعد التعقيد الخطي مهمًا لأنه باستخدام خوارزمية بسيطة تسمى خوارزمية Berlekamp-Massey ، يمكن للمرء تحديد PrCcLOC عن طريق فحص 2n بت فقط من تدفق المفاتيح. من خلال إعادة إنشاء PrCsLOS المطلوب ، يمكنك كسر تشفير الدفق.

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

1.4 حول استقلالية الارتباط للتسلسل المتولد للأرقام العشوائية الزائفة PrCsLOS

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

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

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

1.5 حول الطرق الأخرى لفتح التسلسل الذي تم إنشاؤه للأرقام شبه العشوائية PgCsLOS

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

2. وصف تنفيذ برنامج PrCsLOS كمولد تسلسل شبه عشوائي

2.1 مخطط معمم للخوارزمية

2.2 وصف وحدات البرنامج والواجهة

يوضح الشكل 3 أدناه نافذة البرنامج.

واجهة برنامج الشكل

تحتوي القائمة على الوظائف التالية:

• ملف-> حفظ التقرير

تنشئ هذه الوظيفة ملف تقرير ، حيث تتم كتابة الحالة الأولية لـ PrCsLOS وتسلسل النقر وفترة تسلسل البت شبه العشوائي المستلم والتسلسل نفسه وجدول الحالة. إذا تم حفظ الملف بنجاح ، يتم عرض رسالة حول الحفظ الناجح (الشكل 4). امتداد الملف الموصى به للتقرير هو *.رسالة قصيرة.

رسم

• ملف-> خروج

تضمن هذه الوظيفة إغلاق التطبيق.

• تعيين تسلسل الهروب

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

رسم

• قم بتعيين القيمة الأولية

تقرأ هذه الوظيفة القيمة الأولية للسجل الذي أدخله المستخدم من النافذةتعديل 1 ويتحقق من القيمة المدخلة وفقًا للشروط المحددة: السلسلة التي تم إدخالها غير فارغة (الشكل 6) ، السلسلة التي تم إدخالها بطول ثمانية (8 بت = 1 بايت ، الشكل 7) ، السلسلة التي تم إدخالها تحتوي فقط على أصفار و / أو الآحاد (الشكل 8) ، السلسلة التي تم إدخالها ليست صفرية (الشكل 9). وبخلاف ذلك ، تظهر رسائل خطأ ، ويجب على المستخدم تصحيحها والضغط على الزر مرة أخرى. في حالة نجاح الشيك ، ستتم كتابة القيمة الأولية في جدول الحالة في السطر "الأولي" وسيتم إصدار إشعار (الشكل 10).

رسم

رسم

رسم

رسم

رسم

• أداء نوبة السجل

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

• تعليمات-> حول

تعرض هذه الوظيفة وصفًا موجزًا ​​للبرنامج والتعليمات (الشكل 11).

رسم

• تعليمات-> حول المؤلف

تعرض هذه الوظيفة معلومات حول مؤلف البرنامج (الشكل 12).

رسم

2.3 دليل المستخدم

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

استنتاج

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

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

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

فهرس

1. شناير بروس. التشفير التطبيقي. البروتوكولات والخوارزميات والنصوص المصدر بلغة سي. - م: انتصار ، 2002
2. باباش أ. الجوانب المشفرة والنظرية الآلية لأمن المعلومات الحديثة. المجلد 1 - م: إد. مركز EAOI ، 2009. - 414 ص.
3. إس. سيلمر. دراسة: "العودية الخطية في مجال محدود". جامعة بيرغن ، النرويج ، 1966.
4. N. Zierler و J. Brillhart. "On Primitive Trinomials Modulo 2"، Journal of Information and Control، Vol. 13 No. 6 December 1968، pp.541-544.
5. ك. ماير و WL Tuchman. "يمكن كسر الرموز العشوائية الزائفة" ، مجلة التصميم الإلكتروني ، لا. 23 نوفمبر 1972.
6. جيه إل ماسي. "تعميم سجلات الورديات وفك شفرة Bose-Chowdhury-Hokvingham Code" ،معاملات IEEE على نظرية المعلومات ، v. IT-15 ، ن . 1 ، يناير 1969 ، ص 122-127.
7. S.U. غولومب. تسلسلات سجل التحول ، سان فرانسيسكو ، اليوم الذهبي ، 1967 (أعيد طبعه بواسطة مطبعة Aigean Park ، 1982).

المرفق ألف

جدول لبعض كثيرات الحدود البدائية المقياس 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

مدخلات الحالة الأولية (IS)

التحقق من صحة الإدخال

إصدار رسالة خطأ

ضبط تسلسل الحنفية

تسجيل IP في جدول الحالة

سجل أنا سجل الحالة -th وبت الإخراج في جدول الحالة

IS == الحالة الحالية

نتائج الحفظ

إخراج تسلسل شبه عشوائي

مخرج

إطلاق

نعم

نعم

لا

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

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

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

في هذه الحالة ، عادةً ما يتم استدعاء تلك البتات التي تعد متغيرات لوظيفة التغذية الراجعة الانحناءات.

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

خلال كل دقيقة على مدار الساعة ، يتم إجراء العمليات التالية:

سجل تحويل الملاحظات الخطية

وبالتالي ، فإن العملية المنطقية XOR (حصرية OR) تؤخذ كوظيفة ردود فعل ، أي:

خواص كثيرات الحدود البدائية

الخصائص

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

التعقيد الخطي

يعد التعقيد الخطي للتسلسل الثنائي أحد أهم خصائص تشغيل LFSR. دعونا نقدم الترميز التالي:

تعريف

التعقيد الخطي لتسلسل ثنائي لانهائييسمى الرقم ، والذي يتم تعريفه على النحو التالي:

التعقيد الخطي لتسلسل ثنائي محدوديسمى الرقم ، والذي يساوي طول أقصر LFSR ، والذي يولد تسلسلاً يحتوي على المصطلحات الأولى.

خصائص التعقيد الخطي

اسمحوا و أن تكون متواليات ثنائية. ثم:

استقلالية الارتباط

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

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

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

مثال

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

رقم الخطوة	ولاية	بت ولدت
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

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

خوارزميات لتوليد كثيرات الحدود البدائية

طاولات جاهزة

يعد حساب بدائية كثير الحدود مشكلة رياضية معقدة إلى حد ما. لذلك ، هناك جداول جاهزة تسرد عدد تسلسلات النقر التي توفر أقصى فترة للمولد. على سبيل المثال ، بالنسبة لسجل إزاحة 32 بت ، هناك تسلسل. هذا يعني أنه لإنشاء بت جديد ، من الضروري جمع البتات 31 و 30 و 29 و 27 و 25 و 0 باستخدام وظيفة XOR. رمز LFSR في لغة C كما يلي:

Int LFSR (باطل) (ثابت طويل بدون إشارة S = 1 ؛ S = (((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S) & 1)<< 31 ) | (S>> 1) ؛ عودة S & 1 ؛ )

تطبيقات البرامج لمولدات RSLOS بطيئة جدًا وتعمل بشكل أسرع إذا تمت كتابتها في المجمّع بدلاً من C. أحد الحلول هو استخدام 16 RLLS بالتوازي (أو 32 ، اعتمادًا على طول الكلمة في بنية جهاز كمبيوتر معين). في مثل هذا المخطط ، يتم استخدام مصفوفة من الكلمات ، حجمها يساوي طول LFSR ، وكل بت من كلمة المصفوفة تشير إلى LFSR الخاص بها. شريطة استخدام نفس أرقام تسلسل النقر ، يمكن أن يؤدي ذلك إلى زيادة ملحوظة في الأداء. [بحاجة إلى رمز عينة] (انظر: bitslice).

تكوين جالوا

تكوين Galois لسجل تحول التغذية المرتدة الخطية

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

Int LFSR (باطل) (ثابت طويل بدون إشارة Q = 1 ؛ Q = (Q >> 1) ^ (Q & 1؟ 0x80000057: 0) ؛ إرجاع Q & 1 ؛)

الفائدة هي أن جميع XORs يتم إجراؤها في عملية واحدة.

• يمكن إثبات أن تكوين فيبوناتشي المعطى أولاً وتكوين جالوا المعطى هنا يعطيان نفس التسلسلات (بطول 2 32 −1) ، لكنهما ينتقلان في الطور من بعضهما البعض
• حلقة من عدد ثابت من المكالمات لوظيفة LFSR في تكوين Galois هي أسرع مرتين تقريبًا من تكوين Fibonacci (مترجم MS VS 2010 على Intel Core i5)
• لاحظ أنه في تكوين Galois ، يتم عكس ترتيب البتات في كلمة التغذية المرتدة مقارنةً بتكوين فيبوناتشي

أمثلة المولدات

مولدات كهربائية

مولد التيار المتردد Stop-and-Go

يستخدم هذا المذبذب خرج LFSR واحد للتحكم في تردد ساعة LFSR آخر. يتم التحكم في خرج الساعة لـ RSLOS-2 عن طريق إخراج RSLOS-1 ، بحيث يمكن لـ RSLOS-2 تغيير حالتها في الوقت t فقط إذا كان إخراج RSDOS-1 في الوقت t-1 يساوي واحدًا. لكن هذا المخطط لم يقاوم فتح الارتباط.

لذلك ، تم اقتراح مولد محسّن يعتمد على نفس الفكرة. يطلق عليه مولد التوقف والتشغيل المتشابك. يستخدم ثلاثة LFSRs بأطوال مختلفة. يتم تسجيل LFSR-2 عندما يكون إخراج LFSR-1 مساويًا لواحد ، و LFSR-3 ، عندما يكون ناتج LFSR-1 مساويًا للصفر. ناتج المولد هو مجموع modulo 2 لـ RSLOS-2 و RSLOS-3. هذا المولد له فترة كبيرة وتعقيد خطي كبير. أظهر مؤلفوها أيضًا طريقة لفتح الارتباط لـ RLOS-1 ، لكن هذا لا يضعف المولد بشكل كبير.

شلال جولمان

شلال جولمان

Gollmann Cascade هو نسخة محسنة من مولد التوقف. وهو يتألف من سلسلة من سجلات LFSR ، يتم التحكم في توقيت كل منها بواسطة LFSR السابق. إذا كان خرج LFSR-1 في الوقت t هو 1 ، فسيتم تسجيل LFSR-2. إذا كان ناتج LFSR-2 في الوقت t هو 1 ، فسيتم تسجيل LFSR-3 ، وهكذا. خرج LFSR الأخير هو خرج المولد. إذا كان طول جميع LFSRs هو نفسه ويساوي n ، فإن التعقيد الخطي لنظام k LFSR هو.

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

مولد العتبة

مولد العتبة

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

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

بالنسبة لسجلات الورديات الثلاثة ، يمكن تمثيل المولد على النحو التالي:

هذا المولد مشابه لمولد Geff ، فيما عدا أن مولد العتبة به تعقيد خطي أكثر. تعقيدها الخطي هو:

حيث ، ، هي أطوال سجلات التحول الأول والثاني والثالث.

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

أنواع أخرى

ترقق الذات

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

مذبذب متعدد مع المنتج الداخلي

يستخدم هذا المولد سجلي تحول مع ردود فعل خطية مع ترددات مختلفة على مدار الساعة: LFSR-1 و LFSR-2. تردد ساعة RLOS-2 أعلى بمقدار d مرة من تردد RLLS-1. يتم دمج البتات الفردية لهذه السجلات مع عملية AND. ثم يتم XORed نواتج العملية AND. تسلسل الإخراج مأخوذ من كتلة XOR هذه. مرة أخرى ، هذا المولد ليس مثاليًا (لم ينجو من فتح الاتساق الخطي. إذا - طول LFSR-1 ، - طول LFSR-2 ، و d هي نسبة ترددات الساعة ، فإن الحالة الداخلية لـ يمكن الحصول على المولد من تسلسل الإخراج للطول) ، ولكن لديه تعقيد خطي عالي وأداء إحصائي ممتاز.

سجل تحويل الملاحظاتيتكون من جزأين: سجل التحول و وظائف التغذية الراجعة.

الشكل 19. ردود الفعل سجل التحول.

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

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

الشكل 20. LFOS لتكوين فيبوناتشي.

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

الشكل 21. RLOS لتكوين Galois.

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

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

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

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

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

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

أرز. 1.2.1.

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

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

أرز. 1.2.2.

على التين. يُظهر الإصدار 1.2.3 LFSR 4 بت مع نقرة على البتتين الأولى والرابعة. إذا تمت تهيئته بالقيمة 1111 ، فقبل تكرار السجل ، ستأخذ الحالات الداخلية التالية:

أرز. 1.2.3. 4

سيكون تسلسل الإخراج عبارة عن سلسلة من البتات الأقل أهمية:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

قد يكون n-bit LFSR في إحدى الحالات الداخلية 2n-1. وهذا يعني ، من الناحية النظرية ، أن مثل هذا السجل يمكن أن يولد تسلسلًا شبه عشوائي مع فترة 2n-1 بت. (عدد الحالات الداخلية والفترة هي 2n-1 ، لأن ملء LFSR بالأصفار سيؤدي إلى إخراج سجل الإزاحة تسلسلًا لانهائيًا من الأصفار ، وهو أمر عديم الفائدة تمامًا.) فقط مع تسلسلات ضغط معينة ، سينتقل LFSR عبر جميع الحالات الداخلية 2n-1 ، مثل LFSRs هي LFSR مع فترة قصوى. النتيجة الناتجة تسمى تسلسل M.

للحصول على فترة زمنية قصوى لـ LFSR معين ، يجب أن يكون كثير الحدود المكون من تسلسل الضغط والثابت 1 هو النمط البدائي 2. درجة كثير الحدود هي طول سجل التحول. كثير الحدود البدائي من الدرجة n هو كثير حدود غير قابل للاختزال وهو قاسم لكنه ليس مقسومًا على xd + 1 لجميع d التي هي قواسم على 2n-1.

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

بعض ، ولكن ليس كل ، كثيرات الحدود بدرجات مختلفة هي نمط بدائي 2. على سبيل المثال ، الترميز (32 ، 7 ، 5 ، 3 ، 2 ، 1 ، 0) يعني أن كثير الحدود التالي هو المقياس البدائي 2:

x32 + x7 + x5 + x3 + x2 + x + 1

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

استمرارًا للمثال ، الكتابة (32 ، 7 ، 5 ، 3 ، 2 ، 1 ، 0) تعني أنه بالنسبة لسجل إزاحة 32 بت معين ، يتم إنشاء بت جديد بواسطة XORing في الثانية والثلاثين ، والسابع ، والخامس ، والثالث ، والثاني ، والبتات الأولى ، سيكون LFSR الناتج أقصى طول ، ويتم التدوير عبر قيم 232-1 قبل التكرار.