معيار التعمية المتقدم

معيار التعمية المُتقدِّم
تمثيل لدالة الدورة في معيار التعمية المتقدم
معلومات عامة
المطورون	جون ديمان وفنسنت ريمين
تاريخ النشر	1998
اشتقت من	المعمي المربع
اشتق منها	أنوبيس ، Grand Cru، Kalyna
الشهادة	اختيار خوارزمية معيار التعمية المتقدم ‏ winner, لجان أبحاث التعمية وتقييمها ‏, NESSIE، NSA
معلومات التعمية
مقاس المفتاح ‏	128 أو 192 أو 256 بتاً
مقاس الفدرة ‏	128 بتاً
البنية	شبكة إعاضة وتباديل
عدد الدورات	10 أو 12 أو 14 حسب مقاس المفتاح.

معيار التعمية المُتقدِّم (بالإنجليزية: Advanced Encryption Standard)‏ اختصاراً AES، ويُعرف أيضاً باسمه الأصيل رِنْدِل (بالهولندية: Rijndael) وتُقرأ ‎ˈrɛindaːl‏، هو محدِّد تعمية اعتمده المعهد الوطني للمعايير والتقانة في الولايات المتحدة سنة 2001م.

معيار التعمية المتقدِّم هو تنويعة لمعمي فِدر رِنْدِل. طوره عالما التعمية البلجيكيان جون ديمان وفنسنت ريمين ليكون مقترحاً خلال عملية اختيار خوارزمية معيار التعمية المتقدم التي أدارها المعهد الوطني للمعايير والتقانة. معميات رندل عائلة من معميات الفدر تدعم مقاسات مختلفة للفدر والمفاتيح. اختار المعهد الوطني للمعايير ثلاثة معميات من هذه العائلة تتشابه بمقاس الفدرة (128 بت)، ولكنها تختلف بمقاس المفتاح: 128 و192 و256 بتاً على الترتيب. تستعمل هذه المُعمِّيات تعمية متناظرة وحيدة المفتاح، أي أن المفتاح نفسه يُستخدم لتعمية البيانات ولفك تعميتها.

أعلن المعهد الوطني للمعايير والتقانة في الولايات المتحدة عن هذا المعيار بوصفه معياراً اتحادياً لمعالجة المعلومات في 26 نوفمبر 2001م، وحمَّله بالاسم الرمزي FIPS 197. وتلا ذلك عملية تعيير استمرت 5 سنوات تنافس فيها 15 اقتراحاً مختلفاً، انتهت باختيار معمي رِندل ليكون أساساً لهذا المعيار. تبنَّت الحكومة الاتحادية للولايات المتحدة معيار التعمية المُتقدِّم في 26 مايو 2002م، ليحل محل معيار تعمية البيانات الذي طُوِّر سنة 1977. وهو المعمي الوحيد المتاح للعموم من المعميات التي أجازتها وكالة الأمن القومي الأمريكية للتعامل مع المعلومات بالغة السرية.

معايير رسمية

عرِّف معيار التعمية المُتقدِّم في:

• المعيار الاتحادي لمعالجة المعلومات ذو المُعرِّف FIPS 197، المُسمَّى: معيار التعمية المتقدم.
• معيار المنظمة الدولية للمعايير واللجنة الكهرتقنية الدولية ذو المُعرِّف 18033-3، المُسمَّى معميات الفدر.

الوصف

بُني معيار التعمية المتقدم على بدئية تعمية تُسمَّى شبكة الإعاضة والتباديل . لا يستعمل معيار التعمية المتقدم شبكة فِستل ، كما هو حال سابقه: معيار تعمية البيانات. معيار التعمية المُتقدِّم هو تنويعة من معميات رنِدل، مقاس الفِدرة التي يعميها ثابت: 128 بتاً، أما مقاس المفتاح فقد يكون 128 أو 192 أو 256 بتاً.

يعالج المعيار مصفوفة مربعة، تُسمَّى مصفوفة الحالة، فيها 16 عنصراً (4x4)، طول كل منها 16 بايتاً، يُرمز لها على الترتيب: b₀, b₁, ..., b₁₅. تُرتَّب عناصر المصفوفة حسب الأعمدة، أي يكون العنصر الواقع في أعلى العمود الأول هو صاحب أصغر الفهارس (0)، ثم يليه العنصر الذي يقع تحته مباشرة في العمود نفسه، وهكذا حتى نهاية عناصر العمود، ثم الانتقال للعمود التالي وصولاً للعنصر الواقع في أسفل العمود الأخير الذي يكون صاحب الفهر الأكبر (15)، وتكون المصفوفة على الشكل التالي:

${\begin{bmatrix}b_{0}&b_{4}&b_{8}&b_{12}\\b_{1}&b_{5}&b_{9}&b_{13}\\b_{2}&b_{6}&b_{10}&b_{14}\\b_{3}&b_{7}&b_{11}&b_{15}\end{bmatrix}}$

يحدد مقاس المفتاح في معمي معيار التعمية المتقدِّم عدد الدورات اللازمة لتحويل الدخل، الذي يُسمَّى نصاً واضحاً إلى الشكل النهائي للخرج، المُسمَّى نصاً معمى . يتحدد عدد الدورات كما يأتي:

• 10 دورات لو كان مقاس المفتاح 128 بتاً.
• 12 دورات لو كان مقاس المفتاح 192 بتاً.
• 14 دورات لو كان مقاس المفتاح 256 بتاً.

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

وصف عام لمراحل العمل

1. تمديد المفتاح: أي اشتقاق مفالتيح الجولات من مفتاح التعمية اعتماداً على مُجدوِل مفاتيح . يحتاج المعيار مفتاحاً فريداً بطول 128 بتاً لكل دورة، ومفتاح إضافياً آخر بالطول نفسه.
2. إضافة مفتاح الدورة الأولى:
   1. إضافة مفتاح الدورة تطبق عملية الفصل المنطقي الإقصائي (XOR)، على مستوى البت، بين كل بايت من المصفوفة والبايت المقابل له من مفتاح الدورة.
3. 9 أو 11 أو 13 دورة يُطبَّق فيها ما يلي:
   1. إعاضة البايتات: خطوة إعاضة غير خطية يُستبدَل فيها بايتٌ جديد بكل بايتٍ موجود آخر حسب جداول معدة مسبقاً .
   2. الإزاحة في الصفوف: خطوة لتبديل مواقع العناصر في الصفوف الثلاثة الأخيرة من مصفوفة الحالة بإزاحتها عدداً محدداً من المراتب.
   3. الخلط في الأعمدة: عملية خلط خطي لعناصر أعمدة مصفوفة الحالة تجري على البايتات الأربعة لكل عمود.
   4. إضافة مفتاح الدورة
4. دورة أخيرة (ليصبح مجمل عدد الدورات 10 أو 12 أو 14):
   1. إعاضة البايتات
   2. الخلط في الأعمدة
   3. إضافة مفتاح الدورة

وصف مفصل لمراحل العمل

خطوة إعاضة البايتات

يُستبدَل بكل بايتٍ في خطوة إعاضة البايتات بايتٌ آخر مغاير له بالقيمة.

يُستبدَل في هذه الخطوة بكل بايت في مصفوفة الحالة ($a_{i,j}$) ببايت آخر $b_{i,j}$ حسب العلاقة:

$b_{i,j}=S(a_{i,j})$

وفيها $S$ هو صندوق إعاضة ثماني البتات. يكون الدخل هو النص الواضح ممثلاً بمصفوفة الحالة قبل الدورة الأولى.

تؤدي هذه الخطوة وظيقة اللاخطية في المُعمِّي، وتُشتق صناديق الإعاضة المستعملة من دالة مقلوب محدودة الحقل (2⁸)، مضيفة بذلك الخواص اللاخطية للمُعَمِّي. تُبنى صناديق الإعاضة بجمع دالة عكسية مع تحويل تآلفي غير عكوس لصد الهجمات التي تعتمد على تحليل الخواص الجبرية.

يُصمم صندوق الإعاضة ليبدِّل عناصر مصفوفة الحالة تبديلاً فعلياً ، فلا يحتفظ أي عنصر بقيمته الأصيلة، وذلك لتجنب النقاط الثابتة التي تُضعف سرية التعمية، أي يلزم أن يتحقق دائماً:

$S(a_{i,j})\neq a_{i,j}$

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

$S(a_{i,j})\oplus a_{i,j}\neq {\text{FF}}_{16}$

في عملية فك التعمية، يلزم تطبيق خطوة الإعاضة العكسية، وهي تشمل عكس التحويل التآلفي أولاً، ثُمَّ إيجاد معكوس دالة المقلوب بعد ذلك.

خطوة الإزاحة في الصفوف

تكون إزاحة العناصر نحو اليسار دوماً، تعني صفة الحلقية افتراض أن العمود الرابع يقع إلى يسار العمود الأول، وكأن أعمدة المصفوفة مرتبة في حلقة مغلقة.

تُطبَّق خطوة الإزاحة في صفوف مصفوفة الحالة، وفيها تزاح العناصر حلقياً في كل صف من الصفوف إزاحةً معينة. تبقى عناصر الصف الأول من غير تغيير في معيار التعمية المتقدِّم. أما عناصر الصف الثاني فتزاح يساراً مرتبةً وحيدة، في حين تزاح عناصر الصف الثالث يساراً مرتبتين، وعناصر الصف الرابع يساراً ثلاث مراتبَ. تهدف هذه العملية إلى جعل كل عمود في المصفوفة الناتجة عن الإزاحة مكوناً من عناصر من كل صفوف المصفوفة قبل الإزاحة (عنصر واحد من كل صف)، ما يؤدي إلى تجنُّب تعمية الأعمدة قبل الإزاحة تعمية مستقلة، وتجنب إنتاج أربعة مُعَمِّيات مستقلة: مُعَمِّ لكل عمود.

خطوة الخلط في الأعمدة

تشمل عملية الخلط في الأعمدة جداء مصفوفات مع مصفوفة ثابتة القيمة..

تجري عملية الخلط على العناصر الأربعة في كل عمود من مصفوفة الحالة باستعمال تحويل خطي غير عكوس. دخل هذه العملية هو أربعة بايتات وخرجها هو أربعة بايتات كذلك، وفيها يؤثر كل بايت في الدخل على بايتات الخرج كلها. الغرض من هذه الخطوة هو إضافة عنصر الإرباك إلى المُعَمِّي.

يشمل التحويل الخطي استعمال مصفوفة ثابتة القيم تُضرَب بعناصر العمود ذي الفهرس j من مصفوفة الحالة كما يأتي:

${\begin{bmatrix}b_{0,j}\\b_{1,j}\\b_{2,j}\\b_{3,j}\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}{\begin{bmatrix}a_{0,j}\\a_{1,j}\\a_{2,j}\\a_{3,j}\end{bmatrix}}\qquad 0\leq j\leq 3$

يشمل جُداء المصفوات عمليات ضرب وجمع. في الضرب، يعامل كل بايت، مكون من 8 بتات، معاملة كثير حدود أكبر مرتبة فيه $x^{7}$، أما الجمع فينجز باستعمال عملية الفصل الحصرية (XOR).

خطوة إضافة مفتاح الدورة

إضافة مفتاح الدورة، يعني الرمز (⊕) عملية الفصل المنطقي الإقصائي (XOR).

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

تستعمل عملية الفصل المنطقي الإقصائي (XOR) ويكون مدخلاها: عنصر من مصفوفة الحالة، والعنصر المقابل له من المفتاح.

استمثال المُعَمِّي

يمكن تسريع التنفيذ في المُعمِّيات المُشغَّلة على أنظمة تدعم كلمات بطول 32 بتاً أو أكبر، بدمج خطوتي إعاضة البايتات والإزاحة في الصفوف مع خطوة الخلط في الأعمدة. ينتج عن الدمج خطوة تشمل تتابعا من عمليات البحث في 4 جداول ثابتة القيم في كل منها 256 مدخلاً بمقاس 32 بتًا، تَشغَل كلها معاً 4096 بايتًا. يمكن في هذه الحالة إنجاز دورة واحدة بعمل 16 عملية بحث في الجداول متبوعة باثني عشر عملية فصل منطقي حصري (مقاسات المدخلين والمخرج 32 بتاً). يلي ذلك 4 عمليات فصل منطقي حصري (مقاسات المدخلين والمخرج 32 بتاً) لإضافة مفتاح الدورة. يمكن أيضاً إنجاز البحث في الجدول باعتماد جدول واحد ثابت القيم فيه 256 مدخلاً بمقاس 32 بتًا يشغل 1024 بايتاً، يُتبع بعمليات تدوير حلقية.

يمكن أيضاً دمج خطوات إعاضة البايتات والإزاحة في الصفوف والخلط في الأعمدة معاً باعتماد منهج يعالج البايتات.

الأمن

راجعت وكالة الأمن القومي الأمريكية الخوازرميات التي رُشحت في أثناء تطوير معيار التعمية المتقدم، وصرَّحت بأن الخوارزميات كلها آمنة بما يكفي للتعامل مع بيانات الحكومة الأمريكية غير السرية. أعلمن الحكومة في شهر يونيو 2003م بإمكانية استعمال معيار التعمية المُتقدِّمة لحماية المعلومات السرية:

يكفي تصميم خوارزمية معيار التعمية المتقدِّم ومقاس المفاتيح: 128 و192 و256 بتاً فيها لحماية المعلومات المُصنَّفة سرية. أما المعلومات بالغة السرية فيلزم استعمال مفاتيح مقاساتها 192 و256 بتاً.

يُنفِّذ معيار التعمية المُتقدِّم 10 دورات لو كان مقاس مفتاح الدورة 128 بتاً، و12 دورة لو كان المقاس 192 بتاً، و14 دورة لو كان المقاس 256 بتاً. كانت أفضل الهجمات المعروفة في سنة 2006 قادرة على استخراج مُعَمَّى المعيار لو كان عدد الدورات 7 بمقاس مفتاح 128 بتاً، و8 بمقاس 192 بتاً، و9 بمقاس 256 بتاً.

انظر أيضًا

• معيار تعمية البيانات (DES)
• نظرية التعقيد الحسابي
• المعهد الوطني للمعايير والتقانة (NIST)
• دالة وحيدة الاتجاه