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

[آبجی]

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

24368951877405221493008950603399859633578287983910 70516253607140448055114932771201027350325,32391566 61331877771746337433076657414951585135873876216674 4284515065903121845841724822236676
N = 51920810450204744019132202403246112884629925425640 897326550851544998255968235697331455544257
کلید عمومی e و عامل N علنی و در اختیار تحلیل گر قرار دارد. با توجه به اینکه تحلیل گر کلید خصوصی را در اختیار ندارد، برای شکستن متن رمز شده باید N را فاکتورگیری کند، که این کار برای قدرتمندترین کامپیوترهای موجود هم در زمان مناسب عملاً غیر ممکن است. به همین خاطر است که RSA و بسیاری دیگر از الگوریتمها در برابر تحلیل مقاومند