Cryptography-Digest Digest #920, Volume #13 Fri, 16 Mar 01 18:13:01 EST
Contents:
Re: Factoring RSA (br)
Re: Factoring RSA (br)
Re: Q: IP (Ben Cantrick)
Re: NTRU - any opinions (Paul Rubin)
Re: An extremely difficult (possibly original) cryptogram (Jim Gillogly)
Re: How to eliminate redondancy? (SCOTT19U.ZIP_GUY)
Re: Factoring RSA (Jeffrey Williams)
Re: Factoring RSA ("Dann Corbit")
Re: Q: IP (Vernon Schryver)
Re: PKI and Non-repudiation practicalities (Anne & Lynn Wheeler)
Re: Factoring RSA (br)
Re: Factoring RSA ("Tom St Denis")
----------------------------------------------------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 16:07:04 -0400
You wrote :
"I can't say that I really understand how your algorithm works, since S
does not change during the iterations. Perhaps I fail to understand
some
fundamental piece of the algorithm.
Suppose as sample n=1633
you have to try gcd( (10^1633)- 1,1633)
gcd( (10^1632)-1,1633)
etc... until S= (10^816) - 1
Is it clear?
------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 16:08:35 -0400
The algo is not practical for small numbers.
Dann Corbit wrote:
>
> "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Try this algo to factor N.
> > Let S= (10^k) - 1
> > for k=N to (n/2) step -1
> > Let c=gcd(S,N)
> > if c<>1 or c<>N then c is a solution.
> >
> > It's hard to compute hudge number. But with computers able to manage a
> > hudge number, it's feasible.
>
> Do yourself a favor and only test odd numbers. Doubles the speed of the loop.
> Here is an efficient GCD, with a nice Maple implementation:
> http://citeseer.nj.nec.com/cache/papers2/cs/5083/http:zSzzSzwww.math.ncsu.eduz
> Sz~kaltofenzSzbibliographyzSz99zSzKaMo99.pdf/kaltofen99genericity.pdf
>
> I can't say that I really understand how your algorithm works, since S does
> not change during the iterations. Perhaps I fail to understand some
> fundamental piece of the algorithm.
>
> I once had a similar notion, except that I took a product of known primes up
> to some K. For instance, if you form a product of all primes from 2 up to the
> largest prime in [0..2^32] then GCD of that product with any number up to
> 2^64th will partly factor it unless it is prime.
>
> However, this is a horrible algorithm and not at all impractical.
>
> Have you had a look at Chris Cauldwell's prime page?
>
> He lists some very efficient techniques for factoring.
> Even so, it is very expensive to factor large numbers. A product of two large
> primes is dauntingly difficult to factor. The RSA challenges (for instance)
> very effectively show that it is not cost effective to try to break RSA for
> even modest modulus sizes.
>
> If you look at the actual CPU hours, it is a stupefying total. And the
> algorithms used are among the best known for problems in that particular size
> range.
> --
> C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> "The C-FAQ Book" ISBN 0-201-84519-9
> C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Re: Q: IP
Date: 16 Mar 2001 14:13:27 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Thanks for the informations. I asked the question because
>I read a newspaper article saying that having a fixed IP
>means that attackers have a fixed target to work on, while
>with dynamically assigned IPs one is rather anonymous, being
>only one element of a more or less large set belonging
>to the same ISP, and is thus advantageous in that respect.
>In case this statement of the newspaper is incorrect, please
>kindly tell.
Well... it's kind of like saying that if you worked in a different
office every day, you wouldn't ever get mugged going home.
You are a small bit safer using a dynamic IP. But I wouldn't
depend on it as a safety measure. A dynamic IP is no guarantee of
safety.
-Ben
--
Ben Cantrick ([EMAIL PROTECTED]) | Yes, the AnimEigo BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
"I took an IQ test once." "Yeah?" "The results came back negative."
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: NTRU - any opinions
Date: 16 Mar 2001 13:21:40 -0800
Robert Harley <[EMAIL PROTECTED]> writes:
> Generating a 113-bit curve for short-term security e.g., for
> key-exchange in the WAP standard, takes 8 seconds with just a
> StrongARM chip and 36 K of RAM.
Very good work with the point counting. But why is WAP key exchange
short term security? Doesn't it need forward secrecy?
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Fri, 16 Mar 2001 21:36:01 +0000
daniel mcgrath wrote:
>
> On Thu, 15 Mar 2001 11:43:18 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
> >The first hint is consistent with my monome-dinome hypothesis, and the
> >second hint could mean something like HTML.
>
> HTML it is. I thought at the time that telling you that would make it
> too easy, but apparently you really want bigger hints.
Certainly. As people (including me) keep saying, a very strong
algorithm will still be strong even if everything except the key
used for that message has been totally exposed. Even if you give
away the plaintext to all but the last 10% of a message, this
should give the cryptanalyst no help in decrypting the last 10%.
A few people enjoy working on ciphertext-only challenges in unknown
cipher systems, but for most that gets very old in a hurry.
Just to add a little content, here's the sorted dictionary from
this, gathered together from my hypotheses with Daniel's
confirmations, and from the messages from Henk and Doug:
> >6. Daniel gave a big clue, as follows:
> >
> > You came 620711143 close with 54006 of the 806648
> > first hypotheses 711015 you had 450103. The code
> > 696690137 used here, 27465680662, is based 7774
> > the same 20650362042 idea as 71112 system used
> > 1743 my cryptograms.
for 1743 (probably)
general 20650362042
however 27465680662
made 450103
one 54006
rather 620711143
system 696690137
that 711015
the 71112
upon 7774
very 806648
Note that pieces of words fit into this ordering: the "ther"
from "rather" fits in well after "the", the end of "very"
(either 6648 or 648) fits after "rather", "tem" may be 690137,
the "ver" from "however" fits just before "very", and so on.
Given enough of these, one could use one-part code methods
even without recovering the actual algorithm used to create
the codes. Assuming this property is representative of the
actual messages, I'd expect exposing half of the plaintext
to make it fairly straightforward to recover the other half.
Note that this clue is illustrative only: it demonstrates
the encoding idea without giving away the actual system.
In particular, 71112 and the longer strings do not appear
in the real challenge cryptograms.
--
Jim Gillogly
Sterday, 24 Rethe S.R. 2001, 21:14
12.19.8.1.0, 7 Ahau 3 Cumku, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: How to eliminate redondancy?
Date: 16 Mar 2001 21:42:00 GMT
[EMAIL PROTECTED] (Joseph Ashwood) wrote in <#bd5eebrAHA.296@cpmsnbbsa09>:
>There are 3 possibilities.
>1 to many (expansion)
>many to 1 (lossy compression)
>and 1-1 (convolution, may be compression, expansion, or unchanged)
>All of these are possible for removing redundancy, although 1-1 is the
>most reasonable to use, with 1-1 onto being most preferable.
> Joe
>
Interesting comment Joe. So you prefer compression that is 1-1.
Let's be a little more specific. If you have to compression methods
that compress a given file type to a the same size range.
Which would you rather use.
1) that when a false key is used you usually get a file that could
not have been compresses with the compressor you used.
2) One that no matter what key an attacker tries it leads to a file
that could have been compresses. Thud forcing the attacker to use
other information if any about the possible file he thinks may have
been encrypted.
Assuming maybe falsely that you would prefer number 2.
which method do you actually use. I think most people rather
foolishly think that if they remove the so called headers from
the front of the file that they are using something close to
number 2. While they most likely are not.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 16:03:58 -0600
It's also insanely inefficient for large numbers. Have you actually *tried* this to
factor, say, a 150-bit number?
br wrote:
> The algo is not practical for small numbers.
>
> Dann Corbit wrote:
> >
> > "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > > Try this algo to factor N.
> > > Let S= (10^k) - 1
> > > for k=N to (n/2) step -1
> > > Let c=gcd(S,N)
> > > if c<>1 or c<>N then c is a solution.
> > >
> > > It's hard to compute hudge number. But with computers able to manage a
> > > hudge number, it's feasible.
> >
> > Do yourself a favor and only test odd numbers. Doubles the speed of the loop.
> > Here is an efficient GCD, with a nice Maple implementation:
> > http://citeseer.nj.nec.com/cache/papers2/cs/5083/http:zSzzSzwww.math.ncsu.eduz
> > Sz~kaltofenzSzbibliographyzSz99zSzKaMo99.pdf/kaltofen99genericity.pdf
> >
> > I can't say that I really understand how your algorithm works, since S does
> > not change during the iterations. Perhaps I fail to understand some
> > fundamental piece of the algorithm.
> >
> > I once had a similar notion, except that I took a product of known primes up
> > to some K. For instance, if you form a product of all primes from 2 up to the
> > largest prime in [0..2^32] then GCD of that product with any number up to
> > 2^64th will partly factor it unless it is prime.
> >
> > However, this is a horrible algorithm and not at all impractical.
> >
> > Have you had a look at Chris Cauldwell's prime page?
> >
> > He lists some very efficient techniques for factoring.
> > Even so, it is very expensive to factor large numbers. A product of two large
> > primes is dauntingly difficult to factor. The RSA challenges (for instance)
> > very effectively show that it is not cost effective to try to break RSA for
> > even modest modulus sizes.
> >
> > If you look at the actual CPU hours, it is a stupefying total. And the
> > algorithms used are among the best known for problems in that particular size
> > range.
> > --
> > C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> > "The C-FAQ Book" ISBN 0-201-84519-9
> > C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 14:14:23 -0800
"br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> You wrote :
> "I can't say that I really understand how your algorithm works, since S
> does not change during the iterations. Perhaps I fail to understand
> some
> fundamental piece of the algorithm.
>
> Suppose as sample n=1633
> you have to try gcd( (10^1633)- 1,1633)
> gcd( (10^1632)-1,1633)
> etc... until S= (10^816) - 1
>
> Is it clear?
What you are trying is clear now.
Suppose we are trying to factor a mere 56 bit number. How long will your
algorithm take? For instance, suppose you are wondering about this number:
72057594037927907 = 768467471 x 93767917
10^72057594037927907-1 has a lot of bits! Do you have a computer at your
disposal that can hold this number?
I don't think it is a good idea to use this method. I think it will be
impossibly slow on very easy problems.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Q: IP
Date: 16 Mar 2001 15:02:23 -0700
In article <98ttnn$9u$[EMAIL PROTECTED]>,
Henrick Hellstr�m <[EMAIL PROTECTED]> wrote:
> ... I you are seriously worried a dynamic IP is no replacement for a
>personal firewall and a sound security policy.
Note that "personal firewall" is usually salescritter talk in the tradition
of "switch" for "multi-port Ethernet bridge" and later "not particularly
slow IP router." "Personal firewall" usually means "lame intrusion detection
software for systems that are grossly insecure by design and implementation."
Most so called "personal firewall" packages at best look for holes that
you could better detect with Microsoft's version of "netstat" and trivially
block by deleting files and turning off "file and print sharing." At worst
"personal firewall" packages make your system less secure by paying
attention to packets that your system would otherwise ignore. Somewhere
in between is their most common effect of causing people to make pests of
themselves by reporting non-events as serious security attacks.
In other words, a "sound security policy" is good and necessary, but
a "personal firewall" is usually something else.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
Subject: Re: PKI and Non-repudiation practicalities
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Fri, 16 Mar 2001 22:30:18 GMT
[EMAIL PROTECTED] (those who know me have no need of my name) writes:
> further, while your description is slightly different than mine, you still
> describe exactly what i did, to wit, you are without access to the
> materials or services controlled by the compromised secret until the
> replacement is generated and communicated to all linked institutions.
> granted each material or service becomes available as the associated
> institution is notified, so that you can sequence according to need vs
> convienience. but that still leaves quite a lot of work to do to get it
> all done. (i don't like most of those credit card "registries" as it is,
> and it looks like aads would make them almost a necessity.)
looking at some pieces
does the bank trust the card & does the bank trust who you are.
current system has the bank mailing you the card and you get to call
up and answer one or more questions (sometimes just touch-tone & AR
unit and sometimes it kicks out to real person).
Given the AADS chip strawman that a bank can trust w/o having to mail
you something ... then it comes down are you really you. Simplest is a
website analogy to the 1-800 activation, you show you have the private
key by signing something that includes the public key, the web site
asks you one or more questions (like off recent statements, from
credit history, etc), the more questions that are answered the higher
the confidence (credit limit); confidence increases over time with use
and/or somebody walking into their local branch.
In this scenerio, it switches from bank choice about how many cards to
individual choice about how many cards ... the person can choose to
use as many or as few different cards for their relationship
... however lost/stolen pattern tends to be wallet/purse associated
... not single cards.
So the issue is the person has the same number of cards they have
today, only one card ... or some number inbetween.
The risk/vulnerability analysis says that stealing cards is much less
lucrative business since the cards don't work w/o PIN/secret
key. Current credit cards can be used at point-of-sale w/o additional
information or the account number used (w/o the card) in MOTO/internet
(aka mail order/telephone order) transactions (i.e. X9.59 introduces
authenticated transactions which eliminates most of the current
account number havesting vulnerabilities).
Counterfeiting is a lot harder also ... i.e. one of the new major
credit card frauds is waiter with a PDA & magstripe stripe reader
inside their jacket, as they do their normal business, they are also
harvesting the magstripe information with the PDA. Six hours later,
there are counterfeit cards in use someplace else in the world
(i.e. the actual card doesn't have to be lost/stolen, just the
information from the magstripe). The chip, private key, & secret key
are significantly more difficult to counterfeit.
So now the issue is what, if anything, new has to be done for
lost/stolen reports. Just stealing the card doesn't do much good w/o
the PIN. For most practical fraud purposes, extracting the private key
from the chip costs more than any likely benefit. Most of the existing
attacks go away since the costs rise significantly compared to any
likely gain. With all the major existing easy fraud issues addressed,
the weakest link is possibly the lost/stolen infrastructure ... either
as a denial-of-service attack (and forcing the infrastructure to deal
with person in less secure way) and/or as part of getting a fraudulent
replacement authorized. At the worst, it is the same as it is
today. Improvement, is using some of the web server techniques
associated with variable confidence techniques based on the number of
different random questions that can be answered, aka rather than
absolute lost/stolen report ... have a variable confidence lost/stolen
report.
The other issue in lost/stolen report ... is loosing your wallet/purse
and your one (or more) authentication devices ... which may be
collectively registered for 20 different relying parties ... can the
notification be simplified. Current 1-800 global notification is a
cost, somebody has to be prepared to pay for it. The success of any
1-800 service is going to be individuals willing to fund it (directly
or indirectly) or preferring to perform the function themselves (again
an individual choice). The individual could automate the process
personally with a PDA device (i.e. the centralized 1-800 is somewhat
left-over from the days where only corporate infrastructures had data
processing capability). The downside is that the PDA may be in the
same wallet/person package as the card(s) ... and also lost/stolen.
A 1-800 and/or automated PDA possibly is a vulnerability point since
the information there could be used to compromise the infrastructure
also (also. a bank confirming with variable, random questions from
recent statements/transactions isn't likely to get the information
from a 1-800 service since there needs to have some other type of
trust relationship).
The are a number of ways of enhancing the lost/stolen reports (and
replacements) both from aspect of ease-of-use as well as
vulnerabilities. The fixes also introduce costs and/or different kinds
of vulnerabilities. I would like to see a dozen or more different
approaches with well researched cost/vulnerability trade-offs and
allow the market to decide on how many of them are acceptable (similar
to allow person to decide on how many different authentication
hardware tokens they may wish to posses and how they distribute their
trust relationships among the hardware tokens).
However, if the frequency of (at least the stolen part of) lost/stolen
drops, the aggregate costs for lost/stolen infrastructure declines,
even with more sophisticated infrastructure introducing various forms
of variable confidence techniques.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED] - http://www.garlic.com/~lynn/
------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 17:30:09 -0400
Maybe someone who is crack on mathematics skills can prouve that before
computing.
You may choose randomly k values between (10^n)-1 and (10^(n/2)-1 to see
if it works.
Jeffrey Williams wrote:
>
> It's also insanely inefficient for large numbers. Have you actually *tried* this to
> factor, say, a 150-bit number?
>
> br wrote:
>
> > The algo is not practical for small numbers.
> >
> > Dann Corbit wrote:
> > >
> > > "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > > > Try this algo to factor N.
> > > > Let S= (10^k) - 1
> > > > for k=N to (n/2) step -1
> > > > Let c=gcd(S,N)
> > > > if c<>1 or c<>N then c is a solution.
> > > >
> > > > It's hard to compute hudge number. But with computers able to manage a
> > > > hudge number, it's feasible.
> > >
> > > Do yourself a favor and only test odd numbers. Doubles the speed of the loop.
> > > Here is an efficient GCD, with a nice Maple implementation:
> > > http://citeseer.nj.nec.com/cache/papers2/cs/5083/http:zSzzSzwww.math.ncsu.eduz
> > > Sz~kaltofenzSzbibliographyzSz99zSzKaMo99.pdf/kaltofen99genericity.pdf
> > >
> > > I can't say that I really understand how your algorithm works, since S does
> > > not change during the iterations. Perhaps I fail to understand some
> > > fundamental piece of the algorithm.
> > >
> > > I once had a similar notion, except that I took a product of known primes up
> > > to some K. For instance, if you form a product of all primes from 2 up to the
> > > largest prime in [0..2^32] then GCD of that product with any number up to
> > > 2^64th will partly factor it unless it is prime.
> > >
> > > However, this is a horrible algorithm and not at all impractical.
> > >
> > > Have you had a look at Chris Cauldwell's prime page?
> > >
> > > He lists some very efficient techniques for factoring.
> > > Even so, it is very expensive to factor large numbers. A product of two large
> > > primes is dauntingly difficult to factor. The RSA challenges (for instance)
> > > very effectively show that it is not cost effective to try to break RSA for
> > > even modest modulus sizes.
> > >
> > > If you look at the actual CPU hours, it is a stupefying total. And the
> > > algorithms used are among the best known for problems in that particular size
> > > range.
> > > --
> > > C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> > > "The C-FAQ Book" ISBN 0-201-84519-9
> > > C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 22:48:13 GMT
"br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> You wrote :
> "I can't say that I really understand how your algorithm works, since S
> does not change during the iterations. Perhaps I fail to understand
> some
> fundamental piece of the algorithm.
>
> Suppose as sample n=1633
> you have to try gcd( (10^1633)- 1,1633)
> gcd( (10^1632)-1,1633)
> etc... until S= (10^816) - 1
>
> Is it clear?
Why are you proposing this? A better method is to make a pseudo Congruetial
generator and use some feedback to check for factors.
I.e
1. X=1
2. X = X^2 + 1 mod N
3. Check GCD(X, N)=d
4. If D is not one then if D is prime emit D and perform N=N/D. If D is not
prime recurse and factor D, N=N/D
5. Goto 2 until N=1
That's simpler and for smooth integers is more likely to factor them.
Tom
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
