Cryptography-Digest Digest #82, Volume #9 Mon, 15 Feb 99 15:13:06 EST
Contents:
Re: hardRandNumbGen (Patrick Juola)
Re: hardRandNumbGen (Patrick Juola)
Re: True Randomness ("hapticz")
Re: some hash questions (Vektor)
Re: Factoring Complex Numbers ("Wm. Toldt")
Re: hardRandNumbGen (R. Knauer)
Re: some hash questions ([EMAIL PROTECTED])
Re: True Randomness (Noah Paul)
Crack On-Line (Peter K.)
Re: Help! Cryptosystem needed. (Paul Crowley)
Re: hardRandNumbGen (Patrick Juola)
Really lousy random numbers (John Curtis)
Re: hardRandNumbGen (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 15 Feb 1999 09:18:14 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 11 Feb 1999 15:42:48 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>A TRNG must be capable of generating all possible finite sequences
>>>equiprobably. If it is biased, then is it not doing that. Anti-skewing
>>>procedures do not generate those sequences that under-representted
>>>because of the bias.
>
>>Um... This is simply incorrect. That's *exactly* what anti-skewing
>>procedures do.
>
>I would like to see how that is possible.
>
>>Think of it this way. Assume you have a biased, but independent, bit
>>source that generates 1s with probability p > 0.5. Consider two
>>successive bits, x, y.
>
>>The probability of getting the sequence 1, 0 is p * (1-p).
>>The probability of getting the sequence 0, 1 is (1-p) * p, which is
>>identical to the above.
>
>>So if you output a 1 bit when you see the pair 1,0 and a zero bit
>>when you see the pair 0,1 (and nothing otherwise), then you've
>>got a provably unbiased output stream -- the bias has been scrubbed
>>from the input -- by the technique of throwing away everyting that
>>*isn't* unbiased, broadly speaking.
>
>I believe that algorithm is attributed to Knuth.
Before that, it was attributed to Von Neumann. it's an old one.
>This all sounds good on the surface but I am not convinced at this
>point. For example, there are sequences from a TRNG that are heavily
>biased, like 111...1 and 000...0, yet the scheme above does not seem
>to be able to produce those sequences. Can that anti-skewing technique
>above generate all possible sequences including 111...1 and 000...0
>with their expected probability based on their length? Is so, please
>show us how.
Certainly. Remember that the symbol (1) is generated from a subsequence
of 10 (or 1110, 0010, etc... in fact, by any sequence of the form
[(00)+(11)*10]. So any sequence of the form [(00)+(11)*10]*
will "debiasify" into 11111...11...
As to proof that the expected probability is based on the length;
do it by case analysis and induction.
There are four cases for the first four bits; as expressed above :
>>The probability of getting the sequence 1, 0 is p * (1-p).
>>The probability of getting the sequence 0, 1 is (1-p) * p.
The probability of getting the sequence 1, 1 is p*p.
The probability of getting the sequence 0, 0 is (1-p)*(1-p).
Note : only the first two generate output.
Assume for induction that all (output) sequences of length K or less
are printed uniformly with probability proportional to their length.
(The base case of length zero sequences is, literally, trivial).
Assume for contradiction, wolog, that the sequence X1 is more
probable than the sequence X0. This means that it's more likely
that a 1 was printed than a 0. But *this*, in turn, means that
the sequence [(00)+(11)*10] was *generated* more probably than
the sequence [(00)+(11)*01]. The prefix probability is the same
in both cases, so the only possible source of such difference is
in the probability of generating 10 vs. 01. But by case analysis,
these probabilities are equal, hence the desired contraction is
obtained.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 15 Feb 1999 09:19:27 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 11 Feb 1999 15:42:48 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>A TRNG must be capable of generating all possible finite sequences
>>>equiprobably. If it is biased, then is it not doing that. Anti-skewing
>>>procedures do not generate those sequences that under-representted
>>>because of the bias.
>
>>Um... This is simply incorrect. That's *exactly* what anti-skewing
>>procedures do.
>>
>>Think of it this way. Assume you have a biased, but independent, bit
>>source that generates 1s with probability p > 0.5. Consider two
>>successive bits, x, y.
>>
>>The probability of getting the sequence 1, 0 is p * (1-p).
>>The probability of getting the sequence 0, 1 is (1-p) * p, which is
>>identical to the above.
>>
>>So if you output a 1 bit when you see the pair 1,0 and a zero bit
>>when you see the pair 0,1 (and nothing otherwise), then you've
>>got a provably unbiased output stream -- the bias has been scrubbed
>>from the input -- by the technique of throwing away everyting that
>>*isn't* unbiased, broadly speaking.
>
>I have a further objection to this method.
>
>If this method produced perfectly secure numbers, then it could be
>applied to the output of any PRNG to produce perfectly secure random
>numbers. But we know this is impossible in general.
No. This method produces perfectly unbiased numbers *IF* the
underlying bit sequence is independent. PRNGs, not being
independent, can't be improved by this.
-kitten
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: True Randomness
Date: Mon, 15 Feb 1999 09:55:29 -0500
hoo haaa+ACE- NSA, masturbation hmmm....
now that gets me thinking, how about a microscopic viewing device that
observes the flaggelating spermatozoa and creates a +ACI-random element+ACI- from
some aspect of their orientation as they thrash themselves to some death+ACE-
--
best regards
hapticz+AEA-email.msn.com
------------------------------
From: Vektor <"vektor_"@hotmail.com(orsoyouthink!)>
Subject: Re: some hash questions
Date: Mon, 15 Feb 1999 11:37:16 -0500
[EMAIL PROTECTED]
wrote:
>
> Get a real programming language. Or play with XOR's like the rest of the
> VB idiots.
>
this is certainly not the place for a language war, so if you want one,
join #visualbasic on efnet. we'll give you a run for your money (most of
us there program in both VB and C (also assembly/raw machine code for
the more experienced in the channel)), and most of the regulars are
proffesional programmers.
though vb doesnt lend itself well to encryption, C does. writing a
library of basic encryption functions in C for use in VB is a fairly
simple and straight forward task.
what i'm hoping to accomplish is a collection of powerful and easy to
use encryption routines that can be used in any programming language
(delphi,vb,c,etc.).
once this library is completed...'the rest of the vb idiots' will be
able to put together a professional looking, SECURE application, while
your still trying to debug your message loop.
My warmest regards to the nameless coward,
-Alex
------------------------------
From: "Wm. Toldt" <[EMAIL PROTECTED]>
Subject: Re: Factoring Complex Numbers
Date: Mon, 15 Feb 1999 09:19:55 -1000
Lee Winter wrote:
>
> [EMAIL PROTECTED] wrote:
>
> > In article <[EMAIL PROTECTED]>,
> > "Wm. Toldt" <[EMAIL PROTECTED]> wrote:
> > > Trevor Jackson, III wrote:
> > >
> > > > How do you feel about factoring complex numbers whose terms are
> > > > integral?
> > >
> > > (This was in thread "Re: Clarification on PGP. pls")
> > >
> > > I never tried that, but here is an example:
> >
> > stuff deleted...
> >
> > > I do not feel good about this problem. How would I
> > > factor 2380i-1884 or even know is a unique
> > > factorization exists?
> >
> > Because Q(i) has class number 1. Therefore factorization is unique.
> >
> > > Maybe there are
> > > several complex factors which give
> > > the same result.
> >
> > Nope. There is a unique way to factor every Gaussian integer (up to
> > multiplication by units, of course) into prime ideals. All ideals are
> > principal.
> >
> > And the factorization is (as) easy as factoring ordinary integers. Just
> > factor the norm.
>
> I interpret your statement to imply that, for cryptographic purposes, the
> concept reduces to that of existing ciphers based on integer factorization.
> Is my interpretation accurate?
Yes, but I am not bobs.
Still, there are polynomials without unique factorization. For example:
(x-a)(x-b) = x^2-(a+b)x = x(x-a-b)
Maybe there is a use for non-unique factorization Rings. A public key
could be formed by multiplying factors but not publishing the factors.
The result is published and it is used to encrypt. Unique decryption can
only be done if the factors are known. This concept is not fully
developed yet, so feel free to shoot it down, or make it work.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Mon, 15 Feb 1999 15:56:41 GMT
Reply-To: [EMAIL PROTECTED]
On 15 Feb 1999 09:19:27 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>No. This method produces perfectly unbiased numbers *IF* the
>underlying bit sequence is independent. PRNGs, not being
>independent, can't be improved by this.
Let me attempt to reiterate this and your earlier post.
If a RNG produces finite sequences independently, but they are not
equidistributed, then the Knuth method of anti-skewing will cause the
output to become equidistributed - which then brings the RNG into
compliance with the specifications for a TRNG.
Is that correct?
If so, then this should be part of the design of a TRNG. One advantage
is that if the output is shorted or pulled up, there will be no final
output since there will be no dibits of the kind 01 or 10. That means
that the TRNG will be self-diagnosing in that regard.
Bob Knauer
"Of all tyrannies, a tyranny exercised for the good of its victims may
be the most oppressive. It may be better to live under robber barons
than under omnipotent moral busybodies. The robber baron's cruelty may
sometimes sleep, his cupidity may at some point be satiated; but those
who torment us for our own good will torment us without end, for they
do so with the approval of their consciences."
--C.S. Lewis
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: some hash questions
Date: 15 Feb 1999 18:01:12 GMT
VB is a toy language. I don't know any intelligent people who haven't
stopped using BASIC at the onset of puberty.
>
> Re: some hash questions
>
> From: Vektor <"vektor_"@hotmail.com(orsoyouthink!)>
> Reply to: orsoyouthink!
> Date: Mon, 15 Feb 1999 11:37:16 -0500
> Newsgroups:
> sci.crypt
> Followup to: newsgroup(s)
> References:
> <7a8jmk$b6b$[EMAIL PROTECTED]>
>[EMAIL PROTECTED]
>wrote:
>>
>> Get a real programming language. Or play with XOR's like the rest of the
>> VB idiots.
>>
>
>this is certainly not the place for a language war, so if you want one,
>join #visualbasic on efnet. we'll give you a run for your money (most of
>us there program in both VB and C (also assembly/raw machine code for
>the more experienced in the channel)), and most of the regulars are
>proffesional programmers.
>
>though vb doesnt lend itself well to encryption, C does. writing a
>library of basic encryption functions in C for use in VB is a fairly
>simple and straight forward task.
>
>what i'm hoping to accomplish is a collection of powerful and easy to
>use encryption routines that can be used in any programming language
>(delphi,vb,c,etc.).
>
>once this library is completed...'the rest of the vb idiots' will be
>able to put together a professional looking, SECURE application, while
>your still trying to debug your message loop.
>
>My warmest regards to the nameless coward,
>-Alex
------------------------------
From: Noah Paul <[EMAIL PROTECTED]>
Subject: Re: True Randomness
Date: 15 Feb 1999 18:05:00 GMT
1. Tag half of the sperm.
2. If a tagged sperm reaches it's ... uh ... target, the bit is 1.
3. Otherwise it is 0.
>
>hoo haaa+ACE- NSA, masturbation hmmm....
>
>now that gets me thinking, how about a microscopic viewing device that
>observes the flaggelating spermatozoa and creates a +ACI-random element+ACI- fr
>om
>some aspect of their orientation as they thrash themselves to some death+ACE-
>
>--
>best regards
>hapticz+AEA-email.msn.com
------------------------------
From: [EMAIL PROTECTED] (Peter K.)
Subject: Crack On-Line
Reply-To: [EMAIL PROTECTED]
Date: Mon, 15 Feb 1999 17:59:37 GMT
Is there any computer readily available on-line to cracking (DES for
example)
Peet
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Help! Cryptosystem needed.
Date: 15 Feb 1999 12:04:17 -0000
Divon Lan <[EMAIL PROTECTED]> writes:
> 2) What symetric system should I choose (it must be non-patented,
> royalty-free and preferably (but not necessaraly) exportable):
> 3) What do suggest I use for a hash function - faster than MD5 (I don't
> care too much about collisions - and I think 64 bits is enough for me)?
Exportable and secure don't go together. The current speed
front-runner for both encryption and hashing is Joan Daemen and Craig
Clapp's Panama; you'd need two instances of the Panama state to do
both functions, unless there's a clever and secure way to make one do
double duty (alternating push and pull?). There's a sample
implementation of Panama on
http://www.esat.kuleuven.ac.be/%7Erijmen/daemen.html
hope this helps,
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 15 Feb 1999 13:11:35 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 15 Feb 1999 09:19:27 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>No. This method produces perfectly unbiased numbers *IF* the
>>underlying bit sequence is independent. PRNGs, not being
>>independent, can't be improved by this.
>
>Let me attempt to reiterate this and your earlier post.
>
>If a RNG produces finite sequences independently, but they are not
>equidistributed, then the Knuth method of anti-skewing will cause the
>output to become equidistributed - which then brings the RNG into
>compliance with the specifications for a TRNG.
>
>Is that correct?
Yes.
>If so, then this should be part of the design of a TRNG.
Not necessarily. This technique is sufficient but not necessary
for removing bias, and there may be other, more appropriate
techniques depending on your needs. For example, this technique
throws away approximately 1/2 of the generated bits, which means
that your random number generator needs to generate bits in excess
of twice the needed volume. This could rightly be objected to
as inefficient.
A further objection is that the number of bits that may need to
be generated and thrown away are unbounded, and as such this would
be inappropriate to use in a real-time system where response time
is required to be faster than a certain threshhold. In plain English,
I may be unwilling to wait several seconds before my RNG spits out
any data.
Furthermore, if you are sufficiently confident that your generator
is unbiased, such a technique is redundant.
So this is an engineering question, and not a formal requirement.
-kitten
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Subject: Really lousy random numbers
Date: 15 Feb 1999 19:42:08 GMT
O.K. please entertain this rather naive question:
Let posit that a TRNG exists, that outputs a perfect
16 bit random number every 50 microsecs.
Unfortunately, the TRNG is less than perfect, and
a sinusoidal signal with a period of 16.6666 millisecs appears
additively mixed in with the perfect 16 bit random numbers at a
signal level such that the spurious signal toggles bit 4
of the TRNG at its peak.
If one were to employ this badTRNG to encrypt an English
ASCII message via OTP how much of the clear text is recoverable?
Does gathering more cipher text increase the proportion of clear
text that is recovered?
Is there some way of quantifying the probability that the
recovered text will contain a significant amount of
information? (for example, is there a significant probablility
that 5 contiguous characters are recovered?).
Thanks. I'm interested in how serious cryptographers approach
this issue, so please indulge me.
regards,
jcurtis
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Mon, 15 Feb 1999 20:03:47 GMT
Reply-To: [EMAIL PROTECTED]
On 15 Feb 1999 13:11:35 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>Not necessarily. This technique is sufficient but not necessary
>for removing bias, and there may be other, more appropriate
>techniques depending on your needs. For example, this technique
>throws away approximately 1/2 of the generated bits, which means
>that your random number generator needs to generate bits in excess
>of twice the needed volume. This could rightly be objected to
>as inefficient.
>A further objection is that the number of bits that may need to
>be generated and thrown away are unbounded, and as such this would
>be inappropriate to use in a real-time system where response time
>is required to be faster than a certain threshhold. In plain English,
>I may be unwilling to wait several seconds before my RNG spits out
>any data.
>Furthermore, if you are sufficiently confident that your generator
>is unbiased, such a technique is redundant.
>So this is an engineering question, and not a formal requirement.
Until another proveably secure anti-skewing technique can be
identified, it has the advantage that it works. And since this
discussion is mostly theoretical regarding the proveable security of
the OTP system, the fact that such a generator would not be useable
for a real time stream cipher is not relevant.
Regarding non-TRNG streams (such as text streams), one thing that I
forgot to ask when we were discussing decorrelation techniques is
whether those schemes proposed, such as CRC hash or the LZ77
compression algorithm you suggested, also remove bias?
Do such decorrelation procedures also remove bias, or is it necessary
to run an anti-skewing technique on the stream? If so, should it be
run before or after the decorrelation procedure?
Bob Knauer
"Of all tyrannies, a tyranny exercised for the good of its victims may
be the most oppressive. It may be better to live under robber barons
than under omnipotent moral busybodies. The robber baron's cruelty may
sometimes sleep, his cupidity may at some point be satiated; but those
who torment us for our own good will torment us without end, for they
do so with the approval of their consciences."
--C.S. Lewis
------------------------------
** 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
******************************
