RSA Verschlüsselung Theorie

[Felix_krueger]

Hi Leute,

ich habe mich ein wenig mit dem RSA Algorithmus beschäftigt, aber offensichtlich noch arge Verständnisprobleme bzw. einen Denkfehler.

Direkt am Anfang werden zwei Primzahlen benötigt (die ~100 Stellen haben). Da frage ich mich: Wo kommen diese her?

(I) Werden die einfach berechnet? ... Das kann ich mir nämlich eher weniger gut vorstellen, da ich ja so lange zwei Zahlen erzeugen muss, bis zwei Primzahlen dabei waren - afaik würde es ziemlich lange dauern bis ich die Zahlen getestet habe.

(II) Kommen sie aus einer Liste und sind "geheim" ? ...Hier könnte ich mir vorstellen, dass man sich eine wirklich große Primzahl kauft (die geheim ist) und dann mit einer Primzahl multipliziert die öffentlich verfügbar ist.

Naja, ich hoffe es kann mich jemand erleuchten.
LG

 

[Margot Honecker]

zu II

wenn man eine primzahl mit einer primzahl multipliziert erhält man aber keine primzahl

ansonsten: so viele hundertstellige primzahlen wird es auch wieder nicht geben, ausserdem sind die eh alle bekannt.

 

[tnoay]

(I) Werden die einfach berechnet? ...

weiß nicht, aber man kann sie speichern. die herausforderung ist für den angreifer diese beiden zahlen zu finden

 

[Felix_krueger]

Also man kann Primzahlen wohl doch simpler berechnen als ich dachte. Stichwort "Miller-Rabin-Test".
Dann ist der Clou, dass es so viele Primzahlen gibt die sich wirtschaftlich berechnen lassen, dass es unmöglich ist alle Primprodukte im Vorhinein zu errechnen?
Aber dann frage ich mich: Wie sage ich meinem PC wo er Anfangen soll die Primzahl zu suchen?
Nehme ich da einfach einen Seed aus dem ich einen Zufallswert erzeuge (123456789) und dann sucht mein Rechner nach der nächsten Primzahl ab 123456789?

& Margot: Doch es gibt ja unendlich viele Primzahlen. Die Frage ist eher: Wie aufwendig ist es diese zu berechnen?

 

[kevchen01]

Die Primzahlen werden nur zur Berechnung für das RSA Modul, die Inverse, etc. verwendet. Danach werden zum Codieren/Decodieren nur noch die Module verwendet die Primzahlen sind dann unwichtig.

watch?v=Grd-sxx5dEQ

4 Teile - sehr gut erklärt

Gruß

 

[ghost_zero5]

RSA errät quasi Primzahlen.
Es gibt dann diverse Primzahlentests mit denen man die Wahrscheinlichkeit dass es eine Primzahl ist durch mehrfache Durchführung erhöhen kann.
Damit kann man die Wahrscheinlichkeit klein genug halten, dass die Wahrscheinlichkeit, dass es sich um keine Primzahl handelt klein genug ist.

Bzgl. Anzahl der Primzahlen, wenn es nicht extrem viele große Primzahlen geben würde, wäre RSA nicht sicher (da man sie einfach mittels Brute-Force erraten könnte), siehe auch Primzahlsatz diesbzgl.

 

[Felix_krueger]

@kevchen01: Das Video ist gut, aber leider erklärt er auch nicht woher ich die Primzahlen nehme.
Wenn ich es richtig verstanden habe, dann ist es doch grade entscheidend was die Primzahlen sind, damit die Faktorisierung von N möglichst schwierig ist.

@ghost_zero5:
Bleibt die Frage wie ich meinem PC sage, wo er anfangen soll zu suchen. Sage ich einfach gib mir mit /dev/random zwei Zahlen mit mindestens 100 Dezimalstellen und dann suche ich mit Miller-Rabin nach der nächsten Primzahl?

 

[xbrtll]

Nach der nächsten Primzahl ausgehend von einem Startwert suchen klingt für mich nach einer Schwäche, die man vermeiden sollte. Wirf vielleicht mal eine Blick ein die englische Wikipedia: http://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_generation + nächster Absatz

 

[Felix_krueger]

xbrtll: Guter Einwand, dann gibt es wohl noch eine Reihe weiterer mathematischer Bedingungen, die mein Primzahlenpaar erfüllen sollte.

Laut des Artikels haben aber einige Zufallszahlengeneratoren Schwächen, sodass man 0,2% der untersuchten Schlüssel faktorisieren konnte.
"Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise or atmospheric noise from a radio receiver tuned between stations should solve the problem." - Kann man nur hoffen, dass die Hersteller in Zukunft auf die Stärke ihrer Entropiepools achten werden.

 

[Margot Honecker]

& Margot: Doch es gibt ja unendlich viele Primzahlen. Die Frage ist eher: Wie aufwendig ist es diese zu berechnen?

aber nicht unendlich viele mit hundert stellen

 

[xbrtll]

Es gibt ~3.9*10^97 Primzahlen mit 100 Dezimalstellen, also viel zu viele um sie alle speichern zu können.

 

[ghost_zero5]

Ja man kann relativ gut eine x-beliebig Primzahl finden mit PC, wenn man zufällig sucht.
Die Wahrscheinlichkeit ist relativ hoch, da es doch relativ viele sind.
Es kann hier ja irgendeine sein und muss nicht eine bestimmte sein.

Mittels dem Primzahlensatz (Anzahl der Primzahlen bis zu einer bestimmten zahl) kann man sich diese ausrechen.
Man kann bei der Suche das ganze auch noch verbessern indem man nur ungerade Zahlen nimmt (gerade Zahlen sind ja durch 2 teilbar).

Siehe auch hier:
http://www-ti.informatik.uni-tuebingen.de/~reinhard/krypto/German/deutsch.html
bzw. genauer der Unterpunkt:
http://www-ti.informatik.uni-tuebingen.de/~reinhard/krypto/German/2.3.d.html

und evtl. hier:
http://books.google.at/books?id=KKCuzFFdSQkC&pg=PA68&dq=isbn:3934196667&hl=de#v=onepage&q&f=false

EDIT:
Wenn man sie alle speichern könnte, wäre die mögliche Menge der Zahlen evtl. auch zu klein, damit der Algorithmus noch sicher ist (darf ja nicht klein genug sein, damit man hier mittels Bruteforce einfach an den Key kommt innerhalb vernünftiger Zeit mit modernen PCs).

 

[olfbc]

Primzahlen prüfen und in Primfaktoren zerlegen ist vom Rechenaufwand extrem assymetrisch.
Man weiß sehr schnell, daß eine Zahl zusammengesetzt ist aber es dauert ewig die Primfaktoren zu finden!
Eine 100 stellige Primzahl zu finden dauert mit Mathematika einen Wimpernschlag

erste 100stellige 10^100 + 267; 0,016s
10^1000 + 453; 0,8s
10^10000 + 28579; 13883s = 3,9h

Aber eine z.B. 62 Stellige Zahl zu zerlegen dauert schon sehr lange:
(10^31+21544346907 )*(10^31+271)= 10^62 zerlegen dauert 341s
Bei 10^100*10^100=200 Stellen? Bitte warten...

einstweilen hier lesen:
http://scienceblogs.de/mathlog/2010/01/09/232stellige-zahl-faktorisiert/

 

[AccountPasswort]

In dem Video, auf Youtube geht es um die "very basics" über "geheime Nachrichten" sehr toll erzählt und es fallen auf jeden Fall auch die "Primzahlen".
Wunderbar erklärt von einem Rudolf Taschner. Durch ihn bin erst mal drauf gekommen das RSA (Initialien der drei "Erfinder", bzw Patentanmelder) mit Primzahlen zu tun hat und das zurück geht bis auf Fermat und Euler, auch sehr schön erklärt von Taschner im "Der Irrtumm von Pierre de Fermat".

v=rzmdfb0I6dg

In diesem Video hier wir genau erklärt wie das Prinzip

Modul = Primzal * Primzahl (öffentlicher Schlüssel?)
Exponent = irgend eine Zahl? (auch öffentlich)
Geheimer Schlüssel = wird aus Modul und Exponent errechnet. (geheim)

funktioniert.

Das ist für mich sehr interessant und dabei kann ich gar nicht gut rechnen...