دو عدد اول و تابع توتینت: رمزنگاری RSA چگونه کلیدهای عمومی و خصوصی را می‌سازد

در سال ۱۹۷۷، سه پژوهشگر در موسسه فناوری ماساچوست (MIT) — ران ریورست (Ron Rivest)، آدی شامیر (Adi Shamir) و لئونارد ادلمن (Leonard Adleman) — الگوریتم رمزنگاری‌ای را منتشر کردند که نحوه ایمن‌سازی اطلاعات دیجیتال را اساساً تغییر داد. سیستم آن‌ها که با نام RSA شناخته می‌شود، یک آسیب‌پذیری لجستیکی حیاتی در ارتباطات امن را حل کرد: اینکه چگونه دو طرف می‌توانند بدون اشتراک‌گذاری قبلی یک کلید مخفی، پیام‌های رمزنگاری‌شده را تبادل کنند. مکانیزمی که آن‌ها طراحی کردند کاملاً بر ویژگی‌های اعداد اول و یک فرمول ریاضی خاص به نام تابع توتینت اویلر (Euler's totient function) متکی است.[1]

امروزه، زمانی که یک مرورگر وب مدرن به یک سرور امن متصل می‌شود، به طور معمول بر همین عملیات ریاضی تکیه می‌کند. این پروتکل محاسباتی را روی اعدادی انجام می‌دهد که طول آن‌ها به ۲۰۴۸ بیت می‌رسد، که معادل حدود ۶۱۷ رقم اعشاری است. این اعداد عظیم به طور تصادفی انتخاب نمی‌شوند؛ اندازه بسیار بزرگ آن‌ها، مکانیسم دفاعی اصلی برای محافظت از تراکنش‌های مالی جهانی، ایمیل‌های امن و هویت‌های دیجیتال در برابر حملات محاسباتی جستجوی فراگیر (brute-force) است.[1]

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

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

برای تولید یک جفت کلید RSA، سیستم کار خود را با انتخاب دو عدد اول متمایز و بسیار بزرگ آغاز می‌کند که معمولاً با p و q نشان داده می‌شوند. این اعداد اول در هم ضرب می‌شوند تا یک عدد مرکب به نام N تولید کنند که به عنوان پیمانه (modulus) برای هر دو کلید عمومی و خصوصی عمل می‌کند. در حالی که ضرب p و q برای یک کامپیوتر مدرن کسری از میلی‌ثانیه طول می‌کشد، معکوس کردن این فرآیند — یعنی یافتن اعداد اولِ اولیه از حاصل‌ضرب N — برای اعداد به اندازه کافی بزرگ، از نظر محاسباتی غیرممکن است.[1]

این دشواری یک‌طرفه که به عنوان مسئله تجزیه اعداد صحیح شناخته می‌شود، دیوار دفاعی بیرونی رمزنگاری RSA را تشکیل می‌دهد. با این حال، صرفاً ضرب دو عدد اول در یکدیگر یک سیستم رمزنگاری کاربردی ایجاد نمی‌کند. این الگوریتم به یک ساختار ریاضی خاص نیاز دارد تا داده‌ها را با یک کلید قفل کرده و با کلید دیگر باز کند. سیستم به یک تله‌در (trapdoor) نیاز دارد — قطعه‌ای از اطلاعات پنهان که معکوس کردن تابع را برای صاحب کلید آسان، اما برای هر کس دیگری غیرممکن می‌سازد.[1]

اینجاست که تابع توتینت اویلر، که به صورت φ(N) نوشته می‌شود، تله‌درِ ریاضی لازم را فراهم می‌کند. این تابع که به نام ریاضیدان سوئیسی قرن هجدهم، لئونارد اویلر نام‌گذاری شده است، تعداد اعداد صحیح مثبتی تا سقف N را می‌شمارد که نسبت به N متباین (coprime) هستند. دو عدد زمانی متباین در نظر گرفته می‌شوند که هیچ مقسوم‌علیه مشترکی جز ۱ نداشته باشند. به عنوان مثال، اعداد ۸ و ۱۵ متباین هستند زیرا عوامل اول آن‌ها هم‌پوشانی ندارند، حتی اگر هیچ‌کدام از آن‌ها به تنهایی عدد اول نباشند.[2]

برای یک عدد اول p، محاسبه تابع توتینت به طرز شگفت‌آوری ساده است. از آنجا که یک عدد اول هیچ مقسوم‌علیهی جز ۱ و خودش ندارد، تک‌تک اعداد صحیح مثبتِ کوچکتر از p نسبت به آن متباین هستند. بنابراین، مقدار φ(p) همیشه دقیقاً برابر با p - ۱ است. این ویژگی بنیادین اعداد اول، موتوری است که کل الگوریتم RSA را به حرکت درمی‌آورد.[2]

تابع توتینت دارای یک ویژگی حیاتی دیگر نیز هست: این تابع برای اعداد متباین، ضرب‌پذیر است. این بدان معناست که اگر دو عدد اول متمایز p و q را در هم ضرب کنید، توتینتِ حاصل‌ضرب آن‌ها برابر با حاصل‌ضرب توتینت‌های فردی آن‌هاست. در نتیجه، مقدار φ(N) برای پیمانه RSA دقیقاً برابر با (p - ۱) × (q - ۱) است.[1][2]

این محاسبه خاص، پل پنهانی است که باعث کارکرد RSA می‌شود. اگر یک سیستم کامپیوتری اعداد اولِ اولیه p و q را بداند، محاسبه φ(N) تنها به یک تفریق و ضرب ساده نیاز دارد. با این حال، اگر یک مهاجم تنها پیمانه عمومی N را بداند، محاسبه φ(N) بدون تجزیه اولیه N به عوامل اول سازنده‌اش عملاً غیرممکن است. عبور از تابع توتینت در صورت در اختیار داشتن اعداد اول آسان است، اما اگر تنها حاصل‌ضرب آن‌ها را داشته باشید، نامرئی و غیرقابل عبور خواهد بود.[1][5]

با محاسبه φ(N)، سیستم یک توان عمومی به نام e را انتخاب می‌کند. این عدد باید بزرگتر از ۱، کوچکتر از φ(N) و کاملاً نسبت به φ(N) متباین باشد. در پیاده‌سازی‌های مدرن، عدد ۶۵۵۳۷ اغلب برای e انتخاب می‌شود زیرا یک عدد اول است که امکان محاسبات باینری بسیار کارآمد را فراهم می‌کند. سپس کلید عمومی به صورت جفت اعداد (N, e) برای همه منتشر می‌شود.[1]

برای ایجاد کلید رمزگشایی خصوصی، سیستم باید مقداری به نام d را بیابد به طوری که ضرب d در e، هنگام تقسیم بر φ(N)، باقیمانده ۱ را به دست دهد. در زبان حساب پیمانه‌ای، d وارون ضربی پیمانه‌ایِ e به پیمانه φ(N) است. از آنجا که محاسبه d اکیداً نیازمند دانستن φ(N) است، تنها طرفی که اعداد اولِ اولیه را تولید کرده می‌تواند کلید خصوصی را محاسبه کند.[1][2]

هنگامی که یک فرستنده می‌خواهد پیام امنی را ارسال کند، ابتدا متن ساده را به یک مقدار عددی M تبدیل می‌کند. سپس M را به توانِ توان عمومی e می‌رساند و نتیجه را بر پیمانه N تقسیم می‌کند تا باقیمانده را بیابد. این باقیمانده به متن رمزنگاری‌شده C تبدیل می‌شود که می‌تواند با خیال راحت در یک شبکه باز منتقل شود.[1]

برای رمزگشایی متن رمزنگاری‌شده، گیرنده دقیقاً همان عملیات ریاضی را انجام می‌دهد، اما از کلید خصوصی خود استفاده می‌کند. او متن رمزنگاری‌شده C را به توان d می‌رساند و بر N تقسیم می‌کند تا باقیمانده را بیابد. ریاضیات این الگوریتم تضمین می‌کند که این عملیات به طور کامل رمزنگاری را معکوس کرده و پیام اصلی M را بازمی‌گرداند.[1]

این تضمین بر قضیه اویلر استوار است، که تعمیمی از قضیه کوچک فرما (Fermat's little theorem) است و نحوه رفتار توان‌ها را در حساب پیمانه‌ای دیکته می‌کند. همان‌طور که جان دی. کوک (John D. Cook)، ریاضیدان و مشاور، در مورد نظریه اعدادِ زیربنایی این موضوع اشاره می‌کند، قضیه کوچک فرما — که برای اولین بار در سال ۱۶۴۰ بیان شد — «نسبتاً پیچیده، با اثباتی آسان و بسیار کاربردی» است و اساس حساب پیمانه‌ای را که RSA بر آن تکیه دارد، تشکیل می‌دهد. قضیه اویلر تضمین می‌کند که چون d و e با استفاده از φ(N) تولید شده‌اند، مراحل رمزنگاری و رمزگشایی کاملاً یکدیگر را خنثی می‌کنند.[3][4]

در حالی که ریاضیات نظری RSA بی‌نقص است، پیاده‌سازی عملی آن برای حفظ امنیت باید بدون ایراد باشد. اگر اعداد اولِ انتخاب‌شده بیش از حد به هم نزدیک باشند، یا اگر تولیدکننده اعداد تصادفیِ مورد استفاده برای انتخاب آن‌ها قابل پیش‌بینی باشد، مهاجمان می‌توانند کلیدها را بدون حل کامل مسئله تجزیه استنتاج کنند. سیستم‌های دنیای واقعی همچنین باید از طرح‌های پدینگ (padding) پیچیده استفاده کنند تا از دستکاری متن رمزنگاری‌شده توسط مهاجمان برای افشای پیام زیربنایی جلوگیری کنند.[1][5]

علاوه بر این، ظهور محاسبات کوانتومی یک تهدید قطعی و بلندمدت برای این الگوریتم به شمار می‌رود. در سال ۱۹۹۴، ریاضیدانی به نام پیتر شور (Peter Shor) یک الگوریتم کوانتومی را منتشر کرد که می‌توانست اعداد صحیح بزرگ را به طور تصاعدی سریع‌تر از هر روش کلاسیک شناخته‌شده‌ای تجزیه کند. یک کامپیوتر کوانتومی به اندازه کافی قدرتمند که الگوریتم شور را اجرا کند، به طور کامل از دشواری مسئله تجزیه عبور کرده و تله‌درِ توتینت را بی‌فایده می‌سازد.[1]

موسسه ملی استاندارد و فناوری (NIST) از قبل آماده‌سازی برای این احتمال را آغاز کرده است و در حال ترسیم یک گذار به استانداردهای رمزنگاری پسا-کوانتومی است که به تجزیه اعداد صحیح متکی نیستند. با این حال، تا زمانی که چنین ماشین‌های کوانتومی به صورت فیزیکی و در مقیاس وسیع ساخته شوند، رابطه ریاضی بین دو عدد اول و تابع توتینت اویلر همچنان به ایمن‌سازی پایه و اساس اقتصاد دیجیتال جهانی ادامه می‌دهد.[5]