XProfan

Deutsch

p.specht

Modulares Potenzieren
==================
Beim RSA-Verschlüsselungsverfahren werden zwei große Primzahlen multipliziert bzw. potenziert, zu einem Modul für weitere Berechnungen. Diese Berechnungen wären wegen der irrsinnigen Größe der enstehenden Zahlen enorm aufwendig. Als Abhilfe gibt es den Algorithmus "Modulares Potenzieren": Man muss dann nicht zuerst das Endergebnis errechnen, sondern kann Zwischenergebnisse schon "unterwegs" MODULO-nehmen, sprich: Mit den enstehenden Divisionsresten weiterrechnen, ohne daß das Endergebnis verändert würde. Das untenstehende Machwerk ist allerdings nicht auf Gültigkeitsgrenzen geprüft, es handelt sich nur um eine Prinzipstudie. Gegengeprüft wurde mittels der Sprache "R".

Eine der Quellen: [...]

Wollte man tatsächlich das RSA-Verfahren nachbilden, müsste selbstverständlich Assemblercode geschrieben werden. Und selbst das könnte zu langsam werden, deshalb wird zur Codierung und Decodierung in moderneren Geräten bereits die Grafikkarte (Parallelcomputing) herangezogen.

Kompilieren Markieren Separieren

WindowTitle "Modulares Potenzieren (Prinzipstudie zB. für das RSA-Verfahren)"
' (CL) CopyLeft 2018-05 P.Specht, Wien; Ohne jede Gewähr!  Quelle: https://www.
' inf-schule.de/kommunikation/kryptologie/rsa/modpotenz/station_schnellespotenzieren
Windowstyle 24:font 2:set("decimals",17)
Declare w$,x!,y!,m!

Repeat

    Cls rgb(200+rnd(56),200+rnd(56),200+rnd(56)):w$=""
    print "\n\n (x ^ y) mod m  soll berechnet werden:"
    Print "\n\n x = ";:input w$:x!=val(w$)
    Print "\n y = ";:input w$:y!=val(w$)
    Print "\n m = ";:input w$:m!=val(w$)
    print "\n ModPotf(x,y,m) = ";
    color 14,1:print " "+format$("%g",ModPotf(x!,y!,m!))+" "
    color 0,15
    waitinput

Until %key=27

End

Proc modpotf :parameters x!,y!,m!

    var pot! = 1

    while y!>0

        if remodf(y!,2)=1

            pot!=remodf(pot!*x!,m!)
            y!=y!-1

        else

            x!=remodf(sqr(x!),m!)
            y!=y!/2

        endif

    endwhile

    return pot!

endproc

'-----------------------------
'Hilfsfunktionen aus geplanter Include (work in progress):

proc floor :parameters x!

    case abs(x!)<(10^-35):return 0
    case x!>0:return intf(x!)
    return (abs(x!-intf(x!)) < 10^-35)-intf(abs(x!-1))

endproc

proc remodf :parameters x!,y!

    ' Q: https://de.wikipedia.org/wiki/Modulo , wie in ADA
    case abs(x!)<(10^-35):return 0
    case abs(y!)<(10^-35):return x!
    return ((x!>0)-(x!<0))*abs(x!-y!*floor(x!/y!))

endproc

proc frac :parameters x!

    var s!=(x!>0)-(x!<0)
    x!=abs(x!)
    x!=x!-round(x!,0)
    case x!<0:x!=1+x!
    return s!*x!

endproc

proc intf :parameters x!

    var s!=(x!>0)-(x!<0)
    x!=abs(x!)
    x!=x!-frac(x!)
    return s!*x!

endproc