Aufgabe 4

[kukugo]

Ich habe ein kleine Fehler gemacht
die Verschluesselung bei mier ist auch : 17502712952585122157418603047178562651163505295924481547515758527

[fake]

weiß jemand was zu der b)?

[salami]

weiß jemand was zu der b)?

Eine Möglichkeit wäre wohl wieder "brute force", also alle Möglichkeiten ausprobieren, bis was richtiges rauskommt. Sonst wüsste ich auch nicht, was man machen könnte.
Man hat v1 und v2 (verschlüsstelter Text mit e1 und mit e2) und weiß dass der Ursprungstext gleich ist.

Vielleicht so irgendwie:

m^e1 mod n = v1
m^e2 mod n = v2

n = (m^e1) * k1 + v1
n = (m^e2) * k2 + v2
(k1, k2 € N)

also
(m^e1) * k1 + v1 = (m^e2) * k2 + v2

Aber läuft wohl wieder auf brute force hinaus.

[Christian S.]

Das macht man so:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

http://www.iti.uni-stuttgart.de/~stanka ... rsa.2.html "Common modulus"

Wer nur einen Tipp will:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Das n ist bei beiden Nachrichten das gleiche

Wer noch einen braucht:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Euklidischer Algorithmus

[Snoop]

Ich habe d per erweitertem Euklidischem Algorithmus berechnet, wie in der Vorlesung.
Nun habe ich allerdings ein negatives d rausbekommen, obwohl d € N sein sollte
Nämlich:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

-21126419409859803121266374069605297534252934684919424098653094821

Der Schlüssel funktioniert auch, für beide Nachrichten. Ich habe das eigentlich so verstanden das es für RSA nur einen Schlüssel gibt, kann mir das jemand erkären?

[SLS]

Ich habe d per erweitertem Euklidischem Algorithmus berechnet, wie in der Vorlesung.
Nun habe ich allerdings ein negatives d rausbekommen, obwohl d € N sein sollte
Nämlich:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

-21126419409859803121266374069605297534252934684919424098653094821

Der Schlüssel funktioniert auch, für beide Nachrichten. Ich habe das eigentlich so verstanden das es für RSA nur einen Schlüssel gibt, kann mir das jemand erkären?

Dein Schlüssel ist kongruent modulo phi(n) zu dem eigentlichen, deswegen funktioniert er. In dem Sinne - dein Schlüssel und der eigentliche sind äquivalent, repräsentieren also dieselbe Zahl modulo phi(n). Nach Definition gilt aber:

was d automatisch zwischen 0 und phi(n)-1 einschränkt, also solltest du für d den positiven Repräsentanten nehmen.

Lange Rede, kurzer Sinn - berechne einfach mod phi(n) von dem, was du bekommen hast, und du bist fertig

[Snoop]

Ahh ok. Ich hab die ganze Zeit d mod n probiert -.-
Danke

[lyzrd]

achja auf dem übungsblatt ist ein link zu einem programm (aribas) mit welchem man die berechnungen auch durchführen kann.

[Rob]

Das macht man so:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

http://www.iti.uni-stuttgart.de/~stanka ... rsa.2.html "Common modulus"

Wer nur einen Tipp will:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Das n ist bei beiden Nachrichten das gleiche

Wer noch einen braucht:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Euklidischer Algorithmus

und noch einer der mir letztes jahr bei einer rsa presentation in der schule sehr geholfen hat...

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

http://en.wikipedia.org/wiki/Modular_exponentiation

[Johann]

Kleiner Tipp für Maple-User: Möchte man K^e mod n berechnen und hat es mit riesigen Zahlen zu tun, kann man das mit K&^e mod n machen. So benutzt Maple intern selbst die verfügbaren Algorithmen um das hinzukriegen, ohne das "&" versucht Maple erst K^e und dann mod n zu berechnen, was eben einen Overflow ergibt.