شرح خوارزميتي Shor وGrover

لا تشغّل الحواسيب الكمّية الخوارزميات التقليدية بسرعة أكبر فحسب، بل تستفيد من التراكب والتداخل الكمّيَين لحل مسائل معيّنة بسرعة أُسّية. تهدّد خوارزميتان معظم أنظمة التشفير المستخدمة حاليًا: خوارزمية Shor (تكسر RSA/ECC) وخوارزمية Grover (تضعف التشفير المتماثل ودوال التجزئة).

تحل خوارزمية Shor (1994) مسألتي تحليل الأعداد الصحيحة إلى عواملها واللوغاريتم المتقطع في زمن كثير الحدود على حاسوب كمّي. وهذا يكسر مباشرةً RSA (المبني على التحليل إلى عوامل)، وDiffie-Hellman (اللوغاريتم المتقطع بترديد p)، وECDH/ECDSA (اللوغاريتم المتقطع على المنحنيات الإهليلجية).

العنصر الأساسي في خوارزمية Shor هو تحويل فورييه الكمّي (QFT)، وهو نسخة كمّية من تحويل فورييه المتقطع (DFT) أسرع أُسّيًا. عند البحث عن الدورة، يحدّد QFT دورة الدالة f(x) = a^x mod N، ومنها تُشتق عوامل N باستخدام GCD.

لتحليل N إلى عوامله: (1) اختر a عشوائيًا بحيث a < N، وتحقّق من أن gcd(a,N)=1. (2) أوجد دورة الدالة r من f(x)=a^x mod N باستخدام QFT. (3) باحتمال مرتفع، يعطي gcd(a^{r/2}±1, N) عاملًا غير تافه. تستغرق الخطوة التقليدية O(log N)، بينما يستغرق البحث الكمّي عن الدورة O((log N)^3)، أي زمنًا كثير الحدود.

أفضل خوارزمية تقليدية للتحليل إلى عوامل هي GNFS، بزمن دون أُسّي O(exp((64/9 log N)^{1/3} log log N)^{2/3})). أما خوارزمية Shor على حاسوب كمّي متحمّل للأخطاء فتعمل في زمن كثير الحدود O((log N)^3). يتطلب RSA-2048 نحو 4000 كيوبت منطقي ونحو 10^9 عملية بوابة. وتمتلك حواسيب NISQ الحالية نحو 1000 كيوبت مشوّش، لذا لا تمثّل تهديدًا بعد.

توفّر خوارزمية Grover (1996) تسريعًا تربيعيًا للبحث غير المنظّم. بالنسبة إلى فضاء بحث يضم N عنصرًا، تحتاج الخوارزميات التقليدية إلى O(N) استعلامًا، بينما تحتاج خوارزمية Grover إلى O(√N). وعند تطبيقها على التشفير، تكسر المفاتيح المتماثلة ذات n بت في O(2^{n/2}) بدلًا من O(2^n).

AES-128: مستوى الأمان التقليدي 2^128، وتخفضه خوارزمية Grover إلى 2^64، مما يجعله غير آمن أمام حاسوب كمّي كبير. AES-256: من 2^256 إلى 2^128، ولذلك يظل آمنًا. الحل: مضاعفة أحجام المفاتيح المتماثلة. مقاومة التصادم في SHA-256: من 2^128 إلى 2^85 (مفارقة أعياد الميلاد + Grover). أما إيجاد صورة سابقة لـ SHA-256 فمن 2^256 إلى 2^128، وهو مقبول.

إن حواسيب NISQ الكمّية الحالية (IBM Heron: ‏133 كيوبتًا، وGoogle Sycamore: ‏70 كيوبتًا) صغيرة جدًا ومليئة بالضوضاء بحيث لا تستطيع إجراء حسابات ذات صلة بالتشفير. وتشير التقديرات إلى إمكانية كسر RSA-2048 بين عامي 2035 و2050 باستخدام حواسيب كمّية متحمّلة للأخطاء. أما هجمات اجمع الآن وفكّ التشفير لاحقًا فهي تهديد قائم حاليًا.

يجمع المهاجمون حركة البيانات المشفّرة اليوم ويخزّنونها. وعندما يتوفر حاسوب كمّي، يفكّون تشفيرها بأثر رجعي. وهذا يجعل الأسرار طويلة الأجل، مثل بيانات الحكومات المصنّفة والسجلات الطبية، عرضة للخطر اليوم. لذلك يجب البدء الآن في ترحيل التشفير ما بعد الكمّي (PQC) لهذه البيانات.

مسائل الشبكات (LWE وSIS)، والمسائل القائمة على الشفرات (McEliece)، والتوقيعات القائمة على التجزئة (SPHINCS+)، والمسائل متعددة الحدود، لا توجد لها خوارزمية كمّية معروفة بزمن كثير الحدود. وتشكل هذه المسائل أساس معايير NIST لما بعد الكم.

أُنجزت معايير NIST للتشفير ما بعد الكم (ML-KEM وML-DSA وSLH-DSA) في عام 2024. ينبغي للمؤسسات أن تجرد استخدام التشفير الحالي، وتحدّد البيانات طويلة الأجل، وتعطي الأولوية لنشر التشفير ما بعد الكم في تبادل المفاتيح، لأنه الأكثر إلحاحًا بسبب هجمات اجمع الآن وفكّ التشفير لاحقًا. أما التوقيعات فلديها وقت أطول.

تكسر خوارزمية Shor، التي تعمل في زمن كثير الحدود، أنظمة RSA وDH وECC. وتخفض خوارزمية Grover، التي توفر تسريعًا تربيعيًا، قوة المفاتيح المتماثلة إلى النصف. الحل: الترحيل إلى معايير NIST للتشفير ما بعد الكم القائمة على الشبكات. التالي: CRYSTALS-Kyber KEM.