[Powered by Google Translate] [RSA]
[راب Bowden] [تامی MacWilliam] [دانشگاه هاروارد]
[این CS50.] [CS50.TV]
بیایید نگاهی به RSA، یک الگوریتم به طور گسترده ای مورد استفاده برای رمزنگاری داده ها.
الگوریتم های رمز نگاری مانند سزار و رمزهای Vigenère خیلی امن نیست.
با استفاده از رمزنگاری سزار، مهاجم تنها نیاز به 25 کلید های مختلف را امتحان کنید
برای به دست آوردن متنهای نوشتهشده در این پیام.
در حالی که رمزنگاری Vigenère امن تر است نسبت به رمزنگاری سزار
به دلیل فضای بزرگتر جستجو برای کلید، یک بار یک مهاجم
می داند که طول کلید در رمزنگاری Vigenère،
است که می تواند از طریق تجزیه و تحلیل از الگوهای موجود در متن رمز شده مشخص شده است،
رمزنگاری Vigenère است که بسیار امن تر از رمزنگاری سزار نیست.
RSA، از سوی دیگر، به مانند این حمله آسیب پذیر است.
رمزنگاری سزار و Vigenère رمزنگاری با استفاده از کلید
به هر دو رمزگذاری و رمزگشایی یک پیام است.
این ویژگی باعث می شود این الگوریتم های رمز کلید متقارن است.
یک مشکل اساسی با الگوریتم های کلید متقارن
این است که آنها در یکی از رمزنگاری و ارسال پیام تکیه می کنند
و یکی از دریافت و رمز گشایی پیام
در حال حاضر در صف مقابل توافق بر روی کلید آنها را از هر دو استفاده شده است.
اما در حال حاضر کمی مشکل راه اندازی است.
چگونه 2 کامپیوتر که می خواهند برای برقراری ارتباط برقرار کلید مخفی بین آنها؟
اگر کلید های مخفی باید، پس ما نیاز به یک راه برای رمزگذاری و رمزگشایی کلید.
اگر همه ما باید رمزنگاری کلید متقارن است
پس از آن ما فقط به مشکل مشابه آمده است.
RSA، از سوی دیگر، با استفاده از یک جفت کلید،
یکی برای رمزگذاری و دیگری برای رمزگشایی.
یکی کلید عمومی نامیده می شود، و از سوی دیگر، کلید خصوصی است.
کلید عمومی مورد استفاده برای رمزگذاری پیام است.
همانطور که شما ممکن است توسط نام خود را حدس بزنید، ما می توانیم کلید عمومی خود را با به اشتراک گذاشتن
هر کسی که ما بدون به خطر انداختن امنیت یک پیام رمز شده می خواهم.
پیام های رمزگذاری شده با استفاده از یک کلید عمومی
می تواند تنها با کلید خصوصی مربوط به خود را رمزگشایی می شود.
در حالی که شما می توانید کلید عمومی خود را به اشتراک بگذارید، شما همیشه باید راز کلید خصوصی خود را نگه می دارد.
و تنها کلید خصوصی را می توان به پیام های رمزگشایی استفاده می شود
اگر 2 کاربران میخواهند برای ارسال پیام های رمزگذاری شده با RSA
به جلو و عقب هر دو نیاز کاربران عمومی و خصوصی خود را به جفت کلید خود را.
پیامها از کاربر 1 کاربر 2
تنها جفت کلید 2 کاربر و پیام از کاربر 2 کاربر 1 استفاده کنید
تنها جفت کلید کاربر 1 استفاده کنید.
واقعیت این است که 2 کلید جداگانه برای رمزگذاری و رمزگشایی پیام وجود دارد
باعث می شود RSA الگوریتم کلید نامتقارن است.
ما لازم نیست که کلید عمومی به منظور رمزگذاری برای ارسال آن به یک کامپیوتر دیگر
از کلید عمومی است به هر حال.
این به این معنی است که RSA مشکل راه اندازی ندارد
و الگوریتم های کلید متقارن است.
پس اگر من می خواهم به ارسال پیام با استفاده از رمزگذاری RSA
به غارت، من برای اولین بار می خواهید کلید عمومی راب نیاز دارند.
برای تولید یک جفت کلید، راب نیاز به 2 عدد اول بزرگ انتخاب کنید.
این اعداد خواهد شد در هر دو کلید عمومی و خصوصی استفاده می شود،
اما تنها کلید عمومی خواهد شد که محصول استفاده از این 2 عدد،
نه خود اعداد.
هنگامی که من در رمزگذاری پیام با استفاده از کلید عمومی راب
من می تواند این پیام را به راب ارسال کنید.
برای یک کامپیوتر، تعداد مقاطعه یک مشکل سخت است.
کلید عمومی، به یاد داشته باشید، با استفاده از محصول، از مجموع 2 عدد اول است.
این محصول پس از آن باید تنها 2 عوامل داشته باشد،
که اتفاق می افتد به اعداد است که کلید خصوصی را تشکیل می دهند.
به منظور رمزگشایی پیام، RSA این کلید خصوصی استفاده کنید
یا اعداد را با هم در این روند ایجاد کلید عمومی ضرب.
از آنجا که آن محاسباتی سخت به عامل شماره
در یک کلید عمومی را به 2 شماره مورد استفاده در کلید خصوصی استفاده می شود
این مشکل برای یک مهاجم به شکل از کلید خصوصی
که لازم خواهد بود به رمزگشایی پیام.
حالا اجازه دهید به بعضی از جزئیات سطح پایین تر از RSA.
اجازه بدهید که چگونه ما می توانیم یک جفت کلید تولید را ببینید.
اول، ما نیاز به 2 عدد اول است.
ما می خواهیم با این 2 عدد p و q.
به منظور انتخاب P و Q، در عمل ما pseudorandomly تولید
اعداد بزرگ و سپس با استفاده از یک آزمایش برای تعیین اینکه آیا یا نه
کسانی که احتمالا نخست.
ما می توانیم به تولید اعداد تصادفی بارها و بارها
تا زمانی که ما دارای 2 عدد اول است که ما می توانیم با استفاده از.
در اینجا انتخاب کنید p = 23 و q = 43.
به یاد داشته باشید، در عمل، p و q باید بسیار بزرگتر اعداد.
تا آنجا که ما می دانیم، چه اعداد بزرگتر، سخت تر از آن است که
برای شکستن یک پیام رمزگذاری شده است.
اما آن نیز گران تر برای رمزگذاری و رمزگشایی پیام.
امروزه آن را اغلب توصیه می شود که P و Q حداقل 1024 بیت،
قرار می دهد که هر تعداد در بیش از 300 رقم اعشار است.
اما ما این اعداد کوچک برای این مثال را انتخاب کنید.
حالا p و q را در هم ضرب شماره 3 برای به دست آوردن،
که ما بهش زنگ می زنم N.
در مورد ما، N = 23 * 43، که = 989.
در حال حاضر به N = 989.
1 با q - - بعد خواهیم P ضرب 1
برای به دست آوردن شماره 4، که ما بهش زنگ می زنم متر است.
در مورد ما، M = 22 * ​​42، که = 924.
M = 924.
در حال حاضر ما به A و E است که نسبتا نخست نیاز به متر
و کمتر از م.
دو عدد نسبتا نخست یا coprime
اگر تنها عدد صحیح مثبت که آنها را به دو قسمت تقسیم هر دو به طور مساوی 1 است.
به عبارت دیگر، بزرگترین مقسوم علیه مشترک E و M
باید 1.
در عمل، آن را مشترک برای E را به عنوان نخست شماره 65،537
تا زمانی که این شماره اتفاق نمی افتد که به یک عامل از م.
برای کلیدهای خود، ما را انتخاب کنید E = 5
چون 5 نسبتا نخست به 924 است.
در نهایت، ما می خواهیم یک شماره، که ما بهش زنگ می زنم D نیاز دارند.
D باید برخی از ارزش است که این معادله را ارضا د = 1 (وزارت دفاع متر).
این وزارت دفاع متر دلالت می کنیم چیزی به نام حساب مدولار استفاده کنید.
در حساب مدولار، یک بار در شماره می شود بالاتر از برخی از حد بالا
اطراف آن خواهد بپیچید تا 0.
یک ساعت، به عنوان مثال، با استفاده از حساب مدولار.
یک دقیقه به عنوان مثال، پس از 1:59، 2:00،
1:60 نیست.
دست دقیقه تا 0 پیچیده
پس از رسیدن به حد بالا از 60.
بنابراین، می توان گفت 60 معادل 0 (وزارت دفاع 60)
و 125 تا 65 معادل است معادل 5 (MOD 60) می باشد.
کلید عمومی ما خواهد بود که جفت E و N
که در این مورد 5 E و N 989.
کلید خصوصی ما خواهد بود جفت D و N،
که در مورد ما، 185 و 989 است.
توجه کنید که اصلی ما اعداد اول p و q به نظر نمی رسد
در هر جای کلید خصوصی یا عمومی است.
حالا که ما باید جفت خود را از کلید، اجازه دهید یک نگاهی که ما چگونه می تواند رمزنگاری
و رمزگشایی یک پیام است.
من می خواهم به ارسال پیام به راب،
بنابراین او خواهد بود برای تولید این جفت کلید است.
سپس من راب کلید عمومی خود را، که من با استفاده از درخواست
به رمز در آوردن یک پیام برای ارسال به او.
به یاد داشته باشید، آن را کاملا درست است راب برای به اشتراک گذاشتن کلید عمومی خود را با من.
اما آن را نمی خواهد درست کلید خصوصی خود را برای به اشتراک گذاشتن.
من هیچ ایده چه چیزی کلید خصوصی خود را ندارد.
ما می توانیم م پیام ما شکستن به تکه های مختلف
کوچکتر از N و سپس به رمز در آوردن هر یک از کسانی که تکه.
خواهیم CS50 رشته، که ما می توانیم به 4 تکه رمزگذاری،
یکی در نامه است.
به منظور رمزنگاری پیام من، من نیاز به آن را تبدیل به
نوعی از نمایندگی عددی.
بیایید الحاق مقادیر ASCII با شخصیت ها در پیام من است.
به منظور رمزنگاری داده م پیام
من نیاز به محاسبه C = M به E (وزارت دفاع N).
اما متر باید کوچکتر از N،
و یا دیگری کامل پیام را می توان بیان پیمانه N.
ما می توانیم متر شکستن به تکه های مختلف، که همه آنها کوچکتر از N،
و رمز در آوردن هر یک از کسانی که تکه.
رمزگذاری هر یک از این تکه های، ما C1 = 67 تا 5 (وزارت دفاع 989)
که = 658.
برای تکه دوم ما ما از 83 تا 5 (وزارت دفاع 989)
که = 15.
برای تکه سوم ما 53 تا 5 (وزارت دفاع 989)
که = 799.
و در نهایت، برای تکه آخر ما ما 48 تا 5 (وزارت دفاع 989)
که = 975.
در حال حاضر ما می توانیم بیش از این ارزش های رمز شده را به راب.
در اینجا شما بروید، راب.
در حالی که پیام ما این است که در هنگام پرواز، اجازه دهید نگاهی دیگر نگاه
ما در چگونه که ارزش برای D است.
ما D تعداد مورد نیاز برای برآورده 5D = 1 (mod 924) را.
این باعث می شود د ضربی معکوس از 5 پیمانه 924.
با توجه به 2 اعداد صحیح، A و B، الگوریتم اقلیدسی گسترده
را می توان مورد استفاده قرار گیرد برای پیدا کردن بزرگترین مقسوم علیه مشترک این 2 اعداد صحیح.
این نیز ما را به 2 عدد دیگر، x و y،
که برآورده معادله ax + by = بزرگترین مقسوم علیه مشترک a و b است.
چگونه به ما کمک کند؟
خب، متصل کردن در E = 5 برای
و m = 924 ب
ما در حال حاضر می دانیم که این اعداد coprime است.
بزرگترین مقسوم علیه مشترک آنها 1 است.
این به ما می دهد 5X + 924y = 1
یا 5X = 1 - 924y.
اما اگر ما فقط در مورد مراقبت از همه چیز پیمانه 924
924y - پس از آن ما می توانیم قطره.
فکر می کنم به ساعت.
اگر دست در 1 دقیقه می باشد و پس از آن دقیقا 10 ساعت از زمان،
ما می دانیم که هنوز هم از سوی دقیقه در 1.
در اینجا ما در 1 شروع و پس از آن پوشش در اطراف بار دقیقا Y،
بنابراین ما هنوز هم می خواهید در 1.
ما 5X = 1 (mod 924) را.
و در اینجا این X به عنوان د ما قبل دنبال می شد،
بنابراین اگر ما با استفاده از الگوریتم اقلیدسی گسترده
برای به دست آوردن این عدد X است، که ما باید به عنوان D ما استفاده کنید.
در حال حاضر اجرای الگوریتم اقلیدسی را برای 5 =
و B = 924.
ما می خواهیم یک روش به نام روش جدول استفاده کنید.
جدول ما 4 ستون، X، Y، D و K را داشته باشد.
میز ما شروع می شود با 2 ردیف است.
در سطر اول ما، 1، 0، پس از آن ارزش خود را از، که 5
و ردیف دوم ما 0، 1 است، و ارزش خود را برای ب، است که 924.
مقدار ستون 4، k، خواهد بود و در نتیجه
از تقسیم مقدار در ردیف بالای آن را با مقدار D از D
در همان ردیف.
ما 5 و تقسیم بر 924 0 است با برخی باقی مانده است.
این بدان معناست که ما k = 0.
در حال حاضر ارزش هر سلول دیگر خواهد بود که ارزش از 2 سلول ردیف بالای آن
منهای مقدار از سطر بالاتر از آن بار K است.
بیایید شروع با D در ردیف 3.
در حال حاضر 5 - 924 * 0 = 5.
بعد ما باید 0 - 1 * 0 که 0 است
و 1 - 0 * 0 که 1 است.
خیلی بد نیست، بنابراین اجازه دهید تا به سطر بعدی.
در ابتدا ما نیاز داریم ارزش ما از K.
924 5 = 184 با برخی از باقی مانده تقسیم،
بنابراین ارزش ما برای K 184 است.
در حال حاضر 924 - 5 * 184 = 4.
1 - 0 * 184 1 و 0 - 1 * 184 -184 است.
خوب، اجازه دهید ردیف بعد را انجام دهید.
ارزش ما از K خواهد بود 1. چون
5 4 = 1 با برخی از باقی مانده تقسیم شده است.
بیایید در ستون دیگر را پر کنید.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
و 1 - 184 * 1 185 است.
بیایید ببینید که چه مقدار بعدی ما از K خواهد بود.
خب، به نظر می رسد که در حال حاضر 4 تقسیم 1، 4 است.
در این مورد که در آن ما در حال تقسیم بر 1 به طوری که K برابر است با
مقدار D در سطر بالا به این معناست که ما با الگوریتم ما انجام می شود.
ما در اینجا می توانید ببینید که ما باید x = 185 و Y = -1 در ردیف آخر.
اجازه دهید در حال حاضر دوباره به هدف اصلی ما است.
به ما گفت که مقدار x را به عنوان یک نتیجه اجرای این الگوریتم
معکوس ضرب (MOD B خواهد بود).
این بدان معناست که 185 ضربی معکوس از 5 (وزارت دفاع 924)
که بدان معنی است که ما باید یک مقدار از 185 D می باشد.
واقعیت این است که D = 1 در سطر آخر
بررسی الکترونیکی به متر coprime شد.
اگر آن را به 1 نیست پس ما را الکترونیکی جدید را انتخاب کنید.
حالا اگر راب پیام من را دریافت کرده است.
وقتی کسی به من می فرستد یک پیام رمز شده
تا زمانی که من کلید خصوصی یک راز نگه داشته ام
من یکی از تنها کسی که می تواند رمزگشایی پیام.
رمز گشایی یک قطعه می توانید پیام اصلی را محاسبه
به تکه D قدرت (وزارت دفاع N) برابر است.
به یاد داشته باشید که D و N از کلید خصوصی من هستند.
برای دریافت پیام کامل از تکه های آن را رمزگشایی هر تکه
و الحاق نتایج.
دقیقا چه امن است RSA؟
حقیقت این است که ما نمی دانیم.
امنیت در چه مدت آن را یک نفوذگر برای شکستن یک پیام را بر اساس
رمزگذاری RSA
به یاد داشته باشید که یک مهاجم دسترسی به کلید عمومی شما،
که شامل هر دوی E و N است.
اگر مهاجم مدیریت عامل N به آن 2 اعداد اول p و q،
پس از آن او می تواند D با استفاده از الگوریتم اقلیدسی گسترده را محاسبه نمود.
این امر به او کلید خصوصی، که می تواند هر پیام برای رمزگشایی استفاده می شود.
اما چگونه به سرعت می تواند اعداد صحیح از فاکتور؟
باز هم، ما نمی دانیم.
هیچ کس راه سریع از انجام آن،
که بدان معنی است که داده می شود به اندازه کافی بزرگ N
آن را یک مهاجم unrealistically طولانی را
عامل شماره.
اگر کسی نشان داد یک راه سریع از اعداد صحیح مقاطعه
RSA شکسته خواهد شد.
اما حتی اگر فاکتور عدد صحیح ذاتا آهسته
الگوریتم RSA هنوز می تواند برخی از نقص در آن را داشته باشد
است که اجازه می دهد تا برای رمزگشایی آسان از پیام.
هیچ کس پیدا کرده است و نشان داد چنین نقص هنوز،
اما این به این معنا نیست که یکی وجود ندارد.
در تئوری، کسی که می تواند در خارج وجود دارد خواندن تمام داده های رمزگذاری شده با RSA است.
یکی دیگر از کمی مسئله حفظ حریم خصوصی وجود دارد.
اگر تامی کدگذاری برخی از پیام با استفاده از کلید عمومی من
و یک مهاجم کدگذاری پیام با استفاده از کلید های عمومی من
مهاجم خواهید دید که این 2 پیغام یکسان هستند
و به این ترتیب آنچه تامی رمزگذاری می دانم.
به منظور جلوگیری از این پیام ها به طور معمول با بیت تصادفی خالی
قبل از اینکه رمزگذاری رمزگذاری شده به طوری که همان پیام
چند بار نگاه متفاوت به عنوان طولانی به عنوان بالشتک در پیام متفاوت است.
اما به یاد داشته باشید که ما چگونه باید به تقسیم پیام ها را به تکه های
به طوری که هر یک از تکه است کوچکتر از N؟
عمل توسعه دادن تکه های این بدان معنی است که ما ممکن است مجبور به تقسیم کردن کارها
به تکه حتی بیشتر از تکه های خالی را باید کوچکتر از N.
رمزنگاری و رمزگشایی نسبتا گران قیمت با RSA،
و به همین ترتیب نیاز به شکستن تا یک پیام را به تکه های مختلف می تواند بسیار پر هزینه است.
اگر حجم زیادی از داده ها نیاز به رمزگذاری و رمزگشایی
ما می توانیم از مزایای الگوریتم کلید متقارن ترکیب
با کسانی که از RSA برای به دست آوردن هر دو امنیت و کارایی.
اگر چه ما نمی خواهد به آن در اینجا،
AES یک الگوریتم کلید متقارن مانند Vigenère و رمزهای سزار
اما بسیار سخت تر به کرک.
البته، ما می توانیم AES بدون ایجاد یک کلید مخفی مشترک استفاده نمی کنند
بین 2 سیستم، و ما را دیدم مشکل با آن شده قبل از.
اما در حال حاضر ما می توانیم با استفاده از RSA کلید مخفی مشترک بین 2 سیستم برای ایجاد.
ما به کامپیوتر فرستنده ارسال داده ها تماس بگیرید
و کامپیوتر دریافت اطلاعات مربوط به گیرنده است.
گیرنده دارای یک جفت کلید RSA می فرستد و
کلید عمومی فرستنده است.
فرستنده تولید یک کلید AES،
کدگذاری آن را با کلید عمومی RSA گیرنده،
می فرستد و کلید AES به گیرنده است.
گیرنده رمزگشایی پیام کلید RSA خصوصی خود است.
هر دو فرستنده و گیرنده در حال حاضر دارای یک کلید AES مشترک بین آنها است.
AES، که بسیار سریعتر در رمزنگاری و رمزگشایی از RSA،
هم اکنون می توانید حجم زیادی از داده ها و ارسال آنها را به گیرنده مورد استفاده برای رمزگذاری،
که می تواند رمزگشایی با استفاده از همان کلید است.
AES، که بسیار سریعتر در رمزنگاری و رمزگشایی از RSA،
هم اکنون می توانید حجم زیادی از داده ها و ارسال آنها را به گیرنده مورد استفاده برای رمزگذاری،
که می تواند رمزگشایی با استفاده از همان کلید است.
ما فقط نیاز RSA به انتقال کلید به اشتراک گذاشته است.
ما دیگر نیاز به استفاده از RSA در تمام.
به نظر می رسد مثل من یک پیام است.
مهم نیست که اگر کسی خواندن آنچه بر روی موشک های کاغذی قبل از من آن را گرفتار
چون من تنها با کلید خصوصی.
بیایید رمزگشایی هر یک از تکه ها در این پیام.
تکه اول، در 658، ما به قدرت D، که 185 بالا بردن،
وزارت دفاع ازت، است که 989، تا 67 برابر است،
است که C نامه ای در ASCII.
در حال حاضر، بر روی تکه دوم.
تکه دوم ارزش 15
که ما به قدرت 185 بالا می برد،
وزارت دفاع 989، و این برابر است به 83
است که S نامه ای در ASCII.
در حال حاضر برای تکه سوم، که دارای ارزش 799، به 185 افزایش دهد،
وزارت دفاع 989، و این برابر است به 53،
است که ارزش شخصیت 5 در ASCII.
در حال حاضر برای تکه گذشته، که دارای ارزش 975،
ما به 185 را بالا می برد، وزارت دفاع، 989،
و این برابر است به 48، است که ارزش از 0 کاراکتر در ASCII است.
نام من راب Bowden، و این CS50.
[CS50.TV]
RSA در تمام.
RSA در تمام. [خنده]
در همه.