Benutzer:Arbol01/Potentielle Schwachstellen des RSA-Verfahren (und verwandter Verschlüsselungsverfahren)

Potentielle Schwachstellen des RSA-Verfahren (und verwandter Verschlüsselungsverfahren)

Vorwort

In diesem Buch soll es nicht um die Zerstörung des RSA-Verfahrens gehen. Das Buch erhebt auch nicht den Anspruch der Weisheit letzter schluß zu sein. Es geht nur darum sich über mögliche Schwachstellen gedanken zu machen. Vielleicht hilfe es auch, klarer zu machen, was das RSA-Verfahren für ein Verfahren ist, und wo seine Besonderheitel liegen.

Das Produkt zweier Primzahlen

Der große Vorteil des RSA-Verfahren, und auch anderer Verschlüsselungsverfahren, liegt darin, das aus zwei sehr großen Primzahlen (100 stellgen Zahlen und mehr) Produkt gebildet wird, aus dem dann die weiteren Zahlen gebildet werden. Mit der Kenntnis der Faktorisierung des Produkts ist eine Entschlüsselung von Texten möglich, die mit einem Code verschlüsselt worden sind, der auf diesem Produkt basiert. Die Faktorisierung ist aber gerade bei großen Zahlen, es handelt sich hier um Zahlen mit 200 und mehr Stellen, sehr aufendig und langwierig.

In ihrem Vorteil liegt aber auch ihre Schwäche Es ist Bekannt, das die Zahl das Produkt aus zwei großen Primzahlen ist, und es ist nicht möglich, das die Zahl etwas das Produkt von drei, vier, fünf oder mehr Primzahlen ist. Damit kann man Verfahren einsetzten, die als Faktorisierungsverfahren ungeeignet sind, sich aber für diesen Speziellen Fall gut eignen.

Beispiel für ein RSA-Verfahren

Quadratischer Rest

Der quadratische Rest ist der Modulo, den man bekommt, wenn man eine Quadratzahl durch eine festgelegte Zahl ganzahlig dividiert.

Beispiel:

$169\mod 19=17$

Damit ist 17 ein Quadratischer Rest zur Zahl 19. Es ist nicht der einzige Quadratische Rest, und 169 ist nicht die einzige Quadratzahl, für die gilt, das $x\mod 19=17$ ist.

Soviel erstmal als Erklärung zum quadratischen Rest. In diesem Beispiel wird der qadratische Rest als Codebrecher mißbraucht. Bei dem oben gennante Bespiel (19 ist eine Primzahl) gibt es zu den meisten quadratischen Resten jeweils zwei Quadratzahlen, die diesen quadratischen Rest zurückliefern. Bei $N=p\cdot q$ gibt es für die meisten quadratischen Zahlen vier Quadratzahlen. Man kann leich systematisch eine Tabelle dieser 4-Tupel erstellen. Berücksichtigt werden dabei die Quadrate von 1 bis $(N-1)^{2}$ Als Beispiel soll die Zahl $147=13\cdot 19$ dienen:

$1\mod 147=1$

$4\mod 147=4$

$9\mod 147=9$

$16\mod 147=16$

$25\mod 147=25$

$36\mod 147=36$

$49\mod 147=49$

$64\mod 147=64$

$81\mod 147=81$

$100\mod 147=100$

$121\mod 147=121$

$144\mod 147=144$

$169\mod 147=22$

$196\mod 147=49$

$\cdots$

Folgende 4-Tupel hat die Zahl 147:

Fermatsche Pseudoprimzahl

Da für das RSA-Verfahren ein Produkt aus zwei, zueinander teilerfremden. Primzahlen gebildet wird, bildet die Basis des RSA-Verfahrens eine Zahl, die zu mindestens zwei Basen eine Fermatsche Pseudoprimzahl ist. Mit fermatschen Pseudoprimzahlen, zumal solchen, die nur das Produkt zweier Pseudoprimzahlen sind, hat es eine besondere Bewandnis. Nimmt man als Beispiel die fermatsche Pseudoprimzahl $91\$. Die Basen, zu denen die Pseudprimzahl 91 pseudoprim ist, sind: 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87 und 88. Von diesen Basen ist nicht jede Zahl geeignet. Also sucht man sich die geeigneten Basen heraus. Ungeeignet ist auf jeden Fall eine fortlaufende Zahlenfolge. Also 3 und 4 bzw. 9 und 10 sind zum Beispiel ungeeignet. Bleiben noch 12, 25, 27, 36, 38, 40, 43, 48, 51, 53, 55, 64, 66 und 79. Die Zahlen, auf die es in dem Fall ankommt sind 27 und 64. Warum? Weil 91 das Produkt aus 7 und 13 ist, und man aus 27 und 64 beide Faktoren gewinnen kann, denn links und rechts von 27 liegen 26 und 28, und links und rechts von 64 liegen 63 und 65, un d alle diese Zahlen enthalten einen der beiden Primfaktoren. Das ist kein Zufall, denn alle fermatschen Pseudoprimzahlen, die nur aus zwei Primfaktoren bestehen, und nur zu zwei Basen pseudoprim sind, erfüllen diese Eigenschaft wie 15 (4, 11), 21 (8, 13), 667 (231, 436), ... .

Bei einer zusammengesetzten Zahl $n=a\cdot b$ bei dem $a\$ und $b\$ die Primfaktoren bilden, kann man folgendes Verfahren anwenden:

Man bestimmt die Vielfachen von $a\$ und $b\$, die zwischen $1\$ und $n\$ liegen, also $a,\ 2a,\ 3a,\ \cdots$ und $b,\ 2b,\ 3b,\ \cdots$.

Nun sucht man jeweils ein Vielfaches von $a\$ und $b\$, wobei die Differenz dieser beiden Vielfachen $2\$ beträgt. Die Zahl, die zwischen diesen beiden Vielfachen liegt, ist eine Basis, zu der die Zahl $n\$ pseudoprim ist.

Beispiel: Man sucht Basen, zu denen die Zahl $91=7\cdot 13$ pseudoprim ist).

Die Vielfachen von $7\$ sind: $7,\ 14,\ 21,\ 28,\ 35,\ 42,\ 49,\ 56,\ 63,\ 70,\ 77,\ 84$ und $91\$.

Die Vielfachen von $13\$ sind: $13,\ 26,\ 39,\ 52,\ 65,\ 78$ und $91\$.

Ene Differenz von $2$ bilden $26\$ und $28\$, sowie $63\$ und $65\$. Mehr Zahlenpaare mit der Differenz $2$ wird man nicht finden. Daraus ergibt sich, das die Zahl $91\$ zu den Basen $27\$ und $64$ pseudoprim sind. Dabei sind die beiden Basen zueinander komplementär, da $27+64=91\$ ist.

Die Frage, die sich stellt ist: "Wie weit liegen die Basen zu der die Zahl $N=p\cdot q$ pseudoprim ist vom Rand weg?" oder "Wie leicht läßt sich eine der gesuchten Basen durch Brute-Force finden?"

Da man ja bei der Zahl $N\$ die beiden Primfaktoren ja nicht kennt, sondern nur bekannt ist, das $N\$ aus genau zwei Primfaktoren zusammengesetzt ist, kann man ja das Verfahren über die Vielfachen nicht anwenden.

Bei kleinen Zahlen liegen, mit Ausnahmen (15 [4;11], 35 [6;29], 143 [12;131]), die kleineren der beiden Basen jeweils weit jenseits von ${\sqrt {n}}$, so das ein Brute Force im Sinne des naiven Durchtestens auf Teilbarkeit erfolgreicher erscheint, als das Suchen nach Basen, zu denen die Zahl $N\$ pseudoprim ist, und deren Nachbarn beide Vielfache von $N\$ sind.