moji5
6th March 2010, 04:39 PM
رمزنگاری 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 √ بزرگتر خواهد بود. برای مثال محدوده جستجوی عددی ٥١٢ بیتی از مرتبه ٢٢٥٦ میشود که جستجوی چنین فضایی عملا غیر ممکن است. بنابر این تنها راه چاره استفاده از یکسری از قضایای ریاضی است که به ما کمک می کنند محدوده جستجو را کوچکتر نموده و مراحل حدس زدن کمتر شود.
در تمام الگوریتمهای رمزنگاری با کلید متقارن، فرستنده و گیرنده پیام باید کلید رمز را بدانند. وقتی فرستنده پیام از کلیدی یکتا و سری برای رمزنگاری استفاده می کند و گیرندگان پیام از همان کلید برای رمزگشایی بهره می برند، افشای کلید رمز از طریق یکی از گیرندکان پیام ،امنیت همه را به خطر می اندازد.در چنینی وضعیتی فرستنده مجبور خواهد بود با یکایک گیرندگان بطور مجزا بر سر یک کلید سری متقارن توافق کند تا هر یک گیرنده کلید مخصوص خود را داشته و افشای آن در امنیت دیگران خللی ایجاد نکند.در این حالت فرستنده پیام باید به تعداد گیرندگان خود کلید تعریف کرده و از آنها نگهداری کند. تعریف مثلا دهها هزار کلید متقارن برای کاربران و ذخیره و بازیابی مطمئن آنها به نوبه خود مشکل بزرگی است.
در الگوریتمهای کلید عمومی برای رمزنگاری و رمزگشایی از دو کلید کاملا متفاوت استفاده می شود: «کلید عمومی» و «کلید خصوصی».
کلید عمومی برای رمزنگاری اطلاعات بکار می رود و همه آن را میدانند ، زیرا از این کلید صررفا برای رمز کردن اطلاعات استفاده می شود و دشمنان با در اختیار داشتن آن نخواهند توانست داده ها ی رمز شده توسط دیگران را از رمز خارج کنند.
کلید خصوصی کلیدی است که داده های رمز شده با آن رمز گشایی می شوند. این کلید راهیچکس حتی معتمدین و دوستان نمی دانند. بدین ترتیب هر موجودیت در سطح شبکه (اعم از کاربر، ماشین یا پروسه ها) نیاز به دو کلید مستقل دارد که فقط یکی از آنها حساس و سری است و باید به دقت از آن نگهداری کرد.ماهیت الگوریتم رمزنگاری به گونه ای است که در عمل نمی توان با در دست داشتن کلید عمومی کلید خصوصی را استنتاج کرد.
در سال ١٩٧٨ سه نفر به نامهای رىوست ،شامیر و اَدِلمن الگوریتمی را برای پیاده سازی رمزنگاری کلید عمومی با یک جفت کلید معرفی کردند که به 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 √ بزرگتر خواهد بود. برای مثال محدوده جستجوی عددی ٥١٢ بیتی از مرتبه ٢٢٥٦ میشود که جستجوی چنین فضایی عملا غیر ممکن است. بنابر این تنها راه چاره استفاده از یکسری از قضایای ریاضی است که به ما کمک می کنند محدوده جستجو را کوچکتر نموده و مراحل حدس زدن کمتر شود.