Cryptography-Digest Digest #501, Volume #11 Thu, 6 Apr 00 20:13:01 EDT
Contents:
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" ("Owen Lewis")
Re: [Q] Knuth on ACGs in 3rd edition ("David C. Oshel")
Re: [Q] Knuth on ACGs in 3rd edition ("John Michener")
Re: Help decrypt message exercise ([EMAIL PROTECTED])
Encrypt the signature? ([EMAIL PROTECTED])
Re: Is this code crackable? (Richard Herring)
Re: Q: Simulation of quantum computing (Bill Unruh)
Re: RNG based on Blum Blum Shub (Herman Rubin)
Re: Q: Simulation of quantum computing (Mok-Kong Shen)
Q: Petri nets (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: Q: Entropy (Will Dickson)
Re: GSM A5/1 Encryption (Paul Schlyter)
Re: Q: Entropy ("Tony T. Warnock")
Re: GSM A5/1 Encryption (David A. Wagner)
Re: Q: Simulation of quantum computing (Mok-Kong Shen)
Re: Q: Entropy (Johann Hibschman)
Re: Massey-Omura protocol & ECC ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Owen Lewis" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.politics.censorship
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
Date: Tue, 4 Apr 2000 09:53:15 +0100
"A. Little" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> If you want to use your vote wisely, withhold it.
>
> Incidentally, I have a feeling that inciting people not to vote is
> actually illegal in England.
I believe that you are right.
It is also unlawful not to put one's name forward to the Electoral Roll.
Nevertheless and as you surmise, a decision not to vote may be better
reasoned and as valid a choice than most votes cast.
Owen
------------------------------
From: "David C. Oshel" <[EMAIL PROTECTED]>
Crossposted-To: alt.sources.crypto
Subject: Re: [Q] Knuth on ACGs in 3rd edition
Date: Thu, 06 Apr 2000 08:34:32 -0500
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
> "David C. Oshel" wrote:
> >
> > I've heard that Don Knuth reports recent (post-1990) deprecations on the entire
>class of additive
> > congruential generators in his 3rd edition of _Art of Computer Programming_.
> >
> > Does anyone know what the test is that he refers to, other than that
> > it's allegedly "simple"? Does anyone have source code?
> >
> > A pity, if true, because Mitchell & Moore's version has always looked like a
> > winner to me.
>
> Maybe he refers to the GAP test, or the fact they are linear. Generally
> though a lfg with a big enough lag is sufficiently random [not secure,
> but statistically well balanced].
>
> Tom
Thanks, Tom. This is a bit of a puzzle for me, because M&M's acg (or at least the
Lewis & Payne variant,
see http://homepage.mac.com/dcoshel/2^55.html for C source) passes Chi-square very
nicely. What in the world could
the objection be?
E.g., I used URandomLibTest at
http://www.geocities.com/~mikemclaughlin/software/URandomLib.html to generate this
result:
Coin-flip test:
Enter the number of repetitions.
100000
Expected frequencies:
100000 1000000 4500000 12000000 21000000 25200000 21000000 12000000 4500000 1000000
100000
Using URandomLib...
99986 999645 4498493 12000392 20998449 25196999 21004189 11994649 4504946 1002632
99620
ChiSquare = 18.146735 ==> Randomness is rejected with more than 90.000000% confidence.
Using RANDU...
64399 671425 3340257 10064362 19742182 25962139 22995902 13468608 4968204 1032213
90309
ChiSquare = 1250260.156568 ==> Randomness is rejected with more than 99.999999%
confidence.
Using ACG...
100276 999736 4498808 11998017 21000787 25203905 20998185 12002132 4498383 999440
100331
ChiSquare = 4.635413 ==> Randomness is accepted.
--
David C. Oshel mailto:[EMAIL PROTECTED]
Cedar Rapids, Iowa http://pobox.com/~dcoshel
``Tension, apprehension, and dissension have begun!" - Duffy Wyg&, in Alfred
Bester's _The Demolished Man_
------------------------------
From: "John Michener" <[EMAIL PROTECTED]>
Crossposted-To: alt.sources.crypto
Subject: Re: [Q] Knuth on ACGs in 3rd edition
Date: Thu, 6 Apr 2000 06:55:56 -0700
I saw a discussion of the statistical properties of these generators in the
membership newsletter of the Society for Industrial and Applied Mathematics
about a year or two ago. The additive generators have been used in large
numerical simulations and were found to generate artifacts. Interestingly,
the behavior is significantly better if multiplication is used rather than
addition, and the behavior improves if instead of a 3 term relationship a 4
or 5 term relationship is used. An interesting question is what would the
behavior be if the feedback operation were through an S table.
Don't ask me to product the reference. I have moved twice since then. I
don't know where I put it.
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> "David C. Oshel" wrote:
> >
> > I've heard that Don Knuth reports recent (post-1990) deprecations on the
entire class of additive
> > congruential generators in his 3rd edition of _Art of Computer
Programming_.
> >
> > Does anyone know what the test is that he refers to, other than that
> > it's allegedly "simple"? Does anyone have source code?
> >
> > A pity, if true, because Mitchell & Moore's version has always looked
like a
> > winner to me.
>
> Maybe he refers to the GAP test, or the fact they are linear. Generally
> though a lfg with a big enough lag is sufficiently random [not secure,
> but statistically well balanced].
>
> Tom
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Help decrypt message exercise
Date: Thu, 06 Apr 2000 14:01:59 GMT
I DIT it! Thanks for all your help!
Anyone who wants to know the decrypted msg
just drop me a line.
e-mail: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> [ ... ]
>
> > Besides individual letter frequencies, go through and underline
> > repeated strings. In this case the symbol 8 is indeed an E, and
> > the word THE appears here and there, as you would expect in
> > English. Try each of the likely 3-letter repeats for THE and
> > see if anything recognizable pops out.
>
> Allow me to add that what "pops out" for Jim Gillogly usually takes
> quite a lot of work for most of the rest of us, so don't get
> discouraged if it takes more time and effort than he implies above.
> It takes a while, but it's definitely solvable.
>
> --
> Later,
> Jerry.
>
> The universe is a figment of its own imagination.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Encrypt the signature?
Date: Thu, 06 Apr 2000 14:35:42 GMT
Dear all,
Just a beginner question:
If I want to have a crypted signed document, have I to
encrypt the signature ???
Patrice Krakow
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Is this code crackable?
Date: 6 Apr 2000 15:05:48 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, 1198 ([EMAIL PROTECTED]) wrote:
> Richard Herring wrote in message <8cf7sp$ekc$[EMAIL PROTECTED]>...
> >In article <[EMAIL PROTECTED]>, 1198 ([EMAIL PROTECTED])
> wrote:
> >> If the key file can be safely sent to the other end without security
> problem
> >> then there is no point of having any encrytion at all..
> >
> >Not so. You're assuming that a channel that is "safe" now will
> >always be safe.
> Mind I ask is a channel be more secure than any encryption method could
> provide??
With conventional private-key encryption you have to get the key
to the other party without it being compromised by eavesdroppers or
active attacks. That requires a secure channel of some sort.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Q: Simulation of quantum computing
Date: 6 Apr 2000 15:39:34 GMT
>The question involved 'Turing machine' not 'Turing machine WITH
>a random oracle'! If I had had a 'random oracle', then I could
>certainly have generated my truly random bits with the help
>of that oracle :-)
Yes, and I am saying that IF you also want to simulate the readout, then
you must use a Turing machine with a random oracle. A quantum computer
simulator can calculate for you what the probabilities are for various
outcomes. It cannot create for you a variable whose values are random
and which follow that probablility law. Note tht such a classical
simulator in fact gives you much more than a quantum computer does. It
gives the detailed probability distribution, something tht the quantum
computer, running as a quantum computer, cannot give you. It does this
however at an exponential cost.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: RNG based on Blum Blum Shub
Date: 6 Apr 2000 10:39:21 -0500
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>What about changing it to
>p = large prime, (p - 1)/2 is prime
>X = seed
>g = large primitive generator (modulo p), above (p - 1) / 2, with at
>least log2(p)/2 bits set.
>M[0] = g^X
>To generate an output compute:
*>M[i] = M[i - 1] * g (mod p)
*>Y = M[i] mod 2^log2(p)
>Y = output, so with a 256 bit prime, this will output 8 bits each
>itteration. I know this is probably not strong, so where would you
>start to attack it?
>Tom
Only the lines I have indicated with a * are relevant;
one could start with M[0] and g. This is getting the
least significant part of a multiplicative congruential
generator, and that is how it should be attacked.
It is also expensive; this is a lot of computing for
only 8 bits.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Thu, 06 Apr 2000 18:08:17 +0200
J.Wallace wrote:
>
> No, you could not obtain truly random bits through this type of
> simulation. As you say yourself, with a classical computer and
> classical programming you can only get pseudo-random bits. The
> quantum computer simulators that have been written are classical
> programs running on classical computers.
I hope I understand the matter as follows: The simulation is not
'exact' (i.e. not an emulation) but only a very good approximation.
Hence it can't do everything that a real quantum computer can.
One thing it can't is generation of truly random bits.
Please kindly correct me, in case I am wrong.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: Petri nets
Date: Thu, 06 Apr 2000 18:08:23 +0200
Recently in another thread there has been much interesting
discussions related to the theory of automata. I have some
questions of ignorance:
In computer science, a theory that has certain practical
applications bears the name 'Petri nets'. Are these automata? If
yes, why are they not treated at all in textbooks on automata
(at least in the few books I have seen)? If not, what beasts are
they from the view point of theory of automata? Can Petri nets do
computations in the sense of automata (treated in the textbooks)?
If yes, are they equivalent to TM or more powerful? Do Petri nets
possess the potential of having some relevance to crypto much like
the cellular automata?
Thanks in advance.
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Thu, 06 Apr 2000 18:07:13 +0200
Niklas Frykholm wrote:
>
> It is true that entropy is in the process and not in the sequence, but in
> practice it is usually the sequence that matters, because the attacker will
The following citatation, however, contradicts you claim that
entropy is not in the sequence:
Schneier, p.233: Formally, the amount of information in a
message M is measured by the entropy of a message, denoted
by H(M).
Thus each particular sequence (message) should have an entropy.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: Q: Entropy
Date: Thu, 06 Apr 2000 16:23:08 GMT
>I think that what you said is indeed worth noting. To mention a
>situation in different context: If I use a perfect coin to generate
>a bit sequence, it has the full entropy corresponding to the length
>of the sequence. But this entropy value is based on my knowledge of
>the process of generation and (what I suppose is more important for
>use of the sequence in encryption) depends on the fact that I am
>the single person in possession of the sequence. If I hand out the
>sequence to someone else, then the same sequence has exactly zero
>entropy for him for encryption purposes in my humble opinion (for I
>know his 'secret' OTP and can utilize that to crack his encipherments).
>The choice of any procedures, if these can be kept secret from the
>opponent (which I suppose is possible in many practical situations),
>does contribute to strength in general in crpto systems. As a
>particular example of situations where this may apply, I like to
>recall the recently discussed topic of multiple encryption where
>one has a choice of the encryption algorithms and their diverse
>combinations (in either serial or parallel form of combination).
This point is expressed if you do the proper probability-theoretic
calculations that underlie the use of entropy in this context; all the
probabilities involved are properly written as conditional on "I", the
background information which you already possess. In the case you
describe, your "I" and his are very different, and so the entropies
you derive are also very different. This part is frequently missed out
of textbooks unless the author is a Bayesian!
Will.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: GSM A5/1 Encryption
Date: 6 Apr 2000 16:58:24 +0200
In article <8cfvb9$cqm$[EMAIL PROTECTED]>,
David A. Wagner <[EMAIL PROTECTED]> wrote:
> By modern cryptographic standards, A5/1 is a weak cipher, but I
> think you were more interested in the practicalities of interception,
> right?
>
> What's your threat model? The curious average man on the street
> who wanders down to Radio Shack to pick up a scanner, or a dedicated
> knowleadgeable individual with some budget (e.g., $10k), or worse?
>
> I think the GSM A5/1 cipher is likely to be secure against the former,
> but it would be unwise to assume that it is secure against dedicated
> attack by knowleadgeable individuals.
Even if the GSM transmission wasn't encrypted at all, it would still
be secure against the former, since pretty sophisitcated equipment
will be required to even distinguish one particular GSM conversation
from all the others occurring at the same frequency. No scanner
available at Radio Shack will be able to do that. You would need to
either construct your own equipment, or open up and modify a cellular
phone -- both are non-trivial tasks.
> Today, breaking GSM A5/1 appears to be feasible for corporate espionage,
> but probably not for most curious hobbyists. But that could well
> change 3-5 years down the road; in this field, history teaches us
> that sophisticated attacks often have a way of filtering down to the
> street in the form of black boxes that require little or no
> sophistication to use.
>
> If you are interested in intelligence agencies, I would be amazed if
> they do not have the capability to eavesdrop on GSM traffic when they
> want to.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Thu, 06 Apr 2000 10:31:42 -0600
Reply-To: [EMAIL PROTECTED]
My point is that in practice one ignores really small probabilities. I
stated things loosely, not as theorems.
In theory a "random bit generator" could produce a long string of zeros
for example, but in practice, we would consider the generator broken if
it did.
Complexity theory is generally more useful for cryptography than
probability in these cases. One could use a "universal" probability
function rather than assuming the usual probability measure on bit
strings. Take some universal Turing machine; for each output string get
the length of the input string that generated that output; assign a
weight or 1/2**(length) to the output string. Except from some details
in normalization, this will assign a measure to strings. Strings like
0000... or 010101010, or 011011100101110111... will have high measure.
Unstructured strings will have lower measure. Then occurence of 00000...
would not seem as "random" as 010010001 or such.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 6 Apr 2000 09:04:07 -0700
In article <8ci8mg$hv6$[EMAIL PROTECTED]>,
Paul Schlyter <[EMAIL PROTECTED]> wrote:
> Even if the GSM transmission wasn't encrypted at all, it would still
> be secure against the former, [..]
Right. Digital scanners aren't readily available today.
> [..] since pretty sophisitcated equipment
> will be required to even distinguish one particular GSM conversation
> from all the others occurring at the same frequency. No scanner
> available at Radio Shack will be able to do that.
I think that's optimistic. After all, your already phone does it!
Sure, no scanner available at Radio Shack can do it *today* -- Radio
Shack doesn't stock digital scanners at the moment -- but as for the
future, it is hard to say. May I point you to a lovely quote from
the president of the Cellular Telecomunications Industry Association
(the US cellphone standards body)? He said
``history will likely repeat itself as digital scanners and
decoders, though expensive now, drop in price in the future.''
All it takes is a small software mod to your GSM cellphone
(or maybe even just knowing the right test code) ...
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Thu, 06 Apr 2000 18:51:04 +0200
Bill Unruh wrote:
>
> Yes, and I am saying that IF you also want to simulate the readout, then
> you must use a Turing machine with a random oracle. A quantum computer
> simulator can calculate for you what the probabilities are for various
> outcomes. It cannot create for you a variable whose values are random
> and which follow that probablility law. Note tht such a classical
> simulator in fact gives you much more than a quantum computer does. It
> gives the detailed probability distribution, something tht the quantum
> computer, running as a quantum computer, cannot give you. It does this
> however at an exponential cost.
>From what you said we have:
TM + oracle can generate truly random bits
QC can generate truly random bits
I suppose
TM (alone) can't generate truly random bits
I seems to follow from these that QC is more powerful than TM.
Is that right?
Thanks.
M. K. Shen
------------------------------
From: Johann Hibschman <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: 06 Apr 2000 09:49:12 -0700
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen writes:
>> In short, the question you're asking (i.e. what's the entropy of a
>> given string) just doesn't make any sense.
> I don't exclude that the difference in different disciplines
> matters essentially here. For cryptology, whether a bit sequence
> being used has patterns is an important question. A sequence of
> 010101.... is virtually useless for encryption purpose. You seemed
> to claim that a particular sequence as such (your example 1 2 4)
> has no entropy. I must say that I am not yet very sure the one way
> or the other (that's one reason why I initiated this thread). But
> let me quote from Schneier's Applied Cryptography (which may not be
> familiar to you physicists but is well-known in cryptology):
> Formally, the amount of information in a message M is
> measured by the entropy of a message.
> This means that a single (particular) message does have entropy.
I'm afraid that you are misunderstanding the quote.
A "message" in that context is a total potential communication, the
set of all possibilities for that message, not any individual concrete
message. In crypto, it's the cyphertext you're looking at, which
could (due to your ignorance) possibly decode to any of a number of
plaintexts.
Reread the start of the section: "Information theory defines the
amount of information in a message as the minimum number of bits
needed to encode all possible meanings of that message." A "message"
is something with many possible meanings, not an already-decoded
result.
Just read that section over again, being aware that "message"
sometimes means the set of all possible messages and sometimes just
the concrete message itself. The language is unweildy. The example
he gives of encoding days of the week clearly operates by enumerating
the possible messages, right?
Have you read Shannon's original paper? It's pretty clear, and is
available online. Well, the first few sections are clear; I've never
managed to finish the whole thing. ;-)
Don't ask me for too many details, or I'll say something stupid and
then Ian and Dave will mock me mercilessly...
--
Johann Hibschman [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Massey-Omura protocol & ECC
Date: Thu, 06 Apr 2000 16:36:22 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
>
> so, xP would be the ECC version, t|#E, and txP = 1. This doesn't
> explain the
> more complicated method of converting the "x" component of xP to an
> integer and
> using it as a multiplier to combine stuff. I better go talk to a
lawyer
> :-)
>
> Patience, persistence, truth,
> Dr. mike
When your lawyer can shed some light, I'd love to hear about it :)
I went to three books stores today, and not a sign of koblitz anywhere.
Even the local online stores could not get it any faster than 4-6
weeks. And Amazon.com would charge me an arm and a leg and maybe anoher
body part or shipping. I did find prisoner of Azkaban in paperback. But
my wife has already bought the hardback months ago.
Anyway, i am beginning to think that even with a Digital signature what
would stop malfour from generating the signature both ways as well thus
completing the protocol with both parties using his own keys ?
Is this a possibility ?
Petang
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
