[HaBo]

speedo

Hallo HABO-Leser!

In den letzten Tagen habe ich mich mit dem Serpent-Algorithmus beschäftigt. Nun hab ich es geschafft, es mit der Permutation (also nicht im Bitslice-Modus) zu implementieren. Jetzt, wo ich mich an die Bitslice-Sache wagen möchte, also die S-Boxen, die aus logischen Operationen bestehen und nicht auf Table-Lookups basieren. Diese in den Code einzufügen mag ja recht einfach sein, aber welche Logik dahinter steckt, ist mir bisher noch nicht klar. Gibt es irgendwo Dokumente die mir weiterhelfen, das zu verstehen?


LG, speedo

Elderan

Hallo,
evt. mal nach Allgemeinen Prinzipien von Bitslice suchen.


Stell dir die S-Boxen einfach vor wie eine Abbildung, sie nehmen einen Input entgegen und bilden diese auf eine andere Bit-Zahl ab.

Hat man z.B. die S-Box (für ein 2 Bit Input):
sbox = new int[] {0,0x08,0x10,0x18};

wäre dies die gleiche wie:
sbox = new int[] {0,8,16,24};

Die Bitslice Variante wäre dann:
new_2_bit_number = old_2_bit_number*8;
bzw. new_2_bit_number = old_2_bit_number<<2;

statt:
new_2_bit_number = sbox[old_2_bit_number];


Dies ist eine ganz simple Umwandlung.

Die Permutationen in echten Algorithmen sind erheblich komplex, womit die Bitslice Varianten auch deutlich umfangreicher sind.

Allerdings: Nicht unbedingt jede S-Box lässt sich gut per Bitslice simulieren, da diese nicht linear sein sollen (und ggf. zu groß sind).
Mit Bit-Slice versucht man oft auch unangenehme Permutationen zu realisieren, wie es z.B. bei DES notwendig ist.

Ansonsten such auch mal nach DES+Bitslice oder AES+Bitslice.

Also Einstieg evt:
http://www2.informatik.hu-berlin.de/...ent/node6.html

speedo

So habe ich mir das auch ansatzweise vorgestellt.

Auf dieser Seite hat wohl jemand ein Programm geschrieben, das durch Probieren eine richtige Kombination aus Logik-Operatoren für jede SBox findet: http://fp.gladman.plus.com/cryptogra...ology/serpent/


Ich frage mich nun, wie die Serpent-Entwickler vorgegangen sind um zu ihren Bitslice-SBoxen zu gelangen. Haben die das auf eine ähnliche Weise gemacht oder steckt da ein mathematischer "Trick" hinter?

Elderan

Hallo,
die Orginal-Implementierung von Serpent war die BitSlice Variante, dieses wurde aber beim Einreichen auf S-Boxen umgestellt.

Sie hatten also nicht das Problem, eine performante BitSlice Variante aus den S Boxen zu erstellen sondern konnten die simple Richtung gehen, hin zu S Boxen (eine logische Schaltung über ein Speicher zu realisieren ist trivial).

speedo

Also waren die Sboxen einst als Logik-Operation gedacht und nicht als Lookup-Table.

Ich werde mir mal die Implementation auf den MMX-Registern von diesem dr. gladman ansehen, das sieht recht übersichtlich aus. Danke aber schonmal für diesen kleinen Hinweis

speed0