[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.
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.