DeFacto: Primfaktorzerlegung

Knacken von Verschlüsselungen bei den Projekten RC5-72, RSAttack und anderen

Unread postby test123 » 26.02.2008 21:49

Ja, dieser cyrix42 bin ich.

Wenn du wissen willst, warum ich bei WuMV gesperrt wurde, dann solltest du dir dieses Form mal genau anschauen. Ich wurde gesperrt, weil ich RT-"Kritikern", die sich selbst als Laien outen, empfohlen habe ersteinmal die nötige PPhysik und Mathematik zu lernen um zu verstehen, was sie da eigentlich tun... Credo: Nur was du verstanden hast, kannst du auch widerlegen. Frau J.Lopez und Co. begehn nämlich jede Menge logischer Fehler, aber gut. Kritik ist bei dieser Gemeinschaft offenbar unerwünscht, sollte sie von der vorherrschenden Meinung dort Abweichen. Ich verweise mal auf das Forum AlphaCentauri, dort erfährt man weiteres über WumV...

zum Inhalt hier:

Leider reicht der Platz im Gästebuch nicht aus eine ordentliche Analyse zu machen. Aber das sollte man tun, bevor man das Projekt groß feiert, denn es ist nichts weiter als ein naiver Versuch. :)

Das kann man Schülern auch nicht vorwerfen, aber die Rechenzeit ist dort einfach nur verschwendet...

Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby test123 » 26.02.2008 21:57

Und jetzt mal ernsthaft:

Also: Was dort beschrieben wird, ist i.W. ein zufälliges Raten der einzelnen Bits der Faktoren, und ein Testen, ob die beiden zufällig gewählten Faktoren denn Passen. Dazu werden zuerst immer die letzten Bits betrachtet und das ganze dann "von niedrigen zu hohen Bits" hochgezogen.

Pro Bit gibt es nach deren Argumentation zwei Möglichkeiten. Gelangt man in eine "Sackgasse", so muss nach Back-Tracking in der vorhergehenden Stufe das Bit geändert werden. Geht das nicht, so in der vorvorgehenden, usw. Wir landen also in einem binären Suchbaum der Tiefe log(n) (um genau zu sein: log_2(sqrt(n)), was aber auf das gleiche Hinausläuft), und müssen potentiell alle Knoten chekcen. (Im Erwartungswert immernoch die Hälfte, was für die Zeitkomplexität keine Rolle spielt). Damit fallen schonmal O(sqrt(n)) zu überprüfende Knoten an.

In jedem dieser Knoten sind aber noch einmal O(log(n)) Operationen durchzuführen, sodass wir insgesamt auf eine Komplexität von O(log(n)sqrt(n)) in der zu faktorisierenden Zahl[!] n kommen. Man gibt im normalfall aber die Komplexität in Abhängigkeit der Eingabelänge an, sodass wir auf ziemlich exponentielles Verhalten kommen!


Zum Vergleich: Probedivision läuft auch in O(sqrt(n))...

Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby test123 » 26.02.2008 21:58

Anders formuliert: Man kommt durch Raten schneller zum Ziel als durch dieses Programm! Oder wieder anders formuliert: Seinen Rechner darauf anzusetzen ist ungefähr genauso gut wie Geld zu verbrennen... ;)


Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby Myrmidon » 26.02.2008 21:59

test123 wrote:Ja, dieser cyrix42 bin ich.

Das kann man Schülern auch nicht vorwerfen, aber die Rechenzeit ist dort einfach nur verschwendet...

Cyrix


junge interessierte leute brauchen rechenkapazität, rechenkraft.net hat welche. ob deren projekt zum erfolg führt ist erstmal zweitrangig, da es für den verein ja hauptsächlich um die präsenz geht.
PS: das deren algorithmus schlechter ist hab cih mir fast gedacht, da ich die gefundene Priemzahl einmal mit dem tool der seite www.primzahlen.de getestet hatte und einmal mit dernen prog. und rein subjektig war das programm der beiden wesentlich langsamer.
Image

Image
User avatar
Myrmidon
Brain-Bug
Brain-Bug
 
Posts: 542
Joined: 04.10.2007 17:55

Unread postby yoyo » 26.02.2008 22:01

Hallo,
um ehrlich zu sein kann ich mir auch nicht vorstellen dass 2 Schüler die Faktorisierung beschleunigen, einen besseren Algorythmus finden als bisherige Mathematiker. Aber es könnte ja passieren. Aber dafür gibts ja auch die JugendForscht Gremien, die das besser analysieren können als ich. Auch weiß ich nicht genau was denn nun konkret das Forschungsobjekt ist, nur der Algorythmus oder auch die verteilte Rechenumgebung oder beides oder noch was anderes. Daher werde ich das Projekt zumindest erstmal bis zum nächsten JugendForscht Meilenstein weiter unterstützen.

Du könntest den Algorythmus, den sie verwenden und die die "besser" sind ja mal versuchen für mich Laien zu erläutern.

yoyo

PS: Herzlich Willkommen hier bei uns!!
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Image Image
User avatar
yoyo
Vereinsvorstand
Vereinsvorstand
 
Posts: 7678
Joined: 17.12.2002 14:09
Location: Berlin

Unread postby test123 » 26.02.2008 22:02

Nun, die Schüler sollten wenigstens etwas sinnvolles mit der Rechenkraft, die ihnen hier zur Verfügung gestellt wird machen!

Ansonsten ist dies nur ein "wir Heizen unseren Raum jetzt mal nicht mit der Heizung sondern mit Prozessoren-Abwärme". Leider passiert hier nicht mehr!
Nochmal: Sogar der völlig naive Ansatz ist besser als das dort vorgestellte Programm!


Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby test123 » 26.02.2008 22:05

Hallo yoyo!

Die Mathematik hinter aktuellen Verfahren ist nicht trivial (eigentlich wollte ich an der Schiene promovieren, klappt jetzt nicht, aber gut).

Wie gesagt: Was die Schüler hier machen ist verklausuliert folgendes:

Wenn ich eine gegebene Zahl n in ein Produkt a*b zerlegen will, dann kann ich das versuchen so zu machen: Ich rate a und b, berechne das Produkt, und schaue nach, ob n herausgekommen ist. Wenn ja, dann freue ich mich, wenn nein, probiere ich weiter.

(Ein klein wenig intelligenter machen sie es schon, aber das ist etwa das, was da in dem Programm passiert...)


Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby test123 » 26.02.2008 22:09

(Die Leistung der Schüler in dem Projekt ist eben nicht die Faktorisierung, sondern "höchstens" [ohne es klein reden zu wollen] die Architektur der Verteilung der Aufgaben auf verschieden Rechner.)


Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Unread postby Michael H.W. Weber » 26.02.2008 22:11

Ich selbst habe von Mathematik nicht ausreichend Ahnung, um das zu beurteilen. Sollte die Kritik berechtigt sein - und ich habe die beiden DeFacto-Betreiber per eMail über die Einwände informiert mit der Bitte um Stellungnahme - dann ist klar, daß wir hier nicht längerfristig unsere Rechenzeit investieren können, da es sinnvollere Projekte gibt. Was wir aber in jedem Fall tun sollten - sozusagen aus Solidarität - ist eine Unterstützung am 4. März zu gewähren. Wichtig wäre nun zu wissen, wo das Projekt Priorität legt.

Michael.
Last edited by Michael H.W. Weber on 26.02.2008 22:12, edited 1 time in total.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Aktive DC Projekte
http://signature.statseb.fr II: Abgeschlossene DC Projekte

Image Image Image
User avatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
 
Posts: 19983
Joined: 07.01.2002 01:00
Location: Marpurk

schade, dass der Traum so schnell platzt!?

Unread postby EdmundBlackadder » 26.02.2008 22:12

Michael H.W. Weber wrote:
laguna2 wrote:Huh? Laut Taskmanager rechnet er was...
Nur was?

Ja, einfach Hirn ausschalten und rechnen lassen (Hintergrund des Projekts wurde oben ja gepostet).

Michael.

Nun, ohne hier allzu kritisch zu sein, möchte ich anmerken, das das schon naiv ist, in ein Projekt einzusteigen, ohne ansatzweise prüfen zu lassen, ob das einen "Sinn" macht, wie auch immer. Sowas können uns nur EU-weit leisten oder auch in Bayern! Manche rechnen schon lange bei Seti nicht mehr mit und hier wird einfach blind losgeschlagen. Ich hatte gehofft, dass mal irgendwer den Algorithmus anschaut und das auch erklären kann. Vielleicht hätten die 2 vor dem Start entsprechende "Experten" aufsuchen sollen. Wenn das alles stimmt, finde ich es schon merkwürdig, dass der Algorithmus so schlecht sein soll.
Also ich für meinen Teil bleibe noch dabei bis 4.3. Gut, ich kapiere andere Projekte auch nur ansatzweise. Das hält mich aber nicht von DC ab. Ich bin lernwillig, sonst wäre ich nicht hier.

Euer Edmund
Verschenke XP x64 und Vista Business 32/64 bit Lizenzen.
Ritschie wrote:Ich will ja nicht nur für Credits rechnen, sondern 'nen sinnvollen Beitrag leisten.
User avatar
EdmundBlackadder
Task-Killer
Task-Killer
 
Posts: 784
Joined: 20.02.2008 17:56
Location: Prekariat

Unread postby test123 » 26.02.2008 22:15

Hallo!

Nun, wer seinen Rechner wozu benutzt, ist noch seine Sache. Ich wollte nur angeben, dass hier der Stromverbrauch für etwas vollkommen Sinnloses verpulvert wird.

Ihr rechnet, um den zwei Leuten ein gutes Gefühl zu geben, nicht aber, um inhaltlich etwas vorwärts zu bringen...


Grüße,
Cyrix
test123
XBOX360-Installer
XBOX360-Installer
 
Posts: 68
Joined: 26.02.2008 21:45

Re: schade, dass der Traum so schnell platzt!?

Unread postby Michael H.W. Weber » 26.02.2008 22:19

EdmundBlackadder wrote:
Michael H.W. Weber wrote:
laguna2 wrote:Huh? Laut Taskmanager rechnet er was...
Nur was?

Ja, einfach Hirn ausschalten und rechnen lassen (Hintergrund des Projekts wurde oben ja gepostet).

Michael.

Nun, ohne hier allzu kritisch zu sein, möchte ich anmerken, das das schon naiv ist, in ein Projekt einzusteigen, ohne ansatzweise prüfen zu lassen, ob das einen "Sinn" macht, wie auch immer.

Ja, das ist korrekt, allerdings bringst Du hier mein Posting ziemlich aus dem Zusammenhang. Es bezog sich darauf, daß zum technischen Betrieb des Clients nicht weiter "herumgedoktort" werden muß. Keineswegs ging es um den Inhalt des Projekts. Deswegen hatte ich extra auch nochmal auf die URL mit der Projektbeschreibung hingewiesen, damit jeder vorher dort nachsieht, ob es sinnvoll ist. Und natürlich hatte ich schon erwartet, daß Einwände von unseren mathematisch besser betuchten kommen würden, falls da etwas offensichtlich ungereimt ist. Aber wie gesagt, jetzt stellt sich erst mal die Frage, wo die Priorität bei dem Projekt liegt: Ist es der mathematische Ansatz oder z.B. die Aufgabenverteilung auf verschiedene Rechner.

Michael.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Aktive DC Projekte
http://signature.statseb.fr II: Abgeschlossene DC Projekte

Image Image Image
User avatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
 
Posts: 19983
Joined: 07.01.2002 01:00
Location: Marpurk

PreviousNext

Return to Kryptographie

Who is online

Users browsing this forum: No registered users and 4 guests