Cryptography-Digest Digest #59, Volume #9 Tue, 9 Feb 99 09:13:03 EST
Contents:
Re: hardRandNumbGen (R. Knauer)
Re: RNG Product Feature Poll (Patrick Juola)
Re: help wanted please (Mok-Kong Shen)
Re: What is left to invent? (R. Knauer)
Re: hardRandNumbGen (R. Knauer)
Re: Rsa cryptology as a personal math project ([EMAIL PROTECTED])
Re: 2048-bit block cipher (Paul Crowley)
Re: Privacy, Traps and Frozen Hell (Paul Crowley)
Re: hardRandNumbGen (Patrick Juola)
Re: 2048-bit block cipher ([EMAIL PROTECTED])
Re: What is left to invent? (R. Knauer)
Re: What is left to invent? (R. Knauer)
Re: Questions about pseudoprimes, testing primes (mathematical) (Ernst G. Giessmann)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Tue, 09 Feb 1999 13:16:14 GMT
Reply-To: [EMAIL PROTECTED]
On 8 Feb 1999 08:49:11 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>The thing that really bothers me is that "good chance" part in your
>>statement above. If your tests are probabilistic with only a "good
>>chance" of being correct, then how can they be relied on?
>The "good chance" is quantifiable (as is the "fairly sure").
>What is your acceptable degree of uncertainty? What is your
>minimal "good chance."
I am not objecting to statistical measure per se. I could not do that
and still believe that Quantum Mechanics is correct.
My objections center on the fact that one cannot characterize the
randomness of a TRNG by measuring the statistical properties of the
numbers it generates. If that were the case, how do you explain what
happens when a PRNG passes such tests, and yet that PRNG is a poor
generator for crypto purposes.
The only way to get a "minimal good chance" of characterizing the TRNG
itself is to do a complete audit on it. That is what experimental
scientists have to do to have a "minimal good chance" of having their
experimental results accepted in the scientific community.
If as a scientist I proposed that the soundness of my experimental
equipment were determined by the output of that equipment, I would be
laughed out of science. Yet that is exactly what is being proposed
here - that the soundness of a TRNG be determined from its output.
>Remember that, according to modern physics, it's only probabilistic
>with a good chance that water will get hotter instead of colder
>when placed over a lit gas burner.
I certainly have no quarrel with statistical mechanics. I once
calculated the probability that all the molecules of air in a room
would end up in the corner. A bit on the small side, so small that it
would never have happened in the age of the Universe.
BTW, I can rig that experiment you describe above to make you think
the phenomenon is happening. I put water in the pot, create a
separation, put in another layer of water and freeze that top layer.
Then I put the thermometer at the bottom, and raise the temperature
just to the point where the ice is about to fall into the bottom. Then
I bring you in to observe how the temperature will decrease when I put
the pot on the stove.
You will only discover what is actually happening if you do a complete
audit of how I prepared the system. The same is true of a TRNG.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: RNG Product Feature Poll
Date: 8 Feb 1999 10:35:13 -0500
In article <79ms1g$[EMAIL PROTECTED]>,
Herman Rubin <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>Michael Sierchio <[EMAIL PROTECTED]> wrote:
>>"R. Knauer" wrote:
>
>>Knauer -- I think that you're either being disingenuous or stupid. Most
>>of your posts lead me to believe that you're intelligent, so I think
>>you're intentionally misconstruing the point.
>
>>> >Reasonable statistical properties are more than enough for cryptography,
>
>>> You will have to prove that assertion - I cannot take it on your word
>>> alone. In particular, I would have to see how indeterminancy comes
>>> from "reasonable statistical properties".
>
>>Herman will correct me, but statisticians regard a sequence of outcomes as
>>random if each outcome is independent of the previous ones. This is sufficient
>>for crypto, and explains why PNRGs are inadequate -- if you include choice of
>>initial conditions in "previous outcomes."
>
>Random is used in many ways. Many times this is assumed, but it is not
>necessarily the case. Sampling without replacement violated this assumption,
>and there are other models. Queuing models, birth and death processes,
>diffusion processes, and many others violate independence.
So what you're staying is that independence proves randomness, but
randomness does not necessarily proves randomness?
Seems reasonable to me.
-kitten
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: help wanted please
Date: Tue, 09 Feb 1999 12:37:43 +0100
Despontin M. wrote:
>
> Hi,
> I am currently preparing a paper concerning cryptography used for electronic
> banking. Does anybody know of a general survey that could help me out.
>
I suggest that you get some of the proceedings of a conference on
financial cryptography in the Lecture Notes on Computer Science
published by Springer-Verlag and see if there are literature references
to stuffs of the kind that exactly meets your need. A URL explaining
crypto techniques is e.g.
http://www.aci.net/kalliste/cryptnum.htm
M. K. Shen
http://www.stud.uni-muenchen.de/~mok-kong.shen/
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Tue, 09 Feb 1999 13:23:24 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 08 Feb 1999 18:05:09 -0600, Jim Felling
<[EMAIL PROTECTED]> wrote:
>Nope. PROOVE the coin is fair, and proove that you flip it in a "random
>manner".
Actually I do not believe that chaotic classical events can be proved
to be random in the sense of complete indeterminancy.
Only Quantum Mechanical phenomena can be proved to be completely
indeterminant.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Tue, 09 Feb 1999 13:20:57 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 09 Feb 1999 04:06:24 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>Even when characters have an overall "entropy" of less than a bit,
>there is no particular reason to expect to find the entropy
>concentrated in the LSB's. The LSB represents part of the coding; it
>has nothing to do with the entropy transported by the variation in
>usage of that coding.
I suppose the problem I am having is that if you include all the bits
of the text characters, you will be introducing bias into the stream.
If you use only the first 128 ASCII characters, the most significant
bit will always be 0, so there will be a bias towards more 0s than 1s.
Do you assume that some kind of anti-skewing procedure has been
employed prior to hashing the data? Or is anti-skewing even necessary
in what you are proposing? Does hashing remove bias?
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Rsa cryptology as a personal math project
Date: Tue, 09 Feb 1999 12:34:30 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (MarcusOman) wrote:
> Hello,
>
> I am studying in France as a somphmore and I have chosen to study cryptology,
> and more specifically the way Rsa works.
Hello Marcus,
please take a look at my study of RSA at
www.online.de/home/aernst/RSA.html
Regards
Alex
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: 2048-bit block cipher
Date: 9 Feb 1999 08:33:53 -0000
"Wm. Toldt" <[EMAIL PROTECTED]> writes:
> It is trivial to break your algorithm. If you want to know how, just ask.
I'm curious for one. If I understand his description properly (I went
looking for sample source and found assembly, though Alex seems
willing to fix this problem), then it should be possible to find the
fixed transposition with a chosen-ciphertext attack, after which
attacking the chaining is pretty trivial. Was that what you had in
mind?
It is also rather slow; it should really be at least ten times that
speed.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Privacy, Traps and Frozen Hell
Date: 9 Feb 1999 08:40:53 -0000
[EMAIL PROTECTED] writes:
> The example defines a hypotetical protocol called M-DES, which
> achieves an "effective" secret-key bit-length of 70-bits when viewed
> by Carol, even though the initial shared-secret between Bob and Alice
> was only one DES key with 56-bits. With +25% safety margin, the
> M-DES protocol forces Carol to cope with 70-bits of ignorance, which
> would force Carol to spend an expected number of
> (2^(69))*40/((60*24*30*12)*2^55) = 1.26 years to decode Bob's
> communication to Alice. While Alice faces 70 - 56 = 14 bits of
> ignorance and that takes her only (2^13)/(60*150) = 1 minute to
> solve.
What advantage does this offer over Schneier's "key stretching"
technique? I know that's primarily aimed at passphrases but the paper
mentions its applicability to 56-bit keys, and it seems to me to offer
better predictability (as well as better control over opponent's
resource needs) than your technique.
cheers,
--
__
\/ 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: 8 Feb 1999 10:42:38 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 8 Feb 1999 09:13:28 -0500, [EMAIL PROTECTED] (Herman Rubin)
>wrote:
>
>>>I am still having a problem relating this "deviation from randomness"
>>>you are testing for and the indeterminancy inherent in a TRNG. You are
>>>claiming that a property for infinite numbers applies to finite
>>>numbers, albeit with less than probability one.
>
>>There is a language problem, and it does cause confusion.
>
>Indeed!
>
>>ANY physical device producing bits is a TRNG,
>
>Not necessarily the kind of True Random Number Generator that produces
>proper sequences for the OTP cryptosystem.
>
>>in the sense that there
>>is a joint probability distribution of all the bits produced. It
>>does not follow from this that the probability that any k of the
>>bits form any particular k-element sequence is exactly 1/2^k.
>
>A TRNG has a specific definition - it must be capable of generating
>all possible finite sequences equiprobably. The best example of a TRNG
>is a fair coin toss.
>
>>Your generator, or any other physical generator, produces random
>>bits.
>
>Not necessarily the kind of random bits that a TRNG produces to
>satisfy the requirement above.
>
>>The question remains as to whether they have the particular
>>properties needed to use these bits as if they had the ideal
>>properties. It is THIS which is being tested.
>
>Here is the crux of the position I am maintaining. I agree that
>statistical tests can be used for diagnostic purposes to demonstrate
>that a RNG is not a TRNG to within a certain level of confidence. Even
>then you can reject a perfectly good TRNG if you do not subject it to
>a large number of tests. But that is not where the real danger lies -
>the worst is that you will reject properly working TRNGs.
>
>The danger comes about when you attempt to use statistical tests to
>demonstrate that a RNG is a crypto-grade TRNG. Even if a RNG passes
>your statistical tests, you still do not know if it is a properly
>working TRNG or not.
>
>Therefore the very thing you are testing the RNG for, namely its
>suitability for use with the OTP system, is not determinable. You
>might be able to determine that a RNG is not suitable, but you cannot
>determine that an RNG is suitable.
No. There are two things you need to do to produce a certifiable
TRNG.
One is to confirm that the device is, in fact, a "random number generator"
in the sense that it produces random bits. The main thing to confirm
then is that you can get an unbounded number of random (although not
necessarily equiprobable) bits out of the system. This requires
examination of the generator -- and is probably impossible unless
you're willing to make certain assumptions about various physical
processes such as radioactive decay or wave height or something.
The other is to confirm that the outputs are bias-free -- or more
accuratley as bias-free as possible, since there's no way to prove
ZERO bias. And this is best done statistically, although if you
really trust your engineers you can probably do it by design analysis
as well.
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 2048-bit block cipher
Date: Tue, 09 Feb 1999 12:41:16 GMT
In article <[EMAIL PROTECTED]>,
"Wm. Toldt" <[EMAIL PROTECTED]> wrote:
> It is trivial to break your algorithm. If you want to know how, just ask.
Dear Wn.Toldt,
It would be very nice of you if you can
expend your statement.
Thank you in advice.
Regards
Alex
============= 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: What is left to invent?
Date: Tue, 09 Feb 1999 13:38:12 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 09 Feb 1999 04:07:13 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>>> But there *is* *no* PROVABLY random source.
>>That's not so;
>That *is* so.
Radioactive decay can be proved to be random to within an arbitrarily
small error. This can be done by measurements on the indeterminancy of
the time of decay (half life measurements) and measurements of the
indeterminancy of the energy level of the excited state which produces
the decay (measurements of the Mossbauer Effect spectrum).
>There are techniques for *hopefully* "producing truly random bit
>streams." There are no techniques for producing PROVABLY random bit
>streams.
The statement above did not address random bit streams per se - it
addressed sources of true randomness.
>>For example, radioactive decay can
>>be used (with sufficient processing to ensure that any systematic
>>bias has been removed).
>And here, of course, we are to *assume* that "sufficient" processing
>has occurred. But assumption is not PROOF. Nor is the simple use of
>a supposedly random process
Radioactive decay is not "supposedly random" - it is proveably random
from Quantum Mechanics. I am talking about the decay process itself -
the actual source of randomness - not some particular measurement of
it.
>equivalent to PROVING that our machine has
>properly sensed that process, that there is no interference, and that
>we detect every event we should.
That is correct. The only way to know that the TRNG is operating
properly is to do a complete audit, including subsystem diagnostics.
IOW, you must treat the TRNG like any other piece of scientific
apparatus and prove it out the same way scientists prove out their
equipment.
>But the discussion was not about "pattern analysis," which would be
>"security in practice." The discussion was about ABSOLUTE PROOF of
>security due to a PROVABLY random source; this is simply not
>available.
I do not believe anyone is expecting "ABSOLUTE PROOF". But the fact
that we cannot ever achieve "ABSOLUTE PROOF" is no excuse to accept
poor measurement techniques.
Expecting to characterize the suitability of a RNG for the OTP system
by using its own output is folly. It is the same as expecting the
results of a scientific experiment to be the source of confidence that
the equipment was working properly.
The only time that will ever happen is with a Centurian Snake Oil
Generator.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Tue, 09 Feb 1999 13:44:59 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 09 Feb 1999 04:05:28 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>I would say not. But I would be glad to listen to what you consider a
>proof.
How can you prove the opposite - that it is not a TRNG? But I am not
really trying to defend a chaotic classical phenomenon like the coin
toss. I only believe that Quantum Mechanical processes are proveably
random.
To the ancients the weather looked completely random, yet it nowadays
it can be predicted reasonably well for a few days into the future.
But no one is ever going to predict in advance when a particular
radioisotope is going to decay.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (Ernst G. Giessmann)
Subject: Re: Questions about pseudoprimes, testing primes (mathematical)
Date: Tue, 09 Feb 1999 14:59:53 +0100
Benjamin Johnston schrieb:
> Hi,
> I'm a "newbie" to encryption, so excuse me if I'm asking a stupid question.
>
> I'm trying to find primes to use for encryption (using methods that I can
> sort of understand).
> What I've found out so far...
>
> All primes, p, should have the property that
> m^(p-1) mod p = 1
> for all 0<m<p, correct?
>
Yes.
>
> so if I have a number, n, which is not a prime (but I don't know that yet).
> and on my first test I find that (using 2 for this example),
> 2^(n-1) mod n =1,
> then n is said to be a pseudoprime (in this context), right?
pseudoprime to base 2
>
> What I would like to know is:
> 1. If know that n is a composite, and I find that 2^(n-1) mod n =1, does
> this tell me anything about n (eg. info about it's factors)?
you know that 2^(n-1) mod n = 1, about the factors of n,IMHO, you don't know
anything.
>
> 2. Given a composite number, n, can I determine all m where
> m^(n-1) mod n = 1.
m has the property, that the order k of m modulo p, where p is a prime divisor
of m, is a divisor of p-1
The order k is the min integer such that m^k=1 mod p.
All m with this property for all p are these you searching for.
>
> 3. If I am using the above test, to find verify primes with very high
> certainty, how many m should I try, and are there any rules for choosing an
> m that is most effective at proving that a number is not prime.
There are composite numbs, like 561, you can not filter out by this test.
> (does anybody know where I can find out mora about the Euler Totient
> Function (phi(n)), maybe even a proof that it works, or an explanation how
> it manages to work).
> Thanks
> -Benjamin Johnston [EMAIL PROTECTED] (no spam please)
Paulo Ribenboim: The book of prime number records.
Ernst
------------------------------
** 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
******************************
