RSA-Beispiel mit kleinen Zahle < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Hi, ich habe eine Frage zu einem einführenden Zahlenbeispiel zur RSA-Verschlüsselung.
Warum wird für p:=7 q:=13 und e:=25 alles auf sich selbst abgebildet, also: Warum ist a^25 mod 91 = a mod 91 ? |
Es geht also um das multiplikative Inverse einer Zahl e im Ring
[mm] ({x^z|z aus Z}, [/mm] *(p,q):=x^(p*q))
Wir haben hier also ϕ(N)=72 und e=25.
Es gilt für alle a:
a^25 mod 91 = a mod 91
Wählt man e=35, so ist (a^35)^35 mod 91 = a mod 91
Der öffentliche "Schlüssel" wäre also gleich dem privaten.
Klar ist, dass RSA auf dem Faktorisierungsproblem beruht und für so kleine Zahlen keinerlei Sinn ergibt.
Man wird bei riesigen Zahlen auch lieber direkt eine Primzahl e wählen, als den ggT(ϕ(N), e?) zu berechnen.
Trotzdem rein aus Interesse: Warum ergibt sich für e=25 oder e=35 in diesem speziellen Ring mod 91=7*13 dieses Verhalten?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:28 So 02.03.2014 | | Autor: | SuRRioR |
In der tatsächlichen anwendung wird in fast immer [mm] $e=2^{16}+1$ [/mm] gewählt. [mm] $2^{16}+1$ [/mm] ist eine Primzahl womit $ggT(p(N), e)=1$ sichergestellt ist (ist $ggT(p(N), [mm] e)\not=1$ [/mm] gibt es kein multiplikatives Inverses).
Warum bei kleinen Zahlen der öffentliche Schlüssel gleich dem privaten ist und der ciphertext in den meissten Fällen dem plaintext entspricht kann ich dir leider nicht sagen :/
|
|
|
| |
|
Hallo SuRRioR,
>
> [mm]2^{16}+1[/mm] ist eine Primzahl womit
> [mm]ggT(p(N), e)=1[/mm] sichergestellt ist (ist [mm]ggT(p(N),
> e)\not=1[/mm]
Das ist falsch. Es gibt unendlich viele Primzahl p, mit [mm] $2^{16}+1|p-1$ [/mm] nach dem Dirichletschen Primzahlsatz https://de.wikipedia.org/wiki/Dirichletscher_Primzahlsatz .
Die Wahl von e als Primzahl verringert allerdings die Wahrscheinlichkeit für [mm] $ggT(\varphi(N),e) \neq [/mm] 1$, ebenso wie die Wahl größerer e.
|
|
|
| |
|
Hallo,
das Beispiel ist *hust*extrem unglücklich*hust* gewählt. (außer es ist die Absicht die Unzulänglichkeiten von [mm] $\varphi$ [/mm] aufzuzeigen)
Es gilt [mm] $a^{12}\equiv [/mm] 1 [mm] \mod 7\cdot [/mm] 13$ für alle $a [mm] \in (\mathbb [/mm] Z/91 [mm] \mathbb Z)^\times$,
[/mm]
siehe https://de.wikipedia.org/wiki/Carmichael-Funktion
Da N quadratfrei gilt sogar (chin. Restsatz):
$a [mm] \equiv a^{k\cdot 12 +1} \mod [/mm] N$ für alle $a [mm] \in \mathbb [/mm] N$,$ [mm] 1\leq [/mm] k [mm] \in \mathbb [/mm] N$
Für e ist es nicht unbedingt wichtig ob es prim ist;ferner ist i.d.R keine Faktorzerlegung von [mm] $\varphi(pq)$bekant; [/mm] wichtiger ist, dass man schnell mit e multiplizieren kann, also e sollte insbesondere fast nur aus 0 in der Binärdarstellung bestehen. Die Berechnung eines ggT geht sehr schnell.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:36 Mo 03.03.2014 | | Autor: | moritzrbk |
Es war, zugegeben, nicht ein Beispiel von einem Prof o.ä., sondern ich hatte nur mit den Werten herumprobiert und bin darauf gestoßen. Habe aber keine Ahnung von Zahlen- und Gruppentheorie.
|
|
|
|
