اعداد اول و سیستمهای رمز

در اکثر قریب به اتفاق الگوریتمهای رمز مدرن (متقارن و نامتقارن) بر خلاف سیستمهای رمز ساده (جانشینی و جایگشتی) از اعمال ریاضی فراتر از 4 عمل اصلی استفاده شده است. نقطه قوت و امنیت عملی این الگوریتمها دقیقاً ناشی از همین پیچیدگی محاسبات ریاضی لازم برای تحلیل کردن (شکستن) آنهاست. اساسی ترین عمل ریاضی در رمز های مدرن ، محاسبات پیمانه ای یا همنهشتی است. در اینجا هدف پرداختن به جزئیات عملیات همنهشتی (4 عمل اصلی در یک مبنای دلخواه مثل n) نیست، فقط مایلم به نقش کلیدی و استثنایی اعداد اول  در اینگونه محاسبات اشاره کنم. علم رمز مدرن بدون شک مدیون خواص بی مانند و جادویی اعداد اول است. در بسیاری از الگوریتمهای رمز مدرن از دیفی هلمن گرفته تا RSA ، Elgamal و ... از اعداد اول (و یا حاصلضرب چند عدد اول) به عنوان پیمانه محاسبات تولید کلید، رمز کردن و ترجمه رمز استفاده می­شود. همین خواص است که در کنار پیچیدگی مسایلی مثل لگاریتم گسسته، فاکتورگیری و ... امکان شکستن رمز را از تحلیل گر (که کلید را در اختیار ندارد) سلب می­کند. تولید اعداد اول بزرگ، بسیار مشکل است و در حالت کلی الگوریتمی برای آن وجود ندارد، اما از آن پیچیده تر، مساله فاکتورگیری است، یعنی تجزیه یک عدد بسیار بزرگ به حاصلضرب فاکتورهای اول. برای مثال، متن زیر تحت الگوریتم RSA با کلید عمومی e = 5 و عامل N (که حاصلضرب دو عدد اول مخفی است) رمز شده:

2436895187740522149300895060339985

9633578287983910705162536071404480

55114932771201027350325,32391566613

3187777174633743307665741495158513

5873876216674428451506590312184584

1724822236676

N = 51920810450204744019132202403246112

884629925425640897326550851544998255968235697331455544257

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