رمزنگاری پس کوانتومی - الگوریتم جدید "در 60 دقیقه از بین رفت"

ما در مورد PQC نوشته‌ایم که مختصر آن است رمزنگاری پس کوانتومی، چندین بار قبلا

در صورتی که تمام هیجانات رسانه ای چند سال گذشته در مورد محاسبات کوانتومی را از دست داده اید…

... این (اگر ببخشید آنچه که برخی کارشناسان احتمالاً ساده سازی بیش از حد بی پروا را در نظر می گیرند) راهی برای ساخت دستگاه های محاسباتی است که می توانند ردیابی نتایج ممکن متعدد یک محاسبه در همان زمان

با دقت زیاد، و شاید کمی شانس، این بدان معنی است که شما می توانید برخی از انواع الگوریتم ها را در پاسخ درست بازنویسی کنید، یا حداقل به درستی تعداد زیادی از پاسخ های اشتباه را بدون امتحان و آزمایش هر نتیجه ممکن کنار بگذارید. یکی یکی.

با استفاده از یک دستگاه محاسباتی کوانتومی، دو افزایش سرعت رمزنگاری جالب امکان پذیر است، با این فرض که می‌توان دستگاهی مناسب و قدرتمند و قابل اعتماد ساخت:

• الگوریتم جستجوی کوانتومی گروور معمولاً، اگر می‌خواهید مجموعه‌ای از پاسخ‌ها را که به‌طور تصادفی مرتب شده‌اند را جستجو کنید تا ببینید پاسخ‌های شما در لیست است یا خیر، انتظار دارید در بدترین حالت، قبل از دریافت پاسخ قطعی، کل لیست را بررسی کنید. برای مثال، اگر می‌خواهید کلید رمزگشایی 128 بیتی AES را برای باز کردن یک سند پیدا کنید، باید فهرست همه کلیدهای ممکن را جستجو کنید. 000..001, ..2, ..3، و غیره، تا آخر FFF..FFF (16 بایت FF) برای اطمینان از تکمیل مشکل. به عبارت دیگر، برای امتحان هر 2 باید بودجه داشته باشید¹²⁸ کلیدهای ممکن قبل از یافتن کلید مناسب یا تعیین اینکه کلیدی وجود ندارد. با این حال، الگوریتم گروور، با توجه به یک کامپیوتر کوانتومی به اندازه کافی بزرگ و قدرتمند، ادعا می کند که می تواند همان شاهکار را با ریشه دوم از تلاش های معمول، بنابراین در تئوری، کد را تنها در 2 شکسته می کند⁶⁴ در عوض تلاش می کند.
• الگوریتم فاکتورسازی کوانتومی شور چندین الگوریتم رمزگذاری معاصر بر این واقعیت تکیه دارند که ضرب دو عدد اول بزرگ را می توان به سرعت انجام داد، در حالی که تقسیم محصول آنها به دو عددی که با آن شروع کردید به همان اندازه غیرممکن است. برای درک این موضوع، سعی کنید 59×87 را با استفاده از قلم و کاغذ ضرب کنید. ممکن است یک دقیقه یا بیشتر طول بکشد تا آن را بیرون بیاورید (5133 پاسخ است)، اما آنقدرها هم سخت نیست. حالا راه دیگری را امتحان کنید. مثلاً 4171 را به دو عامل آن تقسیم کنید. بسیار سخت تر! (43×97 است.) حال تصور کنید این کار را با عددی 600 رقمی انجام دهید. به زبان ساده، در تلاش برای تقسیم عدد 600 رقمی بر هر عدد اول 300 رقمی ممکن است تا زمانی که به جکپات دست پیدا کنید، یا متوجه شوید که پاسخی وجود ندارد، گیر کرده اید. الگوریتم Shor، با این حال، نوید حل این مشکل را با لگاریتم از تلاش معمول بنابراین فاکتورگیری تعداد 2048 رقم دودویی باید فقط دو برابر فاکتورگیری یک عدد 1024 بیتی طول بکشد، نه دوبرابر فاکتورگیری یک عدد 2047 بیتی، که نشان دهنده افزایش سرعت است.

مقابله با تهدید

تهدید ناشی از الگوریتم گروور را می توان به سادگی با افزایش اندازه اعدادی که استفاده می کنید با مربع کردن آنها مقابله کرد، که به معنای دو برابر کردن تعداد بیت ها در هش رمزنگاری یا کلید رمزگذاری متقارن شما است. (به عبارت دیگر، اگر فکر می کنید SHA-256 در حال حاضر خوب است، استفاده از SHA-512 به جای آن می تواند جایگزین مقاوم در برابر PQC باشد.)

اما الگوریتم Shor را نمی توان به این راحتی مقابله کرد.

یک کلید عمومی 2048 بیتی باید اندازه آن به صورت تصاعدی افزایش یابد، نه صرفاً با مربع کردن، به طوری که به جای یک کلید 2×2048 = 4096 بیت، یا به یک کلید جدید با اندازه غیرممکن 2 نیاز دارید.²⁰⁴⁸ بیت…

... یا باید یک نوع کاملاً جدید از سیستم رمزگذاری پس کوانتومی را که الگوریتم Shor در آن اعمال نمی شود، اتخاذ کنید.

خوب، سازمان استاندارد ایالات متحده NIST یک را اجرا کرده است "رقابت" PQC از اواخر سال 2017

این فرآیند برای همه باز بوده است، با استقبال همه شرکت‌کنندگان، همه الگوریتم‌ها به طور آشکار منتشر شده است، و بررسی عمومی نه تنها امکان پذیر است، بلکه فعالانه تشویق می شود:

فراخوان برای پیشنهادات [بسته شد 2017/11/30]. در نظر گرفته شده است که استانداردهای جدید رمزنگاری کلید عمومی، یک یا چند الگوریتم امضای دیجیتال، رمزگذاری کلید عمومی، و کلید عمومی را که در سرتاسر جهان در دسترس هستند و قادر به محافظت از اطلاعات حساس دولتی هستند را مشخص کند. در آینده قابل پیش‌بینی، از جمله پس از ظهور رایانه‌های کوانتومی.

پس از سه دور ارسال و بحث، NIST اعلام کرد، در تاریخ 2022/07/05، چهار الگوریتم را انتخاب کرد که آنها را "استاندارد" با تأثیر فوری در نظر گرفت، همه با نام‌های خوش‌صدا: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONو SPHINCS+.

اولی (CRYSTALS-KYBER) به عنوان چیزی که a نامیده می شود استفاده می شود مکانیسم توافق کلیدی (KEM)، که در آن دو انتهای یک کانال ارتباطی عمومی به طور ایمن یک کلید رمزگذاری خصوصی یک بار برای تبادل اطلاعات محرمانه یک جلسه ایجاد می کنند. (به زبان ساده: جاسوسان فقط کلم خرد شده می گیرند، بنابراین نمی توانند مکالمه را استراق سمع کنند..)

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

الگوریتم های بیشتری مورد نیاز است

همزمان با اعلام استانداردهای جدید، NIST نیز اعلام کرد دور چهارم در رقابت خود، چهار الگوریتم دیگر را به عنوان KEMهای جایگزین ممکن معرفی می کند. (به یاد داشته باشید که در زمان نگارش، ما در حال حاضر سه الگوریتم امضای دیجیتال تایید شده برای انتخاب داریم، اما فقط یک KEM رسمی.)

این ها بودند: BIKE, Classic McEliece, HQC و SIKE.

به طرز جالب توجهی ، الگوریتم McEliece در دهه 1970 توسط رمزنگار آمریکایی رابرت مک الیس اختراع شد که در سال 2019 درگذشت، درست پس از شروع مسابقه NIST.

با این حال، هرگز مورد توجه قرار نگرفت، زیرا در مقایسه با جایگزین محبوب روز، الگوریتم Diffie-Hellman-Merkle (DHM، یا گاهی اوقات فقط DH) به مقادیر زیادی از مواد کلیدی نیاز داشت.

متاسفانه یکی از سه الگوریتم دور چهار، یعنی SIKE، به نظر می رسد کرک شده است.

در مقاله ای با عنوان پیچش مغزی یک حمله بازیابی کلید کارآمد به SIDH (نسخه اولیه)به نظر می رسد رمزنگاران بلژیکی ووتر کاستریک و توماس دکرو ضربه مهلکی به الگوریتم SIKE وارد کرده اند.

اگر تعجب می کنید، SIKE کوتاه شده است کپسوله سازی کلید ایزوژنی فوق منفردو SIDH مخفف آن است ایزوژنی فوق مفرد دیفی-هلمن، استفاده خاص از الگوریتم SIKE به موجب آن دو انتهای یک کانال ارتباطی یک "کریپتودانس" مانند DHM را برای مبادله دسته ای از داده های عمومی انجام می دهند که به هر انتهایی اجازه می دهد تا یک مقدار خصوصی را برای استفاده به عنوان یک کلید رمزگذاری مخفی یکبار مصرف استخراج کند.

ما قصد نداریم در اینجا حمله را توضیح دهیم. ما فقط آنچه را که مقاله ادعا می کند تکرار می کنیم، یعنی اینکه:

به بیان بسیار ضعیف، ورودی‌ها در اینجا شامل داده‌های عمومی ارائه‌شده توسط یکی از شرکت‌کنندگان در رمزنگاری تاسیسات کلیدی، همراه با پارامترهای از پیش تعیین‌شده (و در نتیجه شناخته‌شده عمومی) مورد استفاده در فرآیند می‌شوند.

اما خروجی استخراج شده (اطلاعاتی که به عنوان ایزوژن φ در بالا) قرار است بخشی از فرآیند باشد که هرگز فاش نشده است - به اصطلاح کلید خصوصی.

به عبارت دیگر، تنها از طریق اطلاعات عمومی، مانند داده‌هایی که آشکارا در حین تنظیم کلید رد و بدل می‌شوند، رمزنگاران ادعا می‌کنند که می‌توانند کلید خصوصی یکی از شرکت‌کنندگان را بازیابی کنند.

و هنگامی که کلید خصوصی من را بشناسید، می توانید به راحتی و به طور غیرقابل شناسایی وانمود کنید که من هستم، بنابراین فرآیند رمزگذاری شکسته می شود.

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

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

چه کاری انجام دهید؟

هیچ چی!

(این خبر خوب است.)

همانطور که نویسندگان مقاله پیشنهاد می کنند، پس از اشاره به اینکه نتیجه آنها هنوز مقدماتی است، "با وضعیت فعلی، به نظر می رسد SIDH برای هر منحنی پایه تولید شده عمومی کاملاً شکسته شده است."

(این خبر بد است.)

با این حال، با توجه به اینکه الگوریتم SIKE هنوز به طور رسمی تأیید نشده است، اکنون می توان آن را برای خنثی کردن این حمله خاص (چیزی که نویسندگان اذعان دارند ممکن است) سازگار کرد یا به سادگی حذف شد.

هر اتفاقی که در نهایت برای SIKE بیفتد، این یادآوری عالی است که چرا تلاش برای اختراع الگوریتم‌های رمزگذاری خود مملو از خطر است.

این همچنین یک مثال برجسته از چرایی سیستم های رمزگذاری اختصاصی است که بر محرمانه بودن خود الگوریتم تکیه دارند حفظ امنیت آنها در سال 2022 به سادگی غیرقابل قبول است.

اگر یک الگوریتم PQC مانند SIKE به مدت بیش از پنج سال توسط متخصصان سراسر جهان از کاوشگری و کاوشگری جان سالم به در برد، علیرغم اینکه به طور خاص افشا شده بود تا بتوان آن را در معرض بررسی عمومی قرار داد…

... پس نیازی نیست از خود بپرسید که الگوریتم‌های رمزگذاری پنهان و مخفی خانگی شما در صورت انتشار در طبیعت چقدر خوب عمل می‌کنند!

---