Document

Design and analysis of recursive binary sequences for the use of stream cipher crypto-system

Publisher
Sultan Qaboos University
Gregorian
2001
Language
English
English abstract
At one end, tremendous advances in information technology faces the challenges of ultra-high speed data communication. On the other hand, the infrastructure of information society necessitates and demands for more and more secure communication links. Thus, mutual authentication, integrity and confidentiality have become an essential part of bulk of information. In this scenario, for high-speed networks, stream ciphering mechanisms have become an appropriate and essential technology of the age. Most often Linear Feedback Shift Registers (LFSRs) are used in hardware designs of the stream ciphers. This is the reason that most practical stream ciphers center on LFSRs. However, because of well-set mathematical properties of the sequences generated by LFSRs, the analyzing of stream ciphers is often easier than of analyzing block ciphers. But by knowing the 2n bits of the sequence generated by an n-bit LFSR, the structure of the LFSR can be computed. Thus, because of these, the sequence generated by LFSRs cannot be simply used for stream ciphering. . Further, a stream ciphering sequence is subjected to meet the standard cryptographic criteria such as a large period, high linear complexity, and good statistical properties. The need to generate more complex sequence led to the idea of using multiple LFSRs and some how mixing their generated sequences in some manner. In this work we use three different structures for mixing those multiple LFSRs. In all the type of the structures of the combiners, we use to combine the sequences generated by four input LFSRs of small lengths. However, different filter circuits control these structures. Two of the filter circuits use only an LFSR while another is based on a set of the two LFSRs of same lengths. The period of the resultant generated sequences can be controlled by least common multiples of periods of each LFSRs, used either in combiner or in the filter circuits. In order to evaluate the strength of stream ciphering we used several types of tests. We used all such test namely; Golomb's postulates, correlation properties, frequency/equi-distribution, serial, run length, and Poker test to validate the proposed designs. Also, a large number of sequences are generated with the variations of the parameters like the lengths, initial conditions and characteristic polynomials of the LFSRs used in the combiner as well as filter circuits. On the basis of the results of the analysis it is found that the Third structure, which uses a set of two LFSRs, of same lengths in the filter circuit, is the optimum one. Most the sequences generated by the Third structure passes all the desired tests for strong stream ciphering satisfactorily.
Arabic abstract
إن التطور الهائل في تكنولوجيا المعلومات يواجه من أحد الجوانب تحدي اتصال البيانات ذات السرعة الفائقة جدا. كما يواجه من جانب آخر احتياجات عالم المعلومات الأساسي لاتصالات آمنة وعلى درجة عالية من الوثوقية. من العوامل الأساسية في تكنولوجيا المعلومات. وفي هذا المضمار يصبح نظام التشفير الانسيابي (stream cipher) هو النظام المناسب والضروري في الوقت الحالي. يعتبر المسجل ذو الازاحه الخطية المغذی عکسبا (LFSR) ، المستخدم في تصميم دوائر الحاسوب، أساسا لدوائر التشفير الانسيابي. ويفضل هذا النوع من التشفير على النوع الثاني وهو التشفير الخاص بالمحاميع ( block ciphering) لكون تحليل المتسلسلات الناتجة من المسجلات ذات الازاحه والمغذاه عكسيا له خصائص رياضيه واضحه. ولكن باستخدام مسجل ازاحه مغذی عكسيا حجمه (n) رقما ثنائيا، ومعرفة متسلسله طولها (23) من المتسلساء الناتجة من هذا المسجل، يمكننا معرفة التركيب الأساسي لهذه المسجلات مما يجعل من الصعوبه استخدام هذه المتسلسلات الناتجه من المسجلات في التشفير الانسيابي. هذا بالاضافة إلى أن التشفير الانسيابي يجب أن يراعي المتطلبات القياسية لعلم التشفير من الدورة الطويلة والتعقيد الخطى جدا واخواص الاحصائية الجيدة. إن الحاجة لتوليد متسلسلات اكثر تعقيدا دعتنا في هذا العمل لاستخدام عدة مسجلات والقيام بمزج المتسلسلات الناتجه عن كل منهم عن طريق ثلاث دوائر ربط ( combiner) مختلفة. في كل أنواع دوائر الربط المستخدمه تم ربط المتسلسلات الناتجه عن أربع مجاميع للمسجلات ذات الحجم الصغير. وتختلف دوائر الربط الثلاث المستخدمه باختلاف دوائر الترشيح المسيطرة على عملية مزج المتسلسلات. اثنان من هذه الدوائر تستخدم مسجل واحد، بينما تعتمد الثالثه على مسجلين لهما نفس الطول. ويمكن تحديد دورة المتسلسله الناتجه عن طريق العامل المشترك الأصغر للدورات الناتجه عن كل مسجل مستخدم كإدخال إلى دوائر الربط أو في دوائر الترشيح. يوجد عدة طرق فحص لتخمين جودة التشفير الانسيابي. ثم في هذا العمل استخدام معظمها مثل: مسلمان جولومب (Golomb) خصائص العلاقة المتبادلة، التوزيع التساوي للتردد، المتوالي، وفحص بو کر. كما تم استخدام عدد كبير من المتسلسلات مولدة بتغيير بعض العناصر مثل الطول، الحاله الابتدائية، والخصائص المتعددة الحدود للمسجلات المستخدمه في دوائر الربط والترشيح. وبمقارنة النتائج التي تم الحصول عليها في هذا البحث، تم استنتاج أن النوع الثالث من دوائر الترشيح الذب يستخدم مسجلين هما نفس الطول ، هو النوع الأمثل. معظم المتسلسلات الناتجه عن استخدام هذا المرشح نجحت باجتياز كل طرق الفحص المستخدمه وبنتائج مقنعه تماما للتشفتر الانسيابي الناتج عنها.
Category
Theses and Dissertations