Cryptography-Digest Digest #404, Volume #11 Thu, 23 Mar 00 18:13:01 EST
Contents:
Re: Factoring Large Numbers - I think I figured it out! (Xcott Craver)
Re: implementing rot13 (Dan Day)
Re: Do you think I'm ready? What do I need? (Dan Day)
Re: Opinions? (Johnny Bravo)
Re: Open source or not. (Was: Re: Planet Poker Claims...) (Johnny Bravo)
Re: Card shuffling (DMc)
Re: NIST publishes AES3 papers (Jerry Coffin)
Re: Hashes! (newbie question) (Jerry Coffin)
Re: Prime numbers? (newbie alert) (Jerry Coffin)
Re: NIST publishes AES3 papers (Jerry Coffin)
Next Vernam variety idea. ("RecilS")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: 23 Mar 2000 22:23:27 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
>Johnny Bravo <[EMAIL PROTECTED]> wrote:
>
>: You are missing the point, there is no getting rich from this, there is
>: no commercial application. [...]
>
>Bob Silverman has also said that there's no commercial application.
>It seems to me that (say) the ability to read practically all RSA (etc)
>messages ever created ought to be worth something to somebody.
Whether or not it's "worth" something is different from whether
or not you can profit from it. First it has to be worth something
to somebody who will have to pay for it (if you patent it, you
can probably get royalties from _companies_ implementing the
algorithm in a software product; you won't get any money from
individuals who implement it themselves.) Secondly, there has
to be a pretty good number of somebodies --- after your
algorithm is out, its usefulness will quickly drop as people
stop using RSA; only people who have archives of intercepted
RSA messages will need your algorithm (see the "firstly" part.)
>Since such a factoring algorithm can be used to build and market an
>RSA-cracking machine. No doubt in America, you could get a patent on
>such an implementation.
You can probably patent the algorithm, that's not a problem.
-S
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: implementing rot13
Date: Thu, 23 Mar 2000 22:32:31 GMT
On 23 Mar 2000 01:42:10 +0100, [EMAIL PROTECTED] (Paul Schlyter) wrote:
>> And if you want to be really anal and do it in a single
>> C/C++ expression:
>>
>> for (i=0; i<strlen(string); i++)
>> {
>> if (isalpha(string[i])
>> string[i] = 'A' + (toupper(string[i])-'A'+13)%26 +
>> islower(string[i])*('a'-'A');
>> }
>
>Why not instead:
>
>for ( char *s=string; *s; s++)
> *s += isalpha(*s) ? (toupper(*s)<('A'+13))*26-13 : 0;
Cute.
Okay, the gauntlet has been thrown -- who can do it in even
fewer (non-whitespace) characters?
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Do you think I'm ready? What do I need?
Date: Thu, 23 Mar 2000 22:36:27 GMT
On Thu, 23 Mar 2000 19:00:57 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>
>Dan Day wrote:
>> Q: "Can you play the guitar"?
>> A: "I don't know -- I've never tried. Hand me a guitar and
>> I'll find out."
>> That attitude will take you farther in life than any amount of
>> classroom time. In the trite slogan of a Nike commercial,
>> "Just Do It". That applies to more than just sports.
>
>I frankly think that we have far too many instances already
>of people who don't know what they're doing going ahead and
>"just doing". That includes musically incompetent guitar players.
That rather misses the point...
The idea being espoused is not "hand me the guitar and let's
see if I can fake it after ten minutes", what was meant is
"I don't know if I'll be able to play the guitar competently
(or perhaps even brilliantly) until I make the attempt and see
how far I can go with it."
As opposed to saying, "no, I don't currently know how to play the
guitar, no use even picking one up", which is a great way to
never find out whether you've got talent (or the ability to
acquire it) or not.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Opinions?
Date: Thu, 23 Mar 2000 17:31:48 -0500
On Thu, 23 Mar 2000 13:19:22 GMT, [EMAIL PROTECTED] wrote:
>By this statements, you're reducing the notion of randomness to
>predictability.
Not exactly. In the half life of an atom there is a 50-50 chance it
will decay. There is no way to tell in advance if it will do so, an atom
fresh from a reactor core have the exact same 50-50 chance as atoms of
that type that have existed without decay for a billion years. Over the
halflife there is a 50-50 chance, and which one occurs is entirely random.
You are confusing overall probability with predictability. If I can
flip an unbiased coin a billion times, I will have a very close result in
heads and tails. This 50-50 distribution does not have any predictive
power.
>However, there's a theoretical difference. If, as an
>experiment of thought, a time machine had been invented, we would be able
>to predict the time when one single atom decays by traveling forward in
>time and observing it.
As a similar experiment of thought God is all-knowing, and all-powerful
and designed in advance every sequence that will be created when he
created the universe. Since it was designed in advance, no sequence will
ever be random. Now that the concept of randomness has been disproved, we
can return to the real world.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Crossposted-To: rec.gambling.poker
Subject: Re: Open source or not. (Was: Re: Planet Poker Claims...)
Date: Thu, 23 Mar 2000 17:41:12 -0500
On Wed, 22 Mar 2000 06:16:36 GMT, Mike Caro <[EMAIL PROTECTED]> wrote:
>I also specifically challenge the idea that "atomic decay" methods of
>random number generation are a superior solution.
Because natural atomic decay is proven to be random. If you know of a
flaw in John Bell's proof or Alain Aspect's experimental verification of
that proof, publish it and pick up your Nobel Prize in Physics. :)
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: DMc <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Thu, 23 Mar 2000 22:54:03 GMT
On Thu, 23 Mar 2000 17:20:19 GMT, [EMAIL PROTECTED] (Scott Nelson)
wrote:
> [snip]
>
>What I meant by negative property is that randomness isn't a thing,
>it's a lack of a thing. I.e. Randomness means without pattern,
>without order, lacking predictability, not repeatable, unbiased.
>
I am very glad I asked the question. I thank you very much for the
clarity of your answer.
I have numerous math dictionaries in my private collection. There
are some others I rejected, along with some regular dictionaries,
because they define randomness so poorly. None that I have, or do
not have, define randomness the same way.
>
>Worse, randomness is generally used meaning lacking all properties.
>Since there are infinitely many possible properties, testing for a
>lack of all of them is hard.
>
If you have that basic viewpoint, I can see how hard it would seem
to be.
> [snip]
>>
>>[EMAIL PROTECTED] previously wrote:
>>
>>Also, the resulting state of a riffled deck has no analysis value
>>by itself. The difference between it and the previous state is the
>>beginning of some possible analysis value.
>>
>That's why I suggested ordering the deck as the first step.
>>Choosing to focus solely on riffling extracted from a more complete
>>process of riffling, cutting, dealing, playing, card collecting, and
>>then back to riffling makes this discussion very much like determining
>>how many angels can fit on the head of a pin.
>>
>Yes, but you have to start somewhere. I chose to start with a single
>property, and how that property changes from a known state after
>shuffling. (I start with an ordered deck, and then examine the
>difference between that ordered deck, and the deck after shuffling.)
>
I agree with you that "knowing" can be a property. If so, and it is
chosen, then testing for the knowing/lack of knowing after the shuffle
would seem a more direct measure of shuffle efficiency(?).
>
>If you want to offer a more complete analysis, or a better definition,
>I'd love to see it.
>
Better definition: Shuffle is ambiguous. There are many different ways
to shuffle. In a previous post I stated I am only discussing the
riffle and the cut. These are but two of those many ways to shuffle. I
know nothing about the efficiency of those many other ways to shuffle,
nor am I interested.
Analysis completeness: My experiments up to now are focused on what is
the minimum riffling required between contract bridge deals necessary
to maintain an unbiased [fair] card deck. I started knowing about the
seven-shuffle propaganda in various literature, and having read about
what P. Dioconis thought. (I apologize for misspelling his name
before.)
I controlled for each of the five process steps I named above. I was
surprised to discover the cut was as important in the process as the
riffle.
My present conclusion based on the evidence I acquired in these
experiments is the minimum riffle is one and the minimum cut is one
in order to maintain a fair contract bridge card deck. This assumes
starting with a fair deck; that is, no person knows its order.
The next level testing would seem to be "knowing" testing. Various
contract bridge experts [they are legion, just ask them] could be
asked to specify specific cards in a deck after one riffle and one
cut of a fair deck. If their answers rise significantly above chance
over time, my present conclusion would be invalid, at least about this
group of people.
If so, the next person in line could move on to the next possible or
probable "knowing" barrier.
>
>>> [snip]
>
I will answer this last snip in a separate response posting.
[EMAIL PROTECTED]
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: NIST publishes AES3 papers
Date: Thu, 23 Mar 2000 15:56:14 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> > The participants, some of whom are maintaining proprietary rights to
> > their algorithms at present, only agreed to let the world use their
> > algorithms free of charge if they were the _sole_ winner of this.
>
> I suspect they might settle for being the "primary" winner, which would
> limit the selection of "secondary" winners to those without encumbrance.
They've already agreed to release their rights if their algorithm is
"selected for inclusion in the AES." There's no limitation on their
being "primary", "secondary", "tertiary", "recommended", or anything
else. If an algorithm is included in any way in the AES, the owner
has already released all rights to it. The agreement even specifies
that NIST is free to modify the algorithm as they see fit, and that
after submissions were closed that the submitters would NOT be free
to back out of what they'd agreed to.
Anybody who didn't like this idea simply should not have submitted an
algorithm in the first place.
> They might maintain their legal
> encumbrance but still be qualified as an approved AES candidate.
That's simply not true.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Hashes! (newbie question)
Date: Thu, 23 Mar 2000 15:56:16 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Runu Knips <[EMAIL PROTECTED]> wrote:
>
> > AFAIK SHA-1 and RIPE MD160 are the algorithms which are
> > considered secure at the moment. RIPE MD160 has been called
> > "secure for the next 10 years" by its inventors in the
> > original paper from April 1996, therefore we have time
> > until the end of 2005 :-) then we need something better.
>
> Indeed. Both can provide at most 80-bits-worth of security against an
> adversary attempting to find collisions.
Yes and no. If you're using it in a situation where a birthday
attack can be used at all, you're right. Hashes are often used in
situations where a birthday attack simply won't work.
Just for example, probably the single most common use of a
cryptographic hash is hashing a pass-phrase to produce a key. In
this situation, a birthday attack ONLY works if the adversary can do
the birthday attack ahead of time, and then get one of the people
he's trying to attack to use a pass-phrase the adversary has already
selected. The problem here, of course, is that if you allow the
adversary to select your pass-phrase, he doesn't need to do a
birthday attack: he already knows your real pass-phrase.
If the person trying to protect the data selects his/her own pass-
phrase, then a birthday attack simply won't work. The adversary now
expects to use approximately 2**159 (i.e 2**160/2) operations to find
another pass-phrase that produces the correct hash.
> I suspect that we need good fast hash functions with at least 256-bit
> outputs right now, to go with the good 128-bit block ciphers we already
> have and the public-key algorithms we use. I don't think there can be
> much argument that the hash is the weak bit in most digital signature
> algorithms at the moment. Even Eli Biham and Ross Anderson's Tiger, at
> 192 bits, doesn't seem to offer commensurate security.
That depends on whether a birthday attack is really even possible
given the situation in which you're using the hash. A sucessful
birthday attack nearly always depends on your signing the hash of
something _precisely_ as provided by somebody in a potentially
adversarial position. The solution is relatively simple: never do
that. Before you sign the hash of a document, always insist on at
least SOME minor change, and sign the hash of the revised version.
In this situation, the only way the adversary can hope to mount a
birthday attack is by foreseeing what last-minute change you might
make. If you want to attack somebody in this situation, there's one
thing you can do that _might_ help you out: if you think they're
making revisions ONLY for the sake of being the last one to make a
revision, try to force their hand: do the birthday attack, then
change something like the spelling of a word in the document in the
hope that they'll change it back to the document you've already
attacked.
Of course, this takes careful planning AND a bit of luck. If the
person you're attacking is clever at all, he'll be careful to include
at least one change he's reasoanbly certain you WON'T anticipate.
In the end, I believe the birthday attack is really a LOT less
dangerous than most people think. It tends to receive more attention
than it really deserves for the simple reason that it's
mathematically neat and basically kind of fun.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Prime numbers? (newbie alert)
Date: Thu, 23 Mar 2000 15:56:20 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>
> Would a prime number instead of an ordinary number
> be better for creating randomness?
This is a bit like asking "would water be better for creating
poetry?" Prime numbers and randomness aren't particularly closely
related. Just for example, some linear-congruential pseudo-random
number generators use a prime number as their modulus, but one that
uses a prime isn't necessarily better than one that uses a composite
and linear congruential generators are useless for most cryptographic
purposes in any case.
> Would they be better to use for keys/seeds when XOR'ing
> streams?
Better than what? You're not telling us enough for anybody to answer
your question.
> I've also understood how the RSA algorithm works
> as its explained in the crypto faq. But I still dont
> understand *why* it works, and if prime numbers are
> required for it to work...
It's _possible_ to encrypt and decrypt correctly using a pair of
composite numbers, but composites that will work this way are quite
rare; primes are much more common.
> And to those who immediately thinks I should go buy
> a book: I cant afford books at the the moment..
You might want to look at the "Handbook of Applied Cryptography",
which is available freely online. I'm sorry, but I don't have the
URL handy right now; you should be able to find it fairly easily.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: NIST publishes AES3 papers
Date: Thu, 23 Mar 2000 15:56:09 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> The participants, some of whom are maintaining proprietary rights to
> their algorithms at present, only agreed to let the world use their
> algorithms free of charge if they were the _sole_ winner of this.
Here's part of what each submitter had to agree to:
Should my submission be selected for inclusion in the AES,
I hereby agree not to place any restrictions on the use of
the algorithm intending it to be available on a worldwide,
non-exclusive, royalty-free basis.
[ ... ]
I understand that NIST will announce the selected
algorithm(s) and proceed to publish the draft FIPS for
public comment.
The second part there seems to make it _quite_ clear that multiple
algorithms may be selected. IMO, the "inclusion in the AES" language
in the first part is just short of a statement that they WOULD select
more than one algorithm. If the intent was to select only one,
they'd probably have said something like "is selected as the
algorithm for the AES" instead.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "RecilS" <[EMAIL PROTECTED]>
Subject: Next Vernam variety idea.
Date: Thu, 23 Mar 2000 18:08:34 -0500
Yes I realize you must think I'm stuck on Vernam, but I'm really just using
it to learn with. It involves simple ciphers and truth be told, I'm better
at designing comunications implementations to get keys transported securely.
I'm going to be writing a chat program soon which makes use of my algorithm
and delivery method.
Let me explain
Firstly I haven't yet decided how to get the initial key across the network,
but I'm thinking about some default encryption involving each user's IP,
screen name, hops route and Proccessor ID.
1) Program starts up and you connect to the remote user directly through
TCP/IP connection (or a central server relay)
2) As soon as the connection starts, until it ends, data is constantly
transmitted. If a message is not being sent, random data will continue the
flow. This will drastically impeed seperate message interception and the
discovery of cascading keys (one key leads to the next)
3) You type in your message and send it. Each time you send a message, the
message and a new key is encrypted and sent. Key length varies but
extreemely long keys will slow data transportation.
a) Note that the key is altered (rearrange bit order) by determining the
time of reciept plus a bit of lag time (Ping value + an arbitrary constant
usually 1-2seconds)
4) The remote computer recieves the message and instantly begins decrypting
it every second. It stops decrypting and prints the message once it detects
a percentage of common characters (you set the percentage)
5) The computer stores the recieved key, to be used in encrypting the next
message.
Since each new key is encrypted with the last key, obviously if they
intercepted the first key they might be able to decrypt it all.
The constant data flow will make this dramatically harder, but the integrity
of the first key is still the most important link in the system. It will
work very well depending on my solution for this.
Whatcha think? ;)
------------------------------
** 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
******************************
