Reklama

Zonda - Największa Polska giełda cyfrowych walut
11 sierpnia 2013 | 16:37

Funkcje i Krzywe

W technicznych kręgach związanych z Bitcoinem funkcjonuje informacja, że w obecnej postaci Bitcoin jest częściowo zabezpieczony przed komputerami kwantowymi. ?Wykorzystane? adresy Bitoinowe, które w przeszłości zarówno otrzymywały jak i wysyłały Bitcoiny widnieją pod postacią klucza publicznego w blockchainie. Nieprzychylne siły wspomożone mocą kwantową mogą wówczas poradzić sobie z kryptografią krzywych eliptycznych protokołu Bitcoina. Tymczasem ?niewykorzystane? adresy Bitcoinowe, które mogły w prawdzie otrzymywać Bitcoiny, ale te nigdy z nich nie wypływały, nie są ujawnione, co zapewnia im bezpieczeństwo za sprawą kryptograficznych funkcji skrótu SHA256 oraz RIPEMD-160. Gdy pierwsza transakcja z danego adresu Bitcoin przenosi wszystkie fundusze na inny adres, bezpieczeństwo powinno zostać zachowane. W chwili obecnej większość portfeli zmienia adresy po każdej transakcji, więc dla większości użytkowników zwiększenie bezpieczeństwa pod kontem komputerów kwantowych odbyłoby się za sprawą minimalnej zmiany w oprogramowaniu. Tak wygląda to w teorii, praktyka okazuje się jednak bardziej skomplikowana.

W  portfelu Bitcoinowym każdy z adresów jest przedstawiony w postaci trzech numerów- klucz prywatny, klucz publiczny oraz sam adres. Klucz publiczny wywodzi się z klucza prywatnego za sprawą multiplikacji krzywych eliptycznych. Przy użyciu dzisiejszych komputerów wydobycie klucza prywatnego z publicznego jest w zasadzie niemożliwe. Adres tworzony jest na podstawie klucza publicznego w trzech krokach: Użycie funkcji skrótu SHA256 na kluczu publicznym, następnie przepuszczenie wyniku przez funkcję skrótu RIPEMD-160 oraz dodanie wartości zwanej sumą kontrolną w celu eliminacji błędów (tzn. kiedy pomylisz jeden numer w adresie podczas wysyłania Bitcoinów, nie znikają one bezpowrotnie). Cechą funkcji skrótu, tak jak w przypadku multiplikacji krzywych eliptycznych, jest to, że są one niemożliwe do cofnięcia. Na podstawie adresu, niemożliwym jest znalezienie klucza publicznego bez wypróbowania wszystkich możliwych kluczy publicznych. Tymczasem jednak, komputery kwantowe mają dwie cechy którymi wyprzedzają klasyczne komputery w zakresie łamania kodów- Algorytm Shora oraz Algorytm Grovera. Algorytm Shora jest przydatny przede wszystkim w rozkładaniu na czynniki- np. 1728499 można również przedstawić jako 1129 * 1531. W przypadku siedmiocyfrowych numerów, działanie może zostać wykonane nawet na papierze przy wystarczającej dozie cierpliwości. Gdy jednak w grę wchodzą setki cyfr, konieczne stają się komputery kwantowe. Kwestia rozkładania na czynniki bardzo długich numerów leży u podstaw RSA- najstarszego i pozostającego wciąż w użyciu algorytmu kodowania kluczy publicznych. Algorytm Grovera jest znacznie bardziej ogólny- wykorzystując zbiór liczb oraz własność matematyczną, rozpoznaje on, która liczba jest odpowiednia dla tej własności. Zmodyfikowana wersja algorytmu Shora radzi sobie z kryptografią krzywych eliptycznych, algorytm Grovera tymczasem właściwie ze wszystkim, łącznie z SHA256 oraz RIPEMD-160. Algorytmy różnią się jednak wydajnością. Algorytm Shora redukuje czas łamania kodu krzywej eliptycznej z O(2k/2) do O(k3)- tzn. Jako, że prywatne klucze Bitcoina mają 256 bitów długości, liczba operacji obliczeniowych wymaganych do złamania ich spada z 340 trylionów trylionów trylionów do co najwyżej kilkuset milionów. Algorytm Grovera nie zapewnia aż takiego przyspieszenia. W jego przypadku jest to wręcz jedynie skromne z O(2k) do O(2k/2). W przypadku RIPEMD-160, czyli słabszego z dwóch funkcji wykorzystywanej do tworzenia adresu Bitcoin, oznacza to redukcję z 1.4 trylionów trylionów trylionów do 1.2 trylionów trylionów. Czyni to działanie łatwiejszym, ale na szczęście w dalszym ciągu dość niepraktycznym. Tak, jak opisano powyżej, adresy Bitcoin, z których wychodzą fundusze ujawniają swój klucz publiczny, co czyni łatwym złamanie kodu krzywych eliptycznych u wąskiego gardła za pomocą algorytmu Shora. ?Niewykorzystane? adresy Bitcoin, z drugiej strony ujawniają tylko adres. W tym przypadku w grę wchodzi problem RIPEMD-160 oraz algorytmu Grovera- wyzwanie o ograniczonym potencjale, ale jednak niezaprzeczalne.

W czym problem?

Wiedza na temat komputerów kwantowych zawarta powyżej obejmuje to co oficjalnie o nich wiadomo. W zasadzie nie budzi ona zastrzeżeń. Jeśli adres Bitcoin jest w istocie ?nieużywany?, rzeczywiście nawet komputery kwantowe nie mogą zagrozić powiązanym z nim Bitcoinom. Komplikacje pojawiają się w chwili wydawania funduszy. W celu przesłania Bitcoinów potrzebne jest stworzenie transakcji zawierającej podpis oraz klucz publiczny, który potwierdza, że to posiadacz prywatnego klucza złożył podpis. Problem ujawnia się w tym właśnie miejscu. Dokonując transakcji ujawniasz jednocześnie wszystkie informacje potrzebne posiadaczowi komputera kwantowego do podszycia się pod ciebie- natychmiastowo. Bez komputera kwantowego jest to niemożliwe, ponieważ podpisy oparte na krzywych eliptycznych zawierają jedynie tyle informacji, by umożliwić odkrycie klucza publicznego, a nie prywatnego. Przy wykorzystaniu komputera kwantowego, krzywe eliptyczne nie stanowią zabezpieczenia.

Dokonujesz transakcji wydając wszystkie 100BTC znajdujące się na adresie 13ign przesyłając 10 BTC pod adres 1v1tal w celu zapłaty za zakupione dobra. Następnie, reszta 90 BTC przechodzi na twój nowy adres- 1mcqmmnx. Pierwszy moduł, któremu wysyłasz pieniądze może zmienić adres ?reszty? na taki jaki mu się podoba, wydobyć klucz prywatny z twojego klucza publicznego oraz podrobić twój podpis. Jedynym sposobem na rozwiązanie tego problemu jest właściwie przesłanie funduszy bezpośrednio do mining poola takiego jak BTCGuild lub Slush w nadziei, że ten będzie na tyle uczciwy, że umieści transakcję bezpośrednio w blockchainie. Nawet wtedy jednak jesteś narażony na atak Finney– Nieuczciwy górnik może podrobić Twój podpis i stworzyć odpowiedni blok zawierający nieuczciwą transakcję i stanowiący kontynuację blockchaina począwszy od przedostatniego bloku (zawierającego twoją transakcję). W tej sytuacji, ponieważ długości nowych i starych blochchainów byłyby równe, atakujący miałby 50% szans na to, że to jego blok wygra w starciu. Bezpieczne transakcje stają się  w ten sposób niemożliwe.

Sygnatury Lamporta– Rozwiązanie

Funkcje skrótu służą jako matematyczny odpowiednik zamka. Upublicznienie hasha wartości jest jak wyeksponowanie zamka, natomiast wyjawienie oryginalnej wartości oznacza otwarcie go. Gdy jednak zamek jest już otwarty, ponowne go zamknięcie jest niemożliwe. Problem polega na tym, że zamki same z siebie nie tworzą bezpiecznego sytemu podpisów cyfrowych. Kryptografia krzywych eliptycznych wyposaża nas w ukrytą wartość schowaną za matematycznym zamkiem, która może być dołączona do określonej wiadomości jako zaświadczenie bez ujawniania pierwotnej wartości i nienadającą się do świadczenia o jakiejkolwiek innej wysłanej przez ciebie wiadomości. SHA265 oraz RIPEMD-160 nie spełniają tego zadania. W przypadku Bitcoina wiadomością tą jest transakcja. Kiedy klient Bitcoina zamieszcza transakcję w sieci, w istocie wysyła matematyczne zaświadczenie, że transakcja na określoną sumę wysłana na dany adres została zainicjowana przez posiadacza prywatnego klucza przypisanego do adresu Bitcoinowego z którego została wysłana.

Istnieje konstrukcja, która pozwala rozwiązać tą kwestię bez użycia RSA, krzywych eliptycznych, lub jakiegokolwiek innego systemu kryptograficznego wykorzystującego klucze publiczne: Sygnatury Lamporta. Sygnatura Lamporta jest jednorazową sygnaturą, która omija problem zamka w następujący sposób. Istnieje wiele zamków, a zawartość wiadomości (albo hash wiadomości) decyduje o tym, które zamki mają zostać otwarte. Jeśli ktoś spróbuje podrobić twoją wiadomość, właściwie pewnym jest, że system sygnatur Lamporta zażąda, by ten ktoś otworzył przynajmniej jeden zamek, którego ty wcześniej nie otwierałeś, co przy braku znajomości nieujawnionej ukrytej wartości jest niemożliwe. W przypadku tego systemu, adres Bitcoin wciąż będzie hashem klucza publicznego opartym na SHA256+RIPEMD-160. Różnica będzie polegać wyłącznie na tym, że klucz publiczny będzie składał się z 320 hashy, a nie z punktu w krzywej eliptycznej. Transakcja będzie zawierać klucz publiczny oraz podpis- tak jak ma to miejsce obecnie. Podobnie, tak jak obecnie, sprawdzane będzie, czy klucz publiczny pasuje do adresu oraz czy podpis pasuje do wiadomości oraz klucza publicznego. Podpisy są niepodrabialne: nawet z użyciem algorytmu Grovera, utworzenie fałszywej transkakcji zajmie 280   operacji i będzie musiało objąć ujawnienie wszystkich 160 ukrytych liczb, które już wcześniej zostały ujawnione przez ciebie. W innym wypadku konieczne byłoby 280 * 80 operacji by zwyczajnie złamać wszystkie hashe. Obie liczby to tryliony trylionów obliczeń. Wymagana byłaby jedna zmiana w zachowaniu użytkowników- musieliby zacząć używać każdego adresu tylko raz. Po dwóch użyciach, bezpieczeństwo systemu Lamporta spada do 240, co wciąż może z początku zapewnić bezpieczeństwo przed komputerami kwantowymi, choć już z trudem. Po trzech użyciach system nie jest już zaś bezpieczniejszy niż kryptografia krzywych eliptycznych. Teoretycznie jednak nawet ten problem może zostać częściowo rozwiązany. System sygnatur Merkle?a oparty na pomyśle Lamporta umożliwia tworzenie sygnatur, które można wykorzystać dziesiątki setek, lub nawet tysięcy razy zanim trzeba będzie zrezygnować z danego klucza prywatnego. Maksymalna ilość transakcji na adres limitowana jest jedynie kwestią ograniczenia rozrostu blockchaina. Biorąc pod uwagę aktualną wiedzę oficjalną, komputery kwantowe są wciąż kwestią odległej przyszłości. Najpotężniejszy dotąd komputer kwantowy zdołał za pomocą alorytmu Shora rozłożyć na czynniki liczbę 21. Nagły postęp jest jednak zawsze możliwy- musimy być przygotowani na wypadek, gdyby okazało się, że NSA (National Security Agency) posiada w pełni działające komputery kwantowe. Prawdopodobnie nie poradzilibyśmy sobie z takim wydarzeniem, ale miesiąc wyprzedzenia mógłby już nam pomóc. Gdy tylko pojawi się ostrzeżenie przed kwantowym stanem wyjątkowym, każdy winien przenieść swoje fundusze do wielopodpisowej transakcji pomiędzy klasycznym, ?nieużywanym? adresem Bitcoin a nowym adresem wygenerowanym za pomocą systemu Lamporta. Następnie deweloperzy powinni szybko stworzyć ?Lamportowy? patch dla tak wielu klientów jak to możliwe i nakłaniać wszystkich do aktualizacji. Jeśli proces przebiegnie w granicach kilku tygodni, w momencie, gdy komputery kwantowe staną się zagrożeniem, większość Bitcoinów będzie już zabezpieczona pod ?Lamportowymi? adresami. Dla tych, którzy wciąż będą przechowywać fundusze z użyciem klasycznych adresów (chodzi tu o ?niewykorzystane? adresy. Do tego momentu każdy ?wykorzystany? adres może zostać wyczyszczony), określone instytucje spełnią funkcję zaufanych modułów. Przy wykorzystaniu systemu sygnatur Merkle?a będą one dołączać jeden dodatkowy podpis do każdej transakcji z klasycznego do nowego adresu. By zapobiec przestępstwom oraz atakom Finney, nowe reguły Bitcoina będą wymagały, żeby wszystkie transakcje ze starych do nowych adresów były zatwierdzone przez te instytucje. Wiąże się to z centralizacją, ale będzie to tylko rozwiązanie tymczasowe. Po paru latach cały system będzie mógł zostać porzucony. Wtedy przyjdzie czas już wyłącznie na radość związaną z nowymi możliwościami oferowanymi przez komputery kwantowe.

Artykuł na podstawie: http://bitcoinmagazine.com/bitcoin-is-not-quantum-safe-and-how-we-can-fix/

Reklama

Zonda - Największa Polska giełda cyfrowych walut