I want to find out how many bit operations are performed for encryption in AES-128 with messages size $128$ bits.

For public key encryptions such as RSA and ElGamal, I know that number of bit operations required are $O(n^3)$ if the key considered has $n$ bits.

Are these equal to $O(1)$?

  • 1
    $\begingroup$ This question has been asked before. No, we don't use Big-Oh for symmetric ciphers, And that really depends on the implementation, use of a pre-computed table or not, etc. The only article that really counted is TOA et. al They went on this to show that their attack better than the brute-force. $\endgroup$
    – kelalaka
    Commented Mar 4, 2021 at 17:14
  • $\begingroup$ And, for the RSA, Why it is $O(n^3)$? $\endgroup$
    – kelalaka
    Commented Mar 4, 2021 at 17:17
  • $\begingroup$ RSA involves modular exponentiation. So, if we use square and multiply algorithm, then it is so. It can further be optimized. $\endgroup$
    – PAMG
    Commented Mar 4, 2021 at 17:20
  • $\begingroup$ It is $\mathcal{O}(3\cdot n^2)$ at most whem $e=3$ $\endgroup$
    – kelalaka
    Commented Mar 4, 2021 at 17:23
  • $\begingroup$ But e is not 3, in general. What if I want to send a same messages to more than 3 entities? $\endgroup$
    – PAMG
    Commented Mar 5, 2021 at 16:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.