## Textcodierung Bei der [[gf_informatik:verschluesselung:caesar]] haben wir bereits den Text in Zahlen verwandelt, um mit den Zahlen rechnen zu können. Wir sagen diesem Vorgehen auch **Textcodierung**. Typischerweise verwandeln wir dabei jeden Buchstaben in eine Binärzahl. Eine gängige Codierung von Text verwendet die [[wpde>American_Standard_Code_for_Information_Interchange#ASCII-Tabelle|ASCII-Codierung]]. Weshalb tun wir das? Der Vorteil ist, dass wir mit einem binären Code nicht nur Texte, sondern auch alle anderen Daten (Bilder, Videos...) verschlüsseln können. **Achtung:** Textcodierung ist noch keine Verschlüsselung, sondern nur eine 1:1 Übersetzung in ein anderes Datenformat. [[https://cryptii.com/pipes/PbRHzQ|Probier es aus]]! ### Python In Python können wir einen Buchstaben mit der `ord()` Funktion in die entsprechende ASCII-Zahl verwandeln, und mit `chr()` wieder zurück: letter = 'A' # Muss ein einzelner Buchstabe sein! print(ord(letter)) print(chr(65)) Um die Zahl im Binärformat auszugeben, können wir die `format()` Funktion wie folgt verwenden: print(format(65, "b")) #### String Formatierung Oft möchten wir einen längeren Text ausgeben, wobei nur einzelne Teile an der richtigen Stelle eingefügt werden sollen. Dafür verwenden wir einen f-String, d.h. vor dem ersten Anführungszeichen steht der Buchstabe `f`. Im String können mit geschweiften Klammern Python-Ausdrücke (z.B. Variablen) in die Ausgabe eingefügt werden: name = "Papa Moll" age = 42 print(f"Ich heisse {name} und bin {age*365} Tage alt.") Um das Ausgabeformat des Arguments zu kontrollieren, fügen wir im entsprechenden Platzhalter eine _[[https://docs.python.org/3/library/string.html#format-specification-mini-language|Format Specification]]_ ein: nach der Variablen wird nach einem Doppelpunkt das Ausgabeformat eingeben, in Beispiel unten `07b`. Das `b` bedeutet wie oben die Ausgabe als Binärzahl; die vorangestellte `7` gibt die Breite (_width_) an, also, dass mindestens sieben Zeichen verwendet werden sollen; die `0` gibt an, mit welchem Zeichen wir die Zahl auffüllen wollen, wenn die Breite nicht erreicht wird: # Die gleiche Zahl wird zweimal ausgegeben: # einmal im normalen Dezimalformat, # einmal als Binärzahl (b) # - mit einer Breite von mindestens 7 Stellen # - vorne mit Nullen (0) aufgefüllt. number = 42 print(f"Die Binärform von {number} ist {number:07b}") ### Aufgabe 1: ASCII-Tabelle erzeugen Drucke eine ASCII-Tabelle aus mit folgenden Einträgen: Buchstaben `a-z`, `A-Z`, Zifferen `0-9`, Leerzeichen ` `, Punkt `.` Für jeden Eintrag soll der Buchstabe sowie seine ASCII-Codierung in Dezimal- und im Binärformat enthalten sein. Das Binärformat soll 8 bits (=1 byte) enthalten und vorne mit Nullen aufgefüllt werden. ``` A | 65 | 01000001 B | 66 | 01000010 C | 67 | 01000011 D | 68 | 01000100 ... ``` ++++Lösung:| def printEntry(code): print(f"{chr(code):2} | {code:7d} | {code:08b}") def printTable(): print("CH | DECIMAL | BINARY") printEntry(ord(' ')) printEntry(ord('.')) for code in range(ord('0'),ord('9')+1): printEntry(code) for code in range(ord('A'),ord('Z')+1): printEntry(code) for code in range(ord('a'),ord('z')+1): printEntry(code) printTable() ++++ ## XOR Da wir jetzt mit Bits arbeiten statt mit Buchstaben, müssen wir uns eine neue Verschlüsselungstechnik ausdenken. Eine Verschiebung wie bei der Cäsar-Verschlüsselung macht nicht mehr viel Sinn, wenn nur noch die Zeichen `0` und `1` zur Verfügung stehen. Eine einfache Operation auf Bits ist die XOR (_eXclusive OR_) Operation. Wie der Name andeutet werden bei der XOR-Operation zwei Bits so verknüpft, dass das Resultat genau dann `1` ist, wenn der eine oder der andere der Operanden `1` ist, aber nicht beide. Die folgende Wahrheitstabelle zeigt, wie je ein Bit des Plaintext (`p`) mit einem Bit des Key (`k`) zum Ciphertext (`c`) verknüpft werden. {{:gf_informatik:verschluesselung:xorg.jpg?nolink&951|}} Die Entschlüsselung funktioniert gleich wie die Verschlüsselung, weil `(p XOR k) XOR k = p` gilt. ### Aufgabe 2: XOR Anwenden Verschlüssle den folgenden Binärcode: `01101000 01100001 01101100` mit diesem Schlüssel `01010011 01110101 01100111` ++++Lösung:| `00111011 00010100 00001011` ++++ ### Aufgabe 3 – Geheimtext von Hand entschlüsseln Gegeben ist folgender Geheimtext: ''7 42 32 60''. Die ASCII-Codes sind hier als Dezimalzahlen angegeben. Das Schlüsselwort heisst ''WOLF''. - Schreibe die Dezimalzahlen als 7-stellige Binärzahlen nebeneinander auf ein Blatt Papier. Wenn möglich ohne Taschenrechner. - Schreibe unter die vier Binärzahlen die ASCII-Codes für die vier Buchstaben des Schlüsselworts. Dazu benutzt du die [[wpde>American_Standard_Code_for_Information_Interchange#ASCII-Tabelle|ASCII-Tabelle]] oder die Tabelle aus [[##aufgabe_1ascii-tabelle_erzeugen|Aufgabe 1]]. - Führe die XOR-Operation Bit-für-Bit für jedes Binärzahl-Paar durch. So erhältst du die Binärzahlen des Klartexts. - Mit der ASCII-Tabelle kannst du nun die Binärzahlen in Buchstaben wandeln und erhälst den Klartext. ++++Lösung:| Der Klartext Lautet: ''Pelz'' ++++ ### Aufgabe 4: XOR Verschlüsselung mit Python In Python können wir einen String, der eine Binärzahl codiert, mit der `int()` Funktion in eine richtige Zahl verwandeln, indem wir die Basis `2` angeben: print(int('101010', 2)) Die binäre XOR-Operation wird in Python mit dem `^` Operator ausgeführt: one = '11110000' two = '01010101' one_number = int(one, 2) two_number = int(two, 2) xor = one_number ^ two_number print(f"{one} XOR {two} = {xor:08b}") Mit diesen Informationen solltest du ein Programm schreiben können, das den folgenden Text entschlüsselt. * der Schlüssel lautet "ROMANSHORN", wobei immer der ASCII-Code jedes Buchstabens verwendet wird. * die Buchstaben des Schlüssels werden alle 10 Buchstaben wieder von vorne verwendet. * mit `split()` kann ein String in einzelne Wörter geteilt werden: `for word in "eins zwei drei".split():` ``` 00010110 00100110 00101000 01100001 00011101 00100110 00101111 00111010 00100001 01101110 00100001 00100110 00100011 00100101 01101110 00110010 00100100 00100011 00110111 01101111 ``` ++++Lösung:| def decode(binary): """Decodes a sequence of binary number strings into a list of numbers.""" decoded = [] for binary in binary.split(): number = int(binary, 2) decoded.append(number) return decoded def decrypt(codes, key): """Decrypts a sequence of numbers by applying the XOR operation to each number and the next number in the key.""" cleartext = "" key_index = 0 for code in codes: key_code = ord(key[key_index]) # Decrypt: combine one number in the ciphertext and the key using XOR. plaintext = code ^ key_code cleartext += chr(plaintext) # Take the next character in the key, wrapping around to 0 if we reach the key's end. key_index = (key_index + 1) % len(key) return cleartext print(decrypt(decode(ciphertext), "ROMANSHORN")) ++++ ### Aufgabe 5 (optional) Entschlüssle das folgende Bild mit einem *eigenen Code*. Den verwendeten Schlüssel findest du unten. Klicke auf das Bild und lade es dann herunter. {{ :gf_informatik:umgang_inet_sca:bild_raetsel_xor_1373.png?200 |}} ++++Schlüssel| key = "11110000011001101100010000110101110010111001100100010110000111110001100101000101101110111111000000000011000000111110010111101010111110001110101010101000001111001010110110100111000000000011111111010001111100110111101001111010000001011101010000101111110101001100010101001011011101110101011001110100100001101110110011000110100100111100010011001100100111000000000011011110000100010010001110101100111101010100111100010001010100101100111101101011100110110000000000101000000010100111110010000011101000111001100000101011110000000100110011000001000101001000011101000100100100100010100111110011101011010101010110001011010001001010000111000100100010111001111100011100001000011001100011100110101101111001000110001001111010111111100001111111111111011101100101111100000101000101100101011111111110001010111000101010110011011010111111101111110100000100100101001000100101100111100010101011111111001001101000011001101111000111111110101100001100110110000101100000000010111110001011011010010010000111010010011001101010010100000011101111110100101001111110011010000101001111001111000000010101111001000101100110010111101111001000010110111101000110110101000101110001001011100111110010111001011111111010000010011000011101100110111001001000110001110110011011000011001010001111000101100100001010110011000001011100001011010011010001110101010001111000000111111101110011000010010000111010111000111000110" ++++ ++++Tipps| 1. Arbeite nicht mit TigerJython sondern mit 'richtigem' Python (z.B. in Visual Studio Code) 1. Arbeite mit der cv2 Library (`pip install opencv-python`) 1. Jedes Pixel besteht aus drei Bytes (je eines für Rot, Grün, Blau). 1. Wandle diese Bytes in 8-Bit Binärzahlen um (wichtig: mit 0 auffüllen, damit immer 8 Bit) ... 1. ... und hänge sie aneinander. 1. Diesen langen Binärstring kannst du nun entschlüsseln. ++++ ++++Full Block Coder:| Achtung, der Code unten verzichtet absichtlich auf: * `bytes` und `bytearray` ([[https://docs.python.org/3/library/stdtypes.html#binary-sequence-types-bytes-bytearray-memoryview|Python Dokumentation]]) * `string.encode()` und `bytes.decode()` ([[https://docs.python.org/3/library/stdtypes.html#str.encode|Python Dokumentation]]) def textToBytes(text): """Converts a string into a list of ASCII codes.""" numbers = [] for letter in text: number = ord(letter) numbers.append(number) return numbers def bytesToText(numbers): """Converts a number list into text using ASCII decoding.""" text = "" for number in numbers: letter = chr(number) text += letter return text def binaryToBytes(binary): """Converts a sequence of binary strings into a list of numbers.""" numbers = [] for bin in binary: number = int(bin, 2) numbers.append(number) return numbers def bytesToBinary(numbers): """Converts a number list into a space separated binary string.""" text = "" for number in numbers: binary = format(number, "b") text += binary + " " return text def parseWords(binaryText): """Splits a string with space-separated words into a list of words.""" return binaryText.split() def xor(block, key): """Computes XOR for a single block of numbers.""" result = [] for i in range(len(block)): result.append(block[i] ^ key[i]) return result def decryptBlock(block, key): return xor(block, key) def decrypt(ciphertext, passphrase): """Decrypts a sequence of binary text using a passphrase""" ciphernumbers = binaryToBytes(parseWords(ciphertext)) key = textToBytes(passphrase) plaintext = [] # Split ciphertext into blocks of key length, then decrypt each block. for i in range(0, len(ciphernumbers), len(key)): block = ciphernumbers[i:i+len(key)] plaintext += decryptBlock(block, key) return bytesToText(plaintext) def encryptBlock(block, key): return xor(block, key) def encrypt(plaintext, passphrase): """Encrypts plaintext as binary string output using passphrase.""" key = textToBytes(passphrase) plaincodes = textToBytes(plaintext) ciphertext = [] # Split plaintext into blocks of key length, then encrypt each block. for i in range(0, len(plaincodes), len(key)): block = plaincodes[i:i+len(key)] ciphertext += encryptBlock(block, key) return bytesToBinary(ciphertext) key = "ROMANSHORN" ciphertext = """00010110 00100110 00101000 01100001 00011101 00100110 00101111 00111010 00100001 01101110 00100001 00100110 00100011 00100101 01101110 00110010 00100100 00100011 00110111 01101111""" print(decrypt(ciphertext, key)) ++++ ++++ Lösung| import cv2 as cv import numpy as np import math key = "11110000011001101100010000110101110010111001100100010110000111110001100101000101101110111111000000000011000000111110010111101010111110001110101010101000001111001010110110100111000000000011111111010001111100110111101001111010000001011101010000101111110101001100010101001011011101110101011001110100100001101110110011000110100100111100010011001100100111000000000011011110000100010010001110101100111101010100111100010001010100101100111101101011100110110000000000101000000010100111110010000011101000111001100000101011110000000100110011000001000101001000011101000100100100100010100111110011101011010101010110001011010001001010000111000100100010111001111100011100001000011001100011100110101101111001000110001001111010111111100001111111111111011101100101111100000101000101100101011111111110001010111000101010110011011010111111101111110100000100100101001000100101100111100010101011111111001001101000011001101111000111111110101100001100110110000101100000000010111110001011011010010010000111010010011001101010010100000011101111110100101001111110011010000101001111001111000000010101111001000101100110010111101111001000010110111101000110110101000101110001001011100111110010111001011111111010000010011000011101100110111001001000110001110110011011000011001010001111000101100100001010110011000001011100001011010011010001110101010001111000000111111101110011000010010000111010111000111000110" img = cv.imread('encryption/bild_raetsel_xor_1373.png') # Note that the key length (in bits) is not byte-aligned (not a multiple of 8). print(img.size) print(len(key)) # Repeat the key as often as necessary to match the image length. key = key * math.ceil(img.size*8 / len(key)) key_offset = 0 # Process each pixel for x in range(img.shape[0]): for y in range(img.shape[1]): # each pixel is three bytes (24 bits), one each per color b, g, r = img[x, y] # fetch 24 bits of key material key_bits = key[key_offset:key_offset + 24] # encryption is XOR b = int(b) ^ int(key_bits[0:8], 2) g = int(g) ^ int(key_bits[8:16], 2) r = int(r) ^ int(key_bits[16:24], 2) # replace the pixel values img[x,y] = b, g, r key_offset = key_offset + 24 cv.imshow('image',img) cv.waitKey() ++++