Java Quellcode - 4 kB

Introduction

As you possibly remember from school, a Turing Machine is a mathematical model of computation. It defines an abstract machine working with characters on an endless tape. In theory, a system that simulates a turing machine is able to support all tasks accomplishable by computers.

Each cell on the tape has to be writable only once. For a second write access, you can copy the used tape to a new segment. As every calculation can be done in binary, the alphabet of writable characters can be limited to {0, 1}, though a larger alphabet may be good to save tape. In this article we'll use {0, 1, 2, 3} to encode everything in base-4.

A cheap and simple way to simulate the endless, writable tape is a clew of yarn. You can write characters by knitting different stitches. If you need to overwrite a used position, just start a new row; that is like rewinding and copying the tape of the turing machine.

This article explains how to encode any content as stitches, render a knitting chart and decode the finished yarn-tape again. It uses the Apache Batik SVG Toolkit to draw the pattern.

You might want to feed the patterns into a knitting machine, turning it into a real hardware Turing Machine. You can as well knit them by hand to transmit secret messages just by letting your messenger wear a warm hat.

The Application

The Java application accepts a text, converts the characters to groups of base-4 numbers and translates those into a row of stitches:

  • 0 = knit
  • 1 = purl
  • 2 = yarn over, knit
  • 3 = yarn over, purl

The screenshot shows the knitting chart generated from the text "Hi CP!". Only the first row contains information. The second row is there to reduce the excess stitches created by the digits "2" and "3". All following rows are just repetitions to make the code look like decoration.

Such a pair of rows would look strange in a piece of cloth. But usually, knitted stuff has decorative patterns and everything looks like a pattern, if you just repeat if often enough. So, feel free to repeat the code row until the result looks pretty unsuspicious.

Encoding and Decoding

This little demonstration uses only latin text. As a character is a value between 0 and 255, it corresponds to four digits between 0 and 3. Those digits are concatenated to one long string and then sent to the graphics frame.

private void encode(String clearText){

	ByteBuffer bytes = Charset.forName("ISO-8859-15").encode(clearText);
	StringBuilder resultBuilder = new StringBuilder(clearText.length() * 4);

    // convert each character
	while(bytes.hasRemaining()){
		int currentValue = bytes.get();			
		String currentWord = Integer.toString(currentValue, 4);
		
		// pad the number to a length of 4
		while(currentWord.length() < 4){
			currentWord = "0" + currentWord;
		}
		
		resultBuilder.append(currentWord);
	}
	
	ChartFrame frame = new ChartFrame();
	frame.drawChart(clearText, resultBuilder.toString());
}

When reading a piece of cloth manually, you may note down digits for the kinds of stitches you recognize...

... then call the decoder with the row of stitches you found. They'll be decoded to the original text:

The decode method converts the chain of numbers back to the original message.

private String decode(String encodedText){

	int n = 0;
	StringBuilder resultBuilder = new StringBuilder(encodedText);

    // translate blockwise to characters
	while(n < resultBuilder.length()){
		String currentWord = resultBuilder.substring(n, n+4);
		
		int currentValue = Integer.parseInt(currentWord, 4);
		String currentClearChar;
		
		// decode or ignore
		if(currentValue < 256){
			ByteBuffer buffer = ByteBuffer.wrap(new byte[]{(byte)currentValue});
			currentClearChar = Charset.forName("ISO-8859-15").decode(buffer).toString();
		}else{
			currentClearChar = "?";
		}
		
		// compress 4 digits to 1 character		
		resultBuilder.replace(n, n+4, currentClearChar);
		n++;
	}
	
	return resultBuilder.toString();
}

Rendering the Chart

For each digit, the corresponding stitches have to be drawn. I used the knit chart symbols by the Craft Yarn Council, which are easy to render with geometric shapes.

The chart consists of three components: Column numbers, odd rows encoding the payload, even rows fixing the count of stitches.

public void drawChart(String title, String base4Digits){
	titleText = title;

    // prepare SVG document
	DOMImplementation impl = SVGDOMImplementation.getDOMImplementation();
	String svgNS = SVGDOMImplementation.SVG_NAMESPACE_URI;
	SVGDocument doc = (SVGDocument) impl.createDocument(svgNS, "svg", null);
	SVGGraphics2D g = new SVGGraphics2D(doc);
	g.setFont(new Font("sans serif", Font.PLAIN, 10));
	
	// calculate chart width
	countColumns = getCountCols(base4Digits);
	countRows = (int)(200 / boxSize);
	svgCanvas.setSize((2+countColumns)*boxSize, countRows*boxSize);
	
	// fill background
	g.setPaint(Color.darkGray);
	g.fillRect(0, 0, svgCanvas.getWidth(), svgCanvas.getHeight());
	
	// draw odd coding rows, even fixing rows
	for(int y = 0; y < (countRows-2); y+=2){
	    // code symbols may add stiches
    	drawOddRow(y, base4Digits, g);
    	
    	// fix excess stitches by knitting two together
    	drawEvenRow(y+1, base4Digits, g);	    	
    }
	
	// draw column numbers
	for(int x=0; x < countColumns; x++){
		drawColNumber(x+1, countRows-1, g);
	}
	
	// prepare and show frame
	titleText = titleText + " - " + "start with " + (base4Digits.length()+2) + " stitches";
	g.getRoot(doc.getDocumentElement());
	svgCanvas.setSVGDocument(doc);
	svgCanvas.getParent().setPreferredSize(svgCanvas.getSize());
	pack();
	setVisible(true);
}

Drawing a row is simple: Place one knit symbol at each end, then fill the space with symbols:

private void drawOddRow(int y, String base4Digits, SVGGraphics2D g){
	// label and left edge
	drawRowNumber(0, y, g);
	drawKnit(1, y, g);

    // append one or two symbols per digit
	int x = 2;
	for(int n=0; n < base4Digits.length(); n++){
		char currentChar = base4Digits.charAt(n);
		
		/* draw box
		   0 = knit
		   1 = purl
		   2 = yarn over, knit
		   3 = yarn over, purl
		*/
		switch(currentChar){
    		case '0': drawKnit(x, y, g); break;
    		case '1': drawPurl(x, y, g); break;
    		case '2': drawYarnOver(x, y, g);
    				  drawKnit(++x, y, g);
    		          break;
    		case '3': drawYarnOver(x, y, g);
    				  drawPurl(++x, y, g);
    				  break;
		}
		
		x++;
	}

	// right edge
	drawKnit(x, y, g);
} 

The chart symbols are primitive shapes. These are a few examples:

private void drawBox(int col, int row, SVGGraphics2D g){
	int x = col*boxSize;
	int y = row*boxSize;
	Rectangle2D.Double box = new Rectangle2D.Double(x, y, boxSize, boxSize);
	
	g.fill(box);    	
	g.setColor(Color.black);
	g.draw(box);
}

private void drawColNumber(int col, int row, SVGGraphics2D g){
	g.setColor(Color.black);
	g.setPaint(Color.cyan);
	drawBox(col, row, g);
	g.drawString(String.valueOf(col),
	       (col*boxSize)+boxPadding,
	       (row*boxSize)+boxSize-boxPadding);
}

private void drawYarnOver(int col, int row, SVGGraphics2D g){
	g.setColor(Color.black);
	g.setPaint(Color.white);
	
	int x = col*boxSize;
	int y = row*boxSize;
	int height = boxSize-(boxPadding*2);
	
	Ellipse2D circle = new Ellipse2D.Double(
				x+boxPadding, y+boxPadding, 
				height, height);
	
	drawBox(col, row, g);
	g.draw(circle);
}

Points of Interest

So far, all we did was encoding and decoding. We are able to fill the tape of our fluffy Turing Machine with characters.

That is good enough to hide text in plain sight wearing a woolen scarf, which may be your only chance to smuggle secrets from Alaska to Siberia.

The next step could be to program a knitting machine, to make it process a calculation line by line. I hope you enjoyed this article and take a closer look at other people's textiles.

SteganoDotNet

Ein Framework für Steganographie in .NET/mono

Quellen, nur Framework - 110 Kb
Quellen, Framework und Demo-Anwendung - 1.5 Mb
Assemblies, nur Framework - 138 Kb
Assemblies, Framework und Demo-Anwendung - 1.4Mb

Unterstützte Trägerformate

  • Pixelgrafiken 24 Bit (verlustfreie Formate)
  • Pixelgrafiken 8 Bit (GIF, PNG)
  • Stichwort-Listen
  • HTML-Seiten
  • MIDI-Sequenzen
  • .NET Assemblies
  • Wave-Klänge (unkomprimiert)
  • Audio-Daten jeder Art (analog-sicher)

Extras

  • Verteilen des Klartextes über mehrere Träger verschiedener Formate
  • Sichern mit einem beliebig langen Schlüssel

Sonstiges

  • Version: 0.1 Alpha
  • Sprache: C# 2.0
  • Lizenz: Gnu GPL

Was kann es?

SteganoDotNet fasst alle hier vorgestellten Techniken plus einige Extras in einem Framework aus zwei Namespaces zusammen:

  • SteganoDotNet.Action: Der steganographische Kern des Frameworks. Er enthält die abstrakten Typen FileType und FileUtility und alle davon abgeleiteten Klassen, die jeweils eine Art von Trägermedium beschreiben und die passenden Stego-Methoden kapseln. Läuft sowohl in .NET als auch in mono.
  • SteganoDotNet.UserControls: Fertige Oberflächen-Bausteine. Für jedes *FileUtility wird ein Konfigurationsdialog als UserControl bereitgestellt. Wenn Sie die Einstellungen nicht selbst festlegen möchten/können, binden Sie das passende UserControl ein, um sie interaktiv abzufragen.

Darüber hinaus enthält das Projekt die Demo-Anwendung Stego For You, die so gut wie alle Framework-Features unter einer Oberfläche vereint.

Wie alles begann... ein Framework stellt sich vor

Wie SteganoDotNet entstand, warum einige schöne Features aus Stego For You wieder entfernt wurden und Platz für Diskussionen finden Sie auf CodeProject:

 

C# Quellcode für MonoDevelop und Visual Studio - 38.87 kB

Worum geht es?

Auf Seite 14 hast du gelernt, wie man eine Nachricht durch Sortieren einer Liste beliebiger Dinge codieren kann. Musik besteht aus Melodien, die gewissermaßen; Notenlisten sind. Warum nicht mal ein Lied komponieren, dessen Melodie ein Text ist?

screen

Entscheiden müssen wir uns nur für die Menge der Noten, die im Lied vorkommen sollen. Weil es Factorial(count) aufzählbare Permutationen gibt, erlauben mehr verschiedene Noten ein größeres Alphabet für die geheime Nachricht. Dieser Artikel wird sich nicht um Harmonielehre und Komposition kümmern. Für den Anfang werden wir eine ganze chromatische Tonleiter aufmischen, um ein langes oder einige kurze Wörter zu codieren. Für längere Texte kann man mehrere Melodieteile verketten.

Hallo Welt

Ein einfaches Beispiel: Eine Tonleiter hat 12 Noten, zwei davon machen 24 Noten, das reicht für ein "hello world". Der Nachrichtentext wid als ein einziger BigInteger behandelt. Die leere Nachricht ist '0', die Default-Reihenfolge der Noten:

chromatic scale

Ich habe mifür 42 verschiedene Zeichen entschieden: a-z 0-9 .:() und Leerzeichen. Mit diesem Alphabet wird die numerische Repräsentation von "hello world" folgendermaßen berechnet:

h =  7		w = 22
e =  4		o = 14
l = 11		r = 17
l = 11		l = 11
o = 14		d =  3
------------------------
   7 * (42^10)	h
+  4 * (42^9)	e
+ 11 * (42^8)	l
+ 11 * (42^7)	l
+ 14 * (42^6)	o

+ 36 * (42^5)	[space]

+ 22 * (42^4)	w
+ 14 * (42^3)	o
+ 17 * (42^2)	r
+ 11 * (42^1)	l
+  3 * (42^0)	d
------------------------
= 121297199112622725

Mit dieser Zahl lässt sich der zuvor erklärte Algorithmus füttern, mit der chromatischen Tonleiter als Trägerliste. (Für Nicht-Musiker: C C# D D# E F F# G G# A H B c c# d d# e f f# g g# a h b.)

Das Ergebnis sieht so aus:

mixed up notes
d d# D e f A G# f# F H g F# C# E g# c# B a G D# c C h b

Weniger Zeichen, mehr Wörter

Die größmögliche numerische Nachricht (und damit die Länge der Textnachricht) ist durch Factorial(countNotes) beschänkt. Um mehr Text zu codieren könnte man entweder mehr Noten verwenden - oder die numerischen Werte kleiner halten. Im obigen Beispiel verursachte die Basis 42 extrem große Werte. Beschränkt man die Zeichen auf a-z und Leerzeichen, so ist die Basis 27 und der Text "hello world" hat den Wert 1474967912327400. Das heißt, wir können einen längeren Text in einer Melodie derselben Länge speichern.

   7 * (27^10)	h		+ 22 * (27^4)	w
+  4 * (27^9)	e		+ 14 * (27^3)	o
+ 11 * (27^8)	l		+ 17 * (27^2)	r
+ 11 * (27^7)	l		+ 11 * (27^1)	l
+ 14 * (27^6)	o		+  3 * (27^0)	d
+ 36 * (27^5)	[space]
---------------------------------------------------
= 1474967912327400

Rhythmus - Warum nicht?

Eine Melodie aus reinen Viertelnoten klingt schnell langweilig. Aber wenn die Noten einmal sortiert sind, kann man überall Duplikate einfügen. Alle Wiederholungen werden vor dem Decodieren entfernt. Da Zeit keine Rolle spielt (im Prototypen noch nicht), dürfen Vierten nach Belieben in Achtel aufgespalten werden. Nichts davon beeinflusst die codierte Nachricht. Hier sind ein paar Varianten von "coding in c sharp" (Nummer 201255931456816565832252 mit dem 27-Zeichen-Alphabet).


Text: "coding in c sharp"
Tonleiter: beginnt mit A
Melodie: f e c# b g a G h F# H g# G# A D c f# E F C d C# B d# D#


Text: "coding in c sharp"
Tonleiter: beginnt mit D
Melodie: H A F# e c d C d# b D# c# C# D g F B a h f G f# E G# g#


Text: "coding in c sharp"
Tonleiter: beginnt mit F
Melodie: c# c A g d# f D# f# D F# e E F h G# d C C# g# H a G B b


Text: "coding in c sharp"
Tonleiter: beginnt mit G
Melodie: dis d B a f g F gis E Gis fis Fis G C H e D Dis h c b A cis Cis

Die Demo-Anwendung

Die Demo codiert in vier Schritten Text als Musik:

  1. Wähle ein Offset für die chromatische Tonleiter.
  2. Wähle ein Alphabet. Die Zeichen des aktuellen Alphabets stehen jeweils in der Titelleiste.
  3. Gib deine Nachricht ein.
  4. "Mix" deine Melodie. Falls das Ergebnis nicht schön genug ist, probier "Random melody" aus, bis es gut klingt.

Natuürlich kann man auch eine Melodie zurück in Text decodieren:

  1. Wähle das Offset das beim Codieren benutzt wurde.
  2. Wähle das gleiche Alphabet.
  3. Gib die Noten ins Ergebnisfeld ein.
  4. "Unmix" die Noten zum Klartext.

Das Programm wurde für eine Vorführung geschrieben. Daher hat es ein paar versteckte Funktionen, welche die Zuschauer nicht mit sichtbaren Buttons oder Menüs verwirren.

Zahlenspiele

Manche Geeks fragten mich, was die Textbedeutung von pi sei. Für solche Situationen können Text- und Zahlenfeld vertauscht werden: Doppelklicke auf das Feld "Content numeric". Es wird dann entsperrt und die eingegebenen Zahlen werden zu Text decodiert.

Schnellnotizen

Um den Inhalt eines Textfelds zu speichern, setze den Fokus in das Feld und drücke Ctrl+Y. Der Text wird dann an die Datei clipboard.txt im exe-Verzeichnis angehängt.

Das Notenbild speichern

Die Anwendung zeigt das Ergebnis in Notenname und malt gleichzeitig die Noten. Weil aber nur die Notennamen später wieder eingetippt und decodiert werden können, können nur diese in die Zwischenablage bzw. clipboard.txt kopiert werden. Um die Noten zu speichern hilft ein Linksklick auf das Bild. Es wird dann als PNG-Datei im exe-Verzeichnis abgelegt.

Den Klang speichern

Die Melodie, wie sie vom "Play"-Button gepiept wird, kann mit einem Rechtsklick auf das Bild gespeichert werden. Sie wird dann als WAV-Datei im exe-Verzeichnis abgelegt.

Workaround für mono/Linux

Mit einigen Kombinationen von mono-Version und Audio-System ist Console.Beep unbrauchbar. Wenn bei dir so ein Problem auftritt, definiere die Präprozessor-Variable IsMono in Form1.cs.

#define IsMono

Anstatt zu piepen, speichert das Programm dann den Klang in einer temporären Datei und lässt ihn von sox abspielen. Es sollte keinen sicht-/hörbaren Unterschied zum normalen Verhalten geben.

Ausblick

Die Demo-Anwendung zeigt nur die grundlegende Idee. Vielleicht werde ich es erweitern, um lange Textnachrichten in mehrteilige Melodien aufzuteilen, eine Tonart zu garantieren, nur Harmonien in vorgegebene Melodien einzufügen und so weiter. Im Prinzip gibt es kaum Grenzen für Komponisten, ihren Instrumentalstücken einen geheimen Subtext zu verleihen.

C# Quellcode für C# Express (.NET 2.0) - 913 Kb

Worum geht es?

Ein ZIP-Archiv besteht aus lokalen Dateien, von denen jede einen lokalen Header besitzt. Am Ende des Archivs befindet sich das Central Directory, in dem Verweise auf alle Dateien aufgelistet werden. Das zentrale Verzeichnis beschleunigt die Suche nach einer bestimmten Datei im Archiv. Wenn eine Archivierungswerkzeug wie WinZip oder FilZip ein Archiv öffnet, liest es zuerst das zentrale Verzeichnis. Erst wenn eine lokale Datei extrahiert werden soll, wird aus dem Verzeichnis der Byte-Offset gelesen, der die Stelle im Archiv angibt, an der die Datei steht; damit kann die lokale Datei gelesen und dekomprimiert werden. Was nicht im Verzeichnis aufgelistst steht, wird von der ZIP-Anwendung nicht angezeigt.

Oft enthalten ZIP-Archive sehr viele Einzeldateien. Jede davon hat zwei Größenangaben: Komprimierte und unkomprimierte Dateigröße. Aber hast du jemals ausgerechnet, ob die Summe der komprimierten Dateigrößen sich der Größe des Archivs auf der Festplatte annähert? Selbst wenn wir das ausprobieren würden, gäbe es immer eine gewisse Differenz, da auch Central Directory und lokale Header etwas Speicher belegen. Deshalb werden ein paar zusätzliche Bytes - zum Beispiel komprimierte Textdateien - nicht durch Zufall entdeckt werden.

Dieser Artikel verwendet Code aus ICSharpCode's SharpZipLib.

Das ZIP-Dateiformat

Dieses Archiv ist sauber, jede gezippte Datei hat ein Gegenstück im zentralen Verzeichnis.

clean zip file

Schau dir dieses Archiv genauer an: Welche ZIP-Anwendung würde die dritte Datei anzeigen? Das Textdokument ist aus dem Inhaltsverzeichnis ausgeblendet.

clean zip file

Was wir brauchen

Um teilweise unsichtbare Archive zu erzeugen, sind nur drei Schritte nötig:

  1. Lesen und Schreiben von ZIP-Dateien.
  2. ZIP-Einträge hinzufügen, ohne Spuren im Verzeichnis zu hinterlassen.
  3. Diese Einträge wiederfinden.

 

Schritt 1: SharpZipLib verwenden

Das erste Problem wurde bereits von ICSharpCode gelöst. Die GPL-lizenzierte Bibliothek SharpZipLib lässt sich problemlos der Projektmappe hinzufügen, mit den Klassen ZipOutputStream und ZipEntry werden Einträge ins Archiv geschrieben. Der Verzeichnis-Eintrag wird für jeden ZipEntry automatisch erstellt.

private void ZipFiles(string destinationFileName, StringCollection sourceFiles)
{
        // Archiv zum Schreiben öffnen
        FileStream outputFileStream = new FileStream(destinationFileName, FileMode.Create);
        ZipOutputStream zipStream = new ZipOutputStream(outputFileStream);

        foreach(string sourceFileName in sourceFiles)
        {
          // Header für eine Datei füllen
          inputStream = new FileStream(sourceFileName, FileMode.Open);
          zipEntry = new ZipEntry(Path.GetFileName(sourceFileName));
          zipEntry.CompressionMethod = CompressionMethod.Deflated;
          zipStream.PutNextEntry(zipEntry);
         
          // Inhalt der Datei hinzufügen
          byte[] buffer = new byte[4096];
			 int countBytesRead;
		 	 while ((countBytesRead = inputStream.Read(buffer, 0, buffer.Length)) > 0)
			 {
				zipStream.Write(buffer, 0, countBytesRead);
			 }
			
          // Datei schließen und Verzeichnis-Eintrag schreiben
          inputStream.Close();
          zipStream.CloseEntry();
        }

        zipStream.Finish();
        zipStream.Close();
}

Schritt 2: ZipOutputStream erweitern

Wie lässt wir nun der Eintrag im Central Directory vermeiden? SharpZipLib erzeugt das Verzeichnis in ZipOutputStream.Finish(). Dort können wir die Dateien abfangen, die versteckt bleiben sollen. Um zwischen sichtbaren und unsichtaren Dateien zu unterscheiden, habe ich der Klasse ZipEntry eine neue Eigenschaft IsVisible angehängt. Diese in ZipOutputStream.Finish() abzufragen, ist eine Änderung von nur wenigen Zeilen.

namespace ICSharpCode.SharpZipLib.Zip
{
	[...]
   public class ZipOutputStream : DeflaterOutputStream
	{
      [...]
		public override void Finish()
		{
			if (entries == null)  {
				return;
			}

			if (curEntry != null) {
				CloseEntry();
			}

			int numEntries = 0;
			int sizeEntries = 0;

			foreach (ZipEntry entry in entries)
			{
				if (entry.IsVisible) //CJ: List only visible entries
				{
                                        [...]
                                        // write the directory item for the zip entry
	                               [...]
                                 }
                         }
                 }
         }
         [...]
}

Schritt 3: ZipFile erweitern

Mit diesen kleinen Anpassungen ist die Bibliothek in der Lage, lokale Dateien vor dem zentralen Verezichnis zu verbergen. Damit beginnt die eigentliche Heruasforderung: Wir müssen unsere Dateien wiederfinden!

SharpZipLib enthält die Klasse ZipFile, um Archive zu lesen und einzelne Dateien zu dekomprimieren. Sie verlässt sich voll und ganz auf Verzeichnis-Einträge: ZipFile.GetInputStream() nimmt einen ZipEntry oder dessen Index an und liest den Inhalt der lokalen Datei am darin verzeichneten Offset. Da unsichtbare Dateien keinen solchen Eintrag haben, muss auch ZipFile angepasst und um zwei Methoden erweitert werden.

Bevor wir unsichtbare Dateien extrahieren können, brauchen wir ein vollständiges Inhaltsverzeichnis mit allen gezippten Dateien, egal ob sie im Central Directory stehen oder nicht. Da jedes Archiv mindestens eine sichtbare Datei enthalten sollte (sonst wäre zu offensichtlich, dass etwas nicht stimmt), habe ich die erste Datei im zentralen Verzeichnis als Ankerpunkt festgelegt. Am Anfang der ersten "offiziellen" Datei werden wir ins Archiv einsteigen und und durch die folgenden Header voran hangeln. So werdne wir an allen Dateien vorbei kommen, die tatsächlich vorhanden sind. Die neue Methode HasSuccessor(ZipEntry zipEntry) findet das Ende eines angegebenen ZIP-Eintrags und schaut im Stream nach, was dahinter folgt.

 /// <summary>
 /// Checks the file stream after the given zip entry for another one.
 /// </summary>
 /// <param name="entryIndex">The index of a zip entry.</param>
 /// <returns>true: there are more entries after this one. false: this is the last entry.</returns>
 public bool HasSuccessor(ZipEntry zipEntry)
 {
       if (entries == null)
       {
           throw new InvalidOperationException("ZipFile is closed");
       }

       //beginning of the preceeding zip entry
       long startPredecessor = CheckLocalHeader(zipEntry);

       //end of the preceeding zip entry
       long endPredecessor = startPredecessor + zipEntry.CompressedSize;

       //get a stream for whatever follows the zip entry
       Stream stream = new PartialInputStream(baseStream, endPredecessor, ZipConstants.LOCHDR);

       //read what may be a local file header
       int localHeaderStart = ReadLeInt(stream);

       //is it the beginning of another local file?
       return (localHeaderStart == ZipConstants.LOCSIG);
 }

Wenn HasSuccessor einen lokalen Header erkannt hat, soll dieser gelesen und anschließend nach dem nächsten gesucht werden. Die meisten Header dürften bereits aus dem Central Directory bekannt sein, aber die für uns interessaten sind neu. Die Unterscheidung fällt leicht, denn bekannte Einträge besitzen die Eigenschaft ZipFileIndex, welche den jeweiligen Index im Verzeichnis angibt. Ist dieser Index -1, so kann es nur eine versteckte Datei sein. Das bedeutet, dieser Header muss gelesen werden. Andernfalls kann einfach der vorhandene Verzeichniseintrag verwendet werden.

/// <summary>
/// Reads the ZipEntry of a file, which has no zip entry.
/// </summary>
/// <param name="entryIndex">The index of the preceeding zip entry.</param>
/// <returns>
/// An input stream.
/// </returns>
/// <exception cref="InvalidOperationException">
/// The ZipFile has already been closed
/// </exception>
/// <exception cref="ICSharpCode.SharpZipLib.Zip.ZipException">
/// The compression method for the entry is unknown
/// </exception>
/// <exception cref="IndexOutOfRangeException">
/// The entry is not found in the ZipFile
/// </exception>
public ZipEntry GetAttachedEntry(ZipEntry predecessor)
{
     if (entries == null)
     {
          throw new InvalidOperationException("ZipFile is closed");
     }

     //beginning of the preceeding zip entry
     long startPredecessor = CheckLocalHeader(predecessor);

     //end of the preceeding zip entry
     long endPredecessor = startPredecessor + predecessor.CompressedSize;

     //get a stream for the undocumented local file
     Stream stream = new PartialInputStream(baseStream, endPredecessor, ZipConstants.LOCHDR);

     //read local file header

     int localHeaderStart = ReadLeInt(stream);
     if (localHeaderStart != ZipConstants.LOCSIG)
     {
          throw new InvalidOperationException("Invalid local file header");
     }

     int version = ReadLeShort(stream);
     int flags = ReadLeShort(stream);
     int method = ReadLeShort(stream);
     int dosTime = ReadLeInt(stream);
     int crc = ReadLeInt(stream);
     int compressedSize = ReadLeInt(stream);
     int uncompressedSize = ReadLeInt(stream);
     int nameLength = ReadLeShort(stream);
     int extraLength = ReadLeShort(stream);

     //get a stream only for file name
     long offset = endPredecessor + ZipConstants.LOCHDR;
     Stream fileInfoStream = new PartialInputStream(baseStream, offset, nameLength);

     byte[] buffer = new byte[nameLength];
     fileInfoStream.Read(buffer, 0, nameLength);
     string name = ZipConstants.ConvertToString(buffer);

     int indexFromDirectoy = FindEntry(name, false);
     ZipEntry zipEntry;
     if (indexFromDirectoy < 0)
     {
             zipEntry = new ZipEntry(name, version);
             zipEntry.CompressedSize = compressedSize;
             zipEntry.CompressionMethod = (CompressionMethod)method;
             zipEntry.Crc = crc;
             zipEntry.DosTime = dosTime;
             zipEntry.Flags = flags;
             zipEntry.IsVisible = false;
             zipEntry.Offset = (int)endPredecessor;
             zipEntry.Size = uncompressedSize;
             zipEntry.IsVisible = false;
             zipEntry.ZipFileIndex = -1;
     }
     else
     {
             zipEntry = entries[indexFromDirectoy];
             zipEntry.IsVisible = true;
     }

     return zipEntry;
}

Damit haben wir alle Methoden beisammen, um ein echtes Verzeichnis des Archivs aufzubauen. So wird eine eine ZIP-Datei geöffnet und durchsucht:

// Archiv öffnen
ZipFile zipFile = new ZipFile(txtZipFileName.Text);

// Von der ersten Datei aus alle folgenden finden
ZipEntry zipEntry = zipFile[0];
AddListViewItem(zipEntry, lvAll);
int entryIndex = 0;
while (zipFile.HasSuccessor(zipEntry))
{
	zipEntry = zipFile.GetAttachedEntry(zipEntry);
	AddListViewItem(zipEntry, lvAll);
	entryIndex++;
}

Obwohl wir nun die vollständige ZipEntry-Auslistung kennen, können wir noch keine unsichtbaren Dateien extrahieren. Das liegt daran, dass ZipFile.GetInputStream() versucht, den Verzeichnisindex zu verwenden, der natürlich nur mit dem Platzhalter -1 gefüllt ist. Aber was wir praktisch nur brauchen, um den Inhalt einer Datei zu lesen, ist ihr Offset im Archiv-Stream: Haben wir die Eigenschaft Offset der ZipEntry-Objekte nicht schon beim Lesen gefüllt? GetInputStream(ZipEntry entry) weiß nur noch nichts davon. Aber das lässt sich ändern, indem ZipFile.GetInputStream() ersetzt und aufgeräumt wird .

public Stream GetInputStream(ZipEntry entry)
{
    if (entries == null) {
            throw new InvalidOperationException("ZipFile has closed");
    }

    /*
     * Original-Methode
     * Wird ersetzt, um "invisible" Einträge zu unterstützen
     *
    int index = entry.ZipFileIndex;
    if (index < 0 || index >= entries.Length || entries[index].Name != entry.Name) {
            index = FindEntry(entry.Name, true);
            if (index < 0) {
                    throw new IndexOutOfRangeException();
            }
    }
    return GetInputStream(index);
    */

    if (entries == null)
    {
            throw new InvalidOperationException("ZipFile is closed");
    }

    // Nicht nach ZipFileIndex suchen! I don't know why it was originally
    // implemented that way, but we know the data offset and indices are not
    // necessary. There are no indices for the invisible files.
    long start = CheckLocalHeader(entry);

    // Kopiert aus GetInputStream(int entryIndex)

    CompressionMethod method = entry.CompressionMethod;
    Stream istr = new PartialInputStream(baseStream, start, entry.CompressedSize);

    if (entry.IsCrypted == true)
    {
            istr = CreateAndInitDecryptionStream(istr, entry);
            if (istr == null)
            {
                    throw new ZipException("Unable to decrypt this entry");
            }
    }

    switch (method)
    {
            case CompressionMethod.Stored:
                    return istr;
            case CompressionMethod.Deflated:
                    return new InflaterInputStream(istr, new Inflater(true));
            default:
                    throw new ZipException("Unsupported compression method " + method);
    }
}

Fertig! Jetzt sind wir in der Lage, alle Dateien zu entpacken, inklusive unserer Geisterdateien. Die so gesammelten Dateien können nun gelesen werden.

private void UnZipFiles(string destinationDirectoryName)
{
       ZipFile zipFile = new ZipFile(txtZipFileName.Text);

       if (chkDecrypt.Checked)
       {
         zipFile.Password = txtOpenPassword.Text;
       }

       foreach (ListViewItem viewItem in lvAll.SelectedItems)
       {
         ZipEntry zipEntry = viewItem.Tag as ZipEntry;
         if (zipEntry != null)
         {
                 Stream inputStream = zipFile.GetInputStream(zipEntry);
                 FileStream fileStream = new FileStream(
                         Path.Combine(destinationDirectoryName, zipEntry.Name),
                         FileMode.Create);
                 CopyStream(inputStream, fileStream);
                 fileStream.Close();
                 inputStream.Close();
       }
 }

 zipFile.Close();
}

Jetzt gibt es für uns keinen großen Unterschied mehr zwischen sichtaren und versteckten ZIP-Einträgen. Unsere angepasste Bibliothek behandelt beide Varianten gleich gut: Ist die Eigenschaft ZipEntry.IsVisible vor dem Komprimieren auf false gesetzt, wird die Datei vor dem Central Directory versteckt - aber Anwendungen, die diese angepasste Version von SharpZipLib und HasSuccessor/GetAttachedEntry anstelle des Verzeichnis-Indexers verwenden, können sie dennoch finden und entpacken.

Die Demo-Anwendung

Die Demo-Anwendung kann neue ZIP-Archive erstellen oder vorhandene bearbeiten. Man kann sichtbare und unsichtbare Dateien hinzufügen/löschen, oder auch ein Archiv mit einem Kennwort versehen. Von Letzterem rate ich allerdings ab, da versteckte Dateien bei mehrmaligem Ver- und Entschlüsseln verloren gehen können. Im Bild unten wird eine unsichtbare Datei in ein vorhandenes Archiv eingefügt. Sichtbare Einträge stehen zusätzlich in der rechten Box, als Vorschau darauf, wie ein normales ZIP-Werkzeug den Inhalt anzeigen wird.

Die Checkboxes in der linken Liste legen fest, ob eine Datei im Central Directory verzeichnet wird oder nicht. Um eine Datei vor dem Inhaltsverzeichnis zu verbergen, entferne einfach den Haken. Mit "Delete" wird die markierte Datei aus dem Archiv gelöscht. "Extract selected files" entpackt jede beliebige Datei, versteckte und sichtbare werden genau gleich behandelt.

add a file

"Save changes" fragt nach einem neuen Dateinamen. Alle Dateien aus dem Archiv und die neu hinzugefügten werden komprimiert und ins neue Archiv eingefügt. Anschließend öffnet die Demo das neue Archiv, so dass es weiter bearbeitet werden kann.

Auf diesem Bild wurde das neue Archiv mit einer versteckten und zwei sichtbaren Dateien gerade gespeichert und wird als Nächstes mit dem Kennwort "hello" verschlüsselt.

encrypt an archive

VORSICHT: Wenn möglich solltest Du Verschlüsselung vermeiden oder zuerst ein unverschlüsseltes Archiv bearbeiten/speichern und die Verschlüsselung im allerletzten Schritt hinzufügen. Manchmal funktioniert es, manchmal verliert man alle versteckten Dateien außer der ersten. :-(
Gewöhnlich geht die erste Verschlüsselung gut, aber erneutes Speichern des bereits verschlüsselten Archivs macht die lokalen Header unverfolgbar. Besonders wenn es mehr als eine unsichtbare Datei im Archiv gibt, probiere das Verschlüsseln bitte erst, wenn alles schon sicher gespeichert ist.

C# Quellcode für MonoDevelop und Visual Studio - 49.62 kB

Worum geht es?

Menschen lieben Chaos. Viele Dinge könnten geordnet und sortiert werden, aber üblicherweise tun wir es nicht. Alles das eine eindeutige Ordnung haben könnte kann genutzt werden, um eine Zahl zu codieren. Denn es gibt Fakultaet(anzahl) mögliche Ordnungen welche man nummerieren kann.

Hier lernst du, wie du irgendeine Nachricht in der Sortierung beliebiger Dinge codieren kannst. (Vielleicht wirst du nachher aus reinem Spaß das Zimmer aufrämen.)

screen

Ich war ziemlich beeindruckt von Da wäre Peter's Beispiel wie man einen Text in einem Spiel mit 52 Karten versteckt. Der Algorithmus ist so klar verständlich und leicht zu implementieren. Deshalb habe ich ihn angepasst, um jeden beliebigen binären Datenstrom in jeder Collection<IComparable> zu speichern.

Die Klasse kann benutzt werden, um Sachen in - zum Beispiel - Noten, Einkaufslisten oder die Palette eines GIF-Bildes hinein zu codieren. Falls du den Sport Geo Caching magst, hast du oft mit Listen von Wegpunkten zu tun. Die Reihenfolge der Wegpunkte in einer LOC- oder GPX-Datei hängt vielleicht von der Zeit ab zu der du die Orte besuchen willst, von der Entfernung nach Hause oder schlicht vom Zufall. Das bedeutet, wir können den Spielkarten-Algorithmus auf deine Wegpunkte anwenden, um einen kurzen Text in der Reihenfolge der Orte zu speichern.

Dieser Artikel beschreibt die verallgemeinerte C#-Implementierung und stellt eine Demo-Anwendung sowohl für einfache Wortlisten als auch für Geo Caching-Dateien vor. Das Programm kann GPX- und LOC-Dateien importieren, durch Sortieren einen UTF-8-Text hinein codieren und das Ergebnis exportieren. (Wenn das niemand braucht, ist es immer noch ein schneller GPX-LOC-Konverter.)

Codieren durch Sortieren

Der Plan lautet, eine Collection von IComparable zu nehmen und die Objekte zu vertauschen, um den Inhalt eines Stream zu notieren:

public static void Encode<T>(
	Collection<T> source, // the carrier list
	Collection<T> result, // an empty list to store the result
	Stream messageStream) // the message to encode
	where T: class, IComparable
{

Jede Nachricht ist eine Zahl. Wir müssen nicht wissen, ob sie ein Text, eine Musikdatei oder sonstwas ist, denn wir werden den ganzen Stream als eine große Ganzzahl behandeln.

// initialize message

messageStream.Position = 0;
byte[] buffer = new byte[messageStream.Length];
messageStream.Read(buffer, 0, buffer.Length);
BigInteger message = new BigInteger(buffer);

Bevor wir eine Objektliste sortieren können, müssen wir einen Sortierschlüssel und seine Default-Reihenfolge festlegen. Für eine Liste von Personen könnten das die alphabetisch sortierten Namen sein. Geo Caches (Wegpunkte) lassen sich nach Koordinaten sortieren, oder nach ID, Name, Entfernung von zu Hause, ... wie auch immer, IComparable-Objekte vergleichen sich selbst. Wir sortieren die Trägerobjekte so wie sie es gern hätten und definieren diese Reihenfolge als "0".

// initialize source list in "0"-order
T[] sortedItems = new T[source.Count];
source.CopyTo(sortedItems, 0);
Array.Sort(sortedItems);

Eine Liste in Default-Reihenfolge (z.B. alphabetisch) codiert den Wert "0". Die ersten beiden Elemente zu vertauschen heißt "1". Eine Möglichkeit, die Elemente der Quellliste auf die freien Felder der Zielliste zu verteilen, ist die ganzzahlige Division: Für jedes Element der Quellliste teilen wir die Nachricht durch die Anzahl freier Felder und legen das Objekt [Rest] Felder von links ab. Folglich brauchen wir eine Trägerliste die genauso lang wie die Quellliste ist, und wir müssen die Anzahl gerade noch freier Felder darin kennen.

// initialize carrier

Collection<int> freeIndexes = new Collection<int>();
result.Clear();
for (int n = 0; n < source.Count; n++)
{
	freeIndexes.Add(n);
	result.Add(null);
}

Nach diese Vorbereitungen können wir über die Quellliste iterieren (die in "0"-Ordnung ist) und die neue Position jedes Objekts aus der noch übrigen Nachricht berechnen.

int skip = 0;
for (int indexSource = 0; indexSource < source.Count; indexSource++)
{
	skip = (message % freeIndexes.Count).IntValue();
	message = message / freeIndexes.Count;
	int resultIndex = freeIndexes[skip];
	result[resultIndex] = sortedItems[indexSource];
	freeIndexes.RemoveAt(skip);
}

Hier ist die vollständige Codier-Methode:

public static void Encode<T>(
	Collection<T> source, // the carrier list
	Collection<T> result, // an empty list to store the result
	Stream messageStream) // the message to encode
	where T: class, IComparable
{
	// sort source list into "0"-order
	T[] sortedItems = new T[source.Count];
	source.CopyTo(sortedItems, 0);
	Array.Sort(sortedItems);
	
	// initialize message
	messageStream.Position = 0;
	byte[] buffer = new byte[messageStream.Length];
	messageStream.Read(buffer, 0, buffer.Length);
	BigInteger message = new BigInteger(buffer);
	
	// initialize carrier
	Collection<int> freeIndexes = new Collection<int>();
	result.Clear();
	for (int n = 0; n < source.Count; n++)
	{
		freeIndexes.Add(n);
		result.Add(null);
	}

	// encode by integer division
	int skip = 0;
	for (int indexSource = 0; indexSource < source.Count; indexSource++)
	{
		skip = (message % freeIndexes.Count).IntValue();
		message = message / freeIndexes.Count;
		int resultIndex = freeIndexes[skip];
		result[resultIndex] = sortedItems[indexSource];
		freeIndexes.RemoveAt(skip);
	}
}

Decodieren der Sortierung

Diesmal beginnen wir mit der Trägerliste in besonderer Ordnung und einer Nachricht von "0". Für jedes Listenelement ist der Rest der ganzzahligen Division aus dem Codierprozess zu finden, so dass wir die Divisionen umkehren können. Woher wissen wir, wie viele freie Felder ein Objekt übersprungen hatte? Ganz einfach: Die Quellliste war in "0"-Ordnung, so dass nach einem Objekt nur noch "größere" Objekte folgen konnten. Das heißt, die Anzahl der "größeren" Elemente nach links ist genau der Sprungwert welcher genau der Rest der vorherigen Division ist.

Die Nachricht wurde durch die Anzahl freier Felder geteilt, was einen neuen Rest ergab. Vor diesem Schritt war sie bereits durch alle frühreren Anzahlen freier Felder geteilt worden. Deshalb könen wir den Sprungwert mit (list.Count - position) für jede vorherige Position multiplizieren, die Werte für alle Elemente aufsummieren - und das Ergebnis ist wieder die Nachricht als Zahl.

Hier ist die Decodier-Methode:

public static void Decode<T>(
	Collection<T> carrier, // the carrier list
	Stream messageStream)  // an empty tream to store the message
	where T : class, IComparable

{

	// get the source list in "0"-order
	T[] sortedItems = new T[carrier.Count];

	carrier.CopyTo(sortedItems, 0);
	Array.Sort(sortedItems);
	
	// initialize message
	BigInteger message = new BigInteger(0);

	for (int carrierIndex = 0; carrierIndex < carrier.Count; carrierIndex++)
	{
		// count skipped slots to reconstruct the division's remainder
		int skip = 0;

		for (int countIndex = 0; countIndex < carrierIndex; countIndex++)
		{
			if (carrier[countIndex].CompareTo(carrier[carrierIndex]) > 0)
			{ // There is a bigger item to the left. It's place
			  // must have been skipped by the current item.
				skip++;
			}
		}

		// Revert the division that resulted in this skip value
		int itemOrdinal = Array.IndexOf(sortedItems, carrier[carrierIndex])+1;
		BigInteger value = new BigInteger(skip);
		for (int countIndex = 1; countIndex < itemOrdinal; countIndex++)
		{
			value *= (carrier.Count - countIndex + 1);
		}

		message += value;
	}


	// write message
	byte[] messageBytes = message.getBytes();
	messageStream.Write(messageBytes, 0, messageBytes.Length);
	messageStream.Position = 0;
}

Flexiblible Sortierschlüssel

Beim sortieren von Objekten ist ein eindeutiger Sortierschlüssel wichtig: In einem Adressbuch können zwei Leute denselben Namen, aber eindeutige Geburtstage besitzen - in einem anderen Adressbuch sind sie Namen eindeutig, aber nicht die Geburtstage. Auf einer Route aus Wegpunkten mag es Punkte mit gleicher Länge oder Breite geben, jedoch mit eindeutigem Zeitstempel - auf anderen Routen kann die Höhe die einzige eindeutige Eigenschaft sein.

Da der beste Sortierschlüssel von den gegebenen Daten abhängt, sollte er eine Eigenschaft der Collection sein. Nachdem wir sie mit Comparable-Objekten gefüllt haben, sagen wir ihr einfach, welches Feld das Vergleichbare ist.

// fill the typesafe flexi-collection with objects
FlexibleComparableCollection<GeoCache> source = 
		new FlexibleComparableCollection<GeoCache>();
foreach (ListViewItem viewItem in lstGC.Items) {
	source.Add((GeoCache)viewItem.Tag);
}
// get the property name from the selected radio button
source.ComparablePropertyName = GetGCSortPropertyName();

Wie funktioniert das? Mit etwas Reflexion! FlexibleComparableCollection ist eine typsichere generische Collection. Wenn ComparablePropertyName gesetzt ist, schlägt sie die Eigenschaft mit diesem Namen in ihrem Elemente-Typ nach und informiert jedes Element.

public class FlexibleComparable : IComparable
{	// read the key value only when it changes
	private object comparableValue;
	internal void UpdateComparableValue(PropertyInfo comparableProperty)
	{
		this.comparableValue = comparableProperty.GetValue(this, null);
	}

	// Interface IComparable
	public int CompareTo(object obj)
	{
		IComparable thisValue = this.comparableValue as IComparable;
		if (thisValue == null) return -1;

		IComparable otherValue;
		FlexibleComparable other = obj as FlexibleComparable;
		
		// get the other's key value (if any), or compare to the whole object
		if (other == null) otherValue = other as IComparable;
		else otherValue = other.comparableValue as IComparable;
	
		// compare, if you can!
		if (otherValue == null) return 1;
		else return thisValue.CompareTo(otherValue);
	}
}

Das ist alles was du brauchst um jede Sammlung von irgendwas als Trägermedium zu nutzen. Du musst nur eine eindeutige Eigenschaft aussuchen oder erfinden und sicherstellen, dass die Nachricht in die Liste rein passt.

private void EncodeInSomething()
{	// set up carrier list
	FlexibleComparableCollection<Something> source = GetList();
	source.ComparablePropertyName = "ChosenField";
	// initialize message and destination list
	Stream message = TextToStream(txtMessage.Text);
	Collection<Something> result = new Collection<Something>();
	// encode message
	OrderUtility.Encode<Something>(source, result, message);
	SaveList(result);
}

private void DecodeInSomething()
{	// set up carrier list
	FlexibleComparableCollection<Something> carrier = GetList();
	carrier.ComparablePropertyName = "ChoseField";
	// decode message
	MemoryStream message = new MemoryStream();
	OrderUtility.Decode<Something>(carrier, message);
	txtMessage.Text = new StreamReader(message).ReadToEnd();
}

Die Demo-Anwendung

Die Anwendung lässt dich eine Wortliste eingeben und GPS-Daten importieren/bearbeiten. Sie zeigt die Kapazität der Liste an und codiert/decodiert Text. Zum besseren Verständnis werden auf der letzten Tab-Seite die Zahlen 1..256 als Liste verwendet, so dass offensichtlich wird, wie sich die Reihenfolge mit dem Text ändert.

Schlusswort

Mit diesen paar Zeilen Code kann man einen Sortierschlüssel auf einer Liste definieren, eine binäre Nachricht in die Reihenfolge der Liste codieren und wieder decodieren. Einzige Voraussetzung ist eine eindeutige Eigenschaft, aber sie muss nur für die betroffene Liste eindeutig sein, nicht allgemein für die Objektklasse.

Mit Dank an Chew Keong TAN für seine C# BigInteger Class und Peter Jerde für die Erklärung der Grundlagen.