التشفير غير التبادلي

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

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

طُوِّرت بروتوكولات التشفير غير التبادلية لحل العديد من المشكلات التشفيرية مثل تبادل المفاتيح ، والتشفير وفك التشفير ، والمصادقة . وتتشابه هذه البروتوكولات إلى حد كبير مع البروتوكولات المقابلة لها في حالة التشفير التبادلي.

بعض بروتوكولات التشفير غير التبادلية

في هذه البروتوكولات، يُفترض أن G زمرة غير تبديلية . إذا كان w و a عنصرين من G، فإن الرمز w a يشير إلى العنصر a −1 wa .

بروتوكولات تبادل المفاتيح

البروتوكول منسوب إلى كو، لي، وآخرون.

يقوم البروتوكول التالي، الذي وضعه كو ولي وآخرون، بإنشاء مفتاح سري مشترك K لأليس وبوب .

  1. تم نشر عنصر w من G.
  2. تم نشر مجموعتين فرعيتين A و B من G بحيث يكون ab = ba لجميع a في A و b في B.
  3. تختار أليس عنصرًا a من المجموعة A وترسل w a إلى بوب. وتحتفظ أليس بالعنصر a سرًا.
  4. يختار بوب عنصرًا b من المجموعة B ويرسل w b إلى أليس. ويحتفظ بوب بالعنصر b سرًا.
  5. تقوم أليس بحساب K = ( w b ) a = w ba .
  6. يحسب بوب K' = ( w a ) b = w ab .
  7. بما أن ab = ba ، فإن K = K' . تشترك أليس وبوب في المفتاح السري المشترك K.

بروتوكول أنشيل-أنشيل-جولدفيلد

هذا بروتوكول لتبادل المفاتيح يستخدم مجموعة غير تبديلية G. وهو ذو أهمية لأنه لا يتطلب مجموعتين فرعيتين متبادلتين A و B من G كما هو الحال في البروتوكول الذي وضعه كو ولي وآخرون.

  1. يتم اختيار ونشر العناصر a 1 و a 2 و ... و a k و b 1 و b 2 و ... و b m من G.
  2. تختار أليس كلمة خاصة x في G ككلمة في a 1 ، a 2 ، ... ، a k ؛ أي أن x = x ( a 1 ، a 2 ، ... ، a k ).
  3. ترسل أليس b 1 x ، b 2 x ، . . . ، b m x إلى بوب.
  4. يختار بوب حرف y خاصًا في G ككلمة في b 1 ، b 2 ، ... ، b m ؛ أي y = y ( b 1 ، b 2 ، ... ، b m ).
  5. يرسل بوب حرف 1 y ، وحرف 2 y ، ...، وحرف k y إلى أليس.
  6. تتشارك أليس وبوب المفتاح السري المشترك K = x −1 y −1 xy .
  7. تقوم أليس بحساب x ( a 1 y , a 2 y , . . . , a k y ) = y −1 xy . بضربها من اليسار في x −1 ، تحصل أليس على K .
  8. يحسب بوب y ( b 1 x , b 2 x , . . . , b m x ) = x −1 yx . بضربها من اليسار في y −1 ثم أخذ المعكوس، يحصل بوب على K .

بروتوكول تبادل المفاتيح الخاص بستيكل

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

  1. ليكن G مجموعة عامة غير تبديلية منتهية .
  2. ليكن a و b عنصرين عامين في G بحيث يكون ab ≠ ba . ولتكن رتبتا a و b هما N و M على التوالي.
  3. تختار أليس رقمين عشوائيين n < N و m < M وترسل u = a m b n إلى بوب.
  4. يختار بوب رقمين عشوائيين r < N و s < M ويرسل v = a r b s إلى أليس.
  5. المفتاح المشترك بين أليس وبوب هو K = a m + r b n + s .
  6. تقوم أليس بحساب المفتاح باستخدام المعادلة K = a m vb n .
  7. يحسب بوب المفتاح باستخدام المعادلة K = a r ub s .

بروتوكولات التشفير وفك التشفير

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

  1. ليكن G زمرة غير تبديلية. ولتكن A و B زمرتين جزئيتين عامتين من G بحيث يكون ab = ba لكل a في A و b في B.
  2. يتم اختيار عنصر x من G ونشره.
  3. يختار بوب مفتاحًا سريًا b من A وينشر z = x b كمفتاحه العام.
  4. تختار أليس قيمة عشوائية r من المجموعة B وتحسب t = z r .
  5. الرسالة المشفرة هي C = ( x r , H ( t )⊕{\displaystyle \oplus }م )، حيث H هي دالة تجزئة ما و⊕{\displaystyle \oplus }يشير الرمز إلى عملية XOR . ترسل أليس الرمز C إلى بوب.
  6. لفك تشفير C ، يستعيد بوب t على النحو التالي: ( x r ) b = x rb = x br = ( x b ) r = z r = t . الرسالة النصية الأصلية التي أرسلتها أليس هي P = ( H ( t )⊕{\displaystyle \oplus }م )⊕{\displaystyle \oplus }H ( t ) = m .

بروتوكولات المصادقة

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

  1. ليكن G مجموعة غير تبديلية وليكن A و B مجموعتين جزئيتين من G بحيث يكون ab = ba لجميع a في A و b في B.
  2. يتم اختيار عنصر w من G ونشره.
  3. تختار أليس عنصرًا خاصًا s من A وتنشر الزوج ( w , t ) حيث t = w s .
  4. يختار بوب حرف r من المجموعة B ويرسل تحديًا w ′ = w r إلى أليس.
  5. ترسل أليس الرد w ′ ′ = ( w ′ ) s إلى بوب.
  6. يتحقق بوب مما إذا كان w ′ ′ = tr . إذا كان هذا صحيحًا، فسيتم تحديد هوية أليس.

الأساس الأمني ​​للبروتوكولات

إن أساس أمان وقوة البروتوكولات المختلفة المذكورة أعلاه يكمن في صعوبة المشكلتين التاليتين:

  • The conjugacy decision problem (also called the conjugacy problem): Given two elements u and v in a group G determine whether there exists an element x in G such that v = ux, that is, such that v = x−1ux.
  • The conjugacy search problem: Given two elements u and v in a group G find an element x in G such that v = ux, that is, such that v = x−1ux.

If no algorithm is known to solve the conjugacy search problem, then the function x → ux can be considered as a one-way function.

Platform groups

A non-commutative group that is used in a particular cryptographic protocol is called the platform group of that protocol. Only groups having certain properties can be used as the platform groups for the implementation of non-commutative cryptographic protocols. Let G be a group suggested as a platform group for a certain non-commutative cryptographic system. The following is a list of the properties expected of G.

  1. The group G must be well-known and well-studied.
  2. The word problem in G should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements of G.
  3. It should be impossible to recover the factors x and y from the product xy in G.
  4. The number of elements of length n in G should grow faster than any polynomial in n. (Here "length n" is the length of a word representing a group element.)

Examples of platform groups

Braid groups

Let n be a positive integer. The braid group Bn is a group generated by x1, x2, . . . , xn−1 having the following presentation:

Bn=⟨x1,x2,…,xn−1|xixj=xjxi if |i−j|>1 and xixjxi=xjxixj if |i−j|=1⟩{\displaystyle B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big |}x_{i}x_{j}=x_{j}x_{i}{\text{ إذا كان }}|ij|>1{\text{ و }}x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}{\text{ إذا كان }}|ij|=1\right\rangle }

Thompson's group

Thompson's group is an infinite group F having the following infinite presentation:

F=⟨x0,x1,x2,…|xk−1xnxk=xn+1 for k<n⟩{\displaystyle F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle }

Grigorchuk's group

لنرمز بـ T إلى الشجرة الثنائية الجذرية اللانهائية . مجموعة الرؤوس V هي مجموعة جميع المتتاليات الثنائية المنتهية. ولنرمز بـ A ( T ) إلى مجموعة جميع التشاكلات الذاتية لـ T. (التشاكل الذاتي لـ T يُبدّل الرؤوس مع الحفاظ على الاتصال). زمرة غريغورتشوك Γ هي الزمرة الجزئية من A ( T ) المولدة بواسطة التشاكلات الذاتية a ، b ، c ، d المعرفة كما يلي:

  • أ(ب1،ب2،...،بن)=(1-ب1،ب2،...،بن){\displaystyle a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})}
  • ب(ب1،ب2،...،بن)={(ب1،1-ب2،...،بن) لو ب1=0(ب1،ج(ب2،...،بن)) لو ب1=1{\displaystyle b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ إذا كان }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ إذا كان }}b_{1}=1\end{cases}}}
  • ج(ب1،ب2،...،بن)={(ب1،1-ب2،...،بن) لو ب1=0(ب1،د(ب2،...،بن)) لو ب1=1{\displaystyle c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ إذا كان }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ إذا كان }}b_{1}=1\end{cases}}}
  • د(ب1،ب2،...،بن)={(ب1،ب2،...،بن) لو ب1=0(ب1،ب(ب2،...،بن)) لو ب1=1{\displaystyle d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},b_{2},\ldots ,b_{n})&{\text{ إذا كان }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ إذا كان }}b_{1}=1\end{cases}}}

مجموعة آرتين

مجموعة آرتين A (Γ) هي مجموعة ذات التمثيل التالي:

أ(Γ)=⟨أ1،أ2،...،أن|μأناج=μجأنا ل 1≤أنا<ج≤ن⟩{\displaystyle A(\Gamma )=\left\langle a_{1},a_{2},\ldots ,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i<j\leq n\right\rangle }

أينμأناج=أأناأجأأنا...{\displaystyle \mu _{ij}=a_{i}a_{j}a_{i}\ldots } (مأناج{\displaystyle m_{ij}}العوامل) ومأناج=مجأنا{\displaystyle m_{ij}=m_{ji}}.

مجموعات المصفوفات

ليكن F حقلاً منتهياً. وقد استُخدمت مجموعات المصفوفات على F كمجموعات أساسية لبعض بروتوكولات التشفير غير التبادلية.

منتجات شبه مباشرة

[ 1 ]

انظر أيضاً

مراجع

  1. ↑ حبيب، م.؛ كهروباي، د .؛ كوباريس، س.؛ شبيلرين، ف. (2013). "تبادل المفاتيح العامة باستخدام الضرب شبه المباشر للمجموعات (شبه)". التشفير التطبيقي وأمن الشبكات. ACNS 2013. سلسلة محاضرات في علوم الحاسوب. المجلد  7954. سبرينغر. الصفحات 475-486 . arXiv : 1304.6572 . CiteSeerX 10.1.1.769.1289 . doi : 10.1007/978-3-642-38980-1_30 . ISBN   978-3-642-38980-1.

للمزيد من القراءة

  1. مياسنيكوف، أليكسي؛ شبيلراين، فلاديمير؛ أوشاكوف، ألكسندر (2008). التشفير القائم على المجموعات . دار نشر بيركهاوزر. ISBN 9783764388270.
  2. كاو، تشنفو (2012). اتجاهات جديدة في علم التشفير الحديث . دار نشر سي آر سي. رقم ISBN 978-1-4665-0140-9.
  3. بنيامين فاين وآخرون  (2011). "جوانب التشفير القائم على المجموعات غير التبديلية: دراسة استقصائية ومشاكل مفتوحة". arXiv : 1103.4093 [ cs.CR ].
  4. مياسنيكوف، أليكسي ج.؛ شبيلراين، فلاديمير؛ أوشاكوف، ألكسندر (2011). التشفير غير التبادلي وتعقيد مسائل نظرية الزمر . الجمعية الرياضية الأمريكية. ISBN 9780821853603.