RSA-Verschlüsselung: Forscher decken Schwachstelle auf

**Annika_Kremer** · 16. 02. 2012, 18:00

Ein Team aus europäischen und US-amerikanischen Mathematikern und Kryptographie-Experten entdeckte kürzlich eine Schwäche im verbreiteten Verschlüsselungs-Verfahren RSA. Ein kleiner Teil der generierten Schlüssel weist offenbar mathematische Schwächen auf, die eine Entschlüsselung der damit verschlüsselten Nachrichten durch Unbefugte ermöglichen.

zur News

**widarr** · 16. 02. 2012, 18:14

Also liegt die Schwäche wie erwartet beim verwendeten Zufallsgenerator. Das ist ein altbekanntes Problem.
Der Zufall beschäftigt Kryptologen und Mathematiker schon lange.

**meranti** · 16. 02. 2012, 18:22

Ein neues Verfahren zur Zufallszahlenerstellung wird gebraucht.

**kami1** · 16. 02. 2012, 18:34

Es gibt recht gute und kostengünstige Methoden, gute (nicht deterministische) Zufallswerte zu erzeugen, beispielsweise über Messung von Signalrauschen.

Das könnte sich langsam durchsetzen.

**Demmi** · 16. 02. 2012, 18:36

Der Artikel hier ist nicht ganz richtig: Das Problem, dass im Paper beschrieben wird, zielt nicht auf die beiden Schlüssel (public & private - die übrigens jede asymmetrische Verschlüsselung hat) ab, sondern darauf, dass bei RSA zwei "secrets" gebraucht werden um die Schlüssel zu erzeugen: die zufällig gewählten Primzahlen p und q, die dann den Modulus n ergeben.
Und das ist offenbar schwieriger als nur eine einzelne Zufallszahl zu erzeugen wie z.B. bei ElGamal oder (EC)DSA. Details dazu im erwähnten Paper.

Das Problem dabei ist, dass über einen Schlüssel hinaus eine (oder beide) der Zahlen p und q zufällig wiederverwendet werden können. Wenn man nun zwei Schlüssel findet, den gcd der beiden Moduli n₁ und n₂ berechnet (trivial) und zufällig einen Primfaktor findet, hat man ganz schnell die kompletten Schlüssel berechnet.
Das ist das eigentliche Problem. Und das kann natürlich verursacht werden durch fehlerhafte Implementierung oder schlechte (bzw. schlecht initialisierte) Zufallszahlengeneratoren, die die gleichen Zahlen erzeugen.

Danke für die Aufmerksamkeit.

**Metal_Warrior** · 16. 02. 2012, 22:36

Zitat von meranti

Ein neues Verfahren zur Zufallszahlenerstellung wird gebraucht.

This! Das mit dem Signalrauschen ist sicher ne gute Möglichkeit (auch wenn das Rauschen hauptsächlich durch den Wechselstrom-Sinus hervorgerufen werden dürfte, was wieder ne Angriffsmöglichkeit wäre), auch Nutzereingaben dürften über einen längeren Zeitraum gemessen ein sehr zufälliges Muster ergeben. Oder Zugriffszeiten von Datenträgern unter Last. Mir würden ein paar Möglichkeiten einfallen, aber ob die dann wirklich zufällig sind, ist ne gute Frage...

Weiß man schon, welche Zufallsgeneratoren höhere Anfälligkeit für Periodizität bzw. Vorhersagbarkeit haben?

**meranti** · 16. 02. 2012, 22:42

Zitat von Metal_Warrior

Mir würden ein paar Möglichkeiten einfallen, aber ob die dann wirklich zufällig sind, ist ne gute Frage...

Das ließe sich dann sehr leicht prüfen, dafür gibt es Tests auf Zufälligkeit. Man könnte auch zu hause Würfel benutzen, um sich die Schlüssel für RSA zu erstellen

**Isschonwech** · 17. 02. 2012, 10:48

Zitat von widarr

beschäftigt Kryptologen und Mathematiker schon lange.

wird es auch weiterhin, wenn man in so eindimenisonale richtungen denkt

**T_Zero** · 17. 02. 2012, 11:46

Zitat von Metal_Warrior

This! Das mit dem Signalrauschen ist sicher ne gute Möglichkeit (auch wenn das Rauschen hauptsächlich durch den Wechselstrom-Sinus hervorgerufen werden dürfte, was wieder ne Angriffsmöglichkeit wäre), auch Nutzereingaben dürften über einen längeren Zeitraum gemessen ein sehr zufälliges Muster ergeben. Oder Zugriffszeiten von Datenträgern unter Last. Mir würden ein paar Möglichkeiten einfallen, aber ob die dann wirklich zufällig sind, ist ne gute Frage...

www.random.org Da wird atmosphärisches Rauschen genommen, was als sehr sehr zuverlässig gilt.

**widarr** · 17. 02. 2012, 12:35

Eine der sichersten Methoden dürfte wohl das ablesen des Zerfalls eines Radionuklids sein. Niemand kann vorhersagen, welches Uran/Thorium/... usw. atom als nächstes zerfällt.

**Metal_Warrior** · 17. 02. 2012, 13:56

Zitat von widarr

Eine der sichersten Methoden dürfte wohl das ablesen des Zerfalls eines Radionuklids sein. Niemand kann vorhersagen, welches Uran/Thorium/... usw. atom als nächstes zerfällt.

Damit hast du aber nur einen einzigen Zeitpunkt, und der liegt definitiv schonmal in der Zukunft (bzw. der Zeit nach Einbau des Nuklids). Ist das Nuklid zerfallen, brauchst du einen neuen Nummerngenerator, hältst du viele Nuklide vor, sind die Hälfte aller Zufallsdaten innerhalb der Halbwertszeit. Wenn du an Schrödingers Katze gedacht hast, hast du wohl das grundlegende Problem nicht wirklich verstanden

**widarr** · 17. 02. 2012, 17:55

Zitat von Metal_Warrior

Damit hast du aber nur einen einzigen Zeitpunkt, und der liegt definitiv schonmal in der Zukunft (bzw. der Zeit nach Einbau des Nuklids). Ist das Nuklid zerfallen, brauchst du einen neuen Nummerngenerator, hältst du viele Nuklide vor, sind die Hälfte aller Zufallsdaten innerhalb der Halbwertszeit. Wenn du an Schrödingers Katze gedacht hast, hast du wohl das grundlegende Problem nicht wirklich verstanden

Es gibt genügend Radionuklide, deren Halbwertszeit wohl nicht mal die Menschheit erleben wird

Das einzige Problem könnte die Bandbreite, also Zufallsereignisse pro Sekunde sein. Dann müsste man einfach ein stärker strahlendes Element hernehmen

**Metal_Warrior** · 17. 02. 2012, 19:11

Zitat von widarr

Es gibt genügend Radionuklide, deren Halbwertszeit wohl nicht mal die Menschheit erleben wird

Das ist nicht das Problem - das Problem ist, dass es ein einziges Ereignis irgendwann in der Zeit ist - und du die Zufallszahl erst hast, wenn es eingetreten ist. Verstehst du das jetzt?

Dann müsste man einfach ein stärker strahlendes Element hernehmen

...das dann aber eine kürzere Halbwertszeit hat, wenn ich dich richtig verstanden habe. Oder willst du die (determinierte) Intensität des Impulses messen? Ich glaube nicht - was du meinst, ist Aktivität, du willst ein aktiveres Element (mehr Zerfälle pro Sekunde, deshalb auch kürzere Halbwertszeit).

**lullsaeckel** · 21. 02. 2012, 00:54

Zitat von widarr

Eine der sichersten Methoden dürfte wohl das ablesen des Zerfalls eines Radionuklids sein. Niemand kann vorhersagen, welches Uran/Thorium/... usw. atom als nächstes zerfällt.

Ich mag ja ein Idiot sein, aber ich glaube einfach nicht, dass jemand von euch ein Radionuklid zerfallen läßt um sein Schlüsselpaar zu generieren. Macht man das in der Waschmaschine?
Auch dürfte schwerlich einer von euch so wichtige Dinge zu sagen haben, dass ein Geheimdienst auf die Idee kommen könnte eure Schlüssel zu knacken - sorry.
Also bleibt mal ganz locker.

L

**Rsistor** · 21. 02. 2012, 01:03

Zitat von kami1

Es gibt recht gute und kostengünstige Methoden, gute (nicht deterministische) Zufallswerte zu erzeugen, beispielsweise über Messung von Signalrauschen.

Das könnte sich langsam durchsetzen.

Zener-Diode kosten nur ein paar Cent...