RSA

امنیت دیجیتال به سختی تجزیه اعداد بزرگ وابسته است. اثبات جدیدی میسر نبودن یک روش، برای شکستن رمزنگاری دیجیتال را نشان می‌دهد.

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

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

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

اگر پیام رمزشده RSA را که گیرنده موردنظر، شما نیستید دریافت کنید و از این رو کلید رمزنگاری برای بازگشایی پیام را نداشته باشید، باید هزاران سال با بهترین کامپیوتر ها صرف پیدا کردن عامل های اول عدد بسیار بزرگ کنید و با این وجود شاید نتوانید پیدا کنید!

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

گام اول: عددی را که می‌خواهید عامل های اول آن را پیدا کنید، انتخاب کنید. در اینجا برای یک مثال ساده اجازه دهید عدد 15 را انتخاب کنیم.

گام دوم: عدد 15 را به باینری تبدیل کنید: 1111

گام سوم: عبارت باینری را به چندجمله‌ای تبدیل کنید بصورتی که که اعداد باینری به ترتیب، ضرایب این چندجمله‌ای باشند:

توجه کنید که این چندجمله ای به ازای $$x = 2$$ برابر 15 می‌باشد؛ چون 2 پایه عبارات باینری است.

گام چهارم: چندجمله ای را تجزیه کنید:

گام پنجم: برای هر عامل قرار دهید x = 2 :

نتیجه: 5 و 3 عامل های عدد 15 هستند.

این روش برای پیداکردن عامل های اعداد کوچک مثل 15 که که با روش مستقیم بسیار ساده تر پیدا می‌شوند، پیچیده بنظر می‌آیند. ولی برای اعداد خیلی بزرگ (که تعداد رقم هایشان هزاران رقم یا بیشتر هستند) روش چندجمله ای مزیت قابل توجهی دارد.

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

آیا این بدین معناست که روش RSA با مشکل مواجه شده است؟! درحقیقت، نه. دلیل برای این سوال منجر به اثبات جدیدی درمورد چندجمله ها شده است.

ریاضیدانان Emmanuel Breuillard و Péter Varjú از دانشگاه کمبریج اثبات کرده اند که چندجمله ای هایی که ضرایب 0 و 1 آنها بیشتر می‌شود، شانس‌شان برای تجزیه شدن کمتر و کمتر می‌شود. و درصورتی که چندجمله ای تجزیه نشود، از آن نمی‌توان برای تشخیص دادن پایه های اول آن استفاده نمود.

اثبات Breuillard و Varjú بطور موثر درب پشتی برای شکستن RSA را درهم کوبید. اعداد بسیار بزرگ مورد استفاده در RSA منجر به چندجمله ای های بسیار بزرگ می‌شود که رابطه مستقیم نسبت بهم دارند. Breuillard و Varjú ثابت کردند که یافتن عامل های چندجمله‌ای ها با این طول تقریبا غیرممکن است. ریاضیدان ها و رمزنگاران به مدت طولانی مشکوک به این مورد بودند اما زمانی که امنیت سایبری در کل دنیا وابسته به برخی هک های ریاضی هست که کار نمی‌کنند، خوب است که اثباتی برای آن داشته باشیم که نمی‌شود.

0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *