[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[To jest CS50.] [CS50.TV]
Rzućmy okiem na RSA, powszechnie stosowany algorytm szyfrowania danych.
Algorytmy szyfrujące jak Cezar i szyfrów Vigenère nie są bardzo bezpieczne.
Z szyfru Cezara, atakujący musi tylko spróbować 25 różnych kluczy
na otrzymanie wiadomości na zwykły tekst.
Podczas szyfrowania Vigenère jest bardziej bezpieczny niż szyfr Cezara
z powodu większej przestrzeni szukać kluczy, raz napastnik
wie długości klucza w szyfr Vigenère
co można stwierdzić poprzez analizę wzorców w zaszyfrowanym tekście,
Szyfr Vigenère nie jest dużo bardziej bezpieczny niż Cezara szyfru.
RSA, z drugiej strony, nie jest wrażliwe na takie ataki.
Caesar szyfr i Vigenère szyfr używać tego samego klucza
zarówno do szyfrowania i deszyfrowania wiadomości.
Ta właściwość sprawia, że ​​te szyfrów symetrycznych algorytmów kluczowych.
Podstawowym problemem algorytmów symetrycznych kluczowych
jest to, że opierają się one na jednej szyfrowania i wysyłania wiadomości
i jeden odbiór i odszyfrowywania wiadomości
aby uzgodniły już Upfront klawisza spowoduje oboje używają.
Ale mamy trochę problem z uruchamianiem się tutaj.
Jak 2 komputery, które chcą komunikować ustalenia tajnego klucza pomiędzy nimi?
Jeśli klucz musi być tajne, to musimy znaleźć sposób na szyfrowanie i deszyfrowanie klucza.
Jeśli wszystko, co mamy jest symetryczny klucz kryptograficzny
wtedy właśnie wrócić do tego samego problemu.
RSA, z drugiej strony, wykorzystuje parę kluczy,
jeden do szyfrowania, a drugi do deszyfrowania.
Jeden z nich to klucz publiczny, a drugi klucz prywatny.
Klucz publiczny jest używany do szyfrowania wiadomości.
Jak można się domyślić z nazwy, możemy dzielić się z klucza publicznego
ktoś chcemy bez narażania bezpieczeństwa zaszyfrowanej wiadomości.
Wiadomości zaszyfrowane przy użyciu klucza publicznego
mogą być odszyfrowane tylko z odpowiadającym mu kluczem prywatnym.
Chociaż można udostępnić swój klucz publiczny, należy zawsze zachować w tajemnicy klucza prywatnego.
i tylko klucz prywatny może być użyty do deszyfrowania komunikatów
jeśli 2 użytkownicy chcą wysyłać wiadomości szyfrowane RSA
iz powrotem, obaj użytkownicy muszą mieć własne publicznego i prywatnego pary kluczy.
Wiadomości od użytkownika do użytkownika 2 1
używać tylko 2 pary kluczy użytkownika, oraz wiadomości od użytkownika do użytkownika 1 2
używać tylko parę kluczy użytkownika 1 jest.
Fakt, że są 2 oddzielne klucze do szyfrowania i deszyfrowania wiadomości
sprawia RSA klucz asymetrycznego algorytmu.
Nie potrzebujemy do szyfrowania klucza publicznego w celu wysłania go do innego komputera
ponieważ klucz publiczny i tak.
Oznacza to, że nie posiada RSA tego samego problemu uruchamiania
jak algorytmów symetrycznych kluczy.
Więc jeśli chcesz wysłać wiadomość, używając szyfrowania RSA
okraść, ja najpierw klucza publicznego Roba.
Aby wygenerować parę kluczy, Rob musi wybrać 2 dużych liczb pierwszych.
Numery te będą wykorzystywane w obu kluczy publicznych i prywatnych,
ale klucz publiczny będzie jedynie korzystać z produktu z tych 2 liczb
nie same numery.
Kiedy już zaszyfrowane wiadomości, używając klucza publicznego Roba
Mogę wysłać wiadomość do Rob.
W przypadku komputera, numery faktoringowych jest trudnym problemem.
Klucza publicznego, pamiętaj, używany produkt z 2 liczb pierwszych.
Ten produkt musi mieć tylko 2 czynniki,
które stało się numery, które tworzą klucz prywatny.
W celu odszyfrowania wiadomości, RSA użyje tego klucza prywatnego
lub numery mnożone w procesie tworzenia klucza publicznego.
Bo to jest obliczeniowo trudne uwzględniać liczbę
używane klucza publicznego do wartości podanych w 2 klucza prywatnego
trudno jest atakująca dowiedzieć klucz prywatny
będzie konieczne odszyfrować komunikat.
Teraz chodźmy do niektórych niższych szczegółów szczebla RSA.
Niech najpierw zobaczyć, jak można wygenerować parę kluczy.
Po pierwsze, musimy 2 liczb pierwszych.
Nazwijmy te 2 liczby p i q.
W celu odebrania P i Q, w praktyce będziemy pseudorandomly generować
duża liczba, a następnie użyć test dla stwierdzenia, czy
te numery są chyba pierwsze.
Możemy informować generowania liczb losowych w kółko
dopóki mamy 2 liczby pierwsze, które możemy wykorzystać.
Tutaj niech odebrać p = 23 i Q = 43.
Należy pamiętać, że w praktyce i p powinny być większe numery.
O ile nam wiadomo, większe liczby, tym trudniej jest
złamać zaszyfrowaną wiadomość.
Ale jest to także droższe do szyfrowania i deszyfrowania wiadomości.
Dziś często jest zalecane piq są co najmniej 1024 bitów,
co stawia każdy numer na ponad 300 miejsc po przecinku.
Ale będziemy wybierać te małe liczby, dla przykładu.
Teraz mnożymy p oraz q, aby otrzymać 3rd numer,
które będziemy nazywać n.
W naszym przypadku n = 23 * 43 = 989 co.
Mamy n = 989.
Dalej będziemy mnożyć p - 1 gdzie q - 1
uzyskania 4-sze numer, który my nazywamy M.
W naszym przypadku, m = 22 * ​​42 = 924 co.
Mamy m = 924.
Teraz potrzebujemy liczba e, która jest względnie pierwsze z m
m, a mniej niż.
Dwie liczby są względnie pierwsze lub względnie pierwsze
jeśli tylko dodatnia, że ​​dzieli ich zarówno równomiernie jest 1.
Innymi słowy, największy wspólny dzielnik E i M
musi być 1.
W praktyce często zdarza się, e jest liczbą 65537
dopóki ta liczba nie stało się czynnikiem m.
Dla naszych kluczy, będziemy pick e = 5
od 5 jest względnie pierwsze z 924.
Wreszcie, musimy jeszcze jeden numer, który my nazywamy d.
D musi być jakaś wartość, która spełnia równanie de = 1 (mod m).
Ten mod m oznacza użyjemy coś zwane modułowe arytmetyki.
W arytmetyce modularnej, raz liczba jest wyższa niż niektóre górne
będzie zawijać powraca do 0.
Zegara, na przykład, stosuje modułową arytmetycznych.
Minutę po 01:59, na przykład, jest 2:00,
nie 1:60.
Minut ręka owinięta do 0
po osiągnięciu górnej granicy 60.
Więc można powiedzieć, 60 odpowiada 0 (mod 60)
i 125 do 65 odpowiada odpowiada 5 (mod 60).
Nasz klucz publiczny będzie para i n e
w tym przypadku, gdy jest 5 i e n 989.
Nasz klucz prywatny będzie parę D, N,
co w naszym przypadku jest 185 i 989.
Zauważ, że nasze oryginalne liczby pierwsze p i q nie pojawiają
wszędzie w naszych kluczy prywatnych lub publicznych.
Teraz, gdy mamy parę kluczy, rzućmy okiem na to, jak możemy szyfrować
i deszyfrowania wiadomości.
Chcę wysłać wiadomość do Roba,
tak, że będzie jeden do wygenerowania tego pary kluczy.
Potem pytam Rob jego kluczem publicznym, który będziesz używać
zaszyfrować wiadomość, aby wysłać do niego.
Pamiętaj, że jest to całkowicie w porządku dla Rob do akcji jego klucz publiczny, ze mną.
Ale to nie byłoby w porządku do akcji swojego klucza prywatnego.
Nie mam pojęcia, co jego klucz prywatny jest.
Możemy przełamać naszą m wiadomość na kilka kawałków
wszystkie mniejsze niż N, a następnie każdy z tych szyfrowania kawałki.
Będziemy zaszyfrować CS50 sznurka, którym możemy przerwać na 4 kawałki,
jeden na liście.
Aby zaszyfrować moją wiadomość, będę potrzebował do przekształcenia
jakaś numerycznej reprezentacji.
Miejmy złączyć wartości ASCII z bohaterów mojej wiadomości.
Aby zaszyfrować daną wiadomość m
Będę potrzebował do obliczenia C = M na e (mod n).
M, ale może być mniejsza niż N,
albo pełna wiadomość nie może zostać wyrażona modulo n.
M można przerwać na kilka fragmentów, z których wszystkie są mniejsze niż N,
i szyfrowania każdego z tych kawałków.
Szyfrowanie każdy z tych kawałków, mamy c1 = 67 do 5 (mod 989)
co = 658.
Na naszym drugim fragmencie mamy 83 do 5 (mod 989)
= 15, który.
Na naszym trzecim fragmencie mamy 53 do 5 (mod 989)
co = 799.
I wreszcie, na nasz ostatni kawałek mamy 48 do 5 (mod 989)
co = 975.
Teraz możemy wysłać na te zakodowane wartości Rob.
Proszę, Rob.
Podczas gdy nasz komunikat jest w locie, weźmy inny wygląd
w jaki sposób mam to wartość dla d.
Nasz numer d potrzebne do zaspokojenia 5D = 1 (mod 924).
To sprawia, że ​​d multiplicative odwrotność 5 modulo 924.
Podane 2 liczby całkowite, i B, rozszerzony algorytm Euklidesa
można znaleźć największy wspólny dzielnik tych 2 liczb.
Będzie on również dać nam 2 inne numery, X i Y,
które spełniają równanie ax + by = największego wspólnego dzielnika A i B.
Jak to nam pomoże?
Cóż, podłączając e = 5 dla
i M = 924 b dla
już wiemy, że te liczby są względnie pierwsze.
Ich największy wspólny dzielnik jest 1.
To daje nam 5x + 924y = 1
lub 5x = 1 - 924y.
Ale jeśli tylko o wszystko modulo 924
wtedy możemy upuścić - 924y.
Pomyśl o zegarze.
Jeśli minut ręka jest na 1, a następnie dokładnie 10 godziny mijają,
wiemy minut ręka nadal będzie na 1.
Tu zaczynają się od 1, a następnie owinąć wokół dokładnie y razy,
więc będziemy nadal w 1.
Mamy 5x = 1 (mod 924).
I tu w x jest taka sama, jak D szukaliśmy wcześniej
więc jeśli używamy rozszerzonego algorytmu Euklidesa
otrzymaj liczby x, to liczba powinniśmy używać jako naszego d.
Teraz uruchom rozszerzony algorytm Euklidesa dla a = 5
oraz b = 924.
Użyjemy metodę zwaną metodą tabeli.
Nasza tabela będzie miała 4 kolumny, x, y, d, k.
Nasza tabela zaczyna się z 2 wierszy.
W pierwszym wierszu mamy 1, 0, wówczas nasza wartość, która jest 5,
i drugi rząd nasz oznacza 0, 1, a dla naszych B, która jest 924.
Wartość 4. k kolumnie, będzie wynikiem
podziału wartości D w wierszu nad nim z wartości d
w tym samym rzędzie.
Mamy 5 podzielić przez 924 wynosi 0 z pewnym reszty.
To oznacza, że ​​mamy k = 0.
Teraz wartość każdej innej komórce będzie wartość komórki 2 rzędach nad nim
minus wartość wiersza ponad nim k razy.
Zacznijmy d w 3 rzędzie.
Mamy 5 - 924 * 0 = 5.
Następnie mamy 0 - 1 * 0, który jest 0
i 1 - 0 * 0, który jest 1.
Nie jest tak źle, więc przejdźmy do następnego wiersza.
Najpierw musimy naszą wartość k.
924 podzielone przez 5 = 184 z jakimś pozostałym
więc nasz stosunek k jest 184.
Teraz 924 - 5 * 184 = 4.
0 - 1 184 * 1 i jest 0 - 1 * 184 jest -184.
Dobra, zróbmy następny wiersz.
Nasza wartość k będzie 1, bo
5 podzielić przez 4 = 1 z niektórych pozostały.
Miejmy wypełnienie innych kolumn.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
I 1 - 184 185 * 1 jest.
Zobaczmy, co nasz następny Wartość k będzie.
Cóż, wygląda na to, że mamy 4 podzielone przez 1, czyli 4.
W tym przypadku, gdy mamy do podziału przez 1, że k równe jest
wartość D w powyższym wierszu oznacza, że ​​skończyliśmy z naszego algorytmu.
Widzimy tutaj, że mamy x = 185, y = -1 w ostatnim rzędzie.
Zróbmy teraz wrócić do naszego pierwotnego celu.
Stwierdziliśmy, że wartość x w wyniku prowadzenia tego algorytmu
będzie w mnożnikowy (odwrotność mod b).
Oznacza to, że 185 z 5 odwrotna mnożnikowy (mod 924)
co oznacza, że ​​mają wartość 185 do D.
Fakt, że d = 1 w ostatnim wierszu
sprawdza, e był względnie pierwsze m.
Gdyby nie 1, a następnie będziemy musieli wybrać nowy e.
Teraz zobaczymy, czy Rob otrzymał mojej wiadomości.
Gdy ktoś wyśle ​​do mnie zaszyfrowaną wiadomość
tak długo, jak ja trzymałem klucz prywatny sekret
Jestem jedynym, który może odszyfrować wiadomość.
Aby odszyfrować kawałek c można obliczyć oryginalną wiadomość
jest równa części do potęgi d (mod n).
Pamiętaj, że d i n są z mojego klucza prywatnego.
Aby uzyskać pełną wiadomość od jego kawałki możemy odszyfrować każda porcja
i łączyć wyniki.
Dokładnie tak, jak bezpieczny jest RSA?
Prawda jest taka, że ​​nie wiemy.
Bezpieczeństwo opiera się na jak długo potrwa atakującemu złamać wiadomość
szyfrowane RSA.
Pamiętaj, że atakujący ma dostęp do klucza publicznego,
który zawiera zarówno e i n.
Jeśli atakujący zdoła czynnik N do swoich 2 liczb pierwszych, P i Q,
następnie mogła obliczyć D Korzystanie rozszerzony algorytm Euklidesa.
To daje jej klucz prywatny, który może być użyty do odszyfrowania każda wiadomość.
Ale jak szybko możemy uwzględniać liczby całkowite?
Ponownie, nie wiem.
Nikt nie znalazł szybki sposób to robić,
co oznacza, że ​​z uwagi na tyle duża N
zajęłoby atakującemu nierealistycznie długi
do czynnika numer.
Jeśli ktoś ujawnił szybki sposób liczb faktoringowych
RSA będzie złamane.
Ale nawet jeśli na czynniki z natury powolne całkowitą
algorytm RSA może jeszcze trochę w nim błąd
, że pozwala na łatwe deszyfrowania komunikatów.
Nikt nie znalazł i ujawnił taką wadę jeszcze,
ale to nie znaczy, nie istnieje.
W teorii, ktoś może być tam czytanie wszystkich danych zaszyfrowanych przy RSA.
Jest jeszcze trochę kwestii prywatności.
Jeśli Tommy szyfruje jakąś wiadomość używając mojego klucza publicznego
i napastnik szyfruje sam komunikat używając mojego klucza publicznego
napastnik będzie wiedział, że 2 komunikaty są identyczne
a więc wiem, co Tommy zaszyfrowane.
W celu zapobieżenia temu, komunikaty są zwykle wypełniane przypadkowych bitów
zanim zostały zaszyfrowane tak, że sama wiadomość zaszyfrowana
Wielokrotne wygląda inaczej ile dopełnienie w komunikacie jest inny.
Ale pamiętam, jak mamy podzielić wiadomości na kawałki
, tak że każdy kawałek jest mniejsza niż N?
Wypychanie na kawałki oznacza, że ​​możemy mieć do podziału rzeczy
do jeszcze większej liczby kawałków od wyściełane kawałek musi być mniejsza niż n.
Szyfrowanie i deszyfrowanie są stosunkowo drogie z RSA,
więc potrzeby rozbijania wiadomość do wielu kawałków może być bardzo kosztowne.
Jeśli duża ilość danych musi być zaszyfrowane i odszyfrowane
możemy połączyć zalety kluczowych algorytmów symetrycznych
z tymi z RSA, aby bezpieczeństwo i skuteczność.
Mimo, że nie będziemy się tym tutaj,
AES jest klucz symetryczny algorytm jak Vigenère i szyfry Cezara
ale znacznie trudniejsze do złamania.
Oczywiście, nie możemy użyć AES bez ustanowienia wspólnego klucza tajnego
między 2 systemów, i widzieliśmy problemu z tym wcześniej.
Ale teraz możemy użyć RSA w celu ustalenia wspólnego tajnego klucza pomiędzy 2 systemami.
Zadzwonimy do komputera przesyłającego dane nadawcy
a komputer odbiera dane do odbiornika.
Odbiornik posiada parę kluczy RSA i wysyła
klucza publicznego nadawcy.
Nadawca generuje klucz AES,
szyfruje go z odbiornika RSA klucz publiczny,
klucz i wysyła do odbiornika AES.
Odbiornik dekoduje komunikat z jego klucz prywatny RSA.
Zarówno nadawca, jak i odbiorca mają teraz wspólnego klucza AES między nimi.
AES, który jest znacznie szybciej niż szyfrowania i deszyfrowania RSA,
mogą być teraz używane do szyfrowania dużych ilości danych i wysyłanie ich do odbiornika,
kto może odszyfrować przy użyciu tego samego klucza.
AES, który jest znacznie szybciej niż szyfrowania i deszyfrowania RSA,
mogą być teraz używane do szyfrowania dużych ilości danych i wysyłanie ich do odbiornika,
kto może odszyfrować przy użyciu tego samego klucza.
Potrzebowaliśmy jedynie RSA przenieść klucz udostępniany.
Nie musimy już używać RSA wcale.
Wygląda na to, mam wiadomość.
To nie ma znaczenia, czy ktoś odczytać, co jest na papierze, zanim samolot złapał
bo ja jestem tylko jednym z kluczem prywatnym.
Załóżmy, deszyfrowanie każdego z kawałków w komunikacie.
Pierwszy kawałek, 658, wznosimy się do d mocy, co jest 185,
mod n, która jest 989, jest równa 67,
co jest litera C w ASCII.
Teraz, na drugim kawałku.
Drugi fragment ma wartość 15,
które wędrują na 185-sze władzy,
mod 989, i wynosi ona 83
która jest literą S w ASCII.
Teraz w trzecim fragmencie, który ma wartość 799, to podnieść do 185,
mod 989, i wynosi ona 53,
która to wartość w postaci 5 ASCII.
Teraz do ostatniego kawałka, który ma wartość 975,
możemy podnieść do 185, 989, mod
i to jest równe 48, co jest wartość 0 znaków w kodzie ASCII.
Nazywam się Rob Bowden, a to CS50.
[CS50.TV]
RSA w ogóle.
RSA w ogóle. [Śmiech]
W ogóle.