Public-Key Verfahren... Ein bisschen Mathe

[oli004]

Hallo zusammen

Das Public Key Verfahren hört sich ja auf dem Papier
sehr gut an...
mit dem public key etwas verschlüsseln, was niemand
anderes wieder entschlüsseln kann, der nicht den
zugehörigen private key besitzt.


Aber wie geht das????

Wie kann man mathematisch gewährleisten, dass man
aus dem public key den private Key nicht berechnen kann

Verschlüsselung macht ja (logischerweise) nur dann Sinn
wenn sie umkehrbar ist...
(Verschlüsselung: A -> B
&&
Entschlüsselung: B -> A)

es dürften also nur umkehrbare (mathematische)
Algorhythmen benutzt werden....
Verschlüsselung:
y = x + 1
y = 2^x
.
.
.
Menge X wird zugeordnet zu Menge Y,
wobei die Abbildung bijektiv (eindeutig
umkehrbar) sein müsste

Entschlüsselung:
y = x - 1
y = log2(x)
.
.
.
Menge Y wird zugeordnet zur Menge X


aber jeden Umkehr-algorhythmus müsste man doch
aus dem ausgangs-algorhythmus (mathematisch)
herleiten können....

Public Key meint aber diese Rückberechnung ginge
nicht

Wie geht das dann?
Wo ist mein Denkfehler?
Wie ist diese Verschlüsselungsmethode also so sicher??

Danke für die Mühe

Gruß Oli4

[Carsten Eilers]

Hallo,

> aber jeden Umkehr-algorhythmus müsste man doch aus dem ausgangs-
> algorhythmus (mathematisch) herleiten können....

Kann man auch.

> Public Key meint aber diese Rückberechnung ginge nicht

Sie geht nicht mit vernünftigen Aufwand, das ist ein Unterschied.
Wenn man ein paar Millionen Jahre rechnen muß, nützt einem Angreifer die theoretische Möglichkeit nichts.

> Wie geht das dann?

Siehe z.B. About Security #76: RSA:

Die Sicherheit des RSA-Verfahrens basiert auf der Faktorisierungsannahme: Es gibt keinen effizienten Algorithmus, um eine gegebene große Zahl in ihre Primfaktoren zu zerlegen. So lange kein effektiver Faktorisierungsalgorithmus bekannt ist, ist RSA für ausreichend große Schlüssel sicher. Für kurze, wie im Beispiel in About Security #76, natürlich nicht. Die lassen sich bei Bedarf mit einem Brute-Force-Angriff berechnen.

> Wo ist mein Denkfehler?

Du denkst, die Rückrechnung ist gar nicht möglich. Das ist sie aber, nur nicht mit vernünftigen Aufwand

> Wie ist diese Verschlüsselungsmethode also so sicher??

Allgemein: Sie ist sicher, weil mindestens eine der verwendeten Rechenmethoden sich nicht mit vernünftigen Aufwand umkehren läßt.

MfG
Carsten