کارشناس می‌گوید نابودی RSA از حملات کوانتومی بسیار اغراق‌آمیز است

سه هفته پیش، پس از اینکه محققان موفق به کشف پیشرفتی شدند که در نهایت، شکستن طرح رمزگذاری پرکاربرد RSA را با استفاده از محاسبات کوانتومی در دسترس قرار داد، وحشت در گوشه و کنار جهان امنیتی فرا گرفت.

دانشمندان و رمزنگاران دو دهه است که می‌دانند یک روش فاکتورسازی به نام الگوریتم Shor از لحاظ نظری این امکان را برای یک کامپیوتر کوانتومی با منابع کافی برای شکستن RSA فراهم می‌کند. به این دلیل که اعداد اول مخفی که امنیت کلید RSA را تامین می‌کنند، با استفاده از الگوریتم Shor به راحتی قابل محاسبه هستند. محاسبه اعداد اول یکسان با استفاده از محاسبات کلاسیک میلیاردها سال طول می کشد.

تنها چیزی که مانع از این سناریوی روز قیامت می شود، حجم عظیمی از منابع محاسباتی مورد نیاز الگوریتم Shor برای شکستن کلیدهای RSA با اندازه کافی است. برآورد فعلی این است که شکستن یک کلید RSA 1024 بیتی یا 2048 بیتی به یک کامپیوتر کوانتومی با منابع گسترده نیاز دارد. به طور خاص، این منابع حدود 20 میلیون کیوبیت هستند و حدود هشت ساعت از آن‌ها به صورت سوپرپوزیشن کار می‌کنند. (کیوبیت یک واحد پایه محاسبات کوانتومی است، مشابه بیت باینری در محاسبات کلاسیک. اما در حالی که یک بیت باینری کلاسیک می تواند تنها یک مقدار دودویی منفرد مانند 0 یا 1 را نشان دهد، یک کیوبیت با برهم نهی چندگانه ممکن نشان داده می شود. ایالت ها.)

این مقاله که سه هفته پیش توسط تیمی از محققان در چین منتشر شد، گزارش داد که یک روش فاکتورسازی پیدا کرده است که می‌تواند یک کلید RSA 2048 بیتی را با استفاده از یک سیستم کوانتومی تنها با 372 کیوبیت، زمانی که با هزاران مرحله عملیاتی کار می‌کند، بشکند. این یافته، اگر درست باشد، به این معنی است که سقوط رمزگذاری RSA به محاسبات کوانتومی می‌تواند خیلی زودتر از آنچه اکثر مردم تصور می‌کردند رخ دهد.

مرگ RSA بسیار اغراق آمیز است

در کنفرانس Enigma 2023 در سانتا کلارا، کالیفرنیا، در روز سه‌شنبه، دانشمند کامپیوتر و متخصص امنیت و حریم خصوصی سیمسون گارفینکل به محققان اطمینان داد که مرگ RSA بسیار اغراق‌آمیز است. او گفت که در حال حاضر، محاسبات کوانتومی کاربردهای عملی کمی دارد.

گارفینکل، نویسنده کتاب 2021 با کریس هوفناگل، می گوید: «در کوتاه مدت، کامپیوترهای کوانتومی برای یک چیز خوب هستند، و آن انتشار مقالات در مجلات معتبر است. قانون و سیاست برای عصر کوانتومی، به حضار گفت. دومین چیزی که آنها در آن به طور معقولی خوب هستند، اما ما نمی دانیم تا چه مدت دیگر، این است که آنها در دریافت بودجه به خوبی خوب هستند.

حتی زمانی که محاسبات کوانتومی به اندازه کافی برای ارائه برنامه های کاربردی پیشرفته پیشرفت می کند، برنامه ها احتمالاً برای شبیه سازی فیزیک و شیمی و انجام بهینه سازی های رایانه ای هستند که با محاسبات کلاسیک به خوبی کار نمی کنند. گارفینکل گفت که کمبود برنامه های کاربردی مفید در آینده قابل پیش بینی ممکن است “زمستان کوانتومی” را به همراه داشته باشد، شبیه به دورهای متعدد زمستان های هوش مصنوعی قبل از اینکه هوش مصنوعی در نهایت شروع به کار کند.

مشکل مقاله منتشر شده در اوایل این ماه اتکای آن به الگوریتم Shnorr بود (نباید با الگوریتم Shor اشتباه شود) که در سال 1994 توسعه یافت. رمزنگاری سازنده و تحلیل رمزی نویسندگانی که الگوریتم Schnorr را ابداع کردند، گفتند که این الگوریتم می‌تواند استفاده از روش بهینه‌سازی کوانتومی اکتشافی به نام QAOA را افزایش دهد.

در کوتاه‌مدت، تعدادی از محققین به نقص‌های مهلکی در الگوریتم Shnorr اشاره کردند که همه آن را از بین برده است. به طور خاص، منتقدان گفتند که هیچ مدرکی وجود ندارد که ادعای نویسندگان را در مورد دستیابی الگوریتم شنور به زمان چند جمله‌ای، برخلاف زمان نمایی که با الگوریتم‌های کلاسیک به دست می‌آورد، تأیید کند.

به نظر می‌رسید که مقاله تحقیقاتی سه هفته پیش از الگوریتم شور استفاده می‌کند. حتی زمانی که ظاهراً با استفاده از QAOA بهبود یافته است – چیزی که در حال حاضر هیچ پشتیبانی از آن وجود ندارد – این سوال وجود دارد که آیا عملکردی را افزایش می دهد یا خیر.

اسکات آرونسون، دانشمند کامپیوتر در دانشگاه تگزاس در آستین و مدیر دانشگاه تگزاس، می‌گوید: «در مجموع، این یکی از گمراه‌کننده‌ترین مقالات محاسباتی کوانتومی است که در 25 سال گذشته دیده‌ام، و … بسیاری را دیده‌ام. مرکز اطلاعات کوانتومی آن نوشت. با این اوصاف، این اولین باری نیست که با این ایده عجیب مواجه می شوم که سرعت کوانتومی نمایی برای فاکتورگیری اعداد صحیح، که ما از الگوریتم Shor می دانیم، باید به نحوی بر روی اکتشافی های بهینه سازی کوانتومی که هیچ کدام را تجسم نمی کنند، ساییده شود. از بینش واقعی الگوریتم شور، گویی با جادوی دلسوزانه.