Cryptography-Digest Digest #322, Volume #10 Tue, 28 Sep 99 06:13:04 EDT
Contents:
Re: Schrodinger's Cat and *really* good compression ("Douglas A. Gwyn")
Re: Comments on ECC ("Douglas A. Gwyn")
Re: Perfect Shuffle Algorithm? ("Douglas A. Gwyn")
Re: NEMA, Swiss cipher machine
Re: Electronic envelopes (Johnny Bravo)
Re: Cryptographically strong random number generator (Scott Nelson)
Re: Electronic envelopes (Mok-Kong Shen)
Re: Electronic envelopes (Johnny Bravo)
Re: Electronic envelopes (Johnny Bravo)
Re: Electronic envelopes (Mok-Kong Shen)
Re: Electronic envelopes (Mok-Kong Shen)
ECC97 Challenge Solved ("Sam Simpson")
Re: simple algorithm for hardware device? (Volker Hetzer)
Re: Electronic envelopes (Mok-Kong Shen)
Re: simple algorithm for hardware device? (Volker Hetzer)
Re: Perfect Shuffle Algorithm? (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Tue, 28 Sep 1999 06:34:27 GMT
John Savard wrote:
> Actually, however, the box has to be *very* well-insulated in order
> for the cat not to be inadvertently observed.
Well, actually that just spreads the superposition to a wider system
(according to the theory of measurement that is being questioned).
> In fact, since a cat is big enough to have a detectable gravitational
> pull, and no insulator for gravity is known - after all, it bends the
> fabric of space itself - and so there may be a *fundamental*
> impssibility involved; at least this is what Roger Penrose has
> suggested.
Gravity works even at the microlevel, but its effects are usually
dwarfed by the e-m and strong forces. So it doesn't seem to have
anything to do with the actual issue; it's another case of "I don't
know whether it is relevant or not, so it might explain something".
Remeber, Penrose was taken in by Searle's "Chinese box" argument.
He's undoubtedly a very smart person in his own field, but like
many, he doesn't seem nearly as smart when dabbling in another field.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: Mon, 27 Sep 1999 14:40:18 GMT
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> >Unless somebody also invents an algorithm for converting
> >any NP-complete problem into a P problem, knowing that
> >P=NP wouldn't be of any practical use.
> Cook invented most of such an algorithm in 1971 -- a problem
> that is known to be NP-complete can be used to solve ANY problem
> in NP by suitable formulation of the inputs, and the process
> of proof of NP-completeness gives such an algorithm. All
> we lack is the ability to reduce one such program to P.
In other words, we don't have a glimmer of an algorithm.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 06:48:39 GMT
There is probably a slick mathematical solution,
but so far as programming a simulation:
A shuffle maps the 1001 card positions to 1001 new positions.
This can be represented as a 1001x1001 sparse array of bits,
with 1s where the input meets the output. (Arithmetic in GF(2).)
It seems like the matrix can be partitioned into blocks.
Then some of the standard matrix techniques can probably be used.
Good luck!
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: NEMA, Swiss cipher machine
Date: 28 Sep 99 05:31:20 GMT
[EMAIL PROTECTED] wrote:
: Thus, only the "contact rotors" or "contact wheels" (I may have done this,
: not Frode) in a NEMA should be called rotors.
After posting this, I realized that even if I disapprove of the term used
for these components of a NEMA rotor machine, I should not speak as if
Frode had made a _mistake_, since, after all, from a historical
perspective one should use exactly the term that was originally used by
the makers and users of a device, even if one perhaps should also note any
difficulties with respect to present usage.
But _then_ I remembered that the name for a reflecting rotor in German is
"Umkehrwalze". Now, if a car in Switzerland should be driven so as to keep
its four _walzen_ on the ground...
that would mean that the wheel/rotor distinction does not exist in the
original German, which gives the opportunity to be faithful to the
original terminology and scrupulous in using words in English with such
assigned meanings as will cause the least confusion at the same time.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 02:57:26 GMT
On Mon, 27 Sep 1999 19:29:38 +0200, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>[Note: Owing to a technical issue, you might receive a duplicated
>copy of this post. My apology for your inconvenience.]
>
>
>I like to know whether it is possible (and how) to realize an
>electronic envelope in the following sense: It is not possible by
>anyone else than the sender to get the contents of the envelope
>before a predetermined time point without that act of manipulation
>be known.
Only possible if you are able to communicate with the holder at some point.
Since you state below that this isn't the case, you are out of luck.
>In other words, one deposits an envelope containing
>secrets at a notary who opens it at a certain time point and
>announces the contents. The envelope is to be opened exactly at
>that time point and not before. No trust on the notary is assumed.
Then you can't even be sure your envelope will even be opened.
>The act of opening should hence prove that it is indeed done at the
>prescribed time point. With such a mechanism one could deposit
>copies at several notaries at different geographical locations and
>the secrets will then be disclosed simultaenously at these places
>(within the error tolerance of the radio clock signal transmission,
>of course).
Not at all possible, even if you give them the keys yourself can
you assume that they will all open them within the same second.
And what radio clock signal transmission are you talking about?
>After deposition of the envelope, no further interaction
>between the sender and the notary is assumed to be available.
>
>M. K. Shen
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Cryptographically strong random number generator
Reply-To: [EMAIL PROTECTED]
Date: Tue, 28 Sep 1999 07:43:14 GMT
On Mon, 27 Sep 1999 09:11:52 +0200, Karsten Spang
<[EMAIL PROTECTED]> wrote:
>On what criteria does one assess that a random number generator is
>cryptographically strong? Is the XPG4r2 random() cryptographically strong?
>
>According to the manual:
>> With 256 bytes of state information, the period of the random-number generator
>> is greater than 2^69.
>
A quick web search turns up this link;
( http://info.netmar.com/cgi-bin/man2html?cgi_command=random )
random() uses a non-linear additive feedback random number
generator employing a default table of size 31 long integers
to return successive pseudo-random numbers in the range from
0 to (2**31)-1. The period of this random number generator
is very large, approximately 16*((2**31)-1).
This is a pathetic random number generator from a cryptographic
viewpoint. In fact, it's not all that hot from a statistical
standpoint either - Combo does about as well with only 128 _bits_
of state, and it's faster.
( http://www.helsbreth.org/random/rng_combo.html )
But for crypto, you probably want something like Yarrow;
http://www.counterpane.com/yarrow.html
Or perhaps Ocotillo might be closer to what you want.
http://www.estinc.com/~eric/
>I guess that with 2048 bits of state information, there can be a very large
>number of different sequences, which look the same for the first "many"
>numbers. The question is how many "many" is.
>
approx. (2^2048) / (2^(64 * first_many))
>Then there is the problem on how to initialise the state array. The manual:
>> The initstate() function allows a state array, pointed to by the state
>> argument, to be initialised for future use.
>and
>> The seed argument specifies a starting point for the random-number sequence
>> and provides for restarting at the same point.
>
>Does this mean that the contents of the state array is discarded by initstate?
Yes, the contents of the state array is discarded.
>If so, the only initial randomness is given by the seed argument, which is only
>32 bits.
>
You could get around this by manually initializing the state table.
(The man page listed gives an example, if you really care.)
But you really should avoid this PRNG altogether, rather than
figuring out ways to hack it.
>And how do I get a random seed? Flipping a coin 32 times or anything else
>involving manual input is out of question. I am using HP-UX and Solaris.
>
There's no easy answer, and virtually all answers are heavily system
dependent, so there's no general answer at all. Read the Yarrow and
Ocotillo web pages.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 07:49:18 +0200
Art Dardia wrote:
>
> You have to assume that if you're using crytography to encrypt the
> envelope until the year 2020, as given in your example. By the year
> 2010, processors should be powerful enough to crack that a lot quicker
> than you'd want them to. You'd need to use a disgustingly large key
> size.
Agree perfectly. One can also use a number of processors. Thus exact
timing via solution of cryptological problems is impossible in my view.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 04:04:20 GMT
On Mon, 27 Sep 1999 20:24:06 -0400, Art Dardia <[EMAIL PROTECTED]> wrote:
>You have to assume that if you're using crytography to encrypt the
>envelope until the year 2020, as given in your example. By the year
>2010, processors should be powerful enough to crack that a lot quicker
>than you'd want them to. You'd need to use a disgustingly large key
>size.
>
> Art Dardia
>
>PS - I'm a newbie. My posts may mean nothing.
He want's the time known to the exact second. Just not possible.
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 04:10:19 GMT
On Tue, 28 Sep 1999 00:41:18 GMT, "Richard Parker" <[EMAIL PROTECTED]>
wrote:
>I think the following method could be used by Alice to deposit an
>envelope containing a secret message with a notary such that the
>message can't be extracted by the notary until after a time that Alice
>specifies.
>
>Assume the existence of trusted clock. The trusted clock generates a
>set of public-key/private-key key pairs. The clock publishes the
>public keys along with a time at which the corresponding private key
>will be announced for each public key. The clock guarantees that it
>will only release a private key at that time.
Why not skip all the crypto and just have the "trusted clock" release the
message on time? All your system does is add another person to the loop. If
you must insist on a second person, give the message to one, and the key to
another. Give them a time and a place to meet to decrypt the message at the
correct time. This is no guarantee that either person will show up or that the
message will be opened. And there is no guarantee that they won't put out a
full page newspaper add looking for the person with the other half either.
Johnny Bravo
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 08:42:32 +0200
Richard Parker wrote:
>
> Assume the existence of trusted clock. The trusted clock generates a
> set of public-key/private-key key pairs. The clock publishes the
> public keys along with a time at which the corresponding private key
> will be announced for each public key. The clock guarantees that it
> will only release a private key at that time.
This is not a bad idea. However, it assumes that there is a central
agent that is trusted by all people and that that agent never fails
(because of political events, etc.) and probably also some minor
technical issues.
> However, note that in the above method there is nothing that prevents
> the notary from stopping at step 4. While this method prevents the
> notary from opening the envelope before the time specified by Alice,
> it does not provide any assurance that the notary will actually open
> the envelope.
You are right. I should have confined the goal a bit and made
that explicit. I negected to say that the depositor trusts the
notaries, i.e. they will dutifully do their job. The big problem is
how the public can believe that there is no manipulation (even though
the depositor has no doubt and there indeed is no manipulation.)
The notary can be sort of forced to open the envelope by a public
announcement of the depositor that such an envelope has been
deposited at the notary to be opened at such and such a date.
One relies also on the fact that copies are deposited at a number
of notaries so that the chance of a total failure is small.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 08:42:38 +0200
Johnny Bravo wrote:
>
> Only possible if you are able to communicate with the holder at some point.
> Since you state below that this isn't the case, you are out of luck.
It's possible that you are right. The problem is to ascertain that.
> >In other words, one deposits an envelope containing
> >secrets at a notary who opens it at a certain time point and
> >announces the contents. The envelope is to be opened exactly at
> >that time point and not before. No trust on the notary is assumed.
>
> Then you can't even be sure your envelope will even be opened.
In the case of normal envelopes I suppose that there are ways of
sealing that are traditionally considered to be adequate against
frauds and there are specialists who can examine that. I don't know
what the actual probability of frauds is, but it seems that people
accept (believe) that degree of security (compare signatures on
cheques).
> >The act of opening should hence prove that it is indeed done at the
> >prescribed time point. With such a mechanism one could deposit
> >copies at several notaries at different geographical locations and
> >the secrets will then be disclosed simultaenously at these places
> >(within the error tolerance of the radio clock signal transmission,
> >of course).
>
> Not at all possible, even if you give them the keys yourself can
> you assume that they will all open them within the same second.
> And what radio clock signal transmission are you talking about?
The signals that synchronize, for example, your alarm clock. As
far as I know, each country has a station sending the time signals
based on an atom clock which is synchronized with Greenwich.
M. K. Shen
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: ECC97 Challenge Solved
Date: Tue, 28 Sep 1999 09:20:50 +0100
http://www.certicom.com/press/99/sept2899.htm
It is interesting to note that this challenge took ~16,000 MIPS-years
whilst an 512-bit RSA key took ~8,000 MIPS-years.
Any comments on the press release?
Regards,
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: simple algorithm for hardware device?
Date: Tue, 28 Sep 1999 11:13:54 +0200
Luigi Funes wrote:
>
> Hi all! I wonder if someone can help me!
>
> I'm building a high speed hardware encryption/decryption
> device working on a data stream of 16 bit words.
> Data coming in variable size packets at 40 Mword/sec
> and every word must be encrypted almost immediately, more
> exactly the delay between the input and output of a every
> word must be < 5 nS.
So, a pipeline wouldn't do?
Sounds unlikely. After all, someone has to process all the messages
which surely takes longer than 5ns.
What exactly are you trying to do? Remember, 5ns are
the equivalent of your data travelling through a 1.5m cable.
Are you not mixing latency with throughput?
> I already succesfully tested a prototipe, using a trivial
> algorithm XORing data and a LFSR, but now I have to
> implement something of better.
> Note the algorithm can be kept secret, because it's
> hidden inside the FPGA, but a enemy could steal the
> device, setup any key and encrypt and analyze any data.
> Besides, the enemy knows the plain texts of many
> encrypted data.
> Someone can suggest me an algorithm for this device?
> I'll appreciate any comment too. Thanks!
If we knew more about your problem we could probably suggest
another solution instead of a poor algorithm.
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 09:09:00 +0200
Douglas A. Gwyn wrote:
>
> Search for "nonrepudiation protocols". There has been a fair
> amount of work on this, but I don't have it in front of me.
Could someone of the group kindly provide some pointers?
I hope that these adequately take the time issue into account
which is essential for the present scheme.
Thanks in advance.
M. K. Shen
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: simple algorithm for hardware device?
Date: Tue, 28 Sep 1999 11:16:06 +0200
Trevor Jackson, III wrote:
> There is _no_ encryption algorithm with a fixed key < ~ 1 megabit that
> cannot be represented by such a code table. Fill the table by running
> 97-DES if you want. It's not more secure.
Wouldn't DES require a 64-Bit table (64 Bit address and 64 bit data)?
You surely mean " There is _no_ 16 Bit encryption algorithm ...".
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 09:22:58 +0200
[EMAIL PROTECTED] schrieb:
>
> I was given a problem for a job interview for a computer programming
> job. I was to write a routine that cuts a computer simulated deck and
> performs a perfect shuffle. A perfect shuffle, you cut the deck x cards
> from the top. Then the bottom card from the top stack deck goes down
.....
Is this your definition of a perfect shulffle or is it from a
literature reference? If you have a perfect random number source
(which is impossible) then I suppose the shuffle with the algorithm of
Durstenfeld (in Knuth's book) is (at least in certain sense) perfect.
M. K. Shen
------------------------------
** 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
******************************
