WinFuture-Forum.de: Frage Zum Rsa-algorithmus - WinFuture-Forum.de

Zum Inhalt wechseln

Beiträge in diesem Forum erhöhen euren Beitragszähler nicht.
Seite 1 von 1

Frage Zum Rsa-algorithmus Bzgl. Schlüsselerzeugung


#1 Mitglied ist offline   Graumagier 

  • Gruppe: aktive Mitglieder
  • Beiträge: 8.811
  • Beigetreten: 01. März 04
  • Reputation: 1
  • Geschlecht:Männlich
  • Wohnort:Graz, Österreich

geschrieben 01. Dezember 2005 - 20:16

Hi,

ich wollte mal fragen wie beim abschließenden Schritt der Schlüsselerstellung ein entsprechendes Näherungsverfahren für die die letzte Zahl aussehen würde bzw. welcher Rechenvorgang hierfür verwendet wird.

In anderen Worten:

c * d = 1 mod Phi(N)


wobei c und Phi(N) gegeben sind und d berechnet werden soll.

Danke schon mal für alle Hinweise :)

Dieser Beitrag wurde von Graumagier bearbeitet: 01. Dezember 2005 - 20:16

"If you make something idiot proof, someone will invent a better idiot." - Marvin

For Emails always use OpenPGP. My KeyID: 0xA1E011A4

Anzeige



#2 Mitglied ist offline   Rika 

  • Gruppe: aktive Mitglieder
  • Beiträge: 11.533
  • Beigetreten: 11. Juni 03
  • Reputation: 2
  • Geschlecht:Männlich

geschrieben 01. Dezember 2005 - 20:38

Man nicht i.A. nicht Phi(n), sondern Lamdba(n) mit l(n)=kgv(p-1,q-1), was mindestens um den faktor 2 kleiner ist als phi(n). Aber das ist Nebensache.

c * d = 1 mod phi(n) bzw. d = 1 / c mod phi(n) ist nix weiter als die Bestimmung des Inversen von c im Ring Z_phi(n). Dazu nimmt man typischerweise den erweiterten euklidischen Algorithmus.

Man sucht nach ggT(c,phi(n)) und erhält eine Kette von Gleichungen, die mit der Zahl 1 endet. Jetzt dreht man die Gleichungen um und setzt sie nacheinander ein.

ggt(11,35) ->
35=3*11+2
11=5*2+1
2=2*1

2=35-3*11
1=11-5*2=11-5*(35-3*11)=-5*35+16*11
1=-5*35+16*11 mod 35
1=16*11 mod 35 bzw. 11 = 1 /16 mod 25 -> d=16

Übersichtlicher ist natürlich eine Matrixschreibweise in der Form

	 35 11
35 = 1   0 
11 = 0   1  | I-3*II
 2 = 1  -3  | II - 5*III
 1 = -5  16


Und noch einfacher wird's, wenn man 35 in die beiden Primfaktoren 5 und 7 zerlegt lässt, die Inversen modulo diesen beiden bestimmt und wie Chinesem Restsatz zusammensetzt
11=1 mod 5 und damit 1*1=1 mod 5, also ist 1/1=1
11=4 mod 7 und damit 4*2=1 mod 7, also ist 1/4=2

Nun ist ggt(5,7)=1 (bei RSA kann man p und q so wählen, daß (p-1)/2 und (q-1)/2 ebenfalls Primzahlen sind! Ist aber egal, der Chinesische Restsatz funktioniert immr) und damit folgt aus
d=1 mod 5, d=2 mod 7 unmittelbar d=11 mod 35

Dieser Beitrag wurde von Rika bearbeitet: 01. Dezember 2005 - 20:52

Konnichiwa. Manga wo shitte masu ka? Iie? Gomenne, sonoyouna koto ga tabitabi arimasu. Mangaka ojousan nihongo doujinshi desu wa 'Clamp X', 'Ayashi no Ceres', 'Card Captor Sakura', 'Tsubasa', 'Chobits', 'Sakura Taisen', 'Inuyasha' wo 'Ah! Megamisama'. Hai, mangaka gozaimashita desu ni yuujin yori.
Eingefügtes Bild
Ja, mata ne!

(For sending email please use OpenPGP encryption and signing. KeyID: 0xA0E28D18)

#3 Mitglied ist offline   Graumagier 

  • Gruppe: aktive Mitglieder
  • Beiträge: 8.811
  • Beigetreten: 01. März 04
  • Reputation: 1
  • Geschlecht:Männlich
  • Wohnort:Graz, Österreich

geschrieben 01. Dezember 2005 - 22:43

Danke Rika,

nur leider steige ich bei dem vierten Absatz aus ;)

Das Einsetzen in den euklidischen Algorithmus ist ja kein Problem, auch das Umstellen bei m = s * a + t * b, aber wenn der Modulo wieder in Spiel kommt kenne ich mich nicht mehr aus. Wäre nett wenn du mir den Teil noch genauer erklären könntest.

Dieser Beitrag wurde von Graumagier bearbeitet: 01. Dezember 2005 - 23:24

"If you make something idiot proof, someone will invent a better idiot." - Marvin

For Emails always use OpenPGP. My KeyID: 0xA1E011A4

#4 Mitglied ist offline   Rika 

  • Gruppe: aktive Mitglieder
  • Beiträge: 11.533
  • Beigetreten: 11. Juni 03
  • Reputation: 2
  • Geschlecht:Männlich

geschrieben 02. Dezember 2005 - 00:26

Am Ende steht doch dann eine Gleichung der Form 1 = c * d + x * n, wobei n genau der Modulus ist. Nimmst du das ganze jetzt also modulo n, bleibt links die 1, rechts das c*d und x*n mod n ist natürlich 0 und fällt deshalb weg.

Ist doch auch umgekehrt logisch: Wenn c * d = 1 mod n ist, dann ist c*d-1=0 mod n und es gibt ein ganzzahliges x, für das c*d-1=x*n gilt.
Konnichiwa. Manga wo shitte masu ka? Iie? Gomenne, sonoyouna koto ga tabitabi arimasu. Mangaka ojousan nihongo doujinshi desu wa 'Clamp X', 'Ayashi no Ceres', 'Card Captor Sakura', 'Tsubasa', 'Chobits', 'Sakura Taisen', 'Inuyasha' wo 'Ah! Megamisama'. Hai, mangaka gozaimashita desu ni yuujin yori.
Eingefügtes Bild
Ja, mata ne!

(For sending email please use OpenPGP encryption and signing. KeyID: 0xA0E28D18)

#5 Mitglied ist offline   Graumagier 

  • Gruppe: aktive Mitglieder
  • Beiträge: 8.811
  • Beigetreten: 01. März 04
  • Reputation: 1
  • Geschlecht:Männlich
  • Wohnort:Graz, Österreich

geschrieben 02. Dezember 2005 - 06:52

Alles klar, danke nochmal ;)

BTW., kann jemand ein gutes Buch zum Thema Verschlüsselungen (Allgemein) empfehlen? Gibt es was Vergleichbares zu "Angewandte Kryptographie" bzw. "Applied Cryptography"?

Dieser Beitrag wurde von Graumagier bearbeitet: 02. Dezember 2005 - 07:05

"If you make something idiot proof, someone will invent a better idiot." - Marvin

For Emails always use OpenPGP. My KeyID: 0xA1E011A4

#6 Mitglied ist offline   Rika 

  • Gruppe: aktive Mitglieder
  • Beiträge: 11.533
  • Beigetreten: 11. Juni 03
  • Reputation: 2
  • Geschlecht:Männlich

geschrieben 02. Dezember 2005 - 12:47

Reinhard Wobst: Abenteuer Kryptologie, Addison-Wesley Verlag. Ist kostenfrei als PDF-eBook erhältlich.
Konnichiwa. Manga wo shitte masu ka? Iie? Gomenne, sonoyouna koto ga tabitabi arimasu. Mangaka ojousan nihongo doujinshi desu wa 'Clamp X', 'Ayashi no Ceres', 'Card Captor Sakura', 'Tsubasa', 'Chobits', 'Sakura Taisen', 'Inuyasha' wo 'Ah! Megamisama'. Hai, mangaka gozaimashita desu ni yuujin yori.
Eingefügtes Bild
Ja, mata ne!

(For sending email please use OpenPGP encryption and signing. KeyID: 0xA0E28D18)

#7 Mitglied ist offline   Graumagier 

  • Gruppe: aktive Mitglieder
  • Beiträge: 8.811
  • Beigetreten: 01. März 04
  • Reputation: 1
  • Geschlecht:Männlich
  • Wohnort:Graz, Österreich

geschrieben 03. Dezember 2005 - 01:01

Hast du die PDF zufällig noch gespeichert? Ich finde keine Quellen, die noch up wären.
"If you make something idiot proof, someone will invent a better idiot." - Marvin

For Emails always use OpenPGP. My KeyID: 0xA1E011A4

Thema verteilen:


Seite 1 von 1

1 Besucher lesen dieses Thema
Mitglieder: 0, Gäste: 1, unsichtbare Mitglieder: 0