في 2 كانون الأول (ديسمبر) 2019 ، أبلغت القائمة البريدية لنظرية الأرقام
nmbrthry@listserv.nodak.edu عن
عامل رقم RSA-240 (240 منزلة عشرية ، 795 بت). هذا إنجاز جديد في نظرية التشفير والأرقام والمهمة المكتملة التالية من قائمة
RSA Factoring Challenge .
هنا الرقم وعوامله:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
استنادًا إلى الاتجاه الحالي ، يمكنك أن تتخيل تقريبًا عند اختراق RSA-1024 (309 رقمًا عشريًا) و RSA-2048 (617 رقمًا).
تمثلت الإنجازات السابقة في تحديد
عدد 768 بت (232 منزلة عشرية) في عام 2009
واللوغاريتم المنفصل لرقم 768 بت في عام 2016 .
تعتمد العديد من خوارزميات تشفير المفتاح العام على أعداد كبيرة للغاية ، والتي هي نتاج رقمين أوليين. يعتمد البعض الآخر على صعوبة حل بعض المشكلات اللوغاريتمية المنفصلة. مع أحجام مفاتيح كبيرة بما يكفي ، لا توجد طريقة معروفة للقضاء على هذا التشفير. تؤدي عوامل الأعداد الكبيرة وحساب اللوغاريتم المنفصل إلى تدمير ضمانات التشفير لحجم مفتاح معين وإجبار المستخدمين على زيادة عدد بتات إنتروبي عند إنشاء سر.
تتشقق الأصفار المتطورة بشكل متزايد مع نمو أداء وحدة المعالجة المركزية وتحسين الخوارزميات.
بعد اختراع خوارزمية غربال مجال الرقم العام (GNFS) في أوائل التسعينيات ، لم يظهر أي شيء ثوري في مجال عدد صحيح ، على الرغم من إجراء بعض التحسينات الهامة. على سبيل المثال ، في السنوات القليلة الماضية ، تمكن الباحثون من الإسراع بشكل كبير في مرحلة العثور على متعدد الحدود المناسب.
إن معاملات RSA-240 خارج الصف العام أيضًا ، لأنه تم تنفيذها ليس فقط عن طريق زيادة الطاقة الحاسوبية ، ولكن أيضًا بسبب تحسين البرمجيات والخوارزميات. لإثبات فعالية التغييرات التي تم إجراؤها ، أطلق الباحثون البرنامج على نفس الجهاز الذي تم استخدامه لحساب اللوغاريتم المنفصل 768 بت في عام 2016. وجدوا أن غربلة مصفوفة من أرقام 795 بت عليها 25 ٪ أسرع من غربلة مصفوفة من أرقام 768 بت دون التحسين.
قامت نفس المجموعة من الباحثين بحساب لوغاريتم منفصل من نفس الحجم. لأول مرة في التاريخ ، يتم تعيين سجلات منفصلة لارتباطات ومعاملات الأرقام من نفس الحجم في نفس الوقت ، وحتى على نفس الأجهزة والبرامج.
بفضل تحسين الخوارزميات والبرامج ، تم تسريع اللوغاريتم المنفصل لرقم 795 بت بنسبة 33٪ مقارنةً بوغاريتم رقم 768 بت دون التحسين على نفس الجهاز.
وفقًا للنظرية ، فإن لوغاريتم رقم 795 بت أكثر تعقيدًا بنسبة 2.25 مرة من رقم 768 بت. هذا يعني أن تأثير التحسين هو في الواقع ثلاث مرات (2.25 × 1.33 = 3).
تم إجراء كلا النوعين من العمليات الحسابية باستخدام خوارزمية حقل رقم الغربال في برنامج
CADO-NFS مفتوح المصدر. من بين التحسينات تحسين التوازي واستخدام الذاكرة ، وكذلك الكثير من العمل للعثور على مزيد من معلمات الحساب المثلى (تم تطوير برنامج خاص لاختبار وترتيب معلمات حساب مختلفة).
يبلغ مقدار الوقت الحسابي لكل من السجلين الجديدين حوالي 4000 عام من تشغيل النوى المادية لمعالجات Intel Xeon Gold 6130 (بتردد 2.1 جيجاهيرتز) ، إذا أخذنا هذا المعالج كمرجع.
انهيار تقريبي للوقت في التوصيف واللوغاريتم:
- الفحص RSA-240: 800 سنة أساسية
- مصفوفة RSA-240: 100 سنة أساسية
- الفحص DLP-240: 2400 سنوات أساسية
- المصفوفة DLP-240: 700 سنة أساسية
تم تسجيل هذا الإنجاز على حساب مجموعة علمية بقيادة إيمانويل ثومي ، الباحث البارز في
المعهد الوطني الفرنسي للمعلوماتية والرياضيات التطبيقية .
نشر مخترعو الشفرة RSA
أرقام RSA
من جميع الأحجام حتى RSA-2048. يمكن للجميع محاولة اختراقهم.
استنادًا إلى الاتجاه الحالي ، يمكنك حساب وقت اختراق RSA-1024 (309 حرفًا) و RSA-2048 (617 حرفًا). إذا قمت باستكمال الجدول ، فستحصل على حوالي 2031 و 2073 ، على التوالي. لكننا نرى أن تحسين البرمجيات والخوارزميات يمكن أن يقرب هذا المصطلح بشكل كبير. ربما سيتم اختراق RSA-2048 خلال حياتنا.
في الممارسة العملية ، توصي RSA باستخدام الحد الأدنى لحجم مفتاح RSA وهو 2048 أو 4096 بت.
انطلاقًا من تطوير أجهزة الكمبيوتر الكمومية ، فإنها لن تقترب قريبًا من كسر المفاتيح بهذا الحجم ، على الرغم من صعوبة التنبؤ بشيء هنا. في عام 2012 ، تعاملت
خوارزمية Shore مع
عامل 21 (3 × 7) ، خمسة أجزاء من الإنتروبيا. ظل هذا الرقم طويلًا وهو رقم قياسي للعوامل الكمومية ، ولكن في عام 2018 ، تم توضيح معامل إنتاج الأعداد الأولية
4088459 على معالجات IBM 5- و 16-bit ، والتي تبلغ بالفعل 22 بت.
