برو به محتوای اصلی

الگوریتم RSA چیست و چه کاربردی دارد؟

ناشناس

من کجام؟ اینجا کجاست؟

در جواب‌کو می‌تونید در مورد هر موضوعی سوال کنید، به سوالای بقیه جواب بدید و تجربتون رو به اشتراک بگذارید!

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

در الگوریتم‌های کلید عمومی برای رمزنگاری و رمزگشایی از دو کلید کاملا متفاوت استفاده می‌شود: «کلید عمومی» و «کلید خصوصی».

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

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

در سال ۱۹۷۸ سه نفر به نام‌های ریوست، شامیر و اَدِلمن الگوریتمی را برای پیاده‌سازی رمزنگاری کلید عمومی با یک جفت کلید معرفی کردند که به RSA شهرت یافت و در طول سه دهه اخیر بطور گسترده‌ای مورد استفاده قرار گرفته و در گذر زمان، سخت‌افزار و نرم‌افزارهای بهینه آن به بازار عرضه شد. اگر چه بعدها الگوریتم قوی‌تری بنام El Gamal ابداع شد اما هنوز هم روش RSA در صدر فهرست الگوریتم‌های کلید عمومی قرار دارد.

فرض کنید فرستنده پیام جفت عدد صحیح و بزرگ (e,n) را بعنوان کلید عمومی برای رمزنگاری اطلاعات خود در اختیار دارد. در طرف مقابل، گیرنده نیز جفت عدد (d,n) را برای رمزگشایی پیام بکار می‌برد. بدیهی است که دو جفت عدد (e,n) و (d,n) با یکدیگر ارتباط زیرکانه‌ای دارند ولی بگونه‌ای نیست که بتوان با در اختیار داشتن e و n براحتی d را استنتاج کرد. با فرض وجود چنین کلید‌هایی، الگوریتم RSA در نهایت سادگی به صورت زیر است:

الف) پیامی که باید رمز شود به بلوک‌های K کاراکتری (k بایتی) تقسیم‌بندی می‌شود.

ب) هر بلوک طبق قاعده‌ای کاملا دلخواه به یک عدد صحیح به نام Pi تبدیل می‌گردد.

ج) با جفت عدد (e,n) به ازای یکایک بلوک‌های Pi اعداد جدیدی طبق رابطه زیر بدست می‌آیند:

Ci = (Pi)e mod n

د) کدهای Ci بجای کدهای اصلی Pi ارسال می‌شوند.

روش رمزگشایی داده‌ها دقیقا مثل روش رمزنگاری است یعنی با داشتن جفت عدد (d,n) بلوک‌های رمز شده بصورت زیر از رمز خارج می‌شوند:

Pi = (Ci)d mod n

کل الگوریتم در همینجا خاتمه می‌یابد.

در RSA، به جفت عدد (e,n) که متن به کمک آن رمز می‌شود، اصطلاحا کلید عمومی (public key) و به جفت عدد (d,n) که متن بوسیله آن از رمز در می‌آید، کلید خصوصی (private key) گفته می‌شود. نکته اساسی در RSA آن است که جهت تضمین وارون‌پذیری روش رمز، اعداد و بایستی در رابطه (x)e.d mod n = x صدق کنند لذا باید در انتخاب اعداد دقت کرد.

اصل اساسی دیگری که باید در رمزنگاری RSA حتما رعایت شود آن است که کدهای Pi که به هر بلوک نسبت می‌دهیم باید در شرط ۰ ≤ Pi< n صدق کند. بنابر این اگر بلوک‌ها بصورت رشته‌های k بیتی مدل شوند، باید شرط ۲K< n برقرار باشد. دلیل این امر آن است که براحتی بتوان گزاره Pi mod n = Pi را نوشت و الا در حالت کلی این گزاره درست نمی‌باشد و در این صورت رمزگشایی صحیح داده‌ها تضمین نخواهد شد.

روش انتخاب e و d که توسط ابداع‌کنندگان RSA پیشنهاد شده، عبارت است از:

الف) دو عدد دلخواه (اما بزرگ) p و q را انتخاب می‌شود.

ب) اعداد n و z را طبق دو رابطه زیر محاسبه می‌گردد:

n = p * q

(z = (p-۱) * (q-۱

ج) عدد d طوری انتخاب می‌شود که نسبت به z اول باشد یعنی هیچ عامل مشترکی که هر دو بر آن بخش‌پذیر باشند یافت نشود.

د) بر اساس d، عدد e طوری انتخاب می‌شود که رابطه زیر برقرار باشد: (بعبارتی معکوس ضربی d در پیمانه z محاسبه شده و e نامیده می‌شود)

 e * d) mod z = ۱)

آنچه که مشخص است در کاربردهای عملی، اعداد pو qحداقل صد رقمی (صد رقم در مبنای ده) انتخاب می‌شوند یعنی این دو عدد حداقل از مرتبه ۱۰۱۰۰ هستند. در این حالت عدد صحیح متناظر با بلوک‌های Pi که طبق شرط فوق باید کمتر از n باشند، نبایستی از ۸۳ کاراکتر بیشتر باشند، زیرا:

p, q ≈ ۱۰۱۰۰ → n = p * q ≈ ۱۰۲۰۰ → (Pi <(۲۶۶۴≈۱۰۲۰۰)) → Pi <۲۶۶۴

پس هر بلوک متن بایستی حداکثر ۶۶۴ بیت یا ۸۳ کاراکتر هشت بیتی باشد.

در اینجا توجه به این نکته ظریف لازم است که برای محاسبه Ae mod n لازم نیست که A به تعداد e بار در خودش ضرب و سپس باقیماده‌اش بر n پیدا شود زیرا با استفاده از برخی خواص ریاضی نتیجه محاسبات هیچگاه از n فراتر نمی‌رود.

حال فرض کنید یک نفر بخواهد با در اختیار داشتن کلید عمومی (e,n)، را بدست آورد. در اینصورت باید در وهله اول n را به دو عامل اول آن یعنی p و q تجزیه کند تا بتواند z را محاسبه کرده و سپس d را بدست آورد. برای تجزیه اعداد به عوامل اول آن هیچ راهی بجز جستجو و آزمون وجود ندارد و با توجه به این که n حداقل دویست رقمی است، تجزیه چنین اعدادی حتی به کمک کامپیوتر هزاران سال طول خواهد کشید.

اگر چه تحقیق بر روی مسئله تجزیه اعداد بزرگ به عوامل آن هنوز ادامه دارد اما هنوز الگوریتم کارآمدی که بتواند اعداد بزرگ را با هر طولی در زمان ثابت یا در حد متعارف کوچکی به عوامل اول آن تجزیه کند، یافت نشده است، لذا با گذشت ۳۰ سال از معرفی RSA هنوز از شان آن کاسته نشده است بلکه فقط کلیدها به جهت محکم کاری بزرگتر شده‌اند.

از آنجا که اعداد اول هیچ نظم شناخته شده‌ای ندارند لذا انتخاب اعداد اول بسیار بزرگ p و q یکی از چالش‌های بزرگ RSA است زیرا برای اثبات اول بودن عددی مثل p باید محدوده اعداد کمتر یا مساوی p √ بررسی و بخش‌ناپذیری p بر آنها مطالعه گردد که هرچه p بزرگتر باشد محدوده جستجوی p √ بزرگتر خواهد بود. برای مثال محدوده جستجوی عددی ۵۱۲ بیتی از مرتبه ۲۲۵۶ میشود که جستجوی چنین فضایی عملا غیر ممکن است. بنابر این تنها راه چاره استفاده از یکسری از قضایای ریاضی است که به ما کمک می‌کنند محدوده جستجو را کوچک‌تر نموده و مراحل حدس زدن کمتر شود.

۱