Hot answers tagged

16

Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer. Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...


12

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg: $\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$ The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the ...


8

"Cycles" are CPU instruction cycles. Cycles per byte roughly measures how many instructions, in a given instruction set, are needed to produce each byte of output. They're a reasonably-good relative measure of the performance of different algorithms. Generally, when you measure an algorithm's cycles per byte, you use carefully controlled conditions. You ...


8

Bitslicing is a technique where a computation is Reduced to elementary operations (called gates) with two bit inputs (typically NOR, XOR, and similar like OR AND NAND NXOR), rather than operations on words or integers spanning several bits. Executed in parallel, with as many simultaneous instances (on a single CPU) as there are bits in some register kind, ...


8

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good ...


8

It depends. Specifically, it depends on the type of cipher, and on the way it's used. For stream ciphers like RC4, and for block ciphers like AES in CTR and OFB modes, decryption is effectively identical to encryption, and thus takes the exact same time. (Minor exception: encryption may require generating a unique nonce / IV, which might take a small ...


7

Yes, AES-128 is intended to be the standard block cipher for building a secure and efficient symmetric cryptosystem using some block cipher operating mode, like CTR for encryption or GCM for authenticated encryption; efficiency can be particularly good when there is hardware support for AES and GCM. There might be better choices in the case at hand, like ...


6

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...


6

From the diagram on CTR mode you can notice that there are no dependencies between any of the phases of the pipeline. If you have more than one block-size worth of data, you can process each block-size chunk completely independently of the others by calculating $\mathrm{ciphertext}_i = E(\mathrm{key}, \mathrm{nonce} \, || \, \mathrm{counter}_i) \oplus ...


6

Given the choice, it is preferable to use the block encryption operation of AES, since it often faster than block decryption (never slower AFAIK). For this reason, AES-CTR is defined to use the block encryption operation of AES exclusively; that's both for AES-CTR encryption and AES-CTR decryption, which are the same operation except for IV generation/input. ...


6

The previous answer has the correct formula for estimating the security level of prime field elliptic curves. However, the table seems to just list the closest Koblitz curve sizes used, as Richie Frame points out. If you computed the actual security strength of the curves in question, you would not end up with exactly the values in the left column. For ...


5

The basic idea of bitslicing, or SIMD within a register, involves two parts: expressing the cipher in terms of single-bit logical operations (AND, OR, XOR, NOT, etc.), as if you were implementing it in hardware, and carrying out those operations for multiple instances of the cipher in parallel, using bitwise operations on a CPU. That is, in a bitsliced ...


5

In RSA encryption as practiced (that is, to encipher a message which is a short symmetric key), the message size after padding is fixed and equal to the modulus size. Thus the size of the message has no impact on performance. Calculating a modular inverse is performed only during key generation, that is seldom. Also, it has low cost compared to generating ...


5

Pretty much all modern encryption systems (including AES, in any standard mode) are data-agnostic: they are designed to encrypt any byte (or bit) stream regardless of its content, and their performance does not depend in any way on what the stream contains. Indeed, if this were not the case, that would open the encryption scheme to timing attacks — if ...


5

Bitslicing is a technique that allows multiple instructions/Data points to be encoded into a single register. The idea is that you encode several bitwise operations within a single register. So, instead of 32 bitwise OR operations in sequence, you could reduce the total number of operations by cramming the data into SIMD registers and executing in ...


5

Dedicated stream ciphers typically are, or at least can be, somewhat faster than constructions based on block ciphers. (If they weren't, there would be no point in using them, since a block cipher can do everything a dedicated stream cipher can.) What you gain in speed (and possibly code size), however, you lose in versatility: A block cipher (in CTR / ...


5

They measure it. Once upon a time, CPUs were simple enough that you really code compute the amount of time for a stretch of code by looking up the clocks per instruction in the manual, add them all together, and that'd be the total time. However, CPU manufacturers have added more and more optimizations and parallelism; this makes the CPUs run faster (for ...


5

A "general computer" simply doesn't exist, test for yourself with this command: openssl speed rsa As an example here is the output on a Mac Pro 2007 withIntel Xeon 5130: Doing 512 bit private rsa's for 10s: 67450 512 bit private RSA's in 9.95s Doing 512 bit public rsa's for 10s: 961891 512 bit public RSA's in 9.94s Doing 1024 bit private rsa's for 10s: ...


4

You should use AES. If you have the AES-NI instruction (which most modern chips have), then this performs very fast. For most applications today, AES-128 is certainly sufficient. However, I want to stress that it's not just the algorithm, it's also the mode of operation. You should use GCM. If you use OpenSSL then with AES-128-GCM you'll get speeds of about ...


4

Predicting speed by looking at the assembly is hard, especially since processors do all sorts of tricks which have memory (e.g. branch prediction). So yes, this is all about measuring. There is an art to it; for instance, you would rather repeatedly encrypt the same relatively small buffer (4 or 8 kB) so as to avoid cache effects. One method is to do the ...


4

Which PRG would be faster? A stream cipher (like AES in Counter Mode) or a Hash Function like SHA-1? While it is correct to say that it depends on the function, the practical answer is that stream ciphers, including AES in CTR mode, are usually faster at generating output than hash functions. In particular SHA-1. Hashes are quite fast at consuming ...


4

There is a lot of confusion in this question. Hash functions provide collision resistance. However, under a pretty reasonable assumption, they can be used to obtain a PRG or a PRF. Thus, hash functions and stream ciphers can be used to obtain a pseudorandom generator. This is true. (Although RC4 is broken and CANNOT be used for this purpose any more.) Now, ...


4

For encryption or decryption of data that is encrypted on the fly, you can do that. For data you store you obviously have to use the same decryption, so if you encrypt a huge file using AES, you have to decrypt it using AES, even when on battery power. First thing: If there is hardware support for AES, AES will be faster and using less power almost certain. ...


4

The performance bottleneck with RSA is the modular exponentiation operation. On the other hand, if you are interested in public key encryption performance, perhaps RSA is not the correct tool. RSA is actually fairly fast during its encryption operation; however it is quite slow during the decryption. If you care about decryption performance, you may want ...


4

Both curves have similar form and primes close to powers of two ($2^{192}-2^{64}-1$ and $2^{224} - 2^{96} + 1$), so you wouldn't expect large differences in performance – all things equal, P-224 might be anywhere from 30% to 60% slower due to the computational scaling of curve operations. However, in practice different implementations will have different ...


4

I think that there is no chance of getting such an asymmetric cipher simply because you forgot about science. The security on todays asymmetric cryptography is mostly based on the assumption that some mathematical algorithms cannot be reversed (e.g. the discrete logarithm or integer factorization). If mathematics solves this problems then the algorithm is ...


4

If you are using the full HKDF each time, you could possibly save time by only using the Extract portion once and Expand once per derived key. That could even halve the total time taken, if you had a worst case situation. Another speedup possibility within HKDF is to use another hash. Either a faster hash or one that matches the required key length better. ...


3

The very fastest elliptic curve algorithms can generate a key-pair in about 40k cycles on a modern CPU. A high end laptop has four cores running at about 3 GHz, so it can generate about 300k key-pairs per second, or a billion per hour. (The cost of SHA-256 is negligible in comparison.) However, secp256k1 is nowhere near the fastest curve. It takes 10 times ...


3

In principle, it is theoretically possible to calculate the time it takes a machine to run some known algorithm. It used to be fairly commonplace, but there are apparently very few people who have ever done it -- the sorts of things that used to require isochronous code are now-a-days generally done in other ways. In practice, it's generally simpler and ...


3

If you need a 32 bit PRP, might I suggest the Speck cipher? It isn't greatly secure (with a 32 bit block size, the only option is a 64 bit key, which isn't great), however it's extremely fast.



Only top voted, non community-wiki answers of a minimum length are eligible