Puste portfele

[ekonokomik]

Tak szafujecie tym "komputerem kwantowym" rozumiejąc przez to jak rozumiem maszynę, zdolną obliczyć klucz prywatny. Ale nie jestem pewny czy to faktycznie jest możliwe. Bardzo trudno znaleźć szacunki ilukrotnie w tego typu obliczeniach hipotetyczny komputer kwantowy byłby szybszy od obecnych (i których obecnych?). Najczęściej pisze się "wielokrotnie" szybszy. Gdzieś przeczytałem "tysiące razy szybszy". No to przyjmijmy x1000.

Czy ktoś wie ile czasu trwałoby teoretycznie złamanie klucza prywatnego w algorytmie używanym przez Bitcoina, na obecnie istniejącym superkomputerze (albo sieci tysięcy zwykłych komputerów)? Potem podzielmy ten czas przez 1000 i zobaczymy czy będzie to rozsądna wartość.

[nostromo8]

Vanitygen. Jednakże dodanie 1 literki go generowanego adresu powoduje 10-100x wydłużenie czasu liczenia.
Tak więc "kopanie adresów" to mrzonka...

Dzięki rav3n
Do 5-6 znaków możnaby było się jeszcze pokusić, ale więcej to już nie koniecznie

[tst]

W przypadku BTC nie chodzi o to o ile szbsze sa kwantowe, tylko o to w czym sa szybsze.
Generowanie hasha w uproszczeniu opiera sie na wykonaniu operacji matematycznej, ktora w "jedna strone" jest latwa dla komputera, a "z powrotem" trudna.
Przykladowo:
Niech nasza operacja matematyczna do hashowania bedzie mnozenie.
a=5
b=3
hash=a*b=5*3=15
Wyliczenie hasha, jak widac, jest algorytmicznie bardzo latwe. Wiec sprawdzenie czy hashe sa poprawne tez jest latwe.
W druga strone algorytm szukajacy dzeilnikow kiedy zna sie tylko wynik juz taki latwy nie jest... dla klasycznego komputera.
Tu wlasnie ujawnia sie kolosalna przewaga komputerow kwantowych. Dla nich skomplikowane dla klasycznych komputerow operacje potrafia byc zaskakujaca proste. Dostepne juz chemiczne modele komputerow kwantowych znajduja dzielniki liczby w "jednym takcie procesora".
I na tym polega zagrozenie ze strony komputerow kwantowych. Zarowno dla BTC jak i np SSL.

[pm7]

Tak szafujecie tym "komputerem kwantowym" rozumiejąc przez to jak rozumiem maszynę, zdolną obliczyć klucz prywatny. Ale nie jestem pewny czy to faktycznie jest możliwe. Bardzo trudno znaleźć szacunki ilukrotnie w tego typu obliczeniach hipotetyczny komputer kwantowy byłby szybszy od obecnych (i których obecnych?). Najczęściej pisze się "wielokrotnie" szybszy. Gdzieś przeczytałem "tysiące razy szybszy". No to przyjmijmy x1000.

Czy ktoś wie ile czasu trwałoby teoretycznie złamanie klucza prywatnego w algorytmie używanym przez Bitcoina, na obecnie istniejącym superkomputerze (albo sieci tysięcy zwykłych komputerów)? Potem podzielmy ten czas przez 1000 i zobaczymy czy będzie to rozsądna wartość.

Komputer kwantowy nie jest "tysiące razy szybszy". On działa na innych zasadach, dzięki czemu wolniej rośnie "trudność zadania" w niektórych przypadkach.
Nas interesuje rozkład liczby na czynniki pierwsze, albo coś podobnego to tej czynności (łamanie kluczy prywatnych).
http://en.wikipedia.org/wiki/Shor%27s_algorithm

On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).[1] Specifically it takes time O((log N)3), demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is substantially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — about O(e1.9 (log N)1/3 (log log N)2/3).

[sxzp]

@ekonokomik muszę Cię zmartwić akurat w dwóch algorytmach, które są ważne w kryptografii czyli faktoryzacji o której pisał @tst oraz przeszukiwaniu zbiorów, kolejno algorytm shora i grovera, odpowiednio zaawansowany komputer składający się z dostatecznej ilości kubitów powinien podawać wynik natychmiast. To nie działa jak klasyczny komputer i ciężko przestawić sposób myślenia jak ktoś w tym bardziej nie siedzi. Meritum zjawisko dekohorencji czyli wypadania ze stanów superpozycji jest niebywale trudno wyeliminować, sprzęt zamknięty głęboko pod ziemią w tem. 0 stopni kelwina (-270 stopni C) a i tak pomiar powoduje wypadanie ze stanu i testuje się zamykanie atomów w pułapkach magnetycznych i sterowanie laserem. Dalej wynik podawany jest natychmiast, ale to nie wynik jak w kalkulatorze tylko pewne prawdopodobieństwo trafnego wyniku. Oznacza to, że i tak będą potrzebne klasyczne superkomputery, które będą sprawdzały kolejne wyniki, aż znaleziony zostanie ten właściwy i to tu może być wąskie gardło. Generalnie nie ma się czego bać na razie w kwestii komputerów kwantowych wszystko palcem po wodzie pisane niedawno naukowych podważyli fakt czy komputery d-wave to w ogóle komputery kwantowe. Robiono eksperymenty dla małych 108 kubitowych układów i potwierdzało to, że kwantowe wyżarzanie w sprzęcie d-wave nie jest jednomodalne więc wskazywało by to na komp kwantowy, ale o wydajności 8 rdzeniowego xeona ponoć dla testów o rząd, dwa, trzy większej trudności wyniki rozmijały się z teorią komputerów kwantowych, co d-wave próbuje obalić tak czy siak to nie zagrożenie i temat na najbliższe lata.

[tst]

Mysle, ze warto uswiadomic sobie bardzo wazny fakt. W momencie powstania w pelni funkcjonalnego komputera kwantowego sens traci zdecydowana wiekszosc wspolczesnie uzywanych mechanizmow szyfrowania i hashowania.
BTC i kryptowaluty sa tu zupelnym marginesem, bo problem dotyka "zwyklych" bankow i sklepow. A tam kwoty zagrozone sa o wiele wieksze.
Kto bedzie atakowac BTC mogac np. przejac karty kredytowe klientow amazon.com?
Rozwiazaniem sa kwantowe algorytmy szyfrujace. Takie algorytmy juz istnieja i tylko czekaja na mozliwosc implementacji w swiecie realnym. Kryptowaluty takze beda musialy przejsc rewolucje kwantowa i tyle.

[sxzp]

to nie do końca tak jest, komputery kwantowe mają zastosowanie w pewnym wąskim zakresie algorytmów. BTC, korzysta z kilku przecież sha, rsa i ripmd przy odpowiednio długich kluczach taka kombinacja nadal zapewnia względne bezpieczeństwo i czas aby przejść na inne algorytmy. Litecoin korzysta z innej mieszanki o rząd wielkości lepiej zabezpieczonej. Złamanie kluczy to nadal będzie musiała być praca komputera kwantowego i duużo pracy zwykłego superkomputera. A w dużych bankach i wojsku od dawna już stosuje się szyfrowanie kwantowe bozony, polaryzacje, kryształ...

[hanti]

Vanitygen. Jednakże dodanie 1 literki go generowanego adresu powoduje 10-100x wydłużenie czasu liczenia.

Kod: Zaznacz cały

C:\raf\vg>vanitygen.exe 1nosto
Difficulty: 15318045009
[343.28 Kkey/s][total 1179392][Prob 0.0%][50% in 8.6h]

C:\raf\vg>vanitygen.exe 1nostor
Difficulty: 888446610538
[355.68 Kkey/s][total 751360][Prob 0.0%][50% in 20.0d]

C:\raf\vg>vanitygen.exe 1nostorm
Difficulty: 51529903411245
[361.00 Kkey/s][total 1252864][Prob 0.0%][50% in 3.1y]

C:\raf\vg>vanitygen.exe 1nostormo
Difficulty: 2988734397852220
[338.42 Kkey/s][total 1410304][Prob 0.0%][50% in 194.1y]

C:\raf\vg>vanitygen.exe 1nostormo8
Difficulty: 173346595075428786
[356.37 Kkey/s][total 2364160][Prob 0.0%][50% in 10691.4y]

Tak więc "kopanie adresów" to mrzonka...

jakbys uzyl oclvanitygen.exe to by bylo duzo szybciej ;p

[rav3n_pl]

Przy 10^50 lat co za różnica?

[majkel_94]

Nie wiem jak kwantowymi komputerami chcecie odwracać skróty...

Przecież jak mam funkcję skrótu, np. kombinacja mnożenia i dodawania dwóch liczb. Na wejściu 3 i 2, na wyjściu 18. Masz liczbę 18 i jak chcesz w drugą stronę dojść do tego jakie liczby? Prościej podstawiać i sprawdzać wynik do skutku

[drogowaWiewiorka]

Zanim zaczniecie stosować zmodyfikowany algorytm Shora do łamania ECDSA (:D) przypominam, że ciągle czeka nagroda dla osoby, która udowodni, że komputer kwantowy rozwiązuje problemy np-trudne w czasie wielomianowym. Jak jesteście tego tacy pewni to miliony na wyciągnięcie ręki.

[MusX]

dużo ciekawych informacji w tym wątku niemalże w ogóle nie związanych z tematem pierwszego posta, warto by po myślniku lub w nawiasie dopisać co nieco o kwantach.

[sxzp]

@drogowaWiewiorka o krzywych eliptycznych nikt nie wspominał bynajmniej d-wave udowodnił, że algorytm Grovera sprawdza się w 95% przypadków a shora w 50%.

[drogowaWiewiorka]

Zapodasz mi link do tej publikacji?

[pm7]

Nie wiem jak kwantowymi komputerami chcecie odwracać skróty...

Przecież jak mam funkcję skrótu, np. kombinacja mnożenia i dodawania dwóch liczb. Na wejściu 3 i 2, na wyjściu 18. Masz liczbę 18 i jak chcesz w drugą stronę dojść do tego jakie liczby? Prościej podstawiać i sprawdzać wynik do skutku

Nie chcemy odwracać skrótów, tylko wyliczać klucz prywatny z publicznego.

[majkel_94]

Czyli coś jak całkowanie i pochodne? Że pochodną łatwo policzyć, a niektórych całek nie jesteśmy w stanie, mimo że istnieją?

[najw]

To jest matematyka. Musisz w tym dłużej posiedzieć, aby zrozumieć wszystko. Całki i pochodne są kwestią logiki.

_________________
Nextpol.