Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

euklidische algoritmus
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> euklidische algoritmus
 
Autor Nachricht
kamischiki
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.12.2004
Beiträge: 129
Wohnort: Kiev/Frankfurt

BeitragVerfasst am: 24 Mai 2005 - 11:27:08    Titel: euklidische algoritmus

Hallo Leute!
Ich brauche dringend euere hilfe!
und zwar sollte ich nach RSA-schema eine nachricht kodieren, und dafuer muss man folgendes ausrechnen:

k(a) kongruent 1013^385 mod 8137
k(a)-?

hat jemand vielleicht eine idee, wie man es macht?
danke im voraus!
KTU
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 17.01.2005
Beiträge: 188
Wohnort: Cologne

BeitragVerfasst am: 24 Mai 2005 - 12:37:55    Titel:

Hi,

gib mir mal bitte p und q für n=p*q,
sowie das e, was du in e*d kongruent 1 (mod phi(n))
benutzt hast. komme irgendwie mit diesem k(x) begrifflich nicht klar Sad
kamischiki
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.12.2004
Beiträge: 129
Wohnort: Kiev/Frankfurt

BeitragVerfasst am: 24 Mai 2005 - 13:41:26    Titel:

also:
m=8137=79*103
s=385
zu kodieren ist a=1013
und man muss auch den schluessel t berechnen.
mein t=1591/77 (ic hoffe, es ist richtig, aber wenn es dir nichts ausmacht, oder wenn du lust dazu hast, koenntest du vielleicht noch mal nachschauen? Rolling Eyes

Danke uebrigens, dass du dich damit beschaeftigst Very Happy
KTU
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 17.01.2005
Beiträge: 188
Wohnort: Cologne

BeitragVerfasst am: 24 Mai 2005 - 14:49:27    Titel:

So: Ich habe mich mal an die allgemeinen Buchstaben gehalten, siehe auch:

http://de.wikipedia.org/wiki/RSA-Kryptosystem

n = 79*103 = 8137

Phi(n) = (p-1)*(q-1)= 78*102 = 7956

als teilerfremde Zahl dazu habt ihr e = 385 gewählt. Wenn du das nachher programmieren sollst, nimm einfach die nächste Primzahl größer als Phi(n).
Wenn zwei Zahlen teilerfremd sind, ist der ggT 1, das sollte man in diesem Fall mit dem euklidischen Algorithmus machen, da wir die Linearkombination
1= d*385+k*7956 suchen.

euklidischer Algorithmus:

1) 7956 = 20 * 385 + 256
2) 385 = 1* 256 + 129
3) 256 = 1*129 + 127
4) 129 = 1*127 + 2
5) 127=63*2+1

Jetzt kommt das ätzende an der Sache: Man muss damit ausdrücken, welche Vielfachen von 385 und 7956 eins ergeben. Dazu muss man das von unten nach oben wieder zurückrechnen:

aus der letzten Zeile folgt:

1=127-63*2

aus 4) wissen wir, dass 2=129-127 ist

1 = 127-63*(129-127) = 127 - 63*129 + 63*127 = 64*127-63*129

aus 3) do we know dass 127 = 256 - 129 ist

1= 64 * (256-129) - 63 * 129 = 64*256 - 127 * 129

aus 2) folgern wir fröhlich 129 = 385-256

1= 64*256 - 127*(385-256) = 191*256 - 127 *385

und zu guter letzt aus 1) 256 = 7956 - 20*85

1 = 191*(7956-20*385) - 127*385 = 191* 7956 - 3947 * 385

Nun sind wir schon fertig: die 191 sind mathematischer Sondermüll, aber die -3947 heissen von jetzt an d.

public key sind also: e = 385 und n = 8137
für dich behälst du: d =-3947

alles andere sollte sorfältigst gelöscht werden!

m = 1013

c = 1013^(385) mod 8137
c = 168

Und wenn du mit deinem geheimen Schlüssel das wieder lesen willst:

m = 168^(-3947) mod 8137 = 1013

Wenn du wissen willst wie man per Hand mit Kongruenzen rechnet:

http://de.wikipedia.org/wiki/Kongruenz_%28Zahlentheorie%29

Etwas über die Sicherheit von RSA, bzw. das Problem der Faktorisierung großer Zahlen:

http://mathworld.wolfram.com/news/2005-05-10/rsa-200/

und zu guter letzt empfehle ich: Known-Plaintext-Angriffe, falls ihr in Informatik die Codes eurer Mitschüler knacken sollt. Das Problem ist nämlich, dass bei diesem reinen RSA jedem Klartext genau ein chiffrierter zugeordnet wurde.

Siehe dazu auch:

http://de.wikipedia.org/wiki/Kryptoanalyse
black Man
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 28.01.2007
Beiträge: 14

BeitragVerfasst am: 24 Feb 2007 - 02:26:31    Titel: der euklidische algorithmus

hey ihr Nachteulen kann mir vllt jemand bei meiner rückrechnung helfen ich komme dabei voll durch einander? von dieser hinrechnung
1= d*7+k*160 suchen. Jetzt versuche ich den ggT für die Zahlen p=17 und q=11 zu

berechnen.

160=22*7+4
7=1*4+3
4=1*3+1
jetzt weiss ich nicht wie ich weiter machen solle.
bitte um hilfe ist sehr wichtig bitte.
kamischiki
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.12.2004
Beiträge: 129
Wohnort: Kiev/Frankfurt

BeitragVerfasst am: 24 Feb 2007 - 14:55:29    Titel:

wie du schon geschrieben hast
160=22*7+4 (1)
7=1*4+3 (2)
4=1*3+1 (3)

jetzt formen wir (3) um:
1=4-3 (4)
aus (2) kommt 3=7-4; das setzen wir jetzt ins(4) und beckommen
1=4-(7-4)=2*4-7 (5)
aus (1) 4=160-22*7
das setzen wirnun ins (5) rein
1=2*(160-22*7)-7
1=2*160-45*7
fertig!
d=-45
k=2
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> euklidische algoritmus
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum