[14053] in cryptography@c2.net mail archive
Re: cryptographic ergodic sequence generators?
daemon@ATHENA.MIT.EDU (Tim Dierks)
Sun Sep 7 00:04:31 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sat, 06 Sep 2003 20:59:20 -0400
From: Tim Dierks <tim@dierks.org>
To: cryptography@metzdowd.com
In-Reply-To: <87ptidwmss.fsf@snark.piermont.com>
At 06:54 PM 9/6/2003, Perry E. Metzger wrote:
>Tim Dierks <tim@dierks.org> writes:
> > I'm sure that it would be possible to design a Feistel-based block
> > cipher with variable block size, supporting some range of even values
> > of n.
>
>Perhaps -- I don't know of a good one.
I'm not a cryptographer, so I can only make a tentative proposal, but I
believe you could make use of any secure keyed one-way function as the
function f() in a 2-round Feistel cipher and end up with a secure
construction. For example, let's use DES.
Let's say we wanted a 16-bit block cipher. Then f() must take a round # and
a 8-bit input and translate it into an 8-bit output. It doesn't have to be
a unique or reversible mapping.
Using DES, we could lay out the plaintext block as:
round # | input
with the round # in the first 32 bits and the input in the last 32 bits
(padded with zero bits), then encrypt and take the low byte of the output
as the output of f().
Thus, to encrypt a 16-bit block:
- Divide it into 2 halves, L0 & R0
- L1 = R0
- R1 = L0 ^ DES(1 | R0)
- L2 = R1
- R2 = L1 ^ DES(1 | R1)
Output = R2 | L2
This will take two DES operations per iteration, so it's not super-speedy,
but it's pretty fast for most operations. It's reversible, so you know it
will generate all values. And the construction works for any even-length
value of n. If you want, you can probably use a faster function for f(),
depending on your security requirements.
Here's a simple Perl script I wrote just to make sure I had it right:
use Crypt::DES;
$n = shift @ARGV;
if (!defined($n) || $n < 2 || $n % 2 != 0 || $n > 32 || $#ARGV > 0) {
die "Usage: $0 n\n2 <= n <= 32 && n even\n";
}
$key = pack("A8", rand());
$cipher = new Crypt::DES $key;
$hn = $n/2;
$fmask = (1 << ($n/2)) - 1;
sub f($$) {
my ($round, $v) = @_;
my $pt = pack("LL", $round, $v);
my $ct = $cipher->encrypt($pt);
my ($high, $low) = unpack("LL", $ct);
return $low & $fmask;
}
sub E($) {
my ($p) = @_;
my $L = $p >> $hn;
my $R = $p & $fmask;
my $round;
for $round (1..2) {
$Ln = $R;
$Rn = $L ^ f($r, $R);
$L = $Ln;
$R = $Rn;
}
return ($R << $hn) | $L;
}
foreach $v (0..(1<<$n)-1) {
$o = E($v);
print "$v => $o\n";
if ($o >= 1<<$n) {
die "Too big";
}
if ($retvals{$o}++) {
die "Duplicate";
}
}
This takes the length of the sequence in bits as a parameter.
This will take a while to run for any value of n much larger than 10 or so,
but I've tested it for up to n = 16 and it works fine: generates a random
ordering of the values 0..2^n-1.
- Tim
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
