Kryptographie - RSA - Verwenden von Nicht-Primzahlen

Wissenschaft Mathematik
#1

Hallo zusammen,

Ich hätte eine frage zwecks des RSA-Verschlüsselungs Algorithmus. Und zwar werden zur Berechnung der Schlüssel 2 Primzahlen benötigt, p und q ( n = (pq) bzw m = (p-1)(q-1)). Nun die Frage, was passiert nun, sollte man an stelle von p und q keine Primzahlen verwenden? Die Primzahlenzerlegung von n wären nicht mehr p und q da diese selbst aus Primzahlen bestehen. Doch wie wirkt sich dies im Endeffekt aus? Sind hierdurch die Schlüssel leichter zu knacken und wenn ja warum?

Vielen Dank im Voraus
Liebe Grüße
Michael

#2

Hallo,
naja, schau Dir mal an, in welcher Gruppe (Menge) Du nachher e und d bestimmst. Die waere
fuer Nicht-Primzahlen p, q ja viel viel kleiner und damit unsicherer in dem Sinne, dass sie schneller zu durchlaufen waere als die volle Gruppe.

Z.B. p = 8, q = 4, n waere 32, m waere 4 * 2 = 8, du suchst also das Inverse von e modulo 8.
Im Gegensatz dazu, p = 7, q = 3, n waere 21, aber hier ist m = 12. Schon mal groesser als 8, obwohl n deutlich kleiner ist.

#3

Tschuldigung, rechnen muesste man koennen, phi(32) ist natuerlich 16. Aber gut, mein Punkt steht trotzdem: wenn n mehr als 2 Primfaktoren hat, dann ist phi(n) kleiner als ein `naheliegendes’ n mit nur 2 Primfaktoren.

#4

Vielen dank für die Antwort,

ich habe mich in letzter Zeit weiter mit diesem Problem beschäftigt. Das Problem an der Sache ist, dass ein Angreifer zu Berechnung des Privaten Schlüssels (mithilfe des Public-Key) ᵠ(n) berechnen muss. Für die Phi-Funktion werden die Primfaktoren von n benötigt. Dies ist bei n=p*q quasi unmöglich zu berechnen (sollten p und q extrem hohe Primzahlen sein). Werden für p oder q jedoch keine Primzahlen gewählt, so können durch beispielsweise einfaches durchprobieren die Primfakotern gefunden werden und somit der Private Schlüssel errechnet werden.

nochmals vielen Dank für die Hilfe
Viele Grüße
Michael

#5

Naja fast, ganz korrekt ausgedrueckt: Falls Du drei grosse Primzahlen p, q und r hast. Dann kannst Du natuerlich RSA mit n = p * q * r machen, nur falls Du einen Faktor raten kannst, dann ist das Verfahren eben nur noch so sicher wie ein Standard-RSA, also entweder n = p * q, oder n = p * r oder n = r * q.

Es wird also nicht sicherer, sondern hoechstens genauso sicher wie die Variante mit 2-Faktoren, aber einfacher wird es nun auch nicht. Man koennte sagen, dass 3-Faktor RSA und 2-Faktor RSA in diesem Sinne aequivalent sind.