Bitcoin, Kryptographie und Quantencomputer

[The Statistician]

In dem Thread soll es um das Thema Quantencomputer und Bitcoin bzw. Kryptographie gehen. Mit kryptographischen Algorithmen hat jeder im Alltag u.a. via Internet zu tun und mit Quantencomputern sind einige der aktuell gängigen Algorithmen, insbesondere für digitale Signaturen, potentiell unsicher. Ein bekannter Quantum-Algo ist beispielsweise Shors Algorithm, welcher sehr effizient bei der Faktorisierung großer Zahlen ist, was bei gängigen Algorithmen wie RSA die Grundlage darstellt.

 

Von der NIST (National Institute of Standards and Technology) gibt es bereits seit vielen Jahren ein Projekt zu genau diesem Thema, in welchem es darum geht Algorithmen zu identifizieren, die quantum-resistent sind:

Post-Quantum Cryptography Standardization

NIST to Standardize Encryption Algorithms That Can Resist Attack by Quantum Computers

 

Gerade bei Bitcoin wird dieses Thema immer sehr gerne stark diskutiert, da viele wissen, dass es sich hier um Kryptographie handelt. Das potentielle Sicherheitsrisiko ist jedoch in vielen Bereichen präsent und folglich wird man dafür ohnehin eine Lösung benötigen. Bei Bitcoin kann eine mögliche Anpassung via Soft oder Hard Fork umgesetzt werden, sofern sich in Zukunft die Notwendigkeit abzeichnet. Das kann beispielsweise ähnlich ablaufen wie bei Schnorr Signature. Generell dürfte es sich ähnlich verhalten wie in allen anderen Bereichen, in denen die Algos ausgetauscht werden müssten.

 

Bei Bitcoin sollte man zudem zwischen SHA-256 und dem Algo für die digitale Signatur (ECDSA) unterscheiden. Für letzteres stellt Shors Algo ein entsprechendes Risiko dar, sofern der Public Key der eigenen Wallet bekannt ist (siehe u.a. P2PKH). So kann man dann den Private Key auf Basis des Public Keys ableiten. Für SHA-256 kann zwar Govers Algo genutzt werden, um die erforderliche Zeit zu minimieren, jedoch ist der Aufwand nach wie vor zu groß und stellt derzeit kein Sicherheitsproblem dar. Govers Algo ist auch kein effizienter Algorithmus, da der Aufwand auch hier nach wie vor exponentiell zunimmt. Zudem dürfte es sich beim Mining eventuell ähnlich verhalten wie in der Vergangenheit (CPU > GPU > ASIC), sofern es irgendwann rentabel und nutzbar werden sollte.

 

Nachtrag

Da hier in dem Thread einige Themen aufgekommen sind und darunter auch rein konzeptionelle Themen angeschnitten und teils diskutiert wurden, würde ich noch ein paar allgemeine Infos zu Quantencomputern, ein paar Verweise zu dem aktuellen Entwicklungsstand sowie den Limitierungen ergänzen. Denke das ist in dem Thread ganz passend im Eingangspost zu ergänzen, auch wenn es bereits einen separaten Thread zu dem Thema zu geben scheint (aber auch ohne allgemeinen Infos).

 

Bits vs Qubits
Bei Quantencomputern kommen Qubits als grundlegende Einheit zum Einsatz. Im Gegensatz zu Bits, die einen Wert zwischen 0 oder 1 aufweisen, liegt bei Qubits die Eigenschaft vor, dass Werte zwischen 0 und 1 gleichzeitig existieren (Superposition). Derzeit gibt es zwei zentrale Ansätze von Qubits auf denen heutige real existierende Quantencomputer basieren. Diese habe ich weiter unten einmal sehr oberflächlich thematisiert, da hier noch ein paar weitere Informationen sinnig sind.

 

Superposition
Hier handelt es sich um eines der fundamentalen Konzepte, dass ein Quantensystem gleichzeitig in mehreren Zuständen existieren kann. Wichtig ist bei Qubits zu beachten, dass es hier nicht nur um einen diskreten Zustand geht (0 vs 1), sondern um eine Überlagerung (Werte zwischen 0 und 1). Zum Zeitpunkt der Messung kollabiert ein Qubit dann entsprechend in einen der beiden Werte. Was an der Stelle wichtig zu bedenken ist, ist die Differenzierung zwischen Quantenzustand und der Messung des Zustands. Auch wenn Qubits mehrere Zustände gleichzeitig aufweisen können, ist eine Messung nur für einen Zustand möglich. 

 

Verschränkung
Hierbei handelt es sich um einen Zustand mehrerer Qubits, die in einer solchen Weise miteinander verbunden sind, dass der Zustand des einen Qubits den Zustand des anderen beeinflussen kann. Es handelt sich dabei um gezielte Wechselwirkungen zwischen den Qubits.

 

Mit beiden oben aufgeführten Konzepten ist es möglich Prozesse deutlich effizienter zu parallelisieren als mit klassischen Rechnern. Hier handelt es sich um einen theoretisch exponentiellen Anstieg. Bei n Qubits ergeben sich theoretisch 2^n mögliche Zustände, die gleichzeitig repräsentiert werden können. Die Anzahl von Qubits kann man aber nicht problemlos beliebig vergrößern. Die Wahrscheinlichkeit mancher nach wie vor bestehenden Probleme/Herausforderung wird dadurch vergrößert.

 

Nachfolgend mal ein paar grundlegende Herausforderung, die mit der Entwicklung von Quantencomputern verbunden sind.

 

Dekohärenz
Die Kohärenzzeit stellt die Zeitspanne dar, in der ein Quantenzustand stabil und entsprechend ungestört von externen Einflüssen bleibt. Die obigen Konzepte und daraus resultierenden Vorteile können nur mit einem stabilen Quantenzustand genutzt werden. Die Kohärenzzeit definiert folglich auch die maximale Länge der Operation. Eine Dekohärenz tritt dann auf, wenn der Quantenzustand instabil wird. IBM kommt derzeit auf Koheränzzeiten im Bereich von Mikrosekunden (siehe u.a. Eagle’s quantum performance progress). Koheränzzeiten von mehreren Minuten sind aber ebenso bereits möglich. Ich meine auch einmal ein Paper gelesen zu haben, in dem mehrere Stunden geclaimed wurden (gefunden: Nature: Single ion qubit with estimated coherence time exceeding one hour). Muss man aber teils mit Vorsicht genießen, da gerade bei der Nutzung vieler Qubits das Thema eine ordentliche Herausforderung darstellt und bei die Nutzung weniger Qubits sehr gute Ausgangsbedingungen darstellen.

 

Messfehler
Bei der Messung liegt aufgrund der Hardware zwangsläufig Noise vor, sprich äußere Faktoren, die das Messergebnis beeinflussen. Ohne Korrektur dessen sind die gemessenen Ergebnisse immer mit einer Unsicherheit behaftet bzw. fehlerhaft. Die Fehlerkorrektur wird allgemein und auch seitens IBM meines Wissens nach derzeit priorisiert, da das eine der zentralen Herausforderungen darstellt. Eine der bekanntesten Ansätze ist ZNE (wer Lust auf ein Rabbit Whole hat, kann hier anfangen: Digital zero noise extrapolation for quantum error mitigation).

 

Crosstalk
Geht in Richtung des obigen Problems bzgl. Noise, nur dass es sich in diesem Fall um Fehler handelt, die sich aus unerwünschten (!) Wechselwirkungen zwischen Qubits ergeben. Mit zunehmender Anzahl von Qubits wird die Wahrscheinlichkeit für derartige Fehler größer (exponentieller Anstieg potentieller Wechselwirkungen, erforderliche komplexere Schaltkreise, tendenziell geringere Abstände zwischen den Qubits usw.).

 

Aktuelle Architekturen für Qubits
Bezüglich der aktuell genutzten Architektur gibt es zwei zentrale Konzepte mit real existierenden Quantencomputern. Auf der einen Seite Superconducting Qubits (IBM, Alphabet, Intel), welche auf Supraleitern basieren. Andererseits Ion Traps (IonQ), die auf elektromagnetischen Feldern basiert. Letzteres hat weniger Bedarf für Fehlerkorrekturen und es kommt deutlich später zu einer Dekohärenz (mehrere Sekunden, teils auch Minuten). Dafür fällt die Gatterzeit deutlich länger aus (Mikrosekunden). Ersteres hat eine entsprechend kurze Dauer bis zur Dekohärenz (Mikrosekunden) und es gibt einen höheren Bedarf für Fehlerkorrekturen. Dafür ist die Gatterzeit deutlich kleiner (Nanosekunden). 

 

Neben den beiden Architekturen gibt es noch weitere, die teils auch bei Raumtemperaturen funktionieren. Nur gibt es für diese Fälle bisher keine existierenden Quantencomputer.

 

Aktueller Stand
IBM (u.a. IBM Blog - Quantum Research) und IonQ (u.a. IonQ Blog) bieten Einblicke in deren Entwicklung. Man sollte aber immer bedenken, dass man Fortschritte natürlich möglichst schmackhaft präsentieren möchte. IBM hat derzeit mit Osprey einen Quantencomputer mit 433 Qubits. IonQ kommt hingegen mit Forte auf 36 Qubits. An der Stelle muss man aber bedenken, dass die Anzahl der Qubits nur eine Metrik für die Bewertung der Leistungsfähigkeit eines Quantencomputers darstellt. Beispielsweise kann ein Quantencomputer mit weniger Qubits leistungsfähiger ausfallen als ein Quantencomputer mit deutlich mehr Qubits, sofern sich die Qualität der Qubits entsprechend stark unterscheidet.

 

Sowohl IBM als auch IonQ haben zudem eine Roadmap definiert:

Quelle: IBM & IBM (interaktivere Variante)

 

Quelle (IonQ)

 

Limitierungen, NP, P & BQP

Denke jeder aus der Informatik oder einem verwandten Fach kommt wird das Thema kennen. Hier geht es letztlich um die Frage, ob jede Problemstellung, für die eine Lösung schnell überprüft werden kann (NP), auch schnell gelöst werden kann (P). Es geht folglich um die Fragestellung, ob die Klasse der Probleme, die in Polynomialzeit überprüfbar sind (NP), identisch ist mit der Klasse der Probleme, die in Polynomialzeit lösbar sind (P). In dem Thread habe ich bei nahezu allen Beiträgen immer von Effizienz geschrieben, da intuitiv verständlicher als Polynomialzeit. Äquivalent zu klassischen Computern, worauf sich NP und P beziehen, gibt es für Quantencomputer BQP, was alle Probleme umfasst, die mittels Quantencomputern in Polynomialzeit gelöst werden können.

 

Nach meinem aktuellen Stand ist die Ansicht, dass NP != P ist, nach wie vor klar dominierend. Auch für Quantencomputer nimmt derzeit keiner an, dass sämtliche Probleme mit Quantencomputern effizient gelöst werden könnten (BQP = NP, wenn man es äquivalent ausdrücken will). Man darf hier nicht dem Trugschluss unterliegen, dass ein Quantencomputer selbst eine magische Box darstellt, die man auf jedes Problem werfen kann und eine Lösung in kürzester Zeit ausspuckt. Das erinnert mich übrigens stark an Diskussionen mit Kunden / Abteilungen, wenn es um das Thema KI geht und man erst einmal viel Zeit damit verbringen muss die Erwartungen in eine angemessene Richtung zu lenken. Nichts desto trotz muss man bedenken, dass es hier keinen Beweis gibt. Weder für die eine noch für die andere Variante. Und ob es jemals einen solchen Beweis geben wird, steht auch in den Sternen. Aus rein theoretischer Perspektive kann man daher weder das eine noch das andere mit Sicherheit ausschließen. Das führt jedoch auch dazu, dass man nicht davon ausgehen kann, dass BQP = NP ist.

 

Das Grundproblem besteht an der Stelle vor allem darin einen effizienten Algorithmus zu definieren. Dieses Problem besteht bei der Nutzung von Quantencomputern und von klassischen Computern in gleichem Maße, nur dass man bei Quantencomputern andere Eigenschaften nutzen kann. Die obigen Konzepte führen ebenso nicht dazu, dass man mit einem Quantencomputer alle Lösungen ausprobieren könnte und in kurzer Zeit die Lösung serviert bekommt (wäre zu schön um wahr zu sein und ist es entsprechend auch). An der Stelle vermute ich, dass genau dieser Trugschluss bei einigen vorliegt. Ein Quantencomputer ist mittels Superposition in der Lage, viele mögliche Lösungen gleichzeitig zu repräsentieren, aber das ist nicht gleichbedeutend mit dem gleichzeitigen "ausprobieren" vieler Lösungen mit damit verbundener Evaluation (weiß nicht wie man das besser ausdrücken kann an der Stelle). Am Ende kann man nur eine der Lösungen bzw. Zustand messen und eine Wiederholung der Messung eines zuvor gemessenen Zustandes ist nicht möglich. Was an der Stelle entsprechend oft untergeht oder teils völlig unbekannt ist, ist die Interferenz mittels Amplituden, um unerwünschte Ergebnisse abzuschwächen und erwünschte Ergebnisse zu verstärken. Die Kernaufgabe eines entsprechenden Quanten-Algos besteht daher darin die Wahrscheinlichkeit für die Messung des richtigen Ergebnisses zu maximieren. Denn am Ende kommt nur ein Messergebnis raus, welches nicht zwingend richtig sein muss. Quantenberechnungen sind entsprechend probabilistisch. Bei klassischen Computern hat man idR deterministische Berechnungen. 

 

Gerade für den hier vorliegenden Kontext ist der letzte Abschnitt besonders wichtig. Shors Algorithm nutzt u.a. Quanten-Fourier-Transformation für effiziente Bestimmung der Perioden und ist am Ende ausschlaggebend für die Interferenz. Bei Lattice Problemen hat man eine gänzlich andere mathematische Struktur (algebraische Struktur vs geometrische Struktur) und benötigt einen anderen Ansatz für dieses Problem, welchen es derzeit noch nicht gibt. Wer an der Stelle annimmt, dass es definitiv eine Lösung gibt, müsste selbige Annahme auch bei klassischen Computern haben. In beiden Fällen muss man das Problem in doch sehr erfinderischer Weise angehen, da kommt man auch bei Quantencomputern nicht drum herum. Man hat lediglich die Möglichkeit andere Eigenschaften nutzen zu können.

 

 

Abseits dessen auch noch einmal an der Stelle der Verweis auf den allgemeinen Thread zum Thema Quantencomputer (Danke für den Hinweis @chirlu):

____

Am 28.1.2024 um 20:29 von cfbdsir:

Am 26.1.2024 um 19:00 von The Statistician:

Eben das von mir hervorgehobene, es sind schlicht andere Problemstellungen. Mit gängigen Quanten-Algos hast du mit Logarithmen und Primzahlen grundlegende Sicherheitsrisiken, da es hierfür effiziente Algos gibt. Shors Algo ist beispielsweise u.a. erheblich effizienter bei der Faktorisierung großer Zahlen (e.g. RSA). Der genannte Algo ist hingegen Lattice basiert, wofür es bisher keinen Quanten-Algo gibt, der das merklich effizienter gelöst bekommt. Sofern es dich interessiert, macht es Sinn dich mit Shortest Vector Problem (SVP) und Closest Vector Problem (CVP) zu befassen. Darauf basiert Lattices bzw. Gitter, wenn der deutsche Begriff genehmer ist. Und für die Lösung beider Probleme gibt es bis heute keinen nennenswert effizienteren Quanten-Algo. Wo wir dann wieder bei dem Aspekt sind, dass für jedes Problem ein entsprechender Algo benötigt wird, ob klassischer Rechner oder Quantencomputer. Letzteres bietet zwar mehr Möglichkeiten, aber auch hier gibt es Limitierungen.

Eben nicht. Wäre dem so, könntest du hierfür auch Shors Algo nutzen, was aber offenkundig nicht funktioniert. Es sind völlig andere Problemstellungen.

Doch das gleiche. Man braucht nur relativ längere Wörter, cda die Gitteraufgaben größere Wortlängen für die Rückrechnung erfordern. Nichts ändert sich. 

Es ist nicht das gleiche Problem und nicht mit einer bloßen "Vergrößerung der Wortlänge" gleichzusetzen. Es ist ein völlig anderes mathematisches Problem bzw. eine komplett andere Problemstruktur. Würde sich "nichts ändern" und es keine gänzlich andere Problemstellung wäre, könntest du bestehende Quanten-Algorithmen nutzen, so wie zuvor bereits hervorgehoben. Oder zumindest ohne große Probleme einen Algo definieren, der das Problem effizient gelöst bekommt. Setz dich am besten mit Quanten-Algos und der Problematik von error terms auseinander, spielt bei den gängigen Algos basierend auf lattice eine essentielle Rolle (siehe LWE im Allgemeinen). 

Zitat

Die Gitteraufgaben haben einen schwächeren Einweg- Charakter, benötigen mehr Speicher und Rechenzeiten aber erfordern Quantenrechner mit deutlich größerer Wortlänge. Sind daher ein paar Jahre länger quantensicher. 

Ein Quanten Algorithmus muss noch nicht existieren. Es reicht die prinzipielle Lösbarkeit des Rechenrätsels.  

 

Nur weil etwas lösbar ist, ist es nicht zwangsläufig effizient lösbar. Gerade letzteres ist der relevante Aspekt bei diesem Thema, denn prinzipiell ist es auch für klassische Algos lösbar. Wenn bisher niemand einen Quantum-Algo definieren konnte, der das spezifische Problem effizient lösen kann, dann kann man nicht gleichzeitig behaupten, dass ein künftiger Quanten-Algo das definitiv effizient genug gelöst bekommen wird. Wer meint, dass es prinzipiell möglich ist, muss schon etwas mehr dazu schreiben. Bisher gab es noch niemanden, der das aufzeigen konnte, daher setzt man derzeit u.a. auf solche Algorithmen. Mit der existierenden Rechenleistung hat es zudem erst einmal nichts zu tun.

 

Du scheinst dich auch nicht mit den beiden genannten Problemen groß befasst zu haben, anders kann ich mir den Post zumindest nicht erklären. Für mich ist es daher auch schwer nachvollziehbar wieso du trotz dessen teils derart selbstsicher falsche bzw. doch sehr sportliche Aussagen tätigst. Man muss kein Mathe studiert haben, um zu verstehen, dass es mathematisch gänzlich andere Problemstellungen sind. Und dennoch meinst du es sei das Gleiche trotz meiner groben/oberflächlichen Ausführung?

 

[chirlu]

vor 1 Stunde von The Statistician:

In dem Thread soll es um das Thema Quantencomputer und Bitcoin bzw. Kryptographie gehen.

 

Verwandter Thread:

 

[Chips]

vor 1 Stunde von The Statistician:

In dem Thread soll es um das Thema Quantencomputer und Bitcoin bzw. Kryptographie gehen. Mit kryptographischen Algorithmen hat jeder im Alltag u.a. via Internet zu tun und mit Quantencomputern sind einige der aktuell gängigen Algorithmen, insbesondere für digitale Signaturen, potentiell unsicher. Ein bekannter Quantum-Algo ist beispielsweise Shors Algorithm, welcher sehr effizient bei der Faktorisierung großer Zahlen ist, was bei gängigen Algorithmen wie RSA die Grundlage darstellt.

 

Von der NIST (National Institute of Standards and Technology) gibt es bereits seit vielen Jahren ein Projekt zu genau diesem Thema, in welchem es darum geht Algorithmen zu identifizieren, die quantum-resistent sind:

Post-Quantum Cryptography Standardization

NIST to Standardize Encryption Algorithms That Can Resist Attack by Quantum Computers

 

Gerade bei Bitcoin wird dieses Thema immer sehr gerne stark diskutiert, da viele wissen, dass es sich hier um Kryptographie handelt. Das potentielle Sicherheitsrisiko ist jedoch in vielen Bereichen präsent und folglich wird man dafür ohnehin eine Lösung benötigen. Bei Bitcoin kann eine mögliche Anpassung via Soft oder Hard Fork umgesetzt werden, sofern sich in Zukunft die Notwendigkeit abzeichnet. Das kann beispielsweise ähnlich ablaufen wie bei Schnorr Signature. Generell dürfte es sich ähnlich verhalten wie in allen anderen Bereichen, in denen die Algos ausgetauscht werden müssten.

 

Bei Bitcoin sollte man zudem zwischen SHA-256 und dem Algo für die digitale Signatur (ECDSA) unterscheiden. Für letzteres stellt Shors Algo ein entsprechendes Risiko dar, sofern der Public Key der eigenen Wallet bekannt ist (siehe u.a. P2PKH). So kann man dann den Private Key auf Basis des Public Keys ableiten. 

Zur Ergänzung: Der Public Key der eigenen Adresse wird erst öffentlich, wenn man mit der Adresse eine Transaktion (Output) tätigt. Empfängt die Adresse nur, ist das nicht der Fall, denn die Bitcoinadresse ist ein Hash (sogar 2x) des Public Keys. 

 

Meine Meinung: Kryptografie bzw jede Technologie hat den Kampf gegen stärker werdende Angreifer bis jetzt immer bewältigt. Lange bevor auch nur der Hauch eines realistischen Angriffs bestünde, wird man den Tausch der relevanten Stellen anpassen. 

[cfbdsir]

vor 3 Stunden von The Statistician:

Es ist nicht das gleiche Problem und nicht mit einer bloßen "Vergrößerung der Wortlänge" gleichzusetzen. Es ist ein völlig anderes mathematisches Problem bzw. eine komplett andere Problemstruktur

Das Ziel von Einwegfunktionen, die von Quantenrechnern später zu überwinden sein werden, ist es nach meinem Mathematikverständnis, den Adressraum so auszuweiten, dass er nicht mehr in den Quantenrechner mit kurzer Wortlänge "reinpasst", sodass er entweder ausprobieren muss wie ein herkömmliche Rechner oder noch längere Worte beherrschen muss. Diese Gitteralgos sind da sehr praktisch. Die Vektorräume sind sehr groß während die Log/Pro. Faktorbasierenden kompakt sind. 

 

Das führt aber automatisch dazu, dass der Einweg Charakter auf herkömmlichen Rechner reduziert wird. Man verwendet derzeit RSA, weil die Rückrechnung bei kurzer Schlüssellänger maximal lang ist. Eine Postquantumockchain wäre dann extrem viel länger und teurer, da die Umkehr Funktion relativ leichter als heute zu berechnen ist. 

vor 1 Stunde von Chips:

Zur Ergänzung: Der Public Key der eigenen Adresse wird erst öffentlich, wenn man mit der Adresse eine Transaktion (Output) tätigt. Empfängt die Adresse nur, ist das nicht der Fall, denn die Bitcoinadresse ist ein Hash (sogar 2x) des Public Keys. 

Wie weißt der Eigentümer, der empfängt das Eigentum nach, falls ein anderer sich als Eigentümer ausweist wenn er nie einen öffentlichem Schlüssel an den Tokenabgebenden versendet? 

vor 1 Stunde von Chips:

Meine Meinung: Kryptografie bzw jede Technologie hat den Kampf gegen stärker werdende Angreifer bis jetzt immer bewältigt

Wird sie auch. Nur bei Bitcoin zu extrem hohen Kosten und dem Verlust der Tokens derjenigen, die nicht ständig mitmigrieren. 

 

Ich habe es so verstanden, dass vom Bitcoin eine Tochterkette gebadet wird, der man sich als Eigentümer von Tokens anschließen kann z. B. Um längere Schlüssel zu verwenden. Die anderen, die nicht mitmachen sind dann ab der technischen Möglichkeit die Umkehr g der Einwegfunktion billig durchzuführen wertlos. 

 

Da die Tokens sehr wertvoll sind werden viele Millionen in die Überwindung der Kryptographischen Hürden von Angreifer investiert. Nirgendwo sonst ist das so lohnenswert. 

vor 3 Stunden von The Statistician:

Nur weil etwas lösbar ist, ist es nicht zwangsläufig effizient lösbar. Gerade letzteres ist der relevante Aspekt bei diesem Thema, denn prinzipiell ist es auch für klassische Algos lösbar. 

Das ist nur eine Frage der Phantasie der Angreifenden und der verfügbaren Rechenleistung herkömmlichen Rechner bzw Anzahl+Genauigkeit der Qbits im Quamtenrechner. 

[Chips]

vor 8 Stunden von cfbdsir:

 

Wie weißt der Eigentümer, der empfängt das Eigentum nach, falls ein anderer sich als Eigentümer ausweist wenn er nie einen öffentlichem Schlüssel an den Tokenabgebenden versendet? 

Wird sie auch. Nur bei Bitcoin zu extrem hohen Kosten und dem Verlust der Tokens derjenigen, die nicht ständig mitmigrieren.

Der Eigentümer (Besitzer des privaten Schlüssels) kann das nur nachweisen (signieren), wenn er den public key veröffentlicht. In der Regel ist das aber erst nötig, wenn der Eigentümer Coins versenden möchte. Ansonsten steht in einer Transaktion der gehashte puplic key ("Adresse") drin und keiner weiß, wem die Adresse gehört (oder ob überhaupt jemand die private keys besitzt). 

Zitat

Ich habe es so verstanden, dass vom Bitcoin eine Tochterkette gebadet wird, der man sich als Eigentümer von Tokens anschließen kann z. B. Um längere Schlüssel zu verwenden. Die anderen, die nicht mitmachen sind dann ab der technischen Möglichkeit die Umkehr g der Einwegfunktion billig durchzuführen wertlos. 

 

Da die Tokens sehr wertvoll sind werden viele Millionen in die Überwindung der Kryptographischen Hürden von Angreifer investiert. Nirgendwo sonst ist das so lohnenswert. 

Das ist wie mit den sensiblen Daten auf einem Windows XP Rechner. Wenn man nicht updated, sind diese in Gefahr. Wenn jemand bedeutende Mengen an Bitcoin hat, muss er eben mal aktiv werden und die Coins an eine sichere Adresse überweisen. Sind da nur Coins im Wert von 2l Milch drauf, lohnt sich das Update wohl genauso wie der Angriff nicht. 

Höchstwahrschenlich würden irgendwann quantenresistente Adressen eingeführt, die zusätzlich zu den bisherigen Adressen genutzt werden können. Es obliegt dann an den Minern und Nodes, ob sie auch die neuen

Tx akzeptieren oder nur bisherige . 

[Chips]

vor 8 Stunden von cfbdsir:

 

Das ist nur eine Frage der Phantasie der Angreifenden und der verfügbaren Rechenleistung herkömmlichen Rechner bzw Anzahl+Genauigkeit der Qbits im Quamtenrechner. 

äh nein. Der SHA256 Hash besteht aus 256bit. Um nur mal von 0 auf 256 bit hochzuzählen, reicht die Energie von Milliarden Sonnen nicht. Bei jedem Hochzahlen muss man mind. ein bit drehen, dafür benötigt man Energie und diese existiert nicht. Einzig die nicht korrekte Anwendung oder das Erzeugen des Ausgangswertes verschafft eine Schwachstelle. Oder der SHA256 selber, welcher aber schon 20 Jahre im Einsatz ist. 

Der SHA512 existiert auch, nochmal ein deutlich anders Niveau, aber verschlingt natürlich auch mehr Energie und Zeit, den anzuwenden. 

 

Quantencomputer arbeiten anders. Theoretisch können die Schlüssel knacken, die mit herkömmlichen Rechnern unerreichbar sind. Wann und ob ist unbekannt. Wer weiß, vlt ist Bitcoins SHA256 plus ECDSA in 100 Jahren immer noch sicher. 

 

Ich meinte, vor 10 Jahren hies es auch schon "in 10-15 Jahren knacken Quantencomputer Bitcoin". Sind immer noch 10 - 15 Jahre... Fliegende Autos und bügelnde Roboter sollten auch längst da sein...

[cfbdsir]

vor 28 Minuten von Chips:

äh nein. Der SHA256 Hash besteht auf 256bit. Um nur mal von 0 auf 256 bit hochzuzählen, reicht die Energie von Milliarden Sonnen nicht

Lol. Quelle? Man braucht bisher 1,42*2^256 Schritte. Das schafft selbst mit herkömmlichen Rechner in einigen Jahrzehnten und das ohne mehrere Dyson-Sphären.

 

Warum nimmt man dann nicht halb so lange Schlüssel? Der Quantencomputer war nicht absehbar als das Verfahren eingeführt wurde. 2001 gelang es die Zahl 15 zu faktorisieren. 2016 ging der erste zum Programmieren-üben mit 5 Qbits ins Internet. .https://www.heise.de/news/IBM-stellt-Quantencomputer-ins-Netz-3196997.html

https://research.ibm.com/blog/quantum-five-years

 

2023 waren frei programmierbare Rechner von IBM mit 433 Qbits möglich. Das annualisierte Wachstum liegt bei 90%. Innerhalb von 10-11 Jahren wird die Anzahl vertausendfacht. 

[cfbdsir]

vor 22 Minuten von Chips:

Ich meinte, vor 10 Jahren hies es auch schon "in 10-15 Jahren knacken Quantencomputer Bitcoin"

In fünf Jahren nicht unmöglich. 

 

Laut

https://nap.nationalacademies.org/read/25196/chapter/6#103

 

Benötigt man für SHA 256 2400 QBits:

Zitat

Even using Grover’s algorithm, it is currently believed to be essentially impossible (with a depth on the order of 2144 T gates on 2400 logical qubits) to break a hash function like SHA256.
National Academies of Sciences, Engineering, and Medicine. 2019. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. https://doi.org/10.17226/25196.

Bei 90% Wachstum p. a. hat IBM die in 2067 oder 2027 erreicht. 

 

Andere Quellen sprechen von mehr Qbits (bis zu einer Millionen, die nötig seien). Das wären dann ca 32 Jahre bei 90% Wachstum p. a. 

 

 

[Chips]

vor 11 Minuten von cfbdsir:

Lol. Quelle? 

Ich suche gerade nach der Quelle. Hier ein paar andere Ergebnisse: 

Wieviele Sonnen bräuchte man, wenn man mit deren Energie nur minen würde, um einen SHA256 zurück zu rechnen? 

Antwort: 1000000000000000000000000000000000000 Sonnen. Leider nimmt man aktuell an, dass es nicht so viele (in entsprechender Größe ) gibt. Nan müsste erstmal noch 100 Milliarden Universen finden. 

Hier in dem Video geht es auch um das Thema: 

 

[cfbdsir]

Das ist so wissenschaftlich wie die Ideen einer Kifferrunde. Glaubst du das und gründestauf solcher Quellenlage den Kauf von Tokens für e htes Geld? 

Vier Mal kürzere Schlüssel lassen sich heute schon mühelos mit herkömmlichen Rechnern öffnen, weshalb man sie nicht mehr verwendet. 

 

Ob sich da Greater fools noch lange finden lassen?

[Chips]

vor 6 Minuten von cfbdsir:

In fünf Jahren nicht unmöglich. 

 

Laut

https://nap.nationalacademies.org/read/25196/chapter/6#103

 

Benötigt man für SHA 256 2400 QBits:

Bei 90% Wachstum p. a. hat IBM die in 2067 oder 2027 erreicht. 

 

Andere Quellen sprechen von mehr Qbits (bis zu einer Millionen, die nötig seien). Das wären dann ca 32 Jahre bei 90% Wachstum p. a. 

 

 

In deiner Quelle heißt es im ersten Satz: "The impact of a quantum computer: A hash function that produces 256-bit outputs is not expected to be threatened by quantum computing. Even using Grover’s algorithm"

 

in deinem Zitat heißt es "2144" Gates. In der Quelle heißt es "2hoch144". Das ist schon was anderes. 

 

Weiter heißt es, dass die Angriffsfläche eher die ist, dass Passwörter weniger Kombinationen haben. Also Passwörter sind nicht beliebig lang und bestehen in der Regel nicht aus zufälligen Zeichenketten wie "gdJsjxh46v58ft6c5re5f", sondern eher sowas wie "Amerika234!". Für Bitcoin ist das nicht relevant. Der gehashte Wert ist sehr lang(alle Transaktionen) und beliebig. 

 

[Chips]

vor 20 Minuten von cfbdsir:

Das ist so wissenschaftlich wie die Ideen einer Kifferrunde.

oh, welche Zahl oder Rechnung war falsch oder unglaubwürdig? 

vor 20 Minuten von cfbdsir:

Glaubst du das und gründestauf solcher Quellenlage den Kauf von Tokens für e htes Geld? 

Ja, ich denke, SHA256 und das angewandte Public Key Verfahren ist sicher. 

vor 20 Minuten von cfbdsir:

Vier Mal kürzere Schlüssel lassen sich heute schon mühelos mit herkömmlichen Rechnern öffnen, weshalb man sie nicht mehr verwendet. 

4mal kürzer im Sinne von 25% der Länge. Wir machen einen Test: Ich hab ein Passwort bestehend aus nur Kleinbuchstaben, 26 Stück. 

Ein Passwort besteht aus einem Buchstaben. Wieviele Rateversuche brauchst du im Schnitt? 

 

Jetzt hab ich ein Passwort mit 4 Buchstaben. Wieviele Versuche brauchst du? 

vor 20 Minuten von cfbdsir:

 

Ob sich da Greater fools noch lange finden lassen?

hm

[The Statistician]

vor 11 Stunden von Chips:

Zur Ergänzung: Der Public Key der eigenen Adresse wird erst öffentlich, wenn man mit der Adresse eine Transaktion (Output) tätigt. Empfängt die Adresse nur, ist das nicht der Fall, denn die Bitcoinadresse ist ein Hash (sogar 2x) des Public Keys. 

Genau, daher auch mein Hinweis bzgl. P2PHK. Gibt aber auch Adressen, bei denen der Public Key direkt öffentlich ist soweit ich weiß, also P2PK (war zu Beginn äquivalent zu P2PKH?). Gibt ja noch weitere Arten, insbesondere SegWit nutzt glaube ich nochmal was anderes (Edit: es ist P2WPKH)

Zitat

Meine Meinung: Kryptografie bzw jede Technologie hat den Kampf gegen stärker werdende Angreifer bis jetzt immer bewältigt. Lange bevor auch nur der Hauch eines realistischen Angriffs bestünde, wird man den Tausch der relevanten Stellen anpassen. 

Sehe ich genauso. 

vor 9 Stunden von cfbdsir:

vor 13 Stunden von The Statistician:

Es ist nicht das gleiche Problem und nicht mit einer bloßen "Vergrößerung der Wortlänge" gleichzusetzen. Es ist ein völlig anderes mathematisches Problem bzw. eine komplett andere Problemstruktur

Das Ziel von Einwegfunktionen, die von Quantenrechnern später zu überwinden sein werden, ist es nach meinem Mathematikverständnis, den Adressraum so auszuweiten, dass er nicht mehr in den Quantenrechner mit kurzer Wortlänge "reinpasst", sodass er entweder ausprobieren muss wie ein herkömmliche Rechner oder noch längere Worte beherrschen muss. Diese Gitteralgos sind da sehr praktisch. Die Vektorräume sind sehr groß während die Log/Pro. Faktorbasierenden kompakt sind. 

Die lattice basierten Algorithmen beinhalten nach meinem Wissen alle zusätzlich noch LWE, CRYSTALS-DILITHIUM nutzt beispielsweise Module LWE, sprich Noise aufgrund der zufälligen Fehler kommt neben der grundlegenden Problematik von SVP oder CVP hinzu. Das stellt zusätzlich ein fundamentales Problem für quantumbasierte Ansätze dar, wenn es um die Frage der Effizienz geht. Zudem wird man mit quantumbasierten Ansätzen nicht für jedes Problem eine signifikante Effizienzsteigerung erzielen, für SVP und CVP nach wie vor nicht der Fall. Da betrachtest du Quantencomputer als eine Art Magic Box für alle mathematischen Probleme. Das verhält sich IMO ähnlich wie bei Leuten, die glauben, dass man mit AI alles gut lösen könnte. Da macht das Erwartungsmanagement immer sehr viel Freude, wenn man erst einmal erklären muss wo überall Limitierungen bestehen und welche Voraussetzungen gegeben sein müssen.

 

Und um das hier nochmal kurz festzuhalten, auch wenn Formeln hier bisschen blöd einzufügen sind, Latex wäre schön 
RSA: n=p×q, wobei p, q Primzahlen
SVP:  minv∈L∖{0}∥v∥ 

 

Bei SVP müsste man eigentlich noch viel ergänzend schreiben, aber grundlegend hast du hier eine gänzlich andere Problemstellung, die mit RSA beispielsweise nicht vergleichbar ist. Kann auch gerne noch mal was passendes raussuchen zu SVP bzw. lattice im Allgemeinen, wäre dann detaillierter (wäre hier etwas speziell und wir sind ja nicht auf Stack Exchange). 

vor 9 Stunden von cfbdsir:

vor 13 Stunden von The Statistician:

Nur weil etwas lösbar ist, ist es nicht zwangsläufig effizient lösbar. Gerade letzteres ist der relevante Aspekt bei diesem Thema, denn prinzipiell ist es auch für klassische Algos lösbar. 

Das ist nur eine Frage der Phantasie der Angreifenden und der verfügbaren Rechenleistung herkömmlichen Rechner bzw Anzahl+Genauigkeit der Qbits im Quamtenrechner. 

Ist jetzt nicht nur auf Kryptographie bezogen, aber du bist scheinbar der Ansicht, dass durch Quantencomputer P = NP ist? Eben alles nur eine Frage der "Fantasie"? Du hast da eine sehr naive Meinung zu dem Thema und lehnst dich mit solchen Aussagen IMO sehr weit aus dem Fenster. Gerade wenn von dir keine Begründung kommt, macht es eine weitere Diskussion doch an sich hinfällig. Der Hinweis auf mangelnde Fantasie oÄ ist inhaltlich jedenfalls nicht sonderlich sinnvoll.

vor 35 Minuten von cfbdsir:

Laut

https://nap.nationalacademies.org/read/25196/chapter/6#103

 

Benötigt man für SHA 256 2400 QBits:

Zitat

Even using Grover’s algorithm, it is currently believed to be essentially impossible (with a depth on the order of 2144 T gates on 2400 logical qubits) to break a hash function like SHA256.
National Academies of Sciences, Engineering, and Medicine. 2019. Quantum Computing: Progress and Prospects. Washington, DC: The National Academies Press. https://doi.org/10.17226/25196.

Bei 90% Wachstum p. a. hat IBM die in 2067 oder 2027 erreicht. 

SHA-256 wirst du aber nicht knacken können, steht doch dort sehr klar. Du kannst Govers Algo dann endlich mal tatsächlich laufen lassen, aber die dadurch erzielte Ersparnis bringt dir am Ende nicht viel (siehe Eingangspost). Daher besteht für SHA-256 aktuell kein nennenswertes Angriffspotential, gibt bisher jedenfalls keinen Quanten-Algo, der hier gefährlich werden kann.

[cfbdsir]

vor 3 Stunden von The Statistician:

Die lattice basierten Algorithmen beinhalten nach meinem Wissen alle zusätzlich noch LWE, CRYSTALS-DILITHIUM nutzt beispielsweise Module LWE, sprich Noise aufgrund der zufälligen Fehler kommt neben der grundlegenden Problematik von SVP oder CVP hinzu

Walelche Folgen hat das auf die U. Kehrbarkeit der Einwegfunktion mittels Quantenrechner und herkömmlichen Digital-Rechnern? 

vor 3 Stunden von The Statistician:

SHA-256 wirst du aber nicht knacken können, steht doch dort sehr klar.

Du hast Recht. 

vor 3 Stunden von Chips:

in deinem Zitat heißt es "2144" Gates. In der Quelle heißt es "2hoch144". Das ist schon was anderes.

Du hast Recht. 

vor 3 Stunden von Chips:

vor 3 Stunden von cfbdsir:

Das ist so wissenschaftlich wie die Ideen einer Kifferrunde.

oh, welche Zahl oder Rechnung war falsch oder unglaubwürdig? 

Das:

 

vor 3 Stunden von Chips:

Antwort: 1000000000000000000000000000000000000 Sonnen. Leider nimmt man aktuell an, dass es nicht so viele (in entsprechender Größe ) gibt. Nan müsste erstmal noch 100 Milliarden Universen finden. 

 

[Chips]

vor 54 Minuten von cfbdsir:

 

Das:

oh, was sind die richtigen Zahlen? Wie rechnest du oder gefällt dir die Referenz zur Energieabgabe der Sonne nicht? 

 

Hier noch: Sammeln wir für 32 Jahre den gesamten Energieoutput der Sonne und hätten einen idealen Computer, könnten wir von 0 bis 2^192 zählen. 

Um auf 2^193 zu zählen, bräuchten wir eben 64 Jahre die Energie, bei 2^194 entsprechend 128 Jahre. 

Nun kannst du selber rechnen, wieviele Jahre oder Sonnen nan braucht, um auf 2^256 zu zählen. 

 

Das ist nur zählen. Nur Zählen. Kein Vergleichen oder Interpretieren. 

Zitat

Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38 × 10−16 erg/K, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2 K would consume 4.4 × 10−16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21 × 10^41 ergs. This is enough to power about 2.7 × 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 10^51 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

https://security.stackexchange.com/revisions/25392/7

(an die Quelle komm ich nicht ran)

[cfbdsir]

vor 16 Minuten von Chips:

, was sind die richtigen Zahlen? Wie rechnest du oder gefällt dir die Referenz zur Energieabgabe der Sonne nicht? 

 

Hier noch: Sammeln wir für 32 Jahre den gesamten Energieoutput der Sonne und hätten einen idealen Computer, könnten wir von 0 bis 2^192 zählen. 

Um auf 2^193 zu zählen, bräuchten wir eben 64 Jahre die Energie, bei 2^194 entsprechend 128 Jahre. 

Nun kannst du selber rechnen, wieviele Jahre oder Sonnen nan braucht, um auf 2^256 zu zählen

Was ist der ideale Computer? Ein idealer Computer dürfte folgende Eigenschaften haben: er verarbeitet unendlich lange Worte in unendlich vielen Rechenwerken in infinitesimaler Zeit mit infinitesimalem Energieaufwand. 

vor 22 Minuten von Chips:

In fact, we cannot even imagine a world where 256-bit brute force searches are possible

Lol. 

[Chips]

vor 17 Minuten von cfbdsir:

Was ist der ideale Computer? Ein idealer Computer dürfte folgende Eigenschaften haben: er verarbeitet unendlich lange Worte in unendlich vielen Rechenwerken in infinitesimaler Zeit mit infinitesimalem Energieaufwand. 

Lol. 

ja kommt drauf an, wie man ideal in dem Kontext definiert. Ich denke aber, du hast nun verstanden, dass der SHA256 mit herkömmlichen Rechnern nie geknackt wird. Mehr wollte ich nicht. 

[cfbdsir]

vor 1 Stunde von Chips:

ja kommt drauf an, wie man ideal in dem Kontext definiert. Ich denke aber, du hast nun verstanden, dass der SHA256 mit herkömmlichen Rechnern nie geknackt wird. Mehr wollte ich nicht. 

Wie sonst? Der ideale Computer ist als Zuse Z1 definiert? 

Selbstverständlich wird der geknackt auch mit herkömmlichen Rechnern. Das Mooresche Gesetz gilt nach wie vor. 

[Chips]

vor einer Stunde von cfbdsir:

Wie sonst? Der ideale Computer ist als Zuse Z1 definiert? 

Selbstverständlich wird der geknackt auch mit herkömmlichen Rechnern. Das Mooresche Gesetz gilt nach wie vor. 

ha, wenn sich laut Moorsche Law die Rechenleistung immer alle 2 Jahre verdoppelt und es keine physikalische (die es gibt, bei spätestens 2-3nm wirds schwer) oder wirtschaftliche (die es gibt, irgendwann lohnen immer höhere Investitionen den Nutzen nicht mehr) Limitationen gäbe, hieße das: Ein 64bit Hash kann laut deiner Aussage leicht geknackt werden. Vlt schaffen Hochleistungsrechner 128bit? In 2 Jahren schafft man dann 129bit.

Wie viele Jahre wäre der SHA256 dann noch sicher? 

[cfbdsir]

vor einer Stunde von Chips:

ha, wenn sich laut Moorsche Law die Rechenleistung immer alle 2 Jahre verdoppelt

Die Rechenleistung eines Chips. Die Anzahl wächst pro Rechner. Die Leistung eines Hochleistungsrechners nimmt viel schneller zu:

1962 1MFlop

 

2022 1,1 EFlopl

 

Das sind 1190 Milliarden Mal mehr Gleitkommo-Operationen innerhalb von 60 Jahren. Zunahme: 58%  p. a. statt41% 

Die Leistung pro Chip nach Moore hat nur um Faktor 1 Mrd  zugenommen. 

 

https://de.m.wikipedia.org/wiki/TOP500

[Chips]

vor 39 Minuten von cfbdsir:

Die Rechenleistung eines Chips. Die Anzahl wächst pro Rechner. Die Leistung eines Hochleistungsrechners nimmt viel schneller zu:

1962 1MFlop

 

2022 1,1 EFlopl

 

Das sind 1190 Milliarden Mal mehr Gleitkommo-Operationen innerhalb von 60 Jahren. Zunahme: 58%  p. a. statt41% 

Die Leistung pro Chip nach Moore hat nur um Faktor 1 Mrd  zugenommen. 

 

https://de.m.wikipedia.org/wiki/TOP500

Lass es von mir aus 100% pro Jahr sein. Wieviel Jahre benötigt man, wenn man heute einen 128bit Schlüssel schafft, um einen 256bit Schlüssel zu schaffen?

[cfbdsir]

Eben war es doch noch mehr als die Energie des Universums.. 

vor 11 Stunden von Chips:

Wieviele Sonnen bräuchte man, wenn man mit deren Energie nur minen würde, um einen SHA256 zurück zu rechnen? 

Antwort: 1000000000000000000000000000000000000 Sonnen. Leider nimmt man aktuell an, dass es nicht so viele (in entsprechender Größe ) gibt. Nan müsste erstmal noch 100 Milliarden Universen finden. 

 

Dann wäre es unendlich lang, weil dann die Energie des Universums ausgeschöpft ist. Lol

 

Greater Fool - bewiesen! 

[hattifnatt]

vor 6 Stunden von Chips:

https://security.stackexchange.com/revisions/25392/7

(an die Quelle komm ich nicht ran)

Google findet z.B.:

https://github.com/Yadav97/cyberSecurity/blob/master/Applied Cryptography (Bruce Schneier).pdf

[cfbdsir]

1980 Waen 56 Bit üblich, da unentschlüsselbar

1990 128 Bit

2000 256 Bit

2020 1024-2048 Bit

 

Das BSA empfielt 2048Bit

 

In weniger als einem Jahrzehnt muss die Schlüssellänge verdoppelt werden. Das BSA geht also entweder da von aus, dass Hacker demnächst die Energie mehrerer Universen anzapfen oder davon, dass man demnächst die Schlüssel öffnen kann. Ganz ohne Quantencomputer. 

 

 

[Maciej]

Nur um mal die Relationen klar zu machen:

115792089237316195423570985008687907853269984665640564039457584007913129639936  // 2^256
                                         1000000000000000000000000000000000000  // Operationen von 1 Trillion EFlop-Rechnern pro Sekunde

Leider scheint das hier der nächste interessante Thread zu werden, der durch diesen Troll kaputtgespamt wird.