Logo

Magic Highstone's World - Mod-Operator

Mod-Operator

Einleitung

Möchtest du dich mit den kryptografischen Algorithmen etwas genauer anfreunden, dann mußt du dieses Kapitel 100%-tig verstanden haben. Aus diesem Grund werde ich ziemlich viele Beispiele bringen, so daß das ganze ein wenig anschaulicher wird.

Außerdem werde ich zwei Definitionen des mod-Operators vorstellen. Die eine wird in vielen Programmiersprachen und auch Taschenrechnern verwendet und die andere in der Zahlentheorie. Die Kryptografie orientiert sich an dem zweit genannten.

Für gewöhnlich ist vielen gar nicht bewußt, daß es verschiedene Definitionen für den mod-Operator gibt und denen wird gar keine Chance gegeben, überhaupt die kryptografischen Algorithmen zu verstehen. Ich hoffe, diesem nun ein Ende setzen zu können.

1. MOD- Operator als Rest der Division

Betrachten wir ersteinmal den div Operator. Der div-Operator steht für die ganzzahlige Division:

 3 div 4 = 0
12 div 4 = 3
13 div 4 = 3
15 div 4 = 3

So weit so gut, schaun wir uns nun noch einmal kurz die ganze Sache mit den negativen Zahlen an:

 -3 div  4 =  0
-12 div  4 = -3
 12 div -4 = -3
-12 div -4 =  3

Der div- Operator berechnet, wie wir jetzt gesehen haben, den ganzzahligen Anteil einer Division. Leider ist ein glattes Ergebnis beim Durchführen einer Division nicht die Regel. Bei der “normalen” Divison ist eine reele Zahl das Ergebnis. Beim div-Operator wird nur der ganzzahlige Anteil berechnet, damit der Rest nicht einfach unter den Tisch fällt, wurde neben den div-Operator der mod-Operator gestellt:

14 div 4 = 3 Rest 2
19 div 4 = 4 Rest 3

Genau diesen Rest berechnet der mod- Operator:

14 mod 4 = 2
19 mod 4 = 3

Im negativen sind das ganze wie folgt aus:

-14 mod  4 = -2
 14 mod -4 =  2
-14 mod -4 = -2

Diese Ergebnise erhält man, wenn der wissenschaftliche Taschenrechner von Bill Gates benutzt wird. Anderswo können diese schon wieder anders aussehen. Benutzt man diesen Operator in einer Programmiersprache, sollten vorher alle Möglichkeiten durchprobiert werden, damit in Spezialfällen nicht irgendwelche Überraschungen lauern. Denn solche Fehler sind hinterher verdammt schwer zu finden, wenn man von einer anderen Definition des Mod-Operators ausgegangen ist. Um ein wenig die aufsteigende Panik zu nehmen, das Problem sind nicht die positiven Zahlen. Problematisch wird es nur, wenn negative Zahlen ins Spiel kommen...

2. MOD-Operator in der Kryptografie

Das folgende wird nicht ganz leicht, aber ich hoffe, dass ich meine wirren Gedanken, ein wenig geordnet zu Papier gebracht habe.

Die Definition des Mod-Operators liegt in dieser Formel begründet:

a mod n = b, wenn eine ganze Zahl k existiert mit a = b + kn
                    mit 0 <= b < n

Veranschaulichen wir uns diese Formel mal mit Hilfe eines Beispiels:

a = 14
b = 2
n = 4
14 mod 4 = 2    mit 14 = 2 + 3 * 4

Solange a nicht negativ ist, decken sich die Ergebnise mit unser obigen Definition. Unterschiedliche Lösungen treten erst auf, wenn a einen negativen Wert besitzt. Hierzu ein Beispiel:

a = -14; n = 4; b = ?
-14 mod 4 = b     mit -14 = b + k * 4    ;k sei -3
                      -14 = b - 12
                      - 2 = b  => b = -2
                  Nicht möglich, da b < 0 !!!

                  mit -14 = b + k * 4    ;k sei -4
                      -14 = b - 16
                        2 = b => b = 2
-14 mod 4 = 2

Ein weiteres Beispiel:

a = -8; n = 17; b = ?
-8 mod 17 = b    mit -8 = b + k * 17    ;k sei -1
                     -8 = b - 17
                      9 = b  => b = 9
-8 mod 17 = 9

Die gleiche Rechnung mit Bill Gates Taschenrechner:

-8 mod 17 = -8

3. Modulare Arithmetik

Für alle die sich schon mit Gruppen und Körpern beschäftigt haben, ersteinmal eine kleine Enttäuschung, denn so weit werde ich hier nicht gehen bzw. es nicht explizit erwähnen. Ich werde mich hier auf folgendes beschränken:

  1. Addition und Subtraktion
  2. Multiplikation
  3. Kommutativ, Assoziativ und Distributiv
  4. Additives Inverses
  5. Multiplikatives Inverses

3.1 Addition und Subtraktion

Diese Operationen verhalten sich genau wie in der uns geläufigen “normalen” Arithmetik:

( 3 + 5 ) mod 5 = 8 mod 5 = 3
( 9 - 1 ) mod 5 = 8 mod 5 = 3

3.2 Multiplikation

Vorweg ersteinmal eine Bemerkung zur Division. Sie ist in der modularen Arithmetik nicht definiert, weil nur mit ganzen Zahlen gearbeitet wird. Die Multiplikation verhält sich allerdings wieder äquivalent zu unserer “normalen” Arithmetik:

( 2 * 4 ) mod 5 = 8 mod 5 = 3

3.3 Kommutativ, Assoziativ und Distributiv

Alle drei Eigenschaften gelten in der modularen Arithmetik, was das Rechnen doch um einiges erleichtern kann, aber gehen wir die Eigenschaften der Reihe nach durch.

Kommutativ

Bedeutet, daß die Operanden vertauscht werden können. Dieses gilt logischerweise nicht für alle Operatoren und auch nicht zwischen verschiedenen Operatoren. Die Kommutativität gilt nur für die Addition und die Multiplikation. Einige Beispiele:

( a + b ) mod c =  ( b + a ) mod c
( 3 + 5 ) mod 5 =  ( 5 + 3 ) mod 5

( a - b ) mod c <> ( b - a ) mod c
( 9 - 1 ) mod 5 <> ( 1 - 9 ) mod 5
  weil  8   mod 5 =    3
  und  -8   mod 5 =    2 ist!!

( a * b ) mod c =  ( b * a ) mod c
( 2 * 4 ) mod 5 =  ( 4 * 2)  mod 5

Assoziativ

Bedeutet, daß die Rechenreihenfolge innerhalb einer Verkettung gleicher Operatoren keinen Einfluß auf das Ergebnis hat. Die Assoziativität gilt nur für die Addition und die Multiplikation!!
Einige Beispiele:

( a + b + c ) mod d = (( a + b ) + c ) mod d = ( a + ( b + c )) mod d
( 3 + 5 + 8 ) mod 5 = (( 3 + 5 ) + 8 ) mod 5 = ( 3 + ( 5 + 8 )) mod 5

( a - b - c ) mod d = (( a - b ) - c ) mod d <>( a - ( b - c )) mod d
( 8 - 5 - 3 ) mod 5 = (( 8 - 5 ) - 3 ) mod 5 <>( 8 - ( 5 - 3 )) mod 5

( a * b * c ) mod d = (( a * b ) * c ) mod d = ( a * ( b * c )) mod d
( 3 * 5 * 8 ) mod 5 = (( 3 * 5 ) * 8 ) mod 5 = ( 3 * ( 5 * 8 )) mod 5

Distributiv

Bedeutet in unserem Fall, daß die Multiplikation von Zahlen distributiv bezüglich der Addition ist. Erklärung ist ziemlich unsinnig, weil sie das zu erklärende Wort enthält, aber nun denn. Etwas besseres ist mir leider nicht eingefallen. Mein folgendes Beispiel sollte aber verdeutlichen, was gemeint ist:

( a * ( b + c )) mod n = ( a * b + a * c ) mod n
( 3 * ( 5 + 8 )) mod n = ( 3 * 5 + 3 * 8 ) mod n

Rechenvereinfachungen

Obendrauf kann man sich mit folgenden Regeln ein wenig das Rechnen erleichtern:

(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a-b) mod n = ((a mod n) - (b mod n)) mod n
(a*b) mod n = ((a mod n) * (b mod n)) mod n
(a*(b+c))mod n = ((a*b) mod n) + ((a*c) mod n) mod n

Umformungen zur linken Seite ersparen einem einige modulare Berechnungen, die mit der Hand häufig nur sehr mühsam durchzuführen sind.

3.4 Additives Inverses

Stellt sich wahrscheinlich ersteinmal die Frage, was ein “Additives Inverses” ist. Nun das Additive Inverse bringt jede natürliche Zahl auf die Null zurück. Das “Additive Inverse” zu einer natürlichen Zahl z ist -z, da z + -z = 0 ist.

Was ist aber nun das additive Inverse zu (4 mod 16) = 4 ?

Wir brauchen also ein Ergebnis von -4, das ist laut unserer Mod-Definition aber leider nicht möglich. Denn wir haben verlangt, daß das Ergebnis in [0..n-1] liegen muß. Wir müssen unsere Definition also noch allgemeiner fassen und die Beschränkung wegfallen lassen, wenn wir ein additives Inverses benötigen. Unter diesen Umständen gilt folgende Regel:

(a mod n) + ((n-a) mod n) = 0

Ein Beispiel hierzu:

(4 mod 16) + ((16 - 4) mod 16) = 0
4      +  (  12    mod 16) = 0

Und nun? 12 mod 16 = 12 und führt nicht zum gewünschten Ergebnis.
Denken wir zurück an unsere Definitionslockerung. Welche Auswirkungen hat das eigentlich?

a mod n = b, wenn eine ganze Zahl k existiert
mit a = b + kn

Das Ergebnis b ist nicht mehr eindeutig, weil k nun variabel sein kann: b(k) = a - kn .

Zurück zu unserem Beispiel:

b(0) = 12 - 0 * 16 =  12
b(1) = 12 - 1 * 16 = -4
b(2) = 12 - 2 * 16 = -20

Haben wir uns doch schön hingedreht oder?