ملخص تقني: مصفوفات لوكاس المعممة كطريقة جديدة لتشفير المفتاح العام

بيان المشكلة

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

المنهجية

1. الأسس الرياضية

يعتمد جوهر المخطط المقترح على بناء مصفوفات لوكاس المعممة (GLM) المشتقة من مصفوفات فيبوناتشي المعممة (GFM).

• مصفوفات فيبوناتشي المعممة (GFM): يستخدم المؤلفون متتالية فيبوناتشي المعممة من الرتبة $k$، وهي $\{f_{k,n}\}$، وتمثيلها المصفوفي المقابل $Q^k_n$. وتلبي هذه المصفوفات خصائص قياسية مثل $Q^n_k Q^l_k = Q^{n+l}_k$ وقواعد محددات (determinant) محددة بناءً على الرتبة $k$.
• متتاليات لوكاس المعممة: تم تعريف متتالية جديدة $\{l_{k,n}\}$ حيث تُشتق القيم الأولية من أثر (trace) أول $k$ من مصفوفات GFM (أي $l_{k,r} = \text{trace}(Q^r_k)$). وتحاكي علاقة الارتداد (recurrence relation) متتالية فيبوناتشي المعممة: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• مصفوفات لوكاس المعممة (GLM): يتم بناء مصفوفة ارتدادية $L^{(n)}_k$ باستخدام تركيبات خطية من حدود متتالية لوكاس المعممة. ويضع المؤلفون علاقة أساسية بين GLM و GFM:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  حيث $L^{(0)}_k$ هي مصفوفة لوكاس الأولية.

2. المخطط التشفيري

يدمج النظام المقترح هذه المصفوفات في تشفير هيل-أفيني (Affine-Hill Cipher) معدل مدمج مع بنية المفتاح العام لـ إلجامال (ElGamal).

• تبادل المفاتيح (القائم على إلجامال):

  • المستقبل (بوب): يختار عدداً أولياً $p$، وجذراً أولياً $\alpha$، وعدداً صحيحاً سرياً $D$. ثم ينشر $E_1 = \alpha$ و $E_2 = \alpha^D \pmod p$.
  • **المرسل (أليس): عدد صحيح عشوائي $e$. تقوم بحساب توقيع $s = E_1^e \pmod p$ وسر مشترك $\lambda = E_2^e \pmod p$.
  • الإرسال: ترسل أليس النص المشفر والتوقيع $s$ إلى بوب. وهي لا ترسل مصفوفة المفتاح الكاملة أو السر $\lambda$.

• التشفير (هيل-أفيني مع GLM):

  • باستخدام السر المشترك $\lambda$ (رتبة المصفوفة) والتوقيع $s$ (الأس)، تقوم أليس ببناء مصفوفة مفتاح التشفير $K = L^{(s)}_\lambda \pmod p$.
  • يتم إنشاء متجه الإزاحة $B$ باستخدام حدود من متتالية لوكاس: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • يتم تشفير كتل النص الصريح $P$ كالتالي: $C = (P \cdot K + B) \pmod p$.

• فك التشفير:

  • يستعيد بوب قيمة $\lambda$ باستخدام مفتاحه الخاص: $\lambda = s^D \pmod p$.
  • يقوم ببناء المصفوفة العكسية $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$، حيث $H = (L^{(0)}_\lambda)^2$. وقد أثبتت الورقة أن $L^{(s)}_\lambda L^{(-s)}_\lambda = H$، مما يضمن وجود معكوس.
  • يتم فك التشفير عبر: $P = (C - B) \cdot K^* \pmod p$.

المساهمات الرئيسية

1. تعريف مصفوفات لوكاس المعممة: تحدد الورقة رسمياً مصفوفات GLM من الرتبة $k$ وتضع خصائصها الجبرية، بما في ذلك صيغ المحدد (determinant)، وقواعد الضرب ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$)، والإنشاء الصريح لمعكوساتها.
2. توليد المفاتيح القائم على المعاملات: على عكس تشفير المصفوفات التقليدي حيث يجب مشاركة المصفوفة بأكملها أو توليدها من بذرة (seed) كبيرة، يسمح هذا المخطط لكلا الطرفين بإعادة بناء مصفوفة المفتاح باستخدام معاملين فقط: $\lambda$ (المشتق من مسألة اللوغاريتم المنفصل) و $s$ (التوقيع).
3. التكامل مع هيل-أفيني وإلجامال: يقترح المؤلفون نظاماً هجيناً يستخدم كفاءة تشفير هيل-أفيني (تشفير الكتل مع متجه إزاحة) مؤمناً بصعوبة مسألة اللوغاريتم المنفصل المتأصلة في إعداد إلجامال.
4. بناء المعكوس: توفر الورقة طريقة محددة لحساب معكوس GLM دون الاعتماد على طريقة حذف غاوس القياسية، وذلك باستخدام العلاقة $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

النتيات والتحليل

• مثال تنفيذي: يوضح المؤلفون المخطط باستخدام $p=37$، والرتبة $k=3$، وقيم صحيحة محددة لـ $D$ و $e$. لقد نجحوا في تشفير النص الصريح "NOBLE2022" إلى كتل نص مشفر واستعادة الرسالة الأصلية، مما يؤكد الصحة الرياضية لعمليات المصفوفات والحساب النمطي (modular arithmetic).
• تقليل التعقيد: يزعم المخطط أنه يقلل من تعقيد الوقت والمساحة لنقل المفتاح. فبدلاً من إرسال مصفوفة $n \times n$، يتم فقط تبادل الزوج $(\lambda, s)$.
• التحليل الأمني:
  • اللوغاريتم المنفصل: يتطلب استعادة $\lambda$ من $s$ حل مسألة اللوغاريتم المنفصل، وهو أمر غير ممكن حسابياً للقيم الأولية الكبيرة.
  • مساحة المفتاح: يعتمد الأمن ضد هجمات القوة الغاشمة (brute-force) على حجم الزمرة الخطية العامة $|GL(\lambda)|$. حسب حسابات المؤلفين، بالنسبة لـ $p=37$ و $\lambda=50$، تبلغ مساحة المفتاح حوالي $3.105 \times 10^{3920}$، وهي مساحة ضخمة للغاية.
  • استقلالية التوقيع: يشير التحليل إلى أن التوقيع $s$ لا يخل بالأمن حتى لو عُرف، حيث يعتمد الأمن بشكل أساسي على صعوبة تحديد $\lambda$ وضخامة مساحة المصفوفات المتاحة.

الأهمية والادعاءات

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

• توسيع مساحة المفتاح: استخدام مصفوفات لوكاس المعممة يوسع مساحة المفتاح المتاحة بشكل كبير مقارنة بالتطبيقات القياسية.
• الكفاءة: من خلال تقليل نقل المفتاح إلى زوج من الأرقام، يحسن المخطط الكفاءة من حيث عرض النطاق الترددي والتخزين.
• المتانة: إن الجمع بين مسألة اللوغاريتم المنفصل (لاتفاق المفاتيح) وتعقيد بنية المصفوفة (للتشفير) يخلق دفاعاً متعدد الطبقات.

يؤكد المؤلفون أن الطريقة "بسيطة رياضياً للطرف المصرح له ومضنية للمتسلل"، اعتماداً على الصعوبة الراسخة لمسألة اللوغاريتم المنفصل والمساحة التوافقية الضخمة لمصفوفات لوكاس المعممة.