Cryptography-Digest Digest #137, Volume #10 Sun, 29 Aug 99 21:13:03 EDT
Contents:
Re: Can I export software that uses encryption as copy protection? (JPeschel)
Re: What if RSA / factoring really breaks? (Mok-Kong Shen)
Re: Q: Cross-covariance of independent RN sequences in practice (Mok-Kong Shen)
Re: Key Establishment Protocols - free chapter from Handbook of Applied Cryptography
(Mok-Kong Shen)
Re: What if RSA / factoring really breaks? (DJohn37050)
Re: What if RSA / factoring really breaks? (Boudewijn W. Ch. Visser)
Re: What if RSA / factoring really breaks? (David A Molnar)
Re: What if RSA / factoring really breaks? ([EMAIL PROTECTED])
Re: What if RSA / factoring really breaks? ("David J Whalen-Robinson")
Re: RC4 question (fungus)
Re: What if RSA / factoring really breaks? (David A Molnar)
Re: What if RSA / factoring really breaks? ("David J Whalen-Robinson")
Re: What if RSA / factoring really breaks? (Helger Lipmaa)
Re: What if RSA / factoring really breaks? (David Wagner)
Re: What if RSA / factoring really breaks? (Paul Rubin)
Re: What if RSA / factoring really breaks?
Re: Can I export software that uses encryption as copy protection? (Eric Lee Green)
Re: What if RSA / factoring really breaks? ([EMAIL PROTECTED])
Re: What if RSA / factoring really breaks? (DJohn37050)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Can I export software that uses encryption as copy protection?
Date: 29 Aug 1999 20:55:31 GMT
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) writes:
> Joe if one can legally export decrytion could one then export a decryption
>only version of my source code with working executable. Of course there
>may be a few beer drinking German that could be smart enough to reverse
>engineer and come up with a program that did encryption based on his code.
>BUt the infinite powers of the beer drinking mind are beyond my control.
> IF yes I can export it. What is to keep me from exporting a part of
>scott19r
>the decryption portion only of a different program. But haveing the weakness
>the the decyryption part of the source code. could be lefted in five minutes
>by a Brit and used to create a full working copy of scott19u. Note I never
>intended to export encryption (usiing only a small subset of CLintonian logic
>which protects one from prejury). Yes some random thougfhts from to much
>beer that I am sure I will forget when this hangover leaves
Nope, Dave, I don't think you can export a decryption-only version of
your source code. You should be able to export a binary that does
decryption only, but I don't know why you would want to.
A tall glass of vodka on ice will get rid of most beer induced hagovers.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: Sun, 29 Aug 1999 23:08:53 +0200
DJohn37050 schrieb:
>
> The known best method to attack a generic RSA key is the GNFS. GNFS can also
> be used to solve discrete logs (the p value of DSA). One choice would be to go
> to ECC. I presented a paper at PKS '99 on future resiliency. See
> www.certicom.com in the PKS '99 section for my (rudimentary) thoughts on this.
Isn't it that Shamir has in a recent paper shown the feasibility
of building a special machine to crack RSA? I haven't seen the
paper. How is that related to the above?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Cross-covariance of independent RN sequences in practice
Date: Sun, 29 Aug 1999 22:55:01 +0200
[EMAIL PROTECTED] schrieb:
>
> Since independent random sequences can be made at widely separated places,
> while many things have lower bounds due to imperfection, this is not one
> of the stronger examples.
>
> You would be surprised at how many decibels of separation are possible
> between the left channel of my stereo system, and the right channel of
> somebody else's stereo system in Nebraska.
Perhaps I have not expressed myself clear enough. I meant what
magnitude of the value of computed cross-covariance can be safely
considered to be 0 in practice (even though that is non-zero) and
hence assume that there is indeed independence.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Key Establishment Protocols - free chapter from Handbook of Applied
Cryptography
Date: Sun, 29 Aug 1999 23:23:42 +0200
Alfred John Menezes wrote:
>
> of the book will not be affected. Any comments on this publishing
> experiment will be greatly appreciated.
I believe the experiment is successful. Those who can afford the price
at all will certainly buy a copy, for the printout is inconvenient
to handle. Those who can't afford the price don't affect the
gain of the publisher anyway. The experiment has definitely
contributed to make the book known to a wider circle of people and
hence to a higher volume of sales.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 20:55:00 GMT
The known best method to attack a generic RSA key is the GNFS. GNFS can also
be used to solve discrete logs (the p value of DSA). One choice would be to go
to ECC. I presented a paper at PKS '99 on future resiliency. See
www.certicom.com in the PKS '99 section for my (rudimentary) thoughts on this.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Boudewijn W. Ch. Visser)
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 22:13:40 GMT
On 29 Aug 1999 21:45:22 GMT, David A Molnar <[EMAIL PROTECTED]> wrote:
[..]
>> of building a special machine to crack RSA? I haven't seen the
>> paper. How is that related to the above?
>
>The TWINKLE paper is at http://www.jya.com/twinkle.eps . It outlines a
>machine which speeds up the "sieve" in general number field sieve. The
>machine does not help with the next stage, which requires finding
>dependencies between vectors in a very large matrix. So it is not a
>panacea for factoring, although it is an improvement.
>
>I think the point is that subexponential methods like the GNFS exist for
>factoring and discrete logs, while no such efficient methods are known for
>elliptic curve crypto yet. I'm having trouble getting either word or
>powerpoint to run on this computer, so I can't say anything now about the
>presentation.
Uhm, you don't need either Word or Powerpoint to read the Twinkle paper
you pointed to.
The format is Encapsulated PostScript (.eps), so you can just send it to a
PostScript capable printer, or view it with GhostScript,for instance.
(which, unlike Word and PP, is available for many systems and is
free software)
Boudewijn
--
+--------------------------------------------------------------+
|Boudewijn Visser | E-mail:[EMAIL PROTECTED] |
| -finger for PGP-keys.- | http://www.ph.tn.tudelft.nl/~visser |
+-- my own opinions etc ---------------------------------------+
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 21:45:22 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> DJohn37050 schrieb:
>>
>> The known best method to attack a generic RSA key is the GNFS. GNFS can also
>> be used to solve discrete logs (the p value of DSA). One choice would be to go
>> to ECC. I presented a paper at PKS '99 on future resiliency. See
>> www.certicom.com in the PKS '99 section for my (rudimentary) thoughts on this.
> Isn't it that Shamir has in a recent paper shown the feasibility
> of building a special machine to crack RSA? I haven't seen the
> paper. How is that related to the above?
The TWINKLE paper is at http://www.jya.com/twinkle.eps . It outlines a
machine which speeds up the "sieve" in general number field sieve. The
machine does not help with the next stage, which requires finding
dependencies between vectors in a very large matrix. So it is not a
panacea for factoring, although it is an improvement.
I think the point is that subexponential methods like the GNFS exist for
factoring and discrete logs, while no such efficient methods are known for
elliptic curve crypto yet. I'm having trouble getting either word or
powerpoint to run on this computer, so I can't say anything now about the
presentation.
-David
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: Sun, 29 Aug 1999 22:58:06 GMT
>From "David J Whalen-Robinson" <[EMAIL PROTECTED]>:
[entire article elided]
Bill Payne, PhD, of Albuquerque, NM already broke RSA several years ago, and his real
time method using Euler's tuotient was disclosed at that time. RSA is broken already.
Use non inversive encryption instead, such as licensing US Patent No. 5,926,815, a
two-phase random number generator which is the fastest known.
------------------------------
From: "David J Whalen-Robinson" <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: Sun, 29 Aug 1999 18:40:48 -0400
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> DJohn37050 schrieb:
> >
> > The known best method to attack a generic RSA key is the GNFS. GNFS can
also
> > be used to solve discrete logs (the p value of DSA). One choice would
be to go
> > to ECC. I presented a paper at PKS '99 on future resiliency. See
> > www.certicom.com in the PKS '99 section for my (rudimentary) thoughts on
this.
>
> Isn't it that Shamir has in a recent paper shown the feasibility
> of building a special machine to crack RSA? I haven't seen the
> paper. How is that related to the above?
>
This is the current state of the art, and fast machines will continue to
present a growing threat, but
we can always use more digits unless there was a truely radical
revolutionary technique.
This thread is to consider that WHAT-IF situtation where somebody does find
a revolutionary
method for factoring. So revolutionary that an increase in bits would
become impracticle
before it would help the security enough to be usable.
Thanks for your contributions to this thread, though.
It just shows how many different minds are attacking this problem in along
evolutionary and
revolutionary directions as we speak.
> M. K. Shen
David
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: RC4 question
Date: Mon, 30 Aug 1999 02:12:23 +0200
Red_Blue <[EMAIL PROTECTED]> wrote:
>
> Could someone please shed some light on the following issue:
>
> What is the difference in required brute force computing power for
> breaking RC4-40 vs. RC4-128 export (40 secret) keys?
>
The difference is a factor of 2^(128-40) = 2^88.
2^88 is 300,000,000,000,000,000,000,000,000
ie. RC4 128 is zillions of times more secure than RC4-40.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 23:13:21 GMT
Boudewijn W. Ch. Visser <[EMAIL PROTECTED]> wrote:
> Uhm, you don't need either Word or Powerpoint to read the Twinkle paper
> you pointed to.
> The format is Encapsulated PostScript (.eps), so you can just send it to a
> PostScript capable printer, or view it with GhostScript,for instance.
> (which, unlike Word and PP, is available for many systems and is
> free software)
I'm sorry, I was unclear. By "the presentation", I meant Don Johnson's
presentation at PKS '99. I have a copy of GhostScript, which serves me
very well. :-)
Thank you for pointing that out,
-David
------------------------------
From: "David J Whalen-Robinson" <[EMAIL PROTECTED]>
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: Sun, 29 Aug 1999 19:20:58 -0400
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> From "David J Whalen-Robinson" <[EMAIL PROTECTED]>:
>
> [entire article elided]
>
> Bill Payne, PhD, of Albuquerque, NM already broke RSA several years ago,
and his real
> time method using Euler's tuotient was disclosed at that time. RSA is
broken already.
You must mean that somebody broke one of the RCx methods by RSA...
Wasn't RC3 broken quickly and RC1 was scrapped in development?
This thread is about RSA public key's based essentially
on the problem of factoring large composite numbers.
If you do meant that this was broken, but somehow kept out of
public knowledge, can you post more info about this?
> Use non inversive encryption instead, such as licensing US Patent No.
5,926,815, a
> two-phase random number generator which is the fastest known.
Thanks for participating in this discussion.
Combining generators may be great if done carefully, but what method do you
recommend
for public key encryption?
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: Sun, 29 Aug 1999 23:55:00 +0000
David A Molnar wrote:
> I think the point is that subexponential methods like the GNFS exist for
> factoring and discrete logs, while no such efficient methods are known for
> elliptic curve crypto yet. I'm having trouble getting either word or
> powerpoint to run on this computer, so I can't say anything now about the
> presentation.
Discrete logarithm is hard in many groups. Intuitively, "obscurity" helps in this
case. Namely it has been proven that if the group elements can be used only for group
operations, equality tests and as inputs to a random oracle, then the discrete
logarithm problem in this group is exponentially hard to solve. (See, e.g., Victor
Shoup, "Lower Bounds for Discrete Logarithms and Related Problems" (Eurocrypt '97)
and the recent TR by Schnorr and Jakobson available from
http://www.mi.informatik.uni-frankfurt.de/). Such model is coined as a "generic
model". It means intuitevely that the binary encoding of group elements does not help
in calculating the logarithm. For example, Z^*_q has a lot of structure (it is not
only multiplicative group but also additive one!), and therefore there are
subexponential algorithms for discrete log in this group (e.g., index calculus). So
there comes the conjecture that in elliptic curves (and lot of other
groups) interactions between group operations and any other calculations (say,
XORing) do not help at all.
As an interesting application see the method in MQV authentication protocol
(available from http://www.cacr.math.uwaterloo.ca, part of the upcoming P1363
standard) where one tries to simplify calculations by just cutting off half of the
bits in the x-coordinate of a EC point (instead of, say taking hash on it). In
generic model assumption you have to tract this cutting off function as a random
oracle. I'm not sure if the authors thought in the terms of "generic model" but the
idea is the same (Don Johnson can probably comment...).
Helger
http://home.cyber.ee/helger
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 16:29:24 -0700
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Bill Payne, PhD, of Albuquerque, NM already broke RSA several years ago, and his real
> time method using Euler's tuotient was disclosed at that time. RSA is broken
>already.
Bill Payne's method was 100% bogus. (So bogus that I'm a bit embarassed
to even admit to having read it.) It had exponential time complexity, and
would probably perform even worse than trial division. In no way does his
"attack" justify the statement `RSA is broken'.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 29 Aug 1999 23:24:17 GMT
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Bill Payne, PhD, of Albuquerque, NM already broke RSA several years ago,
No he didn't. He believed he did, but believing doesn't make it so.
(Square the circle anyone?)
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 99 00:05:13 GMT
David J Whalen-Robinson ([EMAIL PROTECTED]) wrote:
: 1. What cryptographic techniques would fall prey to the new fast method?
RSA. And possibly other public-key methods would be affected.
: 2. How would the world react? What cryptographic techniques would the world
: move to?
Other public-key algorithms, such as elliptic curves, if they survive.
Conventional symmetric-key cryptography would not be affected.
: (obviously you can't just release it, every cracker would have an
: info-looting-spree before anybody could react. )
Actually, I think it is felt that the spree would be briefest if exactly
that course of action were taken.
John Savard
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Crossposted-To: misc.legal.computing
Subject: Re: Can I export software that uses encryption as copy protection?
Date: Sun, 29 Aug 1999 17:44:47 -0700
Timur Tabi wrote:
> I'm planning on developing software that decrypts the registration
> information that's embedded in the binary. That is, before we ship the
> software to the customer, we use a public-key encryption to generate an
> encrypted message that contains the user's registration information (name,
> etc). This message is then written to the application's binary (.EXE), and
> the binary is e-mailed to the user. The application, whenever it's run,
> decrypts the message (with the other half of the public-key) and verifies the
> contents. If it's invalid, the software terminates.
Yes, that is legal, but note that I could crack this "registration"
scheme within minutes using a normal binary editor to change the output
of your verification routine to always say "verified!".
Back in the early 80's software publishers tried to create "unbreakable"
copy protection schemes. They failed. If I have physical access to your
software, I can load it into a binary debugger, trace its execution, and
'break' it.
In recognition of this fact, I did not bother encrypting the
registration file in the licensing routine that I recently wrote. I
include a MD5 checksum including an internal "secret" to filter out the
"script kiddies", but doing any more than that is just creating work for
me, since the "real" crackers will always be able to break it.
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: Mon, 30 Aug 1999 01:04:49 GMT
>From "David J Whalen-Robinson" <[EMAIL PROTECTED]>:
> Combining generators may be great if done carefully, but what method do you
> recommend
> for public key encryption?
We don't recommend public key encryption at all because public key encryption can now
be
broken in real time with Bill Payne's recent advances in factoring.
We recommend only non inversive encryption, and there are many methods for keeping the
seed and point(s) in the stream of interest completely secure.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 1999 01:11:19 GMT
There are free word and powerpoint viewers (with print capability) from the
microsoft website.
Don Johnson
------------------------------
** 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
******************************
