RSA: Klartext ist gleich verschlüsselter Text

20.07.2013, 19:08

ces

RSA: Klartext ist gleich verschlüsselter Text

Meine Frage:
Hallo,

ich versuche gerade mir RSA anhand kleiner selbst gewählter Beispiele näher zu bringen. Dabei ist mir bei folgender Konfiguration etwas merkwürdiges aufgefallen:

p = 7
q = 13

Daraus folgt:
n = 91
fi(n)=72

Der öffentliche Schlüssel soll

c = 7

sein. Der private Schlüssel ist demnach

d = 31

Wenn ich jetzt die Nachricht

x = 3

verschlüsseln möchte, erhalte ich als verschlüsselte Nachricht

$\begin{eqnarray*} y = 3^{7} mod 91 = 3 \end{eqnarray*}$

Was ja meiner Nachricht im Klartext entspricht. Wie kann das sein bzw. wie kann man so etwas bei der Wahl der Primfaktoren p und q bzw. des öffentlichen Schlüssels verhindern?

Meine Ideen:
Ich nehme mal es liegt wohl daran, dass die 3 ein multiplikativ Inverses der 91 ist. Aber könnte das nicht auch mit anderen Primfaktoren klappen, sodass es Nachrichten gibt, die verschlüsselt auch wieder den Klartext darstellen?

20.07.2013, 21:19

watcher

Auf diesen Beitrag antworten »

Hallo,

den Schlüssel gleich einem Primteiler zu wählen ist erstmal keine so gute Idee.
Denn unter dem chin. Restsatz ist $\begin{eqnarray*} \mathbb Z /91 \mathbb Z \cong \mathbb Z / 7 \mathbb Z \times \mathbb Z / 13 \mathbb Z , \quad x \to (x_1,x_2) \end{eqnarray*}$
wird $\begin{eqnarray*} x^7 \end{eqnarray*}$ abgebildet auf $\begin{eqnarray*} (x_1^7,x_2^7)=(x_1,x_2^7) \end{eqnarray*}$
nach Euler. Das erhöht schonmal die Wahrscheinlichkeit einen Fixpunkt zu kriegen.
Einen solcher ergibt sich wenn $\begin{eqnarray*} ord(x_2)=6 \end{eqnarray*}$ und da 6|12 gibts davon ein paar.
Das Hauptproblem ist, dass p und q sehr klein sind.
Verschärfend kommt hinzu, dass $\begin{eqnarray*} x^{12}\equiv 1 \mod 91 \end{eqnarray*}$ für alle x, siehe hier.

Prinzipiell kann einem dass auch für andere Primzahlen passieren, die W-keit dafür wird aber für größere Primzahlen deutlich kleiner.

Übrigens wär auch 7 ein privater Schlüssel, oder 19,...
Auch nach neuer deutscher Rechtschreibung ist es immer noch phi oder gleich $\begin{eqnarray*} \varphi \end{eqnarray*}$

Zitat:

dass die 3 ein multiplikativ Inverses der 91 ist.

Wie meinen? 3 ist invertierbar mod 91. Was das Inverse von 91 ist hängt vom betrachteten Ring ab.

@Mods: Bitte verschieben, wohl in Sonstiges. Numerik ist es definitv nicht.

20.07.2013, 21:40

Dopap

Auf diesen Beitrag antworten »

eigentlich ist RSA eine fixpunktfreie Permutation der Klartextblöcke. Eigentlich dürfte das nicht auftreten.

Dein c, was üblicherweise e genannt wird ist zufällig = 7=p

Ob es daran liegt verwirrt

20.07.2013, 21:47

watcher

Auf diesen Beitrag antworten »

@Dopap

Zitat:

eigentlich ist RSA eine fixpunktfreie Permutation der Klartextblöcke. Eigentlich dürfte das nicht auftreten.

Quellenangabe?

Ich kann dir zu jedem Paar ungerader Primzahlen (p,q) eine Zahl e angeben mit $\begin{eqnarray*} 1<e<\varphi(pq) \end{eqnarray*}$ mit $\begin{eqnarray*} x^e\equiv x \mod pq \end{eqnarray*}$ für alle x.

Anmerkungen von Edith:
Das einzige was mir gerade an Fixpunktfreien Permutationen einfällt in diesem Kontext ist die Enigma. Und da zeigt sich doch sehr schön, dass sowas nicht unbedingt eine gute Idee ist.

20.07.2013, 22:29

Dopap

Auf diesen Beitrag antworten »

dann habe ich das wohl mit der MatrixVerschlüsselung von HILL verwechselt. unglücklich

Neue Frage »

Antworten »

RSA: Klartext ist gleich verschlüsselter Text

Verwandte Themen