Gefährdet eine simple Rechenoperation unser Kryptogeld

Gefährdet eine simple Rechenoperation unser Kryptogeld

Jeder hat natürlich schon von den Quantencomputern gehört, Shor's Algorithmus und der Primfaktorzerlegung.

Nur so zur Erinnerung der Algorithmus von Shor ist ein Quantenalgorithmus ,der auf Quanteneffekten beruht und eben diese Primfaktorzerlegung in sagen wir mal Polynomialzeit erlaubt.

Hier kommt gleich meine halbbescheuerte Erklärung von Polynomialzeit für alle deren Zeit kostbar ist und den Begriff noch nicht kennen. Sagen wir mal eine Operation soll auf eine Zahl z.B. 100000 ausgeführt werden. In Polynomialzeit würde bedeuten , dass die Operation jetzt nicht 100000 Schritte benötigt sondern in ca. 6 Schritten erledigt werden kann, was weitaus schneller ist und der Anzahl stellen der Zahl entspricht.

Unser Kryptogeld basiert auf elliptischen Kurven, dem diskreten Logarithmusproblem und einer lustigen Funktion nämlich y²=x³+7. Will jetzt aber nicht auf Details eingehen.

Das Gegenstück zum diskreten Logarithmus ist die diskrete Exponentiation und die ist

x = q^key mod p

oder in Worten Primärwurzel hoch Schlüssel und dann der Divisonsrest von irgendeiner passenden Primzahl.

Um den diskreten Logarithmus davon zu lösen müsste man quasi alle möglichen Zahlen ausprobieren was jetzt wirklich ewig dauern würde. Wirklich bewiesen ist das jetzt aber noch nicht. Irgendwann verglühen auch schwarze Löcher und die strahlen bedeutend weniger Energie ab als ein Glühwürmchen.

Was ist jetzt mit dieser simplen Rechenoperation ?

Ja , die heißt Tetration und hats ziemlich in sich ,weil die relativ schnell unser ganzes Zahlensystem zum kollabieren bringt.

Die Exponentiation ist eigentlich nichts weiteres als ein wiederholtes Mal-nehmen (zur Erinnerung : 3^3 = 3 * 3 * 3 ; oder in Worten: 3 hoch 3 ist 3 mal 3 mal 3 ). Die Tetration wäre dann wiederholtes potenzieren. Man spricht auch von sogenannten Potenztürmen.

3^^3 = 3 ^ 3 ^ 3 = 3 ^ 27

Also selbst dieses recht simple Beispiel hätte schon zig Stellen. Es kommt noch besser

2^^5 = 2^2^2^2^2 = 2^2^2^4 = 2^2^16 = 2^65536

Das wären immerhin schon ca. 19800 Dezimalstellen. Also weit länger als dieser Artikel.

Es ist also logisch das eine Tetration aufgrund der unfassbar großen Zahlen keinen Sinn macht, aber eine diskrete Tetration könnte analog zur diskreten Exponentiation Sinn machen.

https://www.quora.com/Could-some-modified-form-of-Diffie-Hellmann-Key-Exchange-use-Tetration/answer/Matt-Groening-2

Nun kann man eine diskrete Tetration überhaupt in Polynomialzeit lösen? Wahrscheinlich nicht und somit wirds auch nichts mit dem Einsatz in der Kryptographie.

Und was ist jetzt mit der Gefährdung von unserem Kryptogeld ?

Sieht ganz so aus als gäbs da einen entsprechenden Forschungsbericht mit dem Titel A reduction of integer factorization to modular tetration.

Und was schreibt der Markus Hittmeir da Schönes : "In this paper, we show how an efficient algorithm for tetration modulo natural numbers N may be used to compute the prime factorization of N. In particular, we prove that the problem of computing the squarefree part of integers is deterministically polynomial-time reducible to modular tetration."

"Hier zeigen wir euch wie ihr mit einem effizienten Algorithmus für die diskrete Tetration die Primfaktorzerlegung hinkriegt."

oder in anderen Worten "Wenn wir die diskrete Tetration in passabler Zeit hinkriegen, dann haben wir euch bei den Eiern, was euer Kryptogeld angeht."