Cryptography-Digest Digest #333, Volume #9 Sat, 3 Apr 99 14:13:04 EST
Contents:
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Software for breaking polyalphabetic substitution ciphers (mike)
Re: Is initial permutation in DES necessary? (John Savard)
Re: Random Walk (R. Knauer)
Re: Random Walk (R. Knauer)
RC4 CAN SOMEONE TELL ME IF THIS WILL WORK? (John Lawrence Singleton)
Re: Random Walk (R. Knauer)
Re: quick RSA key generation question ([EMAIL PROTECTED])
Re: Random Walk (R. Knauer)
is it true that Irish teen found crypto alg faster that RSA ("Nelson G. Rich")
New Hash Algorithim ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sat, 03 Apr 1999 17:11:39 GMT
Reply-To: [EMAIL PROTECTED]
On 3 Apr 1999 09:20:47 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>>Does this mean I have to be careful which "first-year book on
>>statistics" I read?
>There are lots of very bad first year books on statistics.
But Triola's book was recommended by one of the posters here. I don't
read books unless I get a qualified recommendation first. I do not
have the time or patience to read garbage.
>I suggest
>that one avoid all those which concentrate on statistical methods, and
>do not assume an understanding of probability.
Triola spends time developing elementary probability theory.
>BTW, also avoid those which assume that real data is normal.
Triola states the Central Limit Theorem (CLT) without proof and
without reservation. For example, he claims that the Law of the
Distribution of the Mean applies to samples taken from all
distributions.
>From my recollection of some 30 years ago, I recall that data
distributions must be square-integrable for the CLT to be valid. I can
imagine that there are other restrictions too, like the passage to
infinity to obtain the mean and variance of the data distribution.
Nevertheless, Triola does not restrict the CLT to just normal or
binomial sample spaces.
>Statistics requires probabilistic understanding, and to use it
>properly requires strong skepticism about assumptions.
Statistics also requires that you know the actual distribution of the
data so you can calculate the significance of sample means in terms of
supporting or rejecting the null hypothesis.
IOW, you must know with certainty the mean and variance of the actual
distribution for the data in order to calculate the significance of
samples taken to support or reject the null hypothesis. The Z-score
requires certain knowledge of both mu and sigma for the data
distribution. Furthermore, according to Triola, the mean and standard
deviation of the data distribution must be known for an infinitely
large population.
Can anyone give the distribution for a true randomness process? What
are its mean and standard deviation in the infinite limit? And does
the CLT apply for that distribution?
If you claim that pseudo-randomness is an adequate model in the sense
of a necessary condition for true randomness, then you need to prove
that because it cannot be accepted ad hoc - certainly not in light of
the truly random processes seen in quantum mechanics.
If you cannot give the actual distribution for a true random process,
or if you cannot model it with a pseudo-random process, then you
cannot claim that statistical tests have any validity in the
determination that a process is not truly random.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sat, 03 Apr 1999 17:19:17 GMT
Reply-To: [EMAIL PROTECTED]
On 3 Apr 1999 09:24:06 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>>Either I have a 1)defective TRNG that just fooled me on my examination or
>>2) a working TRNG that generated statistically unlikely output.
>>Given those are the only 2 possible hypothesis Occams razor would make me choose
>>hypothesis 1 and I therefore would kick out.
>There are an infinite number of hypotheses; the hypothesis that you
>have a TRNG is one which is essentially impossible.
A quantum computer is capable of generating true random numbers.
+++++
"Explorations In Quantum Computing" by Colin Williams and Scott
Clearwater", chapter 7 entitled "True Randomness":
"... a classical computer can only *pretend* to generate a random
number whereas a quantum computer can *actually* generate a random
number."
"... even when random number generators pass such statistical tests,
the sequence of numbers it generates may still not be random enough to
serve as an approximation to a true random process."
+++++
> Occam's razor is very definitely misused.
Is that statement proveable using Occam's Razor? :-)
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: mike <[EMAIL PROTECTED]>
Subject: Software for breaking polyalphabetic substitution ciphers
Date: Sat, 03 Apr 1999 17:22:25 GMT
Does any of you know where can I find some good software for breaking
polyalphabetic substitution ciphers. They are encrypted using a key and
Vigenere Tableaux.
Thanx
Mike
[EMAIL PROTECTED]
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is initial permutation in DES necessary?
Date: Sat, 03 Apr 1999 17:33:54 GMT
Paul Koning <[EMAIL PROTECTED]> wrote, in part:
>Perhaps "good enough for the time". But "stronger than anyone could
>have come up with"? Clearly not, because a system with the same
>properties but a civilized key size would have been better. And
>of course that was the original proposal; the key was shortened
>later on.
I keep hearing this - but I keep hearing this in different variations.
LUCIFER had a 128-bit block, a 128-bit key, and two S-boxes each with one
permutation of {0..15}.
DES had a 64-bit block, an effective 56-bit key, and eight S-boxes each
with four permutations of {0..15}.
I have heard it claimed that an early design of DES (_not_ LUCIFER) had a
longer key, but various acounts have given its length as either 64, 112, or
128 bits. Is this only an unverified anecdote, or did that early design
ever become public knowledge?
(I do remember reading an early comment, from one of the public key
inventors, that DES would have been (almost?) secure if it had a 64-bit
key, but throwing in parity bits was enough to make it breakable by the NSA
- this comment expressed a reasonable view that the parity bits *appeared*
to be something thrown in at the last minute: I'm beginning to wonder if
_that_ was the source of this rumor.)
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 03 Apr 1999 18:14:29 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 03 Apr 1999 10:58:09 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>To a large extent, *how* it works is understood.
That's what late 19th century physicists said, as the amused
themselves with calculating the dynamics of asymetric objects like
tops with little bumps on them, while the real physicts were concerned
with fundamental difficulties in classical physics, like the
non-Galilean invariance of Maxwell's equations, the failure of the
Dulong-Petit Law, the ultraviolet catastrophy, etc.
>The interesting question is *why* the world works that way.
Physics will never be able to answer that - you must study metaphysics
to obtain the answer. Godel's Theorem applies to physics just as much
as it applies to any other formal axiomatic system, including
mathematics (cf. Chaitin).
>It cannot be
>understood merely in terms of probability, and there is a real
>chance that the attempt to do so is causing us to miss something
>fundamental and unique.
I take that statement as prima facie evidence that you do not believe
that probabilistic measures are adequate to describe the truly random
aspects of quantum phenomena.
DUH! That's *exactly* what I have been saying all along, especially
with regard to the adequacy of statistical tests to characterize true
randomness.
>> Feynman misused mathematical terms; ...
>Maybe so, but it has no bearing on the matter at hand, which was
>simply a mention in passing that at least one famous Nobel
>laureate supported the idea of considering the 2-slit experiment
>as the testbed for understanding the issue of quantum randomness.
These days entanglement and the physics of information are all the
rage.The usual testbed for that is singlet particle emission. (The
term "singlet" refers to a two state system, like the spin of a photon
when measured along one axis in Hilbert space.)
>I thought, from past performance, that that might at least keep
>R. Knauer from pooh-poohing the notion, since he seems to like
>to cite experts.
I am not pooh-poohing any such notion.
Once again you are reading into what I say what you want it to say.
You are deliberately misinterpreting my statements to satisfy your own
agenda of coming off looking like an "expert". But most people know
that deliberately attacking a Devil's Advocate is a cheap shot.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 03 Apr 1999 18:17:17 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 03 Apr 1999 11:04:08 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Whatever passes for
>"probability" in QM is not isomorphic with the thing of the
>same name in standard probability theory.
DUH!
I suppose now you are prepared to join a growing consensus that
standard probabilistic measures such as statistical tests are not
suitable for characterizing true randomness as it is manifest in QM
processes.
It sure as hell took you long enough. <jeez>
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: John Lawrence Singleton <[EMAIL PROTECTED]>
Subject: RC4 CAN SOMEONE TELL ME IF THIS WILL WORK?
Date: Sat, 3 Apr 1999 13:25:37 -0500
CAN someone tell me if this will work? all i have it it doing as of now is
making the state.
/* This program is not finished yet-- all that works so far is the */
/* vector iniitalization and state preperation. The idea is to make*/
/* jcrypt under 20K when compiled -- the people that are going to use*/
/* this only have 5MB of space to work with so too large of a program */
/* is not useful. the END result is to intergrate this into PINE(email)*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
unsigned char state[256];
short counter;
int a,b,c;
main()
{
time_t t; /* declare some varibles */
int i;
int length_pass;
unsigned char pass[256];
int r[10];
char *p = pass;
int *q=r;
srand(time(&t));
printf("Enter your Passphrase\n");
scanf("%s" , pass);
length_pass=strlen(pass);
for(i=0 ; i < 10 ; i++) /* fill up the Vector */
{
r[i] = "0123456789"[rand() % 10];
}
printf("GENERATING INITLAIZATION VECTOR\n");
for( i=0 ; i < length_pass ; p++, i++) /*Find input point*/
printf("\n\n");
for(i=0 ; i< 10 ; i++ , p++ , q++) /* Combine Key to make initalzation
*/
{ *p = *q; /* VECTOR */
}
for(i=0 ; i < 20 ; i++)
printf("%c" , pass[i]);
length_pass=strlen(pass);
printf("\n\n\n\n%d" , length_pass);
for(counter=0 ; counter<256 ; counter++)
{
state[counter]=counter;
}
a=0;
b=0;
for(counter=0 ; counter < 256 ; counter++)
{
b=(pass[a] + state[counter])% 256; /* Add vector and state MOD 256
*/
state[counter]=b;
a=(a+1)% length_pass;
}
a=0;
b=0;
printf("What do you want to do??\n\n");
printf("Encrypt=1, Decode=2\n");
scanf("%d" , &c);
return 0;
}
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 03 Apr 1999 18:29:59 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 03 Apr 1999 11:06:22 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>If you build your "TRNG" exploiting quantum principles,
>then construct a UBP such as a random walk from its output,
>you will get the *same* "counterintuitive" features that
>you gleaned from Feller. It isn't a matter of quantum vs.
>classical, but rather of defective intuition.
I disagree with the last statement.
I believe that true randomness is a quantum phenomenon, and that
classical "randomness" is not true randomness but is a form of
pseudo-randomness. After all, in classical physics everything is
determinant, so classical processes cannot be truly random.
Classical physics relies on the ability to calculate an outcome with
reasonable certainty. IOW, it relies on computable numbers. But there
are an infinite count of uncomputable numbers between any two
computable numbers, so classical physics is excluding an infinite
count of different ways to determine a result.
Quantum physics does not claim to be able to determine all results. I
suspect that what is at work behind the scenes in a quantum process is
something involving uncomputable numbers. Of course, those numbers are
infinitely long, but so are computable numbers. Nevertheless, the
universe has a way of using them to determine the outcome of quantum
events.
But that is just my conjecture. Who am I to know anyway? After all, I
can't do that calculation on the back of an envelope, and it is not
intuitively obvious upon casual inspection, either.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: quick RSA key generation question
Date: Sat, 03 Apr 1999 17:36:35 GMT
In article <Pine.GSO.3.95qL.990402192601.19424B-
[EMAIL PROTECTED]>,
Fritz J Schneider <[EMAIL PROTECTED]> wrote:
> After generating a random p and q, is it standard practice to set
> the MSB of both p and q to 1 to ensure large values?
Huh? I don't understand what you are asking. The most signficant bit of
any number is always 1. And if you propose that you generate p and q such
that they have leading zeros then turn on the MSB, I simply note that that
action changes p and q.
What are you REALLY looking for?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 03 Apr 1999 17:58:55 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 03 Apr 1999 10:49:00 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>I cannot believe that you can consistently actually misunderstand
>simple statements.
Maybe I believe they are oversimplifications. You have displayed a
remarkable ability to oversimplify.
>But I was responding to your query about the impossibility of
>modeling such processes mathematically. So of course you
>change the subject.
Not change the subject - expand the subject. I told you I have several
interconnected themes going on here.
>Yes, I thought it was silly then, too.
That is a very smug comment. It shows how you cope with failure. Most
people cope with failure by laughing at themselves. You cope with
failure by laughing at other people.
I always got a kick out of theoretical physicists who would proclaim
that such and such a theorem could be "calculated on the back of an
envelope". So I started carrying an envelope and would pull it out
whenever some smug theorist would pull that nonsense.
Then there is the famous "intuitively obvious upon casual inspection".
Interestingly whenever people who used that expression had to write up
their work to submit it to peer review, they would take extensive
periods of time to do it. If it was so "intuitively obvious", it
should be easy to express. Apparently it wasn't so obvious after all.
>> The specification for a true random number generation that I have
>> been stating was distilled from the prevailing consensus of people
>> here. I did not make anything up. That specification is:
>I think that overstates it. I don't think it was anything like a
>"consensus of people here", just the ones who continued that thread.
Read my lips: I said ***PREVAILING*** consensus. <jeez>
I am convinced the reason you do not understand what I am saying is
that you do not read what I am saying. You look at the words and read
into them what you want to read into them, not what I obviously
intended with carefully chosen wording.
>> +++++
>> A true random number is one that is produced by a True Random Number
>> Generator (TRNG), which is a process that generates all possible
>> finite sequences equiprobably, namely in an independent and
>> equidistributed manner.
>> +++++
>A veeblefetzer number is one that is produced by a Veeblefetzer
>Generator (VG), which is a process that generates all possible
>finite sequences, although such a process is unrealizable, that
>have some property that is impossible to verify.
You have just invoked the Berry Paradox.
>How do I tell apart a TRNG and a VG?
Who says you should be able to? Who says you should be able to
describe true randomness in analytical terms?
>More importantly, the advantage of your "TRNG" definition over
>my "VG" definition is that the TRNG definition at least tries
>to spell out the *mathematical model* of the process.
Nowhere in the specification of a TRNG is there any explicit modeling
of the true random process. You are reading into that specification
the model for a pseudo-random process, which has the *appearance* of
meeting the specification.
Just because a true random process *looks* like a pseudo-random
process, does not make it a pseudo-random process.
>So, it makes sense to subject a supposed TRNG realization to
>tests to see whether it is in accordance with that model or not.
>If you're selling us a genuine TRNG(tm), what do you have to
>fear from the customers testing that it performs to spec?
>In particular, calling the customers "snake oil" purveyors
>just because they want to independently verify that *you're*
>not selling snake oil, seems most unwarranted.
That is the most convoluted piece of pure bullcrap I have seen around
here in at least 2 days. Now I know why PH.D. means Piled High and
Deep.
>> I am not interested in learning statistics.
>That is too bad, since you keep "dissing" statistics using
>incorrect argumentation.
I do not need to learn a subject to know it is wrong. I have never
learned astrology yet I know it is wrong. All you need to kow is that
the axioms are either wrong or they are not applicable. In effect, I
am not claiming that the axioms and premises of statisitics are wrong
- I know better than do that. I am, however, claiming that the axioms
and premises of statistical testing are not applicable to true
randomness with any reasonable certainty. They are applicable if you
are willing to accept the appearances of randomness, but if you want
true randomness you must look to other methods to certify that the
process meets the specifications.
>I was going to respond to the other
>dozen or so misstatements and misrepresentations in your
>posting (for example, repeating that the validity of the
>chi-square statistic requires some approach to an infinite
>limit), but it seems to have no effect toward educating you,
>and I suspect everyone else is bored with it.
You suspicions are wrong, as is evidenced by the repeated posting to
these threads. When people get bored, they will stop posting.
It is very smug of you to claim that others are bored just because you
can't make substantive contributions. Why not just bugger off? I can
tell you for a fact that you will not be missed by me, because in this
entire debate you haven't said one thing that is to the point. All you
have done is to use these threads as a forum for you to strut your
condescending bluster and pontification in front of everybody.
You claim this, and you claim that, and when challenged to provide
justification for your assertions, you hide behind more smugness to
cope with the fact that you have really never thought deeply about
these issues.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: "Nelson G. Rich" <[EMAIL PROTECTED]>
Subject: is it true that Irish teen found crypto alg faster that RSA
Date: Sat, 3 Apr 1999 12:14:53 -0500
Please excuse me for this if by now it's old hat, but is it true that a 16
year old Irish gal has found an algorithm that's faster than RSA?
Can anyone point me to accurate source?
Thanks.
------------------------------
From: [EMAIL PROTECTED]
Subject: New Hash Algorithim
Date: 3 Apr 1999 19:06:06 GMT
I've cooked up a little hash algorithim based on an unsuccesful attempt
to create a block cipher. It takes in variable-sized data in 192 bit
blocks and produces a 192 bit hash. If brute force is the best attack
(I'll bet it isn't) then 2^96 operations can crack it.
A few examples:
merlin:~$ echo "A" | ./hash
fe2fa108f42d7254450cba9d7fa835856b72a80c9ff29e53 -
merlin:~$ echo "B" | ./hash
786fff9154a8eb7efedc0ece9dcc321eaff1005d0329804e -
merlin:~$ echo "Congress shall make no law respecting the establishment
of a religion or prohibiting the free exercise thereof" | ./hash
e6faaa5a6f071120d0a2a1380380d7a960bc41252ec0ca59 -
merlin:~$ echo "Congress shall make a law respecting the establishment
of a religion or prohibiting the free exercise thereof" | ./hash # note the space
49907ad18e16163aeb88fdb0a631d17dd7b68c4acf592ea4 -
Here's 'C' source:
#include <stdio.h>
#include <string.h>
/* hmmm, names, names, names? PISH? probably insecure hash? naah, to negative */
int hashround( unsigned long b[6] )
{
int i,j,x;
unsigned long k[4] = {
0xABCDEF98,
0x98FEDCBA,
0x12345678,
0x87654321
};
for( j = 0; j < 4; j++ )
{
for( x = 0; x < 4; x++ )
{
k[x] += b[x] ^ k[0] + k[3] - k[0];
k[x] ^= b[6-x] ^ k[1] + k[2] - k[1];
k[x] -= b[x] ^ k[2] + k[1] - k[2];
k[x] |= ((b[x]^~b[6-x])^b[4-x]) ^ k[3] + k[0] - k[3];
}
b[7] ^= b[6] ^= b[5] ^= b[4] ^=
b[3] ^= b[2] ^= b[1] ^= b[0] ^=
(((k[j%4]^((k[j%4]^k[1]%16)^(k[(j+1)%4]^k[0]%k[1]))) ^
(k[(j-1)%4]))^((((k[0]|k[1])&k[2])+k[3])));
for( i = 0; i < 6; i++ )
{
b[i] += (k[0]^(k[3]^(~k[2])))-k[1];
b[(i+1)%8] -= (k[3]^(k[2]^(~k[1])))+k[0];
b[0] ^= ~(((k[3]^(k[0]+k[1])))^~(k[2]));
b[(i+1)%8] ^= ~(((k[2]^(k[1]+k[0])))^(~k[3]));
}
for( x = 0; x < 4; x++ )
{
b[0] ^= k[x];
b[0] += k[3-x];
b[0] -= k[x];
b[0] ^= ~k[x];
b[1] ^= ~k[x];
b[1] += ~k[3-x];
b[1] -= ~k[x];
b[0] ^= ~k[x];
b[2] += (k[x]|(~k[3-x]));
b[2] += ~(k[x]|(~k[3-x]));
k[2] ^= k[x]|k[3-x];
b[2] -= ((k[x]|(~k[3-x])));
b[3] ^= k[3-x];
b[3] -= k[3-x];
b[3] += ~k[x];
b[3] += k[x];
b[3] += k[3-x];
b[4] ^= k[x];
b[4] += k[3-x];
b[4] -= k[x];
b[4] ^= ~k[x];
b[5] ^= ~k[x];
b[5] += ~k[3-x];
b[5] -= ~k[x];
b[4] ^= ~k[x];
}
for( i = 0; i < 6; i++ )
{
b[i] ^= k[i%4];
b[i] ^= k[(3-(i%4))];
b[i] ^= ~k[i%4];
b[i] += k[i];
b[i] ^= (b[i+1]%8^k[i%4]^k[3-(i%4)]);
}
}
}
int main( int argc, char **argv )
{
int i;
unsigned long b[6]={0,0,0,0,0,0};
unsigned long bt[6]={0,0,0,0,0,0};
if(argc == 2)
{
freopen(argv[1],"r",stdin);
if(!stdin)
{
perror(argv[1]);
exit(1);
}
}
for(i=0;i<6;i++)
{
b[i] = i;
}
while(!feof(stdin))
{
for(i=0;i<6;i++)
{
b[i] = 0x00000000 ^ b[i+1%6] ^ 0xAAAAAAAA ^ b[i+2%6] ^
0xFFFFFFFF ^ b[i+3%6] ^ 0xF0F0F0F0 ^ b[i+4%6] ^
0x0F0F0F0F ^ b[i+5%6] ^ (b[i]^(b[i+1%6]|b[i]));
}
fread(&b,4,6,stdin);
hashround(b);
for(i=0;i<6;i++)
{
bt[i] += ~b[i];
bt[i] ^= b[i];
bt[i] -= ~b[i];
bt[i] += (b[i]|(~b[i+1%6]));
}
}
printf("%.8x%.8x%.8x%.8x%.8x%.8x\t%s\n",
b[0],b[1],b[2],b[3],b[4],b[5],(argc==2?argv[1]:"-"));
}
------------------------------
** 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
******************************
