Restklassen zu RSA, Verschlüsselung

Moony · Beiträge: 97 Win XP D7 Prof

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

_________________
Leben ist ein informationsgesteuerter, hochkomplexer Ordnungszustand der Materie mit der Fähigkeit zur Selbstorganisation und Selbstreproduktion!

ub60 · Beiträge: 764 Erhaltene Danke: 127

Hier nur mal eine kleine Hilfe:

für 89^77 mod 221:

1. nimm Produkt=1
2. rechne Produkt=Produkt*89
3. wenn Produkt>=221, nimm Produkt=Produkt mod 221 (also nur mit dem Rest weiterrechnen)
4. und das Ganze 77 mal (natürlich ab Zeile 2)

ub60

Horst_H · Verfasst: 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 ...
www.webplain.de/fore...hp?1,885,898#msg-898

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

markieren

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 ?).

markieren

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 · Beiträge: 629 D7

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:

markieren

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.

Moony · Beiträge: 97 Win XP D7 Prof

HVALA. :flehan: VIELEN LIEBEN DANK *Sternchenaugen*. ES LEBT!!! :dance2: Wie putzig es das mit den Restklassen kann :P
*jedem nen Stück Kuchen durch die Leitung schieb*

_________________
Leben ist ein informationsgesteuerter, hochkomplexer Ordnungszustand der Materie mit der Fähigkeit zur Selbstorganisation und Selbstreproduktion!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme