Zahlencode bruten

[-=Breeze=-]

Hallo zusammen, :-D
gegeben sei ein verschlüsseltes Passwort. Die Buchstaben werden in Ascii-Code umgewandelt und malgenommen, dann wird geguckt, ob das Ergebnis mit dem richtigen PW-Code übereinstimmt.

Die Lösung: 219235317047744800000
Ich habe herausgefunden, dass das PW genau 10 Zeichen lang sein muss.

Hier meine Frage: Wie finde ich am einfachsten heraus, welche 10 Zahlen (von 97-122) malgenommen 219235317047744800000 ergeben?

Mein bisheriger Code braucht ca. 90 Tage :!: zum Bruten, das ist eindeutig zu lang:

Delphi-Quellcode:

for a:=97 to 122 do
      for b:=97 to 122 do
        for c:=97 to 122 do
          for d:=97 to 122 do
            for e:=97 to 122 do
              for f:=97 to 122 do
                for g:=97 to 122 do
                  for h:=97 to 122 do
                    for i:=97 to 122 do
                      for j:=97 to 122 do
                        if (73046314200000/a/b/c/d/e/f=10000000*g*h*i*j) then <Ausgabe>;

Ich hoffe sehr, dass mir jemand helfen kann :angel: :angel:

[Luckie]

Mir ist nur das Verb brüten geläufig. Aber davon mal abgesehen, schon mal im Forum oder mit Google nach bruteforce gesucht?

[-=Breeze=-]

danke für die schnelle Antwort, das Problem liegt aber daran, dass ich eine Zahlenkombination brute und nicht wie üblich Strings per Bruteforce Methode suche.

[Luckie]

aber du redest die ganze Zeit von, ich kann das Wort gar nicht schreiben :?, bruten. Letztendlich läuft es aber wohl auf eine Art Primfaktorzerlegung hinaus.

[-=Breeze=-]

Wir können es auch 'brüten' nennen. :mrgreen: Das Programm probiert alle möglichen Variationen der Reihe nach durch, bis es eine richtige gefunden hat.
Vermutlich hast du Recht, reines durchlaufen aller Möglichenkeiten dauert einfach zu lange. Werde heute abend mal andere Methoden ausprobieren.

[Laufi]

Hallo!

Du kannst die Gleichung vereinfachen indem du paar Nullen kürzt und alle Variablen auf die rechte Seite nimmst um Divisionen zu vermeiden, denn die sind langsam! Du solltest möglichst nie divisionen verwenden :cry:

Liebe grüsse
Laufi

[Torpedo]

Vielleicht hilft dir das weiter:

Code:

73046314200000 = 64 * 3 * 3125 * 121743857
10000000 = 128 * 78125

[cydo]

[gelöscht] oops. hab mich im zahlenbereich vertan... mal sehen ob mir noch was einfällt

Wenn Deine Formel stimmt 73046314200000/a/b/c/d/e/f, dann heisst das, dass f nur 100 oder 120 sein kann,
da keine andere Zahl im Bereich 97..122 die Zahl 73046314200000 gerade teilt. Jetzt einfach weitermachen....

so, teile ich jetzt durch 120 bleibt 608719285000, welche sich nur durch 100 teilen lässt, usw.

stichwort: backtracking!

achja nochwas: das passwort ist logischerweise NICHT einzigartig.
Bei 2 Stelligen Passwort mit Ergebnis 9312 kann sowohl 96,97 also 97,96 das Ergebnis sein...

[sakura]

Ein einfacher Ansatz: Ganzzahldivision ;) Suche mal nach BigInt, dann findest Du auch Bibliotheken zum Verarbeiten solch großer Zahlen, die selbst Int64 sprengen ;)

...:cat:...

[gammatester]

Zitat:

Zitat von -=Breeze=-

Hallo zusammen, :-D
gegeben sei ein verschlüsseltes Passwort. Die Buchstaben werden in Ascii-Code umgewandelt und malgenommen, dann wird geguckt, ob das Ergebnis mit dem richtigen PW-Code übereinstimmt.

Die Lösung: 219235317047744800000
Ich habe herausgefunden, dass das PW genau 10 Zeichen lang sein muss.

Hier meine Frage: Wie finde ich am einfachsten heraus, welche 10 Zahlen (von 97-122) malgenommen 219235317047744800000 ergeben?

Deine Vermutungen können nicht stimmen, denn die Primfaktorzerlegung lautet:

219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

Gruß Gammatester

[cydo]

also. ich habs mal durchprobiert, aber das kann nicht sein. Bist Du dir mit der Lösungszahl sicher? Und dass der Bereich "a"-"z" ist? Habs auch grad mal mit "A"-"Z" probiert, aber beides mal kein Ergebnis. Bist Du mit dem Verschlüsselungsalgo sicher?

[cydo]

gleich nochmal: also hab alle durchprobiert im ASCII-Bereich 10-250, kein Erfolg. Der Verschlüsselungsalgo ist auch selten dämlich. Als Beispiel verschlüsselt man mal das Wort "delphi" (=1334092032000) ergibt das 1440 andere Worte, die auf das selbe Ergebnis passen (z.B. "dblhex").
Ich glaub Du hast Dich mit dem Algo vertan....

Delphi-Quellcode:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  BigInt in 'BigInt.pas';

var
 loesungs: integer;
 bigint: TBigInt;


function Verschl(input: string): TBigint;
var
  i: integer;
  test: TBigint;
begin
  result := TBigInt.Create(ord(input[1]));
  for I := 2 to length(input) do
  begin
    test := TBigint.Create(ord(input[i]));
    result.mul(test);
    test.free;
  end;
end;


procedure Back(zahl: TBigint;pass: string);
var
  i: integer;
  test: TBigint;
  Divi: TBigint;
begin

  test := TBigInt.Create(1);
  if test.IsEqual(zahl) then
  begin
    writeln('Loesung: '+pass);
    inc(loesungs);
    test.Free;
    exit;
  end;
  test.Free;

  //for I := 10 to 250 do
  for I := 97 to 122 do
  begin
    divi := TBigInt.Create(i);
    test := TBigInt.Create(zahl);
    test.div_(divi);
    test.mul(divi);
    if test.IsEqual(zahl) then
    begin
      test.div_(divi);
      Back(test,pass+chr(i));
    end;
    test.free;
    divi.free;
  end;
end;

begin
  loesungs :=0;
  BigInt := Verschl('delphi');
  //BigInt := TBigInt.Create('219235317047744800000');
  Writeln('Suche Loesung zu ',BigInt.ToString);
  readln;
  Back(Bigint,'');
  writelN('ende');
  writeln(loesungs,' Loesungen');
  readln;
end.

[MrKnogge]

Zitat:

Zitat von cydo

Als Beispiel verschlüsselt man mal das Wort "delphi" (=1334092032000) ergibt das 1440 andere Worte, die auf das selbe Ergebnis passen

Dann ist es keine Verschlüsselung, sondern ein Hash.

[-=Breeze=-]

Großen Dank für die vielen Antworten :-D :dp:

Das eingegebene Passwort wird vor der Rechnung in Kleinbuchstaben umgewandelt, kann daher nur zwischen 97 und 122 liegen, außer vllt Zahlen, die ich bis jetzt noch nicht beachtet habe.

Code:

<alles zu Kleinbuchstaben>
for(i = 0; i < password.length; i++) {
passcode *= password.charCodeAt(i);
}
for(x = 0; x < username.length; x++) {
usercode *= username.charCodeAt(x);
}
if(usercode==<zahl>)&&passcode==219235317047744800000)
{
window.location=password+".htm"
}

Der username ging schnell (~2 Minuten), weil das eine recht kleine Zahl (ca 6 Buchstaben) ist. Das PW aber ist eine größere Zahl (10 Buchstaben) :wall: :wall: :wall:

Gesucht sei nach allen möglichen Variationen :shock:

@cydo: Könntest du kurz erläutern, wie ich den Code in mein Programm einbaue? :coder2:

[everdream]

Wenn du nur eine mögliche Lösung brauchst, dann würde ich dir vielleicht (rekursives) Backtracking ans Herz legen. Das ganze kombiniert mit der Ganzzahldivision div (weil du mehr ja hier nicht benötigst) sollte dir in akzeptabler Zeit eine Lösung liefern.

edit: Habe zu viel Zeit und dir darum mal den Code dafür geschrieben:

Delphi-Quellcode:

function rekBacktracking(Hash: Int64; Laenge{in Zeichen}: byte): shortstring;
var
  i: byte;
begin
  if (Laenge = 1) then 
  begin  // Beim letzten Zeichen der Reihe
    for i:=97 to 122 do
      if i=Hash then
        Result:= Char(i);
  end else
  begin  // Bei den Zeichen 1 bis Laenge-1
    for i:=97 to 122 do
    begin
      if (Hash mod i = 0) then
        Result:=Char(i) + rekBacktracking(Hash div i, Laenge-1);
    end;
  end;
end;

Beachte, dass nur die erste erfolgreiche Zeichenkette ausgegeben wird und dass die Zeichen mit dem größten ASCII-Wert dabei immer vorne stehen.

Wenn du die Abbruchbedingung etwas änderst, kannst du auch z.B. alle Lösungen nacheinander in ein Textfile oder Memo schreiben lassen, dann hast du nach ein bischen Rechenzeit vielleicht alle. Das ganze sollte jedenfalls schneller sein als deine For-to-Schleifen, weil nicht alle Kombinationen zuende gerechnet werden.

edit2: 9 Zeichen sind innerhalb eines Augenschlages berechnet. Auch 10 Zeichen sind in relativ kurzer Zeit entschlüsselt, allerdings reicht in diesem Bereich der Typ Int64 auch schon nicht mehr aus.

edit3: Habe das ganze aus Spaß auch nochmal für alle möglichen Lösungen geschrieben:

Delphi-Quellcode:

procedure TForm2.rekBacktracking(Text: string; Hash: extended; Laenge: byte);
var
  i: byte;
begin
  if (Laenge = 1) then
  begin
    for i:=97 to 122 do
    begin
      if i=Hash then
      begin
        Memo.Lines.Add(Text + Char(i));
        Inc(Counter);
      end;
    end
  end else
  begin
    for i:=97 to 122 do
    begin
      Application.ProcessMessages;
      if ((round(Hash) mod i = 0) and (Run)) then
        rekBacktracking(Text + Char(i), round(Hash) div i, Laenge-1);
    end;
  end;
end;

Für den Hash habe ich extended genommen, weil da 2 Bytes mehr drin sind als im Int64. Dafür muss ich ab und an mit round() rumkaspern.

Beispiel:
Der Hash 2001968049246036480 mit einer Wortlänge von 9 Zeichen (maximum, da bei 10 zeichen auch extended eventuell nicht mehr reicht):
181440 Möglichkeiten [abffpqrsz..zsrqpffba] wurden in 16,69 Sekunden berechnet und in das Memo eingetragen.

Ich hänge dir das Proggi inkl. Source mal an. Copyright kannste haben... :drunken:

Hoffe, dass ich dir damit helfen konnte.

Mein Tipp: Vom ASCII-Code der Zeichen erst 96 abziehen (nicht 97!), damit du Zahlen von 1 bis 26 inklusive multiplizierst. Dann reichen auch "normale" Datentypen aus, um den Hash zu speichern.

[alzaimar]

Ein klitzekleine Verschönerung vielleicht?

Delphi-Quellcode:

function rekBacktracking(Hash: Int64; Laenge{in Zeichen}: byte): shortstring;
var
  i: byte;

begin
  if (Laenge = 0) then
    Result := ''
  Else for i:=97 to 122 do
    if (Hash mod i = 0) then
      Result := Char(i) + rekBacktracking(Hash div i, Laenge-1);
end;

[cydo]

öhm. ich weiss ja nicht, ob es schon jemand aufgefallen ist: der von mir gepostete code macht rekursives backtracking mit bigint zahlen und ergibt als ergebnis: es gibt keine lösung zu der genannten zahl.

ausserdem kann "charCodeAt" auch unicode zurückliefern, damit ist der bereich dann wirklich nicht mehr 97-122 (oder wie von mir getestet 10-250).

http://developer.mozilla.org/en/docs...ing:charCodeAt
"Note that charCodeAt will always return a value that is less than 65,536"
ok, dann ist der Bereich also 2-65536 ;-)

@breezel:
der von mir gepostete code einfach in delphi reinkopieren (neu|konsolenanwendung) und die unit bigint noch mit ins verzeichnis packen (einfach hier mal nach "bigint" suchen (von F. Rienhardt).

gehts hier um eine japanische p**n-seite? dann liesse sich der unicode bereich einschränken;-)

[gammatester]

Zitat:

Zitat von cydo

öhm. ich weiss ja nicht, ob es schon jemand aufgefallen ist: der von mir gepostete code macht rekursives backtracking mit bigint zahlen und ergibt als ergebnis: es gibt keine lösung zu der genannten zahl.

ausserdem kann "charCodeAt" auch unicode zurückliefern, damit ist der bereich dann wirklich nicht mehr 97-122 (oder wie von mir getestet 10-250).

http://developer.mozilla.org/en/docs...ing:charCodeAt
"Note that charCodeAt will always return a value that is less than 65,536"
ok, dann ist der Bereich also 2-65536 ;-)

Ist mir schon aufgefallen, aber wie ich schon geschrieben habe, zeigt doch die Primzahlzerlegung

219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

daß es selbst im vergrößerten Bereich kein Lösung gibt.

Gruß Gammatester

[cydo]

Zitat:

Ist mir schon aufgefallen, aber wie ich schon geschrieben habe, zeigt doch die Primzahlzerlegung

219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

daß es selbst im vergrößerten Bereich kein Lösung gibt.

stimmt. noch einfacher. noch schlüssiger.

[everdream]

Zitat:

Zitat von cydo

der von mir gepostete code macht rekursives backtracking mit bigint zahlen

Dann kann der Threadstarter sich ja jetzt meinen Algorithmus (mit alzaimar's Verschönerdung :wink: ) schnappen, da dein BigInt reinhämmern und sollte dann eigentlich alles haben. Mit BigInt kann er dann ja auch mal über die 10 Zeichen hinaus versuchen, was noch so möglich ist.

Oder sind noch fragen offen?

[-=Breeze=-]

@everdream dein Programm funktioniert super, ich habe schon den Username ausprobiert, die Lösung stimmt mit meiner überein :cheers:

Aber: könntest du den Zahlenbereich um die Zahlen 48-57 erweitern? Ich kanns leider nicht selber machen, weil ich Probleme habe die dpr zu öffnen (vllt andere Delphi Version).
Grund dafür ist es, dass evtl auch Zahlen im PW vorkommen, die wir bisher nicht beachtet haben.
Ascii Tabelle

Wie gesagt ich würde es gerne selber machen, kann es aber nicht einwandfrei öffnen... :gruebel:

Eigentlich muss man dann eine Lösung finden, weil der Algo das ja so verschlüsselt und es auch funktioniert... :gruebel:

PS:

:mrgreen: Nein es handelt sich nicht um

Zitat:

Zitat von cydo

eine japanische p**n-seite

[shmia]

Zitat:

Zitat von -=Breeze=-

Eigentlich muss man dann eine Lösung finden, weil der Algo das ja so verschlüsselt und es auch funktioniert... :gruebel:

Das ist doch Quatsch! :wall:
Man testet einen Codebrecher Algorithmus doch immer an einer Verschlüsselung, die man selbst errechnet hat.
Du nimmst also ein Wort mit 3 Zeichen, wandelst jedes Zeichen in eine Zahl, multiplizierst diese Faktoren und versuchst dich zuerst am diesem Ergebnis. Dann darfst du dich auf 10 Zeichen steigern.

Oder würdest du von einer fremden Person eine Mathematikhausaufgabe annehmen, nur um nach einigen Stunden rauszufinden, dass die Aufgabe falsch war und keine Lösung hat ??

[everdream]

Öffne doch die Unit, da steht schließlich der ganze Quellcode drin. Dann kannst du das ganze auf ein eigenes Projekt übertragen und auch die BigInt noch einbauen. 'N Bischen musste auch noch selber machen ;-)

[toms]

:arrow: TBruteForce Komponente von Meflin

[gammatester]

Zum dritten und letzen Mal: Die Voraussetzung über den "Verschlüsselungs"-Algorithmus kann nicht stimmen!

219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

Demnach muss ein Zeichen mit 7321 und ein anderes mit 3402964651 kodiert werden.

Gammatester

[alzaimar]

Zitat:

Zitat von -=Breeze=-

Ich kanns leider nicht selber machen, weil ich Probleme habe die dpr zu öffnen (vllt andere Delphi Version).

Nee, .dpr ist der Quelltext des Projektes. Den kannst Du auch mit Notepad öffnen. Du bist wohl eher zu faul.

[everdream]

Zitat:

Zitat von gammatester

Deine Vermutungen können nicht stimmen, denn die Primfaktorzerlegung lautet:
219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

Wieso zerlegst du das denn in Primzahlen? Es geht doch um 10 Werte im Bereich von 97 bis 122. (+ Eventuell den Ziffernbereich)

[gammatester]

Zitat:

Zitat von everdream

Zitat:

Zitat von gammatester

Deine Vermutungen können nicht stimmen, denn die Primfaktorzerlegung lautet:
219235317047744800000 = 2^8 * 5^5 * 11 * 7321 * 3402964651

Wieso zerlegst du das denn in Primzahlen? Es geht doch um 10 Werte im Bereich von 97 bis 122. (+ Eventuell den Ziffernbereich)

Ist doch piepegal wo das Produkt herkommt: wenn in der Primfaktorzerlegung solch große Zahlen vorkommen, kann die Zahl kein Produkt von Zahlen aus dem Bereich 97 bis 122 sein. Man kann die Tatsache ignorieren und monatelang Brute-Force-Rechnungen durchführen oder 1 Minute nachdenken und 300 Millisekunden die PFZ ausrechnen.


Gruß Gammatester

[everdream]

Jo, du hast recht, sorry.

Wie weit ist denn der Threadstarter jetzt eigentlich?

[-=Breeze=-]

der Threadstarte hat sich gerade davon überzeugt das bei der PFZ tatsächlich eine 3402964651 vorkommt

und er ist jetzt ziemlich durcheinander weil er sich 100%ig sicher ist das die Verschlüsselung so auf der Website ist... :wall:
und sucht gerade danach, ob die Java-Funktion "CharCodeAt(x)" auch andere Werte angeben kann als erwartet (Ascii Code). :roteyes:

[Torpedo]

Vielleicht gibts ja gar keine Lösung und auch kein Passwort. ;)
Was ist das denn für eine Seite? Irgend ein HackIt? Kann sein dass du dich gerade auf das falsche konzentrierst.

[cydo]

Zitat:

Zitat von -=Breeze=-

und sucht gerade danach, ob die Java-Funktion "CharCodeAt(x)" auch andere Werte angeben kann als erwartet (Ascii Code). :roteyes:

oh. ja. ich glaub, posts überlesen macht einfach viel mehr spass. breezel: ich bin mir sicher, der code ist von 97-122, das gewäsch der anderen freundlichen poster ist doch eh quatsch (achtung, sarkasmus).

[cydo]

als tipp: bei integer-überlauf komme ich irgendwann auch auf die gepostete zahl. das passwort ist also größer als 10 stellen.

und da nicht nur ein bliebiges passendes passwort gesucht wird, sondern ein bestimmtes, ist der algo doch recht gut - angenommen, das passwort hat 15 stellen, dann passen für den code ca. millionen von passwörtern auf den code, aber nur ein passwort ist das richtige.

Delphi-Quellcode:

window.location=password+".htm"

ist mit brute force bei längeren passwörtern nicht zu knacken, da diese dann auch mit einer webseite abgelichen werden müssen, dauert bei millionen von passwörtern ewig...