spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Tach,

habe da folgendes Problem:

ich versuche grad, n eigenes verschlüsselungssystem zu entwickeln. da allerdings gerade über das internet das problem des schlüsseltauschs besteht, hab ich mich entschlossen, den schlüsseltausch per RSA vorzunehmen. ich hab mir also RSA angeguckt und habe nun folgendes problem: der private schlüssel d ist das multiplikativ inverse zu e und der eulerschen φ-Funktion zu p und q. φ(p,q) und e sind teilerfremd und e muss kleiner als φ(p, q) sein, laut wikipedia gibt es für die wahl von e jedoch keine weiteren vorgaben. also macht man sich mit dem erweiterten euklidischen algorithmus daran, das multiplikativ inverse zu finden. damit wird folgende gleichung entwickelt: 1 = e * d + k * φ(p, q). d ist dann der private schlüssel. allerdings komme ich bei meinen testweisen versuchen, mit beliebigen zahlen d zu berechnen allerdings fast immer auf eine negative zahl, was eigentlich nicht passieren darf und womit der RSA algo nicht umgehn kann und auch nich soll. vlt mach ich einfach einen rechenfehler, aber ich glaube egt nicht. ich zeig euch mal ne beispiel rechnung:

Als nächstes muss der größte gemeinsame teiler berechnet werden:

Jetzt setze ich die gleichungen wieder rekursiv ineinander ein und erhalte am ende die gleichung

nach dem nächsten schritt sollte ich also egt d und k haben, nachdem ich mit dem einsetzen fertig bin

da e = 37 ergibt sich daraus folgende gleichung:

das stimmt zwar auch, allerdings kann man d (also -107) nicht sinnvoll in die RSA funktion einsetzen. jedenfalls kommt dann beim entschlüsseln ziemlicher müll raus

bsp:

C ist der verschlüsselte wert und K ist der klartext-wert. der zu verschlüsselnde wert ist hier testweise einfach mal 5:

Ich muss wohl nicht anmerken, dass -48 und 5 iwie leicht unterschiedliche zahlen sind.

Wenn mir jemand helfen könnte, wäre das echt... hilfreich

danke schonma im voraus

@Schorsch: wie mastermind richtig erkannt hat, werd ich mit RSA nur den schlüssel für das 2. system verschlüsseln. auch wenn ich für sichere RSA-keys ziemlich große primzahlen brauche (das letzte mal, als ich nach dem standard geguckt hab, warns an die 40 stellen, und die quelle is schon recht veraltet) und ich hierfür prinzipiell sowieso ne klasse bräuchte, die mit solchen zahlen rechnen kann (64bit sind für sowas einfach nich das wahre ), wird allein die RSA-Verschlüsselung des keys ziemlich zeitfressend. sonst würd ich vermutlich gleich ganze nachrichten mit rsa verschlüsseln aber das is für nen end-userpc nichtmal ansatzweise tragbar und was restklassenringe angeht, prog ich erstma das erweiterte euklidische verfahren aus, das is prinzipiell ziemlich einfach und wenn mir das passende werte liefert, reicht mir das fürs erste (falls restklassenringe performanter sind, werd ich mir die nach der erstimplementierung ansehn...)

@mastermind: im prinzip hast du recht, allerdings hab ich mir vor ca nem halben jahr in der schule vorm unterricht ein an die enigma angelehntes (natürlich an computer angepasstes) system ausgedacht, das wie one-time-pads und auch die enigma selbst beim bruteforcen jede erdenkliche zeichenfolge erzeugt und 1,63*10^180 verschiedene schlüssel ermöglicht. das hab ich dann den restlichen schultag über im unterricht nochmal überarbeitet und n 14-seitiges beschreibendes skript geschrieben. wäre doch iwie verschwendete zeit gewesen, wenn ich dann letzten endes AES oä nachbastel xD und das ich mathematisch nich so das ass bin, heißt nich dass ich keine ahnung von kryptographie hätte xD bin zwar nich der beste, aber reicht aber aus um mir relativ sicher zu sein, dass meine chiffre klappen kann

@drakon: ich werds mir auf jeden fall ma durchlesen.

und @ sacaldur: da primfaktorzerlegung so ohne weiteres nich möglich is und modulofunktionen ausser durch bruteforce genau wie n = p * q nicht umkehrbar sind, sollte der schlüssel so ohne weiteres selbst dann nicht umkehrbar sein, wenn man ihn mehrfach verwendet. dh (auch wieder ne relativ alte information, vlt kann man RSA jetzt auch in soeinem fall knacken) im normalfall besitzt jede person ein eigenes schlüsselpaar. N und e sind dann öffentlich und damit wie das wort schon sacht für jeden zugänglich. p, q, φ(N) und d bleiben geheim, was es praktisch unmöglich macht, auf mathematischem wege zurückzurechnen, auch wenn dieses schlüsselpaar mehrfach verwendet wird. und was

angeht: naja wenn man davon ausgeht, dass

korrekt gelöst wurde, ist deine bedingung immer gegeben, da in dem fall entweder e*d oder k*φ(N) exakt um 1 größer ist als die jeweilige andere zahl und somit bei ner modulodivision immer 1 liefert


darf ich dann also annehmen, dass ich mathematisch gesehen prinzipiell nichts falsch gemacht habe beim einsetzen der gleichungen? denn in dem fall muss ich wohl doch auf restklassenringe umsteigen (hab mir die bis jetzt noch nich angeguckt, da auf wikipedia (zumindest auf deutsch) steht, d würde per erweitertem euklidischem verfahren berechnet)

dann dank ich nochmal für die hinweise/anregungen/den link

1. korrekt. hab noch nich die zeit gehabt, mir anzugucken, was das überhaupt is
2. lies den satz zuende, bevor du dran rumkritisierst. wie schon geschrieben kommt jede mit dem verwendeten zeichensatz mögliche zeichenkombination bei raus. also hat man bei 100 zeichen n^100 (n is die anzahl der möglichen zeichen) verschiedene texte. davon ergeben dann vermutlich mehrere tausend texte auch noch sinn. hierbei gehe ich davon aus, wenn man davon ausgeht, dass das verwendete otp nur (im einfachsten fall) 26 zahlen verwendet. werden beliebig große zahlen verwendet, is bruteforcen natürlich nich möglich, allerdings sind wir uns hoffentlich einig, dass selbst wenn man texte, deren schlüsselzeichen nur aufm alphabet basieren, zwar gebruteforced werden können, dass die bruteforce-attacke allerdings aufgrund oben genannter tausenden von möglichen sinnvollen texten niemals ein ergebnis liefern kann.
3. 896...
und 4.: mag sein. das lass aber mal meine sorge sein, da ich wohl niemanden mit fragen zu meinem eigenen system nerven kann xD zumindest nich mit verständnisfragen und da ich imo schon relativ gut durchgeplant habe, wie ichs proggen werde, wird auch das nich euer prob sein

edit:

und was das bruteforcen angeht: in ihrer letzten form war bruteforcen auch bei der enigma bei durchschnittlich langen texten nich drin. das entschlüsseln im 2. weltkrieg durch die briten hat nur funkrioniert, weil die deutschen sie nicht richtig angewendet haben bzw. nich die technischen möglichkeiten hatten, ihre schlüssel sicher zu verteilen

und nochn edit:

so hab mir jetz ma restklassenringe angesehn. wenn ich das in meiner 3-minütigen einarbeitungszeit richtig verstanden habe, könnten die tatsächlich ne um längen sinnvollere und wirklich gut funktionierende lösungen sein. oder eher: sie SIND eine um längen sinnvollere lösung xD