InforLorV4, Main, Merge, bibRecord, 00B174

Factorization of RSA-140 using the Number Field sieve

Identifieur interne : 00B174 ( Main/Merge ); précédent : 00B173; suivant : 00B175

Factorization of RSA-140 using the Number Field sieve

Auteurs : S. Cavallar [Pays-Bas] ; B. Dodson [États-Unis] ; A. Lenstra [États-Unis] ; P. Leyland [Royaume-Uni] ; W. Lioen [Pays-Bas] ; P. L. Montgomery [États-Unis] ; B. Murphy [Australie] ; H. Te Riele [Pays-Bas] ; P. Zimmermann [France]

Source :

Lecture notes in computer science [ 0302-9743 ] ; 1999.

RBID : Pascal:00-0001758

Descripteurs français

Pascal (Inist)
- Cryptographie, Factorisation, Temps calcul, Théorie nombre, Implémentation, Méthode polynomiale, Problème sélection, Internet, Réseau WWW, RSA-140, Cryptage.
Wicri :
- topic : Cryptographie.

English descriptors

KwdEn :
- Computation time, Cryptography, Encryption, Factorization, Implementation, Internet, Number theory, Polynomial method, Selection problem, World wide web.

Abstract

On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper. The implications of the new polynomial selection method for factoring a 512-bit RSA modulus are discussed and it is concluded that 512-bit (= 155-digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000A81
to stream PascalFrancis, to step Curation: 000001
to stream PascalFrancis, to step Checkpoint: 000A86

Links to Exploration step

Pascal:00-0001758

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Factorization of RSA-140 using the Number Field sieve</title>
<author><name sortKey="Cavallar, S" sort="Cavallar, S" uniqKey="Cavallar S" first="S." last="Cavallar">S. Cavallar</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Dodson, B" sort="Dodson, B" uniqKey="Dodson B" first="B." last="Dodson">B. Dodson</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Lehigh University</s1>
<s2>Bethlehem, PA</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Lehigh University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Lenstra, A" sort="Lenstra, A" uniqKey="Lenstra A" first="A." last="Lenstra">A. Lenstra</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Citibank, Parsippany</s1>
<s2>NJ</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>NJ</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Leyland, P" sort="Leyland, P" uniqKey="Leyland P" first="P." last="Leyland">P. Leyland</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>Microsoft Research Ltd</s1>
<s2>Cambridge</s2>
<s3>GBR</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
<wicri:noRegion>Microsoft Research Ltd</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Lioen, W" sort="Lioen, W" uniqKey="Lioen W" first="W." last="Lioen">W. Lioen</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Montgomery, P L" sort="Montgomery, P L" uniqKey="Montgomery P" first="P. L." last="Montgomery">P. L. Montgomery</name>
<affiliation wicri:level="1"><inist:fA14 i1="05"><s1>Microsoft Research and CWI, 780 Las Colindas Road</s1>
<s2>San Rafael, CA 94903-2346</s2>
<s3>USA</s3>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>San Rafael, CA 94903-2346</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Murphy, B" sort="Murphy, B" uniqKey="Murphy B" first="B." last="Murphy">B. Murphy</name>
<affiliation wicri:level="1"><inist:fA14 i1="06"><s1>Computer Sciences Laboratory, The Australian National University</s1>
<s2>Canberra ACT 0200</s2>
<s3>AUS</s3>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Australie</country>
<wicri:noRegion>Canberra ACT 0200</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Te Riele, H" sort="Te Riele, H" uniqKey="Te Riele H" first="H." last="Te Riele">H. Te Riele</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Zimmermann, P" sort="Zimmermann, P" uniqKey="Zimmermann P" first="P." last="Zimmermann">P. Zimmermann</name>
<affiliation wicri:level="3"><inist:fA14 i1="07"><s1>Inria Lorraine and Loria</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>9 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">00-0001758</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 00-0001758 INIST</idno>
<idno type="RBID">Pascal:00-0001758</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A81</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000001</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000A86</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A86</idno>
<idno type="wicri:doubleKey">0302-9743:1999:Cavallar S:factorization:of:rsa</idno>
<idno type="wicri:Area/Main/Merge">00B174</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Factorization of RSA-140 using the Number Field sieve</title>
<author><name sortKey="Cavallar, S" sort="Cavallar, S" uniqKey="Cavallar S" first="S." last="Cavallar">S. Cavallar</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Dodson, B" sort="Dodson, B" uniqKey="Dodson B" first="B." last="Dodson">B. Dodson</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Lehigh University</s1>
<s2>Bethlehem, PA</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Lehigh University</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Lenstra, A" sort="Lenstra, A" uniqKey="Lenstra A" first="A." last="Lenstra">A. Lenstra</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Citibank, Parsippany</s1>
<s2>NJ</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>NJ</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Leyland, P" sort="Leyland, P" uniqKey="Leyland P" first="P." last="Leyland">P. Leyland</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>Microsoft Research Ltd</s1>
<s2>Cambridge</s2>
<s3>GBR</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
<wicri:noRegion>Microsoft Research Ltd</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Lioen, W" sort="Lioen, W" uniqKey="Lioen W" first="W." last="Lioen">W. Lioen</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Montgomery, P L" sort="Montgomery, P L" uniqKey="Montgomery P" first="P. L." last="Montgomery">P. L. Montgomery</name>
<affiliation wicri:level="1"><inist:fA14 i1="05"><s1>Microsoft Research and CWI, 780 Las Colindas Road</s1>
<s2>San Rafael, CA 94903-2346</s2>
<s3>USA</s3>
<sZ>6 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>San Rafael, CA 94903-2346</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Murphy, B" sort="Murphy, B" uniqKey="Murphy B" first="B." last="Murphy">B. Murphy</name>
<affiliation wicri:level="1"><inist:fA14 i1="06"><s1>Computer Sciences Laboratory, The Australian National University</s1>
<s2>Canberra ACT 0200</s2>
<s3>AUS</s3>
<sZ>7 aut.</sZ>
</inist:fA14>
<country>Australie</country>
<wicri:noRegion>Canberra ACT 0200</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Te Riele, H" sort="Te Riele, H" uniqKey="Te Riele H" first="H." last="Te Riele">H. Te Riele</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CWI, P.O. Box 94079</s1>
<s2>1090 GB Amsterdam</s2>
<s3>NLD</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Pays-Bas</country>
<wicri:noRegion>1090 GB Amsterdam</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Zimmermann, P" sort="Zimmermann, P" uniqKey="Zimmermann P" first="P." last="Zimmermann">P. Zimmermann</name>
<affiliation wicri:level="3"><inist:fA14 i1="07"><s1>Inria Lorraine and Loria</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>9 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="1999">1999</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computation time</term>
<term>Cryptography</term>
<term>Encryption</term>
<term>Factorization</term>
<term>Implementation</term>
<term>Internet</term>
<term>Number theory</term>
<term>Polynomial method</term>
<term>Selection problem</term>
<term>World wide web</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Cryptographie</term>
<term>Factorisation</term>
<term>Temps calcul</term>
<term>Théorie nombre</term>
<term>Implémentation</term>
<term>Méthode polynomiale</term>
<term>Problème sélection</term>
<term>Internet</term>
<term>Réseau WWW</term>
<term>RSA-140</term>
<term>Cryptage</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper. The implications of the new polynomial selection method for factoring a 512-bit RSA modulus are discussed and it is concluded that 512-bit (= 155-digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Pays-Bas</li>
<li>Royaume-Uni</li>
<li>États-Unis</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Nancy</li>
</settlement>
</list>
<tree><country name="Pays-Bas"><noRegion><name sortKey="Cavallar, S" sort="Cavallar, S" uniqKey="Cavallar S" first="S." last="Cavallar">S. Cavallar</name>
</noRegion>
<name sortKey="Lioen, W" sort="Lioen, W" uniqKey="Lioen W" first="W." last="Lioen">W. Lioen</name>
<name sortKey="Te Riele, H" sort="Te Riele, H" uniqKey="Te Riele H" first="H." last="Te Riele">H. Te Riele</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Dodson, B" sort="Dodson, B" uniqKey="Dodson B" first="B." last="Dodson">B. Dodson</name>
</noRegion>
<name sortKey="Lenstra, A" sort="Lenstra, A" uniqKey="Lenstra A" first="A." last="Lenstra">A. Lenstra</name>
<name sortKey="Montgomery, P L" sort="Montgomery, P L" uniqKey="Montgomery P" first="P. L." last="Montgomery">P. L. Montgomery</name>
</country>
<country name="Royaume-Uni"><noRegion><name sortKey="Leyland, P" sort="Leyland, P" uniqKey="Leyland P" first="P." last="Leyland">P. Leyland</name>
</noRegion>
</country>
<country name="Australie"><noRegion><name sortKey="Murphy, B" sort="Murphy, B" uniqKey="Murphy B" first="B." last="Murphy">B. Murphy</name>
</noRegion>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Zimmermann, P" sort="Zimmermann, P" uniqKey="Zimmermann P" first="P." last="Zimmermann">P. Zimmermann</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B174 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00B174 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Merge
   |type=    RBID
   |clé=     Pascal:00-0001758
   |texte=   Factorization of RSA-140 using the Number Field sieve
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Factorization of RSA-140 using the Number Field sieve

Factorization of RSA-140 using the Number Field sieve

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri