AES Codeoptimierung auf at91sam7x256 (ARM7TDMI)

Marcel B. OP #3565803
Lesenswert?
• ▲
▼ 
Juten Abend,

ich hab zu Übungszwecken mal eine AES Implementierung für mein 
at91sam7x256 gebastelt. Die Implementierung hällt sich ziemlich streng 
an die ganzen Referenzimplementierungen, die vom AES so im Netz 
rumschwirren. Nun bin ich die ganze Zeit am Testen und habe irgendwie 
das Gefühl das die Verschlüsselung echt lange dauert. Der Code ist 
komplett in C geschrieben. Die Daten die ich verschlüssele bzw. 
entschlüssele werden blockweise über den SPI Bus von einer SD Karte 
gelesen und dort auch wieder geschrieben. Nach einigen Tests kann ich 
jedoch sagen, dass die Lese- bzw. Schreibvorgänge eine Verschlüsselung 
von größeren Dateien nicht stark beeinflusst. Als Blockchiffren Modi 
nutze ich den ECB bzw. CBC Mode. Beide nehmen sich nicht sonderlich 
viel, was die Geschwindigkeit angeht. Ich kann letzten Endes behaupten, 
dass wenn es irgendwas zu optimieren gibt, es irgendwo im eigentlichen 
Algorithmus sein muss.

Um es mal auf den Punkt zu bringen, eine Verschlüsselung einer bmp 
Bilddatei mit der Größe von ca. 198 kByte dauert knapp 63,5 s. Jetzt 
frage ich mich, inwiefern ich auf der Ebene von dem C-Code noch was 
optimieren könnte.

Ich poste hier mal den Code vom AES. Vielleicht fällt ja jemanden auf 
was ich hier besser machen kann. Ich bin für jeden Tipp dankbar!!!

1
/*---------------------------------------------------------------

2
                                helper 

3
-----------------------------------------------------------------*/

4


5
static uint8_t getSBoxValue(uint8_t num)

6
{

7
    return SBox[num];

8
}

9


10
static uint8_t getRSBoxValue(uint8_t num)

11
{

12
    return RSBox[num];

13
}

14


15
static uint32_t galoisMulti(uint8_t fact_1, uint8_t fact_2)

16
{

17
  uint32_t product = 0;

18
  uint8_t i, hi_bit_set;

19
        

20
  //for(i = 0; i < 8; i++)

21
  for(i = 8; i > 0; i--)

22
  {

23
    if((fact_2 & 1) == 1)

24
    {

25
      product ^= fact_1;

26
    }

27
    

28
    hi_bit_set = fact_1 & 0x80;

29
    fact_1 <<= 1;

30
      

31
    if(hi_bit_set == 0x80)

32
    {

33
      fact_1 ^= 0x1B;

34
    }

35
    

36
    fact_2 >>= 1;

37
  }

38
    

39
  return product;

40
}

41


42
static void createRoundKey(uint8_t* expandedKey, uint8_t* roundKey)

43
{

44
  uint8_t i, j;

45
  

46
  // Iterate over the columns

47
  for (i = 0; i < 4; i++) 

48
  {

49
    // Iterate over the rows

50
    for (j = 0; j < 4; j++) 

51
    {

52
      roundKey[(i + (j * 4))] = expandedKey[(i * 4) + j];

53
    }

54
  }

55
}

56


57
/*---------------------------------------------------------------

58
                                Sub Bytes 

59
-----------------------------------------------------------------*/

60


61
static void subBytes(uint8_t* block)

62
{

63
  uint32_t i;

64


65
  for(i = 0; i < BLOCK_SIZE; i++)

66
  {

67
    block[i] = getSBoxValue(block[i]);

68
  }

69
}

70


71
static void iSubBytes(uint8_t* block)

72
{

73
  uint32_t i;

74


75
  for(i = 0; i < BLOCK_SIZE; i++)

76
  {

77
    block[i] = getRSBoxValue(block[i]);

78
  }

79
}

80


81
/*---------------------------------------------------------------

82
                               Shift Rows

83
-----------------------------------------------------------------*/

84


85
static void shiftRow(uint8_t* row, uint8_t rNumber)

86
{

87
  uint8_t i, j, tmp;

88
  

89
  //for(i = 0; i < rNumber; i++)

90
  for(i = rNumber; i > 0; i--)

91
  {

92
    tmp = row[0];

93
    

94
    for(j = 0; j < 3; j++)

95
    {

96
      row[j] = row[j + 1];

97
    }

98
    

99
    row[3] = tmp;

100
  }

101
}

102


103
static void shiftRows(uint8_t* block)

104
{

105
  uint8_t i;

106
  

107
  for(i = 1; i < 4; i++)

108
  {

109
    shiftRow(block + (i * 4), i);

110
  }

111
}

112


113
static void iShiftRow(uint8_t* row, uint8_t rNumber)

114
{

115
  uint8_t i, j, tmp;

116
  

117
  //for(i = 0; i < rNumber; i++)

118
  for(i = rNumber; i > 0; i--)

119
  {

120
    tmp = row[3];

121
    

122
    for(j = 3; j > 0; j--)

123
    {

124
      row[j] = row[j - 1];

125
    }

126
    

127
    row[0] = tmp;

128
  }

129
}

130


131
static void iShiftRows(uint8_t* block)

132
{

133
  uint8_t i;

134
  

135
  for(i = 1; i < 4; i++)

136
  {

137
    iShiftRow(block + (i * 4), i);

138
  }

139
}

140


141
/*---------------------------------------------------------------

142
                               Mix Columns

143
-----------------------------------------------------------------*/

144


145
static void mixColumns(uint8_t* block)

146
{

147
  uint32_t i, j;

148
  uint8_t columnNumber = 4;

149
  uint8_t tmp[16];

150


151
  for(i = 0; i < columnNumber; i++)

152
  {

153
    tmp[i] =

154
      galoisMulti( block[i], 0x02 ) ^ galoisMulti( block[columnNumber + i], 0x03 )

155
        ^ galoisMulti( block[2 * columnNumber + i], 0x01 ) ^ galoisMulti( block[3 * columnNumber + i], 0x01 );

156
    tmp[columnNumber + i] =

157
      galoisMulti( block[i], 0x01 ) ^ galoisMulti( block[columnNumber + i], 0x02 )

158
        ^ galoisMulti( block[2 * columnNumber + i], 0x03 ) ^ galoisMulti( block[3 * columnNumber + i], 0x01 );

159
    tmp[2 * columnNumber + i] =

160
      galoisMulti( block[i], 0x01 ) ^ galoisMulti( block[columnNumber + i], 0x01 )

161
        ^ galoisMulti( block[2 * columnNumber + i], 0x02 ) ^ galoisMulti( block[3 * columnNumber + i], 0x03 );

162
    tmp[3 * columnNumber + i] =

163
      galoisMulti( block[i], 0x03 ) ^ galoisMulti( block[columnNumber + i], 0x01 )

164
        ^ galoisMulti( block[2 * columnNumber + i], 0x01 ) ^ galoisMulti( block[3 * columnNumber + i], 0x02 );

165
  }

166
        

167
  //for (j = 0; j < BLOCK_SIZE; j++)

168
  for (j = BLOCK_SIZE; j > 0; j--)

169
  {

170
    block[j] = tmp[j] & 0xf0ff;

171
  }

172
}

173


174
static void iMixColumns(uint8_t* block)

175
{

176
  uint32_t i, j;

177
  uint8_t columnNumber = 4;

178
  uint8_t tmp[16];

179


180
  for (i = 0; i < columnNumber; i++)

181
  {

182
    tmp[i] =

183
      galoisMulti(block[i], 0x0e) ^ galoisMulti(block[columnNumber + i], 0x0b)

184
        ^ galoisMulti(block[2 * columnNumber + i], 0x0d) ^ galoisMulti(block[3 * columnNumber + i], 0x09);

185
    tmp[columnNumber + i] =

186
      galoisMulti(block[i], 0x09) ^ galoisMulti(block[columnNumber + i], 0x0e )

187
        ^ galoisMulti(block[2 * columnNumber + i], 0x0b) ^ galoisMulti(block[3 * columnNumber + i], 0x0d);

188
    tmp[2 * columnNumber + i] =

189
      galoisMulti(block[i], 0x0d) ^ galoisMulti(block[columnNumber + i], 0x09)

190
        ^ galoisMulti(block[2 * columnNumber + i], 0x0e) ^ galoisMulti(block[3 * columnNumber + i], 0x0b);

191
    tmp[3 * columnNumber + i] =

192
      galoisMulti(block[i], 0x0b) ^ galoisMulti(block[columnNumber + i], 0x0d)

193
        ^ galoisMulti(block[2 * columnNumber + i], 0x09) ^ galoisMulti(block[3 * columnNumber + i], 0x0e);

194
  }

195
  

196
  //for (j = 0; j < BLOCK_SIZE; j++)

197
  for (j = BLOCK_SIZE; j > 0; j--)

198
  {

199
      block[j] = tmp[j] & 0xf0ff;

200
  }

201
}

202


203
/*---------------------------------------------------------------

204
                               Add Round Key

205
-----------------------------------------------------------------*/

206


207
static void addRoundKey(uint8_t* text, uint8_t* roundKey )

208
{

209
  uint8_t i;

210
  

211
  //for(i = 0; i < 16; i++)

212
  for(i = 16; i > 0; i--)

213
  {

214
    text[i] ^= roundKey[i];

215
  }

216
}

217


218
/*---------------------------------------------------------------

219
                               Key expansion

220
-----------------------------------------------------------------*/

221


222
static void rotate(uint8_t* column)

223
{

224
  uint8_t i, tmp;

225
  

226
  tmp = column[0];

227
  

228
  for(i = 0; i < 3; i++)

229
  {

230
    column[i] = column[i + 1];

231
  }

232
  

233
  column[3] = tmp;

234
}

235


236
static void keyScheduleCore(uint8_t* word, uint32_t rconIteration)

237
{

238
  rotate( word );

239
  subBytes( word );

240
  word[0] ^= R_CON[rconIteration];

241
}

242


243
static void expandKey(uint8_t* expandedKey, uint32_t expandedKeySize, uint8_t* cipherKey, uint8_t keySize)

244
{

245
  uint32_t i, currentSize = 0, rconIteration = 1;

246
  uint8_t tmp[4] = {0};

247


248
  //for(i = 0; i < keySize; i++)

249
  for(i = keySize; i > 0; i--) 

250
  {

251
    expandedKey[i] = cipherKey[i];

252
  }

253
  

254
  currentSize += keySize;

255
  

256
  

257
  while(currentSize < expandedKeySize)

258
  {

259
    //asign the previous 4 byte to tmp

260
    for(i = 0; i < 4; i++) 

261
    {

262
      tmp[i] = expandedKey[(currentSize - 4) + i];

263
    }

264
    

265
    // every 16, 24, 32 ... bytes call keyScheduleCore

266
    if((currentSize % keySize) == 0) 

267
    {

268
      keyScheduleCore(tmp, rconIteration++);

269
    }

270
    

271
    if(keySize == Bits256 && ((currentSize % keySize) == 16)) 

272
    {

273
      //for(i = 0; i < 4; i++) 

274
      for(i = 4; i > 0; i--) 

275
      {

276
        tmp[i] = getSBoxValue(tmp[i]);

277
      }

278
    }

279
    

280
    for(i = 0; i < 4; i++) 

281
    {

282
      expandedKey[currentSize] = expandedKey[currentSize - keySize] ^ tmp[i];

283
      currentSize++;

284
    }

285
  }

286
}

287


288
static void round(uint8_t* block, uint8_t* roundKey)

289
{

290
  subBytes(block);

291
  shiftRows(block);

292
  mixColumns(block);

293
  addRoundKey(block, roundKey);

294
}

295


296
static void finalRound(uint8_t* block, uint8_t* roundKey)

297
{

298
  subBytes(block);

299
  shiftRows(block);

300
  addRoundKey(block, roundKey);

301
}

302


303
/*---------------------------------------------------------------

304
                               AES Encryption

305
-----------------------------------------------------------------*/

306


307
void aesEncrypt(uint8_t* block, uint8_t* cipherKey, uint8_t keySize)

308
{

309
  uint8_t roundKey[16];

310
  uint8_t expandedKey[240] = { 0 };

311
  uint8_t i, expandedKeySize, rounds;

312
  expandedKeySize = GET_EXP_KEYSIZE(keySize);

313


314
  setLED(LED_YELLOW);

315


316
  expandKey(expandedKey, expandedKeySize, cipherKey, keySize);

317


318
  if(keySize == Bits128)

319
    rounds = 10;

320
  else if(keySize == Bits192)

321
    rounds = 12;

322
  else

323
    rounds = 14;

324


325
  createRoundKey(expandedKey, roundKey);

326
  addRoundKey(block, roundKey);

327
  

328
  for (i = 1; i < rounds; i++) 

329
  {

330
    createRoundKey(expandedKey + 16 * i, roundKey);

331
    round(block, roundKey);

332
  }

333


334
  createRoundKey(expandedKey + 16 * rounds, roundKey);

335
  finalRound(block, roundKey);

336
  

337
  resetLED(LED_YELLOW);

338
}

339


340
/*---------------------------------------------------------------

341
                               AES Decription

342
-----------------------------------------------------------------*/

343


344
void aesDecrypt(uint8_t* block, uint8_t* cipherKey, uint8_t keySize)

345
{

346
  uint8_t roundKey[16];

347
  uint8_t expandedKey[240] = { 0 };

348
  uint8_t i, expandedKeySize, rounds;

349
  expandedKeySize = GET_EXP_KEYSIZE(keySize);

350
  

351
  setLED(LED_YELLOW);

352


353
  expandKey(expandedKey, expandedKeySize, cipherKey, keySize);

354
  

355
   if(keySize == 16)

356
    rounds = 10;

357
  else if(keySize == 24)

358
    rounds = 12;

359
  else

360
    rounds = 14;

361
  

362
  createRoundKey(expandedKey + 16 * rounds, roundKey);

363
  addRoundKey(block, roundKey);

364
  iShiftRows(block);

365
  iSubBytes(block);

366
  

367
  for (i = rounds - 1; i > 0; i--) 

368
  {

369
    createRoundKey(expandedKey + 16 * i, roundKey);

370
    addRoundKey(block, roundKey);

371
    iMixColumns(block);

372
    iShiftRows(block);

373
    iSubBytes(block);

374
  }

375
  

376
  createRoundKey(expandedKey, roundKey);

377
  addRoundKey(block, roundKey);

378
  

379
  resetLED(LED_YELLOW);

380
}
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Frank K. #3565910
Lesenswert?
• ▲
▼ 
Compiliere das Zeugs mal auf einem PC und lass dann einen Profiler 
mitlaufen. Der sagt Dir dann, wo die "Hotspots" sind, d.h. welche 
Funktionen und Codezeilen besonders viel Rechenzeit brauchen.

Falls Du noch nichts von Profilern gehört hast:
http://www.codeplanet.eu/tutorials/cpp/68-c-cpp-profiler.html

Auf den ersten Blick empfehle ich Dir die beiden ersten Funktionen 
getSBoxValue() und getRSBoxValue() entweder inline zu machen oder in 
Form von Makros zu implementieren. Das ist einfach und macht nicht viel 
Arbeit.

fchk
Antwort Zitieren Bearbeiten Löschen Beitrag melden
(prx) A. K. #3565919
Lesenswert?
• ▲
▼ 
uint8_t bei Skalaren nur dann verwenden, wenn mit nicht mehr als 8 Bits 
gerechnet werden darf - unsigned oder uint_fast8_t verwenden. ARM 
rechnet mit 32 Bits schneller als mit 8 Bits. Return-Werte ebenfalls 
nicht als uint8_t deklarieren.

Diesen zeitkritischen Code ins RAM legen und als ARM Code übersetzen, 
nicht als Thumb, ggf. Interworking verwenden. Der Durchsatz vom AT91 
Flash ist für Thumb optimiert und für nativen ARM Code zu gering.

Optimierung des Compilers einschalten, mindestens -O2.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Frank K. #3565938
Lesenswert?
• ▲
▼ 
weitere Überlegungen:

1. Schleifenvariablen als unsigned int anstelle uint8_t deklarieren. x86 
kann in Registern direkt mit Bytes arbeiten, andere Architekturen wie zB 
ARM nicht.

Beispiel:
in R5 steht ein uint8_t a=0xe0.
in C: a+=0x40; -> ASM: add r5,#40h
in R5 steht jetzt 0xe0+0x40=0x120
Da R5 ja nur ein uint8_t ist, muss normalisiert werden
mov r0,#ffh
and r5,r0
Jetzt steht das drin, was gemäß C Standard drin stehen sollte: 0x20

mit int statt short oder int8_t vermeidest Du das.

2. Vergleiche
if((fact_2 & 1) == 1)
hier kann nur 0 oder 1 rauskommen. Statt auf ==1 zu prüfen, prüfe besser 
auf !=0. Das kann der Prozessor einfacher.
Ändern in:   if((fact_2 & 1) != 0)
oder kürzer: if(fact_2 & 1)

genauso:
    hi_bit_set = fact_1 & 0x80;
    fact_1 <<= 1;

    if(hi_bit_set == 0x80)
->  if(hi_bit_set) // das kann ja auch nur 0 oder 0x80 sein, und der 
Vergleich auf Null oder nicht NUll ist schneller gemacht als der 
Vergleich mit einer Konstante.

Das sind alles Kleinigkeiten, aber die summieren sich.

fchk
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Frank K. #3567094
Lesenswert?
• ▲
▼ 
Ich habe eben durch Zufall noch einen möglichen Fehler entdeckt:

1
  for (j = BLOCK_SIZE; j > 0; j--)

2
  {

3
    block[j] = tmp[j] & 0xf0ff;

4
  }


block[j] und tmp[j] sind uint8_t. Der andere Operand des bitweisen Unds 
ist aber ein 16 Bit Wert. Die obere Hälfte wird weggeworfen, die untere 
Hälfte ist 0xff, und tmp[j] & 0xff ist eben immer tmp[j]. Das wirst Du 
wohl kaum so beabsichtigt haben.

fchk
Antwort Zitieren Bearbeiten Löschen Beitrag melden
123 Gast #3567299
Lesenswert?
• ▲
▼ 
So hört sich das langsam an? Mal ein bischen rechnen.

198*1024*8/128=12672 AES Blöcke

63500ms/12673=5ms je block

So ich nahm jetzt mal 30MHz an.

Macht dan 150000 CPU cycles. Im Vergleich zu avr crypt deutlich 
langsamer. Da stehen 22000 bzw. 40000 je Durchgang.
In ASM lässt sich am avr noch deutlich was rausholen 2600 bzw 6700 
cycles je Durchgang.

Ich würde sagen da geht noch was.
CPU tackt (auf was war der bisher eingestellt)
Code aus RAM ausführen.
Compiler Optimierung aktivieren. (Speed)
Die sboxen auch im RAM halten. Ist schneller als aus dem langsamen 
flash.
Ggf 8 bit code auf 32 bit umbauen. Z.b. copier schleifen, ...

Gruß
Antwort Zitieren Bearbeiten Löschen Beitrag melden
123 Gast #3567319
Lesenswert?
• ▲
▼ 
So da sind ja noch einige Sachen drin....

Den block ggf als 4*32bit verarbeiten. Nicht als 8*8bit.
Alle XOR als32 bit aus führen. Den rotate als >>> definieren nicht als 
byte swap.
Die ganzen kurzen loops vermeiden. Die verursachen einen neu füllen der 
Pipeline.

(Aufpassen mit dem endien Format. Nicht geprüft ob das Probleme machen 
könnte)

Gruss
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Nosnibor Gast #3569976
Lesenswert?
• ▲
▼ 
Als erstes würde ich ja die Schlüsselexpansion nicht für jeden Block neu 
berechnen; die ändert sich nämlich nicht, solange der Schlüssel gleich 
bleibt.
Also: expandKey() einmal am Anfang aufrufen, und aesDecrypt() bekommt 
dann direkt expandedKey übergeben anstatt cipherKey.

Schlüsselexpansion bei jedem Block macht man nur, wenn der Speicher so 
knapp ist, daß man die ca. 200 Bytes zwischendurch dringend anderweitig 
braucht. Oder bei akademischem proof-of-concept-Code, der mit 
Flußdiagrammen und Schaubildern übereinstimmen muß.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Marcel B. OP #3598684
Lesenswert?
• ▲
▼ 
Okay, ich habe nun endlich mal Zeit gefunden mich dem Thema wieder 
einmal auseinander zusetzen. Der ganze AES Code inklusive der Block 
Modis CBC bzw. ECB (hab ich hier nicht gepostet) liegt nun nicht mehr im 
Flash sondern im Ram. Ich führe außerdem die Schlüsselausdehnung (danke 
für den Tipp :) ) nur noch beim ersten Datenblock durch. Alle danach 
folgenden Blöcke nutzen ja den gleichen Schlüssel -> also gleicher 
expandedKey. Ich habe auch einige Schleifen geändert, sprich Prüfung auf 
index >= 0. Das gleiche auch bei den wenigen If -Else Bedingungen.
Die Datentypen von byte/char zu int(also 32 bit) habe ich noch nicht 
geändert...kommt aber noch. Ach so, die Compiler Optimierung auf Zeit, 
ist nun auch dabei.

Im Endeffekt benötigt nun der Vorgang wie er Eingangs von mir erklärt 
wurde nur noch 16 Sekunden :) WOW kann ich da nur sagen. Vielen Dank für 
die vielen Tipps. Ihr habt mir echt geholfen.

@ Frank K.
Ähm ja, keine Ahnung wo das & 0xf0ff herkam. War auf jeden Fall falsch 
und gehört dort nicht hin. Vielen Dank!!

123 schrieb:
> Alle XOR als32 bit aus führen. Den rotate als >>> definieren nicht als
> byte swap.
Den rotate als >>> definieren? Das versteh ich nicht. Kann mir das 
jemand erläutern?

Viele Grüße

Marcel
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren