Fulltext

A Comparison between Single and Multi- Crossover Pointsto Break Hill Cipher Using Heuristic Search: MA & GA

مقارنة بين نقاط التزاوج المفردة والمتعددة لتحليل شفرة Hill باستخدام خوارزميات البحث العشوائي: الميميائية والجينية

Dalal A. Hammood

Engineering and Technology Journal مجلة الهندسة والتكنولوجيا
ISSN: 16816900 24120758 Year: 2013 Volume: 31 Issue: 4 Part (B) Scientific Pages: 490-504
Publisher: University of Technology الجامعة التكنولوجية

Abstract

Hill cipher is a classical cipher which is based on linear algebra. In this method, matrices and matrix multiplication have been used to combine the plaintext.Heuristic search is a search techniques. The methods of HS are: (GA, SE, EP, MA, TS). Genetic algorithms are one of Heuristic search, it is search techniques which is used natural selection. GAs select optimal solution through three operations, they are : selection, crossover and mutation. The parameters are kept in memory and the best values of fitness have been selected to represent next generation.Memetic Algorithm is one of Heuristic search , a memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the convergence, to reach the best solution. This paper focuses on using MA and GA to find optimal solution to cryptanalyse Hill cipher. Then comparing two methods of crossover to see which one has best solution, and comparing between GA and MA to see which one has best solution.MATLAB is used as M-FILE.Theresults ofcryptanalysis cleared as following:- 1- Without genetic algorithms: The number of correct letters for the key was 1 out of 9. 2- Using genetic algorithms: two methods are used, and they have been compared of crossover, they are single and multi- crossover points randomly. After (250) generation, the number of correct letters was 4 out of 9 when single crossover point is used. The number of correct letters was 8 out of 9 when multi crossover point are used. So multi crossover point have best solution. Genetic algorithms are applied successfully.3- Using Memetic Algorithms. After (100) generation, the number of correct letters was 8 out of 9. So MA is better than Genetic algorithms.4- the number of correct letter was 9 out of 9 when the MA is used.

شفرة هيل هي شفرة تقليدية (كلاسيكية) حيث تستند على الجبر الخطي. في هذه الطريقة، تم استخدام ضرب المصفوفات لتكوين النص المشفر.البحث الاستدلائي هي طريقة بحث. طرق البحث الاستلائي هي : (الخوارزميات الجينية، خوارزميات الانصهار والتبريد، البرمجة التطويرية، الخوارزمية الميميائية، بحث التابو). الخوارزميات الجينية هي احدى طرق البحث الاستدلائي، هي تقنيات بحث حيث تستخدم الانتقاء الطبيعي. الخوارزميات الجينية تختار الحل الامثل من خلال ثلاث عمليات : الانتقاء (الاختيار) ، التزاوج والطفرة. الباراميترات تحفظ في الذاكرة ويتم اختيار افضل قيمة للفتنس لتمثل بالجيل القادم.خوارزمية MA هي طرق البحث الاستدلائي، وهي امتداد للخوارزمية الجينية التقليدية. ويستخدم تقنية البحث المحلي إلتى يقلل من احتمالات التقارب للوصول الى الحل الامثل.يركز هذا البحث على استخدام الخوارزميات الجينية وخوارزمية memetic لايجاد الحل الامثل لتحليل شفرة Hill. ثم مقارنة طريقتين لعملية التزاوج لرؤية ايهما يمتلك الحل الافضل. ومقارنة بين خوارزمية GA وMA وملاحظة اي منهما لها افضل الحلول.استخدم الماتلاب كـ M-File، اوضحت النتائج مايلي:1-بدون استخدام الخوارزميات الجينية: عدد الحروف الصحيحة للمفتاح كان 1 من اصل 9 حروف.2-باستخدام الخوارزميات الجينية: استخدمت طريقتين وقورنت نقاط التزاوج، وهي النقطة المفردة للتزاوج والنقاط المتعددة (نقطتي تزاوج) عشوائياً. بعد 250 جيل عدد الحروف الصحيحة كان 4 من اصل 9 عند استخدام النقطة المفردة للتزاوج. عدد الحروف الصحيحة كان 8 من اصل 9 عندما استخدم النقاط المتعددة. لذا الحل الافضل عند استخدام التزاوج المتعدد. طبقت الخوارزميات الجينية بنجاح.3-باستخدام Memetic Algorithm : استخدمت طريقة النقاط المزدوجة، بعد 100 جيل عدد الحروف الصحيحة كان 8 من اصل 9. وقورنت مع الخوارزمية الجينية حيث اوضحت النتائج ان الخوارزمية MA اعطت نفس النتائج لعدد من الاجيال 100 جيل بينما اعطت الخوارزمية الجينية بعد 250 جيل.4-كان عدد الحروف الصحيحة 9 من اصل 9 حروف بعد 150 جيل عندما استخدمت خوارزمية MA.

Keywords

Hill cipher --- Memetic Algorithm --- Genetic Algorithms --- Cryptanalyse --- Key Search --- single & multi crossover point --- شفرة الهيل، الخوارزمية الميميائية، الخوارزمية الجينية، تحليل الشفرة، المفتاح، نقاط التزاوج المفردة والمزدوجة