Die Playfair Verschlüsselung in C#

Anhand der Cäsar– und Vigenère Verschlüsselung haben wir gesehen wie man einzelne Buchstaben mithilfe eines Schlüssels chiffrieren kann. Im Jahr 1854 hat Charles Wheatstone ein Verschlüsselungsverfahren entwickelt bei dem jeweils Buchstabenpaare des Klartextes durch andere Buchstabenpaare ersetzt werden. Später hat sein Freund Lord Lyon Playfair diesen Algorithmus zur Benutzung beim Britischen Militär empfohlen und ist somit auch der Namensgeber des Verfahrens geworden. Die Playfair Verschlüsslung war sicher im Vergleich zu den auf der Verschlüsselung von Einzelzeichen basierenden Verfahren und wurde sogar noch im zweiten Weltkrieg benutzt.

Am besten fangen wir gleich mit einem Beispiel an. Als Input für das Playfair-Verfahren brauchen wir ein Schlüsselwort (Key) und natürlich den Klartext den es zu verschlüsseln gilt. Wir nehmen:

Key=“GEHEIMNIS“

Klartext=“WETTE“

Außerdem brauchen wir ein Alphabet, welches wir zur Erstellung einer Verschlüsselungsmatrix benutzen werden.

(Wichtig! Da wir eine 5×5-Matrix bauen wollen lassen wir den Buchstaben J weg. Stattdessen werden wir I stellvertretend für beide Buchstaben benutzen. Alternativ wird in manchen Implementierungen der Buchstabe Q weggelassen.)

alphabetPlayfair

Nun da wir alles haben können wir das Verfahren wie folgt gliedern.

  1. Passe das Schlüsselwort an und erstelle eine 5×5-Matrix.
  2. Passe den Klartext an.
  3. Benutze zuvor erstellte Matrix und den angepassten Klartext zur Verschlüsselung.

Schritt 1

Um den Schlüssel anzupassen gehen wir das Wort Buchstabe für Buchstabe durch und entfernen mehrfach vorkommende Buchstaben so dass jeder Buchstabe nur noch einmal in dem Schlüsselwort vorkommt. Gleichzeitig entfernen wir jeden Buchstaben der im Schlüssel enthalten ist aus dem Alphabet. So bekommen wir einen neuen Schlüssel.

K=“GEHEIMNIS“→““GEHIMNS

Nach dem Entfernen der Buchstaben sieht unser Alphabet wie folgt aus:

newAlphaPlayfair

Nun da wir Schlüssel und Alphabet angepasst haben, können wir diese benutzen um eine 5×5 Verschlüsselungsmatrix zu erstellen.

emptymatrixPlayfair

Wir beginnen damit, dass wir die Buchstaben des angepassten Schlüssels in die Matrix einfügen.

matrixWithKeyPlayfair

Als nächstes füllen wir die Matrix mit den im Alphabet verbliebenen Buchstaben.

fullmatrixPlayfair

Schritt 2

Nun muss der Klartext angepasst werden. Dabei wird dieser in Buchstabenpaare aufgeteilt.

(Wichtig! Sollte die Anzahl der Buchstaben im Klartext ungerade sein fügen wir am Ende ein X hinzu.)
 
(Wichtig! Um der Frequenzanalyse vorzubeugen wird in jedem Paar welches einen doppelten Buchstaben enthält, der zweite Buchstabe durch ein X ersetzt.)
 

Das Wort Wette enthält fünf Buchstaben, also hängen wir ein X am Ende an und bilden Buchstabenpaare.

Wettex

Da der Buchstabe T sich im Mittleren Paar wiederholt ersetzen wir das zweite T durch ein X. Somit erhalten wir den angepassten Klartext:

wetxex

Schritt 3

In diesem Schritt gehen wir den Klartext Buchstabenpaar für Buchstabenpaar durch und gleichen diese mit der Verschlüsselungsmatrix ab. Gleichzeitig schreiben wir den verschlüsselten Text mit.

Betrachten wir ein gegebenes Paar aus dem Klartext gibt es drei mögliche Konstellationen.

  1. Beide Buchstaben liegen in der Matrix in derselben Zeile. In diesem Fall verschlüsseln wir mit den Buchstaben die jeweils rechts daneben liegen.
  2. Beide Buchstaben liegen in der Matrix in derselben Spalte. Wenn dies zutrifft verschlüsseln wir die beiden Buchstaben mit dem jeweils darunter liegenden Buchstaben in der Matrix.
  3. Beide Buchstaben liegen weder in derselben Zeile noch in derselben Spalte. Hier wird für den ersten Buchstaben in der Matrix das Zeichen genommen, dass in der Spalte des zweiten liegt. Für den zweiten nehmen wir entsprechend den Buchstaben der in der Spalte der ersten liegt.

Das klingt auf den ersten Blick etwas verwirrend. Jedoch wird es am Beispiel ersichtlich. Wir nehmen das erste Buchstabenpaar aus unserem Beispiel.

we

Nun suchen wir die beiden Buchstaben in unserer Matrix und stellen fest, dass diese in derselben Spalte liegen.

weMatrix

Das bedeutet es ist der zweite Fall aus der obigen liste aufgetreten und wir verschlüsseln die beiden Buchstaben mit dem jeweils darunter liegenden Buchstaben. Das W wird zum E, denn wenn wir eine Zeile nach unten gehen landen wir wieder in der ersten Zeile. Entsprechend wird das E zum S weil sich das S direkt unter dem E befindet.

cipher1

Das nächste Buchstabenpaar TX befindet sich weder in der gleichen Spalte noch in der gleichen Zeile. Somit tritt der dritte Fall ein und wir verschlüsseln mit dem Buchstaben der in der Spalte des jeweils anderen liegt.

matrixTX

Das bedeutet, dass wir das T mit R verschlüsseln und das X entsprechend mit dem Y. So ergibt sich:

cipher2

Für das letzte Paar EX trifft wieder der dritte Fall zu, da diese in unterschiedlichen Spalten und Zeilen liegen.

matrixEX

Somit wird das E mit H verschlüsselt und das X mit W. So ergibt sich als resultierender verschlüsselter Text.

cipherresult

Leider ist in diesem Beispiel nie der erste Fall eingetreten. Diesen würden wir jedoch analog zum zweiten Fall behandeln, nur würden wir nicht die darunter liegenden Buchstaben zur Verschlüsselung nehmen sondern die jeweils rechts daneben liegenden.

Was brauchen wir nun um den Playfair Algorithmus zu implementieren? Als erstes schreiben wir ein struct Cell. Mit diesen Zellen werden wir später unsere Matrix füllen. Diese enthalten dann jeweils einen Buchstaben und die entsprechenden X und Y Koordinaten der Zelle in der Matrix.

public struct Cell
        {
            public readonly char Character;
            public readonly int X;
            public readonly int Y;

            public Cell(char _character,int _X, int _Y)
            {
                this.Character = _character;
                this.X = _X;
                this.Y = _Y;
            }
        }

Als nächstes implementieren wir die Methode AdjustString(). Diese benutzen wir dazu den Klar- und Schlüsseltext so zu bearbeiten, dass wir sie für das Verfahren benutzen können. Dabei werden sämtliche Leerzeichen entfernt und jedes J wird mit einem I ersetzt (siehe oben). Außerdem machen wir aus sämtlichen Zeichen Großbuchstaben.

        public static string AdjustString(string text)
        {
            //Entferne leerzeichen
            text = text.Trim();
            text = text.Replace(" ","");
            //Ersetze alle J durch I
            text = text.Replace("J","I");
            //Wandle alle Zeichen in Großbuchstaben um
            text = text.ToUpper();

            return text;
        }

Nun können wir die EncryptText() Methode implementieren. Diese wird von dem Cell-struct und von der Methode AdjustString() gebrauch machen.

(Wichtig! Falls einer der Buchstaben ganz außen oder ganz unten in der Matrix liegt berechnen wir die Verschlüsselung mit der Hilfe des Modulo Operators so springen wir automatisch wieder zum Anfang der Zeile bzw. Spalte.)
 
 
        public static string EncryptText(string keyWord,string plainText)
        {

            //Definiere Alphabet
            //Hier ist kein J enthalten, dafür benutzen wir das I
            char[] alphabet = "ABCDEFGHIKLMNOPQRSTUVWXYZ".ToCharArray();

            #region Passe Schlüssel an

            keyWord = AdjustString(keyWord);

            StringBuilder keyString = new StringBuilder();

            //Entferne alle doppelt vorkommende Buchstaben aus dem Schlüssel
            foreach(char c in keyWord)
            {
                if(!keyString.ToString().Contains(c))
                {
                    keyString.Append(c);
                    //Gleichzeitig erstellen wir ein alphabet welches die Buchstaben
                    //nicht enthält die bereits im Schlüsselwort vorkommen.
                    alphabet = alphabet.Where(val => val != c).ToArray();
                }
            }
            #endregion

            #region Passe klartext an

            plainText = AdjustString(plainText);

            //Wenn die anzahl der Buchstaben im Klartext ungerade ist fügen wir ein X an.
            if((plainText.Length % 2 > 0))
            {
                plainText += "X";
            }

            List plainTextEdited = new List();

            //Teile den Klartext in Buchstabenpaare auf.
            for (int i = 0; i < plainText.Length;i += 2)
            {
                //Sollte ein Paar den gleichen Buchstaben zwei Mal enthalten
                //Erstzen wir den zweiten Buchstaben durch ein X.
                if (plainText[i].ToString() == plainText[i + 1].ToString())
                {
                    plainTextEdited.Add(plainText[i].ToString() + 'X');
                }
                else {
                    plainTextEdited.Add(plainText[i].ToString() + plainText[i + 1].ToString());
                }

            }
            #endregion

            #region Erstelle eine 5 x 5 Matrix

            List matrix = new List();
            int keyIDCounter = 0;
            int alphabetIDCounter = 0;
            //Hier wird die Matrix mit Zellen (Cell) befüllt.
            for (int y = 0; y < 5;y++)
            {
                for (int x = 0; x < 5; x++)
                {
                    //Zuerst werden alle Buchstaben des Schlüssels in die Matrix eingefügt.
                    if (keyIDCounter < keyString.Length)                     {                         Cell cell = new Cell(keyString[keyIDCounter],x,y);                         matrix.Add(cell);                         keyIDCounter++;                     }//Nun befüllen wir die Matrix mit den im alphabet verbliebenen Buchstaben.                     else {                         Cell cell = new Cell(alphabet[alphabetIDCounter], x, y);                         matrix.Add(cell);                         alphabetIDCounter++;                     }                 }             }             #endregion             #region Verschlüssele Text             StringBuilder cipher = new StringBuilder();             //Gehe jedes Buchstabenpaar durch             foreach(string pair in plainTextEdited)             {                 //Finde Buchstabe A und B in der Matrix.                 int indexA = matrix.FindIndex(c => c.Character == pair[0]);
                Cell a = matrix[indexA];

                int indexB = matrix.FindIndex(c => c.Character == pair[1]);
                Cell b = matrix[indexB];

                //Schreibe Verschlüsselung unter Benutzung der drei möglichen Fälle.

                //Fall 1: A und B liegen in der gleichen Zeile
                if (a.Y == b.Y)
                {
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == (a.X + 1)%5 && c.Y == a.Y)].Character);
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == (b.X + 1)%5 && c.Y == b.Y)].Character);
                }
                else if(a.X == b.X)//Fall 2: A und B liegen in der gleichen Spalte
                {
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == a.X && c.Y == (a.Y + 1) % 5)].Character);
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == b.X && c.Y == (b.Y + 1) % 5)].Character);
                }else //Fall 3: A und B liegen weder in der gleichen Zeile noch in der gleichen Spalte
                {
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == b.X && c.Y == a.Y)].Character);
                    cipher.Append(matrix[matrix.FindIndex(c => c.X == a.X && c.Y == b.Y)].Character);
                }

            }

            #endregion

            return cipher.ToString();

        }

Vorausgesetzt wir haben das Schlüsselwort, verläuft die Entschlüsselung analog zu Verschlüsselung mit einigen kleinen Unterschieden. Hier wird wieder der Schlüssel angepasst und ein Alphabet erstellt. Der verschlüsselte Text muss nicht angepasst werden. Außerdem werden wir uns in der Matrix nicht um eine Zelle nach rechts bzw. unten bewegen, sondern nach links bzw. oben. Dadurch kann es bei der Berechnung des Modulo zu negativen Werten kommen. Um dies zu vermeiden verwenden wir hier die selbst implementierte Modulo Methode.

        public static string DecryptText(string keyWord, string cipherText)
        {
            //Definiere Alphabet
            //Hier ist kein J enthalten, dafür benutzen wir das I
            char[] alphabet = "ABCDEFGHIKLMNOPQRSTUVWXYZ".ToCharArray();

            #region Passe Schlüssel an

            keyWord = AdjustString(keyWord);

            StringBuilder keyString = new StringBuilder();

            //Entferne alle doppelt vorkommende Buchstaben aus dem Schlüssel
            foreach (char c in keyWord)
            {
                if (!keyString.ToString().Contains(c))
                {
                    keyString.Append(c);
                    //Gleichzeitig erstellen wir ein alphabet welches die Buchstaben
                    //nicht enthält die bereits im Schlüsselwort vorkommen.
                    alphabet = alphabet.Where(val => val != c).ToArray();
                }
            }
            #endregion

            List cipherTextEdited = new List();

            //Teile den verschlüsselten Text in Buchstabenpaare auf.
            for (int i = 0; i < cipherText.Length; i += 2)
            {
                cipherTextEdited.Add(cipherText[i].ToString() + cipherText[i + 1].ToString());
            }

            #region Erstelle eine 5 x 5 Matrix

            List matrix = new List();
            int keyIDCounter = 0;
            int alphabetIDCounter = 0;
            //Hier wird die Matrix mit Zellen (Cell) befüllt.
            for (int y = 0; y < 5; y++)
            {
                for (int x = 0; x < 5; x++)
                {
                    //Zuerst werden alle Buchstaben des Schlüssels in die Matrix eingefügt.
                    if (keyIDCounter < keyString.Length)                     {                         Cell cell = new Cell(keyString[keyIDCounter], x, y);                         matrix.Add(cell);                         keyIDCounter++;                     }//Nun befüllen wir die Matrix mit den im alphabet verbliebenen Buchstaben.                     else                     {                         Cell cell = new Cell(alphabet[alphabetIDCounter], x, y);                         matrix.Add(cell);                         alphabetIDCounter++;                     }                 }             }             #endregion             #region Entschlüssele Text             StringBuilder plainText = new StringBuilder();             //Gehe jedes Buchstabenpaar durch             foreach (string pair in cipherTextEdited)             {                 //Finde Buchstabe A und B in der Matrix.                 int indexA = matrix.FindIndex(c => c.Character == pair[0]);
                Cell a = matrix[indexA];

                int indexB = matrix.FindIndex(c => c.Character == pair[1]);
                Cell b = matrix[indexB];

                //Schreibe Verschlüsselung unter Benutzung der drei möglichen Fälle.

                //Fall 1: A und B liegen in der gleichen Zeile
                if (a.Y == b.Y)
                {
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == ViaduktLib.Helper.HelperClass.Modulo((a.X - 1), 5) && c.Y == a.Y)].Character);
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == ViaduktLib.Helper.HelperClass.Modulo((b.X - 1), 5) && c.Y == b.Y)].Character);
                }
                else if (a.X == b.X)//Fall 2: A und B liegen in der gleichen Spalte
                {
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == a.X && c.Y == Modulo((a.Y - 1), 5))].Character);
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == b.X && c.Y == Modulo((b.Y - 1), 5))].Character);
                }
                else //Fall 3: A und B liegen weder in der gleichen Zeile noch in der gleichen Spalte
                {
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == b.X && c.Y == a.Y)].Character);
                    plainText.Append(matrix[matrix.FindIndex(c => c.X == a.X && c.Y == b.Y)].Character);
                }

            }

            #endregion

            return plainText.ToString();
        }

Aus Verständnisgründen habe ich versucht den Code so einfach wie möglich zu halten. Dazu sollte man aber folgende Dinge noch anmerken.

  1. Der Code kann noch effizienter geschrieben werden indem man an manchen Stellen LINQ benutzt anstatt schleifen zu implementieren. So könnte man beispielsweise das Entfernen der Buchstaben aus dem Alphabet die im Schlüssel vorkommen in zwei Zeilen implementieren.
  2. Außerdem werden in dieser Implementierung keine Satzzeichen oder Zahlen berücksichtigt.

Um das Playfair Verfahren nachvollziehen zu können sollte das aber reichen. Viel Spaß!

Advertisements
Dieser Beitrag wurde unter .NET, Algorithmen, Beispiel, Beispiel, c#, Kryptologie, Modulo, Modulo, Programmierung, Remainder, Rest, Uncategorized, verschlüsselung abgelegt und mit , , , , , , , , , , , , , , , , , , , , , , , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

w

Verbinde mit %s