Quicksort in C#

Zum Sortieren einer Zahlenreihe haben wir uns bereits den Bubblesort Algorithmus angeschaut. Der hat zwar seinen Zweck erfüllt, ist aber wie bereits erwähnt überhaupt nicht effizient. Eine alternative bildet hier der Quicksort Algorithmus. Dieser kann ebenfalls zum Sortieren von einem mit Elementen gefüllten Feld benutzt werden. In unserem Fall handelt es sich um die Reihe  welche mit Ganzzahligen Werten gefüllt ist. Wer will kann sich mein Videomaterial dazu angucken ansonsten werde ich den Algorithmus in einigen Schritten hier erklären.

 

1

Als erstes müssen wir beim diesem Algorithmus einen Pivot Punkt wählen. Einfachheitshalber werden wir immer das erste Element in einer Reihe als Pivot wählen. In diesem Fall ist a0 = 7 unser Pivot. Somit können wir gleich loslegen. Was machen wir?

  1.  Wir beginnen von links nach einem Element zu suchen welches größer oder gleich unserem Pivot Wert sind (x ≥ 7).
  2.  Gleichzeitig suchen wir von rechts her ein Element welches kleiner oder gleich Pivot ist (x ≤ 7).

Bei Punkt 1 ist die 13 bei a1 gleich die erste Zahl die größer als 7 ist. In Punkt 2 ist die 3 bei a7  die erste Zahl die kleiner als das Pivot Element 7 ist.

2

Haben wir die beiden Zahlen gefunden vertauschen wir sie einfach. Nun fahren wir genau wie oben fort und beginnen unsere Suche von links und rechts. Von links her finden wir die 12 bei a2 die größer ist als die 7. Von rechts ist die 4 bei a3 die erste Zahl die kleiner, gleich Pivot ist. Also vertauschen wir diese beiden ebenfalls.

3

Nun beginnt das Spiel von vorne wir suchen von links und rechts und werden bei den Elementen a3 = 12 von links und a2 = 4 von rechts fündig. Also vertauschen wir diese Elemente.

Wieder suchen wir von links und rechts und werden diesmal wieder bei den Elementen a3 und a2 fündig. Nur dieses Mal hat sich unsere Suche von links mit der Suche von rechts überkreuzt.

4

Da hier eine Überkreuzung stattgefunden hat, vertauschen wir unser Pivot mit dem Element in der Zelle a2.

5

Was ist passiert? Nun die Überkreuzung hat uns signalisiert, dass sich alle Elemente rechts der Zelle a2 größer als das Pivot ist und alle Elemente die links liegen kleiner sind als das Pivot. Also vertauschen wir die 4 und die 7. Somit können wir die 7 in der Zelle a2 als fertig markieren, denn sie befindet sich nun an der richtigen Position und wird nicht mehr verschoben werden.

Gleichzeitig ist noch etwas passiert. Unsere Zahlenreihe wurde in zwei Teile geteilt. Links ist die Reihe a0…a1 und rechts a3…a8. Das bedeutet aber nur, dass wir die oben genannten Regeln jetzt eben auf zwei Listen anwenden müssen. Wir beginnen mit der linken Seite, dabei ist unser Pivot das erste Element also a0.

6

Wir beginnen mit der Suche in der linken Liste. Ein Element dass größer, gleich 4 ist existiert nicht und das einzige Element kleiner, gleich 4 ist die 3 in a1.

7

Nun haben sich die Suchen wieder überkreuzt. Also vertauschen wir Pivot mit dem Element in a1 und markieren die 4 als fertig. Jetzt haben wir wieder zwei Teillisten wobei die linke lediglich ein Element enthält, a0 = 3. Eine Liste mit nur einem Element gilt jedoch als sortiert und kann somit ebenfalls als fertig markiert werden. Jetzt da wir nur noch die rechte Liste haben setzen wir das Pivot bei a3 und verfahren wie gehabt.

8

So machen wir weiter bis alle Elemente in der Zahlenreihe als fertig markiert sind.

9

Bei dem Code handelt es sich um die C# Implementierung des Pseudocodes auf Wikipedia.

//Bekommt eine Liste aus Inegern als Parameter
        public static List<int> QuicksortInt(List<int> array)
        {
            //Eine Liste die nur aus einem Element besteht gilt als sortiert, Abbruchkriterium.
            if (array.Count <= 1)
            {
                return array; //An array of Zero ot one elements is already sorted
            }

            //Das Pivot legen wir immer auf das erste Element in einer Liste
            int pivot = 0;
            List<int> less = new List<int>();
            List<int> greater = new List<int>();

            //Hier teilen wir ein array in ein array mit Elementen die kleiner als das Pivot sind
            //und in eine Liste mit Elementen die größer sind.
            for (int i = 1; i < array.Count; i++)
            {
                if (array[i] <= array[pivot])
                {
                    less.Add(array[i]);
                }
                else
                {
                    greater.Add(array[i]);
                }
            }

            //Hier kombinieren wir die Listen und setzen das Pivot dazwischen.
            List<int> combined = QuicksortInt(less);
            combined.Add(array[pivot]);
            combined.AddRange(QuicksortInt(greater));

            //Liefert sortierte Liste zurück.
            return combined;

        }
Advertisements
Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, c#, Programmierung, Sortieralgorithmus, Uncategorized | Verschlagwortet mit , , , , , , , , | Kommentar hinterlassen

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ß!

Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, c#, Kryptologie, Modulo, Modulo, Programmierung, Remainder, Rest, Uncategorized, verschlüsselung | Verschlagwortet mit , , , , , , , , , , , , , , , , , , , , , , , , | Kommentar hinterlassen

Zellers Kongruenz in C#

Bei Zellers Kongruenz handelt es sich nicht wirklich um einen Algorithmus sondern viel mehr um eine Formel. Sie wurde 1882 von Christian Zeller veröffentlicht und dient dazu den Wochentag eines gegebenen Datums zu Berechnen. Dabei wird zwischen dem Gregorianischen Kalender, den wir heute benutzen und dem Julianischen Kalender unterschieden. Letzterer wurde von Julius Cäsar eingeführt und war mancherorts noch bis in das 20 Jahrhundert gültig.

Ein Datum für den gregorianischen Kalender lässt sich wie folgt berechnen:

ZellerGreg

Hierbei haben die einzelnen Variablen folgende Bedeutung:

  • h: Ist eine ganze Zahl die für den Wochentag steht
  • q: Ist der der Monatstag. Also zB. für den 15.03.1991 ist q=15
  • m: Ist der Monat. Also zB. für den 15.03.1991 ist m=3.
(Wichtig!: Januar und Februar werden nicht als erster und zweiter Monat gezählt. Sie werden zu dem vorherigen Jahr gezählt. Entsprechend ist im Januar m = 13 und Februar m = 14)
 
  • J: Steht für die für die ersten zwei Ziffern des Jahres. Also zB. für den 15.03.1991 ist J=19.
  • K: Steht für die für die letzten zwei Ziffern der Jahresangabe. Also zB. für den 15.03.1991 ist K=91.

Außerdem muss berücksichtigt werden, dass das Ergebnis h uns nicht wie erwartet, einen Wert zwischen 1 und 7 (Montag – Sonntag) liefert. Die Rückgabewerte sehen wie folgt aus.

zellertage

Bevor wir uns an ein Beispiel machen möchte ich noch kurz die eckigen Klammern in der Formel erklären. Diese nennen sich Gaußklammer. Sie treten in zwei Formen auf und können als Auf- bzw. Abrundungsklammer bezeichnet werden. Besser sind sie jedoch als Floor und Ceilingfunktion bekannt (also Boden- und Deckenfunktion). So ist beispielsweise:

floorceiling

So nun da wir alles nötige geklärt haben, nehmen wir einfach den 10.02.2014 als Beispiel. So ergibt sich:

q = 10

m = 14

(Siehe oben, der Februar wird als 14-er Monat des jeweiligen Vorjahres gezählt.)

J = 20

K = 13

(Siehe oben, da der Februar nicht zum Jahr 2014 zählt sondern zu 2013 ist hier K = 13.)

Mit diesen Werten können wir nun den entsprechenden Wochentag wie folgt berechnen:

ZellerExample

Wenn wir jetzt in der obigen Tabelle nachschauen können wir ablesen, dass der 10.02.2014 ein Montag gewesen sein muss.

Glücklicherweise bietet die Math-Bibliothek in .NET beides eine Floor- und eine Ceilingfunktion. So können wir die Berechnung der Zeller Kongruenz für den gregorianischen Kalender wie folgt implementierten.

//Erhält Tag, Monat und Jahr als Argument
        public static int ZellersCongruenceGregorian(double dd, double mm, double yyyy)
        {
            int h = 0;
            double q = dd;
            double m = mm;
            double y = yyyy;
            double J = 0;
            double K = 0;

            #region Hier werden Monat und Jahr angepasst für den Fall, dass es sich um den Januar oder Februar handelt
            switch ((int)m)
            {
                case 1:
                    m = 13;
                    y--;
                    break;
                case 2:
                    m = 14;
                    y--;
                    break;
            }
            #endregion

            #region Da wir das Jahr als Zahl vorliegen haben, müssen wir diese zunächst in J und K umwandeln
            //Wir machen das indem wir die Zahl zu einem String umwandeln.
            string yearString = y.ToString().Trim();
            //Und sie dann in jeweils zwei Teile zerlegen
            J = Int32.Parse(yearString.Substring(0, 2));
            K = Int32.Parse(yearString.Substring(2, 2));
            #endregion

            //Die Formel selbst kann in einer einzelnen Zeile implementiert werden.
            h = (int)((q + Math.Floor(((m + 1) * 26)/10) + K + Math.Floor(K/4) + Math.Floor(J/4) - 2 * J)%7);

            return h;
        }

Analog dazu lässt sich ein Datum im Julianischen Kalender mit folgender Formel berechnen:

zellerJul

Entsprechend müssen wir nur eine Kleinigkeit in der obigen Methode verändern um ZellerCongruenceJulian() zu implementieren.

//Erhält Tag, Monat und Jahr als Argument
        public static int ZellersCongruenceJulian(double dd, double mm, double yyyy)
        {
            int h = 0;
            double q = dd;
            double m = mm;
            double y = yyyy;
            double J = 0;
            double K = 0;

            #region Hier werden Monat und Jahr angepasst für den Fall, dass es sich um den Januar oder Februar handelt
            switch ((int)m)
            {
                case 1:
                    m = 13;
                    y--;
                    break;
                case 2:
                    m = 14;
                    y--;
                    break;
            }
            #endregion

            #region Da wir das Jahr als Zahl vorliegen haben, müssen wir diese zunächst in J und K umwandeln

            string yearString = y.ToString().Trim();
            J = Int32.Parse(yearString.Substring(0, 2));
            K = Int32.Parse(yearString.Substring(2, 2));
            #endregion

            //Wir müssen die Formel nur minimal ändern um einen Wochentag im Julianischen Kalender zu berechnen.
            h = (int)((q + Math.Floor(((m + 1) * 26) / 10) + K + Math.Floor(K / 4) + 5 - J) % 7);

            return h;
        }

Die beiden Methoden geben uns nur Zahlen aus die wir zwar anhand der obigen Tabelle ablesen können, es bietet sich jedoch an eine kleine Methode zu schreiben die die jeweilige Zahl als Wochentag ausspuckt. Hierzu implementieren wir ZellersCongruenceToString():

public static string ZellersCongruenceToString(int h)
        {
            //Hier entscheiden wir welchem Wochentag der gegebene Wert entspricht
            //und liefern den entsprechenden Wochentag als String aus.
            switch(h)
            {
                case 0:
                    return "Saturday";
                    break;
                case 1:
                    return "Sunday";
                    break;
                case 2:
                    return "Monday";
                    break;
                case 3:
                    return "Tuesday";
                    break;
                case 4:
                    return "Wednesday";
                    break;
                case 5:
                    return "Thursday";
                    break;
                case 6:
                    return "Friday";
                    break;
                default:
                    return "Could not convert given number to a String.";
                    break;
            }
        }
Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, c#, Mathematik, Modulo, Programmierung, Uncategorized | Verschlagwortet mit , , , , , , , , , , , , , , , , , | Kommentar hinterlassen

Lokales Sequenzalignment mit dem Smith-Waterman Algorithmus in C#

Wir haben festgestellt, dass der Needleman-Wunsch Algorithmus sich gut dazu eignet ein globales Alignement zweier Sequenzen zu berechnen. Dabei werden beide Sequenzen über ihre gesamte Länge aligniert. Das bedeutet je weniger sich die beiden Sequenzen ähneln, desto mehr Lücken (gaps) wird das resultierende Alignement aufweisen. Dieses Verfahren eignet sich besonders wenn beide Sequenzen ungefähr dieselbe Länge haben und möglicherweise ähnlich sind.

Was ist jedoch wenn wir nur eine teilweise Übereinstimmung der Sequenzen vermuten? Wenn wir annehmen, dass eine Übereinstimmung nur in kleineren Regionen einer längeren Sequenz vorkommt benutzen wir den Smith-Waterman Algorithmus.

Bezüglich der Implementierung unterscheiden sich die beiden Verfahren nur in wenigen Punkten. Auch der Smith-Waterman Algorithmus bedient sich der dynamischen Programmierung. Das bedeutet wir können die Berechnung eines lokalen Alignements in drei Schritte unterteilen, genau wie beim Needleman-Wunsch Algorithmus.

  1. Initialisierung einer Matrix
  2. Berechnung des Score der Matrix
  3. Traceback

Doch worin genau sich die Verfahren unterscheiden sieht man wohl am besten an einem Beispiel. Nehmen wir folgende zwei Sequenzen:

A=‘MISSISSIPPI‘

B=‘ISSP‘

Auch hier brauchen wir Gapkosten f, einen Match- und Mismatchscore als Eingabeparameter für den Algorithmus. Wenn man Elemente der Sequenzen vergleicht, liefert eine Bewertungsfunktion w(x, y) den Matchscore wenn die Elemente identisch sind und entsprechend den Mismatchscore wenn sie sich unterscheiden.

f = -1

MatchScore = 2

MismatchScore = -1

Hier steht m für den MatchScore und mm für den MismatchScore.

Hier steht m für den MatchScore und mm für den MismatchScore.

Die Unterschiede beginnen direkt bei der Initialisierung der Matrix. Beim Needleman-Wunsch Algorithmus werden die erste Zeile mit i * (-1) initialisiert und die erste Spalte mit j * (-1). Beim Smith-Waterman hingegen werden einfach sämtliche Initialisierungsfelder auf 0 gesetzt.

initSW

Ein weiterer Unterschied zu einem globalen Alignement besteht in der Berechnung des Scores. Zwar liefern auch hier die jeweiligen Vorgängerzellen die Werte für die aktuelle Zelle, jedoch dürfen wir diesmal die Werte nicht kleiner als 0 werden lassen. Aus diesem Grund werden Werte in der Score Matrix wie folgt berechnet.

scoreSW

Nehmen wir die Zelle (1,1) hier wird das Element „M“ mit dem Element „I“ verglichen. Also gucken wir uns die Vorgängerzellen an.

(Diagonal) F(i-1, j-1) + w(x, j) = F(0, 0) + w(“M”,”I”) = 0 – 1 = -1

(Links) F(i-1, j) + f = F(0, 1) + f = 0 + (-1) = -1

(Oben) F(i, j-1) + f = F(1, 0) + f = 0 + (-1) = -1

(Vierte Option)    F(i, j) = 0

Da wir uns bei der Berechnung stets für den größtmöglichen Wert entscheiden müssen nehmen wir in diesem Fall natürlich die vierte Option, nämlich 0.

firstCellSW

Wir werden auch in diesem Fall zeitgleich eine Matrix erstellen die uns beim Traceback helfen soll. Der Unterschied zu Needleman-Wunsch besteht darin, dass wir immer wenn der vierte Fall eintritt auch in die Traceback-Matrix eine 0 eintragen. Da auch bei ihrer Initialisierung 0 in die Zellen eingetragen wird, ist die Traceback-Matrix zu diesem Zeitpunkt identisch mit der Scoring-Matrix. So berechnen wir die beiden Matrizen und das Ergebnis sieht wie folgt aus.

scoreMatrixSW

Die Scoring Matrix.

Anders als bei den Needleman-Wunsch Algorithmus liegt der Score der Matrix in der Zelle mit dem höchsten Wert, in diesem Fall 7. Dieser bestimmt auch den Startpunkt des Traceback.

tracebackmatrixSW

Die Traceback Matrix.

Die Einträge in der Traceback Matrix weisen jeweils darauf hin welche Vorgängerzelle den aktuellen Wert geliefert hat. Dabei steht D für diagonal, L für Links und U für „Up“ also oben. Wir beginnen mit dem Score der Matrix und schreiben solange die Alignements bis wir auf eine Zelle mit dem Wert 0 treffen, diese bildet nämlich das Abbruchkriterium für das Traceback. Das mitschreiben der Alignements erfolgt ansonsten genau wie im Needleman-Wunsch Verfahren.

finalTracebackSW

Das Traceback, wobei eine 0 das Abbruchkriterium bildet.

alignmentSW

Das resultierende Alignement.

Wie man sieht wird im Gegensatz zum globalen Alignement nicht über die ganze Länge aligniert sondern nur auf einem begrenzten, also lokalen Bereich.

Auch hier werden wir die ScoreFunction-Methode brauchen. Darin hat sich aber nichts im Vergleich zum NW-Verfahren geändert.

//Bekommt die zu vergleichenden Buchstaben, den Match- und Mismatch-Score als Parameter
        private static int ScoreFunction(char a, char b, int matchScore, int mismatchScore)
        {
            //Wenn die Buchstaben gleich sind ist der Match-Score der Rückgabewert.
            //Wenn nicht gib den Mismatch-Score zurück.
            return a == b ? matchScore : mismatchScore;
        }

Die Methode Align() hat sich dagegen an mehreren Stellen geändert, beispielsweise bei der Initialisierung. Außerdem benutzen wir jetzt eine Variable score[2] um uns die Zelle mit dem Höchsten Wert zu merken. Auch dürfen wir negative Werte nicht mehr zulassen. Außerdem kann die Traceback-Matrix jetzt auch eine 0 enthalten.

//Die Align-Methode bekommt die beiden Sequenzen A und B, den Gap-Penalty, Match- und Mismatch-Score als Parameter.
        public static string[] Align(string sequenceA, string sequenceB, int gapPenalty, int matchScore, int mismatchScore)
        {
            //Hier werden beide Matrizen initialisiert. Die Scoring- und Traceback-Matrix.
            #region Initialize
            int[,] matrix = new int[sequenceA.Length + 1, sequenceB.Length + 1];
            char[,] tracebackMatrix = new char[sequenceA.Length + 1, sequenceB.Length + 1];
            matrix[0, 0] = 0;

            //Befülle die erste Reihe der Matrizen.
            for (int i = 1; i < sequenceA.Length + 1; i++)
            {
                matrix[i, 0] = 0;
                tracebackMatrix[i, 0] = '0';
            }

            //Befülle die erste Spalte der Matrizen.
            for (int i = 1; i < sequenceB.Length + 1; i++)
            {
                matrix[0, i] = 0;
                tracebackMatrix[0, i] = '0';
            }
            #endregion

            //Hier werden die Werte für die Scoring-Matrix berechnet. Zeitgleich befüllen
            //wir die Traceback-Matrix.
            #region Scoring

            //Diese Variable benutzen wir um uns die Zelle mit dem Höchsten Wert zu merken.
            //Diese wird uns beim Traceback als Startpunkt dienen.
            int[] score = new int[2];

            for (int i = 1; i < sequenceA.Length + 1; i++)
            {
                for (int j = 1; j < sequenceB.Length + 1; j++)                 {                     //Lese und berechne die Werte der Vorgängerzellen.                     int diagonal = matrix[i - 1, j - 1] + ScoreFunction(sequenceA[i - 1], sequenceB[j - 1], matchScore, mismatchScore);                     int links = matrix[i - 1, j] + gapPenalty;                     int oben = matrix[i, j - 1] + gapPenalty;                     //Der höchste Wert wird eingetragen.                     matrix[i, j] = Math.Max(Math.Max(oben, Math.Max(links, diagonal)),0);                     //Hier wird geprüft ob die aktuelle Zelle als Score für die matrix taugt.                     if(matrix[i,j] > matrix[score[0],score[1]])
                    {
                        score[0] = i;
                        score[1] = j;
                    }

                    //Finde raus welche der Zellen den Wert geliefert hat und trage
                    //dies in die Traceback-Matrix ein.
                    if (matrix[i, j] == diagonal && i > 0 && j > 0)
                    {
                        tracebackMatrix[i, j] = 'D';
                    }
                    else if (matrix[i, j] == links)
                    {
                        tracebackMatrix[i, j] = 'L';
                    }
                    else if (matrix[i, j] == oben)
                    {
                        tracebackMatrix[i, j] = 'U';
                    }
                    else if (matrix[i, j] == 0)
                    {
                        tracebackMatrix[i, j] = '0';
                    }
                }
            }
            #endregion

            //Hier wird einfach die Traceback-Methode aufgerufen und liefert uns das Alignment.
            #region Traceback
            return TraceBack(tracebackMatrix, score,sequenceA, sequenceB);
            #endregion

        }

Die einzige Veränderung in der Methode Traceback() ist der Score der mit als Parameter übergeben werden muss und als Startzelle fungiert.

//Eine TraceBack-Matrix und die beiden Sequenzen sind die Paramter für das Traceback.
        //Außerdem wird hier die Position der Score-zelle an die Methode übergeben.
        private static string[] TraceBack(char[,] tracebackMatrix,int[] score ,string sequenzA, string sequenzB)
        {
            //Lege die Startposition anhand des Scores fest
            int i = score[0];
            int j = score[1];

            StringBuilder alignedSeqA = new StringBuilder();
            StringBuilder alignedSeqB = new StringBuilder();

            //Das Traceback wird asugeführt solange wir uns nicht in der Zelle (0,0) befinden.
            while (tracebackMatrix[i, j] != '0')
            {
                switch (tracebackMatrix[i, j])
                {
                    case 'D':
                        alignedSeqA.Append(sequenzA[i - 1]);
                        alignedSeqB.Append(sequenzB[j - 1]);
                        i--;
                        j--;
                        break;
                    case 'U':
                        alignedSeqA.Append("-");
                        alignedSeqB.Append(sequenzB[j - 1]);
                        j--;
                        break;
                    case 'L':
                        alignedSeqA.Append(sequenzA[i - 1]);
                        alignedSeqB.Append("-");
                        i--;
                        break;

                }
            }

            string[] alignments = new string[2];

            //Da wir die Zeichen jeweils rechts an die Alignments angefügt haben,
            //rufen wir hier die Reverse-Methode um die Strings umzudrehen.
            alignments[0] = new string(alignedSeqA.ToString().Reverse().ToArray());
            alignments[1] = new string(alignedSeqB.ToString().Reverse().ToArray());

            //Der Rückgabewert ist ein array welches beide alignments enthält.
            return alignments;

        }
Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, Bioinformatik, c#, global alignment, globales alignment, needleman-wunsch, Programmierung, Sequence alignmenet, Sequenzalignment, Uncategorized | Verschlagwortet mit , , , , , , , , , , , , , , , , , | 7 Kommentare

Einführung in das Binärsystem am Beispiel der XOR Verschlüsselung in C#

Das XOR Verfahren ist an sich trivial. Deshalb beginne ich den Artikel mit einem Crashkurs zum Binärsystem und einigen der dazu gehörenden Operatoren.

Eine Maschine verarbeitet Informationen in Form von Binärfolgen. Das heißt, dass Information als eine Folge der Zahlen 1 und 0 (true und false) dargestellt wird. Der Computer kann diese Folgen als Zahlen interpretieren. So entspricht die Zahl 42 im Binärsystem der Folge 101010.

Um 42 von dezimal nach binär umzurechnen, teilen wir unsere Zahl immer wieder durch zwei und notieren uns dabei die Modulo Werte.

42 / 2 = 21        | 0

21 / 2 = 10        | 1

10 / 2 = 5          | 0

5 / 2 = 2           | 1

2 / 2 = 1           | 0

1 / 2 = 0           | 1

Jetzt können wir an den Restwerten die Binärdarstellung der Zahl 42 von unten nach oben ablesen, also 101010. Um es noch etwas anschaulicher zu machen kann man sich diese Darstellung als eine Folge von zweier Potenzen vorstellen.

binary

Nun möchte man aber nicht nur Zahlen abbilden sondern auch Textzeichen. Hierbei werden Daten meist als Folge von acht Bit bzw. einem Byte dargestellt. Also besteht ein Byte aus acht Einsen oder Nullen und kann somit insgesamt 28 Werte annehmen. Diese Werte können benutzt werden um Zeichen zu repräsentieren bzw. zu codieren. Wie es beispielsweise mit den ASCII Zeichen gemacht wird. So steht die Zahl 42 beispielsweise für ‚*‘.

ascii

ASCII-Zeichen mit den entsprechenden Dezimalwerten. (Bildquelle)

Binärfolgen lassen sich aber auch manipulieren. Hierfür gibt es mehrere Operatoren die aus dem Gebiet der Logik stammen und auf Bits bzw. Bytes angewandt werden können. Gehen wir einige dieser Operatoren kurz durch.

Und-Operator (AND)

Nehmen wir zwei Bits 1 und 0. So liefert der Und-Operator 0. Nehmen wir 1 und 1 so liefert der Operator 1. Wir sehen also beide Bits müssen true sein damit der Und-Operator 1 liefert, denn ‚Wahr UND Wahr‘ ist ‚Wahr‘. Wir verwenden das Zeichen für das logische Und ‚˄‘ welches sonst auch als ‚&&‘ in C# beschrieben werden kann. Die möglichen Kombinationen für diesen Operator sehen wie folgt aus.

1 ˄ 1 = 1

1 ˄ 0 = 0

0 ˄ 1 = 0

0 ˄ 0 = 0

Oder-Operator (OR)

Im Gegensatz zum Und-Operator müssen bei dem Oder-Operator nicht unbedingt beide Werte wahr sein. Es können aber auch beide Werte wahr sein. Das logische Oder wird als ‚˅‘ dargestellt oder alternativ als ‚||‘ in C#. So ergeben sich folgende Kombinationen.

1 ˅ 1 = 1

1 ˅ 0 = 1

0 ˅ 1 = 1

0 ˅ 0 = 0

XOR-Operator (entweder..oder)

Im Gegensatz zum Oder-Operator ist XOR ein wörtliches „entweder … oder …“ und wird auch als „exklusives oder“ bezeichnet. So darf entweder nur das eine oder nur das andere Bit wahr sein. In C# ist ‚^‘ der Operator für ‚entweder oder‘, wir verwenden XOR.

1 XOR 1 = 0

1 XOR 0 = 1

0 XOR 1 = 1

0 XOR 0 = 0

Eben dieser XOR-Operator kann dazu benutzt werden um Klartext zu chiffrieren. Nun da wir wissen wie Zeichen binär dargestellt werden können und wie das XOR funktioniert, können wir folgendes Beispiel betrachten.

 Klartext: ‚Geheimnis

Schlüssel: ‚Code

Wir verschlüsseln das Wort ‚Geheimnis‘ mit Hilfe des Schlüsselwortes ‚Code‘. Also nehmen wir als erstes den Buchstaben ‚G‘. Wenn wir nun in der ASCII Tabelle nachschauen sehen wir, dass ‚G‘ den Wert 71 hat. Der Schlüsselbuchstabe C entspricht dem ASCII Wert 67. Um die XOR-Verschlüsselung anzuwenden müssen die jeweiligen Zeichen Binär dargestellt werden.

ascii_bin

Und nun wenden wir auf diese Binärzahlen den XOR-Operator an:

GC

Also ist das erste Zeichen des verschlüsselten Textes 4. Und so machen wir Zeichen für Zeichen weiter. Als nächstes wird der Buchstabe ‚e‘ mit dem Buchstaben ‚o‘ verschlüsselt.

XOR

Sollte der Schlüssel nicht lang genug sein, kann dieser erweitert werden. So ergibt sich folgende Verschlüsselung:

XORcomplete

Somit entspricht der Verschlüsselte Text der Zahlenfolge {4,10, 12, 0, 42, 2, 10, 12, 48}. Glücklicherweise macht es das .NET-Framework einem leicht die XOR-Verschlüsselung zu implementieren. Wichtig dabei ist, dass wir gleich am Anfang der Methode EncryptXOREng() die Methode AdjustKeyLength() benutzen um den Schlüssel wie im obigen Beispiel zu verlängern. Diese Methode findet ihr hier. Die verschlüsselungs Methode liefert uns ein Array welches die einzelnen Zahlen des Chiffre enthält.

//Die methode bekommt den Klartext und den Schlüsseltext als Parameter
        public static byte[] EncryptXOREng(string plainText,string keyText)
        {
            //Diese Methode benutzen wir um die Lägne des Schlüsseltextes
            //an die des Klartextes anzupassen.
            keyText = AdjustKeyLength(plainText,keyText);

            //Mit diesem Befehl zaubern wir aus dem Klartext ein array,
            //welches die Indizes der ASCII Zeichen aus dem Klartext enthält.
            byte[] binaryPlainText = System.Text.Encoding.ASCII.GetBytes(plainText);

            //Mit diesem Befehl zaubern wir aus dem Schlüsseltext ein array,
            //welches die Indizes der ASCII Zeichen aus dem Schlüsseltext enthält.
            byte[] binaryKeyText = System.Text.Encoding.ASCII.GetBytes(keyText);

            //Nun iterieren wir durch jedes Zeichen im Klartext.
            for(int i = 0;i<plainText.Length;i++)
            {
                // Mit dem Befehl '^' verschlüsseln wir jeden Buchstaben im KlarText,
                //mit dem entsprechenden Buchstaben des Schlüsseltextes
                binaryPlainText[i] ^=  binaryKeyText[i];
            }

            //Der Rückgabewert ist ein überschriebenes byte-array welches die Verschlüsselung
            //als Folge ganzer Zahlen enthält.
            return binaryPlainText;
        }

Die XOR-Verschlüsselung ist symmetrisch. Das bedeutet, dass wir entschlüsseln können indem wir den XOR-Operator diesmal auf Chiffre und Schlüsseltext anwenden. Um eine XOR-Chiffre mit einem gegebenen Schlüsseltext wieder zu entschlüsseln benutzen wir die Methode DecryptXOREng().

//Die methode bekommt das Zahlen-Array der Chiffre und den Schlüsseltext als Parameter
        public static string DecryptXOREng(byte[] chiffreNumberArray, string keyText)
        {
            //Hier werden wir den entschlüsselten Text speichern
            string plainText;

            //Um die AdjustKeyLength()-Methode u benutzen müssen wir die Länge des Klartextes
            //aus der Länge des Chiffre-Array auslesen. Dazu erstellen wir ein string-Array
            //mit der Länge des Chiffre-Array.
            string[] cipher = new string[chiffreNumberArray.Length];

            //Diese Methode benutzen wir um die Lägne des Schlüsseltextes
            //an die des Klartextes anzupassen.
            keyText = AdjustKeyLength(cipher.ToString(), keyText);

            //Mit diesem Befehl zaubern wir aus dem Schlüsseltext ein array,
            //welches die Indizes der ASCII Zeichen aus dem Schlüsseltext enthält.
            byte[] binaryKeyText = System.Text.Encoding.ASCII.GetBytes(keyText);

            //Nun iterieren wir durch jeden Eintrag im Chiffre.
            for (int i = 0; i < chiffreNumberArray.Length; i++)
            {
                //Mit dem Befehl '^' entschlüsseln wir jeden Eintrag im Chiffre,
                //mit dem entsprechenden Eintrag des Schlüsseltextes.
                chiffreNumberArray[i] ^= binaryKeyText[i];

            }

            //Hier wandeln wir jeden Eintrag im Chiffre-Array von Zahl nach ASCII Zeichen.
            plainText = System.Text.Encoding.ASCII.GetString(chiffreNumberArray);

            //Unser Rückgabewert ist der entschlüsselte Klartext.
            return plainText;
        }
Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, c#, Chiffre, Kryptologie, Mathematik, Modulo, Modulo, Programmierung, Remainder, Rest, Uncategorized, verschlüsselung | Verschlagwortet mit , , , , , , , , , , , , , , , , | 1 Kommentar

Die Vigenère-Verschlüsselung in C#

Ich empfehle den Artikel Caesar Chiffre/Verschlüsselung in C# zu lesen bevor man sich auf die Vigenère Verschlüsselung stürzt. Dort stellen wir fest, dass eine Cäsar-Verschlüsselung leicht dechiffriert werden kann, beispielsweise durch einfaches Raten oder ausprobieren. Auch die Frequenzanalyse macht die Cäsar-Verschlüsselung anfällig. Das ist genau der Mangel den Blaise de Vigenère (1523-1596) mit seiner Verschlüsselung verbessert hat. Dieses Verfahren galt fast 300 Jahre lang als unknackbar.

Um einen verschlüsselten Text vor Frequenzanalyse zu schützen, hat Vigenère den numerischen Schlüssel der Cäsar-Verschlüsselung durch einen Schlüssel in Textform ersetzt. Somit wird nicht eine einzelne Zahl als Schlüssel verwendet sondern immer der jeweilige Stellenwert des Buchstaben im Schlüssel. Nehmen wir als Beispiel:

K=‘MYKEY‘

T=‘GEHEIMNIS‘

alphabet2

Dabei ist K der Schlüssel und T der Klartext. Da der Schlüssel Kürzer ist als der Text müssen wir ihn erweitern. Daraus ergibt sich folgende Konstellation:

example1

So ist 12 der Schlüssel der zum Buchstaben M gehört, während das G im Klartext der Zahl 6 entspricht. Und nun wird nichts anderes gemacht als die Definition der Cäsar-Verschlüsselung anzuwenden. Wenn G dem Geheimtext entspricht, so ist

G = (T + K)mod26 = (‚G‘ + ‘M’)mod26 = (6 + 12)mod26 = 18mod26 = 18 = ’S’

G = (T + K)mod26 = (‚E‘ + ‘Y’)mod26 = (4 + 24)mod26 = 28mod26 = 2 = ’C’

G = (T + K)mod26 = (‚H‘ + ‘K’)mod26 = (7 + 10)mod26 = 17mod26 = 17 = ’R’

G = (T + K)mod26 = (‚E‘ + ‘E’)mod26 = (4 + 4)mod26 = 8mod26 = 8 = ’I’

G = (T + K)mod26 = (‚I‘ + ‘Y’)mod26 = (8 + 24)mod26 = 32mod26 = 6 = ’G’

G = (T + K)mod26 = (‚M‘ + ‘M’)mod26 = (12 + 12)mod26 = 24mod26 = 24 = ’Y’

G = (T + K)mod26 = (‚N‘ + ‘Y’)mod26 = (13 + 24)mod26 = mod26 = 11 = ’L’

G = (T + K)mod26 = (‚I‘ + ‘K’)mod26 = (8 + 10)mod26 = 18mod26 = 17 = ’S’

G = (T + K)mod26 = (‚S‘ + ‘E’)mod26 = (18 + 4)mod26 = 22mod26 = 21 = ’W’

Somit lautet der Verschlüsselte Text G=‘SCRIGYLSW. Anschaulich lässt sich das Verfahren im Vigenère-Quadrat darstellen. Daran können wir die Buchstaben des Geheimtextes direkt ablesen. Nehmen wir den ersten Buchstaben aus dem obigen Beispiel, mit T = ‚G‘ und K=‘M‘.

Das Vigenère-Quadrat (Bildquelle)

Das Vigenère-Quadrat (Bildquelle)

An dieser Stelle haben wir schon eine Liste an Anforderungen für eine Implementierung der Verschlüsselungsmethode. Die Funktionsweise unserer Methode soll wie folgt aussehen:

UML

Unsere Verschlüsselungsmethode bekommt den Klartext T und den Schlüsseltext K als Parameter. Innerhalb der Verschlüsselung rufen wir die Methode AdjustKey() auf. Diese Methode erweitert unseren Schlüssel so lange bis die Länge des Schlüssels nicht mehr kleiner als die des Klartexts ist (siehe Beispiel oben).

//Bekommt den Klartext und den Schlüssel als Parameter.
        public static string AdjustKeyLength(string text,string keystring)
        {
            StringBuilder key = new StringBuilder(keystring);

            //Solange der Schlüsseltext kürzer als der Klartext ist, wird er erweiter.
            while(text.Length > key.Length)
            {
                key.Append(keystring);
            }

            //Gibt den angepassten Schlüsseltext zurück.
            return key.ToString();
        }

In der Methode EncryptTextEng() Iterieren wir jetzt durch den Klartext und erstellen dabei den verschlüsselten Text. Dabei benutzen wir genau wie im obigen Beispiel den Modulo zur Berechnung der verschlüsselten Buchstaben.

//Bekommt den Klartext und Schlüssel als Parameter.
        public static string EncryptTextEng(string plainText, string keyText)
        {
            StringBuilder encryption = new StringBuilder();

            //damit uns der die Berechnung der Chiffre leichter fällt schreiben      wir alle Buchstaben groß
            //und entfernen alle whitespaces
            plainText = plainText.ToUpper();
            plainText = plainText.Replace(" ","");
            keyText = keyText.ToUpper();
            keyText = keyText.Replace(" ", "");

            //Definiere Alphabet
            char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();

            //Passe Schlüssellänge an.
            string key = AdjustKeyLength(plainText,keyText);

            //Berechne jeden einzelnen Buchstaben im Text
            for (int i = 0; i < plainText.Length;i++)
            {
                encryption.Append(alphabet[HelperClass.Modulo(Array.IndexOf(alphabet,plainText[i]) + Array.IndexOf(alphabet,key[i]),26)]);
            }

            //Der Verschlüsselte Text als Rückgabe.
            return encryption.ToString();
        }

Nicht im Diagramm ist die Entschlüsselungsmethode, DecryptTextEng() hat nur zwei Dinge die wir in EncryptTextEng() ändern müssen. Zuerst Mal bekommt diese Methode nicht den Klartext sondern den verschlüsselten Text als Parameter. Außerdem rechnen wir an dieser Stelle nicht

G = (T + K)mod26

Sondern entschlüsseln mit

G = (T – K)mod26

//Verschlüsselter Text als Parameter und nicht Klartext
        public static string DecryptTextEng(string chiffre, string keyText)
        {

            //damit uns der die Berechnung der Chiffre leichter fällt schreiben    wir alle Buchstaben groß 
            //und entfernen alle whitespaces
            chiffre = chiffre.ToUpper();
            chiffre = chiffre.Replace(" ","");
            keyText = keyText.ToUpper();
            keyText = keyText.Replace(" ", "");

            StringBuilder encryption = new StringBuilder();
            char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
            string key = AdjustKeyLength(chiffre, keyText);

            for (int i = 0; i < chiffre.Length; i++)
            {
                //(T - K)mod26 anstatt (T + K)mod26
                encryption.Append(alphabet[HelperClass.Modulo(Array.IndexOf(alphabet, chiffre[i]) - Array.IndexOf(alphabet, key[i]), 26)]);
            }

            return encryption.ToString();
        }

Zum Schluss möchte ich noch zwei Dinge anmerken. Zum einen ist die Methode AdjustKey() nicht optimal. Da der Schlüssel immer wieder einfach angehängt wird, könnte die Methode einen unnötig langen Schlüsseltext produzieren. Dies ist vor allem bei sehr langen Schlüsseln ein Problem.

Außerdem ist die Vigenère Verschlüsselung, bei allen ihren Vorteilen gegenüber der Cäsar Verschlüsselung, auch nicht hundert prozentig resistent gegen die Frequenzanalyse.

Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, c#, Chiffre, Kryptologie, Mathematik, Modulo, Modulo, Programmierung, verschlüsselung | Verschlagwortet mit , , , , , , , , , , , , , , , , , , , | 2 Kommentare

Globales Sequenzalignment mit dem Needleman-Wunsch-Algorithmus in C#

Wenn es darum geht in der Bioinformatik eine funktionelle oder evolutionäre Verwandschaft zwischen Nukleotid- oder Aminosäuresequenzen nachzuweisen, so ist der Needleman-Wunsch-Algorithmus wohl einer der ersten über die man stolpert. Nukleotide und Aminosäuren werden durch Buchstaben dargestellt und müssen so angeordnet werden, dass man Mutationen (dargestellt durch Fehlpaarung), Deletionen oder Insertionen (dargestellt durch Gaps, „-„) ablesen kann. Dabei gilt, mehr gleiche oder ähnliche Elemente in gleicher Reihenfolge, bedeuten mehr Übereinstimmung.

Der Needleman-Wunsch-Algorithmus bedient sich der Methode der Dynamischen Programmierung. Hierbei wird eine Scoring-Matrix initialisiert anhand welcher dann das Alignement selbst erstellt wird. Das ganze Verfahren kann man generell in drei Schritte unterteilen.

  1. Initialisierung der Scoring-Matrix (befülle Matrix mit initialen Werten)
  2. Berechnung der Scoring-Matrix (berechne alle Werte in der Matrix)
  3. Traceback (benutze die Matrix um ein Alignement zu erstellen)

Doch was brauchen wir eigentlich alles für so ein Alignment? Nun zuerst brauchen wir natürlich die zwei Strings die wir vergleichen wollen.

a=„ACTCCTTAA“

b=„ATCCAA“

Nun brauchen wir noch drei weitere Werte. Die Gapkosten (hier f) für die Bewertung einer Insertion oder Deletion und den Match- bzw. den Mismatchscore. Wir nehmen:

f = -1

MatchScore =  1

MismatchScore = -1

Außerdem brauchen wir noch eine Bewertungsfunktion. Diese bekommt zwei Elemente  der Sequenz als Parameter. Falls diese identisch sind liefert die Funktion den Match-Score, wenn nicht dann den Mismatch-Score. Die Bewertungsfunktion ist wie folgt definiert:

Hier steht m für den MatchScore und mm für den MismatchScore.

Hier steht m für den MatchScore und mm für den MismatchScore.

Nun können wir mit der Initialisierung der beginnen. Nehmen wir zunächst eine  Matrix F(m+1 x n+1), wobei m die Länge des Strings a und n die Länge des Strings b ist. Dabei ist F(0,0) = 0.

Schritt 1 der Initialisierung.

Schritt 1 der Initialisierung.

Im zweiten und letzten Schritt der Initialisierung wird wie folgt vorgegangen:

F(i,0) = F(i -1, 0) – 1 und F(0,j) = F(0, j – 1) – 1

Das bedeutet jede Zelle der Ersten Zeile enthält den Wert der vorhergehenden Zelle – 1. Jede Zelle der ersten Spalte enthält den Wert der vorhergehenden Zelle – 1.

matrix2

Nun können wir uns dem zweiten Schritt des Algorithmus widmen, dem Befüllen der Matrix. Dabei wird der Wert in der Zelle F(m+1 x n+1) (also ganz unten rechts) als der Score der Matrix bezeichnet. Die einzelnen Werte werden wie folgt berechnet.

F(i,j) ist die aktuelle Zelle. w(x,y) ist die Bewertungsfunktion. f steht für die Gapkosten.

F(i,j) ist die aktuelle Zelle, w(x,y) ist die Bewertungsfunktion, f steht für die Gapkosten.

Das sieht auf den ersten Blick nicht trivial aus, ist aber recht simpel. Nehmen wir dazu als Beispiel gleich die erste Zelle F(1,1) hier werden die Buchstaben „A“ und „A“ verglichen. Jetzt werden drei Werte berechnet, jeweils aus den Vorgängerzelle. Als erstes gucken wir uns die diagonale Vorgängerzelle an, F(0,0). Hierzu benutzen wir die erste Zeile in der Formel.

(Diagonal)F(i-1,j-1) + w(x,j) = F(0,0) + w(‚A‘,’A‘) = 0 + 1 = 1

Wie oben bereits erwähnt bekommt w(x,y) zwei Buchstaben übergeben und liefert uns entweder den Match- oder Mismatchscore zurück. In diesem Fall klar den Matchscore weil ‚A’=’A‘. Nun nehmen wir uns die obere und linke Vorgängerzelle vor.

(Links) F(i-1,j)+f = F(0,1) + (-1) = -1 + (-1) = -2

(Oben) F(i,j-1)+f = F(1,0)+(-1) = -1 + (-1) = -2

Wie in der Formel beschrieben gilt es jetzt den größten dieser Werte für die aktuelle Zelle zu nehmen also ist F(i,j) = F(1,1) = 1.

Der Wert der Zelle F(1,1) wird aus den drei Vorgängerzellen errechnet.

Der Wert der Zelle F(1,1) wird aus den drei Vorgängerzellen errechnet.

An dieser Stelle möchte ich anmerken, dass es mehrere Möglichkeiten gibt das Traceback auszuführen. Ich mache hier etwas um mir das Traceback zu erleichter. Bei der Berechnung der Matrix, fülle ich gleichzeitig eine zweite Matrix aus. Nur in dieser Matrix speichere ich einfach Buchstaben, quasi eine Matrix die sich merkt welche der Vorgängerzellen den aktuellen Wert geliefert haben. Dabei steht ‚D‘ für diagonal, ‚L‘ für Links und ‚U‘ für Up, also oben :). Da die diagonale Zelle den aktuellen Wert 1 geliefert hat tragen wir in unsere zweite Matrix F(1,1) = ‚D‘ ein. So sollte unsere zweite Matrix zu diesem Zeitpunkt aussehen.

zweitematrix

Die erste Zeile und Spalte werden bereits bei der Initialisierung ausgefüllt und sehen immer so aus.

Wichtig dabei ist auch, dass ich in die allererste Zelle den Wert 0 eintrage. Warum wir das Ganze machen und wie es uns später hilft sehen wir gleich wenn wir zum Traceback dem letzten Schritt des Algorithmus kommen. Hier könnt ihr aber zuerst sehen wie die beiden Matrizen aussehen wenn wir sie komplett ausgefüllt haben.

Der Score der Matrix beträgt 3.

Der Score der Matrix beträgt 3.

Die dazugehörige Traceback-Matrix.

Die dazugehörige Traceback-Matrix.

An dieser Stelle können wir mit dem Traceback beginnen. Dieses wird uns das Alignement liefern. Das funktioniert indem wir beim Score, also rechts unten anfangen und den „am besten bewerteten“ Weg zurück verfolgen. Wie bereits erwähnt gibt es dazu mehrere Ansätze. Wir könnten das Alignement aus der Scoring-Matrix auslesen indem wir berechnen welche der Vorgängerzellen jeweils den aktuellen Wert geliefert hat. Ich habe mich hier entschieden aber eine zweite Matrix, die Traceback Matrix zu benutzen. Hier habe wir in jeder Zelle bereits vermerkt welche Zellen die Werte geliefert haben. Jetzt gehen wir Zelle für Zelle durch bis wir die Zelle F(0,0) erreichen. Dabei gehen wir wie folgt vor:

D → Die diagonale Vorgängerzelle F(i-1,j-1) hat den Wert geliefert → Die beiden Elemente (Buchstaben) werden jeweils Alignement a und b hinzugefügt. Wir bewegen uns auf die Zelle F(i-1,j-1).

U → Die obere Vorgängerzelle F(i,j-1) hat den Wert geliefert → Alignement a wird eine Gap (‚-‚) hinzugefügt. b bekommt den jeweiligen Buchstaben dazu. Wir bewegen uns auf die Zelle F(i,j-1).

L → Die linke Vorgängerzelle F(i-1,j) hat den Wert geliefert → Alignement a wird der entsprechende Buchstabe hinzugefügt. b bekommt eine Gap (‚-‚) dazu. Wir bewegen uns auf die Zelle F(i-1,j).

Fangen wir mit dem Score rechts unten an. Die Zelle hat den Wert ‚D‘. Wir bewegen uns auf die diagonale Zelle und fügen beiden Alignements die Buchstaben hinzu.

‚A‘

‚A‘

Die nächste Zelle hat wieder den Wert ‚D‘. Wir bewegen uns wieder auf die Diagonale Vorgengängerzelle und fügen den Strings die dazugehörigen Buchstaben an.

‚AA‘

‚AA‘

Diese Zelle hat den Wert ‚L‘. Wir bewegen uns auf die linke Zelle. Alignement a bekommt den Buchstaben. b wird eine Gap angehängt.

‚TAA‘

‚-AA‘

Wichtig ist, dass wir die jeweiligen Zeichen immer an den Anfang der Alignements setzten oder aber an das Ende dann aber das Alignement umdrehen. So gehen wir vor bis wir die Zelle F(0,0) erreicht haben und unser Alignement fertig ist.

traceback2

Das Traceback fängt beim Score an und endet in der Zelle (0,0).

Der Algorithmus liefert dieses Alignment.

Der Algorithmus liefert dieses Alignement.

Wichtig hier ist, dass dies nicht die einzige Lösung ist. Abhängig davon welche Werte bei der Erstellung der Matrix zuerst geprüft werden, kann das Traceback variieren. Beispielsweise wenn zwei Zellen den gleichen Wert liefern.

Bei der Implementierung habe ich beschlossen den ganzen Algorithmus in drei Methoden aufzuteilen. Zuerst die einfachste, die Bewertungsfunktion.

//Bekommt die zu vergleichenden Buchstaben, den Match- und Mismatch-Score als Parameter
        public static int ScoreFunction(char a,char b,int matchScore,int mismatchScore)
        {
            //Wenn die Buchstaben gleich sind ist der Match-Score der Rückgabewert.
            //Wenn nicht gib den Mismatch-Score zurück.
            return a == b ? matchScore : mismatchScore;
        }

In der wichtigsten Methode Align(), findet der Hauptteil des Algorithmus statt. Hier findet man die Initialisierung, Bewertung und Traceback…

//Die Align-Methode bekommt die beiden Sequenzen A und B, den Gap-Penalty, Match- und Mismatch-Score als Parameter.
        public static string[] Align(string sequenceA, string sequenceB, int gapPenalty, int matchScore, int mismatchScore)
        {
            //Hier werden beide Matrizen initialisiert. Die Scoring- und Traceback-Matrix.
            #region Initialize
            int[,] matrix = new int[sequenceA.Length + 1, sequenceB.Length + 1];
            char[,] tracebackMatrix = new char[sequenceA.Length + 1, sequenceB.Length + 1];
            matrix[0, 0] = 0;

            //Befülle die erste Reihe der Matrizen.
            for (int i = 1; i < sequenceA.Length + 1;i++)
            {
                matrix[i,0] = matrix[i-1,0] + gapPenalty;
                tracebackMatrix[i,0] = 'L';
            }

            //Befülle die erste Spalte der Matrizen.
            for (int i = 1; i < sequenceB.Length + 1; i++)
            {
                matrix[0, i] = matrix[0 , i - 1] + gapPenalty;
                tracebackMatrix[0,i] = 'U';
            }
            #endregion

            //Hier werden die Werte für die Scoring-Matrix berechnet. Zeitgleich befüllen
            //wir die Traceback-Matrix.
            #region Scoring
            for (int i = 1; i < sequenceA.Length + 1;i++)
            {
                for (int j = 1; j < sequenceB.Length + 1;j++)
                {
                    //Lese und berechne die Werte der Vorgängerzellen.
                    int diagonal = matrix[i - 1, j - 1] + ScoreFunction(sequenceA[i-1],sequenceB[j-1],matchScore,mismatchScore);
                    int links = matrix[i - 1, j] + gapPenalty;
                    int oben = matrix[i, j - 1] + gapPenalty;

                    //Der höchste Wert wird eingetragen.
                    matrix[i, j] = Math.Max(oben,Math.Max(links, diagonal));

                    //Finde raus welche der Zellen den Wert geliefert hat und trage
                    //dies in die Traceback-Matrix ein.
                    if(matrix[i,j] == diagonal && i > 0 && j > 0)
                    {
                        tracebackMatrix[i, j] = 'D';
                    }
                    else if (matrix[i, j] == links)
                    {
                        tracebackMatrix[i, j] = 'L';
                    }
                    else if (matrix[i, j] == oben)
                    {
                        tracebackMatrix[i, j] = 'U';
                    }
                }
            }
            #endregion

            //Hier wird einfach die Traceback-Methode aufgerufen und liefert uns das Alignment.
            #region Traceback
            return TraceBack(tracebackMatrix,sequenceA,sequenceB);
            #endregion

        }

Die Methode Align() macht Gebrauch von der Traceback-Methode. Hier wird der Weg vom Score zur Zelle (0,0) ausgelesen und entsprechend das Alignement erstellt:

//Eine TraceBack-Matrix und die beiden Sequenzen sind die Paramter für das Traceback.
        public static string[] TraceBack(char[,] tracebackMatrix,string sequenzA, string sequenzB)
        {

            int i = tracebackMatrix.GetLength(0) - 1;
            int j = tracebackMatrix.GetLength(1) - 1;

            StringBuilder alignedSeqA = new StringBuilder();
            StringBuilder alignedSeqB = new StringBuilder();

            //Das Traceback wird asugeführt solange wir uns nicht in der Zelle (0,0) befinden.
            while (tracebackMatrix[i, j] != 0)
            {
                switch (tracebackMatrix[i, j])
                {
                    case 'D':
                        alignedSeqA.Append(sequenzA[i - 1]);
                        alignedSeqB.Append(sequenzB[j - 1]);
                        i--;
                        j--;
                        break;
                    case 'U':
                        alignedSeqA.Append("-");
                        alignedSeqB.Append(sequenzB[j - 1]);
                        j--;
                        break;
                    case 'L':
                        alignedSeqA.Append(sequenzA[i - 1]);
                        alignedSeqB.Append("-");
                        i--;
                        break;

                }
            }

            string[] alignments = new string[2];
            //Da wir die Zeichen jeweils rechts an die Alignments angefügt haben,
            //rufen wir hier die Reverse-Methode um die Strings umzudrehen.
            alignments[0] = new string(alignedSeqA.ToString().Reverse().ToArray());
            alignments[1] = new string(alignedSeqB.ToString().Reverse().ToArray());

            //Der Rückgabewert ist ein array welches beide alignments enthält.
            return alignments;

        }

Im Anschluss noch folgende Überlegung, die Traceback-Matrix könnte effizienter sein, wenn man byte[] anstatt char[] verwendet. Dies würde zwar einige Sonderzeichen ausschließen uns aber gleichzeitig Speicherverbrauch sparen. Dies wäre insofern kein Problem da wir eigentlich nur drei Buchstaben brauchen.

Am besten kann man diesen Algorithmus nachvollziehen indem man vorgeht wie bei den meisten anderen, mit Stift und Papier 🙂

Hier haben wir uns das globale Alignment zweier Sequenzen angeguckt. Als nächstes bietet es sich an entweder mit dem lokalen Alignment (Smith-Waterman-Algorithmus) oder gleich dem Multiple-Sequence-Alignment weiter zu machen.

Bis bald.

Veröffentlicht unter .NET, Algorithmen, Beispiel, Beispiel, Bioinformatik, c#, global alignment, globales alignment, Mathematik, needleman-wunsch, Programmierung, Sequence alignmenet, Sequenzalignment | Verschlagwortet mit , , , , , , , , , | 9 Kommentare