Cryptography-Digest Digest #107, Volume #9 Fri, 19 Feb 99 12:13:03 EST
Contents:
Craete short encryted string with PKE? ([EMAIL PROTECTED])
Where to publish hashes? (dan schwartz)
NSEA and Khufu ("jmp")
Re: Randomness based consciousness?. (Was: Re: *** Where Does The (David A Vivash)
Re: Bruce's Feb. "CRYPTO-GRAM"
Re: Randomness of coin flips (Patrick Juola)
Re: Randomness of coin flips (R. Knauer)
Re: Randomness of coin flips (R. Knauer)
Re: True Randomness (R. Knauer)
Re: Randomness based consciousness?. (Was: Re: *** Where Does The Randomness Come
From ?!? *** ) (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Craete short encryted string with PKE?
Date: Fri, 19 Feb 1999 12:36:05 +0100
Can I use public key encryption to encrypt a short string M (10-20
chars) to a short(!) string C?
The length of C should be about the length of M.
Encrypt(M,a) = C (a is the private key)
Decrypt(C,b) = M (b is the public key)
length(M) = length(C)
Can I use RSA or DSA (512 bit key length) to make the functions
Encrypt(M,a) and Decrypt(C,b)?
Thanks for your help!
Ron
------------------------------
From: [EMAIL PROTECTED] (dan schwartz)
Subject: Where to publish hashes?
Date: 19 Feb 1999 13:44:08 GMT
Let's say I want to publish a secure hash of a document, so I can
later prove that I possessed that document on or before the date
that the hash was published.
Any ideas for the best places to publish the hash? The publishing
method should have the following characteristics:
1 - Visible to the public.
2 - Not subject to manipulation after publication.
3 - Available for viewing for a long time after publication.
4 - Inexpensive.
5 - Convenient.
Placing an ad in a major newspaper satisfies 1 - 3, but probably
not 4 and 5. Is there a method that satisfies all of them?
Dan Schwartz
------------------------------
From: "jmp" <[EMAIL PROTECTED]>
Subject: NSEA and Khufu
Date: Fri, 19 Feb 1999 09:48:17 -0500
NSEA and Khufu
Does anybody know of a PRACTICAL attack that exploits a common feature of
these algorithms? (the fact that there are no subkeys, just key expansion
into S-boxes) Don't tell me about Related-key-Chosen-PlainText attacks.
jmp
------------------------------
From: David A Vivash <[EMAIL PROTECTED]>
Crossposted-To:
sci.skeptic,sci.philosophy.meta,sci.psychology.theory,alt.hypnosis,sci.logic
Subject: Re: Randomness based consciousness?. (Was: Re: *** Where Does The
Date: Fri, 19 Feb 1999 14:06:30 +0000
[EMAIL PROTECTED] wrote:
>
> Isn't random such a fantastic word?
>
> to me, it looks like ants run around 'randomly'
>
> when someone breaks in snooker - the balls shoot off 'randomly'
>
> I don't know where this idea of Random based conscioussness comes
> from, Random Consciousness is an oxymoron...
>
> Consciousness based on Chaos or complexity theory perhaps?
>
> OR, what i suspect, you are somehow referring to Quantum Theory - this
> may well be random in a sense.
>
> Consciosness needs this so called 'randomness' to exploit so it ca
> "have its way", or so to speak.
I really don't see that randomness can ever be considered a human
concept. Whilst there may be problems that we find hard to predict an
answer for (which we might very well call "random"), I believe there are
problems that do not have an answer in a particular system until the
answer has been found.
Okay, so that sounds quite meaningless (probably contradictory too).
Whilst we cannot predict what the next digit of Pi is, we can calculate
it, so this is not random.
But what if I were to ask you what card is on the top of the deck? This
seems like a causality: Event A(shuffling, say) causes event B(king of
spades on top of the deck, say). But... what about systems where event A
is "forgotten" ? Imagine te universe could somehow "forget" what had
happened in the past, and just give you any result because one is
required. I'm not really talking specifically about the universe here,
more generally ANY mathematical system has the potential to "forget"
event A. Consider, for example, the big bang. Event B happened (the big
bang) but event A (the cause of the big bang) has been forgotten since
time starts at event B.
I can see that any mathematical system that contains perfect information
can be used to solve all problems within that system. But it seems to me
that certain systems may not necessarily have all the information to
solve a problem, although the answer to the problem still lies within
the system. (That is, the lack of information is inherent in the design
of the system, rather than the case being that it's too difficult to
know all the necessary variables).
A further problem can arise though. Just as a system may forget event A,
there may be no defined mapping of Event A to Event B - not because we
don't know the mapping, but because one doesn't exist. Hence under some
circumstances Event A may cause Event B, but other times Event A might
cause Event C because no mapping exists. It is here we would find truly
random behaviour - the unpredictable or rather, the uncomputable.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Bruce's Feb. "CRYPTO-GRAM"
Date: 19 Feb 99 14:56:09 GMT
JPeschel ([EMAIL PROTECTED]) wrote:
: My, John, for a layman, you seem awfully
: smug about this.
: Even some of the best, except for you,
: of course, can be confused when trying to
: discern snake-oil from strong crypto.
I regret any offense I may have caused, but that was not at all my
intention. Some snake-oil _is_ obvious, even if one can never be truly
sure about what seem to be quality products.
I just thought that, as Bruce also "named names" of a sort a poor amateur
like myself had *absolutely no possibility* of divining through his own
unaided efforts, that this was ... even more exciting than what you had
mentioned. So I noted the omission. There was no more to it than that.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Randomness of coin flips
Date: 19 Feb 1999 08:31:21 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 18 Feb 1999 13:07:43 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>I fail to see how the regularity of having the "expected" amount of
>>>bias present is a measure of true randomness. It may be a measure of
>>>pseudo-randomness, but that is not appropriate to secure crypto.
>
>>It's not. But *failure* to have the expected amount of bias
>>present is almost certainly a measure -- and a mark -- of a lack of
>>randomness.
>
>I believe that only holds for strings that are a priori random
>according to those tests, which leads to a circular agrument. The
>reason for that is that you are insisting on using the term "almost
>certain". For other strings that are not a prioi random according to
>those tests (e.g., "regular" strings), that "almost certain" turns
>into a probability that is far from "almost certain".
But strings that aren't a priori random are agreed to not be random
to begin with.
Or, to put it another way -- give me a string and tell me whether
you think it's random.
If you don't think it's random, we can agree that it's not random
and we won't use it.
If you *do* think it's random and I can prove subtantial deviations
from the expectations of a runs test for randomness, then I can
reject your idea to any desired degree of (un)certainty.
So although we can't prove a string to be random, we can prove it
to be very probably not random.
-kitten
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Fri, 19 Feb 1999 15:55:16 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Feb 1999 01:30:13 -0500, Nicol So <[EMAIL PROTECTED]>
wrote:
>> >he will observe that the bigrams
>> >HH and/or TT tend to dominate over HT and TH. This means that
>> >he'll see longer than expected runs.
>> I fail to see how the regularity of having the "expected" amount of
>> bias present is a measure of true randomness. It may be a measure of
>> pseudo-randomness, but that is not appropriate to secure crypto.
>if my
>coin flips did display the anomaly he mentioned, then the results of my
>coin flips cannot be modeled as a series of unbiased, independent and
>identically distributed random variables. He was pointing out how a
>statistic on long sequences of coin flips will differ from the
>prediction of an incorrect mathematical model.
The Law Of Large Numbers, which is what is behind your assertion, does
not claim to be certain, or even "nearly certain" for finite runs. You
could experience skewed runs and still have a Uniform Bernoulli
Process (p=1/2).
>By the way, the term pseudorandomness has precise meaning in complexity
>theory, and cryptology. Your usage of the term is not consistent with
>that of theoretical computer scientists.
Oh really? That's strange, since I got it directly from Li & Vitanyi's
book on Kolmogorov Complexity.
It must be that these authors are not qualified as "theoretical
computer scientists". Actually they got the notion from Kolmogorov
himself, so I suppose that means he likewise is not a qualified
"theoretical computer scientist".
Thanks for warning us. BTW, you have read Li & Vitanyi's book, haven't
you?
>> So what? Again, you are using the term "expected", which is a
>> probabilistic concept. Probability only applies to pseudo-randomness,
>> not true randomness. (See Kolmogorov quote below).
>Your last comment is quite counter-intuitive. I suspect that your
>concept of "true randomness" is different from that of most other
>people.
The concept of True Randomness we are using here on sci.crypt comes
from crypto itself. A True Random Number is one that is produced by a
True Random Number Generator (TRNG), which is a process that is
capable of generating all possible finite sequences equiprobably.
Now kindly tell us exactly why that definition of true (crypto-grade)
randomness is so "different from that of most other people".
>If that's not the case, I disagree with the comment. In the
>quote below, which you attributed to Kolmogorov, nowhere did the terms
>"true randomness" and "pseudorandomness" appear. Are you sure you're
>interpreting it correctly?
The term "pseudo-randomness" as I used it here is defined in the
context of the discussion in Li & Vitany's book where the Kolmogorov
quote is contained.
>What do you mean by "pseudorandom tests"?
"Tests for pseudo-randomness".
>The way theoretical computer
>scientists use the term, pseudorandomness is not a property of "tests".
The term "pseudo-random test" can be correctly interpreted as "tests
for pseudo-randomness". IOW, it does not necessarily mean that the
tests themselves have the property of pseudo-randomness.
>> The goal of secure crypto is to prevent a crypanalyst from being able
>> to determine (predict) your messages from the ciphers. That requires
>> true randomness, ...
>Unpredictability requires precisely that. True randomness is NOT
>necessary.
I surely would like to see you prove that latter assertion. You do
have a proof, don't you?
>The differences between secrecy of algorithm and secrecy of key are of a
>*practical* nature. In theory, there is no distinction between hiding
>your algorithm and hiding your key. You said (and I parahprase) that
>all bets are off when your adversary knows your method when you're
>relying on its secrecy for security. The same thing can be said for
>keys too. (All bets are off when your adversary knows your key when
>you're relying on its secrecy for security). Some time ago I wrote a
>message discussing using algorithms as keys and security through
>obscurity. If you're interested, you can look it up at Deja News.
It is widely accepted in crypto that obscurity does not imply
security.
>Pseudorandomness is not a property of a single sequence. Unless you are
>using the term differently than most theoretical computer scientists, it
>doesn't make sense to talk about the pseudorandomness of pi.
HUH?!
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Fri, 19 Feb 1999 16:23:45 GMT
Reply-To: [EMAIL PROTECTED]
On 19 Feb 1999 08:31:21 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>But strings that aren't a priori random are agreed to not be random
>to begin with.
>Or, to put it another way -- give me a string and tell me whether
>you think it's random.
>If you don't think it's random, we can agree that it's not random
>and we won't use it.
>If you *do* think it's random and I can prove subtantial deviations
>from the expectations of a runs test for randomness, then I can
>reject your idea to any desired degree of (un)certainty.
>So although we can't prove a string to be random, we can prove it
>to be very probably not random.
I agree with that in practice, as you know. But there are provisos,
which come about because of the "very probably" part of your
statement. There is a strong wishful temptation to elevate "very
probably" to "probably certain", which can get you into trouble.
Li & Vitanyi have several discussions about Uniform Bernoulli
Processes (p=1/2) in their book on Kolmogorov Complexity that I find
quite interesting. One of them is, of course, on the (Weak) Law Of
Large Numbers, which is what you are invoking. As the number of fair
coin flips increases towards infinity, the fraction of heads
approached 1/2. But there are warnings about how to interpret that for
a number of processes substantially less than infinity.
For example, consider this comment on p 263:
"But we can expect x [an infinite random number generated by a Uniform
Bernoulli Process] to satisfy a few standard laws, like the Law Of
Large Numbers, and presume them always chosen. However, the classical
theory of probability gives us no criteria for selection of such
standard laws."
For example, on p. 300 the authors discuss Laplace's Law Of Succession
in terms on a general Bernoulli Process (as well as in other places).
"... Laplace uses this rule to compute the probability that the sun
will not rise tomorrow, given that it has been rising every morning
since the creation of the world 10,000 years ago. Using the above it
follows that the probability that the sun will not rise tomorrow is
approximately 1/3,650,000."
Even though a one in a 3 million chance seems "very remote", it is
still large enough to be of concern. I believe it ranks along with the
probability of being struck by lightening - which may not concern
*you* as one individual, but it certainly does concern those who get
zapped every day by lightening.
Saying that some event is "very probable" is not good enough, even if
that probability is convergent in Large Numbers. Using statistics to
characterize the output of a RNG may be "very probable", but
if you are "unlucky", your sun may not shine tomorrow and you may get
struck by lightening to boot.
Also, the Law Of Large Numbers says nothing about bit groups of size
greater than 1. In order to take those into account (as in testing for
a preponerance of HH over TT), you have to add more Laws, in
contradiction to the warning given above (Li & Vitanyi, p. 263). IOW,
pretty soon you will be expecting your tests for randomness to do
things that cannot be done for any random number you test.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Fri, 19 Feb 1999 16:34:53 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 23:57:47 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Repeating this ad nauseum does not make it true.
And your repeating this ad nauseam does not make it true, either.
>Quantum processes produce
>output in the form of experimental results. If you can prove that (generated)
>data "truly random", then I can use the same technique to prove data generated by
>an RNG to be "truly random".
Quantum Mechanics is a consistent theory that is proven correct by far
more than a handful of experimental data. It is Quantum Mechanics that
proves that certain process are totally random, like radioactive
decay. IOW, the proveably random nature of radioactive decay is not
based on just a few experimental tests.
Of course, if you are designing a TRNG based on radioactive decay, you
would want to conduct tests on the radioactive decay detection system
to see if the results are consistent with what QM tells you. But that
is not the same as stating that radioactive decay is totally random
based on those tests.
>When you can show me the design notes, implementation log, and ECO revision
>history for the universe, then I'll believe you can "prove" QM indeteminant.
Try a century of modern physics instead.
>And don't try to feed us crap about experimental proofs again.
"Crap"?
Here you go again with the ad hominem attacks. You always do that when
you are frustrated because you don't have anything substantive to say.
>Instead reread my
>first paragraph above and try to grasp the equivalence of the proof methodology.
Instead, you need to study Quantum Mechanics above the level of
freshman physics. Try publishing in it sometime - that'll get your
neurons firing correctly.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To:
sci.skeptic,sci.philosophy.meta,sci.psychology.theory,alt.hypnosis,sci.logic
Subject: Re: Randomness based consciousness?. (Was: Re: *** Where Does The
Randomness Come From ?!? *** )
Date: Fri, 19 Feb 1999 16:51:12 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Feb 1999 14:06:30 +0000, David A Vivash
<[EMAIL PROTECTED]> wrote:
>Whilst we cannot predict what the next digit of Pi is, we can calculate
>it, so this is not random.
And therefore you can predict what the next digit is.
>I can see that any mathematical system that contains perfect information
Perfect information would have to be infinite in size.
>can be used to solve all problems within that system.
Godel would be rolling in his grave now if he heard you say that.
>But it seems to me
>that certain systems may not necessarily have all the information to
>solve a problem, although the answer to the problem still lies within
>the system. (That is, the lack of information is inherent in the design
>of the system, rather than the case being that it's too difficult to
>know all the necessary variables).
You cannot prove more than is contained in the axioms of a formal
system. Therefore there is no answer lurking in a system which does
not have enough information to solve the problem.
The Turing halting problem will show you that.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
** 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
******************************
