Matroids Matheplanet Forum Index
Moderiert von Florian
Informatik » Kryptologie » RSA-Algorithmus in Excel - Binäre Exponentiation
Autor
Universität/Hochschule J RSA-Algorithmus in Excel - Binäre Exponentiation
Lucas85
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 29.07.2021
Mitteilungen: 4
  Themenstart: 2021-07-29

Hallo zusammen, bin neu hier und muss bei einer Aufgabe in Excel RSA programmieren. (e,n) = (5,221) (d, n) = (77, 221) Verschlüsselungsformel: 𝐶=𝑀^e mod 𝑛 Entschlusselungsfomrel: M=C^d mod n mit den ASCI- Werten von 64 bis 90 für die Zeichen @, A, ... Z; Noch ein Hinweis zur Entschlüsselungsformel: Die Potenzierung mit dem privaten Schlüssel erzeugt sehr große Zahlen 𝐶^d,die nicht direkt berechnet werden können. Teilen Sie die Potenz statt dessen mit Hilfe der binären Modulo-Exponentiation in mehrere Teilpotenzen auf und berechnen Sie dazwischen jeweils den Modulo. Habe das mit der Binären Exponentiation nicht ganz verstanden, weil ich nicht weiß, wie das mit den Zwischenergebnisse der Modulo funktioniert. Bitte um Hilfestellung. Danke & LG Lucas


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2964
  Beitrag No.1, eingetragen 2021-07-29

Für nahezu alle Modulorechnungen gilt, dass man bereits in jedem Zwischenschritt modulo rechnen kann. Beispiel: Ich möchte $10^5 \mod 221$ rechnen. $10^5 = 10 \cdot 10^4 = 10 \cdot (10^2)^2$ $10^2 \mod 221 \equiv 100$ $100^2 \mod 221 \equiv 10000\mod 221 \equiv 55$ $10 \cdot 55 \mod 221 \equiv 550 \mod 221\equiv 108$ Das geht auf diese Art auch mit deutlich größeren Potenzen sogar hilfmittelfrei.


   Profil
Lucas85
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 29.07.2021
Mitteilungen: 4
  Beitrag No.2, vom Themenstarter, eingetragen 2021-07-30

Danke für deine schnelle Antwort, jedoch ist es nicht genau das, was ich brauche. Angenommen: Ich möchte jetzt das Zeichen "A" verschlüsseln und ich muss die binäre Exponentiation anwenden. A in ASCII entspricht 65 in Dezimal in Binär wäre das dann 01000001. Jetzt besagt mir der Algorithmus der binären Exponentiation: Umwandlung des Exponenten k in die zugehörige Binärdarstellung. Ersetzen jeder 0 durch Q und jeder 1 durch QM. Nun wird Q als Anweisung zum Quadrieren und M als Anweisung zum Multiplizieren aufgefasst. Somit bildet die resultierende Zeichenkette von links nach rechts gelesen eine Vorschrift zur Berechnung von x^k. Man beginne mit 1, quadriere für jedes gelesene Q das bisherige Zwischenergebnis und multipliziere es für jedes gelesene M mit x. Da die Binärdarstellung von k > 0 immer mit der Ziffer 1 beginnt – und so ebenfalls die Anweisung mit QM beginnt –, ergibt sich für die erste Anweisung QM in jedem Fall das Zwischenergebnis 1^2 ⋅ x = x. Aus diesem Grund ergibt sich eine leicht vereinfachte Variante, bei der die erste Anweisung QM durch x ersetzt wird (Wikipedia, 2020). Verschlüsselungsformel: 𝐶=𝑀^e mod 𝑛 (Wobei dieses M steht hier für das Zeichen A) Also C= 65^5 mod 221 5 in Binär=00000101 Binäre Exponentiation= Q, Q, Q, Q, Q, QM, Q, QM. 65^2 ^2 ^2 ^2 ^2 ^2 *65 ^2 ^2 *65 mod 221 ????. Hierbei würde ich für die Zwischenergebnisse die Modulo benötigen und komme hier nicht weiter. Danke & beste Grüße, Lucas


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2964
  Beitrag No.3, eingetragen 2021-07-30

Da deine Binärdarstellung der 5 nicht mit einer 1 beginnt, widersprichst du dir leider selbst. Es gilt: \[5 = 101_2\] Die Operationen sind also QM,Q,QM.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7077
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2021-07-30

Hallo Lucas85, \quoteon(2021-07-30 16:34 - Lucas85 in Beitrag No. 2) Man beginne mit 1 ... 65^2 ^2 ^2 ^2 ^2 ^2 *65 ^2 ^2 *65 mod 221 ????. \quoteoff Also wäre es 1^2 ^2 ^2 ^2 ^2 ^2 *65 ^2 ^2 *65 mod 221


   Profil
Lucas85
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 29.07.2021
Mitteilungen: 4
  Beitrag No.5, vom Themenstarter, eingetragen 2021-07-31

Die richtige Berechnung der binären Exponentiation ist somit: =1^2*65^2^2*65 = 1160290625 <=> 65^5 Wie gehts jetzt weiter mit Modulo 221 der Zwischenergebnisse? (Das ist wichtig, ansonsten wird bei größeren Potenzen und Berechnungen in Excel der Speicher gesprengt). Danke schonmal. [Die Antwort wurde nach Beitrag No.3 begonnen.]


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2964
  Beitrag No.6, eingetragen 2021-07-31

Das ist so nur zufällig richtig. Richtig wäre: ((1^2*65)^2)^2*65 (Da Potenzen rechtsassoziativ sind, ist die Klammersetzung im Allgemeinen nicht optional) Man rechnet in jedem Schritt modulo. 1^2*65 = 65 mod 221 65^2 = 4225 = 26 mod 221 26^2 = 676 = 13 mod 221 13*65 = 845 = 182 mod 221


   Profil
Lucas85
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 29.07.2021
Mitteilungen: 4
  Beitrag No.7, vom Themenstarter, eingetragen 2021-07-31

Vielen Dank, ihr seit echt super. 👍 Jetzt kann ich das endlich lösen.


   Profil
Lucas85 hat die Antworten auf ihre/seine Frage gesehen.
Lucas85 hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]