I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in symmetric ciphers. In particular:
- matrix multiplication (including permutation matrices)
- XOR of bit strings
- expansions, for instance expanding 64 bits to 128 bits
- bit shifts
- permutations using a P-box (say the one in PRESENT)
- substitutions using an S-box (again, say the one in PRESENT)
- combining the operations (as above or other operations)
Related to item 1: If I multiply (say) $vP$ where $v$ is a $1 \times n$ vector and $P$ is an $n \times n$ permutation matrix I see $1 \times n \times n$ multiplications and $n \times n$ XORs (assuming bits). So am I right to sat $O(vP) = n^2 + n \approx n^2$ ?
Related to item 2: a linear operation so I assume $O(1)$ for each XOR and therefore $O(n) = n$ for $n$-bit string XOR another $n$-bit-string.
Related to item 3: If expanding $64$ bits to $128$ bits then it seems there are $128$ operations so $O(n) = n$
Related to item 4: intuitively I should say $O(1)$ for each bit shift and therefore for $n$ bit-shifts $O(n)=n$.
Related to items 5 and 6: I really have little idea. But if it is the $PRESENT$ P-box then I suppose $64$ operations and therefore $O(n=64)=n$. As for the S-box, I think $O(n = 16) = n$, assuming the $PRESENT$ S-box.
Related to item 7: I think we add the time complexities of each component but can approximate the answer as the most time consuming of all terms.
I have looked at a few videos and books on time complexity but most speak in programming languages, and I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above.
One final question:
- I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ciphers?