Εισαγωγή
Χειρισμός bit
Κάθε bit ενός ακέραιου μπορεί να χρησιμοποιηθεί για να αποθηκεύσει μια δυαδική τιμή.
Επειδή πολλές καταστάσεις περιλαμβάνουν δυαδική πληροφορία, όπως αληθής ή ψευδής, συμπερίληψη ή αποκλεισμό, ενεργό ή ανενεργό, η δυαδική αναπαράσταση ενός ακέραιου N bit παρέχει έναν συμπαγή τρόπο κωδικοποίησης της δυαδικής κατάστασης N στοιχείων.
Αυτό κάνει την ικανότητα χειρισμού bit και byte απαραίτητη στη γλώσσα assembly.
Το σύνολο εντολών x86-64 προσφέρει μεγάλη ποικιλία εντολών χειρισμού bit.
Χειρισμός μεμονωμένων bit
Αυτές οι εντολές λειτουργούν σε μεμονωμένα bit ενός τελεστέου.
Όλες δέχονται δύο τελεστέους, ο δεύτερος υποδεικνύει τη θέση του bit στο οποίο γίνεται η πράξη στον πρώτο τελεστέο.
Όλες αντιγράφουν το επιλεγμένο bit στη σημαία μεταφοράς (CF).
| Όνομα |
Περιγραφή |
bt |
αντιγράφει το bit στο CF χωρίς να τροποποιεί κανέναν τελεστέο |
bts |
αντιγράφει το bit στο CF και το θέτει στον τελεστέο προορισμού |
btr |
αντιγράφει το bit στο CF και το καθαρίζει στον τελεστέο προορισμού |
btc |
αντιγράφει το bit στο CF και το συμπληρώνει (το αντιστρέφει) στον τελεστέο προορισμού |
Πράξεις bit
Οι πράξεις bit εκτελούνται σε όλα τα bit ενός τελεστέου.
Όλες έχουν μια εντολή με το ίδιο όνομα με την πράξη bit που εκτελείται:
| Όνομα |
Περιγραφή |
and |
1 αν και τα δύο bit είναι 1 |
or |
1 αν τουλάχιστον ένα από τα bit είναι 1 |
xor |
1 αν τα bit διαφέρουν |
not |
1 αν το bit ήταν 0, 0 αν το bit ήταν 1 |
Οι περισσότερες δέχονται δύο τελεστέους, εκτελούν μια πράξη bit και στους δύο και αποθηκεύουν το αποτέλεσμα στον τελεστέο προορισμού.
Η εξαίρεση είναι η not, η οποία δέχεται μόνο έναν τελεστέο προορισμού.
Μάσκες
Όταν ερμηνεύουμε το ένα και το μηδέν ως συμπερίληψη και αποκλεισμό αντίστοιχα, ένας ακέραιος ονομάζεται μάσκα bit (ή απλώς μάσκα).
Μια μάσκα bit "αποκλείει" στοιχεία, επειδή ένα μηδέν στο i-οστό bit αποκλείει το i-οστό στοιχείο, ενώ ένα ένα το συμπεριλαμβάνει.
Χρησιμοποιούμε επίσης συνήθως μια μάσκα bit για να συμπεριλάβουμε ορισμένα bit ενός ακέραιου και να αποκλείσουμε άλλα.
Για παράδειγμα, έστω A ένας ακέραιος του οποίου η δυαδική αναπαράσταση είναι:
| θέση |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| bit |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
Επίσης, έστω M ένας ακέραιος του οποίου η δυαδική αναπαράσταση είναι:
| θέση |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| bit |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
Και οι δύο είναι ακέραιοι 8 bit.
Σε αυτή την περίπτωση, μπορούμε να πούμε ότι ο M επιλέγει τα bit 0, 2 και 3 του A και αποκλείει τα υπόλοιπα.
Οι εντολές bit που συζητήσαμε νωρίτερα είναι χρήσιμες για τον χειρισμό ακεραίων με μάσκες.
Για παράδειγμα:
- Για να καθαρίσεις τα bit του
A που δεν επιλέγονται από τον M, κάνε το bitwise AND: A AND M.
- Για να θέσεις τα bit του
A που επιλέγονται από τον M, κάνε το bitwise OR: A OR M.
Εντολή TEST
Η εντολή test κάνει ένα bitwise AND μεταξύ των δύο τελεστέων και θέτει τις σημαίες ανάλογα με το αποτέλεσμα.
Αν ο A είναι ο πρώτος τελεστέος και ο B ο δεύτερος:
| σημαία |
τίθεται όταν |
CF |
καθαρίζεται πάντα |
ZF |
A AND B == 0 |
SF |
το bit προσήμου του A AND B είναι ορισμένο |
OF |
καθαρίζεται πάντα |
Αυτή η εντολή δέχεται δύο τελεστέους και ενημερώνει τις σημαίες, αλλά δεν τροποποιεί τους τελεστέους της.
Πράξεις ολίσθησης
Αυτές οι εντολές μετακινούν τα bit του τελεστέου προορισμού κατά έναν αριθμό θέσεων που καθορίζεται από τον δεύτερο τελεστέο.
Ο δεύτερος τελεστέος πρέπει να είναι ένας σταθερός αριθμός (ένα immediate) ή ο καταχωρητής cl (τα χαμηλότερα 8 bit του rcx).
| Όνομα |
Περιγραφή |
shl/sal
|
Μετατοπίζει τα bit προς τα αριστερά |
shr/sar
|
Μετατοπίζει τα bit προς τα δεξιά |
Σημείωσε ότι ο μετρητής στον δεύτερο τελεστέο περιορίζεται με μάσκα στα 5 bit, ή στα 6 bit όταν ο τελεστέος προορισμού είναι 64 bit.
Κάθε bit μετά από αυτά αγνοείται ουσιαστικά.
Αυτό σημαίνει ότι η μέγιστη ολίσθηση είναι 31, ή 63 με έναν τελεστέο 64 bit.
Shl / Sal
Οι shl και sal εκτελούν την ίδια ακριβώς πράξη, η μία είναι ψευδώνυμο της άλλης.
Κάθε φορά που γίνεται ολίσθηση προς τα αριστερά, τα bit που βρίσκονται πιο κοντά στο τέλος της ακολουθίας από όσο το μήκος της ολίσθησης μετακινούνται πρώτα στο CF και μετά απορρίπτονται.
Από την άλλη, ένας αριθμός νέων μηδενισμένων bit ίσος με το μήκος της ολίσθησης προστίθεται στην αρχή.
Επειδή κάθε bit ενός ακέραιου αντιπροσωπεύει μια δύναμη του 2, μια ολίσθηση προς τα αριστερά κατά n θέσεις έχει το αποτέλεσμα του πολλαπλασιασμού του ακέραιου επί 2ⁿ.
Shr / Sar
Υπάρχουν δύο εντολές για μετακίνηση bit προς τα δεξιά: οι shr και sar.
Κάθε φορά που χρησιμοποιείται οποιαδήποτε από τις δύο εντολές, τα bit που βρίσκονται πιο κοντά στην αρχή της ακολουθίας από όσο το μήκος της ολίσθησης μετακινούνται πρώτα στο CF και μετά απορρίπτονται.
Από την άλλη, ένας αριθμός νέων bit ίσος με το μήκος της ολίσθησης προστίθεται στο τέλος.
Η διαφορά μεταξύ τους είναι ότι η shr μετακινεί 0 bit στο αριστερό άκρο, ενώ η sar μετακινεί 1 αν το πιο σημαντικό bit ήταν ορισμένο και 0 διαφορετικά.
Αυτό σημαίνει ότι η sar διατηρεί το πρόσημο στην ολίσθηση ενός προσημασμένου ακέραιου.
Επειδή κάθε bit ενός ακέραιου αντιπροσωπεύει μια δύναμη του 2, μια ολίσθηση προς τα δεξιά κατά n θέσεις με τη χρήση της shr έχει το αποτέλεσμα μιας χωρίς πρόσημο διαίρεσης με το 2ⁿ.
Παρομοίως, μια ολίσθηση προς τα δεξιά κατά n θέσεις με τη χρήση της sar έχει το αποτέλεσμα μιας προσημασμένης διαίρεσης με το 2ⁿ.
Πράξεις περιστροφής
Αυτές οι εντολές μετακινούν τα bit του τελεστέου προορισμού κατά έναν αριθμό θέσεων που καθορίζεται από τον δεύτερο τελεστέο.
Ο δεύτερος τελεστέος πρέπει να είναι ένας σταθερός αριθμός (ένα immediate) ή ο καταχωρητής cl (τα χαμηλότερα 8 bit του rcx).
Η διαφορά μεταξύ μιας περιστροφής και μιας ολίσθησης είναι ότι η περιστροφή δεν απορρίπτει ούτε προσθέτει bit.
Τα bit που θα απορρίπτονταν από μια ολίσθηση μετακινούνται αντ' αυτού στο αντίθετο άκρο.
Έτσι, όλα τα bit παραμένουν, απλώς αλλάζουν όλα θέση.
| Όνομα |
Περιγραφή |
rol |
Περιστρέφει τα bit προς τα αριστερά |
ror |
Περιστρέφει τα bit προς τα δεξιά |
Σημείωσε ότι ο μετρητής στον δεύτερο τελεστέο περιορίζεται με μάσκα στα 5 bit, ή στα 6 bit όταν ο τελεστέος προορισμού είναι 64 bit.
Κάθε bit μετά από αυτά αγνοείται ουσιαστικά.
Αυτό σημαίνει ότι η μέγιστη περιστροφή είναι 31, ή 63 με έναν τελεστέο 64 bit.
Άλλες εντολές χειρισμού bit
Υπάρχουν και άλλες χρήσιμες εντολές χειρισμού bit:
| Όνομα |
Περιγραφή |
popcnt |
Μετράει τον αριθμό των bit που είναι ορισμένα |
bsr |
Παίρνει τη θέση του πιο σημαντικού ορισμένου bit. Αν δεν είναι ορισμένο κανένα bit, το αποτέλεσμα είναι απροσδιόριστο |
bsf |
Παίρνει τη θέση του λιγότερο σημαντικού ορισμένου bit. Αν δεν είναι ορισμένο κανένα bit, το αποτέλεσμα είναι απροσδιόριστο |
Αυτές οι εντολές λειτουργούν όλες με δύο τελεστέους των 16, 32 ή 64 bit.
Δεν μπορούν να χρησιμοποιηθούν με τελεστέους των 8 bit.
Οδηγίες
Ο φίλος σου μόλις σου έστειλε ένα μήνυμα με ένα σημαντικό μυστικό.
Επειδή δεν ήθελε να είναι εύκολο για τους άλλους να το διαβάσουν, το μήνυμα κρυπτογραφήθηκε με μια σειρά από χειρισμούς bit.
Θα χρειαστεί να γράψεις τις μεθόδους που θα βοηθήσουν στην αποκρυπτογράφηση του μηνύματος.
Αυτές είναι οι εντολές μεμονωμένου bit που αναφέρονται σε αυτή την έννοια:
| Όνομα |
Περιγραφή |
| bt |
αντιγράφει το bit στο CF χωρίς να τροποποιεί κανέναν τελεστέο |
| bts |
αντιγράφει το bit στο CF και το θέτει σε 1 στον τελεστέο προορισμού |
| btr |
αντιγράφει το bit στο CF και το μηδενίζει στον τελεστέο προορισμού |
| btc |
αντιγράφει το bit στο CF και το συμπληρώνει (το αντιστρέφει) στον τελεστέο προορισμού |
Αυτές είναι οι εντολές bitwise που αναφέρονται σε αυτή την έννοια:
| Όνομα |
Περιγραφή |
| and |
1 αν και τα δύο bit είναι 1 |
| or |
1 αν τουλάχιστον ένα από τα bit είναι 1 |
| xor |
1 αν τα bit διαφέρουν |
| not |
1 αν το bit ήταν 0, 0 αν το bit ήταν 1 |
Αυτές είναι οι εντολές μετατόπισης που αναφέρονται σε αυτή την έννοια:
| Όνομα |
Περιγραφή |
| shl/sal |
Μετατοπίζει τα bit προς τα αριστερά |
| shr/sar |
Μετατοπίζει τα bit προς τα δεξιά |
Αυτές είναι οι εντολές περιστροφής που αναφέρονται σε αυτή την έννοια:
| Όνομα |
Περιγραφή |
| rol |
Περιστρέφει τα bit προς τα αριστερά |
| ror |
Περιστρέφει τα bit προς τα δεξιά |
Αυτές είναι οι λοιπές εντολές που αναφέρονται σε αυτή την έννοια:
| Όνομα |
Περιγραφή |
| popcnt |
Μετράει τον αριθμό των ορισμένων bit |
| bsr |
Δίνει τη θέση του πιο σημαντικού ορισμένου bit. Αν δεν έχει οριστεί κανένα bit, το αποτέλεσμα είναι απροσδιόριστο |
| bsf |
Δίνει τη θέση του λιγότερο σημαντικού ορισμένου bit. Αν δεν έχει οριστεί κανένα bit, το αποτέλεσμα είναι απροσδιόριστο |
1. Εξαγωγή της μάσκας
Το μήνυμα είναι κωδικοποιημένο σε έναν ακέραιο 16 bit.
Ωστόσο, από αυτά, τα 8 υψηλότερα bit δεν είναι στην πραγματικότητα μέρος του μηνύματος, αλλά μια μάσκα που πρέπει να χρησιμοποιηθεί στην αποκρυπτογράφηση.
Υλοποίησε τη συνάρτηση extract_higher_bits, η οποία δέχεται έναν ακέραιο 16 bit και επιστρέφει τα 8 υψηλότερα bit του.
extract_higher_bits(0b1010010011000101)
// => 0b10100100
2. Εξαγωγή του μηνύματος
Το να μπορείς να εξάγεις τη μάσκα δεν αρκεί, θα πρέπει επίσης να απομονώσεις το μήνυμα.
Υλοποίησε τη συνάρτηση extract_lower_bits, η οποία δέχεται έναν ακέραιο 16 bit και επιστρέφει τα 8 χαμηλότερα bit του.
extract_lower_bits(0b1010010011000101);
// => 0b11000101
3. Εξαγωγή των πλεοναζόντων bit
Μερικά bit είναι ορισμένα τόσο στο μήνυμα όσο και στη μάσκα.
Αυτή είναι μια πολύ σημαντική πληροφορία που θα χρησιμοποιηθεί αργότερα.
Υλοποίησε τη συνάρτηση extract_redundant_bits, η οποία δέχεται έναν ακέραιο 16 bit, που κωδικοποιεί τόσο το μήνυμα όσο και μια μάσκα, και επιστρέφει έναν ακέραιο 8 bit με ορισμένα μόνο τα πλεονάζοντα bit.
Ένα bit στον αριθμό που επιστρέφεται θα πρέπει να ορίζεται σε 1 όπου είναι επίσης 1 τόσο στο μήνυμα όσο και στη μάσκα.
Όλα τα άλλα bit θα πρέπει να μηδενίζονται.
extract_redundant_bits(0b1010010011000101);
// => 0b10000100
4. Ορισμός όλων των bit του μηνύματος
Στη συνέχεια, υπάρχουν κάποια bit που πρέπει να οριστούν σε 1 στο μήνυμα, σύμφωνα με τη μάσκα.
Υλοποίησε τη συνάρτηση set_message_bits, η οποία δέχεται έναν ακέραιο 16 bit, που κωδικοποιεί τόσο το μήνυμα όσο και μια μάσκα, και επιστρέφει το αποτέλεσμα του ορισμού των bit του μηνύματος σε 1.
Ένα bit του μηνύματος θα πρέπει να ορίζεται σε 1 όπου το bit στη μάσκα είναι 1.
Όλα τα άλλα bit θα πρέπει να παραμένουν αμετάβλητα, ώστε να παραμένουν ορισμένα αν ήταν ήδη ορισμένα, και μηδενισμένα αν ήταν ήδη μηδενισμένα.
set_message_bits(0b1010010011000101);
// => 0b11100101
5. Περιστροφή του ιδιωτικού κλειδιού
Υπάρχει ένα κομμάτι του παζλ που δεν είναι ρητά στο μήνυμα: ο αριθμός 16 bit 0b1011001100111100.
Αυτός ο αριθμός είναι το κοινόχρηστο ιδιωτικό κλειδί σου και θα πρέπει να το χρησιμοποιήσεις για να βοηθήσεις στην αποκρυπτογράφηση του μηνύματος.
Για να το κάνεις αυτό, πρέπει πρώτα να περιστρέψεις τα bit του ιδιωτικού κλειδιού σου προς τα αριστερά κατά έναν ορισμένο αριθμό θέσεων.
Ο αριθμός των θέσεων είναι ίσος με τον αριθμό των πλεοναζόντων bit που είναι ορισμένα τόσο στο μήνυμα όσο και στη μάσκα.
Υλοποίησε τη συνάρτηση rotate_private_key, η οποία δέχεται έναν ακέραιο 16 bit, που κωδικοποιεί τόσο το μήνυμα όσο και μια μάσκα, και επιστρέφει το αποτέλεσμα της περιστροφής του ιδιωτικού κλειδιού σου.
Αυτό το αποτέλεσμα είναι ένας ακέραιος 16 bit.
rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
Ο NASM (The Netwide Assembler, ο assembler που χρησιμοποιεί αυτό το track) υποστηρίζει σταθερές σε δυαδική μορφή με πρόθεμα 0b.
Υποστηρίζει επίσης τη χρήση κάτω παύλας (_) ως διαχωριστικού σε μια σταθερά, για ευκολία ανάγνωσης:
PRIVATE_KEY equ 0b1011_0011_0011_1100
6. Μορφοποίηση του ιδιωτικού κλειδιού
Για να χρησιμοποιηθεί στην αποκρυπτογράφηση, το ιδιωτικό κλειδί σου πρέπει να μορφοποιηθεί ώστε να απομονώσει τα σχετικά bit.
Για να μορφοποιήσεις πλήρως ένα ιδιωτικό κλειδί, πρέπει:
- Να το περιστρέψεις.
- Να απομονώσεις το χαμηλότερο τμήμα 8 bit του περιστρεμμένου ιδιωτικού κλειδιού, που είναι η βασική τιμή.
- Να απομονώσεις το υψηλότερο τμήμα 8 bit του περιστρεμμένου ιδιωτικού κλειδιού, που είναι μια μάσκα που θα εφαρμοστεί στη βασική τιμή.
- Να αντιστρέψεις τα bit της βασικής τιμής που είναι επίσης ορισμένα στη μάσκα.
- Να αντιστρέψεις όλα τα bit του αποτελέσματος.
Ένα αντεστραμμένο bit είναι 1 αν ήταν 0 και 0 αν ήταν 1.
Υλοποίησε τη συνάρτηση format_private_key, η οποία δέχεται έναν ακέραιο 16 bit, που κωδικοποιεί τόσο το μήνυμα όσο και μια μάσκα, και επιστρέφει ένα πλήρως μορφοποιημένο ιδιωτικό κλειδί 8 bit.
format_private_key(0b1010010011000101);
// => 0b11000001
7. Ολοκλήρωση της αποκρυπτογράφησης
Μόλις έχεις το μήνυμα με όλα τα σχετικά bit ορισμένα και το μορφοποιημένο ιδιωτικό κλειδί, ήρθε η ώρα να τα ενώσεις για να πάρεις το τελικό μήνυμα.
Το μήνυμα που προκύπτει είναι ένας ακέραιος 16 bit, του οποίου:
- Τα 8 υψηλότερα bit συμπληρώνονται με το μορφοποιημένο ιδιωτικό κλειδί.
- Τα 8 χαμηλότερα bit συμπληρώνονται με το μήνυμα, αφού οριστούν όλα τα σχετικά bit.
Υλοποίησε τη συνάρτηση decrypt_message, η οποία δέχεται έναν ακέραιο 16 bit που κωδικοποιεί τόσο το μήνυμα όσο και μια μάσκα, και επιστρέφει έναν ακέραιο 16 bit με το μήνυμα πλήρως αποκρυπτογραφημένο.
Αυτή η συνάρτηση θα πρέπει να χρησιμοποιεί το μορφοποιημένο ιδιωτικό κλειδί που παράγεις με τη format_private_key και επίσης το μήνυμα με όλα τα σχετικά bit ορισμένα με τη set_message_bits.
decrypt_message(0b1010010011000101);
// => 0b1100000111100101
Άσκηση εκμάθησης
