C# Quellcode - 34.9 KbWas haben ein GIF-Bild, eine HTML-Seite, und ein Einkaufszettel gemeinsam? Sie alle sind oder enthalten Listen, die keine besondere Reihenfolge erfordern. die Farben in der Palette eines GIF-Bildes können jede Reihenoflge haben, so wie die Attribute in einem HTML-Tag, oder die Wörter auf deinem Einkaufszettel.
In jeder Liste mit anzahl Elementen, können wir anzahl-1 Bits verstecken,
nur durch das Sortieren der Einträge. Keine Tricks, keine komplizierten Formeln.
Fangen wir an mit einer einfache Liste von Wörtern,
dann setzen wir das Prinzip fort mit GIF-Paletten und danach mit HTML-Seiten.
The Algorithmus ist immer der gleiche, weil alle Listen im Grunde gleich sind.
Der erste Schritt ist, die Listenelemente in eine bestimmte Reihenfolge zu zwingen. Diese kann alphabetisch sein, oder eine eigene Sortierung. Dann wird die sortierte Liste neu sortiert, abhängig von den Bits der geheimen Nachricht.
Wenn du die Standard-Sortierung kennst, kannst du die Liste noch einmal sortieren, und die Stegano-Liste mit der sortierten Liste vergleichen. Die Unterschiede sagen dir alles über die Nachrichten-Bits, von denen die Reihenfolge stammte:
Man braucht nicht unbedingt einen Computer für Listen-Steganografie. Such dir ein Stück Papier und einen Stift, und schreib neun Tiere auf. Nein, das ist nicht der Anfang eines Psychotests, es ist ein Trägerdokument. Die Wörter brauchen eine Standard-Sortierung, auf die wir uns bei der späteren Neu-Sortierung beziehen können, darum sortieren wir sie alphabetisch:
Ohne mathematische Tricks können neun Listeneinträge 9-1 = 8 Bits an geheimer Information verstecken, zum Beispiel das ASCII-Zeichen ‘c’ (99 or 01100011). Jeder Eintrag (außer dem Letzten) repräsentiert ein Bit. Für jedes 1-Bit verschieben wir das ersten Element aus der Original-Liste in die neue Liste, für 0-Bits verschieben wir einen anderen Eitnrag in die neue Liste. Angefangen mit dem höchsten Bit, läuft der Prozess folgendermaßen ab:
Original-Liste Neue Liste Vogel --- Katze --- Dinosaurier --- Hund --- Fisch --- Horse --- Kaninchen --- Schaf --- Einhorn --- '0' Verstecken - Irgendein Element außer dem Ersten verschieben Vogel Dinosaurier Katze --- --- --- Hund --- Fisch --- Horse --- Kaninchen --- Schaf --- Einhorn --- '1' Verstecken - Erstes Element verschieben --- Dinosaurier Katze Vogel --- --- Hund --- Fisch --- Horse --- Kaninchen --- Schaf --- Einhorn --- '1' Verstecken - Erstes Element verschieben --- Dinosaurier --- Vogel --- Katze Hund --- Fisch --- Horse --- Kaninchen --- Schaf --- Einhorn --- '0' Verstecken - Irgendein Element außer dem Ersten verschieben --- Dinosaurier --- Vogel --- Katze Hund Kaninchen Fisch --- Horse --- --- --- Schaf --- Einhorn --- ... ... und so weiter ... ... '1' Verstecken - Erstes Element verschieben --- Dinosaurier --- Vogel --- Katze --- Kaninchen --- Einhorn --- Fisch --- Hund Schaf Horse --- --- Kein nicht-erster Element für ein '0'-Bit übrig, dass bedeutet keine Kapazität für weitere Bits. Letzten Eintrag trotzdem verschieben. --- Dinosaurier --- Vogel --- Katze --- Kaninchen --- Einhorn --- Fisch --- Hund --- Horse --- Schaf
Die neue Liste enthält die gleichen Einträge wie die alte, und einen zusätzlichen Sub-Inhalt, von den nur wir etwas wissen. Das versteckte Byte kann wieder gelesen werden, wenn wir den gleichen Prozess rückwärts durchspielen.
Sortierte Liste Trägerliste Vogel Dinosaurier Katze Vogel Dinosaurier Katze Hund Kaninchen Fisch Einhorn Horse Fisch Kaninchen Hund Schaf Horse Einhorn Schaf 'Dinosaurier' ist nicht das erste Element der sortierten Liste, also war das versteckte Bit '0'. Notier dir das, und streich das Element aus beiden Listen. Vogel --- Katze Vogel --- Katze Hund Kaninchen Fisch Einhorn Horse Fisch Kaninchen Hund Schaf Horse Einhorn Schaf 'Vogel' aus der Trägerliste ist das erste Element in der sortierten Liste => '01'. --- --- Katze --- --- Katze Hund Kaninchen Fisch Einhorn Horse Fisch Kaninchen Hund Schaf Horse Einhorn Schaf 'Katze' aus der Trägerliste ist das erste Element in der sortierten Liste => '011'. --- --- --- --- --- --- Hund Kaninchen Fisch Einhorn Horse Fisch Kaninchen Hund Schaf Horse Einhorn Schaf 'Dinosaurier' ist nicht das erste Element der sortierten Liste => '0110'. ... ... und so weiter für alle Tiere ... ...
Das lateinische Alphabet ist keine gute Standard-Sortierung, denn jeder würde es gleich als Erstes ausprobieren. Mein Vorschlag: Misch dir Buchstaben durcheinander, und schreib dir ein benutzerdefiniertes Alphabet. Die Liste wie oben sortieren, können wir genausogut mit C#:
public StringCollection Hide(String[] lines, Stream message, String alphabet)
{
//sort the lines according to a custom alphabet
StringCollection originalList = Utilities.SortLines(lines, alphabetFileName);
StringCollection resultList = new StringCollection();
int messageByte = message.ReadByte();
bool messageBit = false;
int listElementIndex = 0;
Random random = new Random();
//for each byte of the message
while (messageByte > -1) {
//for each bit
for (int bitIndex=0; bitIndex<8; bitIndex++) {
//decide which line is going to be the next one in the new list
messageBit = ((messageByte & (1 << bitIndex)) > 0) ? true : false;
if (messageBit) {
//pick the first line from the remaining original list
listElementIndex = 0;
}else{
//pick any line but the first one
listElementIndex = random.Next(1, originalList.Count);
}
//move the line from old list to new list
resultList.Add(originalList[listElementIndex]);
originalList.RemoveAt(listElementIndex);
}
//repeat this with the next byte of the message
messageByte = message.ReadByte();
}
//copy unused list elements, if there are any
foreach (String s in originalList) {
resultList.Add(s);
}
return resultList;
}
Mit einer Liste und einem Alphabet lässt sich der Prozess ganz einfach umkehren:
public Stream Extract(String[] lines, String alphabet)
{
//initialize empty writer for the message
BinaryWriter messageWriter = new BinaryWriter(new MemoryStream());
StringCollection carrierList = new StringCollection();
carrierList.AddRange(lines);
carrierList.RemoveAt(carrierList.Count - 1);
//sort -> get original list
StringCollection originalList = Utilities.SortLines(lines, alphabetFileName);
String[] unchangeableOriginalList = new String[originalList.Count];
originalList.CopyTo(unchangeableOriginalList, 0);
int messageBit = 0;
int messageBitIndex = 0;
int messageByte = 0;
foreach (String s in carrierList) {
//decide which bit the entry's position hides
if (s == originalList[0]) {
messageBit = 1;
}else{
messageBit = 0;
}
//remove the item from the sorted list
originalList.Remove(s);
//add the bit to the message
messageByte += (byte)(messageBit << messageBitIndex);
messageBitIndex++;
if (messageBitIndex > 7) {
//append the byte to the message
messageWriter.Write((byte)messageByte);
messageByte = 0;
messageBitIndex = 0;
}
}
//return message stream
messageWriter.Seek(0, SeekOrigin.Begin);
return messageWriter.BaseStream;
}
Jede indizierte Bitmap enthält eine Liste, die sich auf die gleiche Weise missbrauchen lässt. Diese beiden Paletten gehören zum gleichen GIF-Bild. Eine ist das Original, die andere enthält einen versteckten Text von 31 Zeichen:
Wieder ist das Erste was wir brauchen eine Palette mit einer Standard-Sortierung. In diesem Beispiel werden wir die Farben nach ihren ARGB-Werten sortieren.
public Bitmap Hide(Bitmap image, Stream message)
{
//list the palette entries an integer values
int[] colors = new int[image.Palette.Entries.Length];
for (int n = 0; n < colors.Length; n++) {
colors[n] = image.Palette.Entries[n].ToArgb();
}
//initialize empty list for the resulting palette
ArrayList resultList = new ArrayList(colors.Length);
//initialize and fill list for the sorted palette
ArrayList originalList = new ArrayList(colors);
originalList.Sort();
Viele Pixel verweisen auf die Paletteneinträge, und die werden wir ebenfalls anpassen müssen. Also sollten wir, wenn wir eine Farbe in die neue Palette verschieben, alten und neuen Index notieren.
//initialize list for the mapping of old indices to new indices SortedList oldIndexToNewIndex = new SortedList(colors.Length);
Jetzt sind die Listen fertig, und wir können in die Nachricht eintauchen und für jedes Bit eine Farbe verschieben…
Random random = new Random();
int listElementIndex = 0;
bool messageBit = false;
int messageByte = message.ReadByte();
//for each byte of the message
while (messageByte > -1) {
//for each bit
for (int bitIndex = 0; bitIndex < 8; bitIndex++) {
//decide which color is going to be the next one in the new palette
messageBit = ((messageByte & (1 < bitIndex)) > 0) ? true : false;
if (messageBit) {
listElementIndex = 0;
}else{
listElementIndex = random.Next(1, originalList.Count);
}
…aber nicht vergessen, von welcher Position in der Original-Palette die Einträge kamen! Tausende Pixel warten auf aktualisierte Farbindizes.
//log change of index for this color
int originalPaletteIndex = Array.IndexOf(colors, originalList[listElementIndex]);
if( ! oldIndexToNewIndex.ContainsKey(originalPaletteIndex)) {
//add mapping, ignore if the original palette contains more than one entry for this color
oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
}
//move the color from old palette to new palette
resultList.Add(originalList[listElementIndex]);
originalList.RemoveAt(listElementIndex);
}
//repeat this with the next byte of the message
messageByte = message.ReadByte();
}
//copy unused palette entries
foreach (object obj in originalList) {
int originalPaletteIndex = Array.IndexOf(colors, obj);
oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
resultList.Add(obj);
}
//create new image
Bitmap newImage = CreateBitmap(image, resultList, oldIndexToNewIndex);
return newImage;
}
Die korrespondierende Extract-Methode änelt einer Kombination der
Hide- und Extract-Methoden für Text-Listen.
Sie sortiert die Palette, rekonstruiert die Nachricht, und entfernt dann die Nachricht aus dem Bild
(produziert ein Bild mit einer Palette in Standard-Sortierung).
Das hier ist die Palette aus dem Beispiel, nachdem die Nachricht ausgelesen und entfernt wurde:
Ein HTML-Document selbst ist keine sortierbare Liste, die Tags müssen in ihrer Reihenfolge bleiben.
Aber innerhalb der Tags stehen Attribute, und diese können beliebig sortiert werden.
Das heißt, jedes Tag einer HTML-Seite kann Attributes.Count-1 Bits speichern.
Die meisten Tags haben gerade genug Attribute für ein oder zwei Bits,
aber wir können die Nachricht über alle Tags der Seite verteilen.
public void Hide(String sourceFileName, String destinationFileName, Stream message, String alphabet) {
//initializations skipped
// ... ... ...
//list the HTML tags
HtmlTagCollection tags = FindTags(htmlDocument);
//loop over tags
foreach (HtmlTag tag in tags) {
//write beginning of the tag
insertTextBuilder.Remove(0, insertTextBuilder.Length);
insertTextBuilder.AppendFormat("<{0}", tag.Name);
//list attribute names
String[] attributeNames = new String[tag.Attributes.Count];
for (int n = 0; n < attributeNames.Length; n++) {
attributeNames[n] = tag.Attributes[n].Name;
}
Ab hier ist der Code fast der gleiche wie in den anderen Hide-Methoden:
//get default sorting
StringCollection originalList = Utilities.SortLines(attributeNames, alphabet);
StringCollection resultList = new StringCollection();
if (tag.Attributes.Count > 1) {
//the tag has capacoty for one or more bits
for (int n = 0; n < attributeNames.Length - 1; n++) {
//get next bit of the message
bitIndex++;
if (bitIndex == 8) {
bitIndex = 0;
if (messageByte > -1) {
messageByte = message.ReadByte();
}
}
if (messageByte > -1) {
//decide which attribute is going to be the next one in the new tag
messageBit = ((messageByte & (1 << bitIndex)) > 0) ? true : false;
if (messageBit) {
listElementIndex = 0;
}else{
listElementIndex = random.Next(1, originalList.Count);
}
}else{
listElementIndex = 0;
}
//move the attribute from old list to new list
resultList.Add(originalList[listElementIndex]);
originalList.RemoveAt(listElementIndex);
}
}
if (originalList.Count > 0) {
//add the last element - it never hides data
resultList.Add(originalList[0]);
}
Die sortierten Attribute müssen zuück ins Dokument geschrieben werden. Der größte Teil des Codes wurde aus dem letzten HTML-Artikel dieser Serie kopiert, und muss hier hoffentlich nicht extra erklärt werden. ;-)
HtmlTag.HtmlAttribute attribute;
foreach (String attributeName in resultList) {
attribute = tag.Attributes.GetByName(attributeName);
insertTextBuilder.Append(" ");
if (attribute.Value.Length > 0) {
insertTextBuilder.AppendFormat("{0}={1}", attribute.Name, attribute.Value);
}else{
insertTextBuilder.Append(attributeName);
}
}
//replace old tag with new tag
//.. ... ...
}
Hast du bemerkt, dass die drei Hide-Methoden fast das gleiche tun?
Die Extract-Methoden sind genauso ähnlich.
Bitte lies sie im vollständigen Quelltext nach, falls du noch keine Bits-Allergie hast…
Die Anwendung besteht aus drei three "Halbduplex-Dialogen". Man kann entweder einen leeren Träger und eine Nachricht, oder einen Träger zum Auslesen einer Nachricht angeben. Bei Text-Listen und Bildern kann man das Ergebnis sofort sehen.
In den Dialogen für Text-Listen und HTML-Dokumente kann man eine "Alphabet-Datei" angeben. Das ist eine Textdatei mit einem benutzerdefinierten Alphabet. Ein beispielhaftes Alphabet findest du in testdata/demo.txt.
