Tag Info

Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$. If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you ...

The last major effort I know of for cracking keys was the Distributed.net effort. You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP ...

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$). If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be ...

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is: $a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$ $a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$ $a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$ As such, addition and subtraction can be ...

The Handbook on Applied Cryptography (link to the pdf version is on Alfred's webpage) has some of the known techniques to do finite field arithematic. If you are doing arithmetic to implement Elliptic Curve Cryptography (note the comment made by Paulo), then there are methods that depends on whether you are doing it in Jacobian or Projective plane (inverse ...

Well, assuming that you have a fixed block cipher (that is, you don't change the block cipher as the length of the message increases), then given a message of length $N$: Both ECB and OFB take $O(N)$ time for both encryption and decryption. Both ECB and OFB take $O(1)$ space in addition to the space to hold the encrypted/decrypted message (which is ...

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem. The first observation is that if you know the group order $n$ and a group generator ...

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 ...

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$). In this question we are given less information, but similar techniques should still apply. Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a ...

On the third case, I have a comment. The third oracle may help the adversary using Cheon's algorithm for the DL problem. Let $q$ be a prime order of the subgroup $\mathbb{G}$ of $(\mathbb{Z}/p\mathbb{Z})^{\times}$. In the third case, the adversary has an oracle $a \mapsto a^k$ for any $a$. Hence, it can obtain $g^{k^i}$ from $g^{k^{i-1}}$ and so on. When ...

In practise the view would be that no, it does not get any easier. Indeed many popular deployed schemes depend on it. For example the Trusted Authority in the Boneh-Franklin IBE scheme has a master secret s and issues private keys to users in the form s.ID_i, where ID_i is a point on an elliptic curve, and ID_i is related to the identity of the i-th user. It ...

I can answer the question for the first of the three cases: Random choice. In this case, seeing $n$ instances cannot help the adversary very much (not more than a $n$-fold speedup). The problem still remains hard, for suitably large $p$. Justification: By a simple reduction. Suppose we had a clever algorithm to solve the problem for $n>1$. I will ...

Any reversible cipher will need at least $\Omega(n)$ time (where $n$ is the size of the plaintext), since we need to touch each bit at least once. A stream cipher (i.e. deterministic pseudo-random bit generator) does some fixed amount of work for each bit (or larger unit) of output (with maybe some initial preparation overhead), which is $O(n)$. A block ...

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit. So: c = m ⊕ G(k) m = c ⊕ G(k) Where c is ciphertext, m is plaintext, G is the RNG and k is the key. As such, all stream ciphers should be O(n) ...

As noted by poncho, both ECB and OFB encryption (and decryption) require $O(n)$ time and $O(1)$ additional space (excluding the input and output, which may be modeled as unseekable streams). These hold both in the average and in the worst case, and it's worth noting that the complexities approach their asymptotes very quickly; typically, the time complexity ...

Just because a lower bound has been shown does not necessarily make the problem good for crypto. For example, approximation algorithms or probabilistic algorithms could be used to break the system. That said, I would imagine that a lower-bound could strengthen the argument for a particular system. So, it would seem that a lower bound is neither necessary ...

Any symmetric crypto with key length of 64 bits or less can be brute forced with the relatively cheap copacobana hardware. If a major player built special purpose hardware like this filling racks with $256$ copacobanas in parallel, they would in theory be able to brute force keys of $2 ^ {64 + 8} = 2 ^ {72}$ bits. But that is still a long way from 128 bits. ...

I'm turning earlier discussion into a partial answer. I apologize if the whole thing can be considered off-topic (we are discussing computer science, with specialization to Java, and only potential application to cryptography). In order to discuss time complexity, we must specify the algorithm used, and that's not done in the question. However, in Java, an ...

Generally speaking, this problem is computationally easy. It is easy to tell whether a solution exists and, if so, to find at least one. If you want to find one solution (one $x$ that satisfies the equation), assuming a solution exists, this is easy. @CodesInChaos explains how. If you want to find all solutions, then it's easy to enumerate all solutions. ...

There is nothing stopping you from doing this. I don't know of any cryptosystem that is in use today that would be considered unsecure against a quasi-polynomial time adversary. RSA is probably the closest. It is super-polynomial (thanks to GNFS), so it would still be secure in a quasi-poly time adversarial model. The only argument I see against ...