Textcodierung [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
## 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. `ord` steht für _ordinal value_, also die Ordnungszahl eines Buchstabens in der ASCII-Textcodierung.
 
<bottom-editor>letter = 'A'  # Muss ein einzelner Buchstabe sein!
print(ord(letter))</bottom-editor>

Mit `chr()` kann ein Zahlencode wieder in den codierten Buchstaben zurückverwandelt werden. `chr` steht für _character_.
<bottom-editor>print(chr(65))</bottom-editor>

#### 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:

<bottom-editor>name = "Papa Moll"
age = 42
print(f"Ich heisse {name} und bin {age*365} Tage alt.")</bottom-editor>

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:

<bottom-editor># 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}")</bottom-editor>
### 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.

Die Ausgabe soll ungefähr so aussehen:

```
A  |      65 | 01000001
B  |      66 | 01000010
C  |      67 | 01000011
D  |      68 | 01000100
...
```

<nodisp 1>
++++Lösung:|
<bottom-editor>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()</bottom-editor>
++++
</nodisp>

## 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`

<nodisp 1>
++++Lösung:|
`00111011 00010100 00001011`
++++
</nodisp>

### 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.

<nodisp 1>
++++Lösung:|
Der Klartext Lautet: ''Pelz''
++++
</nodisp>
### 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:

<bottom-editor>print(int('101010', 2))</bottom-editor>

Die binäre XOR-Operation wird in Python mit dem `^` Operator ausgeführt:

<bottom-editor>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}")</bottom-editor>

Mit diesen Informationen solltest du ein Programm schreiben können, das den folgenden Text entschlüsselt.

Hinweise:
  * Der Schlüssel lautet "ROMANSHORN", wobei immer der ASCII-Code jedes Buchstabens verwendet wird.
    * Wandle den Schlüssel in eine Folge von ASCII-codierten Zahlen um: `[82, 79, 77, ...]`!
  * Mit `split()` kann ein String in einzelne Wörter geteilt werden: `for word in "eins zwei drei".split():`
    * Wandle das Chiffrat in eine Liste von Zahlen um: `[22, 38, 40, ...]`!
  * XOR-kombiniere nun immer eine Zahl aus dem Chiffrat mit einer Zahl aus dem Schlüssel!
    * Die Buchstaben des Schlüssels werden alle 10 Buchstaben wieder von vorne verwendet.
    * Wandle die resultierende Zahl mit `chr()` in Buchstaben um!

```
00010110 00100110 00101000 01100001 00011101 00100110 00101111 00111010
00100001 01101110 00100001 00100110 00100011 00100101 01101110 00110010
00100100 00100011 00110111 01101111
```

<nodisp 1>
++++Lösung:|
<code python decrypt.py>
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"))
</code>
++++
</nodisp>
### 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|
<code python>
key = "11110000011001101100010000110101110010111001100100010110000111110001100101000101101110111111000000000011000000111110010111101010111110001110101010101000001111001010110110100111000000000011111111010001111100110111101001111010000001011101010000101111110101001100010101001011011101110101011001110100100001101110110011000110100100111100010011001100100111000000000011011110000100010010001110101100111101010100111100010001010100101100111101101011100110110000000000101000000010100111110010000011101000111001100000101011110000000100110011000001000101001000011101000100100100100010100111110011101011010101010110001011010001001010000111000100100010111001111100011100001000011001100011100110101101111001000110001001111010111111100001111111111111011101100101111100000101000101100101011111111110001010111000101010110011011010111111101111110100000100100101001000100101100111100010101011111111001001101000011001101111000111111110101100001100110110000101100000000010111110001011011010010010000111010010011001101010010100000011101111110100101001111110011010000101001111001111000000010101111001000101100110010111101111001000010110111101000110110101000101110001001011100111110010111001011111111010000010011000011101100110111001001000110001110110011011000011001010001111000101100100001010110011000001011100001011010011010001110101010001111000000111111101110011000010010000111010111000111000110"
</code>
++++

++++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.

++++

<nodisp 1>
++++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]])

<bottom-editor>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))</bottom-editor>
++++
</nodisp>

<nodisp 1>
++++ Lösung|
<bottom-editor layout="split">
# In normal python: pip install opencv-python numpy
import micropip
await micropip.install(["numpy", "opencv-python"]);

import cv2 as cv
import numpy as np
import math
 
key = "11110000011001101100010000110101110010111001100100010110000111110001100101000101101110111111000000000011000000111110010111101010111110001110101010101000001111001010110110100111000000000011111111010001111100110111101001111010000001011101010000101111110101001100010101001011011101110101011001110100100001101110110011000110100100111100010011001100100111000000000011011110000100010010001110101100111101010100111100010001010100101100111101101011100110110000000000101000000010100111110010000011101000111001100000101011110000000100110011000001000101001000011101000100100100100010100111110011101011010101010110001011010001001010000111000100100010111001111100011100001000011001100011100110101101111001000110001001111010111111100001111111111111011101100101111100000101000101100101011111111110001010111000101010110011011010111111101111110100000100100101001000100101100111100010101011111111001001101000011001101111000111111110101100001100110110000101100000000010111110001011011010010010000111010010011001101010010100000011101111110100101001111110011010000101001111001111000000010101111001000101100110010111101111001000010110111101000110110101000101110001001011100111110010111001011111111010000010011000011101100110111001001000110001110110011011000011001010001111000101100100001010110011000001011100001011010011010001110101010001111000000111111101110011000010010000111010111000111000110"

img_url = 'https://sca.ksr.ch/lib/exe/fetch.php?cache=&media=gf_informatik:umgang_inet_sca:bild_raetsel_xor_1373.png'
# In vanilla python, use urllib.request.urlopen(img_url)
from pyodide.http import pyfetch
response = await pyfetch(img_url)
data = await response.bytes()

arr = np.asarray(bytearray(data), dtype=np.uint8)
img = cv.imdecode(arr, -1) # 'Load it as it is'

# 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()
</bottom-editor>
++++
</nodisp>