متنوع

كيف تقضي خوارزمية بيتر شور على فشل تشفير RSA

كيف تقضي خوارزمية بيتر شور على فشل تشفير RSA

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

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

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

ذات صلة: ما الذي سيتغير الحوسبة الكمية بالضبط؟

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

كان يُعتقد أن تشفير RSA غير قابل للكسر

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

بالنسبة للكمبيوتر الكلاسيكي ، فإن ملف خوارزمية فعالة للعثور على العوامل الأولية من أ عدد مركب غير موجود ، مما يعني أن أفضل ما يمكننا فعله هو العثور على إجابة أقل فظاعة من الوقت الأسي. تشفير RSA عادة ما يكون مؤهلًا بطول قليل ، مثل 128 بت, 256 بت، وما إلى ذلك ، والذي يمثل طول البت للمفتاح المستخدم لتشفير البيانات وفك تشفيرها. لذا فإن خوارزمية القوة الغاشمة مع التعقيد الزمني الأسي العمل على مفتاح تشفير 128 بت سيحتاج إلى المحاولة 2128 القيم كحد أدنى.

هذا يساوي 340,282,366,920,938,463,463,374,607,431,768,211,456 المفاتيح المحتملة ومفاتيح تشفير RSA لم تكن صغيرة مثل 128 بت في أكثر من عقد. طول المفتاح القياسي الحالي الموصى به لمفتاح تشفير RSA هو 2048 بتالذي يساوي (340,282,366,920,938,463,463,374,607,431,768,211,456)16 مفاتيح ممكنة.

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

في العديد من البلدان التي تستخدم تنسيق 12 ساعة بدلا من ساعة بنظام 24 ساعة للحفاظ على الوقت ، يستخدمون الحساب المعياري طوال الوقت ، حرفيًا. إذا كان كذلك 11 ص وأطلب منك مقابلتي في أربع ساعات، أنت تعلم أنني أريد أن ألتقي في 3 مساءً. هذا لأننا نستخدم الرقم 12، ودعا معام، لمعرفة متى نبدأ العد من الصفر مرة أخرى. يستخدم الحساب النمطي هذه العملية نفسها ، فقط بأعداد كبيرة الحجم للمساعدة في إجراء الحسابات.

مثل أي نظام تبادل مفاتيح آخر ، تشفير RSA يستخدم أ المفتاح العمومي و أ مفتاح سري لتشفير البيانات وفك تشفيرها ، باستثناء ملفات تشفير RSA يستخدم رقمين كمفتاح عام له ، وهو الأس العام لاستخدامه في تشفير رسالة و معام لعملية التشفير التي تنتج التشفير. ما الذي يجعل هذا معام من المهم جدًا حقيقة أنه نتاج عددين أوليين كبيرين جدًا ومعرفة هؤلاء رقمين سيسمح لك بعكس هندسة مفتاح سري الذي يفتح التشفير.

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

كيف تتغلب أجهزة الكمبيوتر الكمومية وخوارزمية Shor على تشفير RSA

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

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

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

كيف بدأت خوارزمية بيتر شور وشور الحوسبة الكمية

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

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

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

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

المقال الخامس في سلسلتنا حول الخوارزميات والحساب ، الخوارزميات والتحسين ومشكلة البائع المتجول, يمكن العثور عليها هنا.


شاهد الفيديو: افجر برنامج لي سحب الارقام حرفيا هتسحب اي رقم انتا عاوزه (ديسمبر 2021).