Mixing
What is the time complexity of the basic components of a symmetric cipher?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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?
s-boxes complexity permutation matrix-multiplication present
asked 4 hours ago
Red Book 1
505416
add a comment |Â
up vote
1
down vote
favorite
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?
s-boxes complexity permutation matrix-multiplication present
asked 4 hours ago
Red Book 1
505416
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
s-boxes complexity permutation matrix-multiplication present
asked 4 hours ago
Red Book 1
505416
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?
s-boxes complexity permutation matrix-multiplication present
s-boxes complexity permutation matrix-multiplication present
asked 4 hours ago
Red Book 1
505416
asked 4 hours ago
Red Book 1
505416
asked 4 hours ago
Red Book 1
505416
asked 4 hours ago
Red Book 1
505416
asked 4 hours ago
Red Book 1
505416
505416
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago
add a comment |Â
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Landau (also “Big-Ohâ€Â) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.
- 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?
I did not see, any DES, or similar algorithm complexity. They are, usually, compared by the software/ hardware implementation speed and memory requirements and chip area if it is in hardware;
In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.
What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.
On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;
The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive searchXLS.
I'll look at some of your numbers;
- matrix multiplication (including permutation matrices)
Assuming a square Matrix has input size $n$ then we will have exactly $n^3 in mathcalO(n^3)$ multiplication with standard matrix multiplication. The fastest is $mathcalO(n^2.373)$, see Wikipedia article on Matrix Multiplication
- XOR of bit strings
Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.
- expansions, for instance, expanding 64 bits to 128 bits
This really depends on the expansion algorithm, if it is just copy than $mathcalO(1)$
- bit shifts
If single instruction as in addition in CPUs. $mathcalO(1)$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.
7.combining the operations (as above or other operations)
As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?
Usually, Crypto Algorithms are implemented and compared as in AES candidates.
answered 1 hour ago
kelalaka
2,066421
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
add a comment |Â
up vote
2
down vote
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).
Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.
Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.
answered 45 mins ago
Richie Frame
9,73411530
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Landau (also “Big-Ohâ€Â) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.
- 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?
I did not see, any DES, or similar algorithm complexity. They are, usually, compared by the software/ hardware implementation speed and memory requirements and chip area if it is in hardware;
In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.
What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.
On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;
The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive searchXLS.
I'll look at some of your numbers;
- matrix multiplication (including permutation matrices)
Assuming a square Matrix has input size $n$ then we will have exactly $n^3 in mathcalO(n^3)$ multiplication with standard matrix multiplication. The fastest is $mathcalO(n^2.373)$, see Wikipedia article on Matrix Multiplication
- XOR of bit strings
Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.
- expansions, for instance, expanding 64 bits to 128 bits
This really depends on the expansion algorithm, if it is just copy than $mathcalO(1)$
- bit shifts
If single instruction as in addition in CPUs. $mathcalO(1)$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.
7.combining the operations (as above or other operations)
As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?
Usually, Crypto Algorithms are implemented and compared as in AES candidates.
answered 1 hour ago
kelalaka
2,066421
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
add a comment |Â
up vote
1
down vote
accepted
Landau (also “Big-Ohâ€Â) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.
- 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?
I did not see, any DES, or similar algorithm complexity. They are, usually, compared by the software/ hardware implementation speed and memory requirements and chip area if it is in hardware;
In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.
What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.
On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;
The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive searchXLS.
I'll look at some of your numbers;
- matrix multiplication (including permutation matrices)
Assuming a square Matrix has input size $n$ then we will have exactly $n^3 in mathcalO(n^3)$ multiplication with standard matrix multiplication. The fastest is $mathcalO(n^2.373)$, see Wikipedia article on Matrix Multiplication
- XOR of bit strings
Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.
- expansions, for instance, expanding 64 bits to 128 bits
This really depends on the expansion algorithm, if it is just copy than $mathcalO(1)$
- bit shifts
If single instruction as in addition in CPUs. $mathcalO(1)$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.
7.combining the operations (as above or other operations)
As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?
Usually, Crypto Algorithms are implemented and compared as in AES candidates.
answered 1 hour ago
kelalaka
2,066421
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Landau (also “Big-Ohâ€Â) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.
- 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?
I did not see, any DES, or similar algorithm complexity. They are, usually, compared by the software/ hardware implementation speed and memory requirements and chip area if it is in hardware;
In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.
What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.
On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;
The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive searchXLS.
I'll look at some of your numbers;
- matrix multiplication (including permutation matrices)
Assuming a square Matrix has input size $n$ then we will have exactly $n^3 in mathcalO(n^3)$ multiplication with standard matrix multiplication. The fastest is $mathcalO(n^2.373)$, see Wikipedia article on Matrix Multiplication
- XOR of bit strings
Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.
- expansions, for instance, expanding 64 bits to 128 bits
This really depends on the expansion algorithm, if it is just copy than $mathcalO(1)$
- bit shifts
If single instruction as in addition in CPUs. $mathcalO(1)$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.
7.combining the operations (as above or other operations)
As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?
Usually, Crypto Algorithms are implemented and compared as in AES candidates.
answered 1 hour ago
kelalaka
2,066421
Landau (also “Big-Ohâ€Â) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.
- 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?
I did not see, any DES, or similar algorithm complexity. They are, usually, compared by the software/ hardware implementation speed and memory requirements and chip area if it is in hardware;
In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.
What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.
On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;
The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive searchXLS.
I'll look at some of your numbers;
- matrix multiplication (including permutation matrices)
Assuming a square Matrix has input size $n$ then we will have exactly $n^3 in mathcalO(n^3)$ multiplication with standard matrix multiplication. The fastest is $mathcalO(n^2.373)$, see Wikipedia article on Matrix Multiplication
- XOR of bit strings
Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.
- expansions, for instance, expanding 64 bits to 128 bits
This really depends on the expansion algorithm, if it is just copy than $mathcalO(1)$
- bit shifts
If single instruction as in addition in CPUs. $mathcalO(1)$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.
7.combining the operations (as above or other operations)
As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?
Usually, Crypto Algorithms are implemented and compared as in AES candidates.
answered 1 hour ago
kelalaka
2,066421
answered 1 hour ago
kelalaka
2,066421
answered 1 hour ago
kelalaka
2,066421
answered 1 hour ago
kelalaka
2,066421
2,066421
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
add a comment |Â
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
1
1
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
So just to confirm (regarding item .2), was I right that a $1 times n$ vector times an $n times n$ permutation matrix (or any I suppose) is $O(n^2)$?
– Red Book 1
21 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
@RedBook1 yes..
– kelalaka
17 mins ago
add a comment |Â
up vote
2
down vote
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).
Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.
Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.
answered 45 mins ago
Richie Frame
9,73411530
add a comment |Â
up vote
2
down vote
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).
Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.
Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.
answered 45 mins ago
Richie Frame
9,73411530
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).
Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.
Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.
answered 45 mins ago
Richie Frame
9,73411530
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).
Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.
Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.
answered 45 mins ago
Richie Frame
9,73411530
answered 45 mins ago
Richie Frame
9,73411530
answered 45 mins ago
Richie Frame
9,73411530
answered 45 mins ago
Richie Frame
9,73411530
9,73411530
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63577%2fwhat-is-the-time-complexity-of-the-basic-components-of-a-symmetric-cipher%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Look at this Is there a system behind the magic of algorithm analysis?
– kelalaka
2 hours ago