Cryptography-Digest Digest #384, Volume #11 Wed, 22 Mar 00 00:13:00 EST
Contents:
Re: Factoring Large Numbers - I think I figured it out! ("Dann Corbit")
Re: new Echelon article ("Leo Sgouros")
Re: root mod a prime? (d g)
Re: Factoring Large Numbers - I think I figured it out! (Paul Rubin)
key distribution/management (stanley trepetin)
Re: Card shuffling (wtshaw)
Re: Factoring Large Numbers - I think I figured it out! (Paul Rubin)
Re: new Echelon article ([EMAIL PROTECTED])
Re: Factoring Large Numbers - I think I figured it out! (stanislav shalunov)
nsa patent on new storage device (powerman powerman)
Re: Non-doublespending offline digital money? ([EMAIL PROTECTED])
Re: Factoring Large Numbers - I think I figured it out! (Johnny Bravo)
pgp key collision ("Davis Ford")
Re: Factoring Large Numbers - I think I figured it out! (Johnny Bravo)
----------------------------------------------------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: Tue, 21 Mar 2000 17:58:00 -0800
"Richard Hein" <[EMAIL PROTECTED]> wrote in message
news:IXTB4.5610$[EMAIL PROTECTED]...
> Bob, if we could talk without name calling and insults, then this might be
> more productive. I think that you could figure out an algorithm by using
> the method. And yes, patterns do exist in math and physics, that's how
> people come up with equations that can apply to different numbers. I
don't
> know why you debate that. I guess I'm stupid. But I am pretty sure
Galileo
> came up with his knowledge of movement of planets by looking at the data
> time and again to try to spot some pattern.
>
> Take elliptic curves ... that's a method used to encrypt and decrypt ... I
> don't know much about it, but it seems to me that someone had to develop
the
> method on paper or in their mind first before figuring out an algorithm
that
> describes it and can be coded. I am saying that this method is akin to
the
> elliptic curve method, but different in many ways. In time, after using
the
> method and seeing the results, one may be able to model the system using
an
> algorithm. If that happens, great.
>
> I'm surprised to hear that a ten digit number is easy to do ... that's a
> sure sign of my lack of knowledge in the subject. But it got me to this
> point, so I am not worried one bit.
>
> About patents ... of course an algorithm is not patentable ... but a
device
> that uses the method is. That's what I am trying to build. I didn't
> realize I could get this notarized ... thanks - that helps a lot - at
least
> I garnered some wisdom from this discussion.
>
> In addition, I said eventually it could be made into a microchip - first
you
> have to figure out the algorithm which models the real world methodology.
>
> And yes, I wish I could go back to school ... that would be great!
>
> Although I may only be able to factor a ten digit number, by the way, it
> would demonstrate all I need to demonstrate ... that the method will
reveal
> the solution. I would leave the advancement up to 1000 digits and more up
> to people who know much more than I do about electronics, and
cryptography.
> The speed and size of the digits is probably not the most important thing
> right now ... if I can use a pencil and paper to solve an equation then I
> can do it faster using computers. The same thing applies in this case.
>
> I will get a notarized paper sent to you as soon as I can. I think that
you
> will be surprised when you read it, because it's simple and looks very
> promising. Remember, I did say, "I think I figured it out".
Finding a solution does not mean that it has any value. In fact, we already
know how to factor any number that has factors. It just takes too long.
For instance, if I have a number of 256 digits that looks like it might be
prime, I might throw some prime testing programs at it. They may say, "It's
not prime."
Now, I *can* factor the number with many different ways. I can use elliptic
curves or number field sieve or even brute force.
But the problem is time. If it takes 10000 years to find the answer, then
the answer is not useful.
What I am trying to point out is that "a method that works" is not really
even useful unless it is also fast.
Here is a program which will factor numbers of 15 digits or less in a few
seconds:
#include<math.h>
#include<float.h>
#include<limits.h>
#include<stdlib.h>
#include<stdio.h>
typedef unsigned long ul;typedef double m;typedef void v;
#define T(f,y)(*(f+(y)/16)&(1<<(((y)%16L)/2)))
#define S(f,y)(*(f+(y)/16)|=1<<(((y)%16L)/2))
#define N 65535
#define r return
#define w while
#define z for
#define e else
#define i if
#define p printf
#define h puts
#define t sqrt
#define x exit
unsigned char d[4096]={0};char s[1024];v foo(v){ul a=1,y;w((a+=2)<N)i(!T
(d,a))z(y=3*a;y<N;y+=a<<1)S(d,y);}ul pt(ul j){i(j==1)r 0;i((j%2)==0){i(j
==2)r 1;e r 0;}e r(!T(d,j)&&j!=1);}v lf(ul n){ul j,ub;i(n==0)h("NULL");e
i(n<4)p("%lu\n",n);e{ub=(ul)(t((m)n)+1.);w(n%2==0){h("2");n>>=1;}ub=(ul
)(t((m)n)+1.);ub=ub>N?N:ub;z(j=3;j<=ub;j+=2)i(pt((ul)j))w(n%j==0){p("%l\
u\n",j);n/=j;ub=(ul)(t((m)n)+1.);}i(n>1)p("%lu\n",n);p("\n");}}v df(m n)
{m j,ub,q;if(n<0)h("-1");n=n>0.?n:-n;i(log10(n)>DBL_DIG){h("Too large");
x(EXIT_FAILURE);}i(n==0.)h("NULL");e i(n<4)p("%.0f\n",n);e{ub=t(n)+1;w(
modf(n/2,&q)==0.){h("2");n=q;}ub=t(n)+1;z(j=3;j<=ub;j+=2)i((j<=N&&pt((ul
)j))||j>N)w(modf(n/j,&q)==0){p("%.0f\n",j);n=q;i(n<ULONG_MAX){lf((ul)n);
r;}ub=t(n)+1;}i(n>1)p("%.0f\n",n);p("\n");}}int main(int c,char*o[]){foo
();i(c>1){df(atof(o[1]));}e w(fgets(s,sizeof s,stdin)!=0){df(atof(s));}r
0;}
However, this program is so laughably inefficient that scientists would
rightly ridicule you if you tried to use it for serious factoring work. If
scaled up and applied to numbers with hundreds of digits, it would take
centuries to solve what other programs can solve in minutes.
So (in other words) a method that works is not valuable. A method that
works quickly for large problems is valuable.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: "Leo Sgouros" <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Wed, 22 Mar 2000 01:57:45 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 18 Mar 2000 15:54:27 -0600, "Andy Culp" <[EMAIL PROTECTED]>
> wrote, in part:
>
> >I think that makes perfect sense, why would the government have them if
they
> >weren't worth their money? The NSA obviously has to do something useful
or
> >all of the billions of dollars in funding would be put somewhere else.
>
> They have to do something useful, but it also has to be honest work.
> Spying on terrorists, tyrants, and aggressors, however ignoble it may
> seem to be snooping at all, is honest and necessary work.
>
> Spying on honest businessmen in our allied democratic neighbors for
> the purpose of stealing from them is neither honest nor advisable, and
> hence I tend to believe the NSA's denials, because I think they and
> the U.S. government would be crazy to get involved in this sort of
> thing.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/index.html
Last night at a function in DC Director Tenet made the comment that only in
America could the leader of the intelligence community come and speak and
mingle with the citizens-he was being given an award by AHEPA and it made me
think along similar lines-but this being America, founded on business and
capitalism, I would think it would be entirely natural for the spooks to
help out business.Wrong, yes.But I think in the evolution of a world economy
it is a foregone conclusion.And it doesnt necessarily mean planting bugs in
a hotel room-the intel guys sometimes have excellent foresight and can spot
trends, and they obviously know about the new tech and its applications.I
guess the question should be how can this become a fairer process where all
businessmen could get some sort of nod or helping hand-maybe a lottery or
some other method whereby your company gets to get juicy details this week,
someone elses next(this would also mean a transparent intelligence
community-another good thing BTW).It would end up being another way to
perpetuate a spy vs spy mentality,and to tell you the truth if it was for
purposes other than murder and drugs and terror, I say lets give the spooks
something safe to do.Lord knows they screw up the dangerous stuff.
------------------------------
From: d g <[EMAIL PROTECTED]>
Subject: Re: root mod a prime?
Date: 21 Mar 2000 18:27:09 -0800
Mike Rosing <[EMAIL PROTECTED]> writes:
> Do a web search with "square roots mod p". I got 17 hits from
> google. Knuth has a method, and there's one in H. Reisle's book
> (spelling?) about primes. If you want, I'll get the page numbers
> in those books. (send me e-mail and remind me!!)
I don't know if Knuth covers Cipolla's method, which is different - it
is oblivious to the structure of Fp* unlike Tonelli/Shanks. Also, as
Silverman points out, polynomial factorization methods such as those
of Berlekamp and Cantor/Zassenhaus can always be used.
Cipolla's method and the other algorithms mentioned above are covered
in chapter 7 of Bach & Shallit's excellent book - Algorithmic Number
Theory (vol 1), MIT Press, ISBN 0-262-02405-5.
Cheers,
==
Dipankar
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: 22 Mar 2000 02:42:06 GMT
In article <J2UB4.5613$[EMAIL PROTECTED]>,
Richard Hein <[EMAIL PROTECTED]> wrote:
>Yes, you have every reason to be sceptical. There is a difference between
>sceptical and close-minded. I am not saying you are close-minded since you
>sent those RSA numbers to me. And of course, believe it when you see it ...
>but look for it first!
It's like flying saucers. I suppose if I see them, I'll believe them,
but until then I consider them unlikely enough that it's not worth
spending my time looking for them.
------------------------------
Date: Tue, 21 Mar 2000 22:19:46 -0500
From: stanley trepetin <[EMAIL PROTECTED]>
Subject: key distribution/management
Hi, I'm a graduate student at MIT. I'm writing an in-depth paper on key
distribution and management issues with email applications. Can someone
give me advice (or references to papers or people) on the most
interesting questions in this space? Technical, economic, or public
policy questions would all be relevant.
For example, I see considerable variety in current email encryption
implementations. Hushmail.com automatically exchanges keys necessary to
open up sent messages. Interosa.com forces you to contact your partner
to securely exchange keys before opening messages. Microvault.com allows
the sending of mail, and packages the keys with the note, to
automatically secure a reply without special software. (PGP does a
flavor of this as well). The GTE CyberTrust Accelerator Program installs
PKI on top of existing email desktop programs without the need for
proprietary email programs at all -- like adding a PKI layer on top of
the email system! There is also considerable incompatibility when email
clients use different encryption algorithms or different key lengths.
I'd like to understand the variety of implementations which exist today
based on the issues/problems of key distribution/management. What are
the important questions to ask?
Thank you,
Stanley
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Card shuffling
Date: Tue, 21 Mar 2000 20:37:18 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Well, let me formulate the problem independent of games. Let S be
> the sequence 1, 2, 3, ...... n. and P be a permutation of S. Can
> one give a function f(P) with range [0.0, 1.0] that characterizes
> in some reasonable way (i.e. not contrary to some common sense
> or intuition and hence be acceptable to the common people) the
> 'disordering' of P relative to S? (If such an f exists, then
> evidently f(S)=0. But how about f(P) for the rest of permutations?)
>
What you want is a hashed sequence that uses both parties as factors in
the method. Both, or an number of parties, could enter a text or random
sequence, use my hashing techniques, and have a result that all could
agree was fair, even someone cutting the deck if desired.
Yes, this could be used with any set of permuted keys, save the results
from each shuffle, using it as a starting point for the other(s).
--
To see the results of GW Bush's shaddow, visit the Valley;
notice the miserable conditions he allows to fester.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: 22 Mar 2000 03:31:18 GMT
In article <20UB4.5612$[EMAIL PROTECTED]>,
Richard Hein <[EMAIL PROTECTED]> wrote:
>Not free Paul ... for a share.
Well, since in apparently every estimation except for yours, your
invention is worthless and therefore a share of it is worthless, you
really are asking for free help.
>I am not greedy, but I would have to have a patent. I have tried to
>explain in a post that I would actually have to build a machine to do
>this. That requires knowledge I don't have ... in electronics.
Let's assume the stunningly unlikely, that your method works and is
practical. Let's also assume that a patent issues--that's less
unlikely. After all, the patent office recently granted US patent
6,025,810 for a "hyper-light-speed antenna" which "allows energy from
another dimension to accelerate plant growth" and what you're
proposing can't be that much worse. You will of course become famous
overnight by having solved a that mathemeticians have worked on for
centuries.
But, even assuming all that, how do you propose to commercialize the
invention? Where is the profit potential? Who will buy it? Who will
use it?
>You are right about one thing for sure: I only think I know. I need people
>like you to verify the truth of the situation.
Your statement in another post that you didn't even know that 10-digit
numbers can easily be factored reveals close to everything about the
situation. It's like someone claiming to have invented a revolution
in transportation and it turns out that he hasn't ever heard of automobiles.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto
Subject: Re: new Echelon article
Date: Wed, 22 Mar 2000 03:44:19 GMT
In article <
tMVB4.198$[EMAIL PROTECTED]
m>,
"Leo Sgouros" <[EMAIL PROTECTED]>
wrote:
>
> Last night at a function in DC Director Tenet made the comment that only in
> America could the leader of the intelligence community come and speak and
> mingle with the citizens-he was being given an award by AHEPA and it made me
> think along similar lines-but this being America, founded on business and
> capitalism, I would think it would be entirely natural for the spooks to
> help out business.Wrong, yes.But I think in the evolution of a world economy
> it is a foregone conclusion.And it doesnt necessarily mean planting bugs in
> a hotel room-the intel guys sometimes have excellent foresight and can spot
> trends, and they obviously know about the new tech and its applications.I
> guess the question should be how can this become a fairer process where all
> businessmen could get some sort of nod or helping hand-maybe a lottery or
> some other method whereby your company gets to get juicy details this week,
> someone elses next(this would also mean a transparent intelligence
> community-another good thing BTW).It would end up being another way to
> perpetuate a spy vs spy mentality,and to tell you the truth if it was for
> purposes other than murder and drugs and terror, I say lets give the spooks
> something safe to do.Lord knows they screw up the dangerous stuff.
>
What screw-ups are you referring to? Who
would you rather have gathering intel on the
"dangerous" stuff? Of course, for security
reasons, we are unaware of many successful
achievements by the U.S. intel community.
Consider, for example, that there are no
significant attacks against the continental
U.S. by foreign terrorists.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Factoring Large Numbers - I think I figured it out!
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Wed, 22 Mar 2000 04:08:02 GMT
Tim Gahnstr�m <[EMAIL PROTECTED]> writes:
> Richards problem right now is that he just happens to know that it
> is posible to do this magich fuel, but he doesnt have the tools.
He demonstated repeatedly that he does not understand the problem.
I don't think it would take an expert in this case to point out an error.
But even if he comes back with a description of his algorithm,
and is told what's wrong with it, he won't go away.
Have you ever talked to a person who thinks they have just proven the
last Fermat theorem? "No, this doesn't follow. Here's a
counterexample. Now go." "Yes, you might be right, but the solution
is here. I've got the idea. You're the mathematician here, you do
the technical polishing."
Just ignore him.
------------------------------
From: [EMAIL PROTECTED] (powerman powerman)
Subject: nsa patent on new storage device
Date: Tue, 21 Mar 2000 21:56:22 -0600 (CST)
http://www1.ekstrabladet.dk/visartikel.iasp?pageid=43390
or it that does not work
www.cryptome.org
any comments on this device?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Non-doublespending offline digital money?
Date: Wed, 22 Mar 2000 04:25:37 GMT
In article <
8b97bt$69d$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]>
wrote:
>
> I seem to recall that digital cash was one of the first (maybe the first?)
> application of quantum mechanics to cryptography. For exactly this
> reason: try to copy a state and you end up destroying it.
>
> I can't remember a reference. Does this ring a bell for anyone else?
>
Yes, I think you are referring to "quantum
money", an idea developed by Wiesner in the
late sixties which is the first instance of
theoretical quantum cryptography. He wrote a
paper on this in 1970 but it wasn't published
until 1983 due to a prior lack of interest in
the subject. There is a description of quantum
money and its origin in Singh's "The Code
Book". Note that quantum cryptography can
provide at minimum *partial* security for
quantum money but how much potential
security is attainable remains unknown (at
least to me).
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: Tue, 21 Mar 2000 23:13:06 -0500
On Wed, 22 Mar 2000 00:23:08 +0100, Tim Gahnstr�m
<[EMAIL PROTECTED]> wrote:
>Imagine you find a new fuel that will have no polutions and
>no cost. then you have to options.
>one you go public and get famous
>two you go get a patent and get rich.
>
>Obviously he have chosen the second way.
You are missing the point, there is no getting rich from this, there is
no commercial application. His method would be as useful as a short proof
of Fermat's Last Theorem. Interesting in a mathematical sense, but with
no commercial value other than a spot of fame for the discoverer.
>Richards problem right now is that he just happens to know
>that it is posible to do this magich fuel, but he doesnt
>have the tools.
There is no special tool for a method intended to be implemented on
microchips, any decent home computer will suffice to demonstrate the
method to everyone's satisfaction. Since he is posting to USENET I'll
assume he has access to a computer. Everything else is up to him.
>Al he is looking for is someone to have a look at his
>pressent thougts.
He is going off the deep end and saying that he can do it with a special
microchip but somehow a computer can't execute the instructions. If
anything, he is looking for gullible people to scam money from them to
build a 'prototype' that can factor a 10 digit number after some number of
months of work, then get a lot more money and spend the next ten years
living the high life while his bogus project never comes to fruition. As
has been pointed out several times, any PC can factor a few thousand 10
digit numbers in a second.
To quote him 'It's not an algorithm ... It's a methodology. It would
eventually become a microchip specific to the task.' Microchips deal in
instructions, not methodology. If he can list the instructions, any
computer can duplicate them as a program.
>Is that a reason to try to make him look like a fool???
He's doing a fine job all by himself.
--
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: "Davis Ford" <[EMAIL PROTECTED]>
Subject: pgp key collision
Date: Tue, 21 Mar 2000 23:44:57 -0500
can anyone tell me what the probability is for pgp key id collision?
tia,
davis
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: Tue, 21 Mar 2000 23:39:45 -0500
On Tue, 21 Mar 2000 18:54:05 -0500, "Richard Hein" <[EMAIL PROTECTED]>
wrote:
>I'm surprised to hear that a ten digit number is easy to do ... that's a
>sure sign of my lack of knowledge in the subject. But it got me to this
>point, so I am not worried one bit.
It has also been pointed out that the RSA 100 and 155 digit numbers have
been factored.
>About patents ... of course an algorithm is not patentable ... but a device
>that uses the method is. That's what I am trying to build. I didn't
>realize I could get this notarized ... thanks - that helps a lot - at least
>I garnered some wisdom from this discussion.
You are missing the major point of his post. You claim profit potential
in your device, that is how shares work, a share of the profits. You need
to answer the following question before you can even think a profit
potential exists.
Why will people buy the device?
Just to factor numbers? This is not going to be a large market.
>Although I may only be able to factor a ten digit number, by the way, it
>would demonstrate all I need to demonstrate ... that the method will reveal
>the solution. I would leave the advancement up to 1000 digits and more up
Not necessarily. We already have methods that can factor any number,
it just takes time in proportion to the size of the number. Your method
may work, but we already have working methods. You need to prove that
your method is fast enough to factor a 1000 digit number before we die of
old age waiting for an answer.
>to people who know much more than I do about electronics, and cryptography.
>The speed and size of the digits is probably not the most important thing
>right now ... if I can use a pencil and paper to solve an equation then I
>can do it faster using computers. The same thing applies in this case.
Means nothing if you can't do it faster than already known methods. In
theory I can factor any number given enough time. One solution is trivial,
you just test every integer up to sqrt(x). You seem to be assuming that
no one can factor any numbers at all, that is not the problem. The
problem is the speed of the factoring. If you can't do it faster than
Number Field Sieve (which is faster than Multiple Polynomial Quadratic
Sieve for numbers of larger than 115 digits) you might as well quit now.
--
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
------------------------------
** 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
******************************
