Cryptography-Digest Digest #207, Volume #9 Tue, 9 Mar 99 13:13:04 EST
Contents:
Re: Testing Algorithms (David Miller)
Re: Are there free RSA Software lib's ? (Paul Crowley)
Re: Cyclotomic Number Generators (Nick Battle)
Re: RC4 and keysizes (and Legal info on RC4/5/6) ("jay")
Re: Random Generator (Dworkin of Amber)
Re: DIE HARD and Crypto Grade RNGs. (Jim Gillogly)
Really Nonlinear Cipher Idea (John Savard)
Re: Limitations of testing / filtering hardware RNG's (R. Knauer)
Re: DES => problems with decryption - des.h (0/1) (Moh)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Miller)
Subject: Re: Testing Algorithms
Date: Tue, 09 Mar 1999 17:39:16 GMT
Herman Rubin ([EMAIL PROTECTED]) wrote:
: In article <7bm5lm$17k$[EMAIL PROTECTED]>,
: Patrick Juola <[EMAIL PROTECTED]> wrote:
: >In article <[EMAIL PROTECTED]>,
: >Shawn Willden <[EMAIL PROTECTED]> wrote:
: >>Withheld wrote:
:
: >>> In article <[EMAIL PROTECTED]>, Darren New
: >>> <[EMAIL PROTECTED]> writes
:
: ................
:
: >>You should take a look at the section in Schneier's book on thermodynamic
: >>limitations to brute-force attacks. He assumes an ideal computer, one in
: >>which the energy required to change the value of one bit in the processor is
: >>the smallest possible -- namely the quantum unit.
:
: >And, has been REPEATEDLY pointed out in this forum, he gets this
: >dead wrong as the smallest possible unit of energy for computing is
: >zero if you use reversible computations and get it back.
:
: One might be able to use reversible COMPUTATIONS, but they will
: not get the energy back. A device capable of maintaining a bit
: requires some sort of a hysteresis loop to keep the bit from
: drifting uncontrollably. The second law intrudes.
Doesn't the reversibility require the storage of state? IE, wouldn't
zero energy counting to 2^256 require a minimum of 2^256 bits of
storage? I've seen varying stats, but IIRC all of them put the number
of atoms in the universe well below this.
--- David
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Are there free RSA Software lib's ?
Date: 9 Mar 1999 14:33:33 -0000
Rosenegger Josef <[EMAIL PROTECTED]> writes:
> i've to implement data encryption (Public-Key cryptography) in our
> companies software.
>
> I'm going to use RSA cryptography. Question is, are the RSA sources
> free for companies usage?
If you're worried about this one you're almost certainly wiser using a
system such as ElGamal which is free from patent encumberance. It's
described in Applied Cryptography.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
Date: Tue, 09 Mar 1999 17:28:30 +0000
From: Nick Battle <[EMAIL PROTECTED]>
Subject: Re: Cyclotomic Number Generators
"R. Knauer" wrote:
> Would you all please discuss cyclotomic number generators, in
> particular the class of order 2.
What... *all* of us!? :)
-nick
------------------------------
From: "jay" <[EMAIL PROTECTED]>
Subject: Re: RC4 and keysizes (and Legal info on RC4/5/6)
Date: 9 Mar 1999 17:42:01 GMT
[EMAIL PROTECTED] wrote in article
<7c3k7a$l1l$[EMAIL PROTECTED]>...
>
> A session key is the expand user key. i.e a rc4_key which has 256!
> combinations.
>
If the user key contains repeats, the session key will as well, so I would
still believe that the correct value is 256^256.
jay
------------------------------
From: [EMAIL PROTECTED] (Dworkin of Amber)
Subject: Re: Random Generator
Date: Tue, 9 Mar 1999 12:53:13 -0500
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Does anyone here know a good way of generating (pseudo) random numbers?
> C++ has a random generator but I'd like something better than that one.
>
> Thanks for any help,
> Gerben Dirksen
>
>
Start of Anti-flame-retardant.
NOTE--- THIS ALGORITHM IS NOT CRYPTO GRADE RNG. The poster did not ask
for crypto grade rng. I personally don't have a crypto grade rng. I
found this algorithm some time ago, and liked it as it is much better
than the default rng provided by IBM/INTEL/MS. If you find it useful,
fine. If not, please don't flame me.
End of Anti-flame-retardant.
/*
*------------------------------------------------------------------------
=====
* file: random.c
* desc: routine for a very-long-cycle random-number
sequences
* by: patrick ko shu pui
* date: 6 sep 1991
* comment:
*
* this random number generator was proved to generate random
sequences
* between 0 to 1 which if 100 numbers were calculated every second,
it
* would NOT repeat itself for over 220 years.
*
* reference:
*
* Wichmann B.A. and I.D. Hill. "Building A Random Number Generator."
* Byte Magazine. March 1987. pp.127.
*
* remark: this C routine is a freeware
*
* [EMAIL PROTECTED] Internet
* BiG Programming Club (since 1987), Hong Kong, 6:700/132 FidoNet
* [852] 654-8751
*------------------------------------------------------------------------
=====
*/
#include <time.h>
#include <values.h>
#include "random.h"
#define REAL double
#define INT int
/*
* default seed values
*/
static INT x = 1;
static INT y = 10000;
static INT z = 3000;
/*
*========================================================================
=====
* funct: rndmize
* dscpt: generating random number seeds
* given: nothing
* retrn: nothing
*========================================================================
=====
*/
INT rndmize()
{
time_t timer;
x = time( &timer ) % MAXINT;
y = (x * x) % MAXINT;
z = (y * y) % MAXINT;
}
/*
*========================================================================
=====
* funct: rnd
* dscpt: return a random number of range 0-1
* given: nothing
* retrn: the random number
* cmmnt: you may use prandomize to change the seeds
*========================================================================
=====
*/
REAL rnd()
{
REAL temp;
/*
* first generator
*/
x = 171 * (x % 177) - 2 * (x / 177);
if (x < 0)
{
x += 30269;
}
/*
* second generator
*/
y = 172 * (y % 176) - 35 * (y / 176);
if (y < 0)
{
y += 30307;
}
/*
* third generator
*/
z = 170 * (z % 178) - 63 * (z / 178);
if (z < 0)
{
z += 30323;
}
/*
* combine to give function value
*/
temp = x/30269.0 + y/30307.0 + z/30323.0;
return (temp - (INT)temp);
}
/*
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*
* * * E X A M P L E
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*
*/
/*
int main()
{
int i;
rndmize();
for (i=0; i<100; i++)
{
printf("%f,", rnd() );
}
}
*/
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: DIE HARD and Crypto Grade RNGs.
Date: Tue, 09 Mar 1999 08:40:40 -0800
R. Knauer wrote:
> On Mon, 08 Mar 1999 17:51:39 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>
> >> OK, then try that with an expansion of pi (to any base).
> >> Bet it won't compress worth squat.
>
> >Well, OK, just to test our intuitions and my compression
> >estimates I went ahead and did it for 1,254,540 decimal
> >places. Gzip compressed it by 52.9% (my "random" samples
> >gave 53.0% each), and my 3|4-bit Huffman code compressed
> >it by 57.505% (vs. my theoretical estimate of 57.5%).
>
> Would you expand on all this please - it sounds quite interesting.
> Where did you get the 1,254,540 decimal expansion of pi?
http://www.cs.williams.edu/~bailey/pi.html
> What is the significance of being able to compress pi by that much?
The significance is that pi expressed as ascii decimal digits can't
be compressed either by gzip or a 3|4-bit Huffman code more than you
would expect for any random set of ascii decimal digits. That is,
the compression algorithms don't find anything worth compressing.
Since the distribution of digits isn't exactly even for any truncation
of pi, one can pick the 3-bit codes for the higher frequency ones and
the 4-bit codes for lower frequency ones, getting a very slightly
higher rate of compression than one would get with an even distribution.
For example, picking digits 6, 1, 8, and 4 for the 4-bit codes gives
a compression of 57.511% instead of 57.505% for the "standard"
assignment. With another 10 million digits or so the optimal assignment
would probably be different, and still a very little better than 57.5%.
>> Is the actual compression of pi itself a true random number, since it
> cannot itself be compressed any further?
Uh. No. The best possible compression is a constant for any
subset of pi, if you consider the sum of the size of the compressed
stream and the program that generates it, and would be highly
correlated for increasing subsets. The best compression
algorithm for pi would be a program that generates its digits...
i.e. the usual algorithms for calculating pi.
> >As expected, pi in decimal isn't compressible this way,
>
> I am a bit confused by that statement. In the first paragraph you said
> that you were able to compress pi and now you seem to be saying you
> could not. Obviously I am missing something, so please explain.
I compressed a file of pi represented as ASCII digits 0x30 to 0x39.
Since each digit represents 3.something bits of information, the ASCII
representation is inefficient. The most efficient representation
of individual digits will thus be less than half the size of the
same digits represented as ASCII. I calculated that this representation
results in 57.5% compression of random ASCII digits using a Huffman code
to represent them, and established that this is very close to what can
be achieved for a million digits of pi using per-character codes. I
also established that gzip, which looks for repeated strings as well
as Huffman coding the rest, does no better on pi than on random digits.
Executive summary: general compression algorithms don't compress pi
any more than they compress random digits.
Hope this is clearer.
--
Jim Gillogly
Sterday, 17 Rethe S.R. 1999, 15:04
12.19.6.0.2, 10 Ik 15 Kayab, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Really Nonlinear Cipher Idea
Date: Tue, 09 Mar 1999 16:39:31 GMT
I'm always looking for simple ways to make a block cipher nonlinear. I've
come up with a really extreme one.
Let us take a typical DES-like Feistel cipher, acting on a 64-bit block.
Now, let us build a block cipher for a 128-bit block.
Here is my really weird idea:
One half of the block goes through 16 rounds of the ordinary Feistel
cipher. This process produces 16 intermediate f-function values, each 32
bits wide.
We then encipher the other half of the block for two or more rounds. It is
divided into halves. Each round involves the eight nibbles of one half of
the 64-bit half selecting an entry from an S-box with 16 32-bit entries.
Since we only have one S-box, they're rotated one bit before the next one
is XORed to create the f-function value.
Oh, yes: what was that S-box? It was composed of the 16 f-function values
produced when enciphering the other half of the block.
A *data-dependent* S-box.
Almost (there's Terry Ritter's autokey Dynamic Substitution, for example) a
new frontier in cryptography! If key-dependent S-boxes create high
security, it would seem that one which is even data-dependent as well would
truly produce a cipher that defies analysis.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Limitations of testing / filtering hardware RNG's
Date: Tue, 09 Mar 1999 16:52:30 GMT
Reply-To: [EMAIL PROTECTED]
On 9 Mar 1999 16:05:24 GMT, [EMAIL PROTECTED] (Mark Currie) wrote:
>Any electronic circuit used as a hardware RNG should be tested before use,
>firstly in the diagnostic sense, to prevent usage in case of failure. Secondly,
>to prevent the use of "bad" values. Even a TRNG, as you mentioned earlier, can
>produce long runs of 1's or 0's. These values may not be tolerated in certain
>applications. These are non-ideal, practical, real world problems. The question
>is how much can be tolerated.
Here is the problem as I see it. A uniform Bernoulli process (e.g., a
fair coin toss) can produce long runs of one particular bit and still
result in an asymptotic frequency of 1/2 for that bit. So, when your
turn the TRNG on, it could just as well begin doing just that as begin
outputing any other equiprobable sequence.
Consider a physical analog (not perfect, so don't gripe about it, OK).
Take a radioactive tracer and put it in one small spot in the center
of a piece of metal and heat the metal near its melting point. After
it has cooked for a while section the sample and measure the
readioactive decay of each section, obtaining a diffusion profile of
tracer atoms which have migrated throughout the sample. If you want to
do this in one dimension, use a thin long whisker of metal.
If you heat the sample long enough you will generate lots of very long
random walk sequences and you will find that the tracer atoms
distribute themselves somewhat uniformly throughout the sample.
What that means is that a significant number of tracer atoms went on
random walks that had a high degree of bias (use the one dimensional
case to illustrate that) - that is, they ended up at a considerable
distance from the starting point in the center. IOW, any one tracer
has a significant chance of having a highly biased walk sequence.
If you use that tracer's walk to test the overall behavior of the
sample, it will fail the statistical tests for bias, because it alone
is not representative of the overall diffusion process.
The same can be said of using one given output sequence from a TRNG -
it is only one possible sequence and is not representative of the
overall TRNG process. In order to characterize the TRNG correctly you
would have to analyze all (or nearly all) of the sequences it can
output, and that is clearly impossible.
Bob Knauer
"There's no way to rule innocent men. The only power any government
has is the power to crack down on criminals. Well, when there aren't
enough criminals, one makes them. One declares so many things to be
a crime that it becomes impossible to live without breaking laws."
--Ayn Rand
------------------------------
From: [EMAIL PROTECTED] (Moh)
Subject: Re: DES => problems with decryption - des.h (0/1)
Date: Tue, 09 Mar 1999 16:53:31 GMT
Hi,
actually I read the code about 20 times, looked
for spelling mistakes and logic mistakes and much
more. I tested every function separately and all
seem to work.
Still the whole process does not function at all
and I am really desperate now :-(
In case I do not use the routines of p-box and
S-box things work fine, but then it is no more
des and secure!
All the permuation things shouldn't be the problem.
I have send my whole code here now and hope some-
one can take a look at it. It should be very self-explaning.
The way I implemented the DES algorithm might not
be the fastetst, but that's how I understood.
As the Permutation is nothing serious, it would
be very kind if you could especially take a look
at the functions:
char *des (char *source, int mode);
void des_sub (long *source_block, long *key, long *target_block, int
mode);
long substitution (long *data_block);
void shifting(long *key_block, int round);
In case I did a mistake and I surely did otherwise it would
work it *must* be in one of these four functions.
I know that this message is very rude because
asking someone to read the code is not the fine way.
I still hope someone can afford to take 10-15 min. to
read it.
Thank you a lot in advance, I didn't sleep the last
20 hours because of this code :-( ...and still I cannot
find the mistake.
Best regards
-Moh
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
