شفرة جوبا الثنائية

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

يتم تعريف رمز جوبا الثنائي غير القابل للاختزال بواسطة متعدد الحدود${\displaystyle g(x)}$درجة علمية${\displaystyle t}$على حقل منتهٍ${\displaystyle GF(2^{m})}$بدون جذور متكررة، وتسلسل${\displaystyle L_{1},...,L_{n}}$ل${\displaystyle n}$عناصر مميزة من${\displaystyle GF(2^{m})}$التي ليست جذورًا لـ${\displaystyle g}$.

تنتمي الكلمات المشفرة إلى نواة دالة المتلازمة، وتشكل فضاءً فرعياً من${\displaystyle \{0,1\}^{n}}$:

${\displaystyle \Gamma (g,L)=\left\{c\in \{0,1\}^{n}\,{\Bigg \vert }\,\sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\equiv 0{\bmod {g}}(x)\right\}}$

الكود المحدد بواسطة مجموعة${\displaystyle (g,L)}$له أبعاد على الأقل${\displaystyle n-mt}$والمسافة على الأقل${\displaystyle 2t+1}$وبالتالي، يمكنه ترميز رسائل بطول لا يقل عن${\displaystyle n-mt}$باستخدام كلمات مشفرة بحجم${\displaystyle n}$مع تصحيح على الأقل${\displaystyle \left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor =t}$يحتوي على مصفوفة فحص التكافؤ ملائمة.${\displaystyle H}$يخبر

${\displaystyle H=VD={\begin{pmatrix}1&1&1&\cdots &1\\L_{1}^{1}&L_{2}^{1}&L_{3}^{1}&\cdots &L_{n}^{1}\\L_{1}^{2}&L_{2}^{2}&L_{3}^{2}&\cdots &L_{n}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\L_{1}^{t-1}&L_{2}^{t-1}&L_{3}^{t-1}&\cdots &L_{n}^{t-1}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{g(L_{1})}}&&&&\\&{\frac {1}{g(L_{2})}}&&&\\&&{\frac {1}{g(L_{3})}}&&\\&&&\ddots &\\&&&&{\frac {1}{g(L_{n})}}\end{pmatrix}}}$

لاحظ أن هذا الشكل من مصفوفة فحص التكافؤ، يتكون من مصفوفة فاندرموند${\displaystyle V}$والمصفوفة القطرية${\displaystyle D}$تتشابه هذه الصيغة مع مصفوفات التحقق الخاصة بالرموز البديلة ، وبالتالي يمكن استخدام وحدات فك التشفير البديلة على هذه الصيغة. وعادةً ما توفر وحدات فك التشفير هذه قدرة محدودة فقط على تصحيح الأخطاء (في معظم الحالات).${\displaystyle t/2}$).

لأغراض عملية، عادةً ما يتم تحويل مصفوفة فحص التكافؤ لرمز غوبا الثنائي إلى شكل ثنائي أكثر ملاءمة للحاسوب عن طريق بنية التتبع، التي تحول${\displaystyle t}$-بواسطة-${\displaystyle n}$المصفوفة على${\displaystyle GF(2^{m})}$إلى${\displaystyle mt}$-بواسطة-${\displaystyle n}$المصفوفة الثنائية عن طريق كتابة معاملات متعددة الحدود لـ${\displaystyle GF(2^{m})}$العناصر على${\displaystyle m}$صفوف متتالية.

يتم فك تشفير رموز جوبا الثنائية تقليديًا باستخدام خوارزمية باترسون، التي تتميز بقدرة جيدة على تصحيح الأخطاء (فهي تصحح جميع الأخطاء).${\displaystyle t}$أخطاء التصميم)، كما أنه سهل التنفيذ إلى حد ما.

تحوّل خوارزمية باترسون متلازمة إلى متجه من الأخطاء. متلازمة الكلمة الثنائية${\displaystyle c=(c_{1},\dots ,c_{n})}$من المتوقع أن يتخذ شكلاً من

${\displaystyle s(x)\equiv \sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\mod g(x)}$

صيغة بديلة لمصفوفة فحص التكافؤ بناءً على صيغة لـ${\displaystyle s(x)}$يمكن استخدامها لإنتاج مثل هذه المتلازمة من خلال عملية ضرب مصفوفة بسيطة .

ثم تقوم الخوارزمية بالحساب${\displaystyle v(x)\equiv {\sqrt {s(x)^{-1}-x}}\mod g(x)}$يفشل ذلك عندما${\displaystyle s(x)\equiv 0}$، ولكن هذا هو الحال عندما تكون كلمة الإدخال كلمة رمزية، لذلك لا يلزم تصحيح الأخطاء.

${\displaystyle v(x)}$يتم اختزالها إلى كثيرات الحدود${\displaystyle a(x)}$و${\displaystyle b(x)}$باستخدام خوارزمية إقليدس الموسعة ، بحيث${\displaystyle a(x)\equiv b(x)\cdot v(x)\mod g(x)}$، بينما${\displaystyle \deg(a)\leq \lfloor t/2\rfloor }$و${\displaystyle \deg(b)\leq \lfloor (t-1)/2\rfloor }$.

وأخيرًا، يتم حساب متعددة حدود تحديد موقع الخطأ على النحو التالي:${\displaystyle \sigma (x)=a(x)^{2}+x\cdot b(x)^{2}}$لاحظ أنه في حالة النظام الثنائي، يكفي تحديد الأخطاء لتصحيحها، إذ لا توجد سوى قيمة واحدة أخرى ممكنة. أما في حالات الأنظمة غير الثنائية، فيجب حساب متعددة حدود تصحيح الأخطاء بشكل منفصل.

إذا كانت كلمة السر الأصلية قابلة للفك و${\displaystyle e=(e_{1},\dots ,e_{n})}$كان متجه الخطأ الثنائي، ثم

${\displaystyle \sigma (x)=\prod _{i=1}^{n}(x-L_{i})^{e_{i}}}$

تحليل أو تقييم جميع جذور${\displaystyle \sigma (x)}$وبالتالي يوفر معلومات كافية لاستعادة متجه الخطأ وتصحيح الأخطاء.

تتمتع رموز جوبا الثنائية، التي تُعتبر حالة خاصة من رموز جوبا، بخاصية مثيرة للاهتمام وهي أنها تصحح بشكل كامل${\displaystyle \deg(g)}$الأخطاء، بينما فقط${\displaystyle \deg(g)/2}$الأخطاء في الحالات الثلاثية وجميع الحالات الأخرى. تقاربياً، تصل قدرة تصحيح الأخطاء هذه إلى حد جيلبرت-فارشاموف الشهير .

بسبب قدرة تصحيح الأخطاء العالية مقارنة بمعدل الكود وشكل مصفوفة فحص التكافؤ (والتي عادة ما يصعب تمييزها عن مصفوفة ثنائية عشوائية كاملة الرتبة)، يتم استخدام رموز Goppa الثنائية في العديد من أنظمة التشفير ما بعد الكمومية ، ولا سيما نظام McEliece للتشفير ونظام Niederreiter للتشفير .

• إلوين ر. بيرلكامب، رموز جوبا، معاملات IEEE في نظرية المعلومات، المجلد IT-19، العدد 5، سبتمبر 1973، https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
• دانييلا إنجلبرت، رافائيل أوفربيك، آرثر شميدت. "ملخص لأنظمة التشفير من نوع ماكليس وأمنها". مجلة التشفير الرياضي 1، 151-199. MR 2345114. النسخة السابقة: http://eprint.iacr.org/2006/162/ 
• دانيال ج. بيرنشتاين. "فك تشفير القوائم لرموز جوبا الثنائية." http://cr.yp.to/codes/goppalist-20110303.pdf

• رموز BCH
• معدل الترميز
• تصحيح الخطأ ريد-سولومون