Cryptography-Digest Digest #683, Volume #11 Tue, 2 May 00 02:13:00 EDT
Contents:
Re: factor large composite (Diet NSA)
Re: factor large composite ("Dann Corbit")
Re: A naive question ("Joseph Ashwood")
Re: factor large composite ("Dann Corbit")
Re: factor large composite (Diet NSA)
Re: Interleaving for block encryption ("Joseph Ashwood")
Re: factor large composite ("Dann Corbit")
Re: Silly way of generating randm numbers? ("almis")
Re: mod function? (Mike Kent)
Re: The Illusion of Security (Mike Kent)
----------------------------------------------------------------------------
Subject: Re: factor large composite
From: Diet NSA <[EMAIL PROTECTED]>
Date: Mon, 01 May 2000 20:14:47 -0700
I was talking about *known* methods. Can
you describe, exactly, a general version of
God's algorithm & how it would beat
Shor's? We already know *accurately*
Shor's algorithm & some of its variants.
The 7-qubit quantum computer which
Joseph Ashwood referred to can provide
the necessary first step for implementing
traditional quantum algorithms such as
Shor's. Some researchers believe that a
future large & robust enough realization
of Shor's algorithm is likely (and this is,
partly, why they continue to do research
in this area).
" V hfdt afogx nfvw ufo axb (o)(o) " - Gtnjv
====================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Mon, 1 May 2000 20:16:37 -0700
"Diet NSA" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> In article <
> [EMAIL PROTECTED]
> >, Richard Heathfield <[EMAIL PROTECTED]> wrote:
>
> >My apologies. I should have said 'billions of years, or
> billions of
> >parallel universes, whichever is more convenient'. :-)
> >
>
> Current RSA key sizes, for example, could
> be rendered obsolete by quantum
> computing (QC) in as little as, say, 30
> years. No one knows.
For that matter, a new factoring algorithm might be discovered and render
RSA obsolete tomorrow. But that has no connection whatsoever to *whether* it
will happen or not. What evidence is there that a 40 digit number can be
factored by QC in 10 years? Quantum computing and the notion of using DNA
strands or other interesting ideas may not pan out.
Factoring a number the size we have been discussing using currently feasible
technology requires Moore's law getting completely blown out of the water.
Your argument seems to boil down to "If a frog had wings, then maybe he
would not scrape his butt on the rocks."
Frogs don't have wings. But we can draw some wings on the frog and pretend
it flies. Or even jet engines. Jet powered frogs, factoring away in the
sky.
I'm not saying that huge numbers won't be factored in ten years or even that
they won't be factored tomorrow. Only that the preponderance of evidence
says that they won't and that pie in the sky ideas have yet to be
demonstrated as feasible.
> Also, the concept of
> parallel universes doesn't have to be
> invoked for QC.
Hyperbole, FCOL.
--
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: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Mon, 1 May 2000 20:12:48 -0700
The basic concept is that if you are only protecting n bits
of data, it will take an attacker at most 2^n attempts to
discover what was encrypted, call it inverse brute force if
you'd like. Given this, there is a very hard limit of
security at 56-bits, for a 56-bit encryption scheme (either
key or block). In reality unbreakable, simply should be read
as unbreakable without using brute force (I'm skipping some
other qualifications).
Joe
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> As I wrote in another post, it seems strage that in the
above the one is totally
> unbreakable, while the other is unbreakable albeit with
one weakness that
> you mentioned (in both cases message and key have 256
bits).
>
> M. K. Shen
>
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Mon, 1 May 2000 20:37:34 -0700
"Diet NSA" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I was talking about *known* methods. Can
> you describe, exactly, a general version of
> God's algorithm & how it would beat
> Shor's?
It's just a table of factorizations. The table is of infinite length and
t[i] contains a complete factorization of i.
The algorithm is O(1) in time complexity and large in space complexity,
since the factorizations become arbitrarily large as we approach infinity.
> We already know *accurately*
> Shor's algorithm & some of its variants.
Too bad it's not actually useful for anything yet.
> The 7-qubit quantum computer which
> Joseph Ashwood referred to can provide
> the necessary first step for implementing
> traditional quantum algorithms such as
> Shor's.
Here is a start on God's algorithm:
t[0] = 0
t[1] = 1
t[2] = 2
t[3] = 3
t[4] = 2*2
...
Just because we know how to do it, that does not mean it is actually useful
for anything.
> Some researchers believe that a
> future large & robust enough realization
> of Shor's algorithm is likely (and this is,
> partly, why they continue to do research
> in this area).
Some researchers believe all sorts of interesting things. Why not give a
citation where a competent research actually states that it will be
feasible.
--
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
------------------------------
Subject: Re: factor large composite
From: Diet NSA <[EMAIL PROTECTED]>
Date: Mon, 01 May 2000 20:58:17 -0700
In article <wMrP4.3040$d63.2579@client>
, "Dann Corbit" <[EMAIL PROTECTED]>
wrote:
>"Diet NSA" <[EMAIL PROTECTED]> wrote in message
>> Current RSA key sizes, for example, could
>> be rendered obsolete by quantum
>> computing (QC) in as little as, say, 30
>> years. No one knows.
>
>For that matter, a new factoring algorithm might be discovered
and render
>RSA obsolete tomorrow. But that has no connection whatsoever to
*whether* it
>will happen or not.
Yes, and this is *WHY* I wrote: "No one
knows." If you have difficulty
comprehending written English then you
might consider taking a course to brush
up.
What evidence is there that a 40 digit
number can be
>factored by QC in 10 years?
There is no significant evidence yet.
Quantum computing and the notion of
using DNA
>strands or other interesting ideas may not pan out.
Actually, quantum computing has already
"panned out", albeit at a very small scale
which is irrelevant for crypto.
>Frogs don't have wings.
Now you are starting to catch on to
reality.
Only that the preponderance of evidence
>says that they won't and that pie in the sky ideas have yet to
be
>demonstrated as feasible.
What basis do you have for suggesting
that QC is a "pie in the sky idea"? You
seemingly have little knowledge of the
subject.
>
>> Also, the concept of
>> parallel universes doesn't have to be
>> invoked for QC.
>
>Hyperbole, FCOL.
I don't know what "FCOL" stands for, but
if you do not believe what I wrote (above)
then try reading this paper for yourself,
entitled, "A QC needs only one universe" :
http://arxiv.org/abs/quant-ph/0003084
" V hfdt afogx nfvw ufo axb (o)(o) " - Gtnjv
====================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Date: Mon, 1 May 2000 20:36:46 -0700
I suppose if you were to add the extra stipulation that
there be no realizable guessing technique where given x bits
of plaintext, one could not guess the 64-x remaining bits of
plaintext, there is a possibility for a an increase
security. However if there is a technique of guessing the
remaining bits from having only a few of the bits of each
block, there is obviously llittle to be gaines this way, and
it would probably be more secure to simply encrypt the
blocks as they stand in groups of 64.
Joe
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Mon, 1 May 2000 21:22:50 -0700
"Diet NSA" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> In article <wMrP4.3040$d63.2579@client>
> , "Dann Corbit" <[EMAIL PROTECTED]>
> wrote:
>
> >"Diet NSA" <[EMAIL PROTECTED]> wrote in message
>
> >> Current RSA key sizes, for example, could
> >> be rendered obsolete by quantum
> >> computing (QC) in as little as, say, 30
> >> years. No one knows.
> >
> >For that matter, a new factoring algorithm might be discovered
> and render
> >RSA obsolete tomorrow. But that has no connection whatsoever to
> *whether* it
> >will happen or not.
>
>
> Yes, and this is *WHY* I wrote: "No one
> knows." If you have difficulty
> comprehending written English then you
> might consider taking a course to brush
> up.
No one includes yourself, obviously.
>
> What evidence is there that a 40 digit
> number can be
> >factored by QC in 10 years?
>
>
> There is no significant evidence yet.
>
>
> Quantum computing and the notion of
> using DNA
> >strands or other interesting ideas may not pan out.
>
>
> Actually, quantum computing has already
> "panned out", albeit at a very small scale
> which is irrelevant for crypto.
Exactly.
>
> >Frogs don't have wings.
>
>
> Now you are starting to catch on to
> reality.
>
>
> Only that the preponderance of evidence
> >says that they won't and that pie in the sky ideas have yet to
> be
> >demonstrated as feasible.
>
>
> What basis do you have for suggesting
> that QC is a "pie in the sky idea"? You
> seemingly have little knowledge of the
> subject.
What useful results have been created as far as factoring large numbers with
QC? If there are none, then it is "pie-in-the-sky"
> >
> >> Also, the concept of
> >> parallel universes doesn't have to be
> >> invoked for QC.
> >
> >Hyperbole, FCOL.
>
>
> I don't know what "FCOL" stands for, but
> if you do not believe what I wrote (above)
> then try reading this paper for yourself,
> entitled, "A QC needs only one universe" :
>
> http://arxiv.org/abs/quant-ph/0003084
You obviously don't know what hyperbole means either.
--
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: "almis" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Mon, 1 May 2000 23:32:01 -0500
Dave Ashley wrote in message <8el2ic$8qk$[EMAIL PROTECTED]>...
|
|> Is this completely preposterous?
|>
|>
|Let's generalize your idea slightly and just say that we are going to
|take some arbitrary irrational number (our choices there are algebraic
|or transcendental, let's assume transcendental), figure out a bunch of
|digits, and use those digits as random numbers.
|
|Let's say that we are going to use some little-known transcendental,
|like e^pi or pi^e (only one of those is proved transcendental, the other
|may or may not be, I forget which is which).
|
|Let's ignore the issue of deliberate errors.
|
|Is this a suitable OTP? Are these digits random?
|
|That question is out of my league.
|
|There are really two questions here:
|
|a)Do the numbers meet statistical and other tests of randomness?
|
|b)Is there a way for someone to reproduce the series?
|
|I believe this will pass (a) but not (b). If you introduce "random"
|mistakes in generating the sequence, it may pass (b).
|
|Interesting question, but out of my league.
|
|I recommend coin-tossing.
|
|Dave.
|
|--
|-------------------------------------------------
|Dave Ashley, [EMAIL PROTECTED]
|
|
|Sent via Deja.com http://www.deja.com/
|Before you buy.
As this question is also beyond my league let me present a small
excerpt from a paper written by a group of people who think they know.
From: Cryptography Based on Transcendental Numbers; Pieprzyk, Ghodosi,
Charnes and
Safavi-Naini:
"...An attractive feature of the reals is that they can represent any
(infinite or
finite) sequence of integers. Consider an experiment in which an unbiased
coin
is flipped an `infinite' number of times. It is clear that the resulting
random
sequence is equivalent to some real number. Obviously, this sequence (the
real)
must not be either a rational or algebraic number (see Section 3.1), as in
both
cases a finite subsequence uniquely determines the rest of the (infinite)
sequence.
All infinite sequences of truly random integers fall into the broad class of
tran�
scendentals. Algebraic irrationals may look `random' but their `randomness'
is
limited to a finite subsequence.
Borel [3] introduced the notion of normal reals. A real is called to be
normal
with respect to the base p if for any natural number k all p k possible
strings of
length k occur with equal probability."
So it looks like trancendentals would pass your test (a).
(but not all, as some trancendentals, those involving arccos, arcsin and
log,
are susceptible to the LLL algorithm.)
As for your test (b).
Let's generate some long sequence of digits from the decimal expansion of
a trancendental number such as a^(Sqrt(b)).
I do not know the answer (except intuitivly) but the question is:
Is it easier to determine the a and b of this number, from the sequence,
than it is to determine, given c, the a and b of c=a*b where a and b are
prime?
------------------------------
From: Mike Kent <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: mod function?
Date: Tue, 02 May 2000 05:23:05 GMT
Mok-Kong Shen wrote:
>
> [EMAIL PROTECTED] wrote:
> ...
> > In the first case, we're talking about a function with two arguments
> > that returns a result of the same type as the operands.
> >
> > In the second case we're talking about a function with three arguments
> > that returns a boolean result.
>
> Thanks for the clarification. I am afraid that the three arument mod
> function is at least largely unknown (not previously used) in mathematics
> and other branches of natural sciences.
The function described is the characteristic function of
the relation, a standard construct in mathematics dating
back to the early days of the explicit development of set
theory ... at least 85 years.
------------------------------
From: Mike Kent <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: The Illusion of Security
Date: Tue, 02 May 2000 05:37:15 GMT
Diet NSA wrote:
> This is a good point but I was hoping that someone might know of
> a proof or disproof of whether, in the general case, a nonlinear
> function can be composed of a finite number of linear functions.
Can a nonlinear function (in this context) be composed from
*two*
linear functions? If not, that is if for your combining method
"#",
f#g is linear whenever f, g are linear, then f#(g#h) and (f#g)#h
are
linear for linear f,g,h and a straightforward induction
establishes
the linearity for any finite combination.
------------------------------
** 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
******************************
