Diskussion:Rabin-Kryptosystem

verwirrtes Geschreibsel

ich habe hier eine überschrift eingefügt. was hier folgt erscheint mir unwichtig: --Moritzgedig 05:17, 17. Jan. 2009 (CET)

Der Artikel ist doch in seiner jetzigen Form schlicht lächerlich. Die pseudomathematischen Ausführungen über Kryptographie sind doch letztlich nur inhaltsleeres Gerede. Ich habe versucht den Artikel etwas verständlicher zu fassen und auf die Fakten zu beschränken. Leider werden meine Änderungen ständig zurückgenommen. Es werden merkwürdige Andeutungen gemacht, die aber offenbar nicht durch Fakten zu belegen sind.

Die Einführung ist vollkommen unpräzise.

Das Rabin-Kryptosystem ist innerhalb der Kryptologie ein asymmetrisches Kryptosystem, das auf dem Faktorisierungsproblem beruht und mit RSA verwandt ist. Es lässt sich prinzipiell auch zur Signatur verwenden. In der Praxis findet das Verfahren allerdings wegen bestimmter Angriffsmöglichkeiten kaum Anwendung.

Scheinbar gibt es da ein Problem und darauf beruht das System ???

Was heißt, prinzipiell auch zur Signatur und was für ein Faktorisierungsproblem eigentlich ?

Grundsätzlich kann ein asymmetrisches Verschlüsselungsverfahren (der unklare Begriff "asymmetrisches Kryptosystem" meint wohl Verschlüsselung) immer zur Signatur geeigent. Die Signatur ist dabei schlicht die Verschlüsselung der Nachricht oder eines Hashwerts der Nachricht mit dem privaten Schlüssel. Warum sollte das Rabinverfahren hierfür nicht geeigent sein ?

Was sind bestimmte Angriffsmöglichkeiten ?

Entweder sollte dies präzesiert werden oder auf derart seltsame Andeutungen verzichtet werden. Ich glaube nicht, dass tatsächlich ein entscheidender Nachteil des Rabin-Verfahrens im Vergleich zu RSA besteht. Diese gilt zumindest, falls man die Nachricht mit einer sinnvollen Paddingvorschrift eindeutig macht. Damit kann zugleich das Problem kleiner Werte von m (m^2<n) vermieden werden.

Ein weiteres Beispiel ist die seltsame Aussage:

Der große Vorteil des Rabin-Kryptosystems ist, dass man es nur dann brechen kann, wenn man das beschriebene Faktorisierungsproblem effizient lösen kann.

Tatsächlich ist das Verfahren nur sicher unter der Voraussetzung einer eher zweifelhaften Annahme und dies wird als großer Vorteil verkauft - einfach lachhaft.

Die Aussage ist zudem offensichtlich falsch. Denn für den Spezialfall kleiner Werte von m, genauer falls m^2<n kann der Code völlig trivialer Weise gebrochen werden. In diesem Spezialfall hat die Restbildung modulo n keinen Einfluß auf die Chiffre c=m^2. Die Entschlüsselung ist identisch mit einer ganz gewöhlichen Berechnung der Wurzel aus (m^2). Dies ist auch für große Zahlen überhaupt kein Problem.

Benutzer:Fsswsb 23.05.2006

Also zunächst mal wäre ein weniger arrogant wirkender "I know it all" Schreibstil von dir wünschenswert. Inhaltlich bin ich aber teilweise auf deiner SEite. Der Artikel ist mathematisch sehr unpräzise. Wahrscheinlich nicht von nem Mathematiker geschrieben.

Nun aber mein eigentliches Anliege: Du sagst, für kleine Klartexte m mit m^2 < n kann man den "Code brechen". Das ist doch genauso unpräzise! Was heist "den Code brechen?" Klar kann man die Integer Wurzel ziehen, und man bekommt damit eine Wurzel und die kann der Klartext sein. Den geheimen Schlüssel bekommst du so aber nicht. Dazu brauchst du zwei essentiell verschiedene Wurzeln, also zwei Wurzeln die nicht gegenseitig ihr negatives mod p und mod q sind. Und es gibt keine Möglichkeit diese beiden essentiell verschiedenen Wurzeln aus der einen Integer Wurzel abzuleiten. Bzw. würdest du eine solche Möglichkeit kennen, könntest du damit eine aus zwei Primzahlen zusammengesetzte ntürliche Zahl faktorisieren. Du hättest also das Faktorisierungsproblem gelöst! (Und ja das Faktorisierungsproblem ist ein konkret definiertes math. Problem)

Review-Diskussion

Ich habe viel Mühe in den Artikel gesteckt und versucht ihn auch dem Laien näher zu bringen. Mein (fachfremder) Mitbewohner hat ihn schon gegengelesen und nach einigen Korrekturen alles verstanden. Nun seid Ihr dran: Was fehlt Euch noch, wo habt Ihr Verständnisprobleme? Gewisse Mathevorkenntnisse sind allerdings zum Verständnis des eigentlichen Verfahrens unabdingbar. Stern 02:01, 18. Jun 2004 (CEST)

• Inhaltlich kann ich als Nichtmathematiker wenig dazu sagen, der Stil ist m.E. aber noch etwas "unenzyklopädisch": Wie wir sehen erhalten wir bei der Entschlüsselung neben unserem Klartext auch drei weitere Ergebnisse. Wir müssen also das richtige Ergebnis raten. Sind WIR hier im Matheseminar? ;-) Gruss, Stefan64 10:43, 18. Jun 2004 (CEST)
  • Wie hättest Du es denn formuliert? Würdest Du auf "man" zurückgreifen? 128.176.159.113 11:50, 18. Jun 2004 (CEST)
    • Vieles läßt sich so formulieren, dass auf "wir" oder "man" verzichtet werden kann - meist wird die Formulierung dann sogar klarer und logischer. Für diese beiden Sätze z.B.: "Die Entschlüsselung liefert zusätzlich zum Klartext drei weitere Ergebnisse, das richtige Ergebnis muss also erraten werden." Klingt für weitaus prägnanter als die Formulierung mit "wir", oder ein Äquivalent mit "man". -- srb 13:47, 18. Jun 2004 (CEST)
      • Habt Recht, klingt runder. Ich bau es gerade ein. Stern 17:11, 18. Jun 2004 (CEST)

Hat noch jemand Ergänzungsideen? Ich finde es eigentlich ganz gut jetzt, um nicht zu sagen exzellent :-) Stern 20:30, 20. Jun 2004 (CEST)

Gib es vielleicht irgendwie eine Möglichkeit, nicht sofort in den mathematischen Block der Kryptografie einzusteigen? Der Block ist sicher vollkommen korekkt und super gemacht, der Laie ht von dem Artike jedoch gar nciht. Der gesamte Text bildet ine Herleitung der mathematischen Formel. Ert sagt gar nichts über das Verschlüsselungsverfahren, ausser das er uns die Herleitung der Formeln anbietet. Ein paar Vorschläge: Wie sieht es mit der Geschichte (Entwicklung) dieser Verschlüsselungstechnik aus, wie unterscheidet es sich vion RSA und anderen Verschlüsselungsmethoden. Wo wird oder wurde es angewandt ... ? Die Bewertungen stehn frei im Raum, sind das jetzt Vorteile, Nachteile, warum? In der jetzigen Form kann ich mit dem Artikel leider gar ncihts anfangen. -- Necrophorus 13:33, 22. Jun 2004 (CEST)

Durch den Geschichtsteil sollte der Einstieg nun leichter fallen. Ich hatte im Text bewusst auf Herleitungen verzichtet. Die Formeln im Text erklären ja stur den Algorithmus und sind daher ein einfaches Kochrezept, keine Herleitungen. Das Verfahren wird also durchaus beschrieben, vielmehr konzentriert sich der Text ja sogar auf das Verfahren selbst. Ich habe nun einen kleinen Geschichtsteil eingebaut. Außerdem einen Effizienzvergleich mit RSA ergänzt. Ich habe versucht die Bewertungen alle als Vor- oder Nachteile zu kennzeichnen. Sollte Dir eine Stelle noch nicht als solches erkennbar sein, weise bitte nochmal drauf hin. Ist es nun in Ordnung? Stern 18:06, 22. Jun 2004 (CEST)

Noch ein paar Anmerkungen meinerseits:

• Im Formelteil war ich ständig am überlegen, was jetzt dieser Buchstabe bedeuten soll, und was jener - irgendwie geht da der Lesefluß und das Verständnis ziemlich den Bach runter
• Bei der Effektivität wird davon geredet, dass die Äquivalenz zum Faktorisierungsproblem verloren geht (wenn man das raten erleichtern/vermeiden will), bei Sicherheit steht dagegen nichts davon.
• Welche Auswirkungen hat der Verlust der Äquivalenz? Ist es auch nach Verlust der Äquivalenz noch sicherer als RSA?
• Wird das Verfahren angewendet - wenn ja, mit Klartexte spezieller Struktur?
• Wie groß wählt man die Primzahlen, falls es praktisch eingesetzt wird?
• Zum Geschichtsteil: Wurde es jemals angewandt? wie verbreitet war/ist es?
• Die Optik der math-ausgezeichneten Buchstaben im Fließtext sieht bei mir übel aus. Da ich einfaches Tex durch html ersetzen lasse, sind die math-Buchstaben nur halb so groß wie der normale Text.

Der Artikel gefällt mir schon sehr gut, auch die Verlinkung zu verwendeten Fakten ist sehr gut. Das einzige Problem, das ich im Moment sehe, liegt in den vielen Variablen im Formelteil, -- srb 18:42, 22. Jun 2004 (CEST)

Naja, wesentlich verändert hat sich ja nichts, den Geschichtszweizeiler konnte man auch vorher schon aus dem Kontext erschliessen. Vielleicht mal andersrum: Ich habe in keinster Weise den Anspruch, die mathematischen Methoden zu Verstehen, dazu fehlen mir einfach die mathematischen Kenntnisse. Aber es muss doch mehr an einm Verfahren geben als eine Auflistung unverständlicher Formeln. Ich weiss immer noch nicht, wer wann wie das System warum genutzt hat, welches Systeme es ablöst und von welchen es abgelöst wird, ob es sich weiterentwickelt hat in den 30 Jahren seit seiner Erfindung oder ob es Varianten gibt. Wie wird codiert und decodiert, gibt es Kodiermaschienen oder wurde das Verfahren erst effektiv angewendet, seit es Computer gibt. Ist die Anwendung eher im miulitärischen Bereich zu suchen oder liegt sie irgendeienr Informationsübertragung im Internet zu Grunde? Vielleicht ist meine Kritik für einen Mathematiker auich nicht fassbar, vielleicht schreibe ich Quark, bin halt nur Biologe mit dem Anspruch, dass auch ich wenigstens etwas Information aus einem Artikel ziehen kann, ohne vorher einige Semester Mathematik zu studieren und ganz besonders gilt das für einen Artikel, der in die Exzellenten soll. Ich schreibe meine Tierartikel doch auch nicht auf Latein, was meines Erachtens vergleichbar wäre. Liebe Grüße, -- Necrophorus 18:52, 22. Jun 2004 (CEST)

Warum eigentlich nicht, das würde mich jetzt schon interessieren - und VICIPÆDIA LATINA würde es sicherlich auch freuen ;-) -- srb 19:17, 22. Jun 2004 (CEST)

Ich weiß immer gar nicht, ob Artikel wirklich immer komplett laienverständlich sein sollten und können. Beispielsweise ist ja auch in diesem Artikel eingangs erklärt, was das Verfahren leistet. Das Verfahren selbst ist pure Mathematik und lässt sich wohl kaum einfach erklären (auch wenn ich das wie gesagt weiterhin versuche) ohne zu pfuschen, wobei ja bereits in der Einleitung auf asymmetrische Kryptosysteme verwiesen wird. Die Zielgruppe für Ver-/Entschlüsselung ist bei diesem Verfahren jemand, der ein Kryptosystem praktisch umsetzen will. Muss man also einen Artikel nicht immer auch so schreiben wie die Leute, die auf den Artikel klicken es erwarten? Kann ein Artikel exzellent sein, selbst wenn ihn nicht alle von vorne bis hinten verstehen? Ich meine schon, dann wer den Artikel nicht versteht, hat dank guter Verlinkung ja die Möglichkeit sich die mathematischen Grundlagen anzueignen. Ich bleibe aber weiter am Ball und versuche zu verbessern. Stern 19:29, 22. Jun 2004 (CEST)

Vor dem Problem stehen viele, die einen Artikel auf ein gewisses Level gehoben haben bzw. heben wollen: wenn der Artikel komplett laienverständlich sein soll, dann enthält der Artikel kaum noch was relevantes, wenn man auf Fachchinesisch (in diesem Fall Formeln) weitgehend verzichtet, hat bringt man den eigentlichen Inhalt nur sehr schwer rüber. Verwendet man jedoch Formeln und Fachchinesisch, grenzt man viele Leser aus. Das Problem ist, einen Kompromiss zu finden, der beide Seiten weitgehend zufriedenstellt - den Laien und den Spezialisten. Aber noch eine Frage: Wie kommst Du auf die Idee, das die Zielgruppe bei denen liegt, die das System praktisch umsetzen wollen, m.E. schauen die in dem Fall nicht in einer Enzyklopädie nach, sondern in der entsprechenden Fachliteratur - die Zielgruppe sind einfach Personen, die den Begriff mal hören, und jetzt wissen wollen, worum es sich handelt, egal ob Mathematiker oder z.B. Philosoph. Beide sollten einen Gewinn aus dem Artikel ziehen können, und nach dem Lesen auch wissen, worum es eigentlich geht - auch wenn der Philosoph die dahindersteckende Mathematik nicht verstanden haben sollte. -- srb 20:04, 22. Jun 2004 (CEST)

Wie ich bereits geschrieben habe, habe ich gar nicht den Anspruch, den mathematischen Tei zu verstehen, ich würde einfach bei einem solchen Artikel gern mehr "Beiwerk" lesen, in dem Sinne wie ich es oben geschrieben habe. Alle dort angeführten Fragen sind Fragen, die ich mir stelle und gern beantwortet haben möchte, wenn ich einen Artikel über ein solches Thema angehe, wenn dann noch der spezielle Teil für Mathematiker und Praktiker folgt, umso besser. Ein gutes Beispiel für die Verknüpfung von Laien- und Experteninteresse bietet meines Erachtens der Artikel Elektromigration, sowas sollte doch auch hiermit zu erreichen sein, oder? Wenn nicht, sorry, dann gehört der Artikel in ein Fachbuch oder eine Formelsammlung aber nicht in eine Enzyklopädie und dort schon gar nicht in die Exzellenten. -- Necrophorus 20:20, 22. Jun 2004 (CEST)

Probier doch einfach mal, ob Du nicht in den Abschnitten Verschlüsselung und Entschlüsselung die Idee am Anfang mit ein paar Worten skizzieren kannst, bevor dann die Formeln den Sachverhalt mathematisch korrekt vermitteln.

@Necrophorus: Du scheinst ja heut nicht besonders gut gelaunt zu sein - der Artikel gehört auch jetzt schon zu den besseren im mathematischen Umfeld und hat auch so seinen Platz in der WP verdient - und über die Verlinkung kann sich auch jetzt schon ein Laie ein Bild davon machen, worum es geht. Wir dürfen bei aller Kritik nicht vergessen, dass wir hier eigentlich nur darüber streiten, ob er schon gut genug für die Exzellenten ist - und nicht über einen Löschkandidaten. -- srb 20:39, 22. Jun 2004 (CEST)

Sehe ich zwar auch so, aber ich verstehe ja auch, worum es Necrophorus geht. Ich versuche in den nächsten Tagen mal Stück für Stück eine Verbesserung herbeizuführen und sage dann hier bescheid. Stern 21:06, 22. Jun 2004 (CEST)

Gut, ich habe mich falsch ausgedrückt sorry, natürlich will ich keine Löschung des Artikels. Ich finde einfach nur, dass man als Experte auch mal die Scheuklappen ablegen sollte und sich Gedanken machen könnte, was rechts und links von dem rein mathematischen Inhalt in einen solchen Artikel gehört. Der mathematische Anteil mag ja meinethalben exzellent sein, dem Laien hilft das wenig, der will andere Informationen zu einem Artike über ein spezielles Verschlüsselungsverfahren und die bekommt er weder in dem Artikel noch in den angelinkten Texten. Auf meine Fragen oben wurde bislang nicht mal eingegangen und sie waren sicher nicht destruktiv gestellt, oder? Warum versuche ich eigentlich, Artikel von Medizinern wie das Fragiles X-Syndrom laientauglich zu schreiben, wenn die Mathematiker sich einbilden, die Weisheit mit Löffeln gefressen zu haben. So, und jetzt bin ich tatsächlich sauer über so viel Verbohrtheit. Macht euern Mathekram also bitte ohne mich weiter, hier kommt jedenfalls von mir kein Komentar mehr. -- Necrophorus 21:11, 22. Jun 2004 (CEST)

Haaaaaalt! So schnell kommst Du mir nicht davon :-) Ich habe gerade versucht die einzelnen Abschnitte mit einer "laientauglichen" und zusammenfassenden Einleitung zu versehen. Das dürfte dem Laien vielleicht etwas Angst vor den Formeln nehmen. Ist es jetzt schon halbwegs gut (auf die weiteren Kritikpunkte von Euch versuche ich in den nächsten Tagen auch noch einzugehen)? Übrigens bin ich kein Mathematiker, sondern Ökonom :-) Stern 21:30, 22. Jun 2004 (CEST)

Calm Down! Ein ausführlicher geschichtlicher Abriss über die Kryptographie (von Gaius Julius Caesar bis RSA und weiter) wäre wünschsenswert. Isoliert für das hier abghehandelte Verfahren würde meiner Meinung nach nicht das bringen, im Vergleich zu einem im gesamten Vergleich. Ein Bespiel werde ich mal zurecht konstruieren. Wichtig ist aber auch, das die gesamten neueren Verfahren, sollten sie nicht in einem mehr als 10¹⁰⁰ Zeichen umfassenden Alphabet verwendet werden, ohne Block-Chiffrierung gar keinen Sinn machen würden. Die Kombination machts.

Ach ja, in einer der Ausgaben der C't wurde in einer der Geschichten mal anschaulich das RSA-Verfahren abgehandelt. --Arbol01 21:47, 22. Jun 2004 (CEST)

Ich habe nun versucht, weitere Fragen zu beantworten. Über genauere praktische Anwendungen fehlt mir präzises Wissen, im Web habe ich leider auch sehr wenig gefunden. Ich gehe aber davon aus, dass das Verfahren in vielen Programmen praktisch eingesetzt wird. Wer in den Punkten mehr weiß als ich, kann es ja ergänzen (Das gilt natürlich auch für RSA). Stern 21:51, 22. Jun 2004 (CEST)

Nachdem ich nun auch noch etwas zur praktischen Anwendung des Verfahrens gefunden habe (wird praktisch wegen bestimmter Angriffsmöglichkeiten kaum benutzt) nochmal meine Gretchenfrage: Kann man den Artikel so langsam als exzellent bezeichnen? Stern 23:52, 23. Jun 2004 (CEST)

Durch die Prosaeinleitungen ist der mathematische Teil deutlich übersichtlicher - vielleicht könnte man die "mathematischen Spezialteile" noch komplett eine Stufe einrücken? Das müßte eigentlich dazu führen, dass auch ein Laie sehr schnell erkennt, welche Teile für ihn lesbar sind, und welche nicht.

Das das Verfahren nicht praktisch genutzt wird, sollte auch in der Einleitung schon erwähnt werden - das ist schließlich ein wesentlicher Punkt.

Ansonsten gefällt mir der Artikel mittlerweile sehr gut. -- srb 12:21, 24. Jun 2004 (CEST)

Hier findet, wenn ich das richtig sehe, seit einiger Zeit ein "Kulturkrampf" statt. Das "Mathematik-Trio" gegen den Rest der Welt. Einzig Necrophorus WOLLTE sich überhaupt dazu äussern. Nachdem er dann hier als "Mathe-Trottel" vorgeführt wurde, war er sauer (Macht euren Mathekram also bitte ohne mich weiter) und so findet (und nicht allein in diesem Text!!!) ab jetzt nur ein Trigespräch zum Thema statt. Diese Entfremdung ist sicher nicht durch die "Mathe-Trottel" (ja, ja, ich bin auch einer) zu brechen, befürchtet --Cornischong 12:54, 24. Jun 2004 (CEST)

Da Du mich also anscheinend zum "Mathe-Trio" zählst: Bei einem Artikel über ein mathematisches Verfahren gehört nun mal auch Mathematik, und meist auch einige Formeln dazu - aber wenn Du meine Äußerungen mal durchliest, gehen viele meiner Bemerkungen gerade weg von der Formellastigkeit und hin zu etwas, was auch ein Laie verstehen kann. Ich habe an anderer Stelle schon mal darauf hingewiesen, dass das große Problem bei sehr vielen "Fachartikeln" darin besteht, den Spagat zwischen korrekter Information und Allgemeinverständlichkeit zu schaffen. Und gerade da sind auch Kommentare von Laien, in diesem Fall "Mathe-Trottel" wie Du Dich ausdrückst, unabdingbar.

Was die Sache mit Necrophorus betrifft, ich habe nur seine Aussage, "dann gehört der Artikel in ein Fachbuch oder eine Formelsammlung aber nicht in eine Enzyklopädie" aufgegriffen, und kritisiert. Wenn das schon als Beleidigung zählt, tut es mir leid - aber zu meiner Aussage stehe ich trotzdem: Wir dürfen, bei aller Kritik, nicht vergessen, dass wir wir über Artikel diskutieren, die schon ein durchaus beachtliches Niveau erreicht haben. -- srb 13:24, 24. Jun 2004 (CEST)

Ich verstehe die Diskussion hier nicht. Zum einen kann ich nicht erkennen an welcher Stelle Necrophorus beleidigt oder gar vorgeführt wurde. Dann kann ich nicht erkennen, das nicht auf Verbesserungsvorschläge eingegangen wurden. Und zuguterletzt kann ich auch keinen Kulturkampf sehen. Ich habe selten eine selbst für Nichtmathematiker so verständliche Schilderung des Verfahrens gelesen. Kryptologie ist pure Mathematik auf hohem Niveau, für den Laien meist völlig unverständlich. Da ist es doch toll, wenn sich ein paar Benutzer bemühen, Nichtmathematiker ins Boot zu holen. Wie gesagt: ich finde es ist ziemlich gelungen. Es geht eben nicht um einen Artikel über Fußball oder die Sonnenblume, sondern um Gruppentheorie, Faktorisierungsprobleme und Multiplikationen modulo n. Ich finde es schade, dass sich ausgerechnet derjenige, der nun durch seine kritischen Bemerkungen zu einer entscheidenden Verbesserung Verbesserung des Artikels beigetragen hat, nicht mehr äußern will. 128.176.114.42 18:11, 24. Jun 2004 (CEST)

Eigentlich würde ich vorschlagen diese Diskussion auf die Diskussionsseite des Artikels zu verlagern. Aber vorher würde ich doch noch gerne wissen, was Nichtkryptologen gerne noch etwas näher erleutert haben würden. Weitere Geschichtsdaten und Anwendungsbeispiele liegen mir leider nicht vor. Stern 21:38, 24. Jun 2004 (CEST)

Gut, noch ein Versuch:

• @Stern: Deine Bemühungen, den mathematischen Teil in ein Textgefüge zu basteln sind erstklassig gelungen, danke von allen Nichtmathematikern.
• @srb:sorry, manchmal reagiere ich etwas unkonventionell. Mir ging einfach auf den Geist, dass offensichtlich Konsens herrscht darüber, dass ein Nichtmathematiker den Artikel gar nciht verstehen brauch bzw. sollte, wenn er exzellent werden soll. Ich bin im Moment etwas gestresst (2 kranke Kinder nerven einen schon, wenn man Hausmann ist). Also sorry für die Anfeindung.
• So, nun aber zurück zum Artikel:

1. Das Rabin-Kryptosystem war das erste asymmetrische Kryptosystem, dessen Sicherheit bewiesen werden konnte. Wie wurde das bewiesen, wie haben bei dem gleichen Test andere Systeme abgeschnitten
2. Das Beispiel der Schlüsselerzeugung hinkt irgendwie: Wenn ich den öffentlichen Schlüssel 77 (n) kenne, dann gibt es doch nur zwei Möglichkeiten jeweils für p und q, namentlich die geheimen Schlüssel 7 und 11, ein anderes Multiplikatorenpaar ergibt doch gar nicht 77
3. da ich den Artikel Chinesischer Restsatz nicht verstehe, wüsste ich jetzt auch nicht, wie ich den nutzen soll, aber das ist eher sekundär.

• Ansonsten prima, sehr gute Arbeit. Liebe Grüße, -- Necrophorus 23:16, 24. Jun 2004 (CEST)

Ich habe versucht die Fragen im Text zu beantworten. Wird es jetzt verständlich? Stern 00:01, 25. Jun 2004 (CEST)

O.k., Mathetrottel Necrophorus hat keine Einwände mehr. Sobald ihr die Fachfragen gelöst habt, die ich natürlicherweise nicht nachvollziehen kann, würde ich sagen, ab auf die Vorschlagsliste. -- Necrophorus 10:13, 25. Jun 2004 (CEST)

Zu der Schlüsselerzeugung zwei Dinge: Im Normalfall handelt es sich bei den beiden Primzahlen p und q um hundertstellige, oder größere Primzahlen. Aus einem zweihundertstelligen oder größeren Produkt die Primfaktoren zurück zu ermitteln ist ein riesiger Aufwand.

Trotzdem hakt es irgendwo bei der Schlüsselerzeugung.

Um mit dem RSA-Verfahren als Beispiel zu kommen: mit (p-1)*(q-1) = φ ( N ) bekommt man die eigentliche Zahl, aus der man letztendlich die beiden Schlüsselkomponenten e und d gewinnt. Wenn man N, e und d hat, besitzt man alle notwendigen Komponenten, alle anderen Zahlen p, q und φ ( N ) sind Ballast.

Irgendwie scheint etwas bei dem Rabin-Algorithmus nicht klar genug (oder falsch) beschrieben zu sein.

Die eigentliche Sicherheit liegt vor allem darin, das man leicht ein Produkt aus sehr großen Primzahlen erzeugen kann, daß aber die Faktorisierung von riesigen Zahlen nicht trivial ist (siehe Faktorisierung). --Arbol01 23:57, 24. Jun 2004 (CEST)

Ergänzung: Bei der Schlüsselerzeugung des Rabin-Verfahrens scheint N=p*q der öffentliche Schlüssel zu sein, und p und q selbst Teil des geheimen Schlüssels.

Bei z.B. 20906649663594481 dürfte es schon sehr viel schwieriger sein, die beiden Primfaktoren zu ermitteln, als bei 77. Schwer ist es trotzdem nicht, da mein TI-Taschenrechner Minuten, und ein Programm wie Mathematica (oder so ähnlich) dafür Sekunden brauchen dürfte.

Wäre N und z.B. p Teil des öffentlichen Schlüssels, dann hätte man mit p einen der beiden Primteiler, was nicht sein kann. --Arbol01 00:15, 25. Jun 2004 (CEST)

Was genau stört Dich bei der Rabin-Schlüsselerzeugung? Bei Rabin sind p und q keineswegs Ballast (sondern bilden gemeinsam gerade den geheimen Schlüssel), n natürlich auch nicht (das ist ja gerade der öffentliche Schlüssel). Mehr benötigt man dann aber für Rabin auch nicht. RSA funktioniert anders. Wenn ich irgendwo konkretisieren soll, sag mir nochmal wo genau. Stern 00:05, 25. Jun 2004 (CEST)

Sorry, habe deine Nachricht erst nach meiner Antwort auf Necrophorus Antwort gelesen. Ich bezog den Ballast auch nur auf das RSA-Verfahren (mich erstaunt schon, das nach meinem Geholze im RSA-Artikel, ich noch nicht gesteinigt worden bin).

Wenn ich wüßte, was mich genau stört, hätte ich vieleicht kein Problem. Aber vielleicht sollte man neben r und s (die ich beide Nachvollziehen kann, auch noch (-r) un (-s) als komplette Formel ausschreiben. So war ich mir nicht sicher, ob z.B. $(y_{p}*p*m_{q}+y_{q}*q*m_{p})\mod N$ korrekt ist, oder ob vielleicht versehentlich m_p und m_q versehentlich vertauscht worden sind. --Arbol01 00:36, 25. Jun 2004 (CEST)

Obwohl mir die Formeln für (-r) und (-s) nicht bekannt sind, sind jetzt für mich alle Unklarheiten des Systems beseitigt. Die Schlüsselerzeugung ist korrekt dargestellt.

Bei der Verschlüsselung hätte man vielleicht erwähnen sollen, das maximal 4 verschiedene m ein gemeinsames c besitzen können (das habe ich jetzt nachgeholt).

Danach wird auch verständlich, das für ein c (bis zu) 4 verschiedene m bei der entschluesselung erzeugt werden.

Dies ist auch das größte Manko des Systems, da die Verschlüsselung und die Entschlüsselung nicht von Hand, sondern von Computern automatisch vorgenommen wird. Wenn die erzeugten Permutationen bei einem Zeichen noch 4 sind, dann steigen sie bei längeren Texten schnell auf unerträglich große Mengen

Eine Funktion, die noch eine zusätzliche Information (0=r, 1=s, 2=(-s), 3=(-r)) oder so ähnlich, mitlifern würde, möglicherweise noch als zusätzliche Bits in den Code eingebaut, würden das Dilemma umgehen. --Arbol01 09:22, 25. Jun 2004 (CEST)

Man berechnet (wenn ich das auf die schnelle jetzt richtig sehe) -r und -s folgendermaßen. -r = n - r bzw. -s = n - s. @Arbol01: Hast Du das Verfahren gerade implementiert? Falls ja, kannst Du es ja mal mit diesen Formeln testen und bei Erfolg in den Text einbauen, falls man das mathematisch überhaupt so schreiben darf, wie ich das gerade gemacht habe. Ich kenne mich zu wenig mit Blockchiffre aus, aber bist Du Dir sicher, dass jedes einzelne Zeichen einzeln verschlüsselt wird? Werden nicht ganze Blöcke verwendet? Dann wäre das was Du als großen Nachteil doch nur noch halb so schlimm. Stern 13:22, 25. Jun 2004 (CEST)

Nein, ich habe nicht die Wurzeln berechnet, sondern umgekehrt die ersten 40 Quadratischen Reste berechnet, und dann die Zahlen (die Symmetrie mit berücksichtigend), die Zahlen, die gleiche Reste zurückliefern zusammengefasst. Ein Brute Force-Angriff sozusagen. Ich mache das noch mit 713. So eine kleine Gemeinheit sozusagen.

Ich denke, deine Beobachtung bezüglich -r = n - r bzw. -s = n - s stimmt.

Bei der Blockchiffrierung werden in der Regel eine feste Anzahl von Zeichen zu Blöcken zusammengefaßt, so wie ich es im Beispiel des RSA-Verfahrens gemacht habe. Meist dürfte das eine 2er Potenz aus 8, 16 oder mehr Zeichen sein. Wie schon angedeutet habe ich da etwas vor, nämlich 2er-Blöcke.

Du wirst, so ich recht habe feststellen, das der Nachteil kein bisschen kleiner ist, als mit Einzelverschlüsselung. --Arbol01 16:55, 25. Jun 2004 (CEST)

Wie gesagt, bin kein Experte im Bereich Blcokchiffre. Stern 17:24, 25. Jun 2004 (CEST)

Sehe ich es richtig, dass damit alle Fragen ausgeräumt sind? Wenn keine neuen auftauchen oder gravierende Verbesserungswünsche bestehen, schlage ich vor, diese Diskussion auf die Diskussionsseite des Artikels zu verschieben und den Artikel bei den Exzellenzkandidaten aufzulisten. Seid Ihr damit einverstanden? Stern 17:24, 25. Jun 2004 (CEST)

Umsetzung

Waehrend es mir relativ leicht faellt, den RSA-Algorithmus umzusetzen, habe ich bei dem Rabin-Verfahren sozusagen unueberwindliche Schwierigkeiten. Entweder ein paar der Formeln sind nicht korrekt, oder/und in der Erklaerung sind ein paar Sachen unstimmig bzw. schlecht ruebergebracht. So komme ich nur auf zwei "Wurzeln" statt auf vier. Und von den zwei Wurzeln hat moch nie der Wert die Umkehrung zum Klartext (nicht einmal Zuffaellig) ergeben. --Arbol01 12:06, 24. Jun 2004 (CEST)

Beachte, dass +/-r und +/-s in einem Ring liegen. -r ist also nicht -5, wenn r=5 ist. Klärt das Deine Frage vielleicht? Wenn ja, wie könnte man es anschaulicher schreiben, so dass der nächste nicht wieder vor dem gleichen Problem steht? Stern 00:12, 25. Jun 2004 (CEST)

Quadratischer Rest

Bevor ich kurz vor 02:00 Uhr (griechischer Zeit) letzte Nacht zu Bett gegangen bin, hat sich mir ein schlimmer Verdacht gebildet:

$m^{2}\mod n$ ist nämlich nichts anderes, als ein Quadratischer Rest, der dazu nicht zu einer Primzahl, sondern zu einer zusammengesetzten Zahl ist. Solche Quadratischen Reste sind symmetrisch. Beispiel 11:

$0^{2}\mod 11=0$ $1^{2}\mod 11=1$ $2^{2}\mod 11=4$ $3^{2}\mod 11=9$ $4^{2}\mod 11=5$ $5^{2}\mod 11=3$ $6^{2}\mod 11=3$ $7^{2}\mod 11=5$ $8^{2}\mod 11=9$ $9^{2}\mod 11=4$ $10^{2}\mod 11=1$

Das bedeutet, das sich manche m ein c teilen müssten.

Nun ist 11 eine Primzahl, und ein gesuchtes n ein Produkt zweier Primzahlen mit einer bestimmten Bedingung (p und q sollen Mod 4 gleich 3 sein). Also habe ich mal das Gleiche mit der Zahl 77 gemacht:

[ 1, 34, 43, 76] => 1
[ 2,  9, 68, 75] => 4
[ 3, 25, 52, 74] => 9
[ 4, 18, 59, 73] => 16
[ 5, 16, 61, 72] => 25
[ 6, 27, 50, 71] => 36
[ 7, 70]         => 49
[ 8, 36, 41, 69] => 64
[10, 32, 45, 67] => 23
[11, 66]         => 44
[12, 23, 54, 65] => 67
[13, 20, 57, 64] => 15
[14, 63]         => 42
[15, 29, 48, 62] => 71
[17, 38, 39, 60] => 58
[19, 30, 47, 58] => 53
[21, 56]         => 56
[22, 55]         => 22
[24, 31, 46, 53] => 37
[26, 37, 40, 51] => 60
[28, 49]         => 14
[33, 44]         => 11
[35, 42]         => 70

Zu den meisten c gehören also 4 m. Dazu paßt gut, das bei der entschlüsselung das c die vier Wurzeln r, (-r), s und (-s) zurückliefert.

[13, 20, 57, 64] => 15 "Im Beispiel gilt $m\in \{64,\mathbf {20} ,13,57\}$."

Etwas, was vieleicht fehlen würde, wäre ein Mathematischer Multiplexer. --Arbol01 08:52, 25. Jun 2004 (CEST)

Es seien p und q ...

in meinen Ohren klingt das unnötig gestelzt und gewollt mathematisch. In der Mathematik gehen Formulierungen, die mit es seien x und y beginnen und am besten noch mit o.B.d.A. gespickt werden, normalerweise mit dann gilt weiter. Das ist hier nicht der Fall. Der Konjunktiv ist IMHO unangebracht. Zur Schlüsselerzeugung wählt man zwei verschiedene, möglichst große Primzahlen ähnlicher Größenordnung. Die beiden Primzahlen p und q bilden den geheimen Schlüssel. Das Produkt wird als öffentlicher Schlüssel bekannt gemacht Rat 18:46, 27. Jun 2004 (CEST)

Die Langform wäre ja "Es seien p und q mit dem Wert sowienoch beispielhaft angenommen. natürlich kann man das auch mit "Im Beispiel haben p und q den Wert sowienoch" schreiben. In der Tat entwickelt jede Wissenschaft eine Sprache, die sich von den Gewohnheit der Umgangssprache entfernt. Als jemand, der im fach drin ist, merkt man das aber oft nicht. Darum ändere einfach die Stellen so um, dass sie eingängiger sind! Stern 20:54, 27. Jun 2004 (CEST)

Beispiel

Wie auch aus der Diskussion ersichtlich, ist das Beispiel n=77 etwas ungeschickt gewählt. Wenn du zwei 2 oder 3-stellige Primzahlen nimmst, kann jeder nachvollziehen, dass man das Produkt sofort berechnen kann, die Faktorisierung aber wesentlich schwieriger ist. Mit Zahlen dieser Größenordnung kriegt man auch ein einleuchtend(er)es Beispiel hin, wie man mit Zahlen Nachrichten verschlüsseln kann.

Im Duden Informatik (ISBN 3411052333) wird als Beispiel (bei der Erläuterung des RSA Verfahrens) die Kodierung 00=leer 01=A 02=B .. 26=Z gewählt. Das Wort STALL kodiert sich zu 1920 0112 1200. Ein Klartextblock entspricht also 2 Buchstaben und ist eine Zahl aus dem Bereich 0000 bis 2626. Mit p=47 und q=59 kommst du auf n=2773 und hättest den gewünschten Bereich abgedeckt. Die beiden erfüllen auch die Kongruenzbedingung.

Ein solches Beispiel dürfte für die meisten Leser nachvollziehbarer sein als ein abstrakter "Klartextraum" 0..76 -- Rat 19:24, 27. Jun 2004 (CEST)

Ich hatte das Beispiel bewusst so klein gewählt, damit man es leicht mitverfolgen kann (jeder kann 7 mal 11 im Kopf rechnen :-)). Im Text ist ja auch erwähnt, dass das Problem erst für größere Primzahlen komplexer wird. Solltest Du aber ein besseres Beispiel haben, dann tu Dir keinen Zwang an! Stern 20:54, 27. Jun 2004 (CEST)

Wie wäre es mit n=713. Leider habe ich die beiden Primfaktoren p und q nicht zur Hand, aber sie erfüllen die Nebenbedingung p Mod 4 = 3 und q Mod 4 = 3.

Der Klartextraum AA bis ZZ ist abgedeckt, und ein gewisser Überhang ist nicht zu vermeiden, so das ich mit einem Alphabet aus 27 Zeichen [A=0 ... Z=25 *=26] gearbeitet habe. Einen Schlüssel so zu wählen, das er ideal aufgeht, ist fast immer unmöglich.

AA= [ AA ]
AB= [ AB GX TP *K ]  AC= [ IJ KB QK SC ]  AE= [ AC MT NT *J ]  AI= [ GJ JU QS UC ]
AJ= [ AD FX UP *I ]  AQ= [ AE BA ZL *H ]  AS= [ BL DT WT ZA ]  AZ= [ AF HX SP *G ]
BE= [ IB SK ]        BF= [ GZ MS NU TN ]  BI= [ CG LL PA YF ]  BJ= [ AG LT OT *F ]
BM= [ KZ MC OJ PN ]  BO= [ D* GH UE WM ]  BU= [ JJ KF QG RC ]  BW= [ AH EX VP *E ]
BX= [ CR LE PH XV ]  CF= [ FJ JQ QW VC ]  CI= [ MR NV ]        CK= [ AI CA YL *D ]
CP= [ HS SU ]        CQ= [ BU FE VH YS ]  CR= [ BB HA TL ZK ]  CS= [ CW HL TA XQ ]
CY= [ CM DI XD X* ]  DA= [ AJ IX RP *C ]  DB= [ GF IU RS UG ]  DG= [ IG KO PY SF ]
DM= [ DM W* ]        DN= [ FV MQ NW UR ]  DO= [ BM DE XH Y* ]  DR= [ FO I* RM UY ]
DT= [ AK KT PT *B ]  DU= [ IR MB OK RV ]  EK= [ HC LS OU TJ ]  EN= [ AL DX WP *A ]
EQ= [ KJ QC ]        EU= [ BC MP NX ZJ ]  EX= [ E* GD UI VM ]  EZ= [ JC LK PB RJ ]
FD= [ IO RY ]        FF= [ DQ EM V* WW ]  FH= [ EJ JM Q* WC ]  FJ= [ AM DA XL Z* ]
FV= [ CH EP VX YE ]  GA= [ EG LD PI WF ]  GB= [ HN KY PO SZ ]  GC= [ HZ MO NY SN ]
GD= [ BV MA OL YR ]  GH= [ AN JX QP ZZ ]  GL= [ CB HE TH YK ]  GM= [ BN KA QL YZ ]
GY= [ JF RG ]        GZ= [ BD FT UT ZI ]  G*= [ GB HU SS UK ]  HB= [ ES ID SI VU ]
HE= [ CS IL SA XU ]  HH= [ AO JT QT ZY ]  HL= [ ED FH VE WI ]  HN= [ LR MN NZ OV ]
HW= [ CN KE QH XZ ]  ID= [ DU FM U* WS ]  IJ= [ AP CX XP ZX ]  IP= [ FC L* OM VJ ]
IR= [ KN LJ PC PZ ]  IU= [ HG KS PU TF ]  I*= [ EV MM N* VR ]  JF= [ BE ZH ]
JK= [ F* UM ]        JM= [ BO JP QX YY ]  JN= [ AQ EA WL ZW ]  JO= [ DJ JI RD XC ]
JT= [ BW HP SX YQ ]  JX= [ DF II SD XG ]  KG= [ LC PJ ]        KJ= [ CI YD ]
KK= [ DN KI QD WZ ]  KO= [ CC ML OA YJ ]  KS= [ FR LQ OW UV ]  KT= [ AR KX PP ZV ]

Ausschnitt aus der Tabelle. --Arbol01 07:05, 28. Jun 2004 (CEST)

Um noch ein konkretes Beispiel zu bringen:

Verschlüsselung:

  HAMMER -> CRI*YE

Entschlüsselung:

  CRI*YE -> [BBEVER BBEVLM BBEVO* BBEVVV BBMMER BBMMLM BBMMO* BBMMVV
             BBN*ER BBN*LM BBN*O* BBN*VV BBVRER BBVRLM BBVRO* BBVRVV
             HAEVER HAEVLM HAEVO* HAEVVV HAMMER HAMMLV HAMMO* HAMMVV
             HAN*ER HAN*LM HAN*O* HAN*VV HAVRER HAVRLM HAVRO* HAVRVV
             TLEVER TLEVLM TLEVO* TLEVVV TLMMER TLMMLM TLMMO* TLMMVV
             .
             .
             ZKN*ER ZKN*LM ZKN*O* ZKN*VV ZKVRER ZKVRLM ZKVRO* ZKVRVV]

--Arbol01 07:47, 28. Jun 2004 (CEST)

Sicherheit

Hmmmmmm - ich verrate es euch, der Beweis, das Verfahren sei definitiv sicher, sofern die Primzahlen $p$ und $q$ nicht aus $n=p\cdot q$ bestimmt werden können, ist totaler Unfug.

Die Kenntnis des Wertes $y=x^{2}{\bmod {n}}$ erlaubt für alle $x<{\sqrt {n}}$ den Wert x zu bestimmen. Es handelt sich um die gewöhnliche Quadratwurzel, denn ${\bmod {n}}$ ändert den Wert in diesem Fall nicht.

-- Franz Scheerer (Wiesbaden) (Diskussion) 20:39, 17. Mär. 2018 (CET)

@Arbol01: Du verzeihst mir bitte, dass ich deine Geistesblitze von heute wieder zurückgesetzt habe. Es geht hier um zusammengesetzte Zahlen der Größenordnung 200 und mehr Dezimalstellen. Da probiert man nicht "mal eben" konsequent alle Zustände von 0 bis n-1 durch. Ohne die beiden Faktoren kriegt man es nicht in endlicher Zeit hin, die 4 Quadratwurzeln zu ermitteln. Wäre das System wirklich so offensichtlicher Unsinn, wäre es wohl nie ernsthaft veröffentlicht worden. Rat 15:32, 28. Jun 2004 (CEST)

@Rat: Entschuldige, wenn ich wieder auf meinen Stand zurücksetze. Du übersiehst, das ich nicht alle Millionen von Quadrupeln brauche, sondern nur ein einziges. Und dafür brauche ich vermutlich nicht mal einen Tag. Ich brauche keine Quadratwurzeln zu ermitteln. Das wäre mir viel zu Mühselig. Hier mein Programm:

/* REXX-Programm */
call load '713.r'
say "Gib n ein:
pull n
do i = 1 to (n-1)
  e.i = 0
end
do i = 1 to (n-1)
  in = i
  out = (i*i) // n
  e.out = e.out + 1
  j = e.out
  a.out.j = in
  call tp i
  say i '=' result '|' out '|' e.out
end
do i = 1 to (n-1)
  if ((i // 23) = 0) then pull x
  say i '= [' a.i.1 a.i.2 a.i.3 a.i.4 ']'
end

Ausserdem benötige ich aus einem Quadrupel nur 3 (beziehungsweise 2) der 4 Zahlen, da k₄ = n - k₁ und k₃ = n - k₂. Es ist also ein Kinderspiel, das Verfahren zu knacken. --Arbol01 17:41, 28. Jun 2004 (CEST)

Selbst wenn man (völlig unrealistisch) annähme, dass die erste der 4 Zahlen im unteren Milliardstel des Bereichs 0..n-1 läge. Dann müsstest du bei n ~ 10^200 statt 10^200 "nur" noch 10^191 Zahlen durchprobieren. Bei 1 Milliarde Zahlen in einer Milliardstel Sekunde (das sind 4 Takte bei einem aktuellen PC) schaffst du pro Sekunde 10^18 Kandidaten. Ne Menge Holz. Aber: bis du das erste Milliardstel durch hast, sind schlappe 10^173 Sekunden vergangen. 1 Jahr ist etwa 3*10^7 Sekunden. Das Alter des Universums wird mit etwa 10^10 Jahren (3 * 10^17 Sekunden) angenommen. Algorithmen mit exponentieller Laufzeit sind ziemlich langsam, wenn sie "richtige" Probleme lösen sollen.

Auch wenn dir diese Zeit zur Verfügung stünde, bekämest du mit dem Algorithmus oben ein Problem. Am Anfang initialisierst du e.i mit i von 0 bis n-1. (Ich kann leider kein REXX, aber soviel habe ich verstanden) Bei den genannten Größenordnungen benötigst du also 10^200 Bit Platz. Die Anzahl der Atome im Weltall wird mit 10^77 angenommen. Beim Bau des Hauptspeichers käme man in echte Rohstoffprobleme ;-)

Die Äquivalenz des Rabin Verfahrens zum Faktorisierungsproblem ist seit Jahren bewiesen. Wenn du ein Verfahren findest, dass das Verfahren kinderleicht knackt, hast du offenbar eine Methode zur Faktorisierung riesiger zusammengesetzter Zahlen gefunden. Lass dich nicht erwischen, denn auf der vermuteten Schwierigkeit der Faktorisierung beruhen verschiedene wichtige Verfahren in der Kryptologie. Die entsprechenden Firmen könnten ihren Laden dicht machen. Die Quantenkryptografie verspricht Abhilfe, ist aber noch nicht marktreif entwickelt.

Ich denke, am Absatz Sicherheit muss noch gefeilt werden. Chosen-Ciphertext Attacken sind auch beim RSA Verfahren möglich. Das Problem der 4 möglichen Ergebnisse kann man lösen (unter Aufgabe der beweisbaren Äquivalenz zum Faktorisierungsproblem) Das kann also nicht der Grund sein, warum es nicht mehr verwendet wird, wie im einleitenden Absatz steht.

Rat 18:29, 28. Jun 2004 (CEST)

Pass auf: Die ersten Zahlen sind ja bekannt. Das ist kein Problem. Angenommen, der Schlüssel n sei 99999620000261 (es ist ein gültiger Schlüssel).

Dann stehen folgende Quadrupel, ohne das ich nur einen Strich gerechnet habe so fest:

  1 = [1  k2  k3  99999620000260]
  4 = [2  k2  k3  99999620000259]
  9 = [3  k2  k3  99999620000258]
 16 = [4  k2  k3  99999620000257]
 25 = [5  k2  k3  99999620000256]
  .
  .

99999792 = [9999979  k2  k3  99999610000282]
 .
 .

Und jetzt kommte es:

99999812 mod 99999620000261 = 100

Das dürfte kein Wunder sein, da der bei dem ersten Überlauf immer eine Quadratzahl vorkommt. Bisher war das immer so.

Da wir schon:

100 = [10  k2  k3   99999620000251] wissen (das steht von Anfang an fest), können wir für k2 = 9999981 eintragen

(und der Vollständigkeit halber für k3 = 99999620000261 - 9999981):

100 = [10  9999981  99999610000290   99999620000251]

So, mal sehen:

 9999981-10 = 99999620000251-99999610000280 = 9999971

 99999610000280 - 10 = 99999620000251 - 9999981 = 99999610000270

Ok, stimmt.

Jetzt den ggT:

ggt(99999620000261,9999971) = 9999971

und

ggt(99999620000261,99999610000270) = 9999991

Jetzt die Probe:

9999971 * 9999991 = 99999620000261 (Gotcha!)

--Arbol01 19:43, 28. Jun 2004 (CEST)

Fazit: Natürlich wäre im Enrstfall mein Programm viel zu unhandlich. Praktisch gesehen muß ich eine Wurzel bestimmen, nämlich die von n. Dann muß ich die erste bzw. die ersten paar Quadratischen Reste nach dem Überlauf ermitteln. Dieser erste Überlauf liegt in etwa bei der Wurzel von n (Beispiele 77 und 713):

Die Wurzel von 77 ist größer 8, die von 713 ist größer 26.

7² mod 77 = 49 mod 77 = 49

8² mod 77 = 64 mod 77 = 64

9² mod 77 = 81 mod 77 = 4 (Quadratzahl)

4 = [2 9 68 75]

9-2 = 75-68 = 7

68-2 = 75-9 = 66

ggT(77,7)=7 ; ggT(77,66)=11

25² mod 713 = 625 mod 713 = 625

26² mod 713 = 676 mod 713 = 676

27² mod 713 = 729 mod 713 = 16 (Quadratzahl)

16 = [4 27 686 709]

27-4 = 709-686 = 23 686-4 = 709-27 = 682

ggT(713,23)=23 ; ggT(713,682)=31

Das ist der Schwachpunkt! --Arbol01 20:07, 28. Jun 2004 (CEST)

Sei mir nicht böse und nichts gegen Deine Idee: Tatsache ist, dass man beweisbar (den Beweis habe ich hier) das Verfahren genau dann brechen kann, wenn man Zahlen schnell faktorisieren kann. Entweder Du hast jetzt eine Möglichkeit gefunden wie man schnell Zahlen faktorisieren kann (da wärst Du seit Jahrtausenden der erste) oder Dein Verfahren wird schnell komplex (ist sehr viel wahrscheinlicher). Leider habe ich aus Zeitmangel nicht die Möglichkeit es zu implementieren. Aber Du solltest nochmal die Komplexität Deines Algorithmus überprüfen. Da muss ein Denkfehler sein. Das Rabin-Verfahren ist für genügen kleine Primzahlen mit genügen Rechenpauer auf jeden Fall knackbar. Wenn man die Primzahlen aber nur ein klein wenig größer wird, wird der Algorithmus leicht ins Unermessliche rechnen. Vielleicht als Prüfanregung: welche Komplexität hat Deine ggT-Funktion? Welche der chinesische Restsatz? Wie gesagt, ich habe mir aus Zeitmangel Dein Programm nicht genauer ansehen können. Ich werde die Änderungen im Artikel so lange mal rückgängig machen, eh der CIA einen Job angeboten hat. :-) Stern 20:43, 28. Jun 2004 (CEST)

@Arbol01 In deinen drei Beispielen liegen die beiden Primfaktoren nahe (plus/minus 10) der Wurzel (7*11) und (23*31) und (9999971 * 9999991). Da du geeignete Programme ja offenbar vorliegen hast: Erzeuge dir die beiden Primzahlen so, dass sie etwa 2 Größenordnungen auseinanderliegen. Fang mit 3 und 5 stellig (ergibt 8-9 stelligen Ö-Schlüssel) an, und miss die Zeit die dein Knackprogramm benötigt. Mach dann mit 4 und 6 Stellen weiter, 5 und 7 usw. Dein Programm wird vermutlich von Schritt zu Schritt jeweils die zehnfache Zeit benötigen. Dann kannst du hochrechnen, ab wieviel Stellen es für einen Angreifer uninteressant wird, es überhaupt zu versuchen. Rat 21:09, 28. Jun 2004 (CEST)

Hallo Rat (und Stern),

es ist mir in zwischenzeit schon aufgefallen. Das Problem läßt sich nämlich auf k₂ reduzieren. Denn die Rechnung ist nichts anderes als a² - n = b², so das n = a² - b², und damit n = (a+b)*(a-b). Und (a+b) und (a-b) sind nichts anderes als p und q. Und ja, je dichter p und p beieinander liegen, desto leichter kann man mit dem Verfahren des quadratischen Rest, denn nichts anderes ist es ja, die Zahl n faktorisieren. Das ist bei dem Rabin-Verfahren so, wie auch bei RSA. Nur bei Rabin wurde es richtig deutlich. Es wird keinen Edit-War geben. --Arbol01 22:23, 28. Jun 2004 (CEST)

Natürlich nicht. Wir wollen doch alle das gute im Artikel. Ich bin halt doch sehr skeptisch gewesen, da ich mich nun in letzter Zeit so intensiv mit dem Verfahren befasst habe. Wenn dann plötzlich jemand nach Jahrhunderten Faktorisieren kann, geht man erstmal davon aus, dass das sicher nicht gehen kann und derjenige sich vertan haben muss. So eine Skepsis hat noch lange nichts mit Editwar zu tun. Andersherum auch nicht, wenn jemand seine gute Idee in einen Artikel einbauen möchte. Stern 22:28, 28. Jun 2004 (CEST)

Dann sind wir uns ja einig, wie schön :-) Dein Faktorisierungsverfahren entspricht der Faktorisierungsmethode von Fermat, an dem Artikel hast du ja auch mitgeschrieben. Rat 23:27, 28. Jun 2004 (CEST)

Nicht ganz. Letzlich duerfte schon die Erweiterung zum quadratischen Sieb dahinter stecken. Aber der Fall n = a² - b² ist Fermat.

Da es aber ausreichen wuerde, ein n*c = a² - b² zu finden, so das n*c = (a+b)*(a-b) die es gilt herraus zu sieben, und fuer die es reicht, das a² mod n = b² (also eine Quadratzahl) ist, kann man vom quadratischen Sieb sprechen. Das klaere ich als naechstes ab. Ansonsten folgt (aud der Diskussionsseite):

Sicherheit Teil 2

Fuer den Moment, aber nicht fuer immer, ist sind Rabin-Verfahren und RSA aus dem Schneider. Aber nicht fuer immer, denn:

• c = [k₁ k₂ k₃ k₄]

c ist der gemeinsame quadratische Rest, der bei dem Quadrieren jeder der Klartext-Zahlen k₁ bis k₄ entsteht.

c = k₁² mod n = k₂² mod n = k₃² mod n = k₄² mod n

k₁ bis k₄ stehen dabei in einer bestimmten Beziehung:

k₂ - k₁ = k₄ - k₃ = x₁

k₃ - k₁ = k₄ - k₂ = x₂

x₁ und x₂ enthalten nun jeweils p bzw. q als Faktoren, nicht aber beide Faktoren zusammen. Selbst wenn eine Faktorisierung von x₁ und x₂ zu schwierig sein sollte, ist es doch einfach, über den Euklidschen Algorithmus den ggT von n und x₁ bzw. den ggT von n und x₂ zu bestimmen. Damit besitzt man die beiden Bestandteile p und q des geheimen Schlüssels.

Sorry, aber ihr sollte besser die Bezeichnungen aus dem Artikel verwenden, so dass die Sache hier noch nachvollziehbar ist. Dort ist der Klartext mit m und nicht mit k bezeichnet, bzw die mittels p,q berechnet Lösung (mögliche Werte für m) heißen dort +/-r und +/-s. Die Primzahl p (nicht jedoch q) ist Teiler von (r+s) und q (nicht jedoch p) ist Teiler von (r-s). Dies ist aus den im Artikel angegeben Formeln leicht ersichtlich. Damit ist jedoch die Berechnung von p,q ein Kinderspiel, da p=ggT(r+s,n) und q=ggT(r-s,n). Die Berechnung des ggT erfordert maximal ein paar Millisekunden. Daher darf offensichtlich nur einer der Werte s,r bekannt gegeben werden. Ob das Verfahren unter dieser Voraussetzung dann sicher ist, vermag ich nicht zu beurteilen. Tatsache ist, dass nur einer der "Wurzeln" bekannt sein darf, weil sonst p,q sofort berechenbar sind. Die Behauptung, die Sicherheit des Rabin-Verfahrens sei mit der Schwierigkeit der Bestimmung der Primfaktorzerlegung quasi äquivalent, kann damit wohl als abwegig bezeichnet werden. Benutzer:Fsswsb 24.05.06

gilt immer noch, und es ist eine Statistische Frage, je ein (k₁ bzw. k₄) und ein (k₂² bzw. k₃²) zu finden, um ein Quadrupel zu finden, um n zu knacken.

• Reicht es ebenfalls ein a zu finden, fuer das gilt a² mod n = b², so das gilt c*n = a² - b².

Auch das ist eine statistische Frage.

und zuletzt noch eines

• Wenn ich aus a² mod n = b² p und q berechnen kann, warum soll man nicht einen Weg finden, aus a² mod n = b mit (b ist kein Quadrat) p und q zu ermitteln.

Fazit: Zwei Statistische Probleme und eine Tueftelei --Arbol01 10:27, 29. Jun 2004 (CEST)

Wie gesagt: Es lässt sich zeigen, dass Rabin und das Faktorisierungsproblem kongruent sind. Wenn Du eine Möglichkeit zur Faktorisierung gefunden hast, dann kannst Du Rabin brechen. Dies Versuchen Mathematiker schon seit Jahrhunderten. Ich lobe Deine kritischen Fragen, aber gerade RSA wird in der Realität vielfach eingesetzt, weil es als kaum zu brechen gilt. AUs Zeitmangel kann ich Deine Ideen leider nicht prüfen, aber behalte immer im Auge, dass in der Kryptologie sehr viel geforscht wird. Das soll jetzt wieder nicht heißen, dass Du Unrecht hast, aber wie gesagt, der Fachwelt ist momentan bei Rabin nur eine Schwäche wegen des Angriff mit bekanntem Geheimschlüssel bekannt. Faktorisieren kann sie nicht. Stern 10:35, 29. Jun 2004 (CEST)

Auch das Finden der Faktoren von großen zusammengesetzten Zahlen ist letzten Endes nur Statistik. Findet man zufällig einen passenden Faktor, kann man durch Multiplikation leicht prüfen, ob es der richtige ist. Wenn man zum systematischen Durchprobieren aller Kandidaten 10^100 Jahre braucht, ist das auch mit der Statistik so eine Sache. Im Schnitt wird man nach der halben Zeit fündig, mit 5*10^99 immer noch ziemlich lange. Dass es keinen einfachen Weg zur Faktorisierung großer Zahlen gibt, ist nicht bewiesen. Man hat nur noch keinen gefunden, obwohl man seit langem danach sucht. Quantencomputer, wenn es sie denn bereits gäbe, sind in der Lage große Zahlen zu faktorisieren, daher ist man fieberhaft auf der Suche nach praktikablen Alternativen zu RSA, Rabin, ElGamal etc. --Rat 23:29, 29. Jun 2004 (CEST)

Beweisbare Sicherheit

Vielleicht sollte etwas früher erwähnt werden, dass nicht die Sicherheit beweisbar ist, sondern lediglich die Äquivalenz Rabin mit Schlüssel n knacken <=> Faktorisieren von n
Da die praktische Unmöglichkeit des Faktorisierens großer Zahlen zwar vermutet wird (mit gutem Grund) aber nicht bewiesen ist, ist das Rabin Verfahren "nur" genauso sicher, wie die Geheimhaltung der Faktoren von n. Sorgt man für die Eindeutigkeit der passenden Quadratwurzel, spielt man an den Voraussetzungen herum, so dass die Äquivalenz nicht mehr gilt. Es könnte sein, dass man sich damit irgendwo versehentlich ein Türchen öffnet, dass den Klartext offenbart, ohne dass man die Faktoren kennt. Welches Türchen das sein könnte, weiß niemand bzw. er sagt es nicht. Übrigens kann man das Verfahren auch gegen Chosen-Ciphertext Attacken sicher machen, aber eben auch nur unter Veränderung der Voraussetzungen, so dass die Äquivalenz flöten geht. Das Stichwort lautet OAEP (Optimal Asymmetric Encryption Padding). Ob sowas allerdings noch ins Wiki gehört? --Rat 00:08, 30. Jun 2004 (CEST)

Kongruenzbedingung

Die genannte Kongruenzbedingung ist lediglich notwendig, um die Entschlüsselung erheblich zu vereinfachen. (Dann sind die Quadratwurzeln mit wenigen Rechenoperationen zu ermitteln). Ich würde den Absatz daher hinter "Entschlüsseln" als Zusatzinformation stellen --00:08, 30. Jun 2004 (CEST)

Legendre-Symbol

$\left({\frac {-1}{n}}\right)=-1$ oder anders geschrieben:

$\left({\frac {n-1}{n}}\right)=n-1$ trifft dann zu, wenn $n\equiv 3\,{\bmod {\,}}4$ zutrifft, und umgekehrt. Anders ausgrdrückt: beide Ausdrücke sind gleichwertig.

Wenn die Kongruenz die Entschlüsselung vereinfacht, dann sollte vielleicht erklärt werden, in welcher Weise die Kongruenz die entschlüsselung vereinfacht.

Für 7 gilt: $(7-1)^{\frac {7-1}{2}}\equiv (7-1)\,{\bmod {\,}}7$

und für 11 gilt: $(11-1)^{\frac {11-1}{2}}\equiv (11-1)\,{\bmod {\,}}11$

--Arbol01 02:22, 9. Jul 2004 (CEST)

Nachtrag: Ich bin nicht sicher, aber daraus könnte folgen, das wenn $n\equiv 3\,{\bmod {\,}}4$ zutrifft, und daraus :$\left({\frac {n-1}{n}}\right)=n-1$ folgt, es zutrifft, das es kein m gibt, so das (n-1)+(n*m) eine Quadratzahl ergibt.

Folge für 6+(7*m):

6 13 20 27 34 41 48 55 62 69 76 83 90 97 104 111 118 125 132 139 146 ...

Folge für 10+(11*m):

10 21 32 43 54 65 76 87 98 109 120 131 142 153 164 175 186 197 ...

Gegenprobe:

Folge für 4+(5*m):

4 9 14 19 24 29 34 39 44 49 54 59 64 69 74 79 84 89 94 99

Ein Haufen von Quadratzahlen: 4, 9, 49, 64, 144, 169

Folge für 12+(13*m):

12 25 38 51 64 77 90 103 116 129 142 155 168 181 194 207 220 233 ...

25, 64, 324 sind Quadratzahlen, die hier hinein passen.

--Arbol01 02:52, 9. Jul 2004 (CEST)

Die Beobachtung ist richtig.
$\left({\frac {n-1}{n}}\right)=-1$ heißt, dass n-1 ein Quadratischer Nichtrest modulo n ist (Definition des Legendre-Symbols). Indem du auf n-1 der Reihe nach alle Vielfachen von n addierst, bewegst du dich gerade im Restklassenring mod n.
Das Legendre Symbol ist (wo es hinpasst) ganz praktisch. Nervig ist nur, dass man immer darauf hinweisen muss, dass man keinen Bruch meint, da hätte sich der Herr Legendre auch eine andere Schreibweise ausdenken können als zwei große Klammern und einen Strich mittendurch. Im Artikel Quadratischer Rest taucht das Legendre-Symbol ohne diesen Hinweis auf. Für den unvorbereiteten Leser ist das unverständlich und die, die das Legendre-Symbol bereits kennen, brauchen den Artikel nicht. --Rat 15:06, 9. Jul 2004 (CEST)

Verschlüsselung des Rabin-Systems

Eigentlich ist die Codierungsfunktion des Rabin-Systems doch $c(x)\equiv x(x+b)\,{\bmod {\,}}n$! Die Decodierungsfunktion ändert sich dann von der einfachen Wurzelberechnung auf $d(y)\equiv {\sqrt {{\frac {b^{2}}{4}}+y}}-{\frac {b}{2}}\,{\bmod {\,}}n$ Im bisherigen Artikel wird die Variante mit b=0 verwendet, das ist aber nur ein Sonderfall. Ich finde in einem Artikel zu dem Kryptosystem sollten schon die Funktionen aus der Originalen Publikation angegeben werden (siehe http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf)

--TheRealEumel 11:48, 25. Jul 2006

Fehler im Abschnitt "Verschlüsselung"

In dem Abschnitt steht: "Jeder quadratische Rest c hat genau vier verschiedene Quadratwurzeln modulo n = pq." Das ist i.A. falsch, denn: sei p=3,q=7, d.h. n=21 (beachte: 7=3 mod 4). Dann hat z.B. die [7] die genau die Wurzeln [7] und [14]. (da 0=7 mod 7, insb. also m_q = 0 (Def. von m_q siehe Abschnitt "Entschlüsselung")).79.225.247.185 12:59, 2. Apr. 2009 (CEST)