RSA Verschlüsselung - Modulo Berechnung
Zurück zum Hauptartikel über RSA
Methode des fortgesetzten Quadrierens
Beim Potentzieren entstehen beim RSA Algorithmus gigantische große Zahlen. Bereits die in den verkürzten Beispielen verwendeten Größen zeigen das auf, so ist 1697157 eine Zahl mit über 500 Ziffern; bei den im praktischen Einsatz befindlichen Schlüssellängen und Blockgrößen entstehen Werte, die ausgeschrieben mehrere Seiten füllen. Um das Problem der zu großen Zahlen in den Griff zu bekommen, verwenden Programmierer das Verfahren des fortgesetzten Quadrierens.
Dieses Verfahren macht zum Einen davon Gebrauch, dass mehrfaches Quadrieren sehr schnell sehr hohe Potenzen erzeugt, so ist zum Beispiel
1767 = ((((((172)2)2)2)2)2) * 17 * 17 * 17
Zum Anderen möchte man ja gar nicht den Wert 1767 wissen, sondern nur den modularen Rest 1767 ( mod n ). Dabei ändert sich der Rest nicht, wenn bei jedem Schritt des Quadrierens modulo gerechnet wird:
1767 ( mod n )= ((((((172 ( mod n ))2 ( mod n ))2 ( mod n ))2 ( mod n ))2 ( mod n ))2 ( mod n )) * 17 * 17 * 17 ( mod n )
Auf diese Weise muss man nur mit Zwischenwerten arbeiten, die in etwa so groß sind wie n.
Zurück zum Hauptartikel über RSA
