Ein wenig Mathe …

Die hohe Kunst der Verschlüsselung kommt ohne ein paar mathematische Grundlagen nicht aus. Dabei ist “Grundlagen” ernst zu nehmen, denn über die Schulmathematik geht es kaum hinaus. In diesem Abschnitt der Reihe zur asymmetrischen Kryptographie versuche ich ein Verständnis für das Rechnen mit modulo, den größten gemeinsamen Teiler und die Vielfachsummendarstellung zu schaffen. Es wird einfach. Versprochen.

Modulo

In der Grundschule lernt jeder vier Grundrechenarten. Die Addition, die Subtraktion, die Multiplikation und letztlich die Division. Dabei lernten wir, mangels gebrochener Zahlen, eine abgespeckte Variante der Division. Wir rechneten: “10/3 = 3 mit einem Rest von 1”. Der selben Restriktion sind wir heute wieder unterworfen. Wir betrachten nur den Bereich der ganzen Zahlen. Allerdings interessiert uns heute nicht das Ergebnis der Division, sondern exakt deren Rest. Wenn wir also 10/3 rechnen, soll unser Ergebnis 1 sein, da 1 der Rest von 10/3 ist. Wir können dafür aber nicht die Division einnehmen, denn die gibt uns als Ergebnis ja “3 mit einem Rest von 1” zurück. Also führen wir eine weitere Grundrechenart ein und nennen sie “modulo”. Dargestellt wird modulo so: 10 mod 3 = 1.

Größter gemeinsamer Teiler

Für jede Zahl gibt es Zahlen, die diese genau teilen. Oder, um es etwas mathematischer auszudrücken, gibt es für eine Zahl a mindestens eine Zahl b, so dass a mod b = 0. Beispiele für unsere Zahl 10 wären 2 und 5, denn 10 mod 2 = 0 und 10 mod 5 = 0. Diese speziellen Zahlen nennt man Teiler. 1 und 10 sind ebenfalls Teiler der Zahl 10. Jede Zahl wird durch 1 geteilt. Zwei verschiedene Zahlen haben also 1 als gemeinsamen Teiler. Eventuell haben sie auch noch andere Zahlen als gemeinsame Teiler. Die größte Zahl, die Teiler zweier verschiedener Zahlen ist, heißt “größter gemeinsamer Teiler” (ggT). Ist der ggT 1, heißen die beiden Zahlen “teilerfremd”.

Euklidischer Algorithmus

Den größten gemeinsamen Teiler zu berechnen, ist nicht immer trivial. Für 12 und 15 ist es einfach. Für 120 und 98 schon etwas schwerer. Aber vielleicht interessiert mich der ggT von 13024 und 324123. Diese Arbeit hat Euklid von Alexandria (360 v.Chr. – 280 v.Chr.) etwas vereinfacht. Er beschrieb ein Verfahren, das auf einfacher Subtraktion beruht. Haben wir zwei unterschiedlich große Zahlen, dann ziehen wir die kleinere von der größeren so lange ab, bis wir entweder 0 erreichen, oder die ehemals größere Zahl nun kleiner ist. Erreichen wir 0, ist die kleinere Zahl der gesuchte größte gemeinsame Teiler. Wenn nicht, dann beginnen wir von vorn, wobei die ehemals kleinere Zahl nun die Größere ist und der verbliebene Rest der größeren Zahl die Kleinere.

Seien a und b zwei natürliche Zahlen, wobei a > b.
Solange a > b rechne:
 a = a - b.
Wenn a = b:
 b ist ggT.
Ansonsten:
 a' = a,
 a = b,
 b = a',
 beginne von vorn.
Ende.

Verwendet man modulo, wird es noch einmal einfacher:

a mod b = r
Wenn r = 0: 
  b der ggT.
Ansonsten: 
  a = b,
  b = r,
  beginne von vorn.
Ende.

Also: ggT(a,b) = ggT(b,r) = … = ggT(x,0) = x

Erweiterter Euklidischer Algorithmus

Obwohl die Berechnung des größten gemeinsamen Teilers mit dem euklidischen Algorithmus einfach wird, ist dessen Anwendung unter Umständen etwas langwierig. Diese Arbeit möchte man sich ungern zweimal machen. Deshalb hat Euklid seinen Algorithmus erweitert, sodass am Ende eine Gleichung steht. Die Gleichung soll von der Form ggT(a,b) = x·a + y·b sein.

Gehen wir gedanklich zurück zur ganzzahligen Division. Wir rechneten a = b·q + r. Bisher interessierten wir uns vor allem für den Rest r. Für den erweiterten euklidischen Algorithmus benötigen wir nun noch die Zahl q.

Ein Beispiel:

Eingabe: 120, 99
Gesucht: ggT(120, 99)

120 = 1·99 + 21
99 = 4·21 + 15
21 = 1·15 + 6
15 = 2·6 + 3
6 = 2·3 + 0

ggT(120, 99) = 3

Gesucht: ggT(120, 99) = x·120 + y·99

3 = -2·6 + 1·15
3 = -2·(1·21 + (-1)·15) + 1·15 = -2·21 + 3·15
3 = -2·21 + 3·(1·99 + (-4)·21) = -14·21 + 3·99
3 = -14·(1·120 + (-1)·99) + 3·99 = -14·120 + 17·99

ggT(120, 99) = -14·120 + 17·99

Es wird also einfach zurück gerechnet, wobei der Rest immer durch die Gleichung der vorhergehenden Zeile ersetzt wird. Die erhaltene Gleichung trägt den Namen “Vielfachsummendarstellung”.

Der erweiterte euklidische Algorithmus in Ruby:

a = 5166
b = 10752

def extended_euclid(x, y)
  return x, 1, 0 if y == 0

  d_prime, s_prime, t_prime = extended_euclid(y, x % y)

  d = d_prime
  s = t_prime
  t = s_prime - ((x/y)*t_prime).floor

  return d, s, t
end

ggT, alpha, beta = extended_euclid a, b

puts "ggT(#{a}, #{b}) = #{ggT} = #{alpha} * #{a} + #{beta} * #{b}"
Modulare Arithmetik

Zuletzt interessieren wir uns noch für eine spezielle Zahl, die sich aus der Vielfachsummendarstellung berechnen lässt. Dazu gehen wir noch einmal an den Anfang dieses Artikels zurück und betrachten die Definition der modulo-Operation. Aus der Gleichung a mod b = c lässt sich erkennen, dass c auf jeden Fall kleiner als b sein wird. Das heißt, dass b die natürlichen Zahlen nach oben beschränkt. Die Zahl b heißt auch der “Modul” der Operation. Innerhalb eines Moduls kann man (fast) beliebig andere mathematische Operationen ausführen (Mathematiker sprechen an dieser Stelle von Gruppen und Körpern, was aber an dieser Stelle zu weit führen würde…).

Das neutrale Element der Addition ist die 0, denn für jede beliebige Zahl x gilt: x + 0 = x = 0 + x. Für die Multiplikation ist das neutrale Element die 1, denn für jede Zahl y gilt: y * 1 = y = 1 * y. Das Inverse einer beliebigen Zahl ist durch das neutrale Element und die Umkehrfunktion definiert. Bezüglich der Addition beispielsweise durch das neutrale Element 0 und die Subtraktion. Das additiv Inverse zu einer Zahl a ist die Zahl -a, denn a – a = 0. Die Zahl -a ist in den natürlichen Zahlen nicht definiert, wohl aber in den ganzen Zahlen. Für multiplikativ Inverse ist das neutrale Element die 1 und die Operation die Division. Eine Zahl a wird also auf 1/a abgebildet, denn a * 1/a = 1. Der Ausdruck 1/a ist weder in den natürlichen, noch in den ganzen Zahlen definiert, sondern erfordert mindestens den Körper der rationalen Zahlen.

Sind die natürlichen Zahlen durch einen Modul beschränkt, sind beide Inverse wohl definiert. Für die Kryptographie ist vor allem das multiplikativ Inverse von besonderem Interesse. Das berechnet sich durch den erweiterten euklidischen Algorithmus und die Vielfachsummendarstellung. Für den Modul m und eine Zahl n sowie den ggT(n, m) = x·n + y·m ist das Inverse i von n bezüglich der Multiplikation definiert durch i = x mod m.

Ein letztes Beispiel:

ggT(6, 13) = 1 = -2·6 + 1·13

i = -2 mod 13 = 11

ggT(11, 13) = 1 = 6*11 - 5*13

j = 6 mod 13 = 6

Das ist alles, was man als Grundlage für die asymmetrische Kryptographie benötigt. War doch gar nicht so schwer, oder?

__

Dieser Artikel gehört zu einer Reihe über asymmetrische Kryptographie:

  1. Asymmetrische Kryptographie
  2. Ein wenig Mathe…
  3. Romeo, Juliet, Diffie & Hellman

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s