الگوریتم RSA چیست؟ – به زبان ساده

RSA مهم‌ترین الگوریتم «رمزگذاری/رمزگشایی» (Encryption/Decryption) است. تکنیک‌های رمزگذاری و رمزگشایی در این الگوریتم با کمک کلید‌های عمومی و خصوصی پیاده‌سازی می‌شوند. در واقع الگوریتم RSA یکی از سیستم‌های «رمزنگاری کلید عمومی» (Public-Key Encryption) است. بخش عمده‌ای از نظریه سیستم‌های رمز کلید عمومی بر روی نظریه اعداد استوار است. در نتیجه برای درک عمیق‌تر و کامل‌تر الگوریتم‌های کلید عمومی به خصوص الگوریتم RSA چیست، به آشنایی با نظریه اعداد نیاز داریم. البته بدون تسلط بر روی این مبحث ریاضی هم می‌توانیم روش کار الگوریتم RSA را قبول کرده و با کمک کتابخانه‌های از پیش تعریف شده آن را پیاده‌سازی بکنیم.

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

الگوریتم RSA چیست؟

الگوریتم RSA در سال ۱۹۷۸ معرفی شد. هدف از طراحی این تکنیک رمزنگاری آن بود که تمام استانداردهای سیستم‌های کلید عمومی را پوشش بدهد. این الگوریتم توسط سه دانشمند با نام‌های «ران ریوسـت» (Ron Rivest)، «آدی شامیر» (Adi Shamir) و «لن ادلمن» (Len Adleman) در MIT توسعه داده شده است. نام این الگوریتم هم سرنامی از اسامی این دانشمندان است و به صورت (Rivest-Shamir-Adleman | RSA) نوشته می‌شود.

از زمان معرفی RSA تا الان این الگوریتم به‌عنوان پذیرفته شده‌ترین و پرکاربردترین روش عمومی برای رمزنگاری با کلید عمومی شناخته می‌شود.

روش کار الگوریتم RSA چیست؟

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

RSA ابتدا پیام را به بخش‌های کوچک‌تری به نام بلوک‌ تقسیم کرده و سپس این بلوک‌ها را رمزگذاری می‌کند. اندازه هر بلوک باید طوری باشد که مقدار دودویی هر کدام از آن‌ها کمتر از عدد $$n$$ بشود. به بیان دیگر، اندازه بلوک باید کمتر یا مساوی $$‎\log_2(n) + 1$$ باشد. در عمل، اندازه بلوک برابر $$i$$ بیت است، به شرطی که $$2^i \le n < 2^{i+1}$$ باشد.

عملیات رمزگذاری و رمزگشایی برای بلوک پیام $$M$$ و بلوک متن رمز $$C$$ به صورت زیر است:

$$C = M^e \mod n$$

$$M = C^d \mod n = (M^e)^d \mod n = M^{ed} \mod n$$

فرستنده و گیرنده هر دو باید مقدار $$n$$ را بدانند. فرستنده مقدار $$e$$ را می‌داند و تنها گیرنده مقدار $$d$$ را در اختیار دارد. بنابراین این الگوریتم از نوع الگوریتم‌های رمزنگاری کلید عمومی است. در این الگوریتم، کلید عمومی آن $$PU = \{e, n\}$$ و کلید خصوصی آن $$PR = \{d, n\}$$ است.

برای عملیاتی شدن الگوریتم RSA برای رمزنگاری با کلید عمومی باید شرایط زیر برقرار باشند.

1. امکان یافتن مقادیر $$e$$ و $$d$$ و $$n$$ وجود داشته باشد به‌گونه‌ای که عبارت $$M^{ed} \mod n = M$$ برای همه $$M$$-های کوچک‌‌تر از $$n$$ برقرار باشد.
2. محاسبه $$M^e \mod n‎$$ و $$‎C^d \mod n$$ برای تمام مقادیر $$M < n$$ نسبتا آسان باشد.
3. تعیین $$d$$ از روی $$e$$ و $$n$$ در دنیای واقعی، غیرممکن (دشوار از نظر محاسباتی) باشد.

ابتدا بر نخستین شرط تمرکز می‌کنیم. باید رابطه‌ای از شکل زیر بیابیم:

$$M^{ed} \mod n = M$$

این رابطه در صورتی برقرار است که $$e$$ و $$d$$ نسبت به پیمانه $$\phi(n)$$، «وارون‌های ضربی» (Multiplicative Inverses) همدیگر باشند.

نکته: وارون ضربی یعنی وقتی آن‌ها را در هم ضرب کنیم و سپس حاصل را بر عدد دیگری به نام $$\phi(n)$$ تقسیم کنیم، باقی‌مانده ۱ شود. البته به شرطی که $$\phi(n)$$ تابع «توتیان اویلر» (Euler totient function) باشد. در تابع توتیان اویلر برای دو عدد اول $$p$$ و $$q$$، عبارت $$‎f(pq) = (p − 1)(q − 1)$$ برقرار است.

رابطه میان $$e$$ و $$d$$ را می‌توان به صورت زیر نوشت:

$$e × d \mod \phi(n) = 1$$

این رابطه معادل با عبارت‌های زیر است:

$$e × d \equiv 1 \pmod{\phi(n)}$$

$$d \equiv e^{-1} \pmod{\phi(n)}$$

در واقع می‌توان گفت که $$e$$ و $$d$$ وارون‌های ضربی یکدیگر نسبت به پیمانه $$\phi(n)$$ هستند. توجه کنید که بر اساس قوانین «ریاضیات پیمانه‌ای» یا «ریاضیات ماژولار» (Modular Arithmetic)، این رابطه تنها در صورتی برقرار است که $$d$$ (و در نتیجه $$e$$) نسبت به $$\phi(n)$$ تا حدودی اول باشند، یعنی $$‎gcd(\phi(n), d) = 1‎$$.

نکته: تابع $$‎gcd(x,y)$$ برای محاسبه بزرگترین مقسوم‌علیه مشترک $$x$$ و $$y$$ به کار برده می‌شود. اگر بزرگترین مقسوم‌علیه مشترک دو عدد مجزا از هم برابر با ۱ باشد یعنی این دو عدد نسبت به هم اول هستند.

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

• $$‎p$$ و $$q‎$$: دو عدد اول (محرمانه بوده و از قبل انتخاب شده‌اند.)
• $$‎n = p·q‎$$: کلید عمومی (محاسبه شده است.)
• $$‎e$$: عددی که شرایط $$‎gcd(\phi(n), e) = 1‎$$ و $$‎1 ≤ e ≤ \phi(n)‎$$ را داشته باشد(عمومی بوده و از قبل انتخاب شده است).
• $$d \equiv e^{-1} \pmod{\phi(n)}$$: کلید خصوصی (محاسبه شده است.)

کلید خصوصی از $$PR = \{d, n\}$$ و کلید عمومی از $$PU = \{e, n\}$$ تشکیل می‌شود. فرض کنید کاربر A کلید عمومی خود را منتشر کرده است و کاربر B می‌خواهد پیام M را برای A بفرستد. در این صورت، B مقدار $$‎C = M^e \mod n$$ را محاسبه کرده و $$C$$ را ارسال می‌کند. با دریافت این متن رمز، کاربر A با محاسبه $$M = C^d \mod n$$ آن را رمزگشایی می‌کند.

مثالی از عملکرد الگوریتم RSA

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

مثال اول

مراحل رمزگذاری و رمزگشایی پیام را می‌توانیم به صورت مثال ساده زیر بیان کنیم.

1. آلیس جفت کلید «عمومی/خصوصی» خود را تولید می‌کند.
2. باب با استفاده از کلید عمومی آلیس پیام را رمزگذاری می‌کند.
3. سپس آلیس با استفاده از کلید خصوصی خود، متن رمز شده را رمزگشایی می‌کند.

برای این مثال، کلیدها به صورت زیر تولید شده‌اند:

1. دو عدد اول مانند $$‎p = 17‎$$ و $$‎q = 11‎$$ انتخاب کنید.
2. $$‎n = p·q = 17 × 11 = 187‎$$ را محاسبه کنید.
3. $$‎\phi(n) = (p - 1)(q - 1) = 16 × 10 = 160‎$$ را محاسبه کنید.
4. $$e$$ را چنان انتخاب کنید که نسبت به $$‎\phi(n) = 160‎$$ اول بوده و از $$\phi(n)$$ کوچک‌تر باشد. در این مثال $$‎e = 7‎$$ را انتخاب می‌کنیم.
5. $$d$$ را طوری بیابید که $$d × e \equiv 1 \pmod{160}‎$$ و $$‎d < 160‎$$ باشد. مقدار درست $$‎d = 23‎$$ است، زیرا $$23 × 7 = 161 = (1 × 160) + 1‎$$. بنابراین $$d$$ را می‌توان با استفاده از الگوریتم تعمیم‌یافته اقلیدس محاسبه کرد.

کلیدهای بدست آمده از مثال بالا به صورت زیر هستند.

• کلید عمومی: $$PU=\{7,187\}$$
• کلید خصوصی: $$PR=\{23,187\}$$

مثال دوم

در مثال پایین، استفاده از این کلیدها را برای ورودی متن ساده $$M=88$$ نشان می‌دهیم. برای رمزگذاری پیام، باید فرمول $$C = 88^7 \mod 187$$ را محاسبه کنیم. با استفاده از ویژگی‌های «حساب پیمانه‌ای» (Modular Arithmetic)، می‌توانیم این محاسبه را به صورت زیر انجام دهیم:

$$88^7 \mod 187 = [(88^4 \mod 187) × (88^2 \mod 187) × (88^1 \mod 187)] \mod 187$$

$$88^1 \mod 187 = 88$$

$$88^2 \mod 187 = 7744 \mod 187 77$$

$$88^4 \mod 187=59,969,536 \mod 187=132$$

بنابراین:

$$88^1 \mod 187 = (88 × 77 × 132) \mod 187= 894,432 \mod 187= 11$$

برای رمزگشایی باید مقدار $$M = 11^{23} \mod 187$$ را محاسبه کنیم.

$$11^{23} \mod 187 = [(11^1 \mod 187) × (11^2 \mod 187) × (11^4 \mod 187) × (11^8 \mod 187) × (11^8 \mod 187)] \mod 187$$

بنابراین:

$$11^1 \mod 187= 11$$

$$11^2 \mod 187=121$$

$$11^4 \mod 187=14,641 \mod 187=55$$

$$11^8 \mod 187=214,358,881 \mod 187=33$$

$$11^{23} \mod 187 = (11 × 121 × 55 × 33 × 33) \mod 187 = 79720245 \mod 187 = 88$$

مثال سوم

اکنون به مثال دیگری می‌پردازیم که روش استفاده از الگوریتم RSA برای پردازش بلوک‌های داده چندگانه را نشان می‌دهد. در این مثال پیش پا‌ افتاده، متن ساده‌ای (رشته الفبایی-عددی) را رمزنگاری می‌کنیم. به هر نماد در متن، کد منحصربه‌فرد دو رقمی تخصیص داده می‌شود. برای مثال $$a = 00$$ و $$A = 26$$ قرار می‌گیرند. هر بلوک متن ساده از چهار رقم ده‌دهی، یا دو کاراکتر الفبایی-عددی تشکیل شده است.

ابتدا تمام مراحل تولید کلید توسط آلیس را مرور می‌کنیم.

1. آلیس اعداد اول $$p$$ و $$q$$ را انتخاب می‌کند $$(p ≠ q)$$.
2. سپس $$‎n = p × q‎$$ را محاسبه می‌کند.
3. فرمول $$‎\phi(n) = (p - 1)(q - 1)‎$$ را محاسبه می‌کند.
4. عدد صحیح $$e$$ را طوری انتخاب می‌کند که $$‎gcd(\phi(n), e) = 1‎$$ و $$‎1 ≤ e ≤ \phi(n)‎$$ باشد.
5. $$‎d‎$$ را طوری محاسبه می‌کند که ‎$$d \equiv e^{-1} \pmod{\phi(n)}$$.
6. کلید عمومی $$‎PU = \{e, n\}‎$$
7. کلید خصوصی $$‎PR = \{d, n\}‎$$

اکنون نوبت به بررسی مراحل رمزگذاری پیام توسط باب با کلید عمومی آلیس است.

1. متن ساده با این شرط داده شده است که $$‎M < n‎$$ باشد.
2. باب، متن رمز را با فرمول $$‎C = M^e \mod n$$ بدست می‌آورد.

مراحل رمزگشایی توسط آلیس با کلید خصوصی خودش به شکل زیر است.

1. متن رمز برابر با $$C$$ است.
2. آلیس، متن ساده یا پیام را با فرمول $$‎M = C^d \mod n$$ بدست می‌آورد.

چطور با کمک فرادرس امنیت سایبری را یاد بگیریم؟

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

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

در پایین چند مورد از فیلم‌های مجموعه آموزش امنیت شبکه را معرفی کرده‌ایم. برای مشاهده فیلم‌های بیشتر بر روی تصویر بالا کلیک کنید.

• فیلم آموزش حملات DoS و DDoS در شبکه مجازی، از شناسایی تا روش‌های مقابله + گواهینامه
• فیلم آموزش رایانش امن از مبانی تا پیاده سازی امنیت با ۴ روش مختلف + گواهینامه
• فیلم آموزش ساخت برنامه طبقه‌ بندی‌ کننده فایل‌ های مشکوک در پایتون همراه با تحلیل بدافزار و امنیت + گواهینامه
• فیلم آموزش «سیسکو آیس» (Cisco ISE) برای امنیت شبکه های کامپیوتری + گواهینامه
• فیلم آموزش امنیت اطلاعات و رمزنگاری + گواهینامه

در بخش بعدی انواع روش‌های حمله برای رمزگشایی متن‌های رمزی تولید شده با الگوریتم RSA را توضیح داده‌ایم.

بیشترین حمله به الگوریتم RSA چیست؟

پنج روش مختلف برای حمله به الگوریتم RSA وجود دارد. این روش‌ها را در فهرست پایین معرفی کرده‌ایم.

• حمله «جستجوی فراگیر» (Brute Force): در این روش تمام کلیدهای خصوصی ممکن باید امتحان بشوند.
• حملات ریاضی: رویکردهای متنوعی برای این نوع حمله وجود دارد. همه آن‌ها از نظر محاسباتی معادل تجزیه حاصل ضرب دو عدد اول هستند.
• «حملات زمان‌بندی» (Timing Attacks): این حملات به زمان اجرای الگوریتم رمزگشایی بستگی دارند.
• «حمله مبتنی بر خطای سخت‌افزاری» (Hardware Fault-Based Attack): این حمله شامل ایجاد خطا در پردازنده‌ای است که امضای دیجیتال را تولید می‌کند.
• «حملات مبتنی بر متن رمز منتخب» (Chosen Ciphertext Attacks): این نوع حمله از ویژگی‌های الگوریتم RSA سوءاستفاده می‌کند.

در ادامه مطلب تمام حملات بالا و روش پیش‌گیری از آن‌ها را یک به یک بررسی می‌کنیم.

حمله Brute Force

دفاع در برابر حمله بروت فورس برای RSA همانند سایر سیستم‌های رمزنگاری است. یعنی باید از فضای کلید بزرگی استفاده کنیم. بنابراین، هرچه تعداد بیت‌ها در $$‎d$$ بیشتر باشد، بهتر است. با این حال می‌دانیم که محاسبات مورد استفاده برای تولید کلید و همچنین محاسبات رمزگذاری و رمزگشایی پیچیده هستند. بنابراین هرچه اندازه کلید بزرگتر باشد، سیستم کندتر عمل خواهد کرد.

در بخش بعد، رویکرد حملات ریاضی و روش پیش‌گیری از آن‌ها را بررسی می‌کنیم.

روش حملات ریاضی به الگوریتم RSA چیست؟

ما می‌توانیم سه رویکرد برای حمله ریاضی به RSA شناسایی کنیم.

1. تجزیه n به دو عامل اول تشکیل‌دهنده آن: این کار محاسبه فرمول $$\phi(n)=(p−1)×(q−1)$$ را امکان‌پذیر می‌سازد. در نتیجه می‌توانیم عبارت $$d \equiv e^{-1} \pmod{\phi(n)}$$ را نیز محاسبه کنیم.
2. تعیین مستقیم $$\phi(n)$$ بدون نیاز به تعیین $$p$$ و $$q$$: با انجام این کار می‌توانیم فرمول $$d \equiv e^{-1} \pmod{\phi(n)}$$ را محاسبه کنیم.
3. تعیین مستقیم $$d$$ بدون نیاز به تعیین $$\phi(n)$$

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

تجزیه $$n$$ به دو عامل اول تشکیل‌دهنده آن

بیشترین روش انجام حملات ریاضی برای رمزگشایی RSA بر روی عملیات تجزیه $$n$$ به دو عامل اول آن تمرکز کرده‌اند. تعیین $$\phi(n)$$ با داشتن $$n$$ معادل تجزیه $$n$$ است. با الگوریتم‌های شناخته‌شده فعلی، تعیین $$‎d$$ با داشتن $$‎e$$ و $$n$$ حداقل به اندازه مسئله تجزیه زمان‌بر به نظر می‌رسد. بنابراین، می‌توانیم از عملکرد تجزیه به عنوان معیاری برای ارزیابی امنیت RSA استفاده کنیم. تجزیه $$n$$ بزرگ با عوامل اول بزرگ، عملیات دشوار و زمان‌بری است، اما به سختی گذشته نیست. نمونه جالبی از این موضوع را در پایین نوشته‌ایم.

در سال ۱۹۷۷، سه مخترع RSA، خوانندگان مجله «Scientific American» را به چالش کشیدند تا رمزی را رمزگشایی کنند که در ستون «بازی‌های ریاضی» مارتین گاردنر منتشر کرده بودند. آن‌ها برای بازگرداندن یک جمله متن ساده، ۱۰۰ دلار جایزه تعیین کردند. در ضمن پیش‌بینی کردند که این اتفاق شاید حدود ۴۰ کوادریلیون سال طول بکشد. در آوریل ۱۹۹۴، گروهی که از طریق اینترنت همکاری می‌کردند، تنها پس از هشت ماه تلاش، جایزه را دریافت کردند.

این چالش از کلید عمومی به اندازه ۱۲۹ رقم اعشار یا حدود ۴۲۸ بیت (طول $$n$$)، استفاده می‌کرد. آزمایشگاه‌های RSA چالش‌هایی با اندازه کلیدهای ۱۰۰، ۱۱۰، ۱۲۰ و ارقام بیشتر منتشر کردند. آخرین چالشی که با موفقیت حل شد، مسئله «RSA-768» بود. در این مسئله طول کلید ۲۳۲ رقم اعشار، یا ۷۶۸ بیت است.

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

الگوریتم‌های تجزیه $$n$$

نکته قابل توجه در مورد تجزیه چالش‌های متوالی، روش به کار‌ رفته است. تا اواسط دهه ۱۹۹۰، حملات تجزیه با استفاده از رویکردی معروف به «غربال درجه دوم» (Quadratic Sieve) انجام می‌شد. حمله به «RSA-130» از الگوریتم جدیدتری به نام «غربال میدان عددی عمومی» (GNFS) استفاده کرد و توانست عددی بزرگ‌تر از «RSA-129» را تنها با ۲۰ درصد از توان محاسباتی قبلی تجزیه کند.

برای کلیدهای با اندازه بزرگ‌تر، دو نوع تهدید وجود دارد.

• اول اینکه توان محاسباتی دستگاه‌های کامپیوتری به طور مدام در حال افزایش است.
• دوم هم اینکه الگوریتم‌های به کار برده شده برای تجزیه اعداد به طور دائم بهتر و کارآمد‌تر می‌شوند.

مشاهده کرده‌ایم که استفاده از الگوریتم‌های متفاوت، باعث افزایش چشمگیر سرعت می‌شود. بنابراین می‌توان انتظار بهبودهای بیشتری را در الگوریتم «غربال میدان عددی عمومی» (Generalized Number Field Sieve | GNFS) داشت. حتی امکان ظهور الگوریتم‌های بهتر نیز وجود دارد. در واقع، الگوریتم مرتبط با نام «غربال میدان عددی ویژه» (Special Number Field Sieve | SNFS) می‌تواند اعداد دارای ساختار خاص را حتی سریع‌تر از «غربال میدان عددی عمومی» تجزیه کند. بنابراین، منطقی است که انتظار پیشرفت‌های بزرگی را در این زمینه داشته باشیم. الگوریتم‌هایی که سرعت تجزیه عمومی را به سطح SNFS یا حتی بهتر از آن برسانند.

بنابراین، باید در انتخاب اندازه کلید برای RSA دقت کنیم. تیمی که تجزیه ۷۶۸ بیتی را انجام داد اعلام کردند که تجزیه پیمانه ‍۱۰۲۴-بیتی RSA حدود هزار برابر سخت‌تر از تجزیه پیمانه ۷۶۸-بیتی است. به همین ترتیب تجزیه پیمانه ۷۶۸-بیتی RSA چندین هزار برابر سخت‌تر از یک پیمانه ۵۱۲-بیتی است. بر اساس فاصله زمانی میان موفقیت در تجزیه کلید‌های ۵۱۲-بیتی و ۷۶۸-بیتی، این تیم پیش‌بینی کرد که کلیدهای ۱۰۲۴ بیتی RSA نیز به احتمال زیاد در طول دهه آینده، توسط جامعه دانشگاهی با تلاش مشابهی تجزیه خواهند شد. از این رو، توصیه کردند که استفاده از کلید‌های ۱۰۲۴-بیتی RSA ظرف چند سال آینده (یعنی از سال ۲۰۱۰ به بعد) کنار گذاشته شود.

حفظ امنیت با اندازه کلید

در این بخش از مطلب، چند توصیه درباره حفظ امنیت با رعایت صحیح اندازه کلید‌ها در RSA را ارائه داده‌ایم.

• NIST SP 800-131A: توصیه می‌کند که از کلیدهایی با طول ۲۰۴۸ بیت یا بیشتر استفاده کنیم.
• آژانس امنیت شبکه و اطلاعات اتحادیه اروپا: در گزارش «الگوریتم‌ها، اندازه کلید و پارامترها» مربوط به سال ۲۰۱۴، توصیه کرده است که برای تمام توسعه‌های جدید از کلید‌هایی با طول ۳۰۷۲ بیت یا بیشتر استفاده کنیم.
• مرکز ارتباطات امنیتی دولت کانادا: در آگوست ۲۰۱۶ توصیه کرده است که در الگوریتم‌های رمزنگاری برای اطلاعات طبقه‌بندی نشده، حفاظت شده سطح A و حفاظت شده سطح B کلید‌هایی با طول حداقل ۲۰۴۸ بیت را به کار ببریم. طول این کلید‌ها باید تا سال ۲۰۳۰ در کمترین حالت به ۳۰۷۲ بیت افزایش بی‌یابد.

علاوه بر تعیین اندازه $$n$$، محدودیت‌های دیگری نیز توسط محققان پیشنهاد شده است. به منظور جلوگیری از تخصیص مقادیر کم به $$n$$ (که ممکن است راحت‌تر تجزیه شوند)، مخترعان الگوریتم، محدودیت‌های زیر را برای $$p$$ و $$q$$ پیشنهاد داده‌اند.

1. طول $$p$$ و $$q$$ تنها چند رقم تفاوت داشته باشد. بنابراین، برای کلید ۱۰۲۴ بیتی با ۳۰۹ رقم اعشار، باید هر دو $$p$$ و $$q$$ در حدود ۱۰۷۵ تا ۱۰۱۰۰ باشند.
2. هر دو $$(p - 1)$$ و $$(q - 1)$$ باید یک عامل اول بزرگ داشته باشند.
3. کوچکترین مقسوم‌علیه مشترک بین $$p$$ و $$q$$ یا «$$\gcd(p-1, q-1)$$» باید کوچک باشد.

علاوه بر این، نشان داده شده است که اگر $$e < n$$ و $$d \le 6n^{1/4}$$، آنگاه $$d$$ به راحتی قابل شناسایی است.

حملات مبتنی بر زمان در الگوریتم RSA چیست؟

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

این حمله به دو دلیل نگران‌کننده است.

• اول اینکه ناگهانی و غیرمنتظره است.
• دوم اینکه در دسته حملات «فقط با متن رمز شده» (Ciphertext-Only Attack) قرار می‌گیرد.

روش اجرای حملات مبتنی بر زمان

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

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

1. حمله بیت‌به‌بیت با پردازش از چپ‌ترین بیت، یعنی «$$bk$$»، آغاز می‌شود.
2. فرض کنید بیت‌های اول $$j$$ از توان از قبل مشخص باشند (برای یافتن کل توان، از $$j=0$$ شروع کرده و حمله را تکرار کنید تا کل توان مشخص شود).
3. مهاجم برای متن رمز مشخص، می‌تواند مراحل اولیه را با کمک حلقه «for» تا تکرار $$j$$ کامل کند.
4. عملیات مرحله بعدی به بیت نامعلوم توان بستگی دارد. اگر آن بیت برابر با ۱ باشد، دستور $$d \leftarrow (d × a) \mod n$$ اجرا خواهد شد. به عنوان مثال، در برخی مقادیر $$a$$ و $$d$$، این ضرب پیمانه‌ای به طور قابل توجهی کندتر انجام می‌شود و مهاجم می‌داند که این موارد کدام هستند. بنابراین، اگر زمان مشاهده شده برای اجرای الگوریتم رمزگشایی در هر مرحله خاص، کند باشد، این نشان می‌دهد که آن بیت ۱ است.
5. در مقابل، اگر تعدادی از زمان‌های اجرای مشاهده شده برای کل الگوریتم، سریع باشند، فرض می‌کنیم که این بیت ۰ است.

در ادامه توضیح داده‌ایم که روش پیشگیری از انجام موفق حملات مبتنی بر زمان در الگوریتم RSA چیست.

روش‌های محافظت از Timing Attacks در الگوریتم RSA چیست؟

البته در دنیای واقعی، کار با سیستم توان‌دهی پیمانه‌ای شامل چنان نوسانات زمانی شدیدی نیست. منظور نوساناتی هستند که زمان اجرای یکی از تکرار‌های عملیاتی در آن‌ها از زمان اجرای میانگین کل الگوریتم بیشتر شود. اما به اندازه‌ای نوسان وجود دارد که این حمله را عملی کند.

اگرچه «حمله زمانی» تهدیدی بسیار جدی است. بااین‌حال اقدامات ساده‌ای وجود دارند که با کمک آن‌ها می‌توان از این حمله پیش‌گیری کرد.

• «زمان توان‌دهی ثابت» (Constant Exponentiation Time): اطمینان حاصل کنید که زمان ثابتی برای تمام توان‌دهی‌ها قبل از بازگرداندن نتیجه، صرف بشود. این راه حل بسیار ساده است اما سرعت عملیات را کاهش می‌دهد.
• «تاخیر تصادفی» (Random Delay): با اضافه کردن وقفه زمانی به شکل تصادفی در الگوریتم توان‌دهی می‌توانیم عملیات حمله زمانی را فریب بدهیم. در نتیجه کیفیت کار به میزان زیادی افزایش پیدا می‌کند. کوچر اشاره می‌کند که اگر مدافعان نویز کافی اضافه نکنند، مهاجمان می‌توانند با اندازه‌گیری‌ داده‌های زمانی بیشتر حتی میزان تاخیرهای تصادفی را نیز پیش‌بینی کنند.
• «کور کردن» (Blinding): متن رمز را قبل از انجام توان‌دهی در عدد تصادفی، ضرب کنید. با اجرای این عملیات مهاجم نمی‌تواند تشخیص بدهد که کدام بیت‌های متن رمز در داخل کامپیوتر پردازش می‌شوند. بنابراین تکنیک «کورکردن» از تحلیل بیت‌به‌بیت (که برای حمله زمانی ضروری است) جلوگیری می‌کند.

روش پیاده‌سازی تکنیک Blinding در الگوریتم RSA چیست؟

«RSA Data Security» «ویژگی کورسازی» (Blinding Feature) را در برخی از محصولات خود گنجانده است. در این رویکرد، عملیات کلید خصوصی $$M = C^d$$ به صورت زیر پیاده‌سازی می‌شود.

1. سیستم ابتدا عدد تصادفی مخفی $$r$$ را بین ۰ تا $$n-۱$$ تولید می‌کند.
2. سپس نتیجه عبارت $$C' = C(r^e) \mod n$$ را بدست می‌آورد. در این فرمول، $$e$$ توان عمومی است.
3. بعد از آن باید مقدار $$M' = (C')^d \mod n$$ با پیاده‌سازی معمولی RSA محاسبه بشود.
4. در آخر هم فرمول $$M = M'r^{-1} \mod n$$ حساب می‌شود. در این معادله، $$r^{-1}$$ معکوس ضربی $$r$$ به پیمانه $$n$$ است. با توجه به برقرار بودن فرمول $$r^{ed} \mod n = r \mod n$$، می‌توان نشان داد که این نتیجه صحیح است.

توجه کنید: «RSA Data Security» تخمین زده است که با روش کورسازی، عملکرد الگوریتم در حدود ۲ تا ۱۰ درصد کندتر می‌شود.

در بخش بعد توضیح داده‌‌ایم که حمله مبتنی بر خطا در الگوریتم RSA چیست و چطور انجام می‌شود.

حمله مبتنی بر خطا

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

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

یادگیری رمزنگاری در فرادرس

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

در فهرست پایین فیلم‌های مجموعه آموزش رمزنگاری فرادرس را معرفی کرده‌ایم.

• فیلم آموزش ماژول Cryptography در پایتون درباره رمزنگاری و رمزگشایی فایل‌ ها + گواهینامه
• فیلم آموزش رایگان الگوریتم های رمزگذاری و رمزنگاری شبکه های بی سیم 
• فیلم آموزش ساخت اپلیکیشن چت با رمزنگاری سراسری در جاوا و نود جی اس
• فیلم آموزش رمزنگاری Cryptography در دات نت .NET

با کلیک بر روی تصویر زیر به صفحه اصلی این مجموعه آموزشی هدایت می‌شوید.

در بخش بعدی مطلب، حمله CCA را بررسی کرده و توضیح داده‌ایم که راه حل مراقبت از متون رمز شده در مقابل این حمله در الگوریتم RSA چیست.

حمله CCA در الگوریتم RSA چیست؟

الگوریتم پایه RSA در برابر «حمله متن رمز انتخاب شده» (Chosen Ciphertext Attack | CCA) آسیب‌پذیر است. «CCA» به حمله‌ای گفته می‌شود که در آن فرد یا سیستم مهاجم اول تعدادی متن رمز شده را انتخاب می‌کند. سپس متن‌های اصلی متناظر با آن‌ها را که با کلید خصوصی هدف رمزگشایی شده‌اند، دریافت می‌کند. بنابراین، مهاجم می‌تواند پیامی را انتخاب کند. سپس آن را با کلید عمومی هدف رمزگذاری کند و بعد از آن هم با رمزگشایی آن با کلید خصوصی، متن اصلی را بازیابی کند.

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

به عنوان نمونه ساده‌ای از حمله CCA علیه RSA می‌توانیم از ویژگی زیر در RSA بهره‌برداری بکنیم.

$$E(PU, M_1) × E(PU, M_2) = E(PU, [M_1 × M_2])$$

برای مثال می‌توانیم $$C = M^e \mod n$$ را با استفاده از CCA به شکل زیر رمزگشایی کنیم.

1. اول $$X = (C × 2^e) \mod n$$ را محاسبه می‌کنیم.
2. سپس $$X$$ را به عنوان متن رمز انتخاب‌شده ارسال کرده و $$Y = X^d \mod n$$ را دریافت می‌کنیم.

اما اکنون توجه داشته باشید که:

$$X = (C \mod n) × (2^e \mod n)$$

$$= (M^e \mod n) × (2^e \mod n)$$

$$= (2M)^e \mod n$$

بنابراین، $$Y = (2M) mod n$$ بدست می‌آید. اکنون می‌توانیم $$M$$ را استنتاج کنیم.

روش مقابله با حمله CCA

در این بخش از مطلب توضیح داده‌ایم که روش مقابله با حمله CCA محافظت از داده‌های رمزگذاری شده با الگوریتم RSA چیست. با هدف غلبه بر این حمله ساده، سیستم‌های عملیاتی رمزنگاری مبتنی بر RSA به طور تصادفی متن اصلی را قبل از رمزگذاری «Padding» می‌کنند. این کار متن رمز شده را تصادفی می‌کند. در نتیجه معادله بالا برای مزیت RSA دیگر برقرار نیست. با این حال، حملات CCA پیچیده‌تری نیز وجود دارند. ثابت شده است که Padding ساده با یک مقدار تصادفی برای فراهم کردن امنیت، کافی نیست.

برای مقابله با چنین حملاتی، «RSA Security Inc» توصیه می‌کند که متن اصلی با استفاده از روشی به نام «Padding رمزنگاری نامتقارن بهینه» (Optimal Asymmetric Encryption Padding | OAEP) اصلاح شود.

1. در اولین مرحله، پیام «M» که قرار است رمز شود، پد می‌شود. یعنی داده‌های اضافی استانداردی به آن اضافه می‌شوند. به این صورت که مجموعه‌ای از پارامترهای اختیاری با نام «P» از تابع هشی به نام «H» عبور داده می‌شوند.
2. خروجی این تابع بعدا با صفرها پر می‌شود تا به طول مورد نیاز در «بلوک داده» (Data Block | DB) کلی برسد.
3. سپس مقدار تصادفی به نام «Seed» تولید شده و از تابع هش دیگری عبور داده می‌شود. نام این تابع هش، «تابع تولید ماسک» (Mask Generating Function) یا MGF است.
4. مقدار هش حاصل، به صورت بیت‌به‌بیت با «بلوک داده» XOR می‌شود. نتیجه آن «MaskedDB» نام دارد.
5. در مرحله بعد، MaskedDB دوباره از همان تابع MGF عبور داده شده و مقدار هش جدیدی تولید می‌شود.
6. این مقدار هش با Seed اولیه XOR می‌شود. نتیجه این عملیات را «Maskedseed» می‌نامند.
7. در پایان، با کنار هم قرار دادن Maskedseed و MaskedDB، پیام رمزنگاری‌شده نهایی قبل از RSA به دست می‌آید که آن را «EM» می‌نامند.
8. توجه داشته باشید که EM شامل دو بخش است. اول پیام پد شده‌ای که با کمک Seed ماسک شده است، دوم هم Seed که با استفاده از MaskedDB ماسک شده.
9. در آخر، EM با استفاده از RSA رمز می‌شود.

جمع‌بندی

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

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