Kurze Frage zu RSA

[microkernel]

Moin (:
Ich arbeite mich gerade in das RSA Verfahren ein. Nun wurde mir vom Lehrer die Seite hier nahegelegt: http://www.matheprisma.uni-wuppertal.de ... /index.htm Da steht allerdings:

Bei diesen Verschlüsselungen gibt es also zwei Schlüssel, den geheimen private key und den public key. Die beiden Schlüssel sind allerdings nicht gleichwertig.

Und direkt danach:

2 Möglichkeiten:
Der public key wird zum Verschlüsseln vertraulicher Nachrichten an den Besitzer des zugehörigen private keys verwendet. Dieser kann die Nachricht mit seinem private key entschlüsseln.
Den private key kann sein Besitzer [...] ebenfalls zum Verschlüsseln verwenden, um zu zeigen, dass er tatsächlich der Verschicker der Nachricht ist (Authentizität). In diesem Fall kann die Nachricht mit dem public key entschlüsselt werden.

Jetzt bin ich etwas irritiert: Sind die beiden keys dann nicht de facto gleichwertig, wenn man zum entschlüsseln einfach den "anderen" Schlüssel braucht, welcher nicht zum verschlüsseln verwendet wurde?

Grüße, microkernel

[sma]

Ja, es es ist IMHO egal, welchen der beiden Schlüssel man als privat erklärt.

Die Idee einer Signatur ist, nachzuweisen dass eine Nachricht von einer bestimmten Person stammt. Da der öffentliche Schlüssel bekannt ist und meist über eine "Public Key Infrastructure" (z.B. X.500-Zertifikate) glaubwürdig gemacht wurde, dass ein öffentlicher Schlüssel E einer bestimmten Person gehört, kann man nun schlussfolgern, dass eine Nachricht, die sich mit E entschlüsseln lässt, einzig mit dem zugehörigen privaten Schlüssel D verschlüsselt worden sein konnte und damit dass es die per PKI glaubwürdig gemachte Person sein musste, weil nur diese D kennen kann.

Wikipedia hat mehr Informationen, als man über RSA eigentlich haben will, zeigt aber am Schluss ein komplettes einfaches Beispiel. Vielleicht hilft das zum Verständnis.

Stefan

[Hyperion]

Die Frage ist doch eher, wie man "gleichwertig" definiert Ohne den einen nützt einem der andere Schlüssel bei asymmetrischer Verschlüsselung ja nix... welcher ist hier also "wichtiger"?

[cofi]

Um das ganze mal auf deinen Punkt zu bringen: Von der mathematischen Seite sind sie mehr oder weniger gleichwertig. Aber die Bedeutung der Schluessel kommt von aussen, wie das sma so schoen zusammengefasst hat: Die Schluessel werden unterschiedlich benutzt und benoetigen beim Kommunikationspartner den Gegenpart und damit sind sie im Gesamtsystem nicht mehr gleichwertig.

Es sei denn natuerlich man veroeffentlicht den Privaten Schluessel auch. Bei Github zum Beispiel

[microkernel]

Okay danke für die Antworten! (:
Mir bleibt da allerdings noch eine Frage bezüglich der Berechnung der Entschlüsselungsexponenten ´d´:
Es gilt doch:
e * d + k * phi(N) = 1 (hmm... schade das hier kein Latex unterstützt wird)
Angenommen ich habe mir bereits ein ´e´ ausgerechnet und kenne folglich auch schon ´phi(N) = (p-1)*(q-1)´: Wie kann ich dann ´d´ berechnen?

[BlackJack]

@microkernel: Du kannst die Formel ja nach `d` auflösen: `d=-(k*phi(N)-1)/e`. Dann fehlt Dir immer noch `k` zum ausrechnen.

[snafu]

Ich kenne es so, dass man dafür den erweiterten Euklid als Algorithmus nutzt. In Pseudocode sieht das so aus (siehe auch Wikipedia):

Code: Alles auswählen

ERWEITERTER-EUCLID(a,b)
    if b = 0:
        (t, x, d) ← return (a, 1, 0)
    else:
        (t', x', d') ← ERWEITERTER-EUCLID(b,a mod b)
        (t, x, d) ← (t', d', x' -  ⌊a/b⌋d)
        return (t, x, d)

Wobei `a` dein TF(n) (also (p-1)*(q-1)) ist und `b` ist dein `e`.

Die eckigen Dinger um `a/b` sind Gaußklammern und bedeuten, dass an dieser Stelle eine Ganzzahldivision durchgeführt werden soll (also Nachkommastellen vom Ergebnis abschneiden).

Beachte, dass es in den meisten Programmiersprachen sinnvoller ist, den Algorithmus in einer Schleife umzusetzen anstatt rekursiv.

Eine Umsetzung in Python-Code könnte so aussehen:

Code: Alles auswählen

def extended_euclid(a, b):
    for value in a, b:
        if not isinstance(value, int) or value < 0:
            raise ValueError('a and b must be non-negative integers')
    if b > a:
        a, b = b, a
    quotients = []
    while b > 0:
        quotients.append(a // b)
        a, b = b, a % b
    x, d = 1, 0
    for q in reversed(quotients):
        x, d = d, x - q * d
    return a, x, d

Der letzte Wert des zurückgelieferten 3-elementrigen Tupels wäre damit also dein gesuchtes `d`.

Übrigens geht es auch ohne Liste: http://en.wikipedia.org/wiki/Extended_E ... e_method_2