260 views

Skip to first unread message

Apr 2, 2009, 5:27:24 PM4/2/09

to crypto-op...@googlegroups.com, Jeffrey Walton

This note describes a technique for computing GCM using 2KB of memory for

each key, which I haven't seen before in the literature or in published

code. The source code is available in C++ and SSE2 inline assembly, at

http://cryptopp.svn.sourceforge.net/viewvc/cryptopp/trunk/c5/gcm.cpp?revision=457&view=markup,

line 253. Speed seems to be within 1 cpb of the "simple, 4-bit tables

method" that uses 8KB of memory for each key, and within a factor of 2

(counting just the GMAC part of GCM) of the "simple, 8-bit tables method"

that uses 64KB of memory for each key.

each key, which I haven't seen before in the literature or in published

code. The source code is available in C++ and SSE2 inline assembly, at

http://cryptopp.svn.sourceforge.net/viewvc/cryptopp/trunk/c5/gcm.cpp?revision=457&view=markup,

line 253. Speed seems to be within 1 cpb of the "simple, 4-bit tables

method" that uses 8KB of memory for each key, and within a factor of 2

(counting just the GMAC part of GCM) of the "simple, 8-bit tables method"

that uses 64KB of memory for each key.

In the "simple, 4-bit tables method", the following algorithm is used (see

page 11 of http://www.cryptobarn.com/papers/gcm-spec.pdf for notation) to

compute X * H, with x_i being a 4-bit piece of X, and x_i * H * P^4i being

done with a table lookup using x_i as the index. It needs 32 tables since

there are 32 possibilities for P^4i.

Z = 0

for i = 0 to 31

Z = Z + x_i * H * P^4i

end for

return Z

My algorithm is this, with x_i the same as above.

Z_0 = Z_1 = Z_2 = Z_3 = 0

for i = 0 to 3

for j = 0 to 3

Z_j = Z_j + x_(32i+8j) * H * P^32i

Z_j = Z_j + x_(32i+8j+4) * H * P^(32i+4)

end for

end for

return ((((Z_3 * P^8) + Z_2) * P^8) + Z_1) * P^8 + Z_0

There are four P^32i and four P^(32i+4), so 8 tables are needed per key. The

last step is done using a shared table of 512 bytes, similar to Shoup's

method.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu