Entwickler-Ecke :: Thema anzeigen - Restklassen zu RSA, Verschlüsselung

Moony - Mi 14.03.07 12:24
Titel: Restklassen zu RSA, Verschlüsselung

Morgen,
also ich habe folgendes Problem. Für die Schule muss ich RSA programmieren. Das klappt soweit auch. Mein Problem ist jetzt, dass der Rechner bei hohen Zahlen streikt.
Beispiel 89^77 mod 221.
Bei dieser Rechnung soll ich mit Restklassen arbeiten. Was eine Restklasse ungefähr ist, habe ich mir schon angeschaut und auch einigermaßen verstanden. Aber wie zerteile ich 89^77 so, dass der Rechner es rechnen kann. Schon einmal vielen Dank, falls jemand antwortet.
Moony

Horst_H - Mi 14.03.07 19:42

Hallo,

89^77 mod 221 = (89 mod 221 * 89) mod 221)* 89) mod 221)* 89) mod 221)...

Zum Potenzieren von Zahlen mit ganzzahligem Exponenten gibt es natuerlich Abkuerzungen ...
http://www.webplain.de/foren/read.php?1,885,898#msg-898

Ich gehe davon aus, dass 0<Bas < Modulus < 2^16 ist.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

function BasPotMod (Bas,Pot,Modulus :integer):integer;
var
  Quadrat : integer;
begin
  Quadrat := Bas ;
  Result := 1;
  While Pot <> 0 do
    begin
    if Odd(Pot) then
    {Falls Exponent ungerade dann}
      Result= (Result * Quadrat) MOD Modulus;
    Quadrat = (Quadrat * Quadrat) MOD Modulus;
    shr(Pot,1);  {Exponent = Exponent div 2}
    end; {while}
end;

Man kann aber Quadrat auch durch Bas ersetzen und braucht überhaupt keine Variable mehr in der Funktion deklarieren und kann das schon inlinen(auf deutsch ?).

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

function BasPotMod (Bas,Pot,Modulus :Cardinal{Dword}):integer;
begin
Result := 1;
While Pot <> 0 do
  begin
  if Odd(Pot) then
    Result:= (Result * Bas) MOD Modulus;
  Bas :=  (Bas * Bas) MOD Modulus;
  Pot := Pot shr 1;  {Exponent = Exponent div 2}
  end; {while}
end;

Gruß Horst

P.S. Der Rechner von Windows im Zubehör rechnet sogar 89^77 Mod 221 mit dem Ergebnis 72.
P.S.S. Hoffe es hilft noch..

IngoD7 - Mi 14.03.07 19:56

Klingt irgendwie etwas komplizierter als es ist. ;)

Aufgrund gültiger Restklassenarithmetik sind folgende Ausdrücke identisch. Dabei nehme ich zur besseren Veranschaulichung als Exponent 4 anstatt 77:

(89^4) mod 221
= 62742241 mod 221
= 120

( ((89 * 89) mod 221) * ((89 * 89) mod 221) ) mod 221
= ( (7921 mod 221) * (7921 mod 221) ) mod 221
= (186 * 186) mod 221
= 34596 mod 221
= 120

( ((89^2) mod 221) * 89 * 89 ) mod 221
= ( (7921 mod 221) * 89 * 89 ) mod 221
= (186 * 89 * 89) mod 221
= 1473306 mod 221
= 120

Genug der Beispiele. Es sollte deutlich werden, dass zu jedem Zeitpunkt der Multiplikationen (also zwischendurch) ein Zwischenergebnis modulo 221 genommen werden kann, um die Zwischenergebnisse klein zu halten.

Auf die Eingangsfrage bezogen bedeutet das, dass man die 89 nicht erst 77 mal mit sich selbst multiplizieren und erst dann modulo 221 nehmen muss, sondern man kann jederzeit schon die Zwischenergebnisse modulo 221 nehmen. Dadurch hält man die Zahl klein und für den Computer "handlich".

Das kann man auf die Spitze treiben, indem man das nach jedem Multiplikationsschritt macht:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

function MonsterMod(aBas, aExp, aMod : integer) : integer;
var 
   i : integer;
   E : integer;
begin
   E:=aBas;
   for i := 2 to aExp do
      E:=(E*aBas) mod aMod;
   Result:=E;
end;

//Aufruf mit
MySolution := MonsterMod(89,77,221);

//Nachtrag:
Wie witzig ... erst schreibt keiner, dann Alle. :)
Man sollte, während man ein Posting verfasst, nicht zwischendurch ans Telefon gehen. ;)

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!