GRENZWERK

Forschungsjournal: P vs NP, Untergrenzen & SHA-256

THEORY — P vs NP und warum SHA-256 als schwer gilt

Begleitnotiz zum Laborlog (README.md). Zielgruppe: erfahrene Softwareentwickler, die die Mathematik hinter "P vs NP" und hinter der vermuteten Härte kryptografischer Hashfunktionen verstehen wollen. Keine Angriffsrezepte, nur Begriffe, Ergebnisse und Quellen.

1. P, NP, NP-vollständig

Entscheidungsproblem. Eine Sprache L ⊆ {0,1}* — "Ist die Eingabe x in L?". Komplexität wird in der Eingabelänge n = |x| gemessen, und zwar asymptotisch und im schlechtesten Fall.

  entscheidet. Faustregel "effizient lösbar".

  |w| ≤ poly(n) besitzt, den ein Polynomialzeit-Verifizierer V(x, w) prüfen kann.
  Faustregel "Lösung schwer zu finden (vielleicht), aber leicht zu prüfen". Äquivalent:
  von einer nichtdeterministischen Maschine in Polynomialzeit entscheidbar.

  Millennium-Probleme des Clay Mathematics Institute.

  (Karp-Reduktion, A ≤ₚ B). **NP-vollständig** = NP-schwer *und* in NP.

  NP-vollständig. Karp (1972) zeigte danach 21 weitere klassische Probleme als NP-vollständig
  (Clique, Rucksack, Hamiltonkreis, ...). Ein Polynomialzeitalgorithmus für *ein*
  NP-vollständiges Problem ergäbe P = NP.

Intuition für Entwickler: Ein NP-Problem ist ein Suchproblem mit einem schnellen Unit-Test. SAT ist "universell", weil man jeden Polynomialzeit-Verifizierer als Schaltkreis hinschreiben und den Schaltkreis in eine CNF-Formel übersetzen kann (Tseitin-Kodierung). Genau das macht sha_sat.py mit (reduzierten Runden von) SHA-256.

2. Warum ein Hash-Urbild "in NP" liegt — und die Feinheit dabei

Sei H eine Hashfunktion. Die Suchfrage "finde x mit H(x) = y" hat einen offensichtlichen Zeugen: x selbst. Prüfen heißt H(x) einmal berechnen — für SHA-256 linear in der Nachrichtenlänge. Als Entscheidungsproblem formuliert (damit man Suche per Bit-für-Bit-Präfixabfrage darauf zurückführen kann):

PRE_H = { (y, p, n) : es gibt x mit |x| ≤ n, x beginnt mit Präfix p, und H(x) = y }

Der Zeuge ist x, der Verifizierer rechnet H(x) und vergleicht → PRE_H ∈ NP. Mit P = NP könnte man durch ≤ n Präfixabfragen ein Urbild in Polynomialzeit konstruieren (Suche-auf-Entscheidung- Reduktion). Daher die verbreitete Aussage "P = NP bricht die Kryptografie".

Die Feinheit: SHA-256 ist eine feste, endliche Funktion mit 256 Bit Ausgabe. Asymptotische Komplexität ist über endlichen Objekten bedeutungslos: Jedes endliche Problem ist formal O(1) (eine Nachschlagetabelle mit 2^256 Einträgen ist "konstant"). Saubere Aussagen benötigen eine Familie H_n (z. B. Ausgabelänge, Wortbreite oder Rundenzahl wachsen mit n). Für SHA-256 selbst ist die relevante Größe daher keine Komplexitätsklasse, sondern eine konkrete Zahl: Bitoperationen bzw. Hashauswertungen, die ein bester Angriff braucht ("konkrete Sicherheit", vgl. Bellare–Rogaway). Die Mini-SHA-Familie im Labor (Wortbreite 8/12/16) ist genau der Versuch, so eine Familie empirisch zu messen.

3. Warum ein Beweis von P = NP nicht automatisch einen praktischen Algorithmus liefert

  1. Riesige Polynome und Konstanten. P sagt nur "O(n^k) für irgendein k". Ein Algorithmus mit
   n^1000 oder mit Konstante 2^1000 ist polynomiell und trotzdem völlig nutzlos
   ("galaktischer Algorithmus"). Reales Beispiel milderer Art: der AKS-Primzahltest (Agrawal,
   Kayal, Saxena 2004) bewies PRIMES ∈ P, praktisch wird aber weiterhin mit den schnelleren
   probabilistischen Tests (Miller–Rabin) gearbeitet.
  1. Nichtkonstruktive Beweise. Man kann die Existenz eines Polynomialzeitalgorithmus
   beweisen, ohne ihn anzugeben. Prominent: Der Graph-Minor-Satz von Robertson–Seymour impliziert,
   dass jede minorenabgeschlossene Graphklasse in Polynomialzeit erkennbar ist — über eine
   endliche Liste verbotener Minoren, die man im Allgemeinen nicht kennt.
  1. Levins universelle Suche zeigt die Kehrseite: Falls P = NP, gibt es einen *explizit
   angebbaren* Algorithmus, der NP-Suchprobleme in Polynomialzeit löst (er simuliert alle
   Programme parallel und prüft deren Ausgaben). Er ist "optimal bis auf einen konstanten
   Faktor" — aber dieser Faktor ist exponentiell in der Länge des unbekannten guten Programms.
   Formal polynomial, praktisch wertlos.
  1. Endliche Größe zählt. Selbst ein n^3-Algorithmus nützt bei SHA-256 nur, wenn die
   versteckte Konstante deutlich unter 2^256 bleibt — der Asymptotik ist das egal.

4. Warum P ≠ NP allein die Sicherheit von SHA-256 nicht begründet

Umgekehrt würde ein Beweis von P ≠ NP für Hashfunktionen fast nichts liefern:

  Kryptografie braucht, dass *zufällige* Instanzen (zufälliger Zielwert y = H(x) für zufälliges x)
  fast immer schwer sind. Es gibt NP-vollständige Probleme, deren typische Instanzen leicht sind
  (z. B. zufälliges 3-SAT weit weg von der Phasenübergangsschwelle).

  aber für jeden effizienten Gegner ist die Wahrscheinlichkeit, zu f(x) bei zufälligem x
  *irgendein* Urbild zu finden, vernachlässigbar. Bekannt: Existenz von Einwegfunktionen ⇒ P ≠ NP.
  Die Umkehrung ist offen. Impagliazzos "Fünf Welten" (1995) beschreibt die möglichen Universen:
  *Algorithmica* (P = NP), *Heuristica* (NP schwer nur im Worst Case), *Pessiland* (schwere
  Durchschnittsprobleme, aber keine Einwegfunktionen), *Minicrypt* (Einwegfunktionen existieren,
  Hashing/Signaturen möglich), *Cryptomania* (auch Public-Key). Wir *hoffen*, in Cryptomania zu
  leben; bewiesen ist keine dieser Welten.

  nicht, dass gerade SHA-256 eine ist. Für SHA-256 gibt es keine Reduktion auf ein
  wohlstudiertes mathematisches Problem (anders als bei RSA/Faktorisierung oder Gitterverfahren).
  Seine Sicherheit ist eine **heuristische, empirische Annahme**.

  eher ein Merkmal: Probleme mit garantiert genau einer/wenigen Lösungen und "strukturlosem"
  Verhalten passen schlecht zu NP-Vollständigkeit (vgl. die Klasse TFNP für totale
  Suchprobleme, und den Befund, dass NP-vollständige Probleme unter plausiblen Annahmen keine
  geeignete Basis für Einwegfunktionen liefern).

5. Warum SHA-256 trotzdem als schwer gilt

Generische Schranken. Für eine ideale Zufallsfunktion mit 256 Bit Ausgabe kostet - ein Urbild bzw. zweites Urbild ≈ 2^256 Auswertungen (Brute Force), - eine Kollision ≈ 2^128 (Geburtstagsparadoxon). Quantencomputer helfen nur polynomiell: Grover (1996) senkt die Urbildsuche auf ≈ 2^128 Quantenschritte; für Kollisionen bringen Quantenalgorithmen bei realistischen Kostenmodellen kaum Vorteil (Bernstein 2009). Zum Maßstab: 2^128 Operationen liegen jenseits jeder physikalisch plausiblen Rechenleistung; die gesamte Bitcoin-Mining-Leistung liegt grob bei 2^95 SHA-256- Auswertungen pro Jahr (Größenordnung 10^21 Hashes/s) — immer noch um den Faktor 2^33 unter 2^128.

Design. SHA-256 (NIST FIPS 180-4) ist eine Merkle–Damgård-Konstruktion über eine Kompressionsfunktion mit 64 Runden aus Addition mod 2^32, Rotationen und bitweiser Logik (ARX-Stil plus Ch/Maj). Die Mischung von Arithmetik über ℤ/2^32 und über GF(2) verhindert, dass eine einzige algebraische Sichtweise die Funktion vereinfacht; der Nachrichtenexpansions-Plan sorgt dafür, dass jedes Nachrichtenwort in vielen Runden wieder auftaucht. Nach wenigen Runden ist jede Ausgabe ein hochgradiges, "zufällig aussehendes" Polynom der Eingabe (Lawineneffekt). Die Laborbefunde spiegeln das: Cube-Summen sehen nach ~6 Vorwärtsrunden zufällig aus, und ab Runde 17 ist das einfache Zurückrechnen nicht mehr möglich (README.md, Step 3).

Empirische Evidenz: Sicherheitsmarge. Jahrzehnte öffentlicher Kryptanalyse haben nur rundenreduzierte Varianten gebrochen. Größenordnung der veröffentlichten Ergebnisse (Stand der Literatur, grob): - praktische Kollisionen: 31 von 64 Schritten (Mendel–Nad–Schläffer 2013; Li–Liu–Wang,

  EUROCRYPT 2024),

  (Khovratovich–Rechberger–Savelieva, FSE 2012),

Generische Solver als Indiz. SAT-Solver sind sehr gut auf strukturierten industriellen Instanzen, aber bei Hash-Urbildern finden sie keine Abkürzung: Im Labor skaliert CaDiCaL grob mit 2^(0,8k) bei großer Konstante und ist für alle getesteten Größen langsamer als Brute Force (README.md, Step 1/3). Das passt zur Erwartung, dass gut entworfene Hashfunktionen keine Struktur bieten, die Konfliktlernen ausnutzen könnte.

6. Warum P vs NP so schwer zu beweisen ist (Barrieren)

Drei Ergebnisse zeigen, dass die naheliegenden Beweistechniken prinzipiell nicht reichen: - Relativierung (Baker–Gill–Solovay 1975): Es gibt Orakel A mit P^A = NP^A und Orakel B mit

  P^B ≠ NP^B. Beweise, die nur Simulation/Diagonalisierung nutzen, gelten für alle Orakel und
  können die Frage daher nicht entscheiden.

  Schaltkreis-Untergrenzen-Beweise würde — falls sichere Pseudozufallsfunktionen existieren —
  sich selbst widerlegen. Hübsche Pointe: Gerade die Existenz guter Kryptografie macht
  "natürliche" Beweise von P ≠ NP unmöglich.

  algebraische Techniken wie Arithmetisierung.

Folge: Konsens in der Community ist P ≠ NP (Umfragen von Gasarch: deutliche Mehrheit), ein Beweis gilt aber als weit entfernt. Die Kryptografie verlässt sich deshalb nicht darauf, sondern auf konkrete, öffentlich geprüfte Annahmen und Sicherheitsmargen.

7. Kurzfassung

Aussage Status
Hash-Urbild prüfen ist leicht → Urbildsuche ∈ NP wahr (für eine Familie H_n)
P = NP ⇒ SHA-256 praktisch gebrochen nein, nicht automatisch (Konstanten, Nichtkonstruktivität, feste Größe)
P ≠ NP ⇒ SHA-256 sicher nein (Worst vs. Average Case; keine Reduktion für SHA-256)
Einwegfunktionen existieren ⇒ P ≠ NP wahr; Umkehrung offen
SHA-256 sicher heuristische Annahme, gestützt auf Design + ~25 Jahre Kryptanalyse + Rundenmarge

Quellen

  (Kap. 2: NP; Kap. 9: Kryptografie; Kap. 23: Natural Proofs).

  Problembeschreibung).

  Obsolete?", SHARCS 2009.

  EUROCRYPT 2013.

  Skein-512 and the SHA-2 Family", FSE 2012.