Facharbeit RSA KNACKER

[sape]

BlackJack:

Also ich habe nicht studiert und kann das daher nicht beurteilen, aber ich finde die Aufgab recht schwer (OK, wenn die das Thema schon behandelt habe ist es natürlich kein Problem ). Wüsste spontan nicht wie man das Lössen soll. Darüberhinaus finde ich das recht eigenartig das er sowas in Python programmieren soll, obwohl die Python angeblich nicht im unterricht durch genommen haben bzw. nur kurz vom Lehrer vorgestellt bekommen haben. Ein Lehrer kann doch nicht ernsthaft von mir erwarten, dass ich nun mal eben schnell z.B. in Java (Das Wir bisher nicht im Unterricht durchgenommen haben!) einen "RSA-Knacker" schreibe :stupid:

Oder ist das neuerdings Mode auf den Schulen, das man eine Facharbeit mit Werkzeugen machen muss die man nicht kennt? 0o

...

SWNoIGRlbmtlIGRpZSBoYWJlbiBQeXRob24gc2Nob24gZHVyY2hnZW5vbW1lbiwgYmxvw58gZXIg
d2FyIHp1IEZhdWxlIHp1bSBsZXJuZW4gdW5kIGhhdCBhdWNoIG5pY2h0IGF1ZmdlcGFzc3QgOykg
Ck51biB3aWxsIGVyIHZvbiB1bnMgZGFzIHdpciBzZWluZSBIYXVzYXVmZ2FiZW4gbWFjaGVuIDsp

[Dill]

um die primzahlen zu suchen bietet sich der miller rabin test an.
http://de.wikipedia.org/wiki/Miller-Rabin-Test

google mal danach, dann findest du bessere erklärungen, diese ist evtl etwas schwer verdaulich.

[CM]

Hoi,

na, jetzt ist dieser Thread schon dermaßen off-topic, da macht das auch nichts mehr:
Ich könnte an dieser Stelle folgendes Buch von Simon Singh empfehlen & : The Code Book: How to Make It, Break It, Hack It, Crack It - einfach, verständlich, schön geschrieben (vielleicht gibt es auch eine Deutsche Version?). Das bietet sicher zumindest mal einen guten Einstieg ins Thema und ist auch nicht über Abiturniveau (aber was weiß ich davon schon ). Es gibt aber auch noch einen Haufen anderer Trivialliteratur zum Thema.

Ansonsten kann ich mich der anfänglichen Kritik nur anschließen und angesichts der Threadverlaufs empfehlen, daß bunower mit spezifischen, pythonorientierten Problemen neue Threads eröffnet oder hier zumindest Pseudocode aus der Tasche zaubert - vielleicht sogar noch unter Beherzigung des Links von N317V oder unseres Eingangsthreads.

Besten Gruß,
Christian

[Dill]

MR macht natürlich nur sinn wenn die primzahlen einigermassen gross sind...

[BlackJack]

Also ich habe nicht studiert und kann das daher nicht beurteilen, aber ich finde die Aufgab recht schwer (OK, wenn die das Thema schon behandelt habe ist es natürlich kein Problem ). Wüsste spontan nicht wie man das Lössen soll.

Arbeiten für die man mehrere Monate Zeit zum lösen bekommt, sind meistens nicht spontan lösbar.

Ein Lehrer kann doch nicht ernsthaft von mir erwarten, dass ich nun mal eben schnell z.B. in Java (Das Wir bisher nicht im Unterricht durchgenommen haben!) einen "RSA-Knacker" schreibe :stupid:

Wenn die Grundlagen der Programmierung, also Variablen, Funktionen, Schleifen etc. schon in einer anderen Sprache erklärt wurden, dann denke ich schon das ein Lehrer so etwas erwarten kann. Zumal Python recht einfach erlernbar sein sollte wenn man diese Grundlagen schon in Java gelernt hat.

Dem Lösungsansatz hat er selbst hier schon gepostet und in zwei Monaten ist das auf jeden Fall schaffbar.

Oder ist das neuerdings Mode auf den Schulen, das man eine Facharbeit mit Werkzeugen machen muss die man nicht kennt?

Von Schülern zu erwarten, dass sie sich selbständig in ein Thema einarbeiten ist schon ein Unding, stimmt. Der Lehrer soll gefälligst alles vorkauen und den armen Schülern das Denken abnehmen. Sonst überhitzen die und laufen Amok und den schwarzen Peter bekommen wieder die "Killerspiele" zugeschoben.

[sape]

Von Schülern zu erwarten, dass sie sich selbständig in ein Thema einarbeiten ist schon ein Unding, stimmt. Der Lehrer soll gefälligst alles vorkauen und den armen Schülern das Denken abnehmen. Sonst überhitzen die und laufen Amok und den schwarzen Peter bekommen wieder die "Killerspiele" zugeschoben.

OK, schön Gut, dann will ich das du mir innerhalb von 6 Monaten einen LALR(1)-Parser in einer Programmiersprache schreibst die du nicht kennst Oder von mir aus auch eine LR-Parser innerhalb von 3 Monaten. Wie das geht weist du ja bereits.

Jetzt mal ernsthaft: Das ist wirklich so das man auch mal eine Facharbeit kriegt die zur Aufgabe hat, dass man eine komplexe Arbeit abliefern muss in einer Programmiersprache, die man bisher nicht im Unterricht behandelt hat? Nicht euer ernst oder?

[sape]

[...]

Oder ist das neuerdings Mode auf den Schulen, das man eine Facharbeit mit Werkzeugen machen muss die man nicht kennt?

Von Schülern zu erwarten, dass sie sich selbständig in ein Thema einarbeiten ist schon ein Unding, stimmt. Der Lehrer soll gefälligst alles vorkauen und den armen Schülern das Denken abnehmen. Sonst überhitzen die und laufen Amok und den schwarzen Peter bekommen wieder die "Killerspiele" zugeschoben.

Jack, kannst du mir bitte ein gefallen tun. Kannst du das in dem Zitat-thread Wiki schreiben den Leo angelegt hat? Das Zitat ist echt Geil! ROFL xD

lg

EDIT: [wiki]Forum/Zitate[/wiki]

[BlackJack]

Von Schülern zu erwarten, dass sie sich selbständig in ein Thema einarbeiten ist schon ein Unding, stimmt. [...]

OK, schön Gut, dann will ich das du mir innerhalb von 6 Monaten einen LALR(1)-Parser in einer Programmiersprache schreibst die du nicht kennst

Wie das geht weiss ich theoretisch, ich weiss auch das die kompliziert genug sind, dass man dafür für gewöhnlich einen Parsergenerator benutzt. Wenn es also so einen für die Sprache gibt.

Oder von mir aus auch eine LR-Parser innerhalb von 3 Monaten. Wie das geht weist du ja bereits.

LR-Parser in drei Monaten ist okay.

Jetzt mal ernsthaft: Das ist wirklich so das man auch mal eine Facharbeit kriegt die zur Aufgabe hat, dass man eine komplexe Arbeit abliefern muss in einer Programmiersprache, die man bisher nicht im Unterricht behandelt hat? Nicht euer ernst oder?

Ganz ernst: Ich denke das ist realistisch. Wenn man die Grundlagen der Programmierung drauf hat, kann man sich in Python in einem Monat einarbeiten. Für die RSA-Aufgabe braucht man da auch gar nicht viel. Nur ein paar Funktionen; noch nicht einmal Klassen. Ist ja nicht so das er C++ oder Haskell nehmen soll.

Die andere Seite der Aufgabe ist die Mathematik die dahinter steht. Beispiele für RSA mit kleinen Zahlen findet man im Netz und dann braucht man noch eine Methode um Primzahlen zu finden. Das Sieb von Eratosthenes wurde schon erwähnt. Da findet man auch Pseudocode zu Hauf. Wenn man die Lösung des Problems erst in Worten und dann in Pseudocode aufschreibt, dürfte man schon fast ein Python-Programm haben. Für Probleme und Detailfragen gibt's dann Foren wie dieses hier.

In der Uni wird so etwas ständig verlangt. Ausser der ersten Sprache, Haskell, haben wie in der Uni nie wieder eine Sprache im "Unterricht" gelernt. Java, als "universelle" Sprache nach Haskell, C und Makefiles für "Betriebssysteme", PHP für's Projekt in "Einführung in Datenbanksysteme" -- da wurde jeweils erwartet das man sich selbst in die Sprachen einarbeitet.

[sape]

Das mit dem Parser war nur ein Scherz

[...]
In der Uni wird so etwas ständig verlangt. Ausser der ersten Sprache, Haskell, haben wie in der Uni nie wieder eine Sprache im "Unterricht" gelernt. Java, als "universelle" Sprache nach Haskell, C und Makefiles für "Betriebssysteme", PHP für's Projekt in "Einführung in Datenbanksysteme" -- da wurde jeweils erwartet das man sich selbst in die Sprachen einarbeitet.

Oh, ok. Das wusste ich nicht. Schon ein wenig Krass, da man da ja auch kein Lerer hat der eine zu Stil Fragen und sonstiges beraten kann. Wird wohl kaum ein Lehrer bereit sein nach Unterricht sich noch mit einem Schüler über Sprache X zu unterhalten.

EDIT: Nicht das Zitat vergessen Jack

[Daria]

Hmm, ich hab noch gar nichts mit Python gemacht.
Aber ich will mit Python was für meine Facharbeit in Mathe programmieren.
Mir fehlt im Grunde noch das Thema. Also ich darf mir das selber aussuchen.
Das hier würde mich zwar interessieren, aber ich bezweifle, dass ich das in anderthalb Monaten schaffe und wahrscheinlich is der Mathe-Anteil daran zu gering.

Was könntet ihr mir denn eventuell für ein Thema empfehlen?

[bunower]

ok ich hab das mal durchgelesen was ihr inzwischen geschrieben habt.
als erstes möchte ich klar stellen ich möchte mich weder wichtig stellen noch möchte ich das jemand meine aufgaben erledigt.
in diesem thread ging es nur darum mir einen tipp zu geben wie ich anfangen soll.

ich weiss nicht ob jemand von euch abitur gemacht hat, aber facharbeiten ersetzen eine klausur und klausuren gehen 50% in die noten ein.
es ist immer so das man eine komplexe aufgaben für die facharbeit bekommt.
es könnte auch etwas in geschichte oder deutsch (dann hätte ich ein buch lesen müssen was vielleicht 400seiten oder mehr hat)sein dann wäre es vielleicht einfacher, aber da ich informatik als abi fach habe und wel seit 2 hier in nrw zentralabitur gemacht wird, ist es vorgeschrieben was man im unterricht alles so behandeln muss, und python ist auch dabei.

wie schon vorher gesagt habe will ich keine 1000 stellige zahlen knacken es geht auch wenn ich 4 stellige zahlen knacke, nur ich muss dem lehrer vorzeigen was ich gemacht und das ich pyhon etwas verstanden habe.
ich entschuldige mich einfach bei denen ich so unfreundlich war und oder die mich falsch verstanden haben.
inzwischen arbeite ich mich durch paar tutorials durch

[CM]

ich entschuldige mich einfach bei denen ich so unfreundlich war und oder die mich falsch verstanden haben.
inzwischen arbeite ich mich durch paar tutorials durch

Gute Einstellung - laß Dich vom manchmal rauhen Ton hier nicht abschrecken und komm wieder.

Gruß,
Christian

[Sr4l]

und ich habe es mal gecodet cracker und nun bin ich an nem key ersteller um mal zuschauen bis zu welcher länge ich es schaffe in einer vernünftigen zeit. und poste mein Werk hab SiebDesEratosthenes und ErweiterterEuklidischerAlgorithmus zur Hilfe gezogen und in Funktionen gepackt.

[gummibaerchen]

das man eine komplexe aufgaben für die facharbeit bekommt.
es könnte auch etwas in geschichte oder deutsch (dann hätte ich ein buch lesen müssen was vielleicht 400seiten oder mehr hat)sein dann wäre es vielleicht einfacher, aber da ich informatik als abi fach habe und wel seit 2 hier in nrw zentralabitur gemacht wird, ist es vorgeschrieben was man im unterricht alles so behandeln muss, und python ist auch dabei.

Merke: Lasse dir nie etwas von einem Gesamtschüler über Bildung erzählen, schon gar nicht über etwas wie Abitur.

(Ist meine Subjektive Meinung, aber zumindest bei mir in der Stadt sind auf der Gesamtschule 80% Leute mit Hauptschulempfehlung, 18% mit Realschulempfehlung und ganze 2% mit Gymnasialempfehlung. Nicht nur das ich auf Grund persönlicher Erfahrung allgemein nicht mehr viel von der Schulform und den Schülern halte, aber dieser Thread bestätigt mich innerlich wieder einmal.)

Also ich bin mir ziemlich sicher (auch wenn ich jetzt die Oberstufe in Irland besuche und daher nicht mehr aktuell informiert bin, was in Deutschland los ist), dass Python nicht für das Abitur vorgeschrieben ist. Zum Beispiel weiß ich, dass man bei mir am Gymnasium, wo man dann ja auch Zentralabitur schreibt, nur Delphi im Informatikunterricht lernt.

Und was bedeutet "wel seit 2 hier in nrw zentralabitur gemacht wird"? Meines Wissens nach, waren die Leute die ihr Abitur 2006 gemacht haben die letzten ohne Zentralabitur, und ab 2007 wird hier Zentralabitur geschrieben.

PS:
Zum Thema Gesamtschule: Es gibt bestimmt auch positive Ausnahmen, leider sind mir diese noch nicht begegnet

[Luzandro]

na, jetzt ist dieser Thread schon dermaßen off-topic, da macht das auch nichts mehr:
Ich könnte an dieser Stelle folgendes Buch von Simon Singh empfehlen & : The Code Book: How to Make It, Break It, Hack It, Crack It - einfach, verständlich, schön geschrieben (vielleicht gibt es auch eine Deutsche Version?).

Diesen Untertitel kenn ich zwar nicht, aber ich nehme an die dt. Version ist "Geheime Botschaften". Kann mich dieser Empfehlung nur anschließen - sehr unterhaltsam und spannend geschrieben..

Hmm, ich hab noch gar nichts mit Python gemacht.
Aber ich will mit Python was für meine Facharbeit in Mathe programmieren.
Mir fehlt im Grunde noch das Thema. Also ich darf mir das selber aussuchen.
Das hier würde mich zwar interessieren, aber ich bezweifle, dass ich das in anderthalb Monaten schaffe und wahrscheinlich is der Mathe-Anteil daran zu gering.

Das mit den 1 1/2 Monaten kann ich nicht beurteilen - was den Mathe-Anteil angeht, hängt das Thema mit Faktorisierung, (Peudo-) Primzahlen bzw. Primzahlentests, Einwegfunktionen, inversen Moduloberechnung und bekannten Algorithmen zu diesen Problemen zusammen, also sollte sich schon etwas Stoff finden lassen.

und ich habe es mal gecodet cracker und nun bin ich an nem key ersteller um mal zuschauen bis zu welcher länge ich es schaffe in einer vernünftigen zeit. und poste mein Werk hab SiebDesEratosthenes und ErweiterterEuklidischerAlgorithmus zur Hilfe gezogen und in Funktionen gepackt.

Wie war das mit dem Deutsch? Das Problem am Sieb des Erastosthenes ist, dass du dafür immer ALLE vorherigen Primzahlen berechnen und dir diese merken musst - bei größeren Zahlen ist dann wohl sowas wie Pollard-Rho sinnvoller (für die hier genannten Werte uninteressant, aber du willst ja anscheinend auch mehr austesten). Im übrigen müssten die Zahlen AFAIR nicht wirklich zwingend Prim sein und es reicht, wenn sie teilerfremd sind (bzw. kann man bei entspr. hohen Werten eben auch kaum mit Sicherheit sagen, ob es sich um eine Primzahl handelt)
Mit dem Posten würde ich übrigens noch warten - ich bezweifle, dass du bunower damit wirklich einen Gefallen tust, wenn er bevor er wirklich damit anfängt schon eine komplette Lösung vor sich hat.

[merlin_emrys]

Merke: Lasse dir nie etwas von einem Gesamtschüler über Bildung erzählen, schon gar nicht über etwas wie Abitur.

Irgendwie teile ich dies Vorurteil...
Ernsthaft, wer in der 12. Klasse noch nicht automatisch orthographisch und grammatisch korrekte Saetze auf die Reihe bringt, sollte sich das mit dem Abitur nochmal durch den Kopf gehen lassen.

Und was bedeutet "wel seit 2 hier in nrw zentralabitur gemacht wird"? Meines Wissens nach, waren die Leute die ihr Abitur 2006 gemacht haben die letzten ohne Zentralabitur, und ab 2007 wird hier Zentralabitur geschrieben.

Ich tippe auf etwas in der Art: "Wir sind der zweite Jahrgang nordrhein-westfaelischer Schueler, der Zentralabitur machen wird."

P.S. @ Daria: Siehe PN

[Bernhard]

@Daria:

Hallo! Es ist wahrscheinlich keine gute Idee, auf Seite 4 eines Threads, der schon weit off topic geraten ist und wahrscheinlich von vielen bereits als "Unsinn, muss ich nicht weiter lesen" klassifiziert wurde, eine ganz neue Frage zu stellen. Auch wenn sonst Doppelpostings unerwünscht sind: In diesem Fall solltest Du einen neuen Thread mit Deiner Frage aufmachen.

@alle:

Wo kommt denn jetzt auf einmal dieser Gesamtschulenquatsch her? Warum soll ich mir von Gesamtschülern nichts über Bildung erzählen lassen? Und warum sind die Herren sich eigentlich so sicher, dass Abitur und Bildung sehr viel miteinander zu tun haben? Sorry, dafür kenne ich in beiden Richtungen zu viele Gegenbeispiele: Sowohl Abiturienten die grenzdebil doof sind als auch sehr gebildete Nicht-Abiturienten.
(Ja, ich selbst habe Abitur und zwar mit sehr gut, ein Studium an einer Universität und einen Doktortitel und ich verdiene auch mein Geld in meinem studierten Fach. Nein, ich habe keinen Sozialneid auf Abiturienten oder Gymnasiasten, die es werden wollen.)

@ Luzandro (und back to topic):

> Das Problem am Sieb des Erastosthenes ist, dass du dafür immer ALLE vorherigen
> Primzahlen berechnen und dir diese merken musst
Das ist aber doch kein Problem, sondern gut: Wenn ich keine RSA-Schlüssel erstellen, sondern welche cracken will, muss ich doch eine Primfaktorenzerlegung machen. Da brauche ich doch dann alle Primzahlen, oder nicht?

@ bunower

> ich weiss nicht ob jemand von euch abitur gemacht hat

Ja, hat jemand. In Zeiten, in denen in Großstädten fast jeder zweite Schulabsolvent mit Abitur aus der Schule geht, und in einem Forum, in dem sich Leute in ihrer Freizeit mit mathematisch-informatischen Problemen beschäftigen ist das auch sehr wahrscheinlich.

> in diesem thread ging es nur darum mir einen tipp
> zu geben wie ich anfangen soll

Das ist ja auch erfolgt. Damit hat der Thread dann ja seinen Sinn erfüllt!


Gruß an alle,
Bernhard

EDIT: Wenn das hier später mal jemand lesen sollte: Daria hat das dann hier getan: http://www.python-forum.de/topic-8773.html

[Luzandro]

> Das Problem am Sieb des Erastosthenes ist, dass du dafür immer ALLE vorherigen
> Primzahlen berechnen und dir diese merken musst
Das ist aber doch kein Problem, sondern gut: Wenn ich keine RSA-Schlüssel erstellen, sondern welche cracken will, muss ich doch eine Primfaktorenzerlegung machen. Da brauche ich doch dann alle Primzahlen, oder nicht?

Jein - bei verhältnismäßig "kleinen" Zahlen ist das natürlich eine naheliegende und sinnvolle Methode, aber bei großen Zahlen müsstest du verdammt viel speichern und durchprobieren, da sind dann randomisierte Algorithmen effizienter

http://de.wikipedia.org/wiki/Faktorisierungsverfahren

[merlin_emrys]

Und warum sind die Herren sich eigentlich so sicher, dass Abitur und Bildung sehr viel miteinander zu tun haben? Sorry, dafür kenne ich in beiden Richtungen zu viele Gegenbeispiele: Sowohl Abiturienten die grenzdebil doof sind als auch sehr gebildete Nicht-Abiturienten.

Verd*... und ich dachte echt, irgendwann sei das Abitur mal als so etwas wie das Signum einer erfolgreich erfolgten (Aus-)Bildung angesehen worden (was die Existenz hochgebildeter Nicht-Abiturienten ja überhaupt nicht ausschliesst; immerhin ist es ein mehr oder minder rein deutsches Phänomen, wohingegen die Deutschen die Bildung bekanntlich nicht für sich gepachtet haben). Ist echt an mir vorbeigegangen, dass das inzwischen gar nichts mehr miteinander zu tun hat... Erklaert mir aber zumindest, wieso ich bisher der Ansicht war, das System sei ursprünglich mal so angelegt gewesen, dass es eben keine "grenzdebil doofen Abiturienten" geben sollte. Ich bin halt doch nur noch ein Relikt vergangener Zeiten...

[Bernhard]

@Luzandro
Danke für den spannenden Link!