>Multiplikative Inversion bei IDEA<

[MaOfDe]

Hallo zusammen,
muss einen Vortrag zu IDEA(Verschlüsselungsverfahren) gestalten und nicht nur das: Naturlich muss ich noch ein Programm dazu schreiben, was das ganze erst anschaulich macht. Die Codierung war einfach, die hab ich in Sack und Tütten, doch nun die Entschlüsslung! Ich hab mir mühsam alles ausm Netz gekratzt, was ich finden konnte und hier der Stolperstein:
Man muss durch "additives" und "multiplikatives" Inversieren einige Teilschlüssel(à 16 bit) ändern.

Additive Inversion heißt einfach die Gegenzahl des gegebenen Wertes zu bilden, sprich, wenn x der gegebene 16 bit-Wert ist, ist -x, also das Zweier-Komplement, die additive Inversion.

Multiplikative Inversion dagegen wäre dann(wenn wir bei x bleiben): 1/x=a sprich a*x=1.
Und hier ist mein Problem! Da kommt auf jeden Fall was raus, was kleiner gleich 1 und größer Null rauskommt, aber ich beweg mich ja nur in einem 16 bit-Feld und der Typ Real z.B. hat 64-bit....

Wie soll ich det anstellen??? Hat das schon jemand durchgenommen??? HILFE!!!

[MaOfDe]

Weiß keiner eine Antwort?

Es muss sowas wie beim 2er-Komplement sein...
also zum Beispiel 4d(=0100b):
Einer-Komplement(1-->0; 0-->1): 1011b(=-5d oda 11d)
Zweier-Komplement(+1): 1100b(=-4d oda 12d)

Wenn man 4 und die Gegenzahl addiert, erhält man bekanntlich 0:
4d+(-4d)=0
0100b + 1100b = (1) 0000
Da wir uns nur in 4 Bits bewegt haben, fällt die 5. Stelle weg und wir bekommen 0 als Resultat unserer mühseligen Rechenarbeit ^^.

Vielleicht gibts sowas auch in meinem Fall... aba wie ich befürchte, ist das auch net der rischtije Weech..

[MaOfDe]

OK, hab was gefunden... haut zwar nicht hin mit X * MulInv(X)=1, aber immerhin ein Anfang.

Delphi-Quellcode:

//written by Dave Barton ([e-mail])
function MulInv(x: word): word;
var
  t0, t1, q, y: word;
begin
  if x<= 1 then
  begin
    Result:= x;
    Exit;
  end;
  t1:= DWord($10001) div x;
  y:= DWord($10001) mod x;
  if y= 1 then
  begin
    Result:= (1 - t1) and $FFFF;
    Exit;
  end;
  t0:= 1;
  repeat
    q:= x div y;
    x:= x mod y;
    t0:= t0 + (q*t1);
    if x= 1 then
    begin
      Result:= t0;
      Exit;
    end;
    q:= y div x;
    y:= y mod x;
    t1:= t1 + (q*t0);
  until y= 1;
  Result:= (1-t1) and $FFFF;
end;