Cryptography-Digest Digest #452, Volume #11 Thu, 30 Mar 00 22:13:01 EST
Contents:
Re: Looking for some help on RSA public key/private key generation ("Joseph Ashwood")
Re: Looking for some help on RSA public key/private key generation ("Joseph Ashwood")
Re: Looking for some help on RSA public key/private key generation ("Joseph Ashwood")
Re: Particular integer factors (Scott Contini)
Re: The lighter side of cryptology (Xcott Craver)
Re: Improvement on Von Neumann compensator? ("Douglas A. Gwyn")
Re: Q: Entropy ("Douglas A. Gwyn")
Re: Factoring? (NFN NMI L.)
Re: Is it really NSA ?! (Arturo)
Re: new Echelon article (Arturo)
Re: Key exchange using Secret Key Encryption ("Lyalc")
Re: Crypto Webpages (Steve K)
Re: Is it really NSA ?! ("Douglas A. Gwyn")
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" (Anonymous)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Thu, 30 Mar 2000 17:11:11 -0000
I was not aware of the exact limit that had been found so
far, but I generally set a max e to the fourth root of pq,
which should give a d of > 3/4 the length of N, so it is
safe within the bounds given, and should be safe even if the
abstract's speculation of approaching 1/2 the length of N.
I do agree though that it is worth looking at, and I will be
sure to review it in more depth to see if I need to inform
anyone I have made recommendations to.
Joe
"David A Molnar" <[EMAIL PROTECTED]> wrote in message
news:8c0qih$goe$[EMAIL PROTECTED]...
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> > Yes a smaller d will be easier to guess, but with the
sizes
> > involved, the difficulty is not decreased significantly
so
> > I'm not overly worried. It is simply a matter of trading
off
>
> How small is your d in terms of N ?
>
> Have you looked at :
>
> Cryptanalysis of RSA with private key d less than N^0.292
>
> Authors: D. Boneh and G. Durfee
>
> Abstract:
> We show that if the private exponent d used in the RSA
system is less than
> N^0.292 then the system is insecure. This is
> the first improvement of an old result of Wiener showing
that
> when d < N^0.25 RSA is insecure. We hope our approach
> can be used to eventually improve the bound to d < N^0.5.
>
> Reference:
> In Proceedings Eurocrypt '99, Lecture Notes in Computer
Science,
> Vol. 1592, Springer-Verlag, pp. 1--11, 1999.
>
> URL :
> http://crypto.stanford.edu/~dabo/abstracts/lowRSAexp.html
>
>
> From what I can tell by skimming through the paper, the
attack requires
> only access to the public key N and e. This is in contrast
to another
> recent attack in the same spirit ("Factoring N = p^r q for
large
> r," Boneh, Durfee, and Howgarave-Graham CRYPTO '99), which
is really
> impressive until you notice the minor fact that you need
to know (or
> guess) the top 20 or so bits of the factor p.
>
> Anyway, assuming that all you need is the public key in
order to
> mount this attack, it seems worth looking at.
>
> Thanks,
> -David
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Thu, 30 Mar 2000 17:06:47 -0000
The size decrease in d comes from the fact that d must
satisfy the equation:
de = 1 mod (p-1)(q-1)
Given this, d can be computed using the normal processes
(regardless of e), and as e grows d will shrink.
A fairly simple way to compute a viable e (and the way it
was first proposed) is set e to an aribtrary prime. We have
simply taken to small e in order to increase the speed
encryption. Using this fact you can yourself compute a
(d,e,pq) triple that satisfies any size difference that
suits you. I would compute one, but I don't have the compute
time to spare right now.
Joe
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:8c0pgt$7ge$[EMAIL PROTECTED]...
> In article <#ll$PBqm$GA.225@cpmsnbbsa05>,
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> >No, length(d)+length(e) should be very close to
> >length(modulus), as in within 1
>
> I don't get it and would like to see an example, of a
reasonable sized
> modulus N = pq, along with exponents d and e which are
each about half the
> length of N, with de==1 mod phi(N). Given N, how do you
compute d and e
> to have those properties?
>
> >Encryption is NOT inherently faster than decryption, the
> >speed is determined by the values for e and d. By
choosing a
> >d and e of the same length, the timing will be virtually
> >identical. Instead it is generally used in a way that d
> >>>>>> e making it so that decryption takes much longer
than
> >encryption. The observed speed differences are solely an
> >artifact of the chosen e and d.
>
> Yes of course you are correct, you can choose a large e so
that e and
> d are about the same size and that gives up the speed
advantage of a
> small e, but it doesn't make decryption any faster. What
I don't see
> is how to get a small d.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Thu, 30 Mar 2000 17:11:11 -0000
I was not aware of the exact limit that had been found so
far, but I generally set a max e to the fourth root of pq,
which should give a d of > 3/4 the length of N, so it is
safe within the bounds given, and should be safe even if the
abstract's speculation of approaching 1/2 the length of N.
I do agree though that it is worth looking at, and I will be
sure to review it in more depth to see if I need to inform
anyone I have made recommendations to.
Joe
"David A Molnar" <[EMAIL PROTECTED]> wrote in message
news:8c0qih$goe$[EMAIL PROTECTED]...
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> > Yes a smaller d will be easier to guess, but with the
sizes
> > involved, the difficulty is not decreased significantly
so
> > I'm not overly worried. It is simply a matter of trading
off
>
> How small is your d in terms of N ?
>
> Have you looked at :
>
> Cryptanalysis of RSA with private key d less than N^0.292
>
> Authors: D. Boneh and G. Durfee
>
> Abstract:
> We show that if the private exponent d used in the RSA
system is less than
> N^0.292 then the system is insecure. This is
> the first improvement of an old result of Wiener showing
that
> when d < N^0.25 RSA is insecure. We hope our approach
> can be used to eventually improve the bound to d < N^0.5.
>
> Reference:
> In Proceedings Eurocrypt '99, Lecture Notes in Computer
Science,
> Vol. 1592, Springer-Verlag, pp. 1--11, 1999.
>
> URL :
> http://crypto.stanford.edu/~dabo/abstracts/lowRSAexp.html
>
>
> From what I can tell by skimming through the paper, the
attack requires
> only access to the public key N and e. This is in contrast
to another
> recent attack in the same spirit ("Factoring N = p^r q for
large
> r," Boneh, Durfee, and Howgarave-Graham CRYPTO '99), which
is really
> impressive until you notice the minor fact that you need
to know (or
> guess) the top 20 or so bits of the factor p.
>
> Anyway, assuming that all you need is the public key in
order to
> mount this attack, it seems worth looking at.
>
> Thanks,
> -David
>
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Crossposted-To: sci.math
Subject: Re: Particular integer factors
Date: 31 Mar 2000 01:22:53 GMT
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>
>> In sci.crypt JCA <[EMAIL PROTECTED]> wrote:
>> > When attempting to factorize a (large) integer does it help to know
>> > that it is
>> > the product of two unknown factors whose sizes are known?
>>
>> Well, it lets you skip a primality test and searching for small
>> factors. :) I doubt it helps significatly though, apart from simply
>> letting you jump right to mpqs or nfs.
>
> Yes, that's what I was aiming at: Can the sophisticated methods used
>to factorize large integers make anything out of the extra piece of
>information about the factors mentioned above? More tentatively, could
>a new, highly performant method be developed that exploits that knowledge?
>
>
Suppose you know that a number N has a prime factor p where you
know approximately the size (i.e. number of bits) of p .
Assume that N is somewhat large in the arguments below.
Here's exactly what you would do.
You approximate the running time to factor N by the general number
field sieve (GNFS), which is given by the formula:
e ^ [ ( (64/9)^(1/3) * (log N)^(1/3) * (log log N)^(2/3) ) ]
(the experts might complain that I am omitting an o(1) term, but
for practical purposes, you can ignore it here). The "log" here
and below means natural logarithm (base e ).
The best way to approximate the time is to use this formula to predict
how much harder it is than other GNFS factorisations, and to look at
the computation time of the other GNFS factorisations. This gives you
a more realistic estimate than just using the formula blindly.
Next, you compare the approximate time to find factor p of N using
the elliptic curve method (ECM). The formula for this one is:
e ^ [ ( 2 * log p * log log p )^0.5 ]
Again, you probably want to look at other elliptic curve factoring attempts
to get a more realistic estimate than just blindly applying the formula.
If the expected time for ECM is less than that of GNFS, then you use
ECM. Otherwise, you use GNFS.
So, now the only question is where can you find information about
real computation times for factoring these numbers. See the Factorization
Announcements section of my FactorWorld web site, at:
http://www.maths.usyd.edu.au:8000/u/contini/factoring/FactorWorld.html
This web site is new, and still being built, so expect to see a lot
more on it over the next coming months.
Scott
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: The lighter side of cryptology
Date: 31 Mar 2000 01:31:47 GMT
<[EMAIL PROTECTED]> wrote:
>I just saw this limerick which isn't
>extremely funny but at least it's a start:
[Limerick]
How about:
An Alice and Bob in the slammer,
To communicate under a jammer,
Sent innocuous text
To the group alt.sex
But were buried by mail from a spammer.
-S
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Improvement on Von Neumann compensator?
Date: Fri, 31 Mar 2000 00:56:50 GMT
Mok-Kong Shen wrote:
> ... wouldn't the above mentioned imperfection in measurement
> and recording essentially falsify our results?
No, it is quite possible for the precision of a measurement to
greatly exceed the precision of the tools used to construct the
apparatus. We do that all the time in physics laboratories.
As to measuring Brownian motion as a source for random numbers,
it seems too hard compared to several other approaches.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 31 Mar 2000 01:03:02 GMT
Bryan Olson wrote:
> Remember that entropy is defined by probability. Given
> a finite bit sequence but not a probability space,
> there is no such thing as the entropy of the sequence.
Right! Also remember that probability, hence entropy,
is contextual. Where there is no uncertainty, there
is no entropy.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Factoring?
Date: 31 Mar 2000 01:55:37 GMT
<<Is there any point in deveolping methods to factor numbers with small
factors?>>
Generally, for small factors, all you need to do is use one of the common
small-factor methods and throw some computer power at it. So yes, only
algorithms for finding large factors are really interesting. Maybe for
intermediate-size factors....
-*---*-------
S.T. "andard Mode" L.
STL's Quotation Archive: http://quote.cjb.net
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: Is it really NSA ?!
Date: Thu, 30 Mar 2000 07:53:52 GMT
On Mon, 27 Mar 2000 19:25:37 +0200, Ichinin <[EMAIL PROTECTED]> wrote:
>Doug Stell wrote:
>> 1. If they did visit your site, you would never know it.
>
>Perhaps you could; back in 1998 after i published one of my security
>tools i checked every download from my server. I found one that
>simply said "National Security". No contact information, no name
>servers - noting. (CIA seem less important and is listed at Arin)
>
>Generally; those agencies around the world does not have a sign on
>them that say: "Hi I'm a spy, and now i'm looking on your webserver",
Unless it is a deliberate movement to mean "hi, it´s me, and I´m
watching you, so you´d better behave"
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: new Echelon article
Date: Thu, 30 Mar 2000 07:52:07 GMT
On Wed, 29 Mar 2000 16:01:35 +0100, [EMAIL PROTECTED] wrote:
>Is there anyway you can put me in contact with this someone or obrain
>information on how he went about doing this?
>
>As far as I know GSM data encryption works between phones, the exchange does
>not do any encryption.
>
>Thanks,
>-Jared
>
There´s some info on GSM encryption at www.scard.org; it includes
source code and details of how a Berkeley group managed to break the code.
IIRC, GSM encryption only works in the phone-to-cell path.
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Key exchange using Secret Key Encryption
Date: Fri, 31 Mar 2000 08:11:47 +1000
Provided an initial secret key can be passed securely enoug for the purpose,
a practically infinite number of unique secret keys can be used, uniqe to
each message.
See Ansi X9 or ISO 8583.
If that method is not operationaly reliable for the purpose, we have an
extension to those methods that does provide relaibility.
Lyal
[EMAIL PROTECTED] wrote in message <8bvdfk$ghs$[EMAIL PROTECTED]>...
>In article <8bufbm$g75$[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] wrote:
>> Please excuse a newbie question.
>>
>> I am looking for a method of key exchange that only involves secret
>key
>> encryption. The method should also be immune to man-in-the-middle
>> attack. The scenario I am looking at is described below.
>>
>> Alice and Bob are complete strangers and have only one channel of
>> communication. The Channel being the Internet. They only have at their
>> disposal a secret key encryption method. For the sake or argument,
>this
>> method is Bob Schnier's Twofish. It can be assumed that Alice and Bob
>> are both connected to the internet concurrently, so multiple pass
>> protocals can be used. How can Alice and Bob start communicating and
>> protect their messages.
>
>Usually the Diffie-Hellman key exchange is used. However, this method is
>NOT immune to man-in-the-middle attacks. In order to protect against
>man-in-the-middle attacks, you can use digital signatures on the
>messages exchanged in the key exchange. However, this requires that
>Alice and Bob can securely transfer each others public keys, and since
>in this scenario we can only communicate using the internet, it is not
>possible.
>
>In conclusion, there must be some way of securely exchanging information
>in order to setup a completely secure connection. If we only
>have the Internet, we have a cach 22 situation where we can
>only setup a secure connection if we have already done so
>before.
>
>Strangely enough, many "secure" connections, such as those used in
>browsers, completely ignore the man-in-the-middle problem.
>
>-Erik Runeson
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: Crypto Webpages
Date: Fri, 31 Mar 2000 02:17:56 GMT
On 30 Mar 2000 23:53:08 GMT, David A Molnar <[EMAIL PROTECTED]>
wrote:
>RecilS <swehmeier @ mindspring> wrote:
>> Just a URL and a short description would be great
>
>My personal web page is
>http://www.hcs.harvard.edu/~dmolnar/
>
>It has some cryptographic content. Mostly unfinished pages on various
>things which (used to) interest me.
Some of my favorite places to go beat my head against the wall of
mathematical ignorance:
http://fn2.freenet.edmonton.ab.ca/~jsavard/index.html
http://www.rsasecurity.com/rsalabs/faq/
http://cacr.math.uwaterloo.ca/hac/
And don't let Tom St Denis fool you; he has a HUGE crypto archive
available for download on his website.
:o)
Steve
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP key 0x5D016218
All others have been revoked.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Is it really NSA ?!
Date: Fri, 31 Mar 2000 01:06:24 GMT
Arthur Dardia wrote:
> However, to do it properly, I wouldn't suggest an electronic attack, but
> more of a physical, armed-to-the-teeth attack. First things first,
> don't bother cutting power - I'm positive they have a generator, and
> once their generator kicks in, I'm sure they'd be suspicious. Secondly,
> I'm sure they have metal detectors...porcelain guns? I know I saw them
> in some movie. :)
> Please note that the above is a bunch of crap, ...
I'm not going to post a physical vulnerability assessment,
but I will warn you to be careful with such "crap" -- it
could be construed as conspiracy to commit a felony, which
in itself is already a felony. Stay out of jail, don't
publicly discuss how to commit crimes.
------------------------------
Date: Thu, 30 Mar 2000 19:59:20 -0700
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
>>> What this means in effect, no one will want to use encryption in
>>> case they forget their password and end up in jail.
>>
>> Which is precisely their goal, of course.
>> ...
>> The best slave is one who puts on his own shackles. Your country has a
>> bad case of the liberal-socialist disease going back decades. The country
>> formerly known as the USA also has this disease but for not as long so
>> the decay isn't as pronounced. Yet.
>
> It's farther gone than you seem to realize. Consider the close
> analogy with the so-called "smart gun" legislation that gun haters
> have recently proposed. Maryland is on the brink of passing a law
> requiring such technology (which has not been developed beyond the
> laboratory stage yet) in every handgun sold within a few years.
> The obvious goal, which of course differs from the stated goal, is
> simply to prevent sales, or failing that, to reduce the positive
> value of guns to the point that people won't want them any more.
No, I realize the rot has gone much further, I was just limiting the scope
of my statement to this one topic. To attempt to view the rot as a whole is
to risk insanity ( or complete demoralization at the very least). The govt
of the USSA has been nibbling at our freedoms for decades; over the last
20 years the nibbling has given way to bites, and over the last ten years
the bites have given way to large chunks. At present most of the powers and
protections afforded the citizenry by the Constitution are in tatters. Here's
a mind-blower - TV shows that glorify police brutality!!
> One wonders whether the politicians in power actually think that
> their constituency are the career criminals; they sure act like it.
When it is they themselves that are the criminals. And why should they care,
as long as we keep voting for them? A famous quote states, "People get the
government they deserve". Which is a pretty harsh condemnation IMHO.
Steve
(living in the USSA)
PS - since you brought up the gun topic, where are the estimated 190 million
gun owners that are *not* NRA members? Out to lunch? MIA? If every firearm
owner in Amerika told his or her elected public officials that the gun issue
is their "litmus test" for getting their vote the whole gun controversy would
be finished in 10 minutes. The end of firearm ownership by civilians in the
USSA will be brought about by these 190 million uninvolved people in much the
same way as those in GB/NZ/Canada/Austrailia who sat around with their heads
in the sand thinking "It can't happen here". Until it did.
"All that evil needs to triumph is for good to do nothing."
------------------------------
** 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
******************************
