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, und mit `chr()` wieder zurück:
<HTML><script type="module" src="https://bottom.ch/ksr/ed/bottom-editor.js"></script></HTML>
 
<HTML><bottom-editor>letter = 'A'  # Muss ein einzelner Buchstabe sein!
print(ord(letter))</bottom-editor></HTML>

<HTML><bottom-editor>print(chr(65))</bottom-editor></HTML>


Um die Zahl im Binärformat auszugeben, können wir die `format()` Funktion wie folgt verwenden:

<HTML><bottom-editor>print(format(65, "b"))</bottom-editor></HTML>
#### 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:

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

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:

<HTML><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></HTML>
### 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
...
```

<nodisp 1>
++++Lösung:|
<HTML><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></HTML>
++++
</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.


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

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

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

<HTML><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></HTML>

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

<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>
++++ Lösung|
<code python>
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()
</code>
++++
</nodisp>