سيتم التعرف على الأعداد الأولية، وسيتم كسر التشفير

الخوارزمية التي تجعل من الممكن التحديد بشكل مؤكد ما إذا كان الرقم أوليًا قد تستنزف إحدى طرق التشفير الرائدة في العالم، والتي تعتبر شائعة جدًا على الإنترنت

بواسطة أوريل بريزون

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

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

الأعداد الأولية هي أرقام لا تقبل القسمة على أي رقم باستثناء نفسها والواحد. الأرقام الأولية الصغيرة (23، 19، 17، 13، 11، 7، 5، 3...، 2، 1) هي بداية قائمة معقدة للغاية. شغلت دراسة توزيع الأعداد الأولية على خط الأعداد علماء الرياضيات في اليونان القديمة، وما زالت تشغل علماء الرياضيات حتى اليوم. لتحديد ما إذا كان العدد أوليًا، تأكد من عدم وجود عوامل أخرى له غير الواحد ونفسه. هذه العملية بسيطة مع أرقام صغيرة، ولكن كلما زاد العدد الذي يتم اختباره، أصبحت المهمة أكثر صعوبة، لدرجة أنه حتى أجهزة الكمبيوتر العملاقة لا تستطيع القيام بها. على سبيل المثال: يأتي متصفح Microsoft الشهير "Explorer" اليوم مزودًا بتشفير 128 بت. يتطلب كسر هذا التشفير التحقق من أولوية الأرقام التي تصل إلى 39 رقمًا. حتى أقوى جهاز كمبيوتر سيحتاج إلى وقت طويل للتحقق مما إذا كان هذا الرقم قابلاً للقسمة على رقم آخر بدون باقي.

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

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

ويمكن توضيح الفكرة على النحو التالي: لكي أتلقى رسالة سرية من شخص معين، سأرسل له أولاً قفلًا زنبركيًا، من النوع الذي يُقفل بنقرة واحدة. سأترك المفتاح معي. سيقوم هذا الشخص بفتح القفل واستخدامه لقفل الرسالة السرية التي يريد أن يرسلها لي. سيضع الرسالة في الصندوق ويقفلها بالقفل عن طريق النقر. منذ لحظة قفله، لا يمكن لأحد غيري (ولا حتى "خزانة" الرسالة) الوصول إلى الرسالة، لأن المفتاح فقط في يدي. إذا كنت أرغب الآن في إرسال رسالة سرية مرة أخرى، فسأطلب من ذلك الشخص أن يرسل لي قفلًا ويترك المفتاح معه، بنفس الطريقة. يأتي التطور من فصل القفل عن المفتاح - كلمة مرور التشفير عن كلمة مرور فك التشفير. بهذه الطريقة يمكنك إرسال رسائل سرية دون تنسيق كلمات المرور.

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

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

علم

مع كل الاحترام الواجب للخوارزمية الحتمية في زمن متعدد الحدود، لن يتم كسر التشفير

بقلم تامير تيسا

المقال "سيتم تحديد الأرقام الأولى، سيتم كسر الكود" ("هآرتس"، 19.8/XNUMX) يتحدث عن اكتشاف خوارزمية تستخدم للتحقق من أولوية الأرقام. ومع ذلك، فإن الاستنتاجات التي توصل إليها المراسل من هذا الاكتشاف كانت مثيرة ولا أساس لها من الصحة.
إن التحقق من أولية الأعداد هو في الواقع مشكلة كلاسيكية، ذات أهمية نظرية وعملية. الاختبار البسيط هو محاولة قسمة الرقم على جميع الأرقام حتى جذره. إذا فشلت كل محاولات القسمة، فلدينا رقم أولي. لكن "مدة تشغيل" مثل هذه الخوارزمية غير معقولة عندما يتعلق الأمر بأعداد كبيرة. في لغة نظرية علوم الكمبيوتر، يكون وقت تشغيل مثل هذه الخوارزمية "أسيًا في طول الإدخال". أي أننا إذا أردنا التحقق من أولية رقم باستخدام أرقام عشرية d (يشير d في هذه الحالة إلى "طول الإدخال")، فإن عدد عمليات القسمة التي سنحتاج إلى إجرائها سيكون تقريبًا عشرة أس د/2 الطاقة. على سبيل المثال، لغرض اختبار أسبقية

الرقم 728,639 (حيث d=6)، سيكون عدد العمليات التي يتعين علينا القيام بها حوالي عشرة أس 3(d/2)، أي حوالي ألف عملية. المعنى العملي هو أن الخوارزمية أصبحت غير عملية حتى عند التعامل مع أرقام متواضعة. وبما أننا في تطبيقات أمن المعلومات نحتاج إلى أعداد أولية ضخمة (على سبيل المثال، 1,024 بت، أي ما يعادل حوالي 309 رقمًا عشريًا)، فمن الضروري استخدام طرق أخرى.

ونظرا لإيجاز الصفحة، سنتخطى تاريخا يمتد لـ 300 عام، بدأ بفرمات في القرن السابع عشر وانتهى عام 17، عندما نشر عالم الرياضيات مايكل رابين، الحائز على جائزة إسرائيل وجائزة تورينج، نسخته من اختبار GL. ميلر من عام 1980 لاختبار البدائية. وهي عبارة عن خوارزمية عشوائية من النوع المعروف باسم "مونت كارلو". تجري مثل هذه الخوارزمية سلسلة من التجارب على الرقم المحدد. إذا فشلت إحدى المحاولات، تتوقف الخوارزمية وتعلن أن الرقم غريب (غير أولي) مصحوبًا بعلامة تعجب واثقة. من ناحية أخرى، إذا كانت جميع التجارب ناجحة، تشير الخوارزمية إلى الرقم باعتباره أوليًا مصحوبًا بحاشية سفلية "باحتمال كبير جدًا". على سبيل المثال، إذا كان احتمال نجاح رقم غريب في اجتياز تجربة واحدة هو الربع (1976%)، فإن احتمال نجاحه في سلسلة من عشرين تجربة ينخفض ​​إلى الربع أس 25 - وهو رقم صغير للغاية. كلما زاد عدد المحاولات، قل احتمال أن نحدد عن طريق الخطأ عددًا غريبًا على أنه عدد أولي.

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

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

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

والآن فيما يتعلق بالشفرات: يعد التحقق من أولوية الأرقام أمرًا ضروريًا عند إعداد أنظمة أمن المعلومات. هذا البيان صحيح، على سبيل المثال، فيما يتعلق بنظام التشفير المعروف RSA، أو طريقة Diffie-Hellman المستخدمة لتبادل المفاتيح، أو بروتوكول التوقيع الرقمي .DSA، لكن مشكلة التحقق من البداية لا توجد ولا يمكن أن يكون لها أي آثار لكسر مثل هذه الأنظمة. لو كانت القدرة على التحقق من البدائية لها مثل هذه النتيجة المدمرة، لكان من الممكن نشر مقالة معنية حول هذا الموضوع في وقت مبكر من عام 1980 وحتى قبل ذلك.

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

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

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

د. تيسا هي عضو هيئة تدريس في قسم الرياضيات التطبيقية في جامعة تل أبيب