Parallel Encryption Revisited

[Robert J. Hansen]

On 2/3/2012 4:22 PM, Yushu Yao wrote:
> http://lists.gnupg.org/pipermail/gnupg-devel/2007-February/023654.html

The overriding concern you were presented with five years ago is still
valid today: there are almost no opportunities for parallelization in
CFB encryption modes, such as the weird CFB64 mode used by OpenPGP.

Parallelization works well when the problem is composed of independent
subproblems.  For instance, the Merge Sort algorithm works by sorting
the first half of a list and the second half of a list, then splicing
together those two sorted sublists.  The individual halves may be
processed independently by different threads, but the joining is purely
sequential.  This is why Merge Sort is so parallelizable (the expensive
part is made of independent subproblems) and why it has limits to
parallelization (the sequential part cannot be parallelized).

In CFB mode, encrypting block N is dependent on the encryption of block
N-1.  This dependency chain keeps it from being composed of independent
subproblems, which makes it hard to find opportunities to exploit
parallelization.

In short, this is a dog that just won't hunt.  If parallelized
encryption is important to you, I'd suggest arguing for a change to the
OpenPGP RFC.