matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieHohe Potenzen im RSA
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Zahlentheorie" - Hohe Potenzen im RSA
Hohe Potenzen im RSA < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hohe Potenzen im RSA: RSA
Status: (Frage) beantwortet Status 
Datum: 16:52 Do 23.10.2014
Autor: Marcel

Aufgabe
Hallo zusammen,

ich habe gestern einfach mal versucht, mir mit Octave ein kleines Skript
zu schreiben, welche das RSA-Verfahren demonstriert. Natürlich schicke
ich mir da selbst eine Nachricht, verschlüssele sie und entschlüssele sie,
einfach zum Testen.
Leider funktioniert das nicht. Ein erster Fehler, der mir aufgefallen war, war,
dass ich das Alphabet (in Kleinbuchstaben) inklusive Leerzeichen natürlich
mit 26+1 Zeichen ausgestattet hatte, und wenn $n=p*q < [mm] 27\,$ [/mm] ist, dann kann
es eigentlich auch nicht sinnvoll funktionieren.
Nun habe ich [mm] $p=5\,$ [/mm] und [mm] $q=7\,,$ [/mm] und mit einer geeigneten Wahl von [mm] $e\,$ [/mm] mit
$1 < e < [mm] \varphi(n)$ [/mm] und [mm] $\ggT(e, \phi(n))=1$ [/mm] (bei mir [mm] $e=5\,$) [/mm] konnte ich es testen,
und das funktioniert. Leider habe ich nun folgendes Problem:


Ich finde keine guten anderen Test-Tupel. Oft ist es einfach so, dass Octave
an seine Grenzen kommt, wenn man eine etwas größere Zahl potenziert,
denn dann kommt Octave irgendwann mit der anschließenden "mod n" Rechnung
nicht mehr klar.

Beispiel:
In Octave ist

    [mm] $\mod(19^{39}+k,35)=0$ [/mm]

für [mm] $k=1,\,2,\,3,...$ [/mm]

Das macht keinen Sinn. Hat jemand eine Idee, wie man dieses Problem
umgehen kann?

(Wenn es eine allgemeine Strategie gibt, dann wäre es gut, wenn man die
*algorithmisch* beschreiben kann, damit ich die einpflegen kann. Ich kenne
ja auch Sätze wie den kleinen Fermat mit [mm] $a^p \equiv [/mm] a$ [mm] $\mod [/mm] p$ für $p [mm] \in \IP,$ [/mm]
oder auch den Satz von Euler mit [mm] $a^{\varphi(n)} \equiv [/mm] 1 [mm] \mod [/mm] n$. Aber ich
sehe gerade nicht, ob oder wie die helfen - denn $n=p*q$ ist natürlich keine
Primzahl...).

Gruß,
  Marcel

        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:04 Do 23.10.2014
Autor: Marcel

P.S. Eine erste Idee, die mir gerade gekommen ist:

    [mm] $19^{39} \equiv 19*19^{38} \equiv 19*(19^2)*{19^{19}} \mod [/mm] 35$

Kann man sowas sukzessive ausnutzen? (Oder habe ich da einen Denkfehler?)

Denn oben würde man

    [mm] $\mod(19^2,35)$ [/mm]

natürlich schonmal gut in Octave einprogrammieren können...

Gruß,
  Marcel

Bezug
        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 17:07 Do 23.10.2014
Autor: MathePower

Hallo Marcel,

> Hallo zusammen,
>  
> ich habe gestern einfach mal versucht, mir mit Octave ein
> kleines Skript
>  zu schreiben, welche das RSA-Verfahren demonstriert.
> Natürlich schicke
>  ich mir da selbst eine Nachricht, verschlüssele sie und
> entschlüssele sie,
>  einfach zum Testen.
> Leider funktioniert das nicht. Ein erster Fehler, der mir
> aufgefallen war, war,
>  dass ich das Alphabet (in Kleinbuchstaben) inklusive
> Leerzeichen natürlich
>  mit 26+1 Zeichen ausgestattet hatte, und wenn [mm]n=p*q < 27\,[/mm]
> ist, dann kann
>  es eigentlich auch nicht sinnvoll funktionieren.
> Nun habe ich [mm]p=5\,[/mm] und [mm]q=7\,,[/mm] und mit einer geeigneten Wahl
> von [mm]e\,[/mm] mit
>  [mm]1 < e < \varphi(n)[/mm] und [mm]\ggT(e, \phi(n))=1[/mm] (bei mir [mm]e=5\,[/mm])
> konnte ich es testen,
> und das funktioniert. Leider habe ich nun folgendes
> Problem:
>  
> Ich finde keine guten anderen Test-Tupel. Oft ist es
> einfach so, dass Octave
>  an seine Grenzen kommt, wenn man eine etwas größere Zahl
> potenziert,
>  denn dann kommt Octave irgendwann mit der anschließenden
> "mod n" Rechnung
>  nicht mehr klar.
>
> Beispiel:
> In Octave ist
>  
> [mm]\mod(19^{39}+k,35)=0[/mm]
>  
> für [mm]k=1,\,2,\,3,...[/mm]
>  
> Das macht keinen Sinn. Hat jemand eine Idee, wie man dieses
> Problem
>  umgehen kann?
>  


Die einfachste Variante ist:

1:
2: z=mod(19,35)
3: for i=1:38
4:   z=mod(19*z,35)
5: endfor
6: z=mod(z+k,35)



> (Wenn es eine allgemeine Strategie gibt, dann wäre es gut,
> wenn man die
>  *algorithmisch* beschreiben kann, damit ich die einpflegen
> kann. Ich kenne
>  ja auch Sätze wie den kleinen Fermat mit [mm]a^p \equiv a[/mm]
> [mm]\mod p[/mm] für [mm]p \in \IP,[/mm]
>  oder auch den Satz von Euler mit
> [mm]a^{\varphi(n)} \equiv 1 \mod n[/mm]. Aber ich
>  sehe gerade nicht, ob oder wie die helfen - denn [mm]n=p*q[/mm] ist
> natürlich keine
> Primzahl...).
>  
> Gruß,
>    Marcel


Gruss
MathePower

Bezug
                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:11 Do 23.10.2014
Autor: Marcel

Hallo Mathepower,

> Hallo Marcel,
>  
> > Hallo zusammen,
>  >  
> > ich habe gestern einfach mal versucht, mir mit Octave ein
> > kleines Skript
>  >  zu schreiben, welche das RSA-Verfahren demonstriert.
> > Natürlich schicke
>  >  ich mir da selbst eine Nachricht, verschlüssele sie
> und
> > entschlüssele sie,
>  >  einfach zum Testen.
> > Leider funktioniert das nicht. Ein erster Fehler, der mir
> > aufgefallen war, war,
>  >  dass ich das Alphabet (in Kleinbuchstaben) inklusive
> > Leerzeichen natürlich
>  >  mit 26+1 Zeichen ausgestattet hatte, und wenn [mm]n=p*q < 27\,[/mm]
> > ist, dann kann
>  >  es eigentlich auch nicht sinnvoll funktionieren.
> > Nun habe ich [mm]p=5\,[/mm] und [mm]q=7\,,[/mm] und mit einer geeigneten Wahl
> > von [mm]e\,[/mm] mit
>  >  [mm]1 < e < \varphi(n)[/mm] und [mm]\ggT(e, \phi(n))=1[/mm] (bei mir
> [mm]e=5\,[/mm])
> > konnte ich es testen,
> > und das funktioniert. Leider habe ich nun folgendes
> > Problem:
>  >  
> > Ich finde keine guten anderen Test-Tupel. Oft ist es
> > einfach so, dass Octave
>  >  an seine Grenzen kommt, wenn man eine etwas größere
> Zahl
> > potenziert,
>  >  denn dann kommt Octave irgendwann mit der
> anschließenden
> > "mod n" Rechnung
>  >  nicht mehr klar.
> >
> > Beispiel:
> > In Octave ist
>  >  
> > [mm]\mod(19^{39}+k,35)=0[/mm]
>  >  
> > für [mm]k=1,\,2,\,3,...[/mm]
>  >  
> > Das macht keinen Sinn. Hat jemand eine Idee, wie man dieses
> > Problem
>  >  umgehen kann?
>  >  
>
>
> Die einfachste Variante ist:
>  
>
1:
2: >  z=mod(19,35)
3: >  for i=1:38
4: >    z=mod(19*z,35)
5: >  endfor
6: >  z=mod(z+k,35)
7: >  


[bonk]

Du nutzt also

    $a [mm] \equiv [/mm] b [mm] \mod [/mm] n$

    [mm] $\Rightarrow$ $a^k \equiv b^k \mod [/mm] n$

für $k [mm] \in \IN$ [/mm] aus.

Danke. Und ich dachte mir auch schon, dass das Berechnen von [mm] $19^{39}$ [/mm]
(in [mm] $\IR$) [/mm] doch überflüssig sein muss...

Manchmal sieht man den Wald vor lauter Bäumen nicht. :-)

Gruß,
  Marcel

Bezug
                
Bezug
Hohe Potenzen im RSA: RSA - Fall p=q
Status: (Frage) beantwortet Status 
Datum: 15:02 Fr 24.10.2014
Autor: Marcel

Aufgabe
Hallo,

nur, weil diese Frage bei mir gerade bei der Ausführung des entsprechenden
Programms aufgetaucht war:

Muss man beim RSA-Verfahren eigentlich den Fall p=q ausschließen? Von der
Theorie her habe ich drüber nachgedacht und finde dafür eigentlich keinen
Grund.

Von der Praxis her sehe ich, dass mein Programm im Falle p=q leider öfters
falsch codiert. Da tauchen plötzlich Nullen auf...

Ist der Fall p=q nicht erlaubt? Ich hatte mich nämlich auch schon immer
gewundert, wieso da bei dem Primzahlprodukt nur 2 Primzahlen stehen...
Oder ist sowas eigentlich doch erlaubt, hat aber andere Gründe, warum
das keiner macht (vllt. ist der Key leichter zu knacken, wenn Primzahl
inklusive Vielfachheiten gewählt werden...)?

Gruß,
  Marcel

Bezug
                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 15:26 Fr 24.10.2014
Autor: reverend

Hallo Marcel,

in der Tat muss für den öffentlichen Schlüssel $n=pq$ gelten: [mm] p,q\in\IP\;\wedge\;p\not={q}. [/mm]

Grüße
rev

Bezug
                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:57 Fr 24.10.2014
Autor: Marcel

Hallo reverend (und Teufel),

> in der Tat muss für den öffentlichen Schlüssel [mm]n=pq[/mm]
> gelten: [mm]p,q\in\IP\;\wedge\;p\not={q}.[/mm]

aber wie begründet sich das? Ich kann gerne auch mal nach öffentlicher
Literatur gucken, aber bis auf die Tatsache, dass man natürlich sowieso
erstmal Primzahlen in der Nähe und kleinergleich [mm] $\sqrt{n}$ [/mm] suchen würde, um
den Key zu knacken:
Von der Theorie her sehe ich keinen Grund, warum das schiefgehen kann.
In der Praxis geht es öfters gut, aber ab und an geht es dann komischerweise
doch schief.

Ich kann ja demnächst auch mal ein konretes Zahlenbeispiel hinschreiben.

@ Teufel: Dass man die zu kodierenden Zahlen auch als Einheiten wählen
sollte, hatte ich im Gefühl. Aber auch da sagt die Theorie doch nicht, dass
das notwendig wäre?
Über Deinen Hinweis, dass der Key sonst evtl. leicht zu knacken wäre, muss
ich nochmal nachdenken...

Gruß,
  Marcel

Bezug
                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 17:39 Fr 24.10.2014
Autor: Teufel

Ja, für gewöhnlich sind die Primfaktoren von $N$ in RSA gut balanciert, soll heißen, dass die Bitlängen (=Anzahl der Ziffern im Binärsystem) ungefähr gleich sind. Das hat einige Vorteile, weil es einige Angriffe gegen RSA gibt, die Unbalanciertheit ausnutzen können.

Und die Nachrichten müssen nicht unbedingt aus [mm] \IZ_N^\times [/mm] sein. Verschlüsselung und Entschlüsselung funktionieren für [mm] $p\not=q$ [/mm] genau wie für Elemente aus der Einheitengruppe. Aber dann hat man das Problem, dass ein Angreifer dadurch die Faktorisierung geschenkt bekommt,weil ggT-Berechung effizient durchführbar ist. In der Praxis ist das aber weniger ein Problem, weil man einfach aufpassen kann, dass Nachrichten immer in der Einheitengruppe landen. Und auch wenn man das nicht tut, dann ist ein (uniform) zufällig gezogenes [mm] $m\in\IZ_N$ [/mm] mit Wahrscheinlichkeit [mm] $\frac{\varphi(N)}{N}\ge1-\frac{3}{p}$ [/mm] in der Einheitengruppe, was für große $N$ und Balanciertheit, echt nah an 1 ist. hier auch wieder das Problem: Ist $p$ ein zu kleiner Faktor von $N$, dann kann man einfach so lange Werte $m$ erzeugen, bis man nicht in der Einheitengruppe landet.


Bezug
                                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 01:18 Sa 25.10.2014
Autor: Marcel

Hallo Teufel,

> Ja, für gewöhnlich sind die Primfaktoren von [mm]N[/mm] in RSA gut
> balanciert, soll heißen, dass die Bitlängen (=Anzahl der
> Ziffern im Binärsystem)

der Begriff ist mir bekannt. ;-)

> ungefähr gleich sind. Das hat
> einige Vorteile, weil es einige Angriffe gegen RSA gibt,
> die Unbalanciertheit ausnutzen können.

Das ist für mich durchaus interessant, aber erst im nächsten Schritt. Die
ganzen Infos werde ich mir demnächst auch nochmal notieren.

> Und die Nachrichten müssen nicht unbedingt aus
> [mm]\IZ_N^\times[/mm] sein. Verschlüsselung und Entschlüsselung
> funktionieren für [mm]p\not=q[/mm] genau wie für Elemente aus der
> Einheitengruppe.

Genau das ist ja etwas, was ich auch sehe. Daher kam meine Rückfrage
(ohne Bezug auf Sicherheitsaspekte). Okay, diese Frage ist für mich erstmal
geklärt. :-)

> Aber dann hat man das Problem, dass ein
> Angreifer dadurch die Faktorisierung geschenkt bekommt,weil
> ggT-Berechung effizient durchführbar ist.

Die "Sicherheitsaspekte" lasse ich momentan eigentlich außen vor. Mir geht
es erstmal um's "verstehen, wie das funktioniert". Deine Hinweise sind
aber dennoch sehr wichtig, also durchaus weiter auch solche Informationen
mitteilen.

> In der Praxis ist das aber weniger ein Problem, weil man einfach
> aufpassen kann, dass Nachrichten immer in der
> Einheitengruppe landen. Und auch wenn man das nicht tut,
> dann ist ein (uniform) zufällig gezogenes [mm]m\in\IZ_N[/mm] mit
> Wahrscheinlichkeit [mm]\frac{\varphi(N)}{N}\ge1-\frac{3}{p}[/mm] in
> der Einheitengruppe, was für große [mm]N[/mm] und Balanciertheit,
> echt nah an 1 ist. hier auch wieder das Problem: Ist [mm]p[/mm] ein
> zu kleiner Faktor von [mm]N[/mm], dann kann man einfach so lange
> Werte [mm]m[/mm] erzeugen, bis man nicht in der Einheitengruppe
> landet.

  
Was ich allerdings momentan immer noch nicht rauslesen kann: Der
RSA Algorithmus funktioniert bei mir für $p [mm] \not=q$ [/mm] prima. Für [mm] $p=q\,,$ [/mm] auch, wenn
dieser Fall "praktisch nie benutzt werden wird", läuft da aber irgendwas schief.

Jetzt gibt es für mich 2 Möglichkeiten:
1. Fall: Beim nachvollziehen der Theorie übersehe ich eine Stelle, wo der
RSA $p [mm] \not=q$ [/mm] voraussetzen muss, damit er so funktionieren kann, wie er funktionieren
soll. Ich finde diese Stelle aber nicht, daher wäre es toll, wenn mir jemand
sagen könnte:
"Naja, im Falle [mm] $p=q\,$ [/mm] geht dann jedenfalls dann etwas schief, wenn zudem..."

2. Fall: Ich muss einfach nach einem Fehler in meinem Programm suchen. Das
würde mich aber irritieren, denn ich habe gleiches extra mal auf einem
alternativen Weg getestet.

Dazu sei gesagt: Man sagt ja beim RSA, dass man [mm] $\varphi(N)=(p-1)*(q-1)$ [/mm] leicht
ausrechnen könne. Ich habe das im Fall [mm] $p=q\,$ [/mm] auch schon korrigiert, denn in
diesem Falle muss ja

    [mm] $\varphi(N)=p*(p-1)$ [/mm]

gelten. Daran liegt es also nicht. Und, wie gesagt: Manchmal funktioniert
das bei [mm] $p=q\,,$ [/mm] manchmal auch nicht. Nur die Potenz bei der Kodierungs- bzw.
Dekodierungsfunktion ist bei mir da immer etwas anders, aber sie ist schon
so gewählt, dass [mm] $\ggT(e,\varphi(N))=1$ [/mm] gilt.

Daher verwundert mich das...

Gruß,
  Marcel

Bezug
                                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 01:56 Sa 25.10.2014
Autor: Teufel

Hi!

Ohne das jetzt genau durchzusehen: Der Beweis, dass RSA für [mm] $p\not=q$ [/mm] auch für [mm] $m\notin\IZ_N^\times$ [/mm] korrekt funktioniert, nutzt den Chinesischen Restsatz aus. Den hat man für $p=q$ in [mm] \IZ_{p^2} [/mm] ja nicht mehr so richtig zur Verfügung. Eventuell geht das deswegen schief. Im Fall [mm] $N=p^2$ [/mm] geht natürlich auch immer die Ver- und Entschlüsselung von $m=p$ schief, wenn man mal von [mm] $e\not=1$ [/mm] ausgeht (der Fall $e=1$ ist auch wieder witzlos, weil man damit auch den geheimen Schlüssel $d$ geschenkt bekommt, der dann auch 1 ist).

Also gilt schon immer [mm] $m^e\equiv 0\mod{p}$ [/mm] und kann daher nicht mehr korrekt entschlüsselt werden. Also hat man immer ein Gegenbeispiel für $p=q$, was man für [mm] $p\not=q$ [/mm] nicht mehr finden kann. du kannst ja auch mal selbst versuchen zu zeigen, dass RSA immer korrekt für [mm] $p\not=q$ [/mm] läuft, das Stichwort hast du ja jetzt schon. ;)

Bezug
                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:01 Sa 25.10.2014
Autor: Marcel

Hallo Teufel,

> Hi!
>  
> Ohne das jetzt genau durchzusehen: Der Beweis, dass RSA
> für [mm]p\not=q[/mm] auch für [mm]m\notin\IZ_N^\times[/mm] korrekt
> funktioniert, nutzt den Chinesischen Restsatz aus. Den hat
> man für [mm]p=q[/mm] in [mm]\IZ_{p^2}[/mm] ja nicht mehr so richtig zur
> Verfügung. Eventuell geht das deswegen schief.

mhm, in dem Buch hier steht

    [mm] $m^{\varphi(n)+1} \equiv [/mm] m [mm] \mod [/mm] n$

für alle $m [mm] \in \IZ/n\IZ\,,$ [/mm] und das folgt nach dem gruppentheoretischen
Satz von Lagrange. Ich sehe da gerade nicht, wieso der Chinesische Restsatz
da eine Rolle spielt. Da muss ich nochmal drüber nachdenken...

> Im Fall
> [mm]N=p^2[/mm] geht natürlich auch immer die Ver- und
> Entschlüsselung von [mm]m=p[/mm] schief, wenn man mal von [mm]e\not=1[/mm]
> ausgeht (der Fall [mm]e=1[/mm] ist auch wieder witzlos, weil man
> damit auch den geheimen Schlüssel [mm]d[/mm] geschenkt bekommt, der
> dann auch 1 ist).

Klar. Ich gebe vielleicht morgen einfach mal ein Beispiel an, wo ich das
sehe, dass da etwas schiefgeht.

> Also gilt schon immer [mm]m^e\equiv 0\mod{p}[/mm] und kann daher
> nicht mehr korrekt entschlüsselt werden.

Okay, ich muss mal gucken, ob vielleicht gerade die Nicht-invertierbaren "m's"
dieses Problem erzeugen. Das würde für Deine Erklärung sprechen. Aber
das erst morgen im Laufe des Tages, oder evtl. übermorgen...

P.S. Mal ein großes Dankeschön für Deinen Einsatz (natürlich auch den
anderen, aber Deiner sticht gerade besonders hervor). :-)

Gruß,
  Marcel

Bezug
                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:14 Sa 25.10.2014
Autor: Teufel

Du meinst [mm] $m^{\varphi(n)}\equiv [/mm] 1 [mm] \mod{n}$, [/mm] oder? Aber du musst hier aufpassen, in welcher Gruppe du den Lagrange anwendest. Deine Gruppe ist hier [mm] \IZ_n^\times, [/mm] die eine Ordnung von [mm] \varphi(n) [/mm] besitzt. Daher gilt [mm] $m^{\varphi(n)}\equiv [/mm] 1 [mm] \mod{n}$ [/mm] für alle [mm] $m\in\IZ_n^\times$. [/mm] Für [mm] $m\in\IZ_n\setminus\IZ_n^\times$ [/mm] sagt der Lagrange hier nichts aus, weil [mm] $(\IZ_n, \cdot)$ [/mm] ja keine Gruppe mehr ist (2 ist modulo 4 nicht invertierbar).

Und kein Problem, löcher mich ruhig weiter. ;) Aber ich geh jetzt erst mal schlafen... Gute Nacht und ich schau morgen wieder rein! Wie bist du überhaupt darauf gekommen dich mit RSA zu beschäftigen? War es durch den Thread jetzt hier? :D

Bezug
                                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:33 Sa 25.10.2014
Autor: Marcel

Hallo,

> Du meinst [mm]m^{\varphi(n)}\equiv 1 \mod{n}[/mm], oder?

ja, ich habe es etwas abgewandelt, aber ja.

> Aber du musst hier aufpassen, in welcher Gruppe du den Lagrange
> anwendest. Deine Gruppe ist hier [mm]\IZ_n^\times,[/mm] die eine
> Ordnung von [mm]\varphi(n)[/mm] besitzt.

Klar, das ist die Einheitengruppe.

> Daher gilt [mm]m^{\varphi(n)}\equiv 1 \mod{n}[/mm] für alle [mm]m\in\IZ_n^\times[/mm].
> Für [mm]m\in\IZ_n\setminus\IZ_n^\times[/mm] sagt der Lagrange hier
> nichts aus, weil [mm](\IZ_n, \cdot)[/mm] ja keine Gruppe mehr ist (2
> ist modulo 4 nicht invertierbar).

Da wird wohl ein gedanklicher Fehler bei mir liegen - der entstand dann
aber durchaus auch aus dem Buch, denn die schreiben dort:
"... schreibt er die Nachricht als eine Folge von Zahlen [mm] $m_1,...,m_l \in \IZ/n\IZ\,.$" [/mm]

Da wurde ich auch schon etwas stutzig, aber aus einem anderen Grund:
Es gibt ja nur [mm] $\varphi(n) [/mm] < n$ invertierbare Elemente in [mm] $\IZ/n\IZ\,.$ [/mm]

Jetzt sehe ich meinen Denkfehler: Dass [mm] $\IZ/n\IZ$ [/mm] eine Gruppe ist, haben wir
aber dann, wenn [mm] $n=p*q\,$ [/mm] Produkt zweier Primzahlen ist. Okay, das muss
ich mir nun definitiv notieren (ich hoffe, dass das stimmt - aber ich denke, dass
das genau die Stelle ist, wo der chinesische Restsatz eingeht - man, ist das
*versteckt*).

> Und kein Problem, löcher mich ruhig weiter. ;) Aber ich
> geh jetzt erst mal schlafen... Gute Nacht und ich schau
> morgen wieder rein! Wie bist du überhaupt darauf gekommen
> dich mit RSA zu beschäftigen? War es durch den Thread
> jetzt hier? :D

Ganz einfach: In dem Buch (Müller-Stach,Piontkowski: Elementare Algebra
und Zahlentheorie) steht der so schön in 5 Zeilen beschrieben, da wollte
ich mir mal selbst demonstrieren, wie der funktioniert. Und da habe ich eben
gesehen, dass ich da manchmal Kuriositäten erlebe. Übrigens wäre es
vielleicht nett, wenn die Autoren in ihrem Werk dazugeschrieben hätten,
dass man zum einen den Fall [mm] $p=q\,$ [/mm] nicht benutzen sollte (alleine schon,
weil sonst der Code zu schnell zu knacken wäre), und zum anderen vor allem
aber, dass man im Falle [mm] $p=q\,$ [/mm] bei [mm] $\IZ/(p*q)\IZ$ [/mm] keine Gruppe mehr hat, und
Lagrange dann sinnlos wird.
Das sind meines Erachtens typische Fehlerquellen; jedenfalls habe ich wohl
auch eine Gabe, solche *Pingeligkeiten* immer irgendwie aufzuspühren,
und dann wundern mich die Ergebnisse...

Gruß,
  Marcel

Bezug
                                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:20 Sa 25.10.2014
Autor: Teufel

Hi! :)

Nein, aber auch so gilt das nicht, z.B. für n=4, m=2. Dann ist [mm] m^{\varphi(n)+1}=2^{2+1}=0\not=2 \mod{4}. [/mm] Problem ist, dass $m$ gar nicht in der Einheitengruppe liegt und das Resultat von Lagrange da keine Anwendung finden kann im Allgemeinen (für m=0 stimmt es natürlich).

Es ist so, als wenn man sich z.B. [mm] $G=(\IZ_6,+)$ [/mm] als Gruppe nimmt und davon [mm] $H=\{0,3\}$ [/mm] als Untergruppe. $H$ hat die Ordnung 2 und Lagrange sagt dann, dass für alle Elemente in $H$ gilt $2*h=0$ (hier ist Addition die Verknüpfung, daher schreibe ich nicht [mm] h^2). [/mm] In der Tat gilt das auch, aber nur für Elemente in $H$ (0+0=0, 3+3=0).
Du oder das Buch versuchen das aber nun einfach auf alle Elemente in $G$ auszubreiten und sagen, dass auch $2*1=0$, $2*2=4$, $2*4=0$ und $2*5=0$ gelten muss, aber das stimmt ja nicht.

Und [mm] $(\IZ_n,\cdot)$ [/mm] ist nie eine Gruppe, weil dort immer die 0 enthalten ist, die aber kein Inverses hat, was in einer Gruppe aber gegeben sein muss. Das ist unabhängig davon, wie $n$ zusammengesetzt ist. Oder wenn $n=pq$ ist, dann ist $m=p$ auch nicht invertierbar, egal ob $p=q$ oder nicht.

Du musst also immer schauen, w du den Lagrange überhaupt anwendest. Nehmen wir nochmal [mm] $n=p^2$. [/mm] Dann ist [mm] $(\IZ_p^\times, \cdot)=(\{m\in\IZ_n\;|\;\text{ggT}(z,n)=1\}, \cdot)$ [/mm] eine Gruppe. Ihre Ordnung ist [mm] $\varphi(n)=p(p-1)$. [/mm] Damit gilt der Lagrange dort und besagt, dass für alle [mm] $m\in\IZ_n^\times$ [/mm] gilt [mm] $m^{p(p-1)}=1\mod{n}$ [/mm] oder eben [mm] $m\in\IZ_n^\times$ [/mm] gilt [mm] $m^{p(p-1)+1}=m\mod{n}$. [/mm] Für $p=2$ erhalten wir wieder $n=4$ und Lagrange klappt für $m=1$ oder $m=3$. Für $m=2$ schlägt es fehl und für $m=0$ ist wenigstens die zweite Formulierung gültig.

Ich war Anfangs auch etwas verwirrt davon, weil [mm] \IZ_n [/mm] ja auch ein Ring ist und man da addieren und multiplizieren kann, wie man lustig ist, aber für manche Aussagen will man diesen Ring eher als Gruppe betrachten, bei RSA die multiplikative Gruppe. Aber dafür darf man nur Einheiten zulassen, damit man überhaupt von einer Gruppe sprechen kann und Sachen wie den Lagrange anwenden kann.

Bezug
                                                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:52 Sa 25.10.2014
Autor: Marcel

Hi Teufel,

> Hi! :)
>  
> Nein, aber auch so gilt das nicht, z.B. für n=4, m=2. Dann
> ist [mm]m^{\varphi(n)+1}=2^{2+1}=0\not=2 \mod{4}.[/mm] Problem ist,
> dass [mm]m[/mm] gar nicht in der Einheitengruppe liegt und das
> Resultat von Lagrange da keine Anwendung finden kann im
> Allgemeinen (für m=0 stimmt es natürlich).
>  
> Es ist so, als wenn man sich z.B. [mm]G=(\IZ_6,+)[/mm] als Gruppe
> nimmt und davon [mm]H=\{0,3\}[/mm] als Untergruppe. [mm]H[/mm] hat die
> Ordnung 2 und Lagrange sagt dann, dass für alle Elemente
> in [mm]H[/mm] gilt [mm]2*h=0[/mm] (hier ist Addition die Verknüpfung, daher
> schreibe ich nicht [mm]h^2).[/mm] In der Tat gilt das auch, aber nur
> für Elemente in [mm]H[/mm] (0+0=0, 3+3=0).
> Du oder das Buch versuchen das aber nun einfach auf alle
> Elemente in [mm]G[/mm] auszubreiten und sagen, dass auch [mm]2*1=0[/mm],
> [mm]2*2=4[/mm], [mm]2*4=0[/mm] und [mm]2*5=0[/mm] gelten muss, aber das stimmt ja
> nicht.
>  
> Und [mm](\IZ_n,\cdot)[/mm] ist nie eine Gruppe, weil dort immer die
> 0 enthalten ist, die aber kein Inverses hat, was in einer
> Gruppe aber gegeben sein muss. Das ist unabhängig davon,
> wie [mm]n[/mm] zusammengesetzt ist. Oder wenn [mm]n=pq[/mm] ist, dann ist [mm]m=p[/mm]
> auch nicht invertierbar, egal ob [mm]p=q[/mm] oder nicht.
>  
> Du musst also immer schauen, w du den Lagrange überhaupt
> anwendest. Nehmen wir nochmal [mm]n=p^2[/mm]. Dann ist
> [mm](\IZ_p^\times, \cdot)=(\{m\in\IZ_n\;|\;\text{ggT}(z,n)=1\}, \cdot)[/mm]
> eine Gruppe. Ihre Ordnung ist [mm]\varphi(n)=p(p-1)[/mm]. Damit gilt
> der Lagrange dort und besagt, dass für alle
> [mm]m\in\IZ_n^\times[/mm] gilt [mm]m^{p(p-1)}=1\mod{n}[/mm] oder eben
> [mm]m\in\IZ_n^\times[/mm] gilt [mm]m^{p(p-1)+1}=m\mod{n}[/mm]. Für [mm]p=2[/mm]
> erhalten wir wieder [mm]n=4[/mm] und Lagrange klappt für [mm]m=1[/mm] oder
> [mm]m=3[/mm]. Für [mm]m=2[/mm] schlägt es fehl und für [mm]m=0[/mm] ist wenigstens
> die zweite Formulierung gültig.
>  
> Ich war Anfangs auch etwas verwirrt davon, weil [mm]\IZ_n[/mm] ja
> auch ein Ring ist und man da addieren und multiplizieren
> kann, wie man lustig ist, aber für manche Aussagen will
> man diesen Ring eher als Gruppe betrachten, bei RSA die
> multiplikative Gruppe. Aber dafür darf man nur Einheiten
> zulassen, damit man überhaupt von einer Gruppe sprechen
> kann und Sachen wie den Lagrange anwenden kann.

ja, mhm, irgendwie ist das jetzt auch verwirrend.

1. Warum schreiben die dann, dass man die $m [mm] \in \IZ/n\IZ$ [/mm] nehmen kann? Dann
ist das doch falsch, es müssen doch wohl eher die $m [mm] \in (\IZ/n\IZ)^\times$ [/mm] gewählt
werden müssen. Ansonsten funktioniert Lagrange gar nicht. Dann machen
die Autoren dort einen Fehler, oder? Falls ja, so würde ich sie per Mail drauf
aufmerksam machen.

2. Okay, wenn ich das richtig sehe, müßte man dann sagen, dass

    [mm] $(\IZ/(p*q)\IZ)^\times$ [/mm]

eine Gruppe sein muss. Jetzt bin ich aber verwirrt, denn dass das für $p [mm] \not=q$ [/mm] aus
dem chinesischen Restsatz folgt (stimmt das jetzt?), scheint mir klar. Und für
[mm] $p=q\,$ [/mm] muss das nicht sein?

Ich glaube, ich muss mir einfach mal alles, was ich weiß, nochmal hinschreiben,
denn irgendwie verliere ich da ein wenig den Überblick... Ob das nun meine
eigene Schuld ist, oder ob da im Buch etwas falsches steht, oder ich nur
etwas aus dem Buch falsch interpretiere... Keine Ahnung, aber ich muss
es irgendwie *entwirrt* bekommen. ^^

P.S. Mein [mm] $n\,$ [/mm] hier war Dein [mm] $N\,,$ [/mm] also [mm] $=p*q\,.$ [/mm]

Gruß,
  Marcel

Bezug
                                                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:16 Sa 25.10.2014
Autor: Teufel

Ja, das ist dann wahrscheinlich ein Fehler im Buch. Die angegebene Formel gilt so ohne weiteres nicht, aber vielleicht musst du nochmal durchlesen, ob die das irgendwo genauer erläutern. Ansonsten kannst du sie aber mal anschreiben!

[mm] \IZ_{pq}^\times [/mm] zusammen mit der Multiplikation ist immer eine Gruppe, das folgt auch ohne Chinesischen Restsatz. Ganz allgemein ist [mm] \IZ_n^\times [/mm] für alle $n>1$ mit der Multiplikation eine Gruppe (selbst für n=0 und n=1 gilt das). Das kannst du ganz straight forward mit den Gruppenaxiomen durchrechnen, also [mm] $1\in\IZ_n^\times$, $a,b\in\IZ_n^\times\Rightarrow ab\in\IZ_n^\times$ [/mm]  etc. Da braucht man ansonsten keinen Hokuspokus.

Wofür ich den chinesischen Restsatz brauche ist, um zu zeigen, dass RSA im Falle [mm] $p\not=q$ [/mm] auch für alle $m$ funktioniert, nicht nur für die, die in der Gruppe [mm] \IZ_n^\times [/mm] sind. Beispiel: $p=3, q=7$. Dann ist [mm] $m=9\notin \IZ_{21}^\times$ [/mm] und es muss deswegen NICHT nach Lagrange gelten [mm] $9^{\varphi(21)}=1\mod{21}$. [/mm] Gilt es auch nicht, da [mm] $9^{\varphi(21)}=15\mod{21}$. [/mm] Was man jedoch zeigen kann, ist, dass RSA trotzdem korrekt funktioniert, denn:
Es ist [mm] \varphi(21)=12, [/mm] wähle z.B. $e=d=5$. Dann ist [mm] $m^{ed}=9^{25}=9\mod{21}$, [/mm] wie man es haben will. Aber das hat nichts mit dem Lagrange zu tun, weil er für $m=9$ nicht anwendbar ist.

Bezug
                                                                                                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:43 Sa 25.10.2014
Autor: Marcel

Hallo Teufel,

> Ja, das ist dann wahrscheinlich ein Fehler im Buch. Die
> angegebene Formel gilt so ohne weiteres nicht, aber
> vielleicht musst du nochmal durchlesen, ob die das irgendwo
> genauer erläutern. Ansonsten kannst du sie aber mal
> anschreiben!

ich schreibe jetzt einfach mal den Teil aus dem Buch ab, denn so langsam
verliere ich den Überblick. Was ich nun weiß, ist, dass für invertierbare
Elemente [mm] $m_i \in (\IZ/n\IZ)^\times$ [/mm] mit Lagrange gefolgert werden kann, dass

    [mm] $((m_i)^e)^d \equiv m_i$ $\mod n\,.$ [/mm]

Okay, das liegt einfach daran, dass [mm] $(\IZ/(p*q)\IZ)^\times$ [/mm] eine Gruppe ist (das nachzurechnen
war nicht sehr schwer, aber allgemein steht es auch im Buch Algebra von
Meyberg/Karpfinger).
  

> [mm]\IZ_{pq}^\times[/mm] zusammen mit der Multiplikation ist immer
> eine Gruppe, das folgt auch ohne Chinesischen Restsatz.

Einverstanden.

> Ganz allgemein ist [mm]\IZ_n^\times[/mm] für alle [mm]n>1[/mm] mit der
> Multiplikation eine Gruppe (selbst für n=0 und n=1 gilt
> das). Das kannst du ganz straight forward mit den
> Gruppenaxiomen durchrechnen, also [mm]1\in\IZ_n^\times[/mm],
> [mm]a,b\in\IZ_n^\times\Rightarrow ab\in\IZ_n^\times[/mm]  etc. Da
> braucht man ansonsten keinen Hokuspokus.

Okay, ist jetzt verinnerlicht.

> Wofür ich den chinesischen Restsatz brauche ist, um zu
> zeigen, dass RSA im Falle [mm]p\not=q[/mm] auch für alle [mm]m[/mm]
> funktioniert, nicht nur für die, die in der Gruppe
> [mm]\IZ_n^\times[/mm] sind. Beispiel: [mm]p=3, q=7[/mm]. Dann ist [mm]m=9\notin \IZ_{21}^\times[/mm]
> und es muss deswegen NICHT nach Lagrange gelten
> [mm]9^{\varphi(21)}=1\mod{21}[/mm].

Okay - demzufolge machen sie es sich im Buch wohl zu einfach.

> Gilt es auch nicht, da
> [mm]9^{\varphi(21)}=15\mod{21}[/mm]. Was man jedoch zeigen kann,
> ist, dass RSA trotzdem korrekt funktioniert, denn:
>  Es ist [mm]\varphi(21)=12,[/mm] wähle z.B. [mm]e=d=5[/mm]. Dann ist
> [mm]m^{ed}=9^{25}=9\mod{21}[/mm], wie man es haben will. Aber das
> hat nichts mit dem Lagrange zu tun, weil er für [mm]m=9[/mm] nicht
> anwendbar ist.  

Okay. Also, ich schreibe jetzt mal alles modulo eigene Rechtschreibfehler
ab (Fett- und Kursivdruck erspare ich mir):

"
Satz 5.17 (Euler) Sei $n [mm] \in \IN$ [/mm] und $a [mm] \in \IZ$ [/mm] teilerfremd zu [mm] $n\,.$ [/mm] Dann ist

    [mm] $a^{\varphi(n)} \equiv [/mm] 1 [mm] \mod n\,.$ [/mm]

Beweis: Dies folgt aus dem Satz von Lagrange (siehe ...). ...

Beispiel Benannt nach Rivest/Shamir/Adleman ist RSA, ein Public-Key
Kryptosystem. Max und Sebastian wollen wieder Geheimnisse austauschen.
Max bestimmt zunächst eine Einwegfunktion:

1. Max bestimmt zwei große Primzahlen [mm] $p\,$ [/mm] und [mm] $q\,$ [/mm] und berechnet [mm] $n=p*q\,.$ [/mm]

2. Er berechnet leicht [mm] $\varphi(n)=(p-1)*(q-1)\,.$ [/mm]

3. Max wählt eine zufällige Zahl $e [mm] \in \IN$ [/mm] mit $1 < e < [mm] \varphi(n)$ [/mm] und [mm] $\ggT(e,\varphi(n))=1\,.$ [/mm]

4. Max berechnet jetzt eine Lösung der Gleichung

    $ed [mm] \equiv [/mm] 1 [mm] \mod \varphi(n)\,.$ [/mm]

5. Die Kodierungsfunktion ist nun

    $E [mm] \colon \IZ/n\IZ \to \IZ/n\IZ\,,$ [/mm] $x [mm] \longmapsto x^e\,.$ [/mm]

Man beachte den Unterschied zwischen [mm] $n\,$ [/mm] und [mm] $\varphi(n)\,.$ [/mm] Wie funktioniert
nun die Verschlüsselung? Der öffentliche Schlüssel ist das Paar [mm] $(n,e)\,,$ [/mm] das öffentlich
bekannt ist. Max ist aber der einzige, der [mm] $d\,$ [/mm] kennt, da er [mm] $\varphi(n)$ [/mm] kennt. Alle
anderen kennen die Faktorisierung von [mm] $n\,$ [/mm] nicht und damit [mm] $\varphi(n)$ [/mm] nicht und
also [mm] $d\,$ [/mm] nicht. Wenn Sebastian eine Nachricht an Max schicken will, so schreibt
er die Nachricht als eine Folge von Zahlen [mm] $m_1,...,m_l \in \IZ/n\IZ\,.$ [/mm] Die verschlüsselte
Nachricht ist [mm] $E(m_1),...,E(m_l)\,.$ [/mm] Max entschlüsselt die Nachricht, indem er die
[mm] $d\,$-te [/mm] Potenz berechnet:

    [mm] $(E(m_i))^d \equiv (m_i^e)^d \equiv m_i^{ed} \equiv m_i \mod n\,.$ [/mm]

(Und jetzt kommt halt der Teil, der mich da permanent zu verwirren scheint, denn,
sofern ich das nun richtig verstehe, stimmt diese Begründung so nur für
invertierbare [mm] $m_i \in \IZ/n\IZ$?!)
[/mm]

Dies folgt aus dem Satz von Euler, weil $ed [mm] \equiv [/mm] 1 [mm] \mod \varphi(n)$ [/mm] ist.

Zitat Ende"

Also, wenn ich das nun richtig sehe: Meine Beispiele für den Fall [mm] $p=q\,$ [/mm] gehen
vermutlich oft einfach deswegen gut, weil die Elemente meines "Alphabets"
(die Zahlen [mm] $1\,$ [/mm] bis [mm] $27\,$) [/mm] dann wahrscheinlich invertierbar bzgl. der Multiplikation sind.
Dass es im Falle [mm] $p=q\,$ [/mm] manchmal schiefgeht, liegt dann vielleicht daran, dass
ich manchmal halt keine invertierbaren Elemente erwische, oder die
Verschlüsselungspotenz so ist, dass ein [mm] $m_i$ [/mm] auf [mm] $E(m_i)=0$ [/mm] verschlüsselt wird.
Möglich ist das nur, weil man im Falle, dass [mm] $m_i$ [/mm] nicht invertierbar ist, das Argument,
dass der RSA trotzdem funktioniert, den chinesischen Restsatz benötigt. Und
dieses Argument scheint man im Falle [mm] $p=q\,$ [/mm] nicht benutzen zu können.

Aber was mich dann oben im Buch auf jeden Fall stört, ist, dass dort die
Funktionsfähigkeit nur mit Euler/Lagrange begründet wird... Diese Begründung
passt dann zwar "überwiegend" (wenn wir mal $p [mm] \not=q$ [/mm] annehmen), aber sie
ist eigentlich nicht vollständig. Oder sehe ich das immer noch falsch?

Gruß,
  Marcel



Bezug
                                                                                                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 23:20 Sa 25.10.2014
Autor: Teufel

Ja, also der Beweis ist so nicht vollständig und muss mehr begründet werden, z.B. über den chinesischen Restsatz. Und in dem Setting wurde auch [mm] $p\not= [/mm] q$ vorausgesetzt, was aber nirgendwo steht.

Du kannst den Autoren also mal schreiben, wenn du möchtest. :)

Bezug
                                                                                                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:06 Sa 25.10.2014
Autor: Marcel

Hallo nochmal,

sollte ich nerven, so sage man mir Bescheid. ;-)

Ich habe jetzt einfach mal ein wenig gegoogelt:

    []http://de.wikibooks.org/wiki/Beweisarchiv:_Kryptografie:_Kryptosysteme:_Korrektheit_des_RSA-Kryptosystems

Dort sehe ich, dass der Beweisteil, der die Korrektheit des RSA-Verfahrens
zeigt, im Falle, dass wir keine Einheiten haben, bei dem Chinesischen
Restsatz den Fall $p [mm] \not=q$ [/mm] benötigt.

Übrigens, ein weiteres gutes Dokument dahingehend:

    []http://math-www.upb.de/~acrowley/Tutorien/img/elemZahlentheorie.pdf

So langsam scheint es mir, dass dahingehend dann Licht ins Dunkel gekommen
ist. Ich denke, ich kann die Autoren des erwähnten Zahlentheorie-Buches
drauf hinweisen, dass ihre Argumentation zur Korrektheit des RSA-Verfahrens
nicht ganz vollständig ist. Was meint ihr?

Gruß,
  Marcel

Bezug
                                                                                                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 23:24 Sa 25.10.2014
Autor: Teufel

Erst einmal: du nervst nicht! ;)
Und jup, die Beweise sehen gut aus. Du kannst den Autoren das mal schreiben.

Bezug
                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 16:30 Fr 24.10.2014
Autor: Teufel

Hi!

RSA beruht unter anderem darauf, dass man Zahlen nicht effizient genug faktorisieren kann. Gegeben $N=pq$ kann man für "großes" N also nicht an $p$ und $q$ kommen.  Wenn du also eine Zahl der (noch nicht jetzt, aber hoffentlich bald gängigen) Größenordnung [mm] $2^{4096}=pq$, [/mm] dann kannst du lange warten, bis dein PC einen der beiden Faktoren findet. Für $p=q$ geht das jedoch sehr schnell, weil man einfach die Wurzel aus $N$ ziehen kann.

Ansonsten kannst du das RSA-Verfahren durchführen, wobei du dann auch nur Nachrichten verschlüsseln kannst, die in [mm] \IZ_p^\times [/mm] liegen. Generell sollte dafür gesorgt werden, dass Nachrichten $m$ immer in der Einheitengruppe von [mm] \IZ_N [/mm] liegen, weil man sonst durch [mm] \text{ggt}(m,N)\in\{p,q\} [/mm] auch an die Faktorisierung von $N$ kommt.

Bezug
                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:02 Fr 24.10.2014
Autor: Marcel

Hallo Teufel,

> Generell sollte dafür gesorgt werden,
> dass Nachrichten [mm]m[/mm] immer in der Einheitengruppe von [mm]\IZ_N[/mm]
> liegen, weil man sonst durch [mm]\text{ggt}(m,N)\in\{p,q\}[/mm] auch
> an die Faktorisierung von [mm]N[/mm] kommt.

ach, jetzt kapiere ich das: In den Einheiten gilt ja (charakteristisch dafür) [mm] $\ggT(N,m)=1\,.$ [/mm]

Stimmt, ist interessant, dass ansonsten [mm] $\ggT(m,N)=p$ [/mm] oder [mm] $=q\,$ [/mm] sein muss...
Wobei: Wieso gilt denn niemals [mm] $\ggT(m,N)=m$? [/mm]

Irgendwie bin ich jetzt doch verwirrt...

Gruß,
  Marcel

Bezug
                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 17:17 Fr 24.10.2014
Autor: Teufel

Nehmen wir mal wieder den Fall [mm] $p\not=q$ [/mm] an. Dann gilt [mm] \text{ggt}(m,N)=m [/mm] nur für $m=1$. Aber wenn $m$ keine Einheit ist, dann muss ja $p|m$ (exklusives) oder $q|m$ gelten, also $m$ wird genau von einem Faktor von $N$ geteilt. Denn weil [mm] $0\le [/mm] m < N$ kann $m$ nicht von $p$ und $q$ gleichzeitig geteilt werden.

Hilft dir das etwas? Oder habe ich deine Frage nicht verstanden?

Bezug
                                                
Bezug
Hohe Potenzen im RSA: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:54 Sa 25.10.2014
Autor: Marcel

Hallo Teufel,

> Nehmen wir mal wieder den Fall [mm]p\not=q[/mm] an.

gut, denn der Fall [mm] $p=q\,$ [/mm] sollte im RSA eh nicht verwendet werden.

> Dann gilt [mm]\text{ggt}(m,N)=m[/mm] nur für [mm]m=1[/mm].

Wieso? Was ist mit [mm] $m=p\,,$ $m=q\,$ [/mm] oder [mm] $m=N\,$? [/mm] Wenn Du das "nur" durch
ein "jedenfalls" ersetzt, dann bin ich einverstanden.

> Aber wenn [mm]m[/mm] keine Einheit
> ist, dann muss ja [mm]p|m[/mm] (exklusives) oder [mm]q|m[/mm] gelten, also [mm]m[/mm]
> wird genau von einem Faktor von [mm]N[/mm] geteilt.

Moment: Behandelst Du nun den Fall [mm] $\ggT(m,N) \not=1$? [/mm] Okay, ich glaube,
ich blicke gerade durch, um was es geht:
Der [mm] $\ggT(m,N)$ [/mm] ist ja mit Sicherheit ein Teiler von [mm] $N\,,$ [/mm] und dann geht es eigentlich

    mit dem hier

weiter. Ja, interessant, manchmal stellt man Fragen, auf die man selbst in
einem anderen Thread geantwortet hat ^^

> Denn weil [mm]0\le m < N[/mm]
> kann [mm]m[/mm] nicht von [mm]p[/mm] und [mm]q[/mm] gleichzeitig geteilt werden.
>  
> Hilft dir das etwas? Oder habe ich deine Frage nicht
> verstanden?

Mich haben Deine Formulierungen hier etwas verwirrt, aber ich denke, im
Wesentlichen willst Du nur auf das hinweisen, was in Sissiles Thread von
Sissile gefragt wurde:
Ein echter Teiler eines "Primzahlen-Produkts" [mm] $p*q\,$ [/mm] kann nur selbst eine der
beiden Primzahlen sein.

Korrekt?

Gruß,
  Marcel

Bezug
                                                        
Bezug
Hohe Potenzen im RSA: Antwort
Status: (Antwort) fertig Status 
Datum: 01:48 Sa 25.10.2014
Autor: Teufel

Hi!

Jo genau , das meinte ich. :)

Bezug
                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:56 Sa 25.10.2014
Autor: Marcel

Hi Teufel,

> Hi!
>  
> Jo genau , das meinte ich. :)

Danke. Dann ist das geklärt. Cool. :-)
( Ich überlege auch gerade, ob ich das in meinem Code als Kommentar
einfügen sollte. ^^
P.S. Das Ganze ist übrigens eine rein private Sache, aber ich will halt nicht
nur einfach etwas runterprogrammieren, sondern auch die Theorie dahinter
verstehen. ^^ )

Gruß,
  Marcel

Bezug
                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:05 Sa 25.10.2014
Autor: Teufel

Freut mich, dass du da so interessiert bist. :) Ja und es ist immer gut, wenn man wirklich weiß, was man da programmiert und warum das alles funktioniert, das machen viel zu wenig Leute. Naja, zumindest die Nicht-Mathematiker.

Bezug
                                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:13 Sa 25.10.2014
Autor: Marcel

Hi,

> Freut mich, dass du da so interessiert bist. :) Ja und es
> ist immer gut, wenn man wirklich weiß, was man da
> programmiert und warum das alles funktioniert, das machen
> viel zu wenig Leute. Naja, zumindest die
> Nicht-Mathematiker.

naja, ich bin halt quasi *blutiger Anfänger* in Zahlentheorie/Kryptographie,
und da ich das im Studium nicht lernen konnte, ich aber irgendwie immer
im Hinterkopf hatte, dass ich da mal mehr drüber wissen/verstehen will,
muss ich versuchen, es mir selbst beizubringen. Ich habe aber schnell
gemerkt, dass es hier, entgegen etwa anderen Gebieten, wie die Analysis,
eher so ist, dass man ab und an einfach mal das Zeugs runterprogrammieren
und sich anschauen sollte. Ansonsten verliert man irgendwann den Blick
für den Zusammenhang, den die Theorie eigentlich vermitteln soll - jedenfalls
ist es bei mir so ^^
Und da ich in Matlab/Octave relativ fit bin und diese Sprachen sehr User-
freundlich sind, mache ich das am Liebsten damit. Und hier sind mir halt
gewisse Kuriositäten aufgefallen (die ersten bekam ich durch *Analyse*
meines eigenen Codes bereinigt, aber dann kamen Dinge, die mir *unerklärlich*
erschienen sind).

Gruß,
  Marcel

Bezug
                                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:17 Sa 25.10.2014
Autor: Teufel

Ah ok :) na ja es ist nie zu spät damit anzufangen! Und speziell für RSA braucht man keine zu tief greifenden zahlentheoretischen Kenntnisse. Willst du aber Angriffe gegen RSA verstehen, so musst du etwas tiefer in die Materie einsteigen, aber die reine Durchführung ist erst einmal recht leicht.

Wir können den Thread ja hier noch etwas weiterführen :p

Bezug
                                                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:46 Sa 25.10.2014
Autor: Marcel

Hallo,

> Ah ok :) na ja es ist nie zu spät damit anzufangen! Und
> speziell für RSA braucht man keine zu tief greifenden
> zahlentheoretischen Kenntnisse.

ne, soweit ich das sehe Grundkenntnisse aus der Zahlentheorie und
dann noch *etwas* Algebra (eine Schande ist es fast, dass zu meiner
Studienzeit hier nie eine Algebra-Vorlesung angeboten wurde).

> Willst du aber Angriffe
> gegen RSA verstehen, so musst du etwas tiefer in die
> Materie einsteigen, aber die reine Durchführung ist erst
> einmal recht leicht.

Ja, ich glaube, wir haben nun auch rausgefunden (dahingehend war
Deine Vermutung, denke ich, richtig), wo hier der chinesische Restsatz
mit einhergeht. Und dann stimmt es natürlich, dass ich eine Satz der
Gruppentheorie nur dann auf [mm] $\IZ/(p*q)\IZ$ [/mm] anwenden kann, wenn das Ding
auch 'ne Gruppe ist. ;-)

> Wir können den Thread ja hier noch etwas weiterführen :p

Naja, ich lese gerade parallel dazu auch ein Kryptographie-Buch. Irgendwie
springe ich da auch zu viel hin und her, jedenfalls habe ich manchmal das
Gefühl, dass ich mich dadurch ein wenig mehr blockiere, als ich es müßte.
Aber das Verständnis des RSA-Verfahrens hilft mir mit Sicherheit jetzt auch
wieder, die Kryptographie mehr zu verstehen... :-)

Diffie-Hellmann wollte ich mir demnächst auch "demonstrieren", wobei ich
dabei natürlich quasi den lieben Gott spiele, weil ich ja quasi beide Personen
simuliere. ;-)

Mal schauen, was mir da wieder für *Spezialitäten* ins Auge fallen ^^

Gruß,
  Marcel

Bezug
                                                                                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:22 Sa 25.10.2014
Autor: Teufel

Du musst auch immer spezifizieren, mit welcher Verknüpfung es eine Gruppe sein soll. [mm] $\IZ_p^2$ [/mm] ist zusammen mit + auch imemr eine Gruppe, egal ob $p=q$ oder nicht. Für [mm] \cdot [/mm] muss man in beiden Fällen Elemente rausschmeißen, die man nicht invertieren kann.

Diffie-Hellman ist etwas einfacher, weil man ja nur mit Potenzgesetzen arbeiten muss. ;)

Bezug
                                                                                                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:58 Sa 25.10.2014
Autor: Marcel

Hi Teufel,

> Du musst auch immer spezifizieren, mit welcher Verknüpfung
> es eine Gruppe sein soll.

kein Thema. Ich meine hier, da "Potenzen" dabei stehen, eigentlich immer
"multiplikative Gruppe". Aber natürlich ist das Quatsch, wenn ich sage, dass
[mm] $\IZ/n\IZ$ [/mm] dann eine Gruppe sei... Das war auch weniger durch Selbstnachdenken,
als vielmehr ein *Denkfolgefehler*, weil im Buch steht, dass man die [mm] $m_i \in \IZ/n\IZ$ [/mm]
hernehmen kann und dann Lagrange drauf anwenden kann. Das klang
für mich dann so plausibel, dass ich gar nicht mehr drüber nachgedacht habe ^^

>  [mm]\IZ_p^2[/mm] ist zusammen mit + auch
> imemr eine Gruppe, egal ob [mm]p=q[/mm] oder nicht. Für [mm]\cdot[/mm] muss
> man in beiden Fällen Elemente rausschmeißen, die man
> nicht invertieren kann.

Ja, okay. Aber irgendwie steht dann meiner Meinung nach etwas falsches
in dem Buch... ^^
  

> Diffie-Hellman ist etwas einfacher, weil man ja nur mit
> Potenzgesetzen arbeiten muss. ;)

Wird aber noch ein wenig dauern, bis ich mich damit beschäftige, denn das
RSA will ich erst verstanden wissen. ;-)

Gruß,
  Marcel

Bezug
                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:28 Fr 24.10.2014
Autor: reverend

Hallo Marcel,

außer dieser brute-force-Methode ist []"square and multiply" meist vielversprechender, vor allem natürlich bei größeren Exponenten.

Grüße
rev

Bezug
                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:52 Fr 24.10.2014
Autor: Marcel

Hallo reverend,

> Hallo Marcel,
>  
> außer dieser brute-force-Methode ist
> []"square and multiply"
> meist vielversprechender, vor allem natürlich bei
> größeren Exponenten.

Danke für den Hinweis. Diese Methode habe ich erst vor kurzem (3 oder 6
Monaten) gelernt - bzw. eine damit verwandte Methode. Die hieß schnelle
Exponentiation, war aber entweder genau das gleiche oder jedenfalls
dieser binären Exponentiation sehr ähnlich.

Gruß,
  Marcel

Bezug
                                
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:06 Sa 25.10.2014
Autor: reverend

Hallo Marcel,

ich lege mal eine Excel-Tabelle bei, mit der sich solche großen Potenzen schnell und übersichtlich berechnen lassen.
Wahrscheinlich hat sich damit Deine PN auch erledigt, oder?

[a]Berechnung a^k mod(n)

Grüße
reverend

Dateianhänge:
Anhang Nr. 1 (Typ: xls) [nicht öffentlich]
Bezug
                                        
Bezug
Hohe Potenzen im RSA: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:46 Sa 25.10.2014
Autor: Marcel

Hi reverend,

> Hallo Marcel,
>  
> ich lege mal eine Excel-Tabelle bei, mit der sich solche
> großen Potenzen schnell und übersichtlich berechnen
> lassen.
> Wahrscheinlich hat sich damit Deine PN auch erledigt,
> oder?
>  
> [a]Berechnung a^k mod(n)

ich muss mir das mal in Ruhe angucken. Vermutlich wird sich das damit
klären lassen, aber falls doch nicht, dann melde ich mich nochmal. Danke
Dir jedenfalls. :-)

Gruß,
  Marcel

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]