Hello everyone and happy new year in advance.
I'm doing a work about the analysis of the AES algorithm, and I have some doubts about this.
First, I need to do the mathematical analysis of the algorithm:
Determine the computational complexity, worst-case, average-case and best-case
As AES performs n numbers of rounds (10, 12, or 14) and we have a loop, I made a summation for an iterative algorithm, and I have this:
So, my conclusion is that, if I want to encrypt n number of bytes, the most, the average, and the least number of bytes that I must encrypt is n, I cannot encrypt more or less than that. Therefore:
$n \in O(n)$
$n \in \theta(n)$
$n \in \Omega(n)$
My conclusion is that, the cases (worst-average and best) are equivalent and AES have a linear complexity (depends on the number of bytes that I want to encrypt).
Determine de design paradigm
I don't know if this question is clear for you, I need to determine if AES is in one of the following design paradigm: Brute Force, Divide and Conquer, Decrease and Conquer, or Transform and Conquer
AES is designed to work in blocks of 16 bytes, and if we have more than 16 bytes it is supposed to DIVIDE the text in blocks of 16 bytes and work with each block until the whole text is encrypted.
Therefore, my conclusion is that AES has a Divide and Conquer design paradigm; and going deeper, is a divide and conquer by a constant factor (16).
I would really appreciate your opinion, and corrections, if necessary, to my analysis and conclusions.
Do the empirical analysis of the algorithm, and see if it is consistent with the mathematical results
For the empirical analysis, my idea is just to measure the runtime with different number of bytes, then fit a curve and see if it is linear. If you can suggest, maybe, a better or more advance way to do this, it would be great.
I would really appreciate your opinion and help with this.
Thanks again, and happy new year.