Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1} \bmod N$ contribute to the time complexity?

share|improve this question
    
modPow is around $O(n^3)$ –  CodesInChaos Jan 29 '13 at 19:42
    
Note $\log{d} \approx \log{n}$ but $\log{e}$ is independent of $n$ - since $e$ is generally taken as a small value, so in this sense $O(\log{e}) = 1$ (slight abuse of notation). I assume this is the RSA algorithm. –  Thomas Jan 29 '13 at 20:12
    
Mr Thomas you mean log N not log n where n number of bits in N . –  almodawan Jan 29 '13 at 20:26
    
@almodawan My comment assumed $n$ (or $N$) is the modulus itself, and $\log{n}$ (or $\log{N}$) is the number of digits. I find using the same symbol with different capitalization for two different concepts is very misleading and error-prone, but you are of course free to convert to your own notation. –  Thomas Jan 29 '13 at 20:30
    
Welcome to Cryptography Stack Exchange. Questions about specific implementations are considered off-topic here, and including source code is often a sign of this. Therefore, I edited your question to contain the formulas instead of the source code. Still, the actual complexity calculation is only tangentially related to cryptography. –  Paŭlo Ebermann Jan 31 '13 at 22:37
add comment

1 Answer

I'll be assuming the question considers time complexity in big-O notation only, because that's common, the simplest, and there is no indication of the contrary. The price to pay for this simplicity is that the resulting time complexity is often a poor way to compare the efficiency of different algorithms.


In this section I restrict to the standard algorithms for addition, multiplication and division (taught in elementary school using base $10$), because they are the simplest, and often used in cryptography (with a higher base like $2^{32}$, but that does not change the time complexity in $O()$ notation).

Computing $A+B$ or $A-B$ in $\mathbb Z$ has time complexity $O(a)$, where $a$ is the number of digits of $A$ (in any base), and $b=O(a)$ using the same convention for $b$. In a cryptographic context, we take the liberty of writing that time complexity $O(\log(A))$.

Computing $A·B$ in $\mathbb Z$ has time complexity $O(a·b)$, or $O(\log(A)·\log(B))$. When $b=O(a)$, that time complexity is $O(a^2)$, or $O(\log(A)^2)$.

Euclidian division of $A\in\mathbb Z$ by $N\in\mathbb{N^*}$, that is computing $R\in[0…N-1]$ and $Q\in\mathbb Z$ such that $A=N·Q+R$, has time complexity identical to that for computing $N·Q$, that is $O(n·q)$, or $O(\log(N)·\log(Q))$.

When performing modular multiplication $A·B\bmod N$ in a cryptographic context, it is typical, and assumed unless otherwise stated, that $a=O(n)$ and $b=O(n)$. It follows that the time complexity of modular multiplication is $O(n^2)$, or $O(\log(N)^2)$.

Modular exponentiation $A^B\bmod N$ with $B>0$ requires at least $\log_2(B)$ modular multiplications (baring shortcuts possible using the factorization of $N$), and less than ${3\over2}·\log_2(B)$ using square-and-multiply. It thus has time complexity $O(n^2·b)$ or $O(\log(N)^2·\log(B))$.

With standard RSA assumptions, computing $C^d \bmod N$ has time complexity $O(\log(N)^3)$; that's because $d$ has size in bits or digits proportional to that of $N$ (and further, close to that), thus the size of $d$ is $O(\log(N))$. This remains unchanged when the CRT technique is used and there is a fixed number of prime factors in $N$ (which reduces the computational cost "only" proportionally to the square of the number of factors).

In RSA, if the public exponent $e$ is fixed, or of bounded size (which is common, and mandated by FIPS 186), then computing $M^e\bmod N$ has time complexity $O(\log(N)^2)$; that's because it is done with a fixed or bounded number of modular multiplications (e.g. $17$ for the common $e=2^{16}+1$). On the other hand, $e$ is sometime allowed to be of the same order of magnitude as $N$ (e.g. in PKCS#1), in which (rare) case $M^e\bmod N$ has time complexity $O(\log(N)^3)$.

$O(\log(N)^3)$ is, of course, not the same as (and more than) $O(\log(N)^2)$. In practice, the RSA private key operation (using $d$) is often much slower than the public key operation (using $e$).

The most commonly taught algorithm to compute the modular inverse $k^{-1}\bmod N$ is the Extended Euclidian algorithm. It is easy to show that it requires at worse $O(\log(N))$ steps, and that the time complexity of any step is $O(\log(N)^2)$ in the worst case (e.g. on the first step for $k\approx\sqrt N$), which is enough for some to give the time complexity as $O(\log(N)^3)$. However, this is grossly pessimistic: the worst case in term of number of steps corresponds to steps of time complexity $O(\log(N))$, and longer steps correspondingly reduce the number of further steps. By induction, I come to the conclusion that the time complexity really is $O(\log(N)^2)$ (but I would not bet the house on that; I welcome a reference, a refutation, or a proof).

Computing $M·k\bmod N$ with the same assumptions as in standard RSA regarding $N$ and $M$, and assuming that $k$ has size proportional to that of $N$, has obviously the same time complexity as modular multiplication, $O(\log(N)^2)$.

Using the same assumptions, computing $C·k^{-1}\bmod N$ has time complexity $O(\log(N)^2)$; that is dominated by the modular inversion step, for any implementation I can think of that uses comparable care in the modular inversion and the modular multiplication.


Notice the importance of the assumption: standard algorithms for multiplication and division. By using the Karatsuba technique for multiplication and Barett reduction for Euclidian division, modular multiplication has time complexity less than $O(\log(N)^{1.585})$ rather than $O(\log(N)^2)$; that's useful, and used in some software implementations of RSA, reducing the time complexity of the private (resp. public) key operation to less than $O(\log(N)^{2.585})$ (resp. $O(\log(N)^{1.585})$). The exponent can go further down using Toom–Cook, which generalizes Karatsuba. Schönhage–Strassen multiplication has time complexity $O(\log(N)·\log\log(N)·\log\log\log(N))$. And that's not the ultimate theoretical technique.

The crossover between classical and sub-quadratic algorithms depends a lot on the quality of the implementation, and in particular on how close to the CPU architecture it gets (that's an area where assembly language shines over C, which obstructs access to the carry bit, and often to the whole result of the product of two unsigned integers of the widest size natively supported). While nearly optimal implementations of the classical algorithms using assembly language are relatively common, implementations of sub-quadratic algorithms are often quite sub-optimal, or/and complex (and thus hard to prove right in all corner cases, with the possible exception of Karatsuba).

My usual online references for multiple-precision arithmetic are section 14 in the HAC, and Modern Computer Arithmetic.

share|improve this answer
    
Thank you for all. –  almodawan Feb 1 '13 at 23:09
    
Thank you for all. but I have wondered simple in last algorithm MP = C * k^-1 mod N. I can say D = k ^ -1 mod N// here complexity equal O(n^2) and MP = D * C mod N // here complexity is O(n^2). Then Total time is O(n^2)+O(n^2)=O(2 n^2) = O(n^2)............Just to make sure –  almodawan Feb 1 '13 at 23:22
    
@almodawan: I now have improved my own understanding to the point that I can say: Yes! to your above comment. –  fgrieu Feb 3 '13 at 12:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.