نکات فنی بیشتر درمورد RSA

در تاریخ فناوری ها و الگوریتم هایی هست که عمر زیادی دارن ولی هنوز هم جزو موارد مهم و اصلی هستن و جذاب و تحسین برانگیز. یکی از اونا مسلما RSA است!

البته قبلا درمورد RSA پست زده بودم اما امروز چندتا مقاله ویکیپدیا رو نگاه میکردم که به مطالب تکمیلی خوبی درشون برخوردم که اینجا درج میکنم.

یک عدد semiprime یا 2-almost prime یا pq number یا biprime، از ضرب دو عدد اول حاصل میشه. البته این تعریف شامل اعدادی که از ضرب یک عدد اول در خودش ایجاد میشن هم میشه.

Semiprime ها در الگوریتم RSA نقش اساسی دارن. البته همچنین در الگوریتم هایی مثل Blum Blum Shub (تولید کننده اعداد رندوم با کیفیت قابل استفاده در کاربردهای رمزنگاری) هم ازشون استفاده میشه.

البته Semiprime هایی که در RSA استفاده میشن باید خصوصیات خاصی داشته باشن، چون الگوریتم هایی وجود دارن که بعضی Semiprime ها در برابر اونا ضعیف هستن (میشه با سرعت کافی اونا رو به فاکتورهای اولشون تجزیه کرد).

فاکتور p و q در RSA باید هردو خیلی بزرگ باشن (تقریبا از درجهء توان ده (order of magnitude) ریشهء دوم n که عدد حاصل از ضرب اونهاست)، این باعث میشه trial division و الگوریتم Pollard’s rho رو نشه برای فاکتورگیری n استفاده کرد. از طرف دیگر p و q نباید خیلی هم به هم نزدیک باشن، وگرنه میشه با Fermat’s factorization method عدد حاصل رو به سرعت فاکتورگیری کرد. همچنین این اعداد باید طوری انتخاب بشن که هیچکدام از مقادیر p+1, p-1, q+1, q-1 یک عدد smooth نباشن تا در برابر الگوریتم Pollard’s p − 1 یا الگوریتم Williams’ p + 1 ایمن باشن.

در تئوری اعداد، فاکتورگیری عدد صحیح یعنی تجزیهء یک عدد مرکب به ضرب چند عدد صحیح کوچکتر. اگر این اعداد صحیح کوچکتر به اعداد اول محدود بشن، بهش prime factorization گفته میشه. وقتی اعداد خیلی بزرگ باشن، هیچ الگوریتم غیرکوانتمی با سرعت کافی برای فاکتورگیری این اعداد تاکنون کشف نشده.

در تلاشی بوسیلهء چندین محقق که در سال 2009 به پایان رسید تونستن یک عدد 232 رقمی (768 بیتی) را با استفاده از صدها کامپیوتر در زمان دو سال فاکتورگیری کنن. محققان برآورد کردن که فاکتورگیری یک کلید 1024 بیتی RSA حدود هزار برابر زمان بیشتری طلب میکنه (یعنی حدود دو هزار سال – البته با همون تعداد کامپیوتر و نه بیشتر).

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

الگوریتم RSA بر این اساس کار میکنه که تولید p و q با خصوصیات لازم و ضرب اونها در هم و تولید n با سرعت کافی امکان پذیر است، اما در مقابل تجزیهء n به p و q عملیات و زمان بسیار بسیار بیشتری رو طلب میکنه. عملی بودن الگوریتم RSA بر این عدم تقارن بنا شده.

پاسخ دهید

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

*

شما می‌توانید از این دستورات HTML استفاده کنید: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>