31 expanded posts ยท every known parent and child
Hi everybody, I was wondering if anyone is aware of a function or test which would allow a person to feed PGP or other RSA algorithm a test key and then look at the result and determine if the key was greater or lesser than the actual key? I am looking through several books and so far have come up with nada. I was hoping that somebody more familiar w/ the field would offer a suggestion. Thanks for you help ahead of time...
On Fri, 17 Jun 1994, Jim choate wrote:
> I was wondering if anyone is aware of a function or test which would allow
> a person to feed PGP or other RSA algorithm a test key and then look at
> the result and determine if the key was greater or lesser than the
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> actual key?
^^^^^^^^^^
What do you mean by "greater or lesser than the actual key"? If you mean
number of bits you can do a simply file size comparison, if you mean
binary numerical value a simple c program _should_ be able to handle that
without any trouble I think.... although maybe you would need to include
some of those 'big number' routines I keep hearing about... and you would
have to strip off any header info before computing.
Happy Hunting, -Chris.
______________________________________________________________________________
Christian Douglas Odhner | "The NSA can have my secret key when they pry
cdodhner@indirect.com | it from my cold, dead, hands... But they shall
pgp 2.3 public key by finger | NEVER have the password it's encrypted with!"
cypherpunks WOw dCD Traskcom Team Stupid
Key fingerprint = 58 62 A2 84 FD 4F 56 38 82 69 6F 08 E4 F1 79 11
------------------------------------------------------------------------------> What do you mean by "greater or lesser than the actual key"? If you mean > number of bits you can do a simply file size comparison, if you mean > binary numerical value a simple c program _should_ be able to handle that > without any trouble I think.... although maybe you would need to include > some of those 'big number' routines I keep hearing about... and you would > have to strip off any header info before computing. > > Happy Hunting, -Chris. > What I am looking at is a way to do binary searches in the key space w/ a function that would look at a test key and the result of running RSA on it and then tell me the relative magnitude between the real key and the test key. What this means is that I could take a cypher-text and attempt a de-crypt w/ some conveniently large number and then go up or down from there till I find it. The advantage of this approach is that it allows one to search the key-space w/o having to test each and every possibility. This would significantly(!) reduce the time to crack...
Jim choate says: > What I am looking at is a way to do binary searches in the key space w/ a > function that would look at a test key and the result of running RSA on > it and then tell me the relative magnitude between the real key and the > test key. And you think no one would have noticed such a thing before. I can pretty much hint to you that such a thing can't really be done in log base 2 of n time in the sense that I believe I can prove that any algorithm that did that would have to involve none of the basic four arithmetic operations on the numbers in question. (Algorithms involving no arithmetic on the numbers are still possible, but intuitively quite unlikely.) Perry
> > And you think no one would have noticed such a thing before. > Is a possibility...especially since I can find no reference to it or why it won't work. > I can pretty much hint to you that such a thing can't really be done > in log base 2 of n time in the sense that I believe I can prove that > This is a joke right? Why in the world should the base have a damn thing to do with the algorithm? A number is a number last time I checked. any algorithm that did that would have to involve none of the basic > four arithmetic operations on the numbers in question. (Algorithms > involving no arithmetic on the numbers are still possible, but > intuitively quite unlikely.) > Sorry, I don't follow your reasoning here at all. Could you clarify? As far as I am concerned if it could be done w/ a neural network, or boolean algebra (course if no arithmetic ops no logic I guess), or even a fuzzy algorithm (the original impetus to this line, I was looking at "close enough" algorithms for a robot project I am in the middle of. ) would be ok by me. Seems to me though that if one looks at the results of the operation one could glean some sort of magnitude info out of the errors... > Perry >
Jim choate says: > > > > And you think no one would have noticed such a thing before. > > > Is a possibility...especially since I can find no reference to it > or why it won't work. You can't find a reference in the library on why you can't build a machine that cracks DES by repeatedly trying the digitized sound tracks of porno films, either. Maybe you should try that -- who knows, it might work. > > I can pretty much hint to you that such a thing can't really be done > > in log base 2 of n time in the sense that I believe I can prove that > > > This is a joke right? Why in the world should the base have a damn thing > to do with the algorithm? Ahem. Perhaps you should have kept awake in school. Log base 2 of a number just means the number of bits in it. > > any algorithm that did that would have to involve none of the basic > > four arithmetic operations on the numbers in question. (Algorithms > > involving no arithmetic on the numbers are still possible, but > > intuitively quite unlikely.) > > > Sorry, I don't follow your reasoning here at all. Could you clarify? It is very unlikely to me that you can factor a number in time smaller than you can square it. Thats the point I'm trying to make. Sorry to burst your bubble. Oh, I'm sure you'll come back with some silly comment on "what does squaring the number have to do with anything" or some similar crud. > As far as I am concerned if it could be done w/ a neural network, Oh, god. Neural networks have been invoked. As we know, neural networks are magical. They are always the answer. After all, we have a huge number of complex mathematical proofs out there that have been solved with neural nets -- why, the Reiman Hypothesis was recently proved by one, wasn't it? Or was that the exact measurement of Dan Quayle's IQ -- its so easy to confuse them. I tell you what, Jim. I'll pay you $10,000 if you can come up with an algorithm that factors numbers or even just breaks RSA in O(log(n)) time or less (where n is the length of the number being factored or the public key). I'd offer more, but it would be cruel. If you don't know what the notation O(f(n)) means, please don't come back asking. Perry
> > You can't find a reference in the library on why you can't build a > machine that cracks DES by repeatedly trying the digitized sound > tracks of porno films, either. Maybe you should try that -- who knows, > it might work. > I see no reason to expect such a approach to work. > > > I can pretty much hint to you that such a thing can't really be done > > > in log base 2 of n time in the sense that I believe I can prove that > > > > > This is a joke right? Why in the world should the base have a damn thing > > to do with the algorithm? > > Ahem. Perhaps you should have kept awake in school. Log base 2 of a > number just means the number of bits in it. > I understand what you are saying, what I am saying is that factoring is not an issue. I am not factoring anything. > > > any algorithm that did that would have to involve none of the basic > > > four arithmetic operations on the numbers in question. (Algorithms > > > involving no arithmetic on the numbers are still possible, but > > > intuitively quite unlikely.) > > > > > Sorry, I don't follow your reasoning here at all. Could you clarify? > > It is very unlikely to me that you can factor a number in time smaller > than you can square it. Thats the point I'm trying to make. Sorry to > burst your bubble. Oh, I'm sure you'll come back with some silly > comment on "what does squaring the number have to do with anything" or > some similar crud. > see comment above comment above relating to factoring... > > As far as I am concerned if it could be done w/ a neural network, > > Oh, god. Neural networks have been invoked. As we know, neural > networks are magical. They are always the answer. After all, we have a > huge number of complex mathematical proofs out there that have been > solved with neural nets -- why, the Reiman Hypothesis was recently > proved by one, wasn't it? Or was that the exact measurement of Dan > Quayle's IQ -- its so easy to confuse them. > Perry, I have been using neural networks in both software and hardware for several years now. I am well aware of what they can and can't do. Could we please get off this personal attack shit?.... I am interested in discussing a particular idea that I had relating to RSA and comparing keys, not what your personal opinion of me or my idea is. If you don't like it how about not responding to any of my posts or putting me in your kill file.... Ad hominim attacks reflect more on you than me... > I tell you what, Jim. I'll pay you $10,000 if you can come up with an > algorithm that factors numbers or even just breaks RSA in O(log(n)) > time or less (where n is the length of the number being factored or > the public key). I'd offer more, but it would be cruel. If you don't > know what the notation O(f(n)) means, please don't come back asking. > Perry, see the above comments. > Perry >
> > I tell you what, Jim. I'll pay you $10,000 if you can come up with an > algorithm that factors numbers or even just breaks RSA in O(log(n)) > time or less (where n is the length of the number being factored or > the public key). I'd offer more, but it would be cruel. If you don't > know what the notation O(f(n)) means, please don't come back asking. > > Perry > Ok Perry, you are on. When I recieve a certified letter from your lawyer with the appropriate paperwork detailing where the $10k is being held in escrow I will have a certified letter sent to you aknowledeing receipt of it. Short of that you are blowing smoke...
Jim choate says: > > > > I tell you what, Jim. I'll pay you $10,000 if you can come up with an > > algorithm that factors numbers or even just breaks RSA in O(log(n)) > > time or less (where n is the length of the number being factored or > > the public key). I'd offer more, but it would be cruel. If you don't > > know what the notation O(f(n)) means, please don't come back asking. > > Ok Perry, you are on. When I recieve a certified letter from your lawyer > with the appropriate paperwork detailing where the $10k is being held > in escrow I will have a certified letter sent to you aknowledeing > receipt of it. Short of that you are blowing smoke... Why should *I* do it? Thats time and expense for me. If you are so sure of yourself, feel free to have your attorneys write up anything you like. If it looks reasonable, I'll happily sign. I won't put money in escrow, though, as "forever" is a long time to have my cash tied up. Perry
Perry E. Metzger, who is evidently having a bad hair day, said
the following not very nice things to Jim Choate:
> Who cares what you think you are talking about? You haven't
> shown much common sense thus far.
> You can't find a reference in the library on why you can't
> build a machine that cracks DES by repeatedly trying the
> digitized sound tracks of porno films, either. Maybe you
> should try that -- who knows, it might work.
> Ahem. Perhaps you should have kept awake in school. Log
> base 2 of a number just means the number of bits in it.
In the words of Rodney King, "Can't we all just get along?"
Perry further comments:
> If I have an algorithm that will take any arbitrary RSA key
> and produce the private key by a mechanism such as the one
> you propose, you are (almost certainly) proposing an
> algorithm that will factor arbitrary numbers that are a
> product of two primes.
This is likely true. However, it does not necessarily follow
that such an algorithm will be any faster than current methods of
factoring and might very well be a good deal slower.
What you seem to be overlooking is that the function Jim
proposes, which tells the numerical order of two keys from an
examination of the results of using them, is probably an
exponential time algorithm itself as a function of keysize.
Performing such an algorithm log2(n) times does not yield an
algorithm which is O(log2(n)) in computational complexity, unless
Jim's magic function happens to be hardwired into your CPU and
executes in a constant of clock cycles regardless of its
operands.
> I'm afraid that given such a function, I can derive the
> original key within log[base2](n) operations.
Your fears are unfounded. :)
--
Mike Duvos $ PGP 2.6 Public Key available $
mpd@netcom.com $ via Finger. $Mike Duvos says: > > If I have an algorithm that will take any arbitrary RSA key > > and produce the private key by a mechanism such as the one > > you propose, you are (almost certainly) proposing an > > algorithm that will factor arbitrary numbers that are a > > product of two primes. > > This is likely true. However, it does not necessarily follow > that such an algorithm will be any faster than current methods of > factoring and might very well be a good deal slower. Ahem. He was proposing a mechanism that will work in log(n) time. All current known methods are subexponential. As you SHOULD know, a log function will eventually be smaller than a subexponential one if you only let N grow large enough. This is baby complexity theory. I find it astonishing that I should even have to mention it. > What you seem to be overlooking is that the function Jim > proposes, which tells the numerical order of two keys from an > examination of the results of using them, is probably an > exponential time algorithm itself as a function of keysize. Thats not what he was proposing. Obviously one can build such an algorithm given a factoring algorithm, and we know of exponential factoring algorithms. That wasn't the idea. His notion was that there might be a CHEAP algorithm to do this. Perry
(Cypherpunks added to the dist. list, against my better judgment.) > You can't find a reference in the library on why you can't build a > machine that cracks DES by repeatedly trying the digitized sound > tracks of porno films, either. Maybe you should try that -- who knows, > it might work. Perry, please do *not* reveal more about this method. You are "blowing" my new method. The soundtrack to "Debbie Does Fort Meade" is apparently the "back door" to DES. > Oh, god. Neural networks have been invoked. As we know, neural > networks are magical. They are always the answer. After all, we have a > huge number of complex mathematical proofs out there that have been > solved with neural nets -- why, the Reiman Hypothesis was recently > proved by one, wasn't it? Or was that the exact measurement of Dan > Quayle's IQ -- its so easy to confuse them. Riemann's Extenuating Continuation Hypothesis was actually proved with "fractal analysis" and "genetic programming" techniques, both of which are much more trendy than outdated charlatanism like "neural nets" (Intel just cancelled its Ni10000 neural net chip, presumably to more into fuzzy logic and quantum disambiguation...can aptical foddering be the Next Big Thing?). --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."
> > I can pretty much hint to you that such a thing can't really be done > > in log base 2 of n time in the sense that I believe I can prove that > > > This is a joke right? Why in the world should the base have a damn thing > to do with the algorithm? A number is a number last time I checked. I think you misunderstand. Perry and I are talking about the algormithm (If it exists) being O(log_2(n)). That is, "log base 2 of n". This means that the time taken is proportional to the log to the base two of the number of keys. Fascinating as this speculation is, I see no way to craft such an algorithm. The nature of the modular space makes "larger" and "smaller" difficult to distinguish.
From: SINCLAIR DOUGLAS N <sinclai@ecf.toronto.edu>
Date: Fri, 17 Jun 1994 11:55:01 -0400
Perry and I are talking about the algormithm (If it exists) being
O(log_2(n)). That is, "log base 2 of n". This means that the
time taken is proportional to the log to the base two of the
number of keys.
Actually, for a brief moment there, I thought that Jim choate might
have a partial clue, i. e. that he was pointing out that O(log2 n) is
equivalent to O(ln n), O(log10 n), or whatever base you want.
Rick> > I think you misunderstand. Perry and I are talking about the > algormithm (If it exists) being O(log_2(n)). That is, "log base 2 of n". > This means that the time taken is proportional to the log to the base > two of the number of keys. > > Fascinating as this speculation is, I see no way to craft such > an algorithm. The nature of the modular space makes "larger" > and "smaller" difficult to distinguish. > I have made submission of a short text which details my thoughts relating to a mod function attack. I am under no illusion about the complexity of mounting a factor attack. I do see the mod function as the next natural hole to look at the algorithm through. I can find no work relating to periodicities in the mod function and it occurs to me that such relationships might point the way...
Though this is starting to get tedious, I'll do my pedantic part and point out that O(log_2(n)) == O(log_k(n) * C) == O(log_k(n)); the log base doesn't matter in Big O Land. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
> I was wondering if anyone is aware of a function or test which would allow > a person to feed PGP or other RSA algorithm a test key and then look at > the result and determine if the key was greater or lesser than the > actual key? I hope not. If such a thing existed (if I understand your description correctly) RSA could be cracked by a binary search of keyspace. The search would be O(log(n)), meaning it would be directly linear with the number of bits in the key.
> > I hope not. If such a thing existed (if I understand your description > correctly) RSA could be cracked by a binary search of keyspace. The > search would be O(log(n)), meaning it would be directly linear with > the number of bits in the key. > Exactly. If you (or anyone else comes across anything that even looks remotely interesting would appreciate knowing about it).
Jim choate says: > > I hope not. If such a thing existed (if I understand your description > > correctly) RSA could be cracked by a binary search of keyspace. The > > search would be O(log(n)), meaning it would be directly linear with > > the number of bits in the key. > > > Exactly. > > If you (or anyone else comes across anything that even looks remotely > interesting would appreciate knowing about it). I could believe some sort of amazing mathematical breakthrough that produced a factoring algorithm that was polynomial in N. The notion that one will show up thats not merely polynomial but actually logarithmic in N is, I would say, in the "beyond pipe dream" state. I might believe something like that showing up someday -- stranger things have happened -- but I have an incredible amount of trouble believing that one exists now and has merely been overlooked by people smart enough to find an amazing result and too stupid to know what their result implied. Perry
> > I could believe some sort of amazing mathematical breakthrough that > produced a factoring algorithm that was polynomial in N. The notion > that one will show up thats not merely polynomial but actually > logarithmic in N is, I would say, in the "beyond pipe dream" state. I > might believe something like that showing up someday -- stranger > things have happened -- but I have an incredible amount of trouble > believing that one exists now and has merely been overlooked by people > smart enough to find an amazing result and too stupid to know what > their result implied. > > Perry > > I am *NOT* talking about factoring anything. Perhaps this is why you are having a problem understanding what I am asking. I don't care what the original key is, simply am I above it or below it. I don't see this as a 1 to 1 with factoring large digit numbers. I am less than convinced by this line of reasoning, if somebody has looked at it why is there no mention in the texts on number theory or crypto that I have access to? I am no expert and have not read all the texts in their entirety, too busy building rockets and working on my own internet feed, which is why I asked if anyone could point me to some prior work. I myself find it hard to believe that such could be possible but one thing is certain about life, it isn't. Take care...
In message <199406171835.NAA09573@zoom.bga.com>you write: > I am *NOT* talking about factoring anything. Perhaps this is why you > are having a problem understanding what I am asking. I don't care what > the original key is, simply am I above it or below it. I don't see this > as a 1 to 1 with factoring large digit numbers. Lets try a game: I'm thinking of a number, lets call it my private factor. I tell you that it is less than some other number, which we'll call my public key. For any number you choose, I'll tell you whether your choice is above or below my private factor. How long will it take you to guess my factor? Lets try. my public key is 24. Is the factor above 10? No. Is the factor above 5? Yes. Is the factor above 7? No. Is it 6? Yes. And look: 24 / 6 = 4 ! You guessed my private key, and you happen to have factored my public key at the same time! Wow! You may not think that you are talking about factoring, but factoring is a subset of what you are discussing.
> > Lets try a game: > > I'm thinking of a number, lets call it my private factor. > > I tell you that it is less than some other number, which we'll call my > public key. > > For any number you choose, I'll tell you whether your choice is above or > below my private factor. > > How long will it take you to guess my factor? > > Lets try. my public key is 24. > > Is the factor above 10? No. > Is the factor above 5? Yes. > Is the factor above 7? No. > Is it 6? Yes. > > And look: 24 / 6 = 4 ! You guessed my private key, and you happen to have factored > my public key at the same time! Wow! > You only found a single set of factors for your public key (ie 3,8 also work) and if I had asked "is the number 6?" as my first question then I would have had it in 1 single guess which does *NOT* qualify as factoring your key. > You may not think that you are talking about factoring, but factoring is a > subset of what you are discussing. > the fact it is a subset of what I am talking about means that there are some issues (and possibly an algorithm or two) that are outside of the purvue of a discussion limited to simply factoring. The horizon has been expanded.
In message <199406171911.OAA11449@zoom.bga.com>you write: > You only found a single set of factors for your public key (ie 3,8 also work) > and if I had asked "is the number 6?" as my first question then I would have > had it in 1 single guess which does *NOT* qualify as factoring your key. Of course it qualifies. No matter how a key gets broken, its broken. The point is that if a function exists which will tell you if a given number is larger than the RSA private key, that function can be used as a factoring algorithm. > the fact it is a subset of what I am talking about means that there are some > issues (and possibly an algorithm or two) that are outside of the purvue of > a discussion limited to simply factoring. The horizon has been expanded. No, what it means is that you would have to break most of number theory, and common sense, before having to worry about such a function. The risk of exploding in the vacuum caused by all of the molecules in the air of this room suddenly moving to the far corner is far higher than the chance of such a function existing.
> > Of course it qualifies. No matter how a key gets broken, its > broken. The point is that if a function exists which will tell you if > a given number is larger than the RSA private key, that function can > be used as a factoring algorithm. > I have to disagree. What I am asking is a binary question, not one of magnitude. I never care what the magnitude is. Don't want to know it. Will give it away unopened if I do get it. If all you know is 1/0 then you can't use it to factor the number. The other aspect of your method is, yes it can give you some of the factors, but it has no guarantee that you will find all of them. If your algorithm can'g guarantee it finds all of them every time then it can't be positively used to factor number. > No, what it means is that you would have to break most of number > theory, and common sense, before having to worry about such a > function. The risk of exploding in the vacuum caused by all of the > molecules in the air of this room suddenly moving to the far corner is > far higher than the chance of such a function existing. > To each their own (opinion). I am not breaking anything, I *am* asking for a reference. There seems to be a particular sub-set of prima donnas on c-punks who feel it is their duty to stipulate what kinds of questionsss can be asked and how much one has to know to ask them. I have only one other question for these folks, do you work for the government or the church?
Jim choate says: > I am *NOT* talking about factoring anything. Who cares what you think you are talking about? You haven't shown much common sense thus far. If I have an algorithm that will take any arbitrary RSA key and produce the private key by a mechanism such as the one you propose, you are (almost certainly) proposing an algorithm that will factor arbitrary numbers that are a product of two primes. I can't prove that right now -- not even sure that I can prove it right now. However, there are lots of people who's intuitions likely agree with mine. Most people believe RSA is probably equivalent to factoring. > I don't care what the original key is, simply am I above it > or below it. I'm afraid that given such a function, I can derive the original key within log[base2](n) operations. Perry
Jim choate <ravage@bga.com> writes:
> I was wondering if anyone is aware of a function or test
> which would allow a person to feed PGP or other RSA
> algorithm a test key and then look at the result and
> determine if the key was greater or lesser than the actual
> key?
This is an approach that I haven't heard of before. If one could
determine the numerical ordering of two different keys used to
RSA-encrypt the same piece of plaintext by examining the
ciphertext, one could easily break RSA by a binary search of the
keyspace.
Given two moduli N1 and N2, and some plaintext P, and PGP's
favorite encryption exponent, 17, you need to determine if
N1 < N2 by examining P^17 MOD N1 and P^17 MOD N2. Although this
is only a one-bit function, it clearly depends upon P in a very
complicated way. Since P is unknown and deliberately made random
in practical RSA implementations, I am not sure such an attack
shows much promise. I would guess that this would be at least as
complicated as solving an RSA or discrete log problem directly.
--
Mike Duvos $ PGP 2.6 Public Key available $
mpd@netcom.com $ via Finger. $> > This is an approach that I haven't heard of before. If one could > determine the numerical ordering of two different keys used to > RSA-encrypt the same piece of plaintext by examining the > ciphertext, one could easily break RSA by a binary search of the > keyspace. > I also have found no info on it, surprises me... > Given two moduli N1 and N2, and some plaintext P, and PGP's > favorite encryption exponent, 17, you need to determine if > N1 < N2 by examining P^17 MOD N1 and P^17 MOD N2. Although this > is only a one-bit function, it clearly depends upon P in a very > complicated way. Since P is unknown and deliberately made random > in practical RSA implementations, I am not sure such an attack > shows much promise. I would guess that this would be at least as > complicated as solving an RSA or discrete log problem directly. > I would agree with you if we talk about a single P, however I suspect that if one looks at a sequence of P's in a message that there might be some analysis that could be done relating to the residuals. If you take into account the regularity (periodicity?) of english text then it seems to me that you could make some form of 1-1 mapping of the P's in a cypher-text to the plain-text. If you have any other thoughts on it would appreciate them... > -- > Mike Duvos $ PGP 2.6 Public Key available $ > mpd@netcom.com $ via Finger. $ > >
Jim choate says: > I was wondering if anyone is aware of a function or test which would allow > a person to feed PGP or other RSA algorithm a test key and then look at > the result and determine if the key was greater or lesser than the > actual key? Of course you haven't seen such a thing. If factoring RSA keys requires exponential time, such an algorithm is obviously not possible. Were it possible, you could factor in time proportional to the the number of bits in the key. Anyone who had such a function would either be famous or wouldn't be talking. Perry
> > > Of course you haven't seen such a thing. If factoring RSA keys > requires exponential time, such an algorithm is obviously not > possible. Were it possible, you could factor in time proportional to > the the number of bits in the key. Anyone who had such a function > would either be famous or wouldn't be talking. > > Perry > How about some evidence on it? I see no reason to compare taking a key and determining if it is too large or too small as being necessarily equivalent to factoring a large number. I do not need to know the number exactly to determine its relative magnitude. NSA doesn't say much... I have found no evidence so far in my search for such a methodoligy, as a matter of fact I have found no evidence that anyone has ever even looked at such a scheme. If you know something I haven't been able to find then pleas enlighten me so I can move on to other more worthy things to play with... Thanks for the feedback...
I said: > > Of course you haven't seen such a thing. If factoring RSA keys > > requires exponential time, such an algorithm is obviously not > > possible. Were it possible, you could factor in time proportional to > > the the number of bits in the key. Anyone who had such a function > > would either be famous or wouldn't be talking. Jim choate says: > How about some evidence on it? I see no reason to compare taking a key > and determining if it is too large or too small as being necessarily > equivalent to factoring a large number. Its called "binary search". You were supposed to learn it in your intro to computer science class. Lets play the guessing game, shall we? Its much like twenty questions, only that just works for twenty bit things or less. We know that we have a big number. If you give me a function that tells me one bit (greater or not greater) for every guess, I can get a bit of the number. After a short time, I'll know the number -- the time is exactly the number of bits in the number (that is, the log base 2 of the number.) Perry
> > Jim choate says: > > How about some evidence on it? I see no reason to compare taking a key > > and determining if it is too large or too small as being necessarily > > equivalent to factoring a large number. > > Its called "binary search". You were supposed to learn it in your > intro to computer science class. > > Lets play the guessing game, shall we? Its much like twenty questions, > only that just works for twenty bit things or less. We know that we > have a big number. If you give me a function that tells me one bit > (greater or not greater) for every guess, I can get a bit of the > number. After a short time, I'll know the number -- the time is > exactly the number of bits in the number (that is, the log base 2 of > the number.) > > Perry > I am well aware of how to do a binary search. I have been programming since '76. The question I have is not how to do the search but if there is a way to feed a RSA fake keys in such a way that I can determine the relative magnitude of the difference in the key, not even the exact difference. On another note, ad hominim resoning does not impress me. If you would like to discuss my idea that is fine. It has no relation to me personaly.