إيه إي إس (تعمية)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في التعمية، AES: Advanced Encryption Standard او معيار التشفير المُطَور , هو طريقة تشفير رسمية تبنتها NIST ( المركز القومي للمعايير والتكنولوجيا وهو فرع في حكومة الولايات المتحدة ) . هذه الخوارزمية لاقت تقبلا واسعا في العالم إذ أنها تُعتبر طريقة آمنة للتشفير وذلك بسبب طول مفتاح التشفير . هذه الخوارزمية هي تطوير لافكار ظهرت في DES .

تاريخ[عدل]

في عام 1997 بدأت NIST بالبحث عن بديل ل-DES وذلك لان DES كان يُعتبر بشكل واسع آنذاك انه غير آمن وذلك بسبب تطوير وسائل متطورة لكسر هذه الوسيلة, وقد كانت التسعينات نهاية DES حيث انه Wiener في بداية التسعينيات اعلن عن آلة بقيمة 1000000 دولار لكسر DES في 3.5 ساعات فقط ! كل هذا ساهم بالاساس في الاعلان عن اصدار معيار تشفير اقوى , وقد كان احدى اهداف هذا البحث هو الاعلان عن بديل يُستخدم بشكل عام ولا يقتصر على الجيش , ولاجل هذا دعت كل المتخصصين في علم التعمية لتقديم اقتراحاتهم وكانت الشروط كالتالي :

  1. يجب ان يتم تعريف AES علانية
  2. يجب ان يكون AES خوارزمية تشفير كُتل متماثل(symmetric block cipher) .
  3. يجب تصميم AES بحيث ان طول المفتاح يمكن ان نطوله حسب الحاجة .
  4. يمكن برمجة AES بواسطة البرمجيات والعتاد الصلب للحاسوب (software and hardware)
  5. يجب على ِAES ان يكون مُتاح مجانا او مُتاح بتناسق مع سياسة ANSI لبراءة الاختراعات
  6. الخوارزميات التي تتماشى مع النقاط السابقة سيتم اختبارها بناء على المعايير الآتية :
    1. الأمان: أي مدى مقاومته للأساليب المعروفة لكسر خوارزميات التشفير.
    2. جودة الحساب: أي قياس الزمن اللازم للتشفير وكلما كان اقل كانت الخوارزمية اكثر جودة .
    3. مُتطلبات الذاكرة: أي سعة الذاكرة الالكترونية المستخدمة في تنفيذ الخوارزمية.
    4. ملاءمة الخوارزمية للبرمجيات والعتاد الصلب للحاسوب.
    5. بساطة الخوارزمية.
    6. مرونة الخوارزمية.
    7. متطلبات الترخيص.

ولاحقا تم تحديد طول (المفتاح,الكتلة) الذي من المفترض ان يقدمها AES وهي : (256,128),(192,128),(128,128).

والمسابقة كانت على مرحلتين في المرحلة الاولى تقدمت 15 خوارزمية وفي عام 1999 تم اختيار 5 خوارزميات للتصفيات وهي :

  1. MARS
  2. RC6
  3. RIJNDEAL
  4. SERPENT
  5. TWOFISH

وفي تشرين اول من عام 2000 تم اختيار RIJNDEAL ليكون بديل DES وقد تم تغيير اسمه ل- AES وفي تشرين ثاني من عام 2001 اصبح معيارا رسميا (FIPS 197 ). مُخترعي هذا المعيار هما دايمن ورامين(Daemen and Rijmen )

رايندول[عدل]

رايندول هو خوارزمية تشفير كتل وهو يدعم أطوال مفاتيح وأطوال نصوص متعددة . مفتاح التشفير k هو مصفوفة ذات أبعاد  4 \times N_k (اي طول المفتاح هو 4 \cdot N_k بايت ) :

 
\underline{k}=
\begin{pmatrix}
k_{0,0} & k_{0,1} & \cdots & k_{0,N_{k-1}} \\
k_{1,0} & k_{1,1} & \cdots & k_{1,N_{k-1}} \\
k_{2,0} & k_{2,1} & \cdots & k_{2,N_{k-1}} \\
k_{3,0} & k_{3,1} & \cdots & k_{3,N_{k-1}} 
\end{pmatrix}

حيث كل  k_{i,j} يمكن اعتباره :

  • 8 بِْتْ او 1 بَايْتْ اي انه عدد في المجموعة  \mathcal{Z}_{2,8}
  • عدد صحيح في المجموعة  \mathcal{Z}_{256}

طول المفتاح في خوارزمية رايندول يمكن ان يكون  N_k = 4,6,8 \ (128,192,256) بايت .

قراءة مفتاح التشفير من المصفوفة تكون حسب كل عامود من اليسار إلى اليمين أي :

 \underline{k} = (k_{0,0},k_{1,0},k_{2,0},k_{3,0},\cdots,k_{0,N_{k-1}},k_{1,N_{k-1}},k_{2,N_{k-1}},k_{3,N_{k-1}})

الكتلة او النص الذي نريد تشفيره  \underline{x} هو مصفوفة ذات اطوال  4 \times N_b (اي طول المفتاح هو  4 \cdot N_b بايت ) :

 
\underline{x}=
\begin{pmatrix}
x_{0,0} & x_{0,1} & \cdots & x_{0,N_{b-1}} \\
x_{1,0} & x_{1,1} & \cdots & x_{1,N_{b-1}} \\
x_{2,0} & x_{2,1} & \cdots & x_{2,N_{b-1}} \\
x_{3,0} & x_{3,1} & \cdots & x_{3,N_{b-1}} 
\end{pmatrix}

حيث كل  x_{i,j} يمكن اعتباره :

  • 8 بِْتْ او 1 بَايْتْ اي انه عدد في المجموعة  \mathcal{Z}_{2,8}
  • عدد صحيح في المجموعة  \mathcal{Z}_{256}

الكتلة في خوارزمية رايندول يمكن أن تكون  N_b = 4,6,8 \ (128,192,256) بايت .

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

 \underline{x} = (x_{0,0},x_{1,0},x_{2,0},x_{3,0},\cdots,x_{0,N_{k-1}},x_{1,N_{k-1}},x_{2,N_{k-1}},x_{3,N_{k-1}})

وضعية رايندال \boldsymbol{\omega} هو المصفوفة :

 
\underline{\boldsymbol{\omega}}=
\begin{pmatrix}
\boldsymbol{\omega}_{0,0} & \boldsymbol{\omega}_{0,1} & \cdots & \boldsymbol{\omega}_{0,N_{b-1}} \\
\boldsymbol{\omega}_{1,0} & \boldsymbol{\omega}_{1,1} & \cdots & \boldsymbol{\omega}_{1,N_{b-1}} \\
\boldsymbol{\omega}_{2,0} & \boldsymbol{\omega}_{2,1} & \cdots & \boldsymbol{\omega}_{2,N_{b-1}} \\
\boldsymbol{\omega}_{3,0} & \boldsymbol{\omega}_{3,1} & \cdots & \boldsymbol{\omega}_{3,N_{b-1}} 
\end{pmatrix}

حيث كل  \boldsymbol{\omega} _{i,j} هو عدد صحيح في  \mathcal{Z}_{256} .

رايندول هو تركيب تحويلات (Transformations) على وضعيات رايندول وهذه التحويلات سنسميها الدورات (iterations) أي :  RIJ(\underline x )=\underline y = (T_{N_r}\circ T_{N_{r-1}}\circ \cdots \circ T_{N_1} \circ T_{N_0})

كل  T_i : \boldsymbol{\omega} \to \boldsymbol{\omega} أي أن المجال والمدى هو وضعيات رايندول ,

عدد الدورات (N_r)يتعلق بطول المفتاح ( N_k ) وطول النص ( N_b ) :

عدد دورات رايندول (N_r)
N_b =4 N_b =6 N_b =8
N_k =4 10 12 14
N_k =6 12 12 14
N_k =8 14 14 14

الدورة الاولى  T_0 هو XOR بين النص (الوضعية الاولى ) وبين مفتاح التشفير اي :

 
T_0(x)=
\begin{pmatrix}
k_{0,0} & k_{0,1} & \cdots & k_{0,N_{k-1}} \\
k_{1,0} & k_{1,1} & \cdots & k_{1,N_{k-1}} \\
k_{2,0} & k_{2,1} & \cdots & k_{2,N_{k-1}} \\
k_{3,0} & k_{3,1} & \cdots & k_{3,N_{k-1}} 
\end{pmatrix}
\oplus 
\begin{pmatrix}
x_{0,0} & x_{0,1} & \cdots & x_{0,N_{k-1}} \\
x_{1,0} & x_{1,1} & \cdots & x_{1,N_{k-1}} \\
x_{2,0} & x_{2,1} & \cdots & x_{2,N_{k-1}} \\
x_{3,0} & x_{3,1} & \cdots & x_{3,N_{k-1}} 
\end{pmatrix}

الدورات التي تأتي بعد هذا سوف تُعنى بتحويل الوضعية الحالية , ولتتم هذا الخوارزمية تفعل هذا في مراحل :

  1. عملية الخلط الخطية - التحويلات هي ShiftRow و- MixColumn  ;
  2. العملية غير الخطية - وهي التحويلة ByteSub  ;
  3. عملية إضافة المفتاح - التحويلة AddRoundKey .

حتى نُظهر المُعمى يكفي ان نقلب التحويلات أي :  RIJ^{-1}(\underline y )=\underline x = (T_{N_0}^{-1}\circ T_{N_{1}}^{-1}\circ \cdots \circ T_{N_{r-1}}^{-1} \circ T_{N_r}^{-1})

عملية الاستبدال[عدل]

عملية استبدال البايت هي مصفوفة S ثابتة دائما (اي عندما نريد التشفير عملية الاستبدال تتم من خلال هذا الصندوق دوما ) والاستبدال يتم وفقا للمصفوفة التالية :

 

مثال : اذا كان العدد الذي نريد استبداله هو 0x19 (حسب نظام العد الستة عشري) حينها يتم استبداله كالتالي : نذهب للسطر الاول العامود التاسع والناتج هو 0x4d او 212(حسب القاعدة 10 ) كما هو مبين في الصورة :

Rijndael example bytesub.png

عملية ازاحة السطر[عدل]

وهي عملية تزيح اسطر الوضعية بإزاحة دائرية , وهي تزيح السطر ال-i : i ازاحات يساراً,

  
SR: \omega=
\begin{pmatrix}
\omega_{0,0} & \omega_{0,1} & \omega_{0,2} & \omega_{0,3} \\
\omega_{1,0} & \omega_{1,1} & \omega_{1,2} & \omega_{1,3} \\
\omega_{2,0} & \omega_{2,1} & \omega_{2,2} & \omega_{2,3} \\
\omega_{3,0} & \omega_{3,1} & \omega_{3,2} & \omega_{3,3} 
\end{pmatrix}

\to

\begin{pmatrix}
\omega_{0,0} & \omega_{0,1} & \omega_{0,2} & \omega_{0,3} \\
\omega_{1,1} & \omega_{1,2} & \omega_{1,3} & \omega_{1,0} \\
\omega_{2,2} & \omega_{2,3} & \omega_{2,0} & \omega_{2,1} \\
\omega_{3,3} & \omega_{3,0} & \omega_{3,1} & \omega_{3,2} 
\end{pmatrix}

خلط العواميد[عدل]

وهي عملية خلط خطية للعواميد , بمعنى انها تتم بواسطة مصفوفة , وهذه العملية مُعرفة بواسطة عمليات في  GF(2^8) . اي انه لكل عامود

 
\begin{bmatrix}
s_0' \\
s_1' \\
s_2' \\
s_3' \\ 
\end{bmatrix}
=
\begin{bmatrix}
2 & 3 & 1 & 1\\
1 & 2 & 3 & 1\\
1 & 1 & 2 & 3\\
3 & 1 & 1 & 2
\end{bmatrix}
\begin{bmatrix}
s_0 \\
s_1 \\
s_2 \\
s_3
\end{bmatrix}

الحقل GF(2^8) مبني على متعدد الحدود x^8+x^4+x^3+x+1 .

طريقة اخرى لتنفيذ العملية هي :

 
\begin{bmatrix}
b_0 \\
b_1 \\
b_2 \\
b_3 \\ 
\end{bmatrix}
=
\begin{bmatrix}
f(a_0,a_1,a_2,a_3) \\
f(a_1,a_2,a_3,a_0) \\
f(a_2,a_3,a_0,a_1) \\
f(a_3,a_0,a_1,a_2) 
\end{bmatrix}

في حين أَنَّ :  f(a_0,a_1,a_2,a_3)= (a_1\oplus a_2\oplus a_3) \oplus g((a_0 \oplus a_1) << 1) و-  g(x)=\begin{cases} 
x \oplus 11B_x,  & \mbox{if }x \and 100_x \mbox{ true} \\
x , & \mbox{else}
\end{cases}

مقلوب هذه التحويلة هو أيضا خطي وهو مشابه جدا للعملية نفسها ما عدا اننا نكتب d مكان f :

 d_1 (a_0,a_1,a_2,a_3)=a_0 \oplus a_1 \oplus a_2 \oplus a_3

 d_2 (a_0,a_1,a_2,a_3)=g(d_1(a_0, a_1, a_2, a_3) << 1) \oplus (a_0  \oplus a_2)

 d_3(a_0, a_1, a_2, a_3) = g(d_2(a_0, a_1, a_2, a_3) << 1) \oplus (a0 \oplus a1)

 d(a_0, a_1, a_2, a_3) = g(d_3(a_0, a_1, a_2, a_3) << 1) \oplus (a_1 \oplus a_2 \oplus a_3)

اضافة مفتاح الدورة[عدل]

ببساطة هذه العملية تعمل التالي : تأخذ الوضعية الحالية وتعمل XOR مع مفتاح الدورة ( مفتاح الدورة لديه نفس طول الوضعية الحالية اي النص ) مفتاح الدورة نحسبه بواسطة خوارزمية انتاج المفاتيح . اذا كانت الوضعية الحالية هي :  \omega ومفتاح الدورة هو  k حينها :

 
\begin{pmatrix}
k_{0,0} & k_{0,1} & k_{0,2} & k_{0,3} \\
k_{1,0} & k_{1,1} & k_{1,2} & k_{1,3} \\
k_{2,0} & k_{2,1} & k_{2,2} & k_{2,3} \\
k_{3,0} & k_{3,1} & k_{3,2} & k_{3,3} 
\end{pmatrix}
\oplus 
\begin{pmatrix}
\omega_{0,0} & \omega_{0,1} & \omega_{0,2} & \omega_{0,3} \\
\omega_{1,0} & \omega_{1,1} & \omega_{1,2} & \omega_{1,3} \\
\omega_{2,0} & \omega_{2,1} & \omega_{2,2} & \omega_{2,3} \\
\omega_{3,0} & \omega_{3,1} & \omega_{3,2} & \omega_{3,3} 
\end{pmatrix}

التشفير وفك التشفير[عدل]

التشفير كالتالي :

  1. اولا نضيف المفتاح الدورة الاول ( K_0 )
  2.  N_r دورات في كل دورة :
    1. عملية الاستبدال
    2. ازاحة الاسطر
    3. خلط الاعمدة (ما عدا الدورة الاخيرة)
    4. اضافة مفتاح الدورة ( اي انه في الدورة i نضيف المفتاح  K_i ) .

حتى نفك التشفير كما ذكرنا في البداية يجب قلب ترتيب عمليات التشفير حسب الترتيب .

خوارزمية انتاج المفاتيح[عدل]

وهي ضرورية لانتاج مفتاح جديد من الذي استخدمناه سابقا ( لذا لن نستخدم نفس المفتاح مرتين ) والخوارزمية مدخلها مصفوفة بكبر N_k كلمات (كل كلمة هي 32 بيت ) والخوارزمية تحسب مفتاح الدورة  N_{r}+1 (الدورة القادمة),ليكن W مصفوفة كلمات وهو بكبر  W[4*(N_r+1) . حينها 4 الكلمات الاولى تصبح مفتاح الدورة الاولى و 4 الكلمات القادمة هي مفتاح الدورة الثانية وهكذا ... والخوارزمية هي كالتالي :

W[0..Nk-1] = key[*];
for i := Nk to 4*(Nr+1)-1 do {
temp = W[i-1]
if((i%Nk)==0)
temp = bytesubstitution(temp<<<8) ^ RCON[i/Nk];
if((Nk==8) & ((i%Nk)==4))
temp = bytesubstitution(temp);
W[i] = W[i-Nk] ^ temp;
}
  • ()bytesubstitution هي تنفيذ للمصفوفة S ,
  • في حين ان RCON هو المصفوفة التالية :


word32 RCON[] = {

 01_x, 02_x, 04_x, 08_x, 10_x, 20_x, 40_x, 80_x,

 1b_x, 36_x, 6c_x, d8_x, ab_x, 4d_x, 9a_x, 2f_x

} لاحظ ان هذه الاعداد هي قوى العدد 2 في الحقل GF(2^8)

خواص الامان[عدل]

  1. لا يوجد صفة المُكمل كما في DES . اي انه  AES_k(x) \neq AES_{\overline k}(\overline x)
  2. امان الخوارزمية كله متعلق باختيار المصفوفة S وهي الجزء الوحيد في الخوازمية الذي ليس خطيا او تآلفي حيث انه :  S[i]+S[j] \neq S[i+j] , مثلا اذا كان S مصفوفة تآلفية حينها كل العملية كانت لتكون تآلفية وبالتالي ليس آمنا ويمكن كسره بسهولة .
  3. أفضل الهجمات على هذه الخوارزمية وهي على 7 دورات من الخوارزمية تأخذ وقت  2^{110} عندما طول المفتاح هو 128 بيت , اما اذا طول المفتاح 256 بيت فأفضل الهجمات على 8 دورات هو  2^{204} , لا يوجد هجمات مع وقت أقصر من هذا . كما انه لا يوجد هجوم فعال على كل الدورات بمعنى ان وقت اللازم لكسر كل الخوارزمية هو  2^{128} عندما طول المفتاح هو 128 بيت .
  4. بالرغم من انه لا يوجد برهان على ان رايندول آمن ولكن الخوارزمية آمنة لكل انواع الهجمات المعروفة وقد تم فحص فعالية هذه الهجمات على الخوارزمية وكلها بائت بالفشل حيث انها لم تستطع ان تخفض الوقت اللازم لكسر الخوارزمية اي ان أفضل وقت للهجوم على الخوارزمية هو  2^{128} بهذه الوسائل .

هل AES دالة وحيدة الاتجاه؟[عدل]

بشكل عام لا يوجد برهان على أنَّ AES هي دالة وحيدة الاتجاه ولا حتى انه غير قابل للكسر ! ولكن بشكل عام يُعتقد انها غير قابلة للكسر ما يجعل منها مرشحة لتكون دالة وحيدة الاتجاه , ولكن حتى الان يُمكن اعتبارها كذلك وذلك لان نسبة البيانات التي نستطيع الحصول على مقلوبها هو صغير جدا.

استخدامات[عدل]

بما أنَّ AES هو خوارزمية تشفير لذا فان له كثير من الاستخدامات التي تضم حماية المستخدم عبر الانترنت لتصل إلى حماية وضمان البيانات في البنوك والمعامل كما أن ل-AES استخدامات في المجالات العسكرية , ان ما ضمن ان AES نافع في كل هذه التطبيقات هو عدم وجود طريقة فعالة لكسره , كما ان بعض أشهر البرامج والبروتوكلات تعتمد على مقاومة AES للهجمات الالكترونية ومنها :

  • يستخدم AES في برامج وين زيب(WINZIP) في حالة ان المُستخدم طلب تشفير البينات بعد ضغطها .
  • يُستخدم في برتوكول TLS , وهو برتوكول لانشاء اتصال آمن .
  • له كذلك استخدام في برتوكول IPsec وهو برتوكول لضمان الامان في اتصالات التي تعمل بواسطة IP عبر الانترنت .

انظر أيضا[عدل]

مصادر[عدل]