Einführung
Bitmanipulation
Jedes Bit einer Ganzzahl kann verwendet werden, um einen binären Wert zu speichern.
Weil viele Situationen binäre Informationen betreffen (wahr oder falsch, eingeschlossen oder ausgeschlossen, an oder aus), bietet die binäre Darstellung einer N-Bit-Ganzzahl eine kompakte Möglichkeit, den binären Zustand von N Elementen zu kodieren.
Deshalb ist die Fähigkeit, Bits und Bytes zu manipulieren, in Assembler unverzichtbar.
Der Befehlssatz x86-64 bietet eine große Vielfalt an bitweisen Manipulationsbefehlen.
Manipulation einzelner Bits
Diese Befehle arbeiten mit einzelnen Bits in einem Operanden.
Sie alle nehmen zwei Operanden, wobei der zweite den Index des Bits angibt, das im ersten Operanden bearbeitet wird.
Alle von ihnen kopieren das ausgewählte Bit in das Carry-Flag (CF).
| Name |
Beschreibung |
bt |
kopiert das Bit nach CF, ohne einen Operanden zu verändern |
bts |
kopiert das Bit nach CF und setzt es im Zieloperanden |
btr |
kopiert das Bit nach CF und löscht es im Zieloperanden |
btc |
kopiert das Bit nach CF und invertiert (kippt) es im Zieloperanden |
Bitweise Operationen
Bitweise Operationen werden auf alle Bits eines Operanden angewendet.
Für sie alle gibt es einen Befehl mit demselben Namen wie die ausgeführte bitweise Operation:
| Name |
Beschreibung |
and |
1, wenn beide Bits 1 sind |
or |
1, wenn mindestens eines der Bits 1 ist |
xor |
1, wenn die Bits sich unterscheiden |
not |
1, wenn das Bit 0 war; 0, wenn das Bit 1 war |
Die meisten von ihnen nehmen zwei Operanden, führen eine bitweise Operation mit beiden aus und speichern das Ergebnis im Zieloperanden.
Die Ausnahme ist not, der nur einen einzigen Zieloperanden nimmt.
Masken
Wenn wir Eins und Null als Einschluss bzw. Ausschluss interpretieren, nennt man eine Ganzzahl eine Bitmaske (oder einfach eine Maske).
Eine Bitmaske „maskiert“ Elemente aus, weil eine Null im i-ten Bit das i-te Element ausschließt, während eine Eins es einschließt.
Wir verwenden eine Bitmaske auch häufig, um bestimmte Bits einer Ganzzahl einzuschließen und andere auszuschließen.
Zum Beispiel sei A eine Ganzzahl mit folgender binärer Darstellung:
| Index |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| Bits |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
Und sei M eine Ganzzahl mit folgender binärer Darstellung:
| Index |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| Bits |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
Beide sind 8-Bit-Ganzzahlen.
In diesem Fall können wir sagen, dass M die Bits 0, 2 und 3 von A auswählt und die übrigen ausschließt.
Die zuvor besprochenen bitweisen Befehle sind nützlich, um Ganzzahlen mit Masken zu manipulieren.
Zum Beispiel:
- Um die Bits von
A zu löschen, die nicht von M ausgewählt werden, nimm das bitweise AND: A AND M.
- Um die von
M ausgewählten Bits von A zu setzen, nimm das bitweise OR: A OR M.
Der TEST-Befehl
Der test-Befehl führt ein bitweises AND zwischen beiden Operanden aus und setzt die Flags entsprechend dem Ergebnis.
Wenn A der erste Operand und B der zweite ist:
| Flag |
gesetzt, wenn |
CF |
immer gelöscht |
ZF |
A AND B == 0 |
SF |
das Vorzeichenbit von A AND B gesetzt ist |
OF |
immer gelöscht |
Dieser Befehl nimmt zwei Operanden und aktualisiert die Flags, verändert seine Operanden aber nicht.
Schiebeoperationen
Diese Befehle verschieben die Bits im Zieloperanden um eine Anzahl von Positionen, die der zweite Operand angibt.
Der zweite Operand muss eine konstante Zahl (ein immediate) oder das Register cl sein (die niedrigsten 8 Bits von rcx).
| Name |
Beschreibung |
shl/sal
|
Verschiebt Bits nach links |
shr/sar
|
Verschiebt Bits nach rechts |
Beachte, dass die Anzahl im zweiten Operanden auf 5 Bits maskiert wird, bzw. auf 6 Bits bei einem 64-Bit-Zieloperanden.
Jedes weitere Bit wird effektiv ignoriert.
Das bedeutet, dass die maximale Verschiebung 31 beträgt, bzw. 63 bei einem 64-Bit-Operanden.
Shl / Sal
shl und sal führen exakt dieselbe Operation aus, einer ist ein Alias des anderen.
Bei einer Verschiebung nach links werden Bits, die näher am Ende der Sequenz liegen als die Länge der Verschiebung, zuerst nach CF verschoben und dann verworfen.
Andererseits wird am Anfang eine Anzahl neuer gelöschter Bits gleich der Länge der Verschiebung hinzugefügt.
Da jedes Bit in einer Ganzzahl eine Zweierpotenz repräsentiert, hat eine Verschiebung nach links um n Positionen den Effekt, die Ganzzahl mit 2ⁿ zu multiplizieren.
Shr / Sar
Es gibt zwei Befehle, um Bits nach rechts zu verschieben: shr und sar.
Wenn einer der beiden Befehle verwendet wird, werden Bits, die näher am Anfang der Sequenz liegen als die Länge der Verschiebung, zuerst nach CF verschoben und dann verworfen.
Andererseits wird am Ende eine Anzahl neuer Bits gleich der Länge der Verschiebung hinzugefügt.
Der Unterschied zwischen ihnen ist, dass shr mit 0 auffüllt, während sar mit 1 auffüllt, wenn das höchstwertige Bit gesetzt war, und sonst mit 0.
Das bedeutet, dass sar das Vorzeichen bei der Verschiebung einer vorzeichenbehafteten Ganzzahl erhält.
Da jedes Bit in einer Ganzzahl eine Zweierpotenz repräsentiert, hat eine Verschiebung nach rechts um n Positionen mit shr den Effekt einer vorzeichenlosen Division durch 2ⁿ.
Ebenso hat eine Verschiebung nach rechts um n Positionen mit sar den Effekt einer vorzeichenbehafteten Division durch 2ⁿ.
Rotationsoperationen
Diese Befehle verschieben die Bits im Zieloperanden um eine Anzahl von Positionen, die der zweite Operand angibt.
Der zweite Operand muss eine konstante Zahl (ein immediate) oder das Register cl sein (die niedrigsten 8 Bits von rcx).
Der Unterschied zwischen einer Rotation und einer Verschiebung ist, dass eine Rotation keine Bits verwirft oder hinzufügt.
Bits, die bei einer Verschiebung verworfen würden, werden stattdessen an das entgegengesetzte Ende verschoben.
Alle Bits bleiben also erhalten, sie tauschen nur die Plätze.
| Name |
Beschreibung |
rol |
Rotiert Bits nach links |
ror |
Rotiert Bits nach rechts |
Beachte, dass die Anzahl im zweiten Operanden auf 5 Bits maskiert wird, bzw. auf 6 Bits bei einem 64-Bit-Zieloperanden.
Jedes weitere Bit wird effektiv ignoriert.
Das bedeutet, dass die maximale Rotation 31 beträgt, bzw. 63 bei einem 64-Bit-Operanden.
Weitere Bitmanipulationsbefehle
Es gibt weitere nützliche Bitmanipulationsbefehle:
| Name |
Beschreibung |
popcnt |
Zählt die Anzahl der gesetzten Bits |
bsr |
Ermittelt den Index des höchstwertigen gesetzten Bits. Wenn kein Bit gesetzt ist, ist das Ergebnis undefiniert |
bsf |
Ermittelt den Index des niedrigstwertigen gesetzten Bits. Wenn kein Bit gesetzt ist, ist das Ergebnis undefiniert |
Diese Befehle arbeiten alle mit zwei 16-Bit-, 32-Bit- oder 64-Bit-Operanden.
Sie können nicht mit 8-Bit-Operanden verwendet werden.
Anleitung
Dein Freund hat dir gerade eine Nachricht mit einem wichtigen Geheimnis geschickt.
Damit es andere nicht leicht lesen können, wurde die Nachricht verschlüsselt, indem eine Reihe von Bit-Manipulationen durchgeführt wurde.
Du musst die Methoden schreiben, die dir helfen, die Nachricht zu entschlüsseln.
Dies sind die Einzelbit-Befehle, die in diesem Konzept erwähnt werden:
| Name |
Beschreibung |
| bt |
kopiert das Bit nach CF, ohne einen Operanden zu verändern |
| bts |
kopiert das Bit nach CF und setzt es im Zieloperanden |
| btr |
kopiert das Bit nach CF und löscht es im Zieloperanden |
| btc |
kopiert das Bit nach CF und invertiert (kippt) es im Zieloperanden |
Dies sind die bitweisen Befehle, die in diesem Konzept erwähnt werden:
| Name |
Beschreibung |
| and |
1, wenn beide Bits 1 sind |
| or |
1, wenn mindestens eines der Bits 1 ist |
| xor |
1, wenn sich die Bits unterscheiden |
| not |
1, wenn das Bit 0 war; 0, wenn das Bit 1 war |
Dies sind die Schiebebefehle, die in diesem Konzept erwähnt werden:
| Name |
Beschreibung |
| shl/sal |
Verschiebt Bits nach links |
| shr/sar |
Verschiebt Bits nach rechts |
Dies sind die Rotationsbefehle, die in diesem Konzept erwähnt werden:
| Name |
Beschreibung |
| rol |
Rotiert Bits nach links |
| ror |
Rotiert Bits nach rechts |
Dies sind die sonstigen Befehle, die in diesem Konzept erwähnt werden:
| Name |
Beschreibung |
| popcnt |
Zählt die Anzahl der gesetzten Bits |
| bsr |
Ermittelt den Index des höchstwertigen gesetzten Bits. Ist kein Bit gesetzt, ist das Ergebnis undefiniert |
| bsf |
Ermittelt den Index des niedrigstwertigen gesetzten Bits. Ist kein Bit gesetzt, ist das Ergebnis undefiniert |
Die Nachricht ist in einer 16-Bit-Ganzzahl kodiert.
Von diesen sind die 8 höchsten Bits allerdings nicht wirklich Teil der Nachricht, sondern eine Maske, die bei der Entschlüsselung verwendet werden muss.
Implementiere die Funktion extract_higher_bits, die eine 16-Bit-Ganzzahl entgegennimmt und deren 8 höchste Bits zurückgibt.
extract_higher_bits(0b1010010011000101)
// => 0b10100100
Die Maske extrahieren zu können, reicht nicht aus: Du solltest auch die Nachricht isolieren.
Implementiere die Funktion extract_lower_bits, die eine 16-Bit-Ganzzahl entgegennimmt und deren 8 niedrigste Bits zurückgibt.
extract_lower_bits(0b1010010011000101);
// => 0b11000101
Einige Bits sind sowohl in der Nachricht als auch in der Maske gesetzt.
Das ist eine sehr wichtige Information, die später verwendet wird.
Implementiere die Funktion extract_redundant_bits, die eine 16-Bit-Ganzzahl entgegennimmt, in der sowohl die Nachricht als auch eine Maske kodiert sind, und eine 8-Bit-Ganzzahl zurückgibt, in der nur die redundanten Bits gesetzt sind.
Ein Bit in der zurückgegebenen Zahl sollte auf 1 gesetzt sein, wenn es auch in der Nachricht und in der Maske 1 ist.
Alle anderen Bits sollten gelöscht werden.
extract_redundant_bits(0b1010010011000101);
// => 0b10000100
4. Alle Nachrichtenbits setzen
Als Nächstes gibt es einige Bits, die gemäß der Maske in der Nachricht auf 1 gesetzt werden müssen.
Implementiere die Funktion set_message_bits, die eine 16-Bit-Ganzzahl entgegennimmt, in der sowohl die Nachricht als auch eine Maske kodiert sind, und das Ergebnis zurückgibt, nachdem die Bits in der Nachricht auf 1 gesetzt wurden.
Ein Bit der Nachricht sollte auf 1 gesetzt werden, wenn das Bit in der Maske 1 ist.
Alle anderen Bits sollten unverändert bleiben, sodass sie gesetzt bleiben, wenn sie bereits gesetzt waren, und gelöscht bleiben, wenn sie bereits gelöscht waren.
set_message_bits(0b1010010011000101);
// => 0b11100101
5. Privaten Schlüssel rotieren
Ein Puzzlestück steckt nicht ausdrücklich in der Nachricht: die 16-Bit-Zahl 0b1011001100111100.
Diese Zahl ist dein gemeinsamer privater Schlüssel, und du solltest sie verwenden, um die Nachricht zu entschlüsseln.
Dazu musst du zuerst die Bits deines privaten Schlüssels um eine bestimmte Anzahl von Positionen nach links rotieren.
Die Anzahl der Positionen entspricht der Anzahl der redundanten Bits, die sowohl in der Nachricht als auch in der Maske gesetzt sind.
Implementiere die Funktion rotate_private_key, die eine 16-Bit-Ganzzahl entgegennimmt, in der sowohl die Nachricht als auch eine Maske kodiert sind, und das Ergebnis der Rotation deines privaten Schlüssels zurückgibt.
Dieses Ergebnis ist eine 16-Bit-Ganzzahl.
rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
NASM (der Netwide Assembler, der Assembler, der in diesem Track verwendet wird) unterstützt Konstanten im Binärformat mit dem Präfix 0b.
Außerdem unterstützt er die Verwendung eines Unterstrichs (_) als Trennzeichen in einer Konstante, um die Lesbarkeit zu verbessern:
PRIVATE_KEY equ 0b1011_0011_0011_1100
Damit er bei der Entschlüsselung verwendet werden kann, muss dein privater Schlüssel formatiert werden, um die relevanten Bits zu isolieren.
Um einen privaten Schlüssel vollständig zu formatieren, musst du:
- ihn rotieren.
- den niedrigsten 8-Bit-Anteil des rotierten privaten Schlüssels isolieren, der der Basiswert ist.
- den höchsten 8-Bit-Anteil des rotierten privaten Schlüssels isolieren, der eine Maske ist, die auf den Basiswert angewendet wird.
- Bits im Basiswert umdrehen, die auch in der Maske gesetzt sind.
- alle Bits im Ergebnis umdrehen.
Ein umgedrehtes Bit ist 1, wenn es 0 war, und 0, wenn es 1 war.
Implementiere die Funktion format_private_key, die eine 16-Bit-Ganzzahl entgegennimmt, in der sowohl die Nachricht als auch eine Maske kodiert sind, und einen vollständig formatierten 8-Bit-Schlüssel zurückgibt.
format_private_key(0b1010010011000101);
// => 0b11000001
7. Entschlüsselung abschließen
Sobald du die Nachricht mit allen gesetzten relevanten Bits und den formatierten privaten Schlüssel hast, ist es an der Zeit, sie zusammenzufügen, um die resultierende Nachricht zu erhalten.
Die resultierende Nachricht ist eine 16-Bit-Ganzzahl, bei der:
- die höchsten 8 Bits mit dem formatierten privaten Schlüssel gefüllt werden.
- die niedrigsten 8 Bits mit der Nachricht gefüllt werden, nachdem alle relevanten Bits gesetzt wurden.
Implementiere die Funktion decrypt_message, die eine 16-Bit-Ganzzahl entgegennimmt, in der sowohl die Nachricht als auch eine Maske kodiert sind, und eine 16-Bit-Ganzzahl mit der vollständig entschlüsselten Nachricht zurückgibt.
Diese Funktion sollte den formatierten privaten Schlüssel nutzen, den du mit format_private_key erzeugst, und außerdem die Nachricht, bei der alle relevanten Bits mit set_message_bits gesetzt wurden.
decrypt_message(0b1010010011000101);
// => 0b1100000111100101
Lernübung
