[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. Ponieważ klucz prywatny powinien być trzymane w tajemnicy i tylko klucz prywatny mogą być stosowane w celu deszyfrowania komunikatów, jeżeli 2 użytkownik chce wysłać wiadomości szyfrowane RSA iz powrotem obaj użytkownicy muszą mieć własne publicznego i prywatnego pary kluczy. Wiadomości od User 1 do User 2 używać tylko 2 użytkownika, parę kluczy, oraz wiadomości od użytkownika do użytkownika 1 2 używać tylko 1 użytkownika, parę kluczy. 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 algorytmu jako symetrycznego klucza. Jak 2 komputery, które chcą się komunikować ustanowienie 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 symetryczna Kryptografia klucza 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ć nasz klucz publiczny z kimkolwiek 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. Ponieważ klucz prywatny powinien być trzymane w tajemnicy 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.