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
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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

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
StartseiteMatheForenSonstigesRSA Entschlüsselungsexponent
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Sonstiges" - RSA Entschlüsselungsexponent
RSA Entschlüsselungsexponent < Sonstiges < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

RSA Entschlüsselungsexponent: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:24 So 14.12.2008
Autor: sandy_cheeks

Ich verstehe nicht ganz, wie man auf den Entschlüsselungsexponenten d beim RSA-System kommt. N ist das Produkt zweier Primzahlen,  für den Verschlüsselungsexponenten e muss gelten: 1<e<phi(N), soweit nachvollziehbar. Jetzt soll gelten: e*d  [mm] \equiv [/mm] 1 (mod phi(N)). Das bedeutet ja, dass der Rest der Division von e*d durch phi(N) gleich dem Rest der Division von 1 durch phi(N) sein muss (wenn ich es soweit richtig verstanden habe). Dann, habe ich mir überlegt, muss 1 mod phi(N) ja 1 sein, weil phi(N) auf jeden Fall größer als 1 ist. Also müsste gelten:
e*d = k*phi(N) + 1

wobei k der größtmögliche natürliche Faktor ist. Wenn ich die Formel dann umstelle gilt:
e*d - k*phi(N) =1

Bei Wikipedia steht da aber ein +, also
e*d + k*phi(N) =1

Sieht jemand meinen Denkfehler?

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
RSA Entschlüsselungsexponent: Antwort
Status: (Antwort) fertig Status 
Datum: 14:46 Mo 15.12.2008
Autor: rainerS

Hallo!

> Ich verstehe nicht ganz, wie man auf den
> Entschlüsselungsexponenten d beim RSA-System kommt. N ist
> das Produkt zweier Primzahlen,  für den
> Verschlüsselungsexponenten e muss gelten: 1<e<phi(N),
> soweit nachvollziehbar. Jetzt soll gelten: e*d  [mm]\equiv[/mm] 1
> (mod phi(N)). Das bedeutet ja, dass der Rest der Division
> von e*d durch phi(N) gleich dem Rest der Division von 1
> durch phi(N) sein muss (wenn ich es soweit richtig
> verstanden habe). Dann, habe ich mir überlegt, muss 1 mod
> phi(N) ja 1 sein, weil phi(N) auf jeden Fall größer als 1
> ist. Also müsste gelten:
> e*d = k*phi(N) + 1
> wobei k der größtmögliche natürliche Faktor ist. Wenn ich
> die Formel dann umstelle gilt:
> e*d - k*phi(N) =1
> Bei Wikipedia steht da aber ein +, also
> e*d + k*phi(N) =1
>  Sieht jemand meinen Denkfehler?

Ja ;-)

Du hast übersehen, dass die Kongruenz

[mm] e*d \equiv 1 \pmod{\phi(N)} [/mm]

bedeutet, dass k eine beliebige ganze Zahl sein darf. Weder ist es auf die natürlichen Zahlen beschränkt noch muss es die größtmögliche solche Zahl sein.

Der Unterschied zwischen deiner Gleichung und der in der Wikipedia ist nur, ob du k als positive oder negative Zahl wählst.

Viele Grüße
   Rainer


Bezug
                
Bezug
RSA Entschlüsselungsexponent: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:30 Mo 15.12.2008
Autor: sandy_cheeks

Prima, danke! Habe gar nicht darüber nachgedacht, dass k auch negativ sein kann :D, logisch

Bezug
                
Bezug
RSA Entschlüsselungsexponent: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:33 Sa 20.12.2008
Autor: sandy_cheeks

Hmm...Tut mir Leid, aber jetzt wo ich ein eigenes Beispiel ausrechnen wollte, glaube ich, dass ich es doch noch nicht so richtig verstanden habe.
13 [mm] \cdot [/mm] d [mm] \equiv [/mm] 1 (mod 60)
Dann müsste ja gelten:
13 [mm] \cdot [/mm] d + k [mm] \cdot [/mm] 60 = 1
Mit Hilfe des erweiterten euklidischen Algorithmus habe ich herausbekommen, dass d=-23 und k=5, was ja in die letzte Gleichung passen würde. Aber 13 [mm] \cdot [/mm] (-23) [mm] \equiv [/mm] 1(mod 60) passt ja nicht...Ich weiß, dass für d eigentlich 37 rauskommen sollte, aber wie kommt man darauf?

Bezug
                        
Bezug
RSA Entschlüsselungsexponent: Antwort
Status: (Antwort) fertig Status 
Datum: 19:07 Sa 20.12.2008
Autor: Gonozal_IX

Hiho,

die Lösung stimmt doch, da [mm]13*(-23) = 1\text{ (mod 60)}[/mm]

Denn:

[mm]-300 = 0\text{ (mod 60)} \gdw -299 - 1 = 0\text{ (mod 60)} \gdw -299 = 1 \text{ (mod 60)} \gdw 13*(-23) = 1\text{ (mod 60)}[/mm]

Oder Kürzer: bzgl mod 60 gilt -23 = 37, da -23 + 60 = 37 ist.

MfG,
Gono.

Bezug
                                
Bezug
RSA Entschlüsselungsexponent: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:21 Sa 20.12.2008
Autor: sandy_cheeks

Prima, vielen Dank für die Antwort. Ich dachte: -299 = -4 [mm] \cdot [/mm] 60 R-59, was ja schwachsinnig ist, anstatt -299 = -5 [mm] \cdot [/mm] 60 R1.

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


Alle Foren
Status vor 51m 1. mathelernender
ZahlTheo/rat. Zahl = Summe von Brüchen
Status vor 7d 5. Pacapear
UAnaR1Funk/Grenzwert berechnen
Status vor 11d 6. matux MR Agent
UAnaR1/Reaktion - erwünscht
Status vor 11d 2. matux MR Agent
GraphTheo/Zusammenhängender Zufallsgraph
Status vor 11d 2. matux MR Agent
ULinAMat/Householder-Transformation
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]