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:

$\sum_{i=1}^m 1=n$,

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

My analysis:

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.

  • 4
    $\begingroup$ Why not Transform and Conquer? AES uses substitution, shiftrows, MixColumns. (Confusion and Diffusion) $\endgroup$ – SSA Dec 31 '20 at 5:11
  • 1
    $\begingroup$ I agree, the divide and conquer is not wrong per se, but it is more indicative of a block cipher in a mode of operation than the AES cipher itself. $\endgroup$ – Maarten Bodewes Dec 31 '20 at 12:43
  • 2
    $\begingroup$ Complexity is wrong too, for the same reason. AES is a block cipher, so it encrypts exactly one fixed-sized block of data with a fixed-size key (for any of the 3 variants). It's always O(1). And in cryptography, we don't generally ignore the constant terms, AES and other ciphers MUST take a constant number of CPU cycles on any given processor to be secure. It's possible to implement AES in such a way that it's not constant-time while it's still O(1), those implementations are unsafe. $\endgroup$ – SAI Peregrinus Dec 31 '20 at 14:47
  • $\begingroup$ The complexity analysis is not mathematical analysis. It uses Math. Counting the number of operations of AES is extensively performed when an attack needs to be compared against the brute-force. These articles can be found here. Oher than that, we usually inplement and show that why this is faster then the others. $\endgroup$ – kelalaka Dec 31 '20 at 15:25
  • $\begingroup$ Thanks for your help, I was undecided between Divide and Transform but I think you are right. About the complexity, @SAIPeregrinus yes, that was my initial idea, I though it's constant, but I read some documentation and even a post here where says it is linear because AES encrypts plaintext and if the amount of text increases, it also increases the runtime because there are more blocks to encrypt. I'm not saying you're wrong, it is just what I found; I'm still confused/undecided about it. $\endgroup$ – AnthonyLau Dec 31 '20 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.