a big expression
From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 02/26/04
- Next message: Richard Gallagher: "Re: Fast(est) factoring algorithm?"
- Previous message: Brian Gladman: "Re: 3DES and super-encryption"
- Next in thread: Mok-Kong Shen: "Re: a big expression"
- Reply: Mok-Kong Shen: "Re: a big expression"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 26 Feb 2004 11:29:28 GMT
I implemented AES in C++, Java, and Perl straight from the specification, so
that I would have a reference implementation that I *knew* would not have
any licensing problems at work and that didn't have a lot of extra stuff (we
are often concerned over download size, and most libraries come with a lot
of other stuff, and if we hack them up to just have what we want, we negate
one of the advantages of using someone else's library).
Since I went for clarity over speed, my implementations are not fast. For
example, here is the guts of my Perl version:
my @state = @_[0..15];
$state[$_] ^= $W[$_] for 0..15; # @W is the key schedule
foreach my $round (1..$Nr-1)
{
@state = map {$aes_S[$_]} @state;
@state[1,2,3,5,6,7,9,10,11,13,14,15] =
@state[5,10,15,9,14,3,13,2,7,1,6,11];
splice @state, 0, 4, aes_mixcolums(@state[0,1,2,3]);
splice @state, 4, 4, aes_mixcolums(@state[4,5,6,7]);
splice @state, 8, 4, aes_mixcolums(@state[8,9,10,11]);
splice @state, 12, 4, aes_mixcolums(@state[12,13,14,15]);
$state[$_] ^= $W[$_+16*$round] for 0..15;
}
This is my aes_mixcolumns function:
sub aes_mixcolums
{
my @in = @_;
my @out;
push @out, aes_fmul(2,$in[0]) ^ aes_fmul(3,$in[1]) ^ $in[2] ^ $in[3];
push @out, $in[0] ^ aes_fmul(2,$in[1]) ^ aes_fmul(3,$in[2]) ^ $in[3];
push @out, $in[0] ^ $in[1] ^ aes_fmul(2,$in[2]) ^ aes_fmul(3,$in[3]);
push @out, aes_fmul(3,$in[0]) ^ $in[1] ^ $in[2] ^ aes_fmul(2,$in[3]);
return @out;
}
My C++ version is similar. Thinking about how to optimize the C++ version,
it occured to me that I should make the aes_fmul function a table lookup,
and that I could build in the permutations, and unroll the loop, and change
it so alternate rounds bounce between two buffers.
Rather than figure that out by hand, it occured to me that since in Perl a
scalar can hold a number or a string, I could easily change my Perl code to
figure out an expression for each round instead of computing that round.
So, to get expressions for what one round does, with the input coming from
@in and the output going to @out, I can change the mainloop thusly:
So, the main loop becomes this:
$state[$_] = "in[$_]" for 0..15;
foreach my $round (1..$Nr-1)
{
@state = map {"S[$_]"} @state;
@state[1,2,3,5,6,7,9,10,11,13,14,15] =
@state[5,10,15,9,14,3,13,2,7,1,6,11];
splice @state, 0, 4, aes_mixcolums(@state[0,1,2,3]);
splice @state, 4, 4, aes_mixcolums(@state[4,5,6,7]);
splice @state, 8, 4, aes_mixcolums(@state[8,9,10,11]);
splice @state, 12, 4, aes_mixcolums(@state[12,13,14,15]);
$state[$_] = "($state[$_])^W[$_+16*$round]" for 0..15;
if ( $round == 1)
{
print "After round $round:\n";
print $_, ": ", join( "\n", $state[$_] ), "\n" for 0..15;
last;
}
}
and aes_mixcolumns becomes this:
sub aes_mixcolums
{
my @in = @_;
my @out;
push @out, "(f2[$in[0]] ^ f3[$in[1]] ^ $in[2] ^ $in[3])";
push @out, "($in[0] ^ f2[$in[1]] ^ f3[$in[2]] ^ $in[3])";
push @out, "($in[0] ^ $in[1] ^ f2[$in[2]] ^ f3[$in[3]])";
push @out, "(f3[$in[0]] ^ $in[1] ^ $in[2] ^ f2[$in[3]])";
return @out;
}
That works pretty well, and gives this for one round:
After round 1:
out[0]=((f2[S[in[0]]] ^ f3[S[in[5]]] ^ S[in[10]] ^ S[in[15]]))^W[0+16*1]
out[1]=((S[in[0]] ^ f2[S[in[5]]] ^ f3[S[in[10]]] ^ S[in[15]]))^W[1+16*1]
out[2]=((S[in[0]] ^ S[in[5]] ^ f2[S[in[10]]] ^ f3[S[in[15]]]))^W[2+16*1]
out[3]=((f3[S[in[0]]] ^ S[in[5]] ^ S[in[10]] ^ f2[S[in[15]]]))^W[3+16*1]
out[4]=((f2[S[in[4]]] ^ f3[S[in[9]]] ^ S[in[14]] ^ S[in[3]]))^W[4+16*1]
out[5]=((S[in[4]] ^ f2[S[in[9]]] ^ f3[S[in[14]]] ^ S[in[3]]))^W[5+16*1]
out[6]=((S[in[4]] ^ S[in[9]] ^ f2[S[in[14]]] ^ f3[S[in[3]]]))^W[6+16*1]
out[7]=((f3[S[in[4]]] ^ S[in[9]] ^ S[in[14]] ^ f2[S[in[3]]]))^W[7+16*1]
out[8]=((f2[S[in[8]]] ^ f3[S[in[13]]] ^ S[in[2]] ^ S[in[7]]))^W[8+16*1]
out[9]=((S[in[8]] ^ f2[S[in[13]]] ^ f3[S[in[2]]] ^ S[in[7]]))^W[9+16*1]
out[10]=((S[in[8]] ^ S[in[13]] ^ f2[S[in[2]]] ^ f3[S[in[7]]]))^W[10+16*1]
out[11]=((f3[S[in[8]]] ^ S[in[13]] ^ S[in[2]] ^ f2[S[in[7]]]))^W[11+16*1]
out[12]=((f2[S[in[12]]] ^ f3[S[in[1]]] ^ S[in[6]] ^ S[in[11]]))^W[12+16*1]
out[13]=((S[in[12]] ^ f2[S[in[1]]] ^ f3[S[in[6]]] ^ S[in[11]]))^W[13+16*1]
out[14]=((S[in[12]] ^ S[in[1]] ^ f2[S[in[6]]] ^ f3[S[in[11]]]))^W[14+16*1]
out[15]=((f3[S[in[12]]] ^ S[in[1]] ^ S[in[6]] ^ f2[S[in[11]]]))^W[15+16*1]
It then occured to me to see what the expressions would look like if I let
it do all the rounds, instead of just one. That was amusing. The
expression for each byte is about 5 megabytes. I wonder if any compiler
would be able to handle that? :-)
-- --Tim Smith
- Next message: Richard Gallagher: "Re: Fast(est) factoring algorithm?"
- Previous message: Brian Gladman: "Re: 3DES and super-encryption"
- Next in thread: Mok-Kong Shen: "Re: a big expression"
- Reply: Mok-Kong Shen: "Re: a big expression"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
