Advanced Encryption Standard AES - Rijndael - Assembler optimiert
Zum Code
In diesem Projekt habe ich meine eigene Implementierung von AES (Rijndael) verwirklicht. AES ist der Nachfolger vom alten Verschlüsselungsstandard DES (bzw. später Triple-DES). Wer mehr über AES erfahren möchte, kann sich bei Wikipedia informieren: http://de.wikipedia.org/wiki/AES

Die korrekte Ausführung des Algorithmus wird mittels einem einfachem Testmodul überprüft. Dennoch kann ich keine Fehlerlosigkeit garantieren, korrigiere aber gerne jeden Fehler den jemand findet. Für eine weitergehende sicherheitsrelevante Anwendung ist die Implementierung nicht ausreichend abgeschirmt, da weder Variablen gelöscht werden noch sonstige Daten abgeschirmt sind. Zusätzlich zum Testmodul existiert ein Speedtest-Modul, mit welchem die Ausführungszeit für einen Durchlauf gemessen werden kann. Hieraus wird zudem der theoretische Datendurchsatz errechnet.

Die Referenzimplementierung ist in reinem VB abgehandelt und kommentiert. Die Kommentare setzen allerdings Kenntnis von der Materie voraus. Theoretisch dürfte der Referenzcode mit allen vorgesehenen Bitlängen (128/196/256 Bit sowohl für Blöcke als auch Schlüssel) zurecht kommen. Zwecks verbesserter Performanz habe ich die Verschlüsselungsroutine ebenfalls in Assembler zur Verfügung gestellt. Diese Variante ist jedoch auf 128 Bit für die Blöcke und die Schlüssel begrenzt. Der beiliegende Assemblercode ist für MASM vorgesehen. Auf meinem Athlon XP2200+ erreicht die optimierte Variante einen theoretischen Datendurchsatz von ~72 Mb/s.

History
24.09.2004 Hinzugefügt
16.10.2004 Entschlüsselung nun auch in Assembler vorhanden

Autor: Dominik Auras <Dominik_auf_vbInside.de> 

Code aus Rijndael.bas
Option Explicit
'g(x) = a_7*x^7 + a_6*x^6 + a_5*x^5 + a_4*x^4 + a_3*x^3 + a_2*x^2 _
    + a_1*x^1 + a_0
'a_0..7 Element von {0, 1}, endlicher Körper F_2_8

'Jeder Koeffizient wird durch ein Bit repräsentiert, ein Byte
'stellt ein Polynom dar.

'Für die Addition gilt:
'g_a(x) + g_b(x) = (a_7+b_7 mod 2)*x^7 + (a_6+b_6 mod 2)*x^6 ... _
    (a_0+b_0 mod 2)
'Wird ein Polynom durch ein Byte dargestellt, entspricht dies einer
'XOR-Operation

'Generatorpolynom: n(x) = x+1 (Wert '03')
'Für a = 0 .. 255 erzeugt (x+1)^a alle möglichen Polynome 7. Grades
'modulo m(x) = x^8+x^4+x^3+x+1 (irreduzibel, Wert '011B'), für
'a > 255 wiederholen sich die Werte

'Multiplikation, a(x) * b(x)
'a(x), b(x) können durch das Generatorpolynom ausgedrückt werden
'a(x) = n(x)^m, b(x) = n(x)^l
'a(x) * b(x) = n(x)^m * n(x)^l = n(x)^(m+l mod 255)

Private Potenz(254) As Long, Logarithmus(255) As Long
Private Substitution(255) As Long, InvSubstitution(255) As Long
Private Shifts(2, 2, 1) As Long
Private key() As Long, rc(10) As Byte
Private Lr As Long, Lb As Long, Lk As Long
Public Sub Init_Rijndael()
  Dim i As Long, n As Long, tmp(3) As Long
    
    'Initialisierung der Lookup-Tabellen für die Potenzen
    'des Generatorpolynoms und ihrer Logarithmen
    Logarithmus(0) = -1
    'a(x)=0 kann nicht durch g(x) erzeugt werden
    
    Potenz(0) = 1
    Logarithmus(1) = 0
    
    For i = 1 To 254
      'g_i(x) = g_i-1(x) * x + g_i-1 * 1 = g_i-1 * (x+1)
      Potenz(i) = shl(Potenz(i - 1), 1) Xor Potenz(i - 1)
      
      If Potenz(i) > 255 Then
        'Reduktion erforderlich, m(x) = x^8+x^4+x^3+x+1 (Wert '011B')
        Potenz(i) = Potenz(i) Xor &H11B&
      End If
      
      Logarithmus(Potenz(i)) = i
    Next i
    
    'Berechnung der Substitutionsbox und ihrer Inversen
    For i = 0 To 255
      Substitution(i) = fwd_affine(Inv(i))
      InvSubstitution(i) = Inv(inv_affine(i))
    Next i
    
    'Initialisierung der Lookup-Tabelle für die Funktion ShiftRows
    SetLongArray_Row Shifts, 0, 0, 1, 2, 3
    '128 Bit Blockgröße
    SetLongArray_Row Shifts, 1, 0, 1, 2, 3
    '196 Bit Blockgröße
    SetLongArray_Row Shifts, 2, 0, 1, 3, 4
    '256 Bit Blockgröße
    
    SetLongArray_Row Shifts, 0, 1, 3, 2, 1
    '128 Bit Blockgröße
    SetLongArray_Row Shifts, 1, 1, 5, 4, 3
    '196 Bit Blockgröße
    SetLongArray_Row Shifts, 2, 1, 7, 5, 4
    '256 Bit Blockgröße
    
    'Berechnung der Tabelle rc(j), rc(j) = rc(j-1)*x, rc(1) = 1
    'Wird für die Erweiterung des Anwenderschlüssels benötigt
    rc(0) = 1
    For i = 1 To UBound(rc)
      rc(i) = mul(rc(i - 1), 2)
    Next i
    
    For i = 0 To 255
      If InvSubstitution(Substitution(i)) <> i Then
        Stop
      End If
    Next i
End Sub
Private Function mul(a As Byte, b As Byte) As Long
'a(x) * b(x) = g(x)^(a+b mod 255)
    If a <> 0 And b <> 0 Then
      mul = Potenz((Logarithmus(a) + Logarithmus(b)) Mod 255)
    Else
      mul = 0
    End If
End Function
Private Function Inv(a As Long) As Long
  Dim i As Long
    
    'Berechnung des multiplikativen Inversen von a
    'im endlichen Feld F_2_8 mod [m(x) = x^8+x^4+x^3+x+1].
    'Es gilt Inv(a) * a = 1, neutrales Element ist 1
    
    If a < 2 Then
      Inv = a: Exit Function
    End If
    
    Inv = Potenz(255 - Logarithmus(a))
End Function
Private Function fwd_affine(a As Long) As Long
  Dim tmp As Long
    
    'Berechnung einer vorgegebenen affinen Abbildung über F_2
    '|y0| = |1 0 0 0 1 1 1 1||x0| + |1|
    '|y1| = |1 1 0 0 0 1 1 1||x1| + |1|
    '|y2| = |1 1 1 0 0 0 1 1||x2| + |0|
    '|y3| = |1 1 1 1 0 0 0 1||x3| + |0|
    '|y4| = |1 1 1 1 1 0 0 0||x4| + |0|
    '|y5| = |0 1 1 1 1 1 0 0||x5| + |1|
    '|y6| = |0 0 1 1 1 1 1 0||x6| + |1|
    '|y7| = |0 0 0 1 1 1 1 1||x7| + |0|
    
    'Addition: a (+) b = a + b mod 2 = a xor b
    
    'y0 = x0+x4+x5+x6+x7+1
    'y1 = x0+x1+x5+x6+x7+1
    'y2 = x0+x1+x2+x6+x7
    'y3 = x0+x1+x2+x3+x7
    'y4 = x0+x1+x2+x3+x4
    'y5 = x1+x2+x3+x4+x5+1
    'y6 = x2+x3+x4+x5+x6+1
    'y7 = x3+x4+x5+x6+x7
    
    tmp = a Xor shl(a, 1) Xor shl(a, 2) Xor shl(a, 3) Xor shl(a, 4)
    tmp = tmp Xor shr(tmp, 8) Xor &H63&
    '11000110 = &H63
    
    fwd_affine = tmp And &HFF&
End Function
Private Function inv_affine(a As Long) As Long
  Dim tmp As Long
    
    'Berechnung einer vorgegebenen affinen Abbildung über F_2, diesmal
    'mit der inversen Matrix zu fwd_affine
    '|x0| = |0 0 1 0 0 1 0 1||y0| + |1|
    '|x1| = |1 0 0 1 0 0 1 0||y1| + |0|
    '|x2| = |0 1 0 0 1 0 0 1||y2| + |1|
    '|x3| = |1 0 1 0 0 1 0 0||y3| + |0|
    '|x4| = |0 1 0 1 0 0 1 0||y4| + |0|
    '|x5| = |0 0 1 0 1 0 0 1||y5| + |0|
    '|x6| = |1 0 0 1 0 1 0 0||y6| + |0|
    '|x7| = |0 1 0 0 1 0 1 0||y7| + |0|
    
    'Bsp: x0 = y2+y5+y7+1 = (x0+x1+x2+x6+x7)+
    '          (x1+x2+x3+x4+x5+1)+(x3+x4+x5+x6+x7)
    '        = x0+x1+x1+x2+x2+x3+x3+x4+x4+x5+x5+x6+x6+x7+x7+1+1 = x0
    '  da xn xor xn = 0
    
    tmp = shl(a, 1) Xor shl(a, 3) Xor shl(a, 6)
    tmp = tmp Xor shr(tmp, 8) Xor &H5&
    '10100000 = &H05
    
    inv_affine = tmp And &HFF&
End Function
Public Sub KeyExpansion(cipher() As Byte, blockbits As Long)
  Dim i As Long, xi_1(3) As Long
    
    'Es wird nicht überprüft, ob die Bitlängen des Schlüssels
    'und der Blöcke korrekt sind (128, 196 und 256 Bit gültig)
    
    'Diese Funktion bestimmt die Anzahl der Runden und erweitert
    'den Anwenderschlüssel dementsprechend, der erweiterte Schlüssel
    'wird in key() gespeichert
    
    Lk = (UBound(cipher) + 1) / 4
    Lb = blockbits / 32
    
    Select Case Min(Lk, Lb)
      Case 4: Lr = 10
      Case 6: Lr = 12
      Case 8: Lr = 14
    End Select
    
    ReDim key(Lb * (Lr + 1) - 1, 3)
    
    'Die ersten Lk Wörter des Schlüssels werden durch den Anwender-
    'schlüssel definiert
    For i = 0 To Lk - 1
      key(i, 0) = cipher(i * 4)
      key(i, 1) = cipher(i * 4 + 1)
      key(i, 2) = cipher(i * 4 + 2)
      key(i, 3) = cipher(i * 4 + 3)
    Next i
    
    'Die übrigen Wörter des Schlüssel werden aus den vorhandenen _
        errechnet
    'key(i) = key(i-1) xor key(i-Lk), für i mod lk = 0 wird statt _
        key(i-1)
    'der Wert F(key(i-1)) genommen, für 256 Bit Schlüssellänge _
        wird zudem
    'bei i mod lk = 4 key(i-1) mit S(key(i-1)) ersetzt
    For i = Lk To Lb * (Lr + 1) - 1
      If i Mod Lk = 0 Then
        'Alle Lk Wörter wird
        'key(i-1) wird um ein Byte nach links rotiert, dann
        'wird eine Substitution durchgeführt und zum ersten Byte
        'addiert man eine vorberechnete Konstante
        xi_1(0) = Substitution(key(i - 1, 1)) Xor rc(Int(i / Lk))
        xi_1(1) = Substitution(key(i - 1, 2))
        xi_1(2) = Substitution(key(i - 1, 3))
        xi_1(3) = Substitution(key(i - 1, 0))
      ElseIf i Mod Lk = 4 And Lk = 8 Then
        'Bei einer Schlüssellänge von 256 Bit wird alle 4 Wörter
        'Substitution durchgeführt
        xi_1(0) = Substitution(key(i - 1, 0))
        xi_1(1) = Substitution(key(i - 1, 1))
        xi_1(2) = Substitution(key(i - 1, 2))
        xi_1(3) = Substitution(key(i - 1, 3))
      Else
        xi_1(0) = key(i - 1, 0)
        xi_1(1) = key(i - 1, 1)
        xi_1(2) = key(i - 1, 2)
        xi_1(3) = key(i - 1, 3)
      End If
      
      key(i, 0) = xi_1(0) Xor key(i - Lk, 0)
      key(i, 1) = xi_1(1) Xor key(i - Lk, 1)
      key(i, 2) = xi_1(2) Xor key(i - Lk, 2)
      key(i, 3) = xi_1(3) Xor key(i - Lk, 3)
    Next i
End Sub
Public Sub Rijndael_EncryptBlock(block() As Byte)
  Dim i As Long
    
    'Die Addition des Schlüssels als erste und letzte Operation
    'garantiert, dass jedes Bit der Chiffre vom Schlüssel abhängig ist
    AddRoundKey block, 0
    
    For i = 1 To Lr - 1
      'Lr - 1 reguläre Runden
      SubBytes block
      ShiftRows block, 0
      MixColumns block
      AddRoundKey block, Lb * i
    Next i
    
    'Eine finale Runde ohne MixColumns
    SubBytes block
    ShiftRows block, 0
    AddRoundKey block, Lb * Lr
End Sub
Public Sub Rijndael_DecryptBlock(block() As Byte)
  Dim i As Long
    
    'Bei der Entschlüsselung werden alle Schritte der Verschlüsselung
    'rückwärts durchlaufen und falls nötig invertiert
    
    'Zuerst die invertierte finale Runde
    AddRoundKey block, Lb * Lr
    ShiftRows block, 1
    InvSubBytes block
    
    For i = Lr - 1 To 1 Step -1
      'Lr-1 reguläre invertierte Runden
      AddRoundKey block, Lb * i
      InvMixColumns block
      ShiftRows block, 1
      InvSubBytes block
    Next i
    
    'Und zuletzt die Entfernung des letzten Teils des Anwenderschlüssels
    AddRoundKey block, 0
End Sub
Private Sub SubBytes(block() As Byte)
  Dim i As Long, j As Long
    
    'Alle Bytes werden non-linear ersetzt
    
    For i = 0 To 3
      For j = 0 To UBound(block, 1)
        block(j, i) = Substitution(block(j, i))
      Next j
    Next i
End Sub
Private Sub ShiftRows(ByRef block() As Byte, Mode As Long)
  Dim j As Long, i As Long, tmp() As Long, ByteMode As Long
    
    'Vertauscht die Elemente in den Zeilen, die erste Zeile
    'bleibt unberührt, die anderen drei Zeilen werden durch
    'die Werte in Shifts() verschoben. Mode 0 steht für
    'Verschlüsselung, Mode 1 steht für Entschlüsselung
    
    ByteMode = shr(Lb - 4, 1)
    ReDim tmp(UBound(block, 1))
    
    For j = 1 To 3
      For i = 0 To UBound(block, 1)
        tmp(i) = block((i + Shifts(j - 1, ByteMode, Mode)) Mod Lb, j)
      Next i
      For i = 0 To UBound(block, 1)
        block(i, j) = tmp(i)
      Next i
    Next j
End Sub
Private Sub MixColumns(block() As Byte)
  Dim i As Long, j As Long, tmp(3) As Long
    
    'Jede Spalte des Blocks wird als Polynom mit Koeffizienten
    'aus F_2^8 aufgefasst und mit dem festen Polynom
    'a(x) = a3*x^3 + a2*x^2 + a1*x + a0 mit a0(x) = x, a1(x) = 1
    'a2(x) = 1, x3(x) = x+1, dann modulo M(x) = x^4+1 reduziert.
    
'Es ergibt sich folgende Matrixmultiplikation:
    'b0 = |02 03 01 01||b0|, b0 = a0*b0 + a3*b1 + a2*b2 + a1*b3
    'b1 = |01 02 03 01||b1|
    'b2 = |01 01 02 03||b2|
    'b3 = |03 01 01 02||b3|
    
    For j = 0 To UBound(block, 1)
      tmp(0) = mul(block(j, 0), 2) Xor mul(block(j, 1), 3) Xor _
          block(j, 2) Xor block(j, 3)
      tmp(1) = mul(block(j, 1), 2) Xor mul(block(j, 2), 3) Xor _
          block(j, 3) Xor block(j, 0)
      tmp(2) = mul(block(j, 2), 2) Xor mul(block(j, 3), 3) Xor _
          block(j, 0) Xor block(j, 1)
      tmp(3) = mul(block(j, 3), 2) Xor mul(block(j, 0), 3) Xor _
          block(j, 1) Xor block(j, 2)
      For i = 0 To 3
        block(j, i) = tmp(i)
      Next i
    Next j
End Sub
Private Sub AddRoundKey(block() As Byte, rk_off As Long)
  Dim i As Long, n As Long
    
    'Addiert den Rundenschlüssel zum Block
    
    For i = 0 To Lb - 1
      For n = 0 To 3
        block(i, n) = block(i, n) Xor key(rk_off + i, n)
      Next n
    Next i
End Sub
Private Sub InvSubBytes(block() As Byte)
  Dim i As Long, j As Long
    
    'Inversion von SubBytes
    
    For i = 0 To 3
      For j = 0 To UBound(block, 1)
        block(j, i) = InvSubstitution(block(j, i))
      Next j
    Next i
End Sub
Private Sub InvMixColumns(block() As Byte)
  Dim i As Long, j As Long, tmp(3) As Long
    
    'Jede Spalte des Blocks wird als Polynom mit Koeffizienten
    'aus F_2^8 aufgefasst und mit dem festen Polynom
    'a(x) = a3*x^3 + a2*x^2 + a1*x + a0 mit a0(x) = x^3+x^2+x
    'a1(x) = x^3+1, a2(x) = x^3+x^2+1, x3(x) = x^3+x+1,
    'dann modulo M(x) = x^4+1 reduziert.
    
'Es ergibt sich folgende Matrixmultiplikation:
    'b0 = |0E 0B 0D 09||b0|
    'b1 = |09 0E 0B 0D||b1|
    'b2 = |0D 09 0E 0B||b2|
    'b3 = |0B 0D 09 0E||b3|
    
    For j = 0 To UBound(block, 1)
      tmp(0) = mul(block(j, 0), &HE&) Xor mul(block(j, 1), &HB&) _
          Xor mul(block(j, 2), &HD&) Xor mul(block(j, 3), 9)
      tmp(1) = mul(block(j, 1), &HE&) Xor mul(block(j, 2), &HB&) _
          Xor mul(block(j, 3), &HD&) Xor mul(block(j, 0), 9)
      tmp(2) = mul(block(j, 2), &HE&) Xor mul(block(j, 3), &HB&) _
          Xor mul(block(j, 0), &HD&) Xor mul(block(j, 1), 9)
      tmp(3) = mul(block(j, 3), &HE&) Xor mul(block(j, 0), &HB&) _
          Xor mul(block(j, 1), &HD&) Xor mul(block(j, 2), 9)
      For i = 0 To 3
        block(j, i) = tmp(i)
      Next i
    Next j
End Sub