Cryptography-Digest Digest #141, Volume #10 Mon, 30 Aug 99 15:13:02 EDT
Contents:
Re: Key Establishment Protocols - free chapter from Handbook of Applied Cryptography
(John Savard)
Re: Q: Cross-covariance of independent RN sequences in practice ("Trevor Jackson,
III")
Factorization of 512-bits RSA key (Herman J.J. te Riele)
Re: What if RSA / factoring really breaks? (Bob Silverman)
Re: WT Shaw temporarily sidelined (John Savard)
Re: What if RSA / factoring really breaks? (Robert Harley)
Re: 512 bit number factored (Bob Silverman)
Re: 512 bit number factored (Anton Stiglic)
Re: public key encryption - unlicensed algorithm ("shivers")
Re: 512 bit number factored (DJohn37050)
Re: 512 bit number factored (Anton Stiglic)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Key Establishment Protocols - free chapter from Handbook of Applied
Cryptography
Date: Mon, 30 Aug 1999 16:54:20 GMT
[EMAIL PROTECTED] (Alfred John Menezes) wrote, in part:
> Chapter 9 (Key Establishment Protocols).
Actually, that's chapter 12. Chapter 9 was hash functions and data
integrity.
Given that your book was considered to be late enough in its life that
it was included on the Dr. Dobb's CD-ROM, I suppose the publishing
experiment is not entirely reckless, however much I may appreciate it.
But I do have one nitpicking criticism, after having glanced at the
chapter.
An unauthenticated key exhange protocol is, by definition, not
protected against forgery. But that doesn't mean that forgery is
actually possible; the fact that key exchange requires authentication
to protect it is a fact about the real world, which must be derived
(from observation or whatever). Thus, it isn't really accurate to say
that an unauthenticated KEP is vulnerable to forgery _by definition_.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Mon, 30 Aug 1999 12:59:12 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Q: Cross-covariance of independent RN sequences in practice
[EMAIL PROTECTED] wrote:
> Mok-Kong Shen ([EMAIL PROTECTED]) wrote:
> : Because of imperfection in this world, e.g. impossibility of
> : making objects of exact sizes or attaining the temperature of absolute
> : zero, I suppose that there is a certain not too small lower bound of
> : the (average) value of the cross-covariance obtainable in practice.
>
> 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.
Well, there's a Grandmother who competes in the world's-loudest-car-stereo
contest with a remote-control Jeep. It uses a 12 volt power system providing
11,000 amps to generate 45,000 watts of audio output. It was measured at
173.6 decibels. That's about a loud as a .50 BMG rifle, but continuously
instead of a pulse.
They might be able to hear that in Nebraska.
------------------------------
From: [EMAIL PROTECTED] (Herman J.J. te Riele)
Crossposted-To: sci.crypt.research
Subject: Factorization of 512-bits RSA key
Date: 30 Aug 1999 18:07:09 GMT
Reply-To: [EMAIL PROTECTED] (Herman J.J. te Riele)
Factorization of a 512-bits RSA key using the Number Field Sieve
================================================================
On August 22, 1999, we found that the 512-bits number
RSA-155 =
1094173864157052742180970732204035761200373294544920599091384213147634\
9984288934784717997257891267332497625752899781833797076537244027146743\
531593354333897
can be written as the product of two 78-digit primes:
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643
Primality of the factors was proved with the help of two different primality
proving codes. An Appendix gives the prime decompositions of p +- 1.
The number RSA-155 is taken from the RSA Challenge list
(see http://www.rsa.com/rsalabs/html/factoring.html).
This factorization was found using the Number Field Sieve (NFS) factoring
algorithm, and beats the 140-digit record RSA-140 that was set on
February 2, 1999, also with the help of NFS [RSA140].
The amount of computer time spent on this new factoring world record is
estimated to be equivalent to 8000 mips years.
For the old 140-digit NFS-record, this effort was estimated to be
2000 mips years. Extrapolation using the asymptotic complexity formula
for NFS would predict approximately 14000 mips years for RSA-155. The gain
is caused by an improved application of the polynomial search method used
for RSA-140.
For information about NFS, see [LL]. For additional information,
implementations and previous large NFS factorizations, see [DL, E1, E2, GLM].
Polynomial selection
====================
The following two polynomials
F_1(x,y) = 11 93771 38320 x^5
- 80 16893 72849 97582 y *x^4
- 66269 85223 41185 74445 y^2*x^3
+ 1 18168 48430 07952 18803 56852 y^3*x^2
+ 745 96615 80071 78644 39197 43056 y^4*x
- 40 67984 35423 62159 36191 37084 05064 y^5
F_2(x,y) = x - 3912 30797 21168 00077 13134 49081 y
were selected with the help of a polynomial search method developed by
Peter Montgomery (Microsoft Research, USA and CWI) and Brian Murphy
(The Australian National University, Canberra), which was applied already
to RSA-140, and now, even more successfully, to RSA-155.
The polynomial F_1(x,y) was chosen to have a good combination of
two properties: being unusually small over its sieving region and
having unusually many roots modulo small primes (and prime powers).
The effect of the second property alone gives F_1(x,y) a smoothness
yield comparable to that of a polynomial chosen at random for an
integer of 137 decimal digits.
Measured in a different way: the pair (F_1, F_2) has a yield of relations
approximately 13.5 times that of a random polynomial selection for
RSA-155 (the corresponding figure for the polynomial selected for the
RSA-140 factorisation is 8).
The polynomial selection took approximately 100 MIPS years,
which is equivalent to 0.40 CPU years on a 250 MHz SGI Origin 2000
processor (most of the searches were done on such processors).
The original polynomial selection code was ported by Arjen Lenstra
to use his multiple precision arithmetic package LIP.
Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson
ran the polynomial searches for RSA-155 with this code. The above
polynomial emerged from Bruce Dodson's search.
Calendar time for the polynomial selection was approximately nine
weeks.
The Sieving
===========
Sieving was done on about 160 175-400 MHz SGI and Sun workstations,
on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz
Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes.
The total amount of CPU-time spent on sieving was 35.7 CPU years
estimated to be equivalent to approximately 8000 mips years.
Calendar time for sieving was 3 1/2 months.
For the purpose of comparison, both lattice sieving and line sieving were used.
Lattice sieving was introduced by Pollard [P] and the code used is based
on the implementation described in [GLM, Cetal].
For the lattice sieve, a factor base bound of 16 777 216 (2^24) was chosen,
both for the rational and for the algebraic side. Two large primes were
allowed on both sides.
Most of the line sieve was carried out with two large primes on both the
rational and the algebraic side. The rational factor base consisted of the
primes < 44 000 000 and the algebraic factor base of the primes < 110 000 000.
Some line sieving allowed three large primes instead of two on the algebraic
side. In that case the rational factor base consisted of the primes < 8 000 000
and the algebraic factor base of the primes < 25 000 000.
For both sieves the large prime bound 1 000 000 000 was used both
for the rational and for the algebraic primes.
A total of 124 722 179 relations were generated, 71% of them with lattice
sieving (L), 29% with line sieving (C). Among them, there were 39 187 441
duplicates, partially because of the simultaneous use of the two sievers.
Sieving was done at eleven different locations with the following contributions:
(L: using lattice sieving code from Arjen K. Lenstra
C: using line sieving code from CWI)
20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional
Services, Camberley, UK)
17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK)
14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam)
13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA)
13.0 % (1801) Francois Morain and Gerard Guillerm
(L,C at Ecole Polytechnique, Palaiseau, France)
6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France)
5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA
and Univ. of Sydney, Australia)
4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France)
4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada)
0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands)
0.56 % (47) Chris and Craig Putnam (L at ?)
Calendar time for the sieving was 3.7 months.
The relations were collected at CWI and required 3.7 Gbytes of disk space.
^^^
Filtering and linear algebra
============================
The filtering of the data and the building of the matrix were carried out
at CWI and took one month.
The resulting matrix had 6 699 191 rows, 6 711 336 columns, and weight
417 132 631 (62.27 nonzeros per row).
With the help of Peter Montgomery's Cray implementation of the blocked
Lanczos algorithm (cf. [M95]) it took 224 CPU hours and 2 Gbytes of central
memory on the Cray C916 at the SARA Amsterdam Academic Computer Center to find
64 dependencies among the rows of this matrix.
Calendar time for this job was 9 1/2 days.
Square root
===========
On August 20-21, 1999, four different square root (cf. [M93]) jobs were
started in parallel on four different 300 MHz processors of CWI's SGI Origin
2000, each handling one dependency.
One job found the factorisation after 39.4 CPU-hours, the other three jobs
found the trivial factorization after 38.3, 41.9, and 61.6 CPU-hours (different
CPU times are due to the use of different parameters in the four jobs).
Herman te Riele, CWI, August 26, 1999
with the algorithmic and sieving contributors:
Stefania Cavallar
Bruce Dodson
Arjen Lenstra
Walter Lioen
Peter L. Montgomery
Brian Murphy
and the sieving contributors:
Karen Aardal
Jeff Gilchrist
Gerard Guillerm
Paul Leyland
Joel Marchand
Francois Morain
Alec Muffett
Craig and Chris Putnam
Paul Zimmermann
Acknowledgements are due to the contributors of idle PC and workstation cycles,
to the Dutch National Computing Facilities Foundation (NCF) for the use of
the Cray-C916 supercomputer at SARA and (in alphabetical order) to
Centre Charles Hermite (Nancy, France),
Citibank (Parsippany, NJ, USA),
CWI (Amsterdam, The Netherlands),
Ecole Polytechnique/CNRS (Palaiseau, France),
Entrust Technologies Ltd. (Ottawa, Canada),
Lehigh University (Bethlehem, PA, USA),
the Magma Group of John Cannon at the University of Sydney,
the Medicis Center at Ecole Polytechnique (Palaiseau, France),
Microsoft Research (Cambridge, UK),
Sun Microsystems Professional Services (Camberley, UK), and
The Australian National University (Canberra, Australia)
for the use of their computing resources.
References:
===========
[RSA140]Stefania Cavallar, Bruce Dodson, Arjen Lenstra, Paul Leyland,
Walter Lioen, Peter L. Montgomery, Brian Murphy, Herman te Riele,
and Paul Zimmermann,
Factorization of RSA-140 using the Number Field Sieve, to appear in:
Lam Kwok Yan, Eiji Okamoto, and Xing Chaoping, editors,
Advances in Cryptology -- Asiacrypt '99,
Lecture Notes in Computer Science # xxxx,
Springer--Verlag, Berlin, etc., 1999.
[Cetal] James Cowie, Bruce Dodson, R.-Marije Elkenbracht-Huizing,
Arjen K. Lenstra, Peter L. Montgomery and Joerg Zayer,
A world wide number field sieve factoring record: on to 512 bits,
pp. 382-394 in: Kwangjo Kim and Tsutomu Matsumoto (editors),
Advances in Cryptology - Asiacrypt '96, Lecture Notes in
Computer Science # 1163, Springer-Verlag, Berlin, 1996.
[DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an
explosive experiment, Proceedings Crypto 95, Lecture Notes
in Comput. Sci. 963, (1995) 372-385.
[E1] R.-M. Elkenbracht-Huizing, Factoring integers with the
Number Field Sieve, Doctor's Thesis, Leiden University,
1997.
[E2] R.-M. Elkenbracht-Huizing, An implementation of the number
field sieve, Exp. Math. 5, (1996) 231-253.
[GLM] R. Golliver, A.K. Lenstra, K.S. McCurley, Lattice sieving
and trial division, Algorithmic number theory symposium,
Proceedings, Lecture Notes in Comput. Sci. 877, (1994) 18-27.
[LL] A.K. Lenstra, H.W. Lenstra, Jr., The development of the
number field sieve, Lecture Notes in Math. 1554, Springer-
Verlag, Berlin, 1993
[M93] Peter L. Montgomery, Square roots of products of algebraic
numbers, in Proceedings of Symposia in Applied Mathematics,
Mathematics of Computation 1943-1993, Vancouver, 1993,
Walter Gautschi, ed.
[M95] Peter L. Montgomery, A block Lanczos algorithm for finding
dependencies over GF(2), Proceedings Eurocrypt 1995,
Lecture Notes in Comput. Sci. 921, (1995) 106-120.
[P] J.M. Pollard, The lattice sieve, pages 43-49 in [LL].
Appendix
Here are the P+-1 factorizations of the factors:
102639592829741105772054196573991675900716567808038066803341933521790711307779
p78
102639592829741105772054196573991675900716567808038066803341933521790711307778
2.607.305999.
276297036357806107796483997979900139708537040550885894355659143575473
102639592829741105772054196573991675900716567808038066803341933521790711307780
2.2.3.5.5253077241827.
325649100849833342436871870477394634879398067295372095291531269
106603488380168454820927220360012878679207958575989291522270608237193062808643
p78
106603488380168454820927220360012878679207958575989291522270608237193062808642
2.241.430028152261281581326171.
514312985943800777534375166399250129284222855975011
106603488380168454820927220360012878679207958575989291522270608237193062808644
2.2.3.130637011.237126941204057.10200242155298917871797
28114641748343531603533667478173
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: Mon, 30 Aug 1999 18:07:02 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> 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
Who is 'we'?
You post anonymously. Why should anyone take you seriously?
> because public key encryption can now be
> broken in real time with Bill Payne's recent advances in factoring.
Where did he publish his results? Neither I, nor any other
factoring expert has ever seen his paper.
[send all followups to alt.kook]
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: WT Shaw temporarily sidelined
Date: Mon, 30 Aug 1999 18:29:40 GMT
[EMAIL PROTECTED] wrote, in part:
>This may be a dumb question, but what's wrong with him?
I don't know; often, people don't choose to release that information.
But he is in the hospital, and IIRC he is of advanced age.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 1999 18:44:16 +0200
[EMAIL PROTECTED] writes:
> From [EMAIL PROTECTED] (Paul Rubin):
> > [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.
>
> No Paul, you are mistaken.
I'm sure other posters will sugar-coat it, but: You are an idiot. Fuck off.
Rob.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Mon, 30 Aug 1999 17:45:29 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Bob Silverman wrote:
> >
> > > 4. Algorithmic breakthroughs are possible. RSA 512 was thought >>totally
>unbreakable just a few years ago.
> >
> > > Don Johnson
> > >
> > More deceit and lies.
> >
>
> [here he goes again!]
>
> >
> > If, by "a few years ago", you mean 15 years, I will agree.
> >
>
> of cours. The inventors of RSA gave out a challenge, they beleived that
> factoring
> would have taken _much_ longer time (be it impossible). (was that in a
> Scientific
> American journal of something...?).
> Why use the words "deceit and lies" for this statement, when we all know it
> is
> true!
Your facts are confused.
The RSA-129 factoring challenge dates from a 1977 article.
This pre-dates both the quadratic sieve and parallel factoring
methods.
I would call 22 years (1999-1977) more than 'a few years'.
Secondly, as Ron himself has admitted, when he made the
claim about '40 quadrillion years' for RSA-129, he had forgotten
about the continued fraction algorithm. (invented in 1970). Ron
had only considered trial division when he made this now
famous and mistaken estimate. Even back in 1977 it would
not have taken anywhere close to what Ron had estimated.
(But it was legitimately out of reach then)
Thirdly, while Ron is a world class cryptographer, he is not
an expert on factoring algorithms. Nor did he consult with anyone
when he made his 1977 quote.
>
> > The parallel quadratic sieve changed that.
> >
> > We have known sine the mid-80's the level of effort needed for 512
> > bit keys when attacked by QS. However, computers were not
> > fast enough nor abundant enough at that time to consider doing it.
> >
> > We have known since about 1990 the level of effort needed for
> > 512 bit keys when attacked by NFS. We could have done
> > RSA-155 back in 1991 with sufficient effort (albeit much greater
> > effort than was used recently; we needed to learn how to
> > fine tune NFS to get good performance and climbing that learning curve
> > took time)
> >
>
> What do you mean by *we*.
I mean the factoring community.
> Are you talking about RSA labs?
> First of all, Pomerance (1982) came up with QS
Try 1980.
> Pollard came up with NFS
> (1993).
Try 1989.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Mon, 30 Aug 1999 14:52:45 -0400
> Your facts are confused.
>
> The RSA-129 factoring challenge dates from a 1977 article.
> This pre-dates both the quadratic sieve and parallel factoring
> methods.
Yes, I never said the contrary.
>
> I would call 22 years (1999-1977) more than 'a few years'.
>
Ahhh, if you say so. It still stands that cryptologues had no idea
of how to factor.
>
> > Are you talking about RSA labs?
> > First of all, Pomerance (1982) came up with QS
>
> Try 1980.
>
These are the refs I have for Pomerance QS:
@InCollection{Po82,
author = "C. Pomerance",
title = "Analysis and comparison of some integer factoring
algorithms",
booktitle = "Computational Methods in Number Theory",
editor = "H. W. {Lenstra, Jr.} and R. Tijdeman",
publisher = "Math.\ Centrum Tract 154",
address = "Amsterdam",
year = "1982",
pages = "89--139",
}
@InProceedings{Po84,
title = "The Quadratic Sieve Factoring Algorithm",
author = "Carl Pomerance",
pages = "169--182",
booktitle = "Advances in Cryptology: Proceedings of
{EUROCRYPT}~84",
editor = "T. Beth and N. Cot and I. Ingemarsson",
year = "1984",
month = "9--11~" # apr,
series = "Lecture Notes in Computer Science",
volume = "209",
publisher = "Springer-Verlag, 1985",
}
What ref do you have that states 1980?
> > Pollard came up with NFS
> > (1993).
>
> Try 1989.
>
O.k., you are correct here
@InProceedings{LMP90,
author = "A. K. Lenstra and H. W. {Lenstra, Jr.} and M. S.
Manasse and J. M. Pollard",
title = "The Number Field Sieve",
editor = "{ACM}",
booktitle = "Proceedings of the twenty-second annual {ACM}
Symposium on Theory of Computing, Baltimore, Maryland,
May 14--16, 1990",
publisher = "ACM Press",
address = "New York, NY 10036, USA",
year = "1990",
ISBN = "0-89791-361-2",
pages = "564--572",
year = "1990",
bibdate = "Thu Jan 21 13:33:06 1999",
note = "For discussion of the generalized number field sieve,
see \cite{Lenstra:1993:FNF}.",
acknowledgement = ack-nhfb,
}
I was thinking GNFS
@Article{LMP93,
author = "A. K. Lenstra and H. W. {Lenstra, Jr.} and M. S.
Manasse and J. M. Pollard",
title = "The factorization of the ninth {Fermat} number",
journal = "Mathematics of Computation",
volume = "61",
number = "203",
pages = "319--349",
month = jul,
year = "1993",
coden = "MCMPAF",
ISSN = "0025-5718",
mrclass = "11Y05 (11Y40)",
mrnumber = "93k:11116",
mrreviewer = "Rhonda Lee Hatcher",
bibdate = "Thu Apr 29 18:02:36 1999",
note = "See \cite{Lenstra:1990:NFS}.",
acknowledgement = ack-nhfb,
}
as
------------------------------
From: "shivers" <[EMAIL PROTECTED]>
Subject: Re: public key encryption - unlicensed algorithm
Date: Mon, 30 Aug 1999 19:26:26 +0100
Further to my original message, some details about what it's for:
The main purpose is for the development of a _very_ secure online credit
card submission system - where the details stay encryption all the way from
the user's desktop to the serving company's payment processing desk.
Therefore key management is not an issue - the only problem really being
making sure that the (Java) code to be used to encrypt the data cannot be
used to decrypt the data - hence the requirement for a public key algorithm.
Before anyone says it, I know SSL is the de facto standard - but with 40bit
security being the current legal limit (in this country at least) I'm after
something a little stronger...
...I am also looking at various other uses - but that detailed above is the
main one.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: 512 bit number factored
Date: 30 Aug 1999 18:51:45 GMT
It still seems that RSA Labs may not have recommended increasing the key size
of RSA keys beyond 512 bits until 1995. If someone can find an earlier date,
please report it. But if that is the case, then it is only a few years.
Don Johnson
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Mon, 30 Aug 1999 14:53:43 -0400
DJohn37050 wrote:
> It still seems that RSA Labs may not have recommended increasing the key size
> of RSA keys beyond 512 bits until 1995. If someone can find an earlier date,
> please report it. But if that is the case, then it is only a few years.
> Don Johnson
I would also be interested in seeing such an article! An article that "backs
up" its
statements.
as
------------------------------
** 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
******************************
