[Powered by Google Translate] [RSA] [Rob Bowden] [Tommy MacWilliam] [Harvard Universiteti] [Bu CS50 edir.] [CS50.TV] Nin RSA, data Şifreleme üçün geniş istifadə alqoritm nəzər salaq. Sezar və Vigenère ciphers kimi Encryption alqoritmlər çox təhlükəsiz deyil. Olan Sezar parol ilə, bir saldırganın yalnız 25 müxtəlif düymələri cəhd lazımdır mesaj düz mətn almaq üçün. The Vigenère parol the Caesar parol artıq təhlükəsiz olsa çünki düymələri üçün böyük axtarış alan, bir dəfə, bir saldırganın bir Vigenère parol ildə əsas uzunluğu bilir olan şifreli mətn nümunələri təhlil vasitəsilə müəyyən edilə bilər the Vigenère cipher daha təhlükəsiz Caesar parol çox deyil. RSA, digər tərəfdən, bu kimi hücumlara həssas deyil. Bu Caesar parol və Vigenère parol eyni düyməsindən istifadə encrypt və decrypt mesaj həm də. Bu əmlak bu ciphers simmetrik əsas alqoritmləri edir. Simmetrik əsas alqoritmləri olan əsas problem onlar mesaj Şifreleme və göndərilməsi bir etibar ki, və bir qəbul və mesaj decrypting artıq onlar həm istifadə edəcək əsas haqqında upfront razılıq var. Amma burada bir başlanğıc problem bir qədər var. Necə ünsiyyət etmək istəyirəm ki, 2 kompüter arasında bir gizli əsas yaratmaq edirsiniz? Əsas gizli olmalıdır, onda biz əsas şifrelemek və decrypt üçün bir yol lazımdır. Biz bütün simmetrik əsas Kriptoqrafiya deyil sonra biz yalnız eyni problem qayıda etdik. RSA, digər tərəfdən, düymələri bir cüt istifadə parol çözme üçün şifrələmə və digər üçün. Bir ictimai əsas adlanır və digər xüsusi açarı edir. Ictimai əsas messages şifrelemek üçün istifadə olunur. Onun adı ilə tapmaq kimi, biz bizim ictimai əsas payı edə bilərsiniz biz şifrəli mesaj təhlükəsizlik ödün olmadan istədiyiniz hər kəs. Mesajlarım ictimai açarı istifadə şifrelenir yalnız müvafiq xüsusi açar ilə şifresi çözülen bilər. Siz ictimai əsas payı edə bilərsiniz baxmayaraq, siz həmişə xüsusi açarı gizli saxlamaq lazımdır. Özəl əsas gizli saxlanılır və yalnız özəl əsas olmalıdır ildən 2 istifadəçi mesaj göndərmək istəyirsinizsə, decrypt mesaj üçün istifadə edilə bilər geri və irəli RSA ilə şifrelenir həm istifadəçilər, öz ictimai və özəl əsas cüt lazımdır. Istifadəçi 1 istifadəçi 2 Mesajlarım yalnız, istifadəçi 2 əsas cüt istifadə və istifadəçi 2 istifadəçi 1 mesaj yalnız istifadəçi 1 əsas cüt istifadə edin. 2 ayrı-ayrı şifrelemek düymələri və decrypt mesaj var ki, RSA bir asimmetrik açar alqoritmi edir. Biz başqa bir kompüter göndərmək üçün ictimai əsas şifrelemek ehtiyac yoxdur əsas hər halda ictimai göstərir. Bu RSA bir simmetrik əsas alqoritm eyni başlanğıc problem yoxdur deməkdir. Ünsiyyət etmək istəyirəm ki, 2 kompüter necə onların arasında gizli bir əsas qurmaq? Əsas gizli olmalıdır, onda biz əsas şifrelemek və decrypt üçün bir yol lazımdır. Biz bütün simmetrik əsas Kriptoqrafiya onda biz yalnız var Eyni problem geri gəlir. RSA, digər tərəfdən, düymələri bir cüt istifadə parol çözme üçün şifrələmə və digər üçün. Bir ictimai əsas adlanır və digər xüsusi açarı edir. Ictimai əsas messages şifrelemek üçün istifadə olunur. Onun adı ilə tapmaq kimi, biz istəyirik hər kəs ilə ictimai əsas payı edə bilərsiniz şifreli mesaj təhlükəsizlik ödün olmadan. Ictimai açarı istifadə şifrelenir Mesajlarım yalnız şifresi çözülen bilər müvafiq xüsusi açar ilə. Siz ictimai əsas payı edə bilərsiniz baxmayaraq, siz həmişə xüsusi açarı gizli saxlamaq lazımdır. Özəl əsas gizli saxlanılmalıdır ildən və yalnız xüsusi açarı decrypt mesaj üçün istifadə edilə bilər 2 istifadəçi RSA ilə mesaj şifrəli göndərmək istəyirsinizsə geri və irəli də istifadəçilər öz dövlət və özəl əsas cüt lazımdır. Istifadəçi 1 istifadəçi 2 Mesajlarım yalnız user 2 istifadəçi 1 istifadəçi 2 əsas cüt, mesaj istifadə yalnız istifadəçi 1 əsas cüt istifadə edin. 2 ayrı-ayrı şifrelemek düymələri və decrypt mesaj var ki, RSA bir asimmetrik açar alqoritmi edir. Biz başqa bir kompüter göndərmək üçün ictimai əsas şifrelemek ehtiyac yoxdur əsas hər halda ictimai göstərir. Bu RSA eyni başlanğıc problem yoxdur o deməkdir ki, bu simmetrik əsas alqoritmləri kimi. Mən RSA şifreleme istifadə edərək mesaj göndərmək istədiyiniz Belə ki, əgər Rob, mən ilk Rob ictimai əsas lazımdır. Düymələri bir cüt yaratmaq üçün, Rob 2 böyük baş nömrələri yığmaq lazımdır. Bu nömrələr, həm də dövlət və özəl açarları istifadə olunacaq lakin ictimai əsas yalnız bu 2 ədəd məhsul istifadə edəcək deyil nömrələri özləri. Mən Rob ictimai əsas istifadə edərək mesaj şifrelenir sonra Mən Rob mesaj göndərə bilərsiniz. Bir kompüter üçün, faktorinq ədəd ağır problemdir. Ictimai əsas, xatırlayıram, 2 baş nömrələri məhsul istifadə. Bu məhsul, sonra yalnız 2 amillər olmalıdır özəl əsas təşkil edən nömrələri olmaq üçün baş verir. Decrypt mesaj üçün, RSA bu xüsusi açarı istifadə edəcək və ya ədəd ictimai əsas yaradılması prosesi birlikdə vurulur. Bu sayı Factor computationally çətindir, çünki özəl əsas istifadə 2 ədəd bir ictimai əsas istifadə Bir saldırganın özəl əsas anlamaq üçün çətin decrypt mesaj lazım olacaq. İndi RSA bəzi aşağı təfərrüata varmaq bildirin. Gəlin ilk biz düymələri bir cüt yarada necə. Birincisi, 2 baş nömrələri lazımdır. Biz bu 2 ədəd p və q zəng edəcəyik. Praktikada p və q, seçin üçün biz pseudorandomly yaradacaq sonra böyük sayda və müəyyən bir test istifadə və ya bu ədəd yəqin ki, baş var. Biz yenə üzərində təsadüfi nömrələri yaradan saxlaya bilərsiniz biz istifadə edə bilərsiniz ki, 2 primes qədər. Burada p = 23 q = 43 seçin bildirin. Praktikada, saxla, p və q daha nömrələri olmalıdır. Bizdə kimi, ədəd böyük, daha bu şifreli mesajı çat. Lakin bu da şifrelemek və decrypt mesaj daha bahalı. Bu gün tez-tez p və q azı 1024 bit olan tövsiyə, olan 300-dən artıq decimal rəqəm hər sayı qoyur. Amma bu məsələn bu kiçik nömrələri yığmaq lazımdır. İndi, 3-cü nömrə almaq üçün birlikdə p və q çoxaltmaq olacaq biz n zəng bilərsiniz. Bizim halda, n = 23 989 = olan * 43. Biz = 989 n. Q ilə - 1 - Next biz p çoxaltmaq olacaq 1 biz m arayacaðým olan 4-cü sayı. almaq Bizim halda, m = 22 924 = olan * 42. Biz m = 924 var. İndi nisbətən baş ki, bir sıra e lazımdır m və m-dən azdır. Iki ədəd nisbətən baş və ya coprime var həm bərabər onlara ayıran yalnız müsbət tam 1 olsun. E və m Başqa sözlə, ən böyük ortaq bölən 1 olmalıdır. Təcrübədə, bu, baş sayı 65537 olmaq e yaygın kimi uzun kimi bu rəqəm m amil olmaz. Bizim düymələri, biz seçeceğiz e = 5 5 ildən 924 ilə nisbətən baş deyil. Nəhayət, biz d arayacaðým daha bir sayı, lazımdır. D tənlik cavab verən bəzi dəyəri olmalıdır de = 1 (mod m). Bu mod m biz modul hesab deyilən bir şey istifadə edəcəyik bildirir. Modul hesab, bir bir sıra bəzi yuxarı bağlı daha yüksək olur o 0 ətrafında geri paketi olacaq. A saat, məsələn, modul hesab edir. 1:59 sonra bir dəqiqə, məsələn, 2:00 edir 1:60 deyil. Bu dəqiqə tərəfdən 0 ətrafında bükülmüş edib 60 bağlı bir üst çatdıqda. Belə ki, 60 0 (mod 60) bərabərdir demək olar və 125 65 bərabərdir 5 (mod 60) bərabərdir. Bizim ictimai əsas cüt e və n olacaq bu halda e 5 və n 989 edir. Bizim xüsusi düyməsi, cüt d və n olacaq bizim halda olan 185 və 989-dir. Orijinal primes p və q görünmür edək ki, hər yerdə bizim özəl və ya ictimai düymələri ilə. İndi açarları bizim cüt ki, biz şifrelemek necə nəzər edək və decrypt bir mesaj. Mən, Rob bir mesaj göndərmək istəyirəm o bu əsas cüt yaratmaq üçün biri olacaq. Sonra mən istifadə edəcəyik onun ictimai düyməsi üçün Rob isteyeceğiz ona göndərmək üçün mesaj şifrelemek. Rob mənə onun ictimai əsas bölüşmək üçün Unutmayın, tamamilə OK. Amma öz şəxsi əsas bölüşmək tamam olmaz. Mən onun xüsusi açarı nə heç bir fikir yoxdur. Biz bir neçə chunks bizim mesaj m qədər qıra bilər bütün sonra n daha kiçik və o chunks hər şifrelemek. Biz 4 chunks qədər qıra bilər string CS50, şifrelemek lazımdır məktub başına bir. Mənim mesaj şifrelemek üçün, mən çevirmək lazımdır rəqəmli nümayəndəliyinin bir növ. Nin mənim mesaj simvol ilə ASCII dəyərlər concatenate edək. Bir mesaj m şifrelemek üçün Mən e (mod n) c = m hesablamaq lazımdır. Amma m, n daha kiçik olmalıdır və ya başqa tam mesaj modulo n ifadə edilə bilməz. Biz n daha kiçik olan bir neçə chunks, daxil m qədər qıra bilər və bu chunks hər şifrelemek. Bu chunks hər Şifreleme, biz almaq c1 olan 5 = 67 (MOD 989) hansı = 658. Ikinci yığın biz 5 (MOD 989) 83 mövcut hansı = 15. Üçüncü yığın biz 5 (MOD 989) 53 mövcut hansı = 799. Və nəhayət, sonuncu yığın biz 5 (MOD 989) 48 mövcut olan 975 =. İndi Rob bu şifrəli dəyərlər göndərə bilərsiniz. Burada, Rob gedin. Bizim mesaj uçuş olsa, gəlin bir nəzər edək necə ki, biz d üçün dəyəri var. Bizim sayı d 5d = 1 (MOD 924) təmin etmək lazımdır. Bu d 5 modulo 924 və multiplikativ tərs edir. 2 integers, bir və b, uzadılmış Evklid alqoritmi nəzərə alaraq Bu 2 integers ən böyük ortaq bölən tapmaq üçün istifadə edilə bilər. Bu da bizim digər 2 ədəd, x və y, verəcək bir və b = böyük ortaq bölən tərəfindən tənlik balta + qane. Bu bizə kömək edir? Yaxşı, bir üçün e = 5 sayede və b m = 924 biz artıq bu rəqəmlər coprime olduğunu bilirəm. Onların böyük ortaq bölən 1-dir. Bu + 924y = 1 Bookmark 5x verir və ya 5x = 1 - 924y. Amma biz yalnız hər şey modulo 924 qayğı əgər 924y - onda biz açılır. Saat geri düşünün. Dəqiqə əl 1 və sonra tam 10 saat, ötürmək edin biz dəqiqə tərəfdən hələ 1 olacaq bilirik. Burada, 1-də başlayacaq və sonra dəqiq y dəfə ətrafında kesmek biz hələ 1 olacaq. Biz = 1 (MOD 924) 5x var. Və burada x, biz əvvəl aradığınız d eyni Biz uzun Evklid alqoritmi istifadə əgər bu sayı x almaq ki, biz d kimi istifadə etməlidir sayı var. İndi bir = 5 uzadılmış Evklid alqoritmi run bildirin və b = 924. Biz masa metodu deyilən bir üsul istifadə edəcəyik. Bizim masa 4 sütun, x, y, d, və k olacaq. Bizim cədvəl 2 satır ilə off başlayır. Ilk sırada biz sonra 1, 0, 5 olan bizim dəyəri var, və ikinci sıra 0, 1 və b üçün dəyəri olan 924-dir. 4-cü sütun, k, dəyəri nəticə olacaq d dəyəri ilə yuxarıda sırasında d dəyəri ayırıcı ilə eyni sırada. Biz 924 bölünür 5 bəzi qalan 0 var. Yəni = 0 k var deməkdir. İndi hər bir digər mobil dəyəri yuxarıda mobil 2 satır dəyəri olacaq bu dəfə k yuxarıda sıra mənfi dəyər. 3-cü sıra d başlamaq edək. Biz 5 var - 924 * 0 = 5. 0 olan 1 * 0 - 0 biz var Sonraki və 1 - 0 * 0, 1-dir. Çox pis deyil, belə ki, bu və növbəti sıraya hərəkət edək. İlk k bizim dəyər lazımdır. 924, bəzi qalan 5 = 184 bölünür belə k üçün dəyər 184-dir. İndi 924 - 5 * 184 = 4. 1 - 0 * 184 1 və 0 - 1 * 184 -184 edir. Bütün hüquqlar, növbəti sıra nə edək. K Bizim dəyəri 1 çünki olacaq 5 bəzi qalan 4 = 1 bölünür. Nin digər sütunlar doldurmaq edək. 5 - 4 * 1 = 1. 0 - 1 * 1 = -1. Və 1 - 184 * 1 185-dir. K növbəti dəyər ola bilər nə edək. Biz 4 olan 1, 4 bölünür var kimi Bəli, görünür. Biz 1-ayırıcı olduğunuz Bu halda, belə ki, k bərabərdir Yuxarıda sıra d dəyəri bizim alqoritmi ilə tamamlayın deməkdir. Biz son sırada x = 185 və y = -1 ki, burada görə bilərsiniz. Indi bizim orijinal məqsədi qayıtmaq edək. Biz nəticəsində x dəyəri bu alqoritm çalışan bildirib ki, a (mod b) multiplikativ tərs olardı. Bu 185 5 multiplikativ tərs (MOD 924) deməkdir olan biz d 185 bir dəyəri deməkdir. Olması d = 1 son sırada e m coprime edilib doğrular. 1 deyil Əgər biz yeni bir e seçin olardı. İndi Rob mənim mesajı əgər in görək. Kimsə mənə bir şifrəli mesaj göndərir zaman kimi uzun Mən xüsusi açarı gizli saxlanılır olduğunuz kimi Mən kim mesaj decrypt bilər yalnız bir deyiləm. Decrypt bir yığın c Mən orijinal mesajı hesablamaq olar d gücü (mod n) üçün yığın bərabərdir. D və n mənim xüsusi açarı var unutmayın. Biz decrypt hər yığın onun chunks bir tam mesaj almaq üçün və nəticələri concatenate. RSA Məhz necə təhlükəsiz? Həqiqət, biz bilmirik. Təhlükəsizlik bir mesaj çat bir saldırganın almaq necə uzun əsaslanır RSA ilə şifrelenir. Bir saldırganın ictimai əsas çıxışı var ki, saxla, e və n də var. Təcavüzkarın öz 2 primes, p və q, daxil n amil idarə edin sonra o, uzun Evklid alqoritmi istifadə d hesablamaq bilər. Bu onun hər hansı bir mesajı decrypt üçün istifadə edilə bilər olan özəl əsas verir. Amma necə tez biz integers amil ola bilər? Yenə bilmirəm. Heç kəs bunu bir sürətli yol tapdı hansı verilmiş o deməkdir ki, kifayət qədər böyük n bu unrealistically uzun bir saldırganın edəcək sayı amil üçün. Kimsə faktorinq integers bir sürətli yol aşkar edin RSA sınıq olardı. Lakin, hətta tam factorization mahiyyət yavaş RSA alqoritmi, hələ də bəzi qüsur ola bilər mesajlar asan parol çözme üçün imkan verir. Heç kəs, hələ belə bir qüsur aşkar və aşkar lakin bir mövcud deyil demək deyil. Nəzəri olaraq, kimsə RSA ilə şifrelenir bütün məlumatları oxumaq orada ola bilər. Bir gizlilik məsələnin başqa bit var. Tommy mənim ictimai açarı istifadə bir mesaj şifreleyerek edin və təcavüzkar mənim ictimai əsas istifadə edərək eyni mesaj şifreleyerek təcavüzkarın 2 mesaj eyni olduğunu görəcəksiniz və beləliklə Tommy şifrelenir bilirik. Bu qarşısını almaq üçün, mesajlar adətən təsadüfi bit ilə padded olunur eyni mesaj şifrələnir ki şifrelenir əvvəl Mesaj üzrə padding fərqli olaraq birdən çox uzun kimi müxtəlif görünür. Amma biz chunks daxil messages split necə yadda hər yığın n daha kiçik ki? Bu chunks padding biz şeyi split ola bilər o deməkdir ki, ildən daha chunks daxil padded yığın n daha kiçik olmalıdır. Şifrələmə və parol çözme, RSA ilə nisbətən bahalı və bir çox chunks bir mesaj parçalamaq ehtiyac çox bahalı ola bilər. Məlumatların böyük həcmdə şifrəli olmalıdır və şifresi çözülen edin biz simmetrik əsas alqoritmləri faydaları birləşdirə bilər RSA bu təhlükəsizlik və səmərəlilik həm almaq üçün. Biz burada daxil deyil baxmayaraq, AES bu Vigenère və Caesar ciphers kimi bir simmetrik əsas alqoritm edir amma çox çətindir çat. Əlbəttə ki, biz ortaq bir gizli əsas yaratmadan AES istifadə edə 2-sistemləri arasında, biz əvvəl problem gördüm. Amma indi biz 2-sistemləri arasında paylaşılan gizli əsas yaratmaq RSA istifadə edə bilərsiniz. Biz data göndərən göndərilməsi kompüter arayacaðým və kompüter data alıcı alınması. Alıcı bir RSA əsas cüt və göndərir göndərən ictimai düyməsi. Göndərən bir AES əsas yaradır alıcı-nin RSA ictimai əsas ilə şifreleyerek, və alıcı üçün AES əsas göndərir. Alıcı öz RSA Şəxsi düyməsindən ilə mesaj şifrini açır. Göndərən və alıcı, həm də indi onların arasında ortaq bir AES əsas var. RSA çox şifrələmə və parol çözme da çox daha sürətli olan AES, indi məlumatların böyük həcmdə şifrelemek və alıcı onları göndərmək üçün istifadə edilə bilər, decrypt həmin əsas olan istifadə edə bilərsiniz. RSA çox şifrələmə və parol çözme da çox daha sürətli olan AES, indi məlumatların böyük həcmdə şifrelemek və alıcı onları göndərmək üçün istifadə edilə bilər, decrypt həmin əsas olan istifadə edə bilərsiniz. Biz yalnız paylaşılan əsas transfer RSA lazımdır. Biz artıq bütün RSA istifadə etmək lazımdır. Mən bir mesaj var kimi görünür. Hər kağız təyyarə var nə oxumaq əgər mən tutdu əvvəl etməz Mən xüsusi açar ilə yalnız bir deyiləm, çünki. Iletideki chunks hər decrypt edək. Ilk yığın, 658, biz 185 olan d enerji ilə qaldırmaq 989 olan mod n, 67-ə bərabərdir ASCII-ci məktub C-dir. İndi, ikinci yığın daxil. İkinci yığın, dəyəri 15 var biz 185th hakimiyyətə qaldırmaq olan mod 989, və bu 83-ə bərabərdir ASCII-ci məktub S olan. İndi dəyəri 799 olan üçüncü yığın üçün, biz 185 qaldırmaq mod 989, və bu 53-ə bərabərdir, ASCII-ci karakter 5 dəyəri olan. İndi son yığın üçün olan dəyəri 975 var biz 185 mod 989, qaldırmaq və bu ASCII ildə karakter 0 dəyəri olan 48, bərabərdir. My name Rob Bowden, bu CS50 edir. [CS50.TV] Bütün RSA. Bütün RSA. [Gülüş] Bütün.