[17 Krypto] RSA - Einstieg

[Dominik]

Problem der Doppelwoche Nr. 17 (Krypto): RSA - Einstieg

Anmerkungen:
So, mal sehn. Bei den DES-Fragen habt Ihr mich ja schon ziemlich enttäuscht. Ich mein, es war klar, dass wenige sich da rantrauen, aber gar keiner? (Auch der liebe Dennis hat seinem Ruf alle Ehre gemacht )
Diesmal RSA.
Ich hab damit ne Menge Kapitel übersprungen, auch die theoretische Einführung in RSA und PK-Verfahren allgemein.
Das is zwar nicht der beste Weg, aber ich will mal wieder Traffic sehn hier. Fragen kostet nix und Zeit hat man auch, wenn man will. Also hängt Euch mal bissle rein ... würd ich auch tun. ;-))

1)
Public-Key Algorithmen werden in der Praxis häufig zum Austausch eines Schlüssels für ein symmetrisches Verfahren (z.b. DES oder AES) verwendet. Worin liegt der Grund für dieses hybrider Verfahren? Warum ist die alleinige Verschlüsselung mit RSA nicht immer von Vorteil?

2)
In der Praxis ist es manchmal notwendig, dass BEIDE kommunizierenden Parteien Einfluss auf die Schlüsselwhl haben. Hierbei wird verhindert, dass eine der Parteien einen schwachen Schlüssel für ein symmetrisches Verschlüsselungsverfahren wählt, um z.b. aussenstehenden Angreifern Vorteile zu verschaffen. Viele der bekannsten symmetrischen Verfahren wie z.b. IDEA oder DES haben sog. schwache Schlüssel.
Nachrichten die mit diesen schwachen SChlüsseln verschlüsselt worden sind, können leicht aus dem verschlüsselten Text zurückgewonnen werden.

Entwickel ein ähnliches Protokoll wie in Aufgabe 1, bei dem diesmal beide Parteien die Schlüsselwahl beeinflussen. Nehme dazu an, dass sowohl User_A als auch User_B einen privaten und öffentlichen RSA-Schlüssel besitzen.

Anmerkung:
Es gibt sehr viele verschiedene Wege dieses Problem zu lösen. Du brauchst aber nur eine Möglichkeit zu zeigen. ;-))

Lösungen und Lösungsansätze dürfen ab Montag, dem 6. Dezember 2004 (Nikolaus) gepostet werden. Beachtet bitte auch die Allgemeinen Richtlinien zum Problem der Doppelwoche.
Allen Teilnehmern viel Spaß und viel Glück! :rofl:

[mdk]

ach komm, das kanns ja wohl nicht sein dass ich, der nur all 2-3 tage mal 1/4h zeit findet um aufs buboard zu gehen der erste bin welcher hier eine antwort postet. also wirklich...

1.) symetrische verfahren sind um einiges schneller als public-verfahren... das ist soviel ich weiss der einzige grund, korrigiert mich aber gerne falls es noch andere gruende gibt...

2.) hmm, das kommt jetzt einfach so aus dem bauch raus, nach so ca 15 sekunden ueberlegung:
a moechte an b die nachricht m schicken. a schickt zuerst einen mit rsa verschluesselten schluesselrequest r1. b schickt a einen, ebenfalls mit rsa verschluesselten schluessel k1. falls a zufrieden damit ist verschluesselt er m mit k1 und schickt es danach an b, falls er nicht einverstanden ist schickt er ein fu ( ) an b, damit dieser einen neuen schluessel k2 generiert und schickt. das ganze in einer loop bis a endlich zufrieden ist. naja, so ganz ueberzeuggt bin ich davon nicht aber faellt mir gerade nichts schlaueres ein

[Enchanter]

@Dominik
Manchmal glaube ich deine Aufgaben nicht zu verstehen.
Beim RSA Verfahren, haben doch immer beide Kommunikationspartner einfluss auf den Schlüssel?

@mdk
Was genau, ist ein :
[zitat]
rsa verschluesselten schluesselrequest
[/zitat]
Ich komm da nicht dahinter?

[Dominik]

@Dominik
Manchmal glaube ich deine Aufgaben nicht zu verstehen.
Beim RSA Verfahren, haben doch immer beide Kommunikationspartner einfluss auf den Schlüssel?

Jein ...
Während der Anfangssequenz von RSA muss ein Kommunikationsteilnehmer (und zwar der, der K_priv und K_pub generiert um nacher die angekommenen Daten zu entschlüsseln - gleiches auf anderer Seite auch, aber unabhängig vom ersten) phi(n) und ein b (0 < b < phi(n) | GGT(b,phi(n)) = 1) erzeugen.
phi(n) wird durch (p-1)*(q-1) berechnet. p und q sind Primzahlen, sollten zusammen >1024 bzw. >2048 Bit ergeben.
b berechnet man wie --> siehe oben.
n = p * q

Naja, der K_pub dieses Teilnehmers besteht dann aus: K_pub =(b,n). Dies ist sein öffentlicher Schlüssel und kann von jedem Angreifer eingesehen werden.
Googleschlagwort: Faktorisierung, P-vollständiges Problem (wo wir wieder bei der Komplexitätstheorie wären)

Wie Du siehst, wurde K_pub nun völlig autark von dem anderen Teilnehmer(n) generiert ... Partner A hat also keinen Einfluss auf den K_pub von Partner B ... oder auf die Generierung. Rodger?

Um die Aufgabe noch ein wenig zu erklären:
Hier geht es bei der "Schlüsselwahl" nicht um konkreten K_pub sondern um die Generierung eines Sessionkeys für den beidseitigen Schlüsselaustausch.
Aber Du hast Recht ... ich hätte das präzisieren müssen ... wäre ich alleine aber nicht draufgekommen. ;-)

Kleiner Anfangstip:

- Autausch der beiden K_pub der beiden Kommunikationsteilnehmern
- Partnerb B generiert (un) sicheren Schlüssel K_strange
- bedenkt, dass nun ein symmetrisches Verfahren folgen sollte ...

Wenn noch was unklar sein sollte....einfach posten ... dazu is der Laden ja da.

@mdk
Was genau, ist ein :
[zitat]
rsa verschluesselten schluesselrequest
[/zitat]
Ich komm da nicht dahinter?

Raff ich auch noch nicht ganz.

[Enchanter]

[zitat]
Wie Du siehst, wurde K_pub nun völlig autark von dem anderen Teilnehmer(n) generiert ... Partner A hat also keinen Einfluss auf den K_pub von Partner B ... oder auf die Generierung. Rodger?
[/zitat]
Mag an der Uhrzeit liegen, aber ne, ich hab kein Wort verstanden.
Du hast doch gerade selbst gezeigt, das K_pub von beiden Teilnehmern gewählt wurde,
denn beide haben eine Primzahl zu Phi beigetragen. Vieleicht beschreibst du einfach mal so einen Fall,
in dem wie du sagst, diese Abhängigkeit nicht ausreicht.

[zitat]
- Autausch der beiden K_pub der beiden Kommunikationsteilnehmern
- Partnerb B generiert (un) sicheren Schlüssel K_strange
- bedenkt, dass nun ein symmetrisches Verfahren folgen sollte ...
[/zitat]
Warum tut "Partnerb B" soetwas... grübel
Und wie zur Hölle schafft er es ein x zu phi zu wählen,
das auch noch genau dieser Weakkey Regel,
dieses Symetrischen Algos entspricht... Ja, der "Mannb B" muss wohl ein Genie sein. ;-).

Ne, mal ernsthaft ich habs nicht verstanden.

[DrWhiteLetter]

@mdk
Worauf bezieht sich deine Antwort eins? Auf: Gründer hybrider Verfahren?

1.) symetrische verfahren sind um einiges schneller als public-verfahren... das ist soviel ich weiss der einzige grund, korrigiert mich aber gerne falls es noch andere gruende gibt...

Hm weiß aber auch nicht so genau, würde vielleicht sagen, da ein öffentlicher Schlüssel genutzt wird um den Sitzungssschlüssel für das symmetrische Verfahren zu verschlüsseln, werden die Vorteile beider Verfahren durch eine Kombination dieser genutzt, das sollte ja eigentlich für hybride Verfahren sprechen.

Warum ist die alleinige Verschlüsselung mit RSA nicht immer von Vorteil?

*grübel*
Vielleicht weil die Grenze der faktorierbaren Zahlen ständig höher gesetzt wird? Ich meine damit halt, das bessere Berechnungstechniken entwickelt werden und natürlich auch die Leistung der Rechner stark ansteigt und Shamir schaffte es ja auch schon ein Jahr später einen 512-Bit-Schlüssel in nur 3 Tagen zu knacken.

Für ne Musterlösung wäre ich hier allerdings dankbar,...

[triton]

Beide Teilnehmer generieren sich jeweils zwei Primzahlen und berechnen daraus dann ihr eigenes Schlüsselpaar. Teilnehmer A hat also einen privaten und einen öffentlichen Schlüssel und Teilnehmer B hat auch einen privaten und einen öffentlichen Schlüssel. Das Schlüsselpaar von A hat mit dem von B nichts zu tun.
Nun soll noch ein Sitzungsschlüssel für ein symmetrisches Verfahren (nicht RSA) erzeugt werden, der also nach Beendigung einer Sitzung weggeworfen wird.
Die geläufigste Vorgehensweise wird hierbei wohl folgende sein:
- A wählt eine Zufallszahl x, verschlüsselt sie mit dem öffentlichen RSA Schlüssel von B und schickt sie an B
- B wählt einen Zufallszahl y, verschlüsselt sie mit dem öffentlichen RSA Schlüssel von A und schickt sie an A
- A und B kennen dann x und y und berechnen den Sitzungsschlüssel als x XOR y

Sofern die Zufallszahlen von keinem der Teilnehmer vorhersehbar sind, haben sie keine Möglichkeit den endgültigen Schlüssel zu ihrem Vorteil zu beeinflussen.

Was die erste Aufgabe angeht werden hybride Verfahren nicht nur aus Geschwindigkeitsgründen verwendet, sondern auch weil es einige Angriffe bei Public-Key Verfahren im Allgemeinen und bei RSA im Besonderen gibt, wenn man sie zum direkten Verschlüsseln eines Klartexts verwendet.

Einfaches Beispiel:
- A verschlüsselt einen Klartext direkt mit RSA und schickt den resultierenden Chiffretext zu B
- C fängt den Chiffretext ab. Gleichzeitig vermutet C, dass A's Klartext einer von 10 Möglichen ist. C braucht jetzt nur noch seine 10 vermuteten Klartexte mit dem öffentlichen Schlüssel von B zu verschlüsseln und die Resultate mit der abgefangenen Nachricht zu vergleichen. Es ist also bei diesem Szenario einfach einen known-plaintext Angriff auszuführen.

[Dominik]

Nun soll noch ein Sitzungsschlüssel für ein symmetrisches Verfahren (nicht RSA) erzeugt werden, der also nach Beendigung einer Sitzung weggeworfen wird.
Die geläufigste Vorgehensweise wird hierbei wohl folgende sein:
- A wählt eine Zufallszahl x, verschlüsselt sie mit dem öffentlichen RSA Schlüssel von B und schickt sie an B
- B wählt einen Zufallszahl y, verschlüsselt sie mit dem öffentlichen RSA Schlüssel von A und schickt sie an A
- A und B kennen dann x und y und berechnen den Sitzungsschlüssel als x XOR y

Perfekt. Genau so war das Gedacht. Dein Lösungsvorschlag ist korrekt.

Was die erste Aufgabe angeht werden hybride Verfahren nicht nur aus Geschwindigkeitsgründen verwendet, sondern auch weil es einige Angriffe bei Public-Key Verfahren im Allgemeinen und bei RSA im Besonderen gibt, wenn man sie zum direkten Verschlüsseln eines Klartexts verwendet.

Einfaches Beispiel:
- A verschlüsselt einen Klartext direkt mit RSA und schickt den resultierenden Chiffretext zu B
- C fängt den Chiffretext ab. Gleichzeitig vermutet C, dass A's Klartext einer von 10 Möglichen ist. C braucht jetzt nur noch seine 10 vermuteten Klartexte mit dem öffentlichen Schlüssel von B zu verschlüsseln und die Resultate mit der abgefangenen Nachricht zu vergleichen. Es ist also bei diesem Szenario einfach einen known-plaintext Angriff auszuführen.

Is richtig, aber würde ich nicht als schlagkräftiges Argument bezeichnen.
Auch symmetrische Verfahren wie DES sind angreifbar mit known-plaintext und linearen wie differentiellen Attacken allgemein.
Siehe: http://www.wisdom.weizmann.ac.il/~tr...KC2004/des.pdf

Known Plaintext is imho sowieso ein "relativ" hartes Szenario für einen Algorithmus, da der Angreifer ja schon sehr viel weiss ... fast zu viel.

Hm weiß aber auch nicht so genau, würde vielleicht sagen, da ein öffentlicher Schlüssel genutzt wird um den Sitzungssschlüssel für das symmetrische Verfahren zu verschlüsseln, werden die Vorteile beider Verfahren durch eine Kombination dieser genutzt, das sollte ja eigentlich für hybride Verfahren sprechen.

Richtig. So wird das meistens gemacht.
MAn verschlüsselt mit RSA den Schlüssel für das symmetrische Verfahren und kann es somit sicher übertragen.
Das nennt man hybrides Verschlüsselungsverfahren.

Vielleicht weil die Grenze der faktorierbaren Zahlen ständig höher gesetzt wird? Ich meine damit halt, das bessere Berechnungstechniken entwickelt werden und natürlich auch die Leistung der Rechner stark ansteigt und Shamir schaffte es ja auch schon ein Jahr später einen 512-Bit-Schlüssel in nur 3 Tagen zu knacken.

Im Prinzip richtig.
Die "Algorithmen" (es gibt ja leider noch keinen richtigen Alg. von daher vorsicht mit diesem Wort in diesem Zusammenhang) zur Faktorisierung von großen Zahlen werden ausgefeilter, besser:
Man arbeitet an effizienten Algorithmen für die Faktorisierung großer Zahlen.
576-Bit wurden letzten Dezember faktorisiert von den Freaks aus Bonn (siehe Zeitung). Den derzeitigen Stand weiss ich nicht.
Aber wie Du sagst, steigt die Rechenleistung stetig an und somit müssen auch die Primzahlen größer werden. Daher empfiehlt man nun bei RSA auch schon 2048-Bit.
Um zurück zur Frage zu kommen:
1 Gig Daten mit RSA zu verschlüsseln braucht seine Zeit ... mit symmetrischen Verfahren geht das wesentlich schneller.
Daher --> hybride Verfahren

[-frabla-]

1//Das Wort puplik-key algorythmen ist zwar gut aber asymetrische verfahren waere besser. Nun Zur Loesung. Die Antwort der Ersten Frage ist sogleich auch die der Zweiten: mit hilfe des asymetrischen verfahren wird ein symetrischer Schluesssel uebermittelt. Da ein asymetrischer Schluesel relativ langsam ist geht der ganze Spass mit dem uebermittelten Symetrischen schneller. Ausserdem ist die kombination von mehreren Verfahren besser [siehe pgp].


2)
In der Praxis ist es manchmal notwendig, dass BEIDE kommunizierenden Parteien Einfluss auf die Schlüsselwhl haben. Hierbei wird verhindert, dass eine der Parteien einen schwachen Schlüssel für ein symmetrisches Verschlüsselungsverfahren wählt, um z.b. aussenstehenden Angreifern Vorteile zu verschaffen. Viele der bekannsten symmetrischen Verfahren wie z.b. IDEA oder DES haben sog. schwache Schlüssel.
Nachrichten die mit diesen schwachen SChlüsseln verschlüsselt worden sind, können leicht aus dem verschlüsselten Text zurückgewonnen werden.

Entwickel ein ähnliches Protokoll wie in Aufgabe 1, bei dem diesmal beide Parteien die Schlüsselwahl beeinflussen. Nehme dazu an, dass sowohl User_A als auch User_B einen privaten und öffentlichen RSA-Schlüssel besitzen.

2//Wenn beide Parteien geheim komunizieren wollen, wird wohl kaum einer von beiden einen schwachen Schluessel verwenden. Das naechste ist, dass bei RSA die BEIDEN keinen einfluss auf den anderen Schluessel haben, sonst weare RSA sinnlos. Verstehe mich nicht falsch. Aber wie soll das Funktionieren?

[Dominik]

1//Das Wort puplik-key algorythmen ist zwar gut aber asymetrische verfahren waere besser.

Wieso?

Nun Zur Loesung. Die Antwort der Ersten Frage ist sogleich auch die der Zweiten: mit hilfe des asymetrischen verfahren wird ein symetrischer Schluesssel uebermittelt.

Gut!

Da ein asymetrischer Schluesel relativ langsam ist geht der ganze Spass mit dem uebermittelten Symetrischen schneller.

Wie langsam? Der läuft langsam? Krücke? ^^

Ausserdem ist die kombination von mehreren Verfahren besser [siehe pgp].

Zu pauschal ... imho kommt es auf die Zusammensetzung an.

2//Wenn beide Parteien geheim komunizieren wollen, wird wohl kaum einer von beiden einen schwachen Schluessel verwenden.

Wenn beide Partner heiraten wollen, wird wohl kaum einer von beiden fremd gehen? ;-)
Unwissenheit (im oberen Beispiel eher nicht ;-)), Inkompetenz, falsche Implementierung etc...aber ich denke, ich weiss auf was Du hinaus willst und stimme Dir zu:
Mit Absicht wird man sowas wohl nicht machen wollen, ausser man hat böse Absichten (3 Partei in Kommunikation mit einschleusen?)

Das naechste ist, dass bei RSA die BEIDEN keinen einfluss auf den anderen Schluessel haben, sonst weare RSA sinnlos. Verstehe mich nicht falsch. Aber wie soll das Funktionieren?

Hehe, Du verstehst mich falsch. ;-)
Es geht nicht um die RSA keys, sondern um den symmetrischen.
Lese tritons Post:

Nun soll noch ein Sitzungsschlüssel für ein symmetrisches Verfahren (nicht RSA) erzeugt werden, der also nach Beendigung einer Sitzung weggeworfen wird.

[-frabla-]

mit dem langsam hast du natuelich recht. ich meinte, dass es verhaeltnismaessig lange dauert(frag bitte nicht verhaeltnis zu was? )

wenn ich aber deine aufgabenstellung 2 genau durchlese, find ich nichts was RSA verbietet:
"Entwickel ein ähnliches Protokoll wie in Aufgabe 1, bei dem diesmal beide Parteien die Schlüsselwahl beeinflussen. Nehme dazu an, dass sowohl User_A als auch User_B einen privaten und öffentlichen RSA-Schlüssel besitzen."