Zeichen aus verschlüsselten Text auslesen und entschlüsseln

Hi,

habe die Aufgabe einen verschlüsselten Text zu entschlüsseln.
Der verschlüsselte Text kann aus dem kompletten ASCII Zeichenvorrat bestehen und wurde im Cäsar Verfahren verschlüsselt.

Meine Idee war nun den Text zeichen für zeichen ein zu lesen und auf das häufigste Zeichen zu kontrollieren. Dieses müsste dann normaler Weiße dem "e" entsprechen.

Aus der Differenz zwichen dem verschlüsselten Zeichen und dem "e" könnte ich dann die anderen Zeichen entschlüsseln.

Zum zählen der zeichen würde ich map verwenden (map<char, int> zeichen), und ein weiteres mal map zum entschlüsseln (map<char,char> schluessel)

So nun meine Fragen
Ist mein Lösungsansatz überhaupt sinnvoll bzw. praktikabel?
Habe lange vor der Aufgabe gessesen und mir ist erstmal keine wirkliche Lösung eingefallen.
Zumal angegeben ist das wir als einziges Hilfsmittel eine Datei vervwenden dürfen, in der wir beliebeige Wörter angeben können. Nur ich habe keine Ahnung was mir diese Datei bringen soll.

Würde mich über jede Antwort freuen

ScottZhang

Welcher Ansatz? Zeig doch mal den Code!

Hab noch keinen Code, da ich mir erst gedanken gemacht habe, wie ich das lösen kann. Wollte nur eure Meinung zu meiner Idee hören, damit ich mich nicht in irgend eine Idee verrenne. Ich tue mich eben ein wenig schwer mit dieser Aufgabe.

volkard

green_banana schrieb:

Hab noch keinen Code, da ich mir erst gedanken gemacht habe, wie ich das lösen kann. Wollte nur eure Meinung zu meiner Idee hören, damit ich mich nicht in irgend eine Idee verrenne. Ich tue mich eben ein wenig schwer mit dieser Aufgabe.

Hast viel zu wenig oder viel zu ungenau beschrieben, um was es geht.
Ist es ein Cäsar-Chiffre? Oder ist es ein anderes Tauschalphabet?

Wie war das mit der Datei? Du kannst eine Klartextdatei mit ein paat Wörtern einsenden und bekommst dazu das passende Chifrat und anhanddessen sollste dann einen ENtschlüsslter programmieren?

Der Text wurde im Cäsar-Verfahren verschlüsselt.

Du kannst eine Klartextdatei mit ein paat Wörtern einsenden und bekommst dazu das passende Chifrat und anhanddessen sollste dann einen ENtschlüsslter programmieren?

In der Aufgabenstellung steht, dass wir keine anderen Hilfsmittel verwenden dürfen, außer einer von uns angelegten Datei, in der wir Wörter angeben können.
Diese Datei soll bei der Mustererkennung helfen.

Sonst ist nichts angegeben, keine Wörter oder ähnliches.

SeppJ

Also Cäsarverfahren hat selbst im gesamten ASCII-Zeichensatz nur 127 mögliche Schlüssel (0 zähle ich mal nicht mit), selbst im (wahrscheinlich gemeinten) erweiterten ASCII-Zeichensatz hat man nur 255 Schlüssel.

Wenn du zeiteffizient arbeiten möchtest: Einen einfachen Dekoder schreiben ist praktisch trivial. Dann kannst du alle möglichen Kombinationen durchprobieren und als Mensch einzeln entscheiden, welches die Lösung ist. Das geht in 10 Minuten, 4-6 Minuten zum Schreiben des Programms und nochmal 2-4 Minuten, um alle Kombinationen zu probieren, wenn wir annnehmen, dass du eine Kombination pro Sekunde kontrollieren kannst.

Wesentlich komplizierter, aber vermutlich eleganter, ist ein halbautomatischer Ansatz unter Benutzung von Heuristiken. Du hast schon die Suche nach dem 'e' erwähnt, ein weiteres gutes Kriterium wäre auch, dass es sich überhaupt um Text und/oder Zahlen handelt, die meisten Zeichen der Lösung also später im Zeichenraum 'a'-'z', 'A'-'Z' und '0'-'9' landen sollten. Dies gibt dir eine gute Schätzung für den Bereich in dem der Schlüssel sein kann, dann sollte es bloß noch 1-3 mögliche Kombinationen geben. Wenn dann noch die Buchstaben 'a' und 'e' Peaks in der Verteilung sind (ich würde die Bedingung nicht so hart formulieren, dass 'e' am häufigsten vorkommen muss, es sollte bloß in den Top-5 sein, dann deckt man auch kurze, ungewöhnliche oder fremdsprachliche Texte ab). Die dann noch verbliebenen möglichen Schlüssel (sollten bloß noch um die 1 sein) prüft dann wieder ein Mensch. Oder wenn es noch aufwändiger sein soll: Ein Vergleich mit einem Wörterbuch.

Bei allen diesen Verfahren kann die Kontrolle durch einen Menschen auch so erfolgen, dass die Schlüssel und der zugehörige entschlüsselte Text in eine Datei geschrieben werden, wo ein Mensch sie dann ansieht, anstatt direkt am Bildschirm. Beim ersten Verfahren, könnte dies sogar flotter sein, da man dann durch überfliegen der Datei gleich mehrere Schlüssel gleichzeitig prüfen kann und so deutlich mehr als einen Schlüssel pro Sekunde schafft.

volkard

green_banana schrieb:

Der Text wurde im Cäsar-Verfahren verschlüsselt.

Ok. Also nur 256 mögliche Schlüssel, wenn die ganzen Datei-Bytes rotiert werden.
(Dann wäre Zeichenmüll wie "6%$3#+|lj" im Chiffrat.)

Oder 26, wenn nur die Buchstaben rotiert werden.
(Dann wäre es nur Buchstabenmüll wie "fieder Ueht hje lppt".)

green_banana schrieb:

In der Aufgabenstellung steht, dass wir keine anderen Hilfsmittel verwenden dürfen, außer einer von uns angelegten Datei, in der wir Wörter angeben können.
Diese Datei soll bei der Mustererkennung helfen.

Oki, das macht vieles einfacher. Brauchst nicht starr nach dem e zu schauen. Auch nicht nach "die häufigsten buchstaben sind enristl".

Machst in Deine Datei einfach einen längeren recht normalen Text rein. Projekt Gutenberg hilft. Ich hab auch gerne irgendeine *.txt aus dem Windows-Verzeichnis genommen. Den will ich jetzt mal Normaltext nennen.

Und dann zählst Du die Zeichenhäufigkeiten des Normaltextes. Und die Zeichenhäufigkeiten des Chiffrats. Hast dann sozusagen zwei Histogramme.

Denkst Dir noch ein Maß dafür aus, wie gut sich zwei Histogramme einig sind und die selbe Sprache wohl darstellen. Würde mal anfangen mit der Summe der Quadrate der Differenzen der relativen Häufigkeiten der einzelnen Zeichen.

Und dann läßt Du das Histogramm des Chiffrats rotieren und schaust, wo die beste Übereinstimmung ist, fertig, da haste den Schlüssel in der Hand.

Sowas sollte ersaunlich gut klappen, schon bei einer Zeile Text würde ich darauf tippen, daß er normalerweise trifft.

Toll wäre es, wenn das Programm noch am Ende dem Benutzer ein paar Zeilen des mit dem so errungenen Schlüssel entschlüsselten Textes zeigen würde und den Benutzer befragen, ob er glaubwürdig ist und solange immer den nächsten noch verbleibenden besten Schlüssel raussuchen und darbieten, bis der Benutzer den richtigen Schlüssel bestätigt (oder alle Verbaucht sind, dann wars wohl kein Cäsar-Chiffre).

Praktisch recht es völlig, wenn man sich das ganze Brimbnorium spart und dem Benutzer nacheiunander alle 256 Mögliche Schlülles nebst Textprobe anbietet, die hat er in zwei Minuten gesichtet und den echten Schlüssel gefunden. Aber daß Ihr Euch eine Wortliste anlegen sollt, klingt mir danach, der Prof hat sowas mit Histogrammen im Sinn.
Eine simple Wörterbuch-Wortliste bringt natürlich weniger, als ein normaler Text, bei dem normalerweise häufiger vorkommende Wörter auch häufiger vorkommen.

Schon mal vielen Dank für eure Hilfe.
Hab jetzt wirklich ein paar Ideen wie ich das umsetzten kann.

Werde mich mit Sicherheit bei der ein oder anderen Frage hier noch mal melden

Werner Salomon

volkard schrieb:

... Und dann zählst Du die Zeichenhäufigkeiten des Normaltextes. Und die Zeichenhäufigkeiten des Chiffrats. Hast dann sozusagen zwei Histogramme.

Denkst Dir noch ein Maß dafür aus, wie gut sich zwei Histogramme einig sind und die selbe Sprache wohl darstellen. Würde mal anfangen mit der Summe der Quadrate der Differenzen der relativen Häufigkeiten der einzelnen Zeichen.

Und dann läßt Du das Histogramm des Chiffrats rotieren und schaust, wo die beste Übereinstimmung ist, fertig, da haste den Schlüssel in der Hand.

... während Volkard dieses Posting geschrieben hat, habe ich das mal probehalber codiert. Zwei Seelen ein Gedanke - in der Bildverarbeitung macht man so was auch.
Bleibt noch zu erwähnen, dass man die Histogramme vor dem 'best square fit' noch normieren sollte - also alle Häufigkeiten durch die Anzahl der erfassten Zeichen teilen. Und dann braucht man auch nicht das komplette Histogramm zu betrachten, sondern nur einige ausgewählte Zeichen - solche, die sehr häufig vorkommen, reichen völlig aus - z.B. das berühmte "ernst".

volkard hat mit seiner Vermutung ganz Recht. Als Referenz habe ich das erste Posting von green_banana genommen (das ist als Referenz genug) und als Chiffrat das letzte Posting von SeppJ.

Bei meiner gewählten Skalierung liegt der korrekte Wert bei 1,5% und alle anderen Werte zwischen 26% und 80% Abweichung (das % ist nicht ganz ernst zu nehmen) - aber der Unterschied ist so was von eindeutig.

anbei mein Code:

#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
#include <cmath> // pow
#include <streambuf>

// --   streambuf zum Verschlüsseln
class Caesar : public std::streambuf
{
public:
    Caesar( int caesar, std::streambuf* dev )
        : caesar_( caesar )
        , dev_( dev )
    {
        assert( caesar > -128 && caesar < 0x100 );
    }
protected:
    int_type overflow( int_type m = traits_type::eof() )
    {
        assert( pptr() == 0 || pptr() >= epptr() );
        if( traits_type::eq_int_type( m, traits_type::eof() ) )
            return dev_->pubsync() == 0? traits_type::not_eof(m): m;
        return dev_->sputc( char((traits_type::to_char_type( m ) + 0x100 + caesar_) % 0x100) );
    }
    int_type underflow()
    {
        assert( gptr() == 0 || gptr() >= egptr() );
        const int_type m = dev_->sbumpc();
        if( traits_type::eq_int_type( m, traits_type::eof() ) )
            return m; // EOF
        buf_ = char((traits_type::to_char_type( m ) + 0x100 - caesar_) % 0x100);
        setg( &buf_, &buf_, &buf_ + 1 );
        return traits_type::to_int_type( buf_ );
    }
private:
    int caesar_;
    std::streambuf* dev_;
    char buf_;
};

struct Histogramm
{
    Histogramm()
        : histo_()
        , count_(0)
    {}

    friend double dif( const Histogramm& ref, const Histogramm& h, int caesar, const char* mask )
    {
        typedef unsigned char Byte;
        double result = 0.;
        int cnt = 0;
        for( ; *mask; ++mask, ++cnt )   // square sum berechnen
            result += std::pow( ref.share(*mask) - h.share( (*mask + 256 + caesar)%256 ), 2 );
        assert( cnt > 0 );
        return (result * 90) / cnt; // 90 empirisch ermittelt; so werden die größten Abweichungen ungefähr <= 1.0
    }
    friend int best_caesar( const Histogramm& ref, const Histogramm& h, const char* mask )
    {
        int best = 0;
        double best_value = 999.;
        for( int caesar = -127; caesar <= 128; ++caesar )
        {
            const double result = dif( ref, h, caesar, mask );
            // std::clog << caesar << ": " << result << std::endl;
            if( result < best_value )
            {
                best = caesar;
                best_value = result;
            }
        }
        return best;
    }

    double share( char c ) const
    {
        assert( histo_.size() >= 256 );
        return double(histo_[static_cast< unsigned char >( c )]) / count_;
    }
    friend std::istream& operator>>( std::istream& in, Histogramm& s )
    {
        std::vector< int > histo( 256 );
        in >> std::noskipws;
        s.count_ = 0;
        for( unsigned char c; in >> c; ++s.count_ ) // bis EOF lesen
            ++histo[c];
        if( in.eof() && s.count_ > 0 )
        {
            in.clear();
            swap( histo, s.histo_ );
        }
        return in;
    }
private:
    std::vector< int > histo_;
    int count_;
};

int main()
{
    using namespace std;
    Histogramm reference;
    {
        ifstream reference_file( "input.txt" );
        if( !reference_file.is_open() )
        {
            cerr << "Fehler beim Oeffnen des reference_files" << endl;
            return -2;
        }
        reference_file >> reference;
        assert( reference_file );
    }

    Histogramm datei;
    ifstream chiffrat( "chiffrat.bin", ios_base::binary ); // Chiffrat als binary laden
    if( !chiffrat.is_open() )
    {
        cerr << "Fehler beim Oeffnen der Datei" << endl;
        return -2;
    }
    chiffrat >> datei;
    assert( chiffrat );
    const int caesar = best_caesar( reference, datei, "ernst" );
    cout << "Caesar-Verschiebung: " << caesar << endl;

    // --   seek begin und nochmal lesen
    chiffrat.seekg( 0, ios_base::beg );
    Caesar encoding( caesar, chiffrat.rdbuf() );
    cout << &encoding<< endl; // Chiffrat encodiert auf stdout
    return 0;
}

Gruß
Werner

volkard

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass man die Histogramme vor dem 'best square fit' noch normieren sollte - also alle Häufigkeiten durch die Anzahl der erfassten Zeichen teilen.

Dadurch sind es relative Häufigkeiten und keine absoluten Häufigkeiten mehr, hab extra relative gefordert.

Werner Salomon schrieb:

Und dann braucht man auch nicht das komplette Histogramm zu betrachten, sondern nur einige ausgewählte Zeichen - solche, die sehr häufig vorkommen, reichen völlig aus - z.B. das berühmte "ernst".

"enristl"
Hab da ein wenig Angst, daß Folgendes passiert: MS schreibt in der EULA unter jede Überschrift eine gleich breite Reihe von ====== und unter jeden Telabschnittsnamen eine Reihe ------ und lauter Zeilenumbrüche, das sind dann sooo viele, daß es als 'e' und 'n' und 'r' erkannt werden müssen.

Denke, einerseits ist das Quadrieren zu hart. Nur, weil einer eine Marotte mit einem Zeichen hat, muß er nicht so hart bestraft werden.

Und andererseits sollte die absolute Häufigkeit nicht (nur) zur Vorauswahl genommen werden, sondern als Gewichtung.