On the improvement of Wiener attack on RSA with small private exponent.
Identifieur interne : 001E75 ( PubMed/Checkpoint ); précédent : 001E74; suivant : 001E76On the improvement of Wiener attack on RSA with small private exponent.
Auteurs : Mu-En Wu [Taïwan] ; Chien-Ming Chen [République populaire de Chine] ; Yue-Hsun Lin [États-Unis] ; Hung-Min Sun [Taïwan]Source :
- TheScientificWorldJournal [ 1537-744X ] ; 2014.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
RSA system is based on the hardness of the integer factorization problem (IFP). Given an RSA modulus N = pq, it is difficult to determine the prime factors p and q efficiently. One of the most famous short exponent attacks on RSA is the Wiener attack. In 1997, Verheul and van Tilborg use an exhaustive search to extend the boundary of the Wiener attack. Their result shows that the cost of exhaustive search is 2r + 8 bits when extending the Weiner's boundary r bits. In this paper, we first reduce the cost of exhaustive search from 2r + 8 bits to 2r + 2 bits. Then, we propose a method named EPF. With EPF, the cost of exhaustive search is further reduced to 2r - 6 bits when we extend Weiner's boundary r bits. It means that our result is 2(14) times faster than Verheul and van Tilborg's result. Besides, the security boundary is extended 7 bits.
DOI: 10.1155/2014/650537
PubMed: 24982974
Affiliations:
- République populaire de Chine, Taïwan, États-Unis
- Guangdong, Pennsylvanie
- Pittsburgh, Shenzhen
- Université Carnegie-Mellon
Links toward previous steps (curation, corpus...)
Links to Exploration step
pubmed:24982974Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the improvement of Wiener attack on RSA with small private exponent.</title><author><name sortKey="Wu, Mu En" sort="Wu, Mu En" uniqKey="Wu M" first="Mu-En" last="Wu">Mu-En Wu</name><affiliation wicri:level="1"><nlm:affiliation>Department of Mathematics, Soochow University, Taipei, Taiwan.</nlm:affiliation><country xml:lang="fr">Taïwan</country><wicri:regionArea>Department of Mathematics, Soochow University, Taipei</wicri:regionArea><wicri:noRegion>Taipei</wicri:noRegion></affiliation></author><author><name sortKey="Chen, Chien Ming" sort="Chen, Chien Ming" uniqKey="Chen C" first="Chien-Ming" last="Chen">Chien-Ming Chen</name><affiliation wicri:level="3"><nlm:affiliation>School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China ; Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen, China.</nlm:affiliation><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China ; Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen</wicri:regionArea><placeName><settlement type="city">Shenzhen</settlement><region type="province">Guangdong</region></placeName></affiliation></author><author><name sortKey="Lin, Yue Hsun" sort="Lin, Yue Hsun" uniqKey="Lin Y" first="Yue-Hsun" last="Lin">Yue-Hsun Lin</name><affiliation wicri:level="4"><nlm:affiliation>CyLab, Carnegie Mellon University, Pittsburgh, PA 15213, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>CyLab, Carnegie Mellon University, Pittsburgh, PA 15213</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Sun, Hung Min" sort="Sun, Hung Min" uniqKey="Sun H" first="Hung-Min" last="Sun">Hung-Min Sun</name><affiliation wicri:level="1"><nlm:affiliation>Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan.</nlm:affiliation><country xml:lang="fr">Taïwan</country><wicri:regionArea>Department of Computer Science, National Tsing Hua University, Hsinchu</wicri:regionArea><wicri:noRegion>Hsinchu</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2014">2014</date><idno type="RBID">pubmed:24982974</idno><idno type="pmid">24982974</idno><idno type="doi">10.1155/2014/650537</idno><idno type="wicri:Area/PubMed/Corpus">003E66</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">003E66</idno><idno type="wicri:Area/PubMed/Curation">003E39</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">003E39</idno><idno type="wicri:Area/PubMed/Checkpoint">003E39</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">003E39</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On the improvement of Wiener attack on RSA with small private exponent.</title><author><name sortKey="Wu, Mu En" sort="Wu, Mu En" uniqKey="Wu M" first="Mu-En" last="Wu">Mu-En Wu</name><affiliation wicri:level="1"><nlm:affiliation>Department of Mathematics, Soochow University, Taipei, Taiwan.</nlm:affiliation><country xml:lang="fr">Taïwan</country><wicri:regionArea>Department of Mathematics, Soochow University, Taipei</wicri:regionArea><wicri:noRegion>Taipei</wicri:noRegion></affiliation></author><author><name sortKey="Chen, Chien Ming" sort="Chen, Chien Ming" uniqKey="Chen C" first="Chien-Ming" last="Chen">Chien-Ming Chen</name><affiliation wicri:level="3"><nlm:affiliation>School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China ; Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen, China.</nlm:affiliation><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China ; Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen</wicri:regionArea><placeName><settlement type="city">Shenzhen</settlement><region type="province">Guangdong</region></placeName></affiliation></author><author><name sortKey="Lin, Yue Hsun" sort="Lin, Yue Hsun" uniqKey="Lin Y" first="Yue-Hsun" last="Lin">Yue-Hsun Lin</name><affiliation wicri:level="4"><nlm:affiliation>CyLab, Carnegie Mellon University, Pittsburgh, PA 15213, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>CyLab, Carnegie Mellon University, Pittsburgh, PA 15213</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Sun, Hung Min" sort="Sun, Hung Min" uniqKey="Sun H" first="Hung-Min" last="Sun">Hung-Min Sun</name><affiliation wicri:level="1"><nlm:affiliation>Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan.</nlm:affiliation><country xml:lang="fr">Taïwan</country><wicri:regionArea>Department of Computer Science, National Tsing Hua University, Hsinchu</wicri:regionArea><wicri:noRegion>Hsinchu</wicri:noRegion></affiliation></author></analytic><series><title level="j">TheScientificWorldJournal</title><idno type="eISSN">1537-744X</idno><imprint><date when="2014" type="published">2014</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Models, Theoretical</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term><term>Modèles théoriques</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Models, Theoretical</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Modèles théoriques</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">RSA system is based on the hardness of the integer factorization problem (IFP). Given an RSA modulus N = pq, it is difficult to determine the prime factors p and q efficiently. One of the most famous short exponent attacks on RSA is the Wiener attack. In 1997, Verheul and van Tilborg use an exhaustive search to extend the boundary of the Wiener attack. Their result shows that the cost of exhaustive search is 2r + 8 bits when extending the Weiner's boundary r bits. In this paper, we first reduce the cost of exhaustive search from 2r + 8 bits to 2r + 2 bits. Then, we propose a method named EPF. With EPF, the cost of exhaustive search is further reduced to 2r - 6 bits when we extend Weiner's boundary r bits. It means that our result is 2(14) times faster than Verheul and van Tilborg's result. Besides, the security boundary is extended 7 bits.</div></front></TEI><pubmed><MedlineCitation Status="MEDLINE" Owner="NLM"><PMID Version="1">24982974</PMID><DateCreated><Year>2014</Year><Month>07</Month><Day>01</Day></DateCreated><DateCompleted><Year>2014</Year><Month>10</Month><Day>28</Day></DateCompleted><DateRevised><Year>2015</Year><Month>08</Month><Day>05</Day></DateRevised><Article PubModel="Print-Electronic"><Journal><ISSN IssnType="Electronic">1537-744X</ISSN><JournalIssue CitedMedium="Internet"><Volume>2014</Volume><PubDate><Year>2014</Year></PubDate></JournalIssue><Title>TheScientificWorldJournal</Title><ISOAbbreviation>ScientificWorldJournal</ISOAbbreviation></Journal><ArticleTitle>On the improvement of Wiener attack on RSA with small private exponent.</ArticleTitle><Pagination><MedlinePgn>650537</MedlinePgn></Pagination><ELocationID EIdType="doi" ValidYN="Y">10.1155/2014/650537</ELocationID><Abstract><AbstractText>RSA system is based on the hardness of the integer factorization problem (IFP). Given an RSA modulus N = pq, it is difficult to determine the prime factors p and q efficiently. One of the most famous short exponent attacks on RSA is the Wiener attack. In 1997, Verheul and van Tilborg use an exhaustive search to extend the boundary of the Wiener attack. Their result shows that the cost of exhaustive search is 2r + 8 bits when extending the Weiner's boundary r bits. In this paper, we first reduce the cost of exhaustive search from 2r + 8 bits to 2r + 2 bits. Then, we propose a method named EPF. With EPF, the cost of exhaustive search is further reduced to 2r - 6 bits when we extend Weiner's boundary r bits. It means that our result is 2(14) times faster than Verheul and van Tilborg's result. Besides, the security boundary is extended 7 bits.</AbstractText></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Wu</LastName><ForeName>Mu-En</ForeName><Initials>ME</Initials><Identifier Source="ORCID">0000-0002-4839-3849</Identifier><AffiliationInfo><Affiliation>Department of Mathematics, Soochow University, Taipei, Taiwan.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Chen</LastName><ForeName>Chien-Ming</ForeName><Initials>CM</Initials><AffiliationInfo><Affiliation>School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China ; Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen, China.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Lin</LastName><ForeName>Yue-Hsun</ForeName><Initials>YH</Initials><AffiliationInfo><Affiliation>CyLab, Carnegie Mellon University, Pittsburgh, PA 15213, USA.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Sun</LastName><ForeName>Hung-Min</ForeName><Initials>HM</Initials><Identifier Source="ORCID">0000-0003-0870-9973</Identifier><AffiliationInfo><Affiliation>Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan.</Affiliation></AffiliationInfo></Author></AuthorList><Language>eng</Language><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType><PublicationType UI="D013485">Research Support, Non-U.S. Gov't</PublicationType></PublicationTypeList><ArticleDate DateType="Electronic"><Year>2014</Year><Month>03</Month><Day>27</Day></ArticleDate></Article><MedlineJournalInfo><Country>United States</Country><MedlineTA>ScientificWorldJournal</MedlineTA><NlmUniqueID>101131163</NlmUniqueID><ISSNLinking>1537-744X</ISSNLinking></MedlineJournalInfo><CitationSubset>IM</CitationSubset><CommentsCorrectionsList><CommentsCorrections RefType="Cites"><RefSource>ScientificWorldJournal. 2013;2013:860621</RefSource><PMID Version="1">24078798</PMID></CommentsCorrections></CommentsCorrectionsList><MeshHeadingList><MeshHeading><DescriptorName UI="D000465" MajorTopicYN="N">Algorithms</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D008962" MajorTopicYN="Y">Models, Theoretical</DescriptorName></MeshHeading></MeshHeadingList><OtherID Source="NLM">PMC3985315</OtherID></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="received"><Year>2014</Year><Month>02</Month><Day>07</Day></PubMedPubDate><PubMedPubDate PubStatus="accepted"><Year>2014</Year><Month>02</Month><Day>27</Day></PubMedPubDate><PubMedPubDate PubStatus="entrez"><Year>2014</Year><Month>7</Month><Day>2</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="pubmed"><Year>2014</Year><Month>7</Month><Day>2</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2014</Year><Month>10</Month><Day>29</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>ppublish</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">24982974</ArticleId><ArticleId IdType="doi">10.1155/2014/650537</ArticleId><ArticleId IdType="pmc">PMC3985315</ArticleId></ArticleIdList></PubmedData></pubmed><affiliations><list><country><li>République populaire de Chine</li><li>Taïwan</li><li>États-Unis</li></country><region><li>Guangdong</li><li>Pennsylvanie</li></region><settlement><li>Pittsburgh</li><li>Shenzhen</li></settlement><orgName><li>Université Carnegie-Mellon</li></orgName></list><tree><country name="Taïwan"><noRegion><name sortKey="Wu, Mu En" sort="Wu, Mu En" uniqKey="Wu M" first="Mu-En" last="Wu">Mu-En Wu</name></noRegion><name sortKey="Sun, Hung Min" sort="Sun, Hung Min" uniqKey="Sun H" first="Hung-Min" last="Sun">Hung-Min Sun</name></country><country name="République populaire de Chine"><region name="Guangdong"><name sortKey="Chen, Chien Ming" sort="Chen, Chien Ming" uniqKey="Chen C" first="Chien-Ming" last="Chen">Chien-Ming Chen</name></region></country><country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Lin, Yue Hsun" sort="Lin, Yue Hsun" uniqKey="Lin Y" first="Yue-Hsun" last="Lin">Yue-Hsun Lin</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/PubMed/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001E75 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PubMed/Checkpoint/biblio.hfd -nk 001E75 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Amérique
|area= PittsburghV1
|flux= PubMed
|étape= Checkpoint
|type= RBID
|clé= pubmed:24982974
|texte= On the improvement of Wiener attack on RSA with small private exponent.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Checkpoint/RBID.i -Sk "pubmed:24982974" \
| HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Checkpoint/biblio.hfd \
| NlmPubMed2Wicri -a PittsburghV1
| This area was generated with Dilib version V0.6.38. |  |