Cryptography-Digest Digest #720, Volume #13      Tue, 20 Feb 01 08:13:01 EST

Contents:
  Re: FAQ ("John A. Malley")
  New unbreakable code from Rabin? (Roger Schlafly)
  Re: New unbreakable code from Rabin? ("Douglas A. Gwyn")
  Re: Super strong crypto (wtshaw)
  Re: My encryption system..... (Paul Crowley)
  Re: Given any arbitrary numbers a and b.Can I ALWAYS find a   (Jan Kristian Haugland)
  Re: Euler's totient function and factoring (Stefan Katzenbeisser)
  Re: New unbreakable code from Rabin? (Mok-Kong Shen)
  Re: Super strong crypto (Mok-Kong Shen)
  Re: New unbreakable code from Rabin? (Hard)
  Re: The Kingdom of God ("Jashter")
  Re: Is there an algorithm to sequentially enumerate all transcendental  numbers? 
("Henrick Hellström")
  Re: Ciphile Software:  Why .EXE files so large (Anthony Stephen Szopa)
  Re: OverWrite freeware completely removes unwanted files from hard drive (Anthony 
Stephen Szopa)
  Re: Is there an algorithm to sequentially enumerate all transcendental  numbers?
  Re: New unbreakable code from Rabin? (John Savard)
  Re: New unbreakable code from Rabin? (John Savard)
  Re: What's a KLB-7? (John Savard)
  Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental number 
between a and b? (John Savard)

----------------------------------------------------------------------------

From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: FAQ
Date: Mon, 19 Feb 2001 21:22:40 -0800

kwd_kwp0ee9j9 wrote:
> 
> where can I find this newsgroup FAQ?

Posted here every 28 days or so, and there's a copy at

http://www.landfield.com/faqs/cryptography-faq/


Hope this helps,

John A. Malley
[EMAIL PROTECTED]

------------------------------

From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: New unbreakable code from Rabin?
Date: Mon, 19 Feb 2001 21:45:09 -0800

>From the NY Times:
In essence, the researcher, Dr. Michael Rabin and his Ph.D.
student Yan Zong Bing, have discovered a way to make a code
based on a key that vanishes even as it is used. While they are not the
first to have thought of such an idea, Dr. Rabin says that never before
has
anyone been able to make it both workable and to prove mathematically
that the code cannot be broken.
"This is the first provably unbreakable code that is really efficient,"
Dr.
Rabin said. "We have proved that the adversary is helpless."
http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
(free reg reqd)

------------------------------

From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 06:07:29 GMT

Roger Schlafly wrote:
> From the NY Times:

Thanks for the pointer.  Upon closer examination, this is a method
that I have seen before, perhaps in this newsgroup -- basically,
establish a publicly visible stream of random bits, and the
communicating parties select a running sample from the bit stream
pool according to some agreed-upon rule, and use that as an XOR
stream one-time key.  The idea is apparently that since the enemy
cannot store all the "infinite" bit pool, he cannot keep up with
the communicants, since he doesn't know in advance of analysis
which of the pool bits need to be recorded.

------------------------------

From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Super strong crypto
Date: Mon, 19 Feb 2001 23:53:58 -0600

In article <[EMAIL PROTECTED]>, Bryan Olson
<[EMAIL PROTECTED]> wrote:

> Actually, the straw-man system loops out.  Sending a
> new key encrypted under the old key does not move away
> from the unicity distance, so the system has to send 
> another immediately, then another, then another....

I suppose some systems would actually loop out, but this is no excuse for
systems that loop as a norm.

> Is "natural lifetime" some property of a key?

> So given systems for which computational security
> cannot be determined, you can produce systems with the
> same property.
> 
One aspect of strength is surely having the rough equivalent of a long
unicity distance, but that concept may be fading.   Nevertheless, being
able to use a key for a longer time because it can resist analysis
oflanger passages seems important.
-- 
Better to pardon hundreds of guilty people than execute one
that is innocent.

------------------------------

Subject: Re: My encryption system.....
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2001 06:32:52 GMT

Boris Kazak <[EMAIL PROTECTED]> writes:
> > (P.S. If no-one else has what I have, does that make me King Cryppie???).
>   Time to set an appointment with a psychiatrist...

In this country, we don't take our kids to the shrink for being
adolescent...

("All I wanted was a Pepsi!  But she wouldn't give it to me!")
-- 
  __
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/

------------------------------

From: Jan Kristian Haugland <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b.Can I ALWAYS find a  
Date: Tue, 20 Feb 2001 07:41:09 +0100


John Savard wrote:

> On Mon, 19 Feb 2001 21:22:55 +0100, Jan Kristian Haugland
> <[EMAIL PROTECTED]> wrote, in part:
>
> >This, however, doesn't show that the set of
> >transcendentals is uncountable (see other comments
> >about the rationals).
>
> That may not show it, but indeed the set of transcendentals _is_
> uncountable.

Well, yes, but I didn't think it was necessary to
point that out since about six people had said it
already.

--

Jan Kristian Haugland
http://home.hia.no/~jkhaug00



------------------------------

From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Euler's totient function and factoring
Date: Tue, 20 Feb 2001 08:30:17 +0100

[EMAIL PROTECTED] wrote:

> The trick here is to find X with X^2=1 mod n
> ((X-1)(X+1)=0 mod n) but X<>+/-1 mod n.
> Then GCD(X-1,n) is a factor of n.
> 
> If you have a multiple of all the multiplicative orders
> (any multiple of Carmichael's function), splitting that
> into an odd part and a power of two (2^a*b), taking any x,
> taking X=x^b mod n and successively squaring X will very
> often (so you only will have to do this for a few x's
> until you have "success") lead to such an X which allows
> you to factor n.

Ahhh... Thanks for your quick reply. I definitively should have 
known that, as it is in essence the proof that computing
the RSA decryption exponent is computationally equivalent to
factoring the modulus (actually this problem is just a 
special case).

Thanks again,
 --S


------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 08:52:54 +0100



"Douglas A. Gwyn" wrote:
> 
> Roger Schlafly wrote:
> > From the NY Times:
> 
> Thanks for the pointer.  Upon closer examination, this is a method
> that I have seen before, perhaps in this newsgroup -- basically,
> establish a publicly visible stream of random bits, and the
> communicating parties select a running sample from the bit stream
> pool according to some agreed-upon rule, and use that as an XOR
> stream one-time key.  The idea is apparently that since the enemy
> cannot store all the "infinite" bit pool, he cannot keep up with
> the communicants, since he doesn't know in advance of analysis
> which of the pool bits need to be recorded.

There is a problem that needs to be clarified, I suppose. 
How 'random' should the publicly visible stream of random 
bits be? (Could they e.g. stem from PRNGs?)

M. K. Shen

------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Tue, 20 Feb 2001 08:52:47 +0100



"Douglas A. Gwyn" wrote:
> 
> Bryan Olson wrote:
> > Is "natural lifetime" some property of a key?
> 
> No, it's a property of the encryption method.
> Surely you know? that real symmetric-key systems
> require the key to be changed at intervals calculated
> to resist cryptanalysis.  That is a given; what I
> am particularly interested in is, *assuming a correct
> assessment of that property*, is there appreciable
> actual weakness that could be exploited in practice,
> caused by piggybacking the distribution of additional
> key material on the existing channel?  This is not an
> academic exercise about unrealizable infinities; it's
> an important cryptoengineering issue that is relevant
> for certain kinds of communication systems.  It would
> be useful to definitely know the answer.

With the reasonable assumption that the keys are at
least as 'random' as the plaintext being processed,
there is no reason to expect that a scheme with frequent 
key changes can be weaker than one employing a constant
key, I believe.

M. K. Shen

------------------------------

From: [EMAIL PROTECTED] (Hard)
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 07:57:23 GMT

On Mon, 19 Feb 2001 21:45:09 -0800, Roger Schlafly
<[EMAIL PROTECTED]> wrote:

>From the NY Times:
><snip>
>Dr.
>Rabin said. "We have proved that the adversary is helpless."
>http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
>(free reg reqd)

Hmmmm...

The adversary is helpless?  No way to store that much data?  OK then
let's say I'm his adversary:

If we all have access to the same "random" bit stream, and I know that
Dr. Invincible is going to send a short encrypted message to Mr. X at
16:00:00 hours today, what is to keep me from capturing 15:59:59 to
16:00:01 of that stream and just crunching the numbers on it?  It
seems trivial.  Maybe I'm missing something.

He states that the random data stream is going to be something like a
million million bytes per second.  He might as well have said
bazillion.  The tech to keep that kind of stream flowing crypto
quality random continuously is going to be hard to come by, as is the
ability to sync up at any time in a continuous fashion.

But the ability to capture a few seconds (3-4 terabytes by my calc) is
possible now with current disk storage technology.  And if you can
capture the part that was used, can you not decrypt?

You can fit a stack of common DVD disks (4GB - very conservative) 18
of them to an inch in the space a human man would stand (six stacks at
72 inches each) and have eight hours worth of this stream.

Now it is true that most individuals or groups of individuals could
not keep up with this, but I'm *sure* the NSA could if it would mean
being able to chew through a significant portion of encrypted traffic.

The adversary does not appear to be helpless.  But again, one of you
is probably going to clue me in as to why Dr. Rabin's scheme is
provably impossible to crack.

BTW, thanks for the post, Mr. Schlafly.

------------------------------

From: "Jashter" <[EMAIL PROTECTED]>
Crossposted-To: alt.security,comp.security,alt.2600
Subject: Re: The Kingdom of God
Date: Tue, 20 Feb 2001 09:00:56 GMT

Yeah, but then you must wonder if there really is a god in the first
place...

"William Hugh Murray" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Trevor L. Jackson, III" wrote:
> > > Yes.  And your security point is what?  In any case, by definition,
> > > God's will is done.
> >
> > This thesis (sorry) implies that resistance to god's will is futile, and
> > reduces most theological texts (Book of Mormon, Koran, Bible, etc.) into
> > attitude adjustments.  Whither free will?
> >
> > The presumed congruence between divine and human wills makes the
precedence
> > ambiguous.  Just who is the willer and who is the willee, god or the
human?
>
>
> Did you ever think about the lyrics of the song "If I ruled the world?"
> Do you remember the line in the movie "Oh God" in which God says, "I
> never figured out how to make something with an inside and no outside,"
> or,  "I made math too hard." How about St. Anselm's proof for the
> existence of God?
>
> Let us not forget where this thread began and start to take it too
> seriously.  However, I do not think that the positions are
> irreconcilable.  If there is free will for man, it is because God
> consents to it.  Man did not create it and could not rebel without the
> freedom to do so.  If God consents to it, then, by definition, it is
> God's will.  If God is anything like Markku J. Saarelainen
> <[EMAIL PROTECTED]> seems to think of him/her as being, then
> he/she does not have to consent to free will for man if he/she does not
> want to.  This is of course the inconsistency in the position that
> started the thread.  Indeed, it is the central problem of that theology
> that wants to portray God as all loving and good and wants to put all
> the responsibility for evil in the world on man or Satan.  I do not
> pretend to know the answer but I can certainly appreciate the question.



------------------------------

From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental  
numbers?
Date: Tue, 20 Feb 2001 10:21:50 +0100

"Dave Seaman" <[EMAIL PROTECTED]> skrev i meddelandet
news:96st1d$[EMAIL PROTECTED]...
> Do you know what it means for a set to be recursively enumerable?  The
> terminology comes from computability theory, which might be considered to
> be at the intersection of mathematics and computer science.


Isn't a "recursively enumerable set" the same as an inductive set? The
concept of mathematical induction was discovered by Pascal in the 17th
century long before computers.

--
Henrick Hellström
StreamSec HB



------------------------------

From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Ciphile Software:  Why .EXE files so large
Date: Tue, 20 Feb 2001 02:08:49 -0800

Richard Heathfield wrote:
> 
> Anthony Stephen Szopa wrote:
> >
> <snip>
> 
> > For what it's worth:  If you are expert with Borland C++ Builder
> > you can make yourself a million dollars by writing a book similar to
> > Visual Basic 6:  Environment, Programming, and Applications by the
> > two authors Eliason & Malarkey.
> >
> > Then follow it up with an advanced text.
> >
> > At $50 a pop, let's see, 1,000,000/50 = 20,000 books.  Then multiply
> > this by at least 10 because you will at most get $10 per book
> > yourself (hopefully.)
> >
> > So you'd just have to sell 200,000 copies.
> 
> If you are aiming for $1 million royalties, and get $10 per copy, you
> have to sell 100,000 copies. Check the batteries in your calculator. :-)
> 
> A $50 cover price is unlikely to get you a $10 royalty on your first
> book, by the way.
> 
> >
> > If your book was as good as the one above you could do this.
> 
> Sadly, the book's quality isn't as important as its subject matter. If
> you want to cover your costs, write about C++. If you want to make a
> little cash besides, write about Java. If you want to make a million
> pounds, write a romance or a thriller.
> 
> >
> > It should be a slam dunk getting it published since there are no
> > comparable books like this out there for Borland C++ Builder.
> 
> I think you have seriously overestimated sales levels for technical
> books, and indeed the royalties payable on each copy sold.
> 
> That doesn't mean I wouldn't wish such a book to be written. For it to
> be what you want it to be, however, it would have to be not only a
> treatise on C++ Builder but also a high quality tutorial on C++. Such a
> book, written properly, would run to two or even three thousand pages
> and would have to retail for at least $100. It wouldn't sell terribly
> well, either, IMHO. (If it's any help, I'd buy a copy!)
> 
> > Good luck.  Love to buy one.
> 
> So would I. Good heavens! On this at least, we agree!
> 
> --
> Richard Heathfield
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html


Yes,  100,000.  Guess I had a subconscious slip there tending to 
be more realistic as to how many books one would have to sell at 
$50 to get $1 million in royalties.

Certainly more like 200,000 to get a million dollars in royalties.

Here is a very good example.  I bought this book and still have it:  
The C Primer Plus by Steven Prata.  Excellent book if you want to 
learn C programming.  And if I recall correctly, its publisher 
boasts of selling several hundred thousand copies.

It can be done.

Tally ho!

------------------------------

From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: OverWrite freeware completely removes unwanted files from hard drive
Date: Tue, 20 Feb 2001 02:13:36 -0800

Richard Heathfield wrote:
> 
> [crossposts snipped mercilessly]
> 
> Anthony Stephen Szopa wrote:
> >
> > > > > > OverWrite freeware completely removes unwanted files from hard drive
> > > > >
> > > > > I tried it and it didn't work. I got this error:
> > > > >
> > > > > ./OvrWrite.exe: Permission denied
> > > > >
> 
> <snip>
> 
> > [...] the OverWrite Program does not contain
> > source code that would generate such an error message.
> 
> I know that. How could it? After all, the OverWrite program does not
> contain source code! And that, my dear Mr Szopa, is the problem. Well,
> it's /a/ problem.
> 
> Those who have more than a dozen neurons to rub together already knew,
> of course, that the error message is in fact generated by Linux, which
> always refuses to run anything written by Szopa International. Yet
> /another/ reason to use Linux.
> 
> Of course, you could always sue the Linux distributors, for using error
> messages in the first place - I presume they too, like XOR and so on,
> were your idea originally?
> 
> --
> Richard Heathfield
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html


The little woman been giving you a rough time?

------------------------------

From: [EMAIL PROTECTED] ()
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental  
numbers?
Date: 20 Feb 2001 10:28:48 GMT

In article <xbkk6.1257$[EMAIL PROTECTED]>,
        "Paul Lutus" <[EMAIL PROTECTED]> writes:
>"Dik T. Winter" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>
>> Confusing isn't it?  But that
>> is mathematics.
>
>I agree with your enlightening post, and I appreciate your taking the time
>to write it. I came at the original post's terminology from more of a
>computer science perspective, where "enumerate all" has a different shade of
>meaning, and reasonable algorithms eventually stop.

Yes, indeed! My understanding was that, strictly speaking,  the word
'algorithm' should only be applied to a procedure that is guaranteed to
halt. If that is correct, then you should talk about a procedure to
enumerate all prime numbers rather than an algorithm.

Derek Holt.

------------------------------

From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 12:47:20 GMT

On Tue, 20 Feb 2001 06:07:29 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote, in part:

>Thanks for the pointer.  Upon closer examination, this is a method
>that I have seen before, perhaps in this newsgroup -- basically,
>establish a publicly visible stream of random bits, and the
>communicating parties select a running sample from the bit stream
>pool according to some agreed-upon rule, and use that as an XOR
>stream one-time key.  The idea is apparently that since the enemy
>cannot store all the "infinite" bit pool, he cannot keep up with
>the communicants, since he doesn't know in advance of analysis
>which of the pool bits need to be recorded.

However, in general, that sort of method is not unbreakable, for many
and obvious reasons. Since a competent cryptographic researcher claims
to have a proof that his specific scheme is unbreakable, possibly he
has indeed thought of something new.

Obviously, any random bit stream two participants are capable of
exchanging is capable of being stored by an adversary.

However: could there be a case where:

I send a message of length X bits and a larger block of random data of
length N bits.

Using a key of length A to select X bits from the random data of
length N bits,

and a key of length B to encipher those X bits,

and finally combining the X bits so produced with the message,

is there any way I can get information-theoretic security, or
something analogous to it, where either A + B is less than X, or the
same keys of length A and B are re-used for several messages X bits
long?

Would the scheme work better if I changed two steps slightly:

Using a key of length A to select X+B bits from the random data of
length N bits,

and a key of length B, XORed with B of the selected bits to encipher
the other X bits selected,

I would still think this would not work - a proof that it would would
be like a fallacious proof that a Bazeries cylinder is unbreakable
(each block has a single random displacement, and within each block,
each alphabet is different: so it's like the one-time-pad, if you
ignore correlations between corresponding alphabets in different
blocks).

John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm

------------------------------

From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 12:49:15 GMT

On Tue, 20 Feb 2001 08:52:54 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:

>There is a problem that needs to be clarified, I suppose. 
>How 'random' should the publicly visible stream of random 
>bits be? (Could they e.g. stem from PRNGs?)

Only the case where they are really random, and not from a PRNG, would
be considered in the proof. (Note that if they could come from a PRNG,
they wouldn't need to be public! So one could use public really random
bits, and XOR them with a PRNG for greater security - but since this
scheme is already supposed to be 'perfect'...)

John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm

------------------------------

From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What's a KLB-7?
Date: Tue, 20 Feb 2001 12:54:16 GMT

On Mon, 19 Feb 2001 21:49:54 -0500, Steve Portly
<[EMAIL PROTECTED]> wrote, in part:

>Apparently this machine used a 5 bit cipher, does anybody have any
>samples of PT and resulting CT?

True, the keyboard looks like a 5-level code keyboard. So instead of
being a conventional rotor machine, it was a descendant of the M-228?

But with 36-contact rotors, putting 32 signals through it and looping
back four wires is more conventional, and just as possible.

Now, with diodes or something, could I work out a way to make a rotor
machine that did both at once...

John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm

------------------------------

From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental 
number between a and b?
Date: Tue, 20 Feb 2001 12:56:33 GMT

On 19 Feb 2001 23:56:09 -0500, [EMAIL PROTECTED] (Dave Seaman)
wrote, in part:

>>The algebraic numbers are nowhere dense.

>No, the algebraic numbers are everywhere dense.  So are the
>transcendentals.

>The Cantor set is nowhere dense.

Being dense myself, I used the wrong definition of 'dense'. What is
the name of the property of having measure n over a line segment of
length n?

John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm

------------------------------


** 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 by posting to sci.crypt.

End of Cryptography-Digest Digest
******************************

Reply via email to