One Way Trip?

Hi,

ich habe folgenden Code gefunden und frage mich ob dies ein One Way Trip ist, oder man das "verschlüsselte" daraus wieder "entschlüsselt" bekommt.

hier mein code:

#include <cstdlib>
#include <iostream>

long krypt (char *str, char code)
{
    long i, ascii;

    if (code && code != '0')
    for (i=0; str[i]; i++)
    {
        ascii  = (str[i] * code * (i + 1L) + code) % 62L;

        char buffer = ascii;
        if (ascii < 10L)
        {
            buffer += '0';
        }
        else
        {
            if (ascii < 36L)
               buffer += 'A' - 10L;
            else
                buffer += 'a' - 36L;
        }
        str[i] = buffer;
    }
    return(0);
}

int main(int argc, char *argv[])
{

    char data[255] = "pikaboo";
    krypt (data, 'P');

    std::cout << data << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

Kann ich data mit "krypt" später wieder in "pikaboo" umwandeln, oder handelt es sich hier wirklich um einen One Way Trip?

Danke im voraus

hustbaer

Wenn du Passwörter verschlüsseln willst, dann nimm dafür einen cryptographisch sicheren Hash Algorithmus. MD5 sollte es auch tun.

Wichtig ist dabei nämlich nicht nur dass man den original String nicht "zurückgewinnen" kann, sondern auch dass man keinen 2. String (der vielleicht ganz anders ist als das "Original") finden kann dessen "verschlüsselte Abbildung" gleich aussieht wie das Original. Und das wäre bei deiner Funktion nur allzu einfach.

ne0r

Prinzipiell ist dein Algorithmus schon ok, nur musst du schaun, dass du dein % so wählst, das wieder etwas umkehrbares bei rauskommt. (Ich glaube das war so: bei x * s % n muss der größte gemeinsame Teiler von s und n 1 sein und s und n > als die Definitionsmenge von x).
Nimm zum Beispiel x * 5 % 20: bei x = 0 kriegste null, bei x = 4 kriegste auch null => nicht umkehrbar.

Hi ihr Beiden!

Erstmal danke für eure Antworten und sorry, dass es solange gedauert hat bis ich mich gemeldet habe.

Meine Frage war eigentlich nicht, wie man es besser kann, sondern eher ob es bei diesem sehr simplen Algo es einen weg zurück gibt.

Also einfach damit etwas "verschlüsseln" und das danach wieder "entschlüsseln". Ist das damit möglich, wenn ja: Wie?

Nochmals danke im voraus.

hustbaer

Der Fragende schrieb:

Also einfach damit etwas "verschlüsseln" und das danach wieder "entschlüsseln". Ist das damit möglich, wenn ja: Wie?

Nein, es ist nicht möglich. Beispiel:

ascii  = (str[i] * code * (i + 1L) + code) % 62L;

Wenn "code == 62" oder "(i + 1L) == 62", dann ist "ascii" auf jeden Fall gleich "code" - ganz egal was in "str[i]" drinnen steht. Hier trifft dich das was ne0r schon erwähnt hast.

Weiters bekommst du mit "modulo 62" auch immer nur 62 verschiedene Zahlen als Ergebnis, du kannst also durch das "modulo 62" allein schon im besten Fall nur 62 verschiedene Zahlen eindeutig abbilden.
Und da ein char mehr als 62 verschiedene Werte haben kann...

Kurz: die Funktion "vernichtet" Daten, d.h. es kann auch keinen eindeutigen Weg zurück geben. Man kann also eine Menge an Eingaben ausrechnen die alle auf eine gegebene Ausgabe abgebildet werden, man kann allerdings nicht wissen welches Element dieser Menge ursprünglich verwendet wurde.

Okay danke Also ist das einzigste was man machen kann um das zu "knacken" das gute alte Kollisionsverfahren.

Hi,

ich habe das nun mit dem Kollisionsverfahren mal ausprobiert und geht wunderbar. Bekomme mehrere Ergebnisse die das "verschlüsselte" entsprechen.

Kann ich das Kollisionsverfahren aufgrund des mir bekannten verschlüsselungsalgo optimieren, so das ich schneller ergebnisse erziele als jede Möglichkeit einzeln durchzugehen?

Danke im voraus.

hustbaer

Der Fragende schrieb:

Okay danke Also ist das einzigste was man machen kann um das zu "knacken" das gute alte Kollisionsverfahren.

Ich weiss nicht was du unter Kollisionsverfahren verstehst, aber das ganze umzudrehen ist eigentlich ganz einfach.
Erst bildest du '0'-'9', 'A'-'Z' und 'a'-'z' zurück auf 0-61 ab, und dann suchst du dir ein Zeichen raus welches codiert eben diese Zahl ergibt. Dafür würde ich einfach eine Schleife nehmen in der du alle 256 Zeichen durchgehst, bzw. evtl. die überspringst die im Input garnicht vorkommen dürfen (z.B. 0).

Das machst du für jede Stelle im "codierten" String einzeln, und fügst die gefundenen Zeichen einfach aneinander. Du kannst auch für jede Stelle alle möglichen Zeichen abspeichern, dann kannst du wenn du willst nachdem du alle Stellen durch hast schnell weitere mögliche Kombinationen zusammenbasteln.

Das ganze ist deswegen ziemlich trivial zu lösen (und schnell - auf die Laufzeit bezogen), da jedes Zeichen des "codierten" Strings nur vom Zeichen an der selben Position des Eingabestrings abhängig ist. Eine komplette brute-force Attacke erübrigt sich dadurch.

Die Komplexität um einen möglichen Eingabestring zu finden ist O(N), wobei N eben die Länge des Strings ist -- also gleich der Komplexität beim "Verschlüsseln".