MixColumn - Polynom-Multiplikation - wie?

[geofranz01]

Hallo,
ich bin gerade dabei mir meine eigene kleine AES-Verschlüsselung zu bauen. Ich komme auch schon ganz gut vorran, allerdings stellt sich mir das Problem, dass ich MixColumn nicht ganz(oder garnicht) verstehe. Irgendwie werden da Polynom-Mulitplikation in GF(256) durchgeführt.

Ich habe jetzt also z.B. $D4 das ich mit 2 mulitplizieren muss. Rauskommen soll $B3.

Weitere Beispiele:
$BF * 3 -> $DA
$5D * 1 -> $5D
$30 * 1 -> $30

Mein Ansatz wäre etwa so: e = $D4 * 2 mod 255. Aber das liefert (natürlich) falsche Ergebnisse.

Wie mache ich das jetzt richtig ?

P.S. Aus Google und Wikipedia werd ich auch nicht schlau.

Grüße
geofranz

[gammatester]

Zitat von geofranz01:

Hallo,
ich bin gerade dabei mir meine eigene kleine AES-Verschlüsselung zu bauen. Ich komme auch schon ganz gut vorran, allerdings stellt sich mir das Problem, dass ich MixColumn nicht ganz(oder garnicht) verstehe. Irgendwie werden da Polynom-Mulitplikation in GF(256) durchgeführt.

Ich habe jetzt also z.B. $D4 das ich mit 2 mulitplizieren muss. Rauskommen soll $B3.

Weitere Beispiele:
$BF * 3 -> $DA
$5D * 1 -> $5D
$30 * 1 -> $30

Mein Ansatz wäre etwa so: e = $D4 * 2 mod 255. Aber das liefert (natürlich) falsche Ergebnisse. :cry:

Wie mache ich das jetzt richtig ?

P.S. Aus Google und Wikipedia werd ich auch nicht schlau.

Grüße
geofranz

Multiplikation in GF(2^8) ist eine Polynom-Multiplikation modulo einem geigneten Polynom (bei AES in Byteschreibweise $1B). Hier ein vollständiges Testprogramm mit Deinen nichtrivialen Beispielen:

Delphi-Quellcode:

program t_gf28;

{$apptype console}

uses sysutils;

{---------------------------------------------------------------------------}
function gf_mul(a,b: byte): byte;
  {-Return a*b in GF(2^8)}
const
  poly=$1b;
var
  t: byte;
begin
  if b=0 then gf_mul := 0
  else begin
    t := 0;
    while b<>0 do begin
      if odd(b) then t := t xor a;
      b := b shr 1;
      if a and $80 = 0 then a := a shl 1
      else a := (a shl 1) xor poly;
    end;
    gf_mul := t;
  end;
end;

begin
  writeln('GF(2^8):  $D4 * $02  = $',IntToHex(gf_mul($D4,$02),2));
  writeln('GF(2^8):  $BF * $03  = $',IntToHex(gf_mul($BF,$03),2));
end.

Um allerdings halbwegs auf Geschwindigleit zu kommen, benutzt man sinnvollerweise Power- und Logarithmentabellen. Ein Beispiel findest Du im Programm t_mkctab.pas in meinem AES-Archiv.

http://home.netsurf.de/wolfgang.ehrh...2008-01-12.zip
Gruß Gammatester

[geofranz01]

Hey Danke! Das funktioniert ja super! Vielen Dank für den Code.

PS: Meine nichttrivialen Beispiele stammen von der schrittweisen Doku über die Funktionsweise von AES