پیاده سازی الگوریتم RSA در C++

الگوریتم RSA

الگوریتم RSA در مقالات الگوریتم RSA موجود می باشد. توضیحات بیشتر در مورد الگوریتم RSA در زیر آمده‌است:

مقدمه

در سال ۱۹۷۶ وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد، یکی از کاربردی ترین روشهای کد کردن اطلاعات را اختراع و به ثبت رساندند. در این روش که به روش کدینگ نا متقارن (asymmetric encryption) نیز معروف است از دو کلید برای کد کردن اطلاعات استفاده می‌شود. (در روشهای قدیمی تر از یک کلید استفاده می‌شد که به آن symmetric encryption گفته می‌شد.)

آنها مقاله خود را در یکی از شماره‌های سال ۱۹۷۶ مجله IEEE که با عنوان Transactions on Information Theory منتشر شده بود به چاپ رساندند که خیلی زود انقلابی در صنعت Cryptography (پنهان سازی اطلاعات) در دنیا بوجود آورد. Public Key Cryptography یا PKC به معنی استفاده از کلید عمومی برای کد کردن و پنهان کردن اطلاعات است.

کلیدهای Public و Private

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

روش کار اینگونه‌است که هر کاربر دو کلید در دست خود دارد که یکی را در اختیار همه دوستان و اطرافیان برای خواند مطالبی که او کد کرده‌است قرار می‌دهد، این همان کلید عمومی یا Public است.

روش کار

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

اساس استفاده از این روش کدینگ یا مخفی سازی اطلاعات به الگوریتم مشهوری بنام Rivest Shamir Adleman یا الگوریتم RSA برمی‌گردد. از الگوریتم RSA برای تهیه کلیدهای مذکور، کد کردن اطلاعات، دی کد کردن یا آشکار سازی اطلاعات، تهیه امضاهای الکترونیکی و…. استفاده می‌شود. الگوریتم RSA پس از آنکه ران ریوست (Ron Rivest)، آدام شامیر (Adam Shamir) و لن ادلمن (Len Adleman) در سال ۱۹۷۷ آنرا بدست آوردند به این نام مشهور شد، هرچند تکنیک‌های اولیه آن پیشتر در سال ۱۹۷۳ توسط فردی بنام کلیفورد کوکس (Clifford Cocks) بدست آمده بود اما تا سال ۱۹۷۷ اولاً الگورتیم کاملاً محرمانه بود و ثانیاً به سادگی آنچه در زیر بیان خواهیم کرد نبود.

تهیه کلیدهای عمومی و خصوصی الگوریتم RSA

● تهیه کلیدهای عمومی و خصوصی الگوریتم RSA بطور خلاصه روش کار برای تهیه کلیدها به شرح زیر است:

1- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های p و q را انتخاب می‌کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. 2- عدد دیگری بنام n را معادل با حاصلضرب p در q تعریف می‌کنیم : n = p x q ۳- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می‌کنیم : (m = (p-۱) x (q-۱ ۴- عدد e را که از m کوچکتر است آنگونه پیدا می‌کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند.

3- عددی مانند d را پیدا کنید که باقی‌مانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی : d x e) mod m = ۱) حال پس از طی این مراحل شما می‌توانید از e و n بعنوان کلید عمومی و از d و n بعنوان کلید اختصاصی استفاده کنید.

روش پنهان کردن و آشکار کردن در الگوریتم RSA

● روش پنهان کردن و آشکار کردن در الگوریتم RSA برای کد کردن اطلاعات کافی است عدد منتصب به هر کاراکتر – مثلاً ASCII – را که در اینجا M می‌نامیم در فرمول زیر قرار دهید و بجای ارسال آن عدد C = M^e mod n را ارسال کنید. در واقع دراینجا شما توانسته‌اید با کمک کلید عمومی، کاراکتر M را به C تبدیل کنید. حال گیرنده برای آشکار سازی کافی است عدد دریافتی یعنی C را با استفاده از کلید خصوصی به M تبدیل کند. برای اینکار کافی است از این فرمول استفاده کنید : M = C^d mod n، بنابراین شما با دریافت کاراکتر کد شده C و در دست داشتن کلید خصوصی توانسته‌اید کاراکتر اصلی را مشخص نمایید.

مثال

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

پس p=۱۱ , q=۳ – حاصلضرب p در q که همان n است را به اینصورت خواهیم داشت : n = ۱۱ x ۳ = ۳۳ ۳- حاصلضرب p-۱ در q-۱ که همان m است را به اینصورت خواهیم داشت : m = ۱۰ x ۲ = ۲۰ ۴- برای انتخاب عدد e که نسبت به m=۲۰ اول باشد و کمتر از آن هم باشد ساده ترین گزینه یعنی عدد ۳ را انتخاب می‌کنیم. ۵- برای یافتن عدد d که در رابطه d x e) mod m = ۱) صادق باشد اعداد ۱٬۲,۳٬۴,۵ و… را امتحان می‌کنیم، بنظر می‌رسد که عدد ۷ برای اینکار مناسب باشد چرا که ۷x۳=۲۱ باقی‌مانده‌ای معادل ۱ بر m=۲۰ دارد.

محصول

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

ویدئوی معرفی محصول