Software Implementation of Modular Exponentiation, Using Advanced Vector Instructions Architectures View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Shay Gueron , Vlad Krasnov

ABSTRACT

This paper describes an algorithm for computing modular exponentiation using vector (SIMD) instructions. It demonstrates, for the first time, how such a software approach can outperform the classical scalar (ALU) implementations, on the high end x86_64 platforms, if they have a wide SIMD architecture. Here, we target speeding up RSA2048 on Intel’s soon-to-arrive platforms that support the AVX2 instruction set. To this end, we applied our algorithm and generated an optimized AVX2-based software implementation of 1024-bit modular exponentiation. This implementation is seamlessly integrated into OpenSSL, by patching over OpenSSL 1.0.1. Our results show that our implementation requires 51% less instructions than the current OpenSSL 1.0.1 implementation. This illustrates the potential significant speedup in the RSA2048 performance, which is expected in the coming (2013) Intel processors. The impact of such speedup on servers is noticeable, especially since migration to RSA2048 is recommended by NIST, starting from 2013. More... »

PAGES

119-135

References to SciGraph publications

Book

TITLE

Arithmetic of Finite Fields

ISBN

978-3-642-31661-6
978-3-642-31662-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31662-3_9

DOI

http://dx.doi.org/10.1007/978-3-642-31662-3_9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032931092


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Haifa", 
          "id": "https://www.grid.ac/institutes/grid.18098.38", 
          "name": [
            "Department of Mathematics, University of Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gueron", 
        "givenName": "Shay", 
        "id": "sg:person.01343073557.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01343073557.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Intel Corporation, Israel Development Center, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krasnov", 
        "givenName": "Vlad", 
        "id": "sg:person.014171561755.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014171561755.37"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45760-7_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039182300", 
          "https://doi.org/10.1007/3-540-45760-7_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48059-5_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040330126", 
          "https://doi.org/10.1007/3-540-48059-5_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48059-5_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040330126", 
          "https://doi.org/10.1007/3-540-48059-5_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s13389-012-0031-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041407203", 
          "https://doi.org/10.1007/s13389-012-0031-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-36400-5_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053463230", 
          "https://doi.org/10.1007/3-540-36400-5_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-36400-5_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053463230", 
          "https://doi.org/10.1007/3-540-36400-5_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1049/el:19991230", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056788977"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/comjnl/bxm099", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059479898"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.2004.100", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061533917"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/itng.2012.61", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094365024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511921698", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098776070"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "This paper describes an algorithm for computing modular exponentiation using vector (SIMD) instructions. It demonstrates, for the first time, how such a software approach can outperform the classical scalar (ALU) implementations, on the high end x86_64 platforms, if they have a wide SIMD architecture. Here, we target speeding up RSA2048 on Intel\u2019s soon-to-arrive platforms that support the AVX2 instruction set. To this end, we applied our algorithm and generated an optimized AVX2-based software implementation of 1024-bit modular exponentiation. This implementation is seamlessly integrated into OpenSSL, by patching over OpenSSL 1.0.1. Our results show that our implementation requires 51% less instructions than the current OpenSSL 1.0.1 implementation. This illustrates the potential significant speedup in the RSA2048 performance, which is expected in the coming (2013) Intel processors. The impact of such speedup on servers is noticeable, especially since migration to RSA2048 is recommended by NIST, starting from 2013.", 
    "editor": [
      {
        "familyName": "\u00d6zbudak", 
        "givenName": "Ferruh", 
        "type": "Person"
      }, 
      {
        "familyName": "Rodr\u00edguez-Henr\u00edquez", 
        "givenName": "Francisco", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31662-3_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31661-6", 
        "978-3-642-31662-3"
      ], 
      "name": "Arithmetic of Finite Fields", 
      "type": "Book"
    }, 
    "name": "Software Implementation of Modular Exponentiation, Using Advanced Vector Instructions Architectures", 
    "pagination": "119-135", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31662-3_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9ce13a23220f71d7d4e881423695537267844b683149688f1fcb40fa10655910"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032931092"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31662-3_9", 
      "https://app.dimensions.ai/details/publication/pub.1032931092"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000263.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-31662-3_9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31662-3_9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31662-3_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31662-3_9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31662-3_9'


 

This table displays all metadata directly associated to this object as RDF triples.

110 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31662-3_9 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N8b3b948bdf5c47599a1d6bf7966fdc7a
4 schema:citation sg:pub.10.1007/3-540-36400-5_5
5 sg:pub.10.1007/3-540-45760-7_3
6 sg:pub.10.1007/3-540-48059-5_9
7 sg:pub.10.1007/s13389-012-0031-5
8 https://doi.org/10.1017/cbo9780511921698
9 https://doi.org/10.1049/el:19991230
10 https://doi.org/10.1093/comjnl/bxm099
11 https://doi.org/10.1109/itng.2012.61
12 https://doi.org/10.1109/tc.2004.100
13 schema:datePublished 2012
14 schema:datePublishedReg 2012-01-01
15 schema:description This paper describes an algorithm for computing modular exponentiation using vector (SIMD) instructions. It demonstrates, for the first time, how such a software approach can outperform the classical scalar (ALU) implementations, on the high end x86_64 platforms, if they have a wide SIMD architecture. Here, we target speeding up RSA2048 on Intel’s soon-to-arrive platforms that support the AVX2 instruction set. To this end, we applied our algorithm and generated an optimized AVX2-based software implementation of 1024-bit modular exponentiation. This implementation is seamlessly integrated into OpenSSL, by patching over OpenSSL 1.0.1. Our results show that our implementation requires 51% less instructions than the current OpenSSL 1.0.1 implementation. This illustrates the potential significant speedup in the RSA2048 performance, which is expected in the coming (2013) Intel processors. The impact of such speedup on servers is noticeable, especially since migration to RSA2048 is recommended by NIST, starting from 2013.
16 schema:editor N1463580a28ff4c8ca94b1a4c950d4082
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N7a72d519c9b94531a5c250fbe5ba09df
21 schema:name Software Implementation of Modular Exponentiation, Using Advanced Vector Instructions Architectures
22 schema:pagination 119-135
23 schema:productId N87064c7ec71646f3842b29f0fc95b2e2
24 N9fa98d42da5c42fb808e6bfb2fdd24aa
25 Nc1d9084a381b45e88614ecb5c38d0f1a
26 schema:publisher N55272e713aea46a485d0cd5e1389e296
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032931092
28 https://doi.org/10.1007/978-3-642-31662-3_9
29 schema:sdDatePublished 2019-04-15T14:26
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N3b83322bf97344409817b3a6ba6c42c2
32 schema:url http://link.springer.com/10.1007/978-3-642-31662-3_9
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N1463580a28ff4c8ca94b1a4c950d4082 rdf:first Na8723d862687454eb185e1db956970e7
37 rdf:rest Ne49eb896f00545f18bbd872a8a4da780
38 N3b83322bf97344409817b3a6ba6c42c2 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N55272e713aea46a485d0cd5e1389e296 schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N76db1b8a936e4e1e896ff8de910ddc28 schema:familyName Rodríguez-Henríquez
44 schema:givenName Francisco
45 rdf:type schema:Person
46 N7a72d519c9b94531a5c250fbe5ba09df schema:isbn 978-3-642-31661-6
47 978-3-642-31662-3
48 schema:name Arithmetic of Finite Fields
49 rdf:type schema:Book
50 N87064c7ec71646f3842b29f0fc95b2e2 schema:name readcube_id
51 schema:value 9ce13a23220f71d7d4e881423695537267844b683149688f1fcb40fa10655910
52 rdf:type schema:PropertyValue
53 N8b3b948bdf5c47599a1d6bf7966fdc7a rdf:first sg:person.01343073557.40
54 rdf:rest Nde5b998b35b246838809ddde27e3f50f
55 N9fa98d42da5c42fb808e6bfb2fdd24aa schema:name dimensions_id
56 schema:value pub.1032931092
57 rdf:type schema:PropertyValue
58 Na8723d862687454eb185e1db956970e7 schema:familyName Özbudak
59 schema:givenName Ferruh
60 rdf:type schema:Person
61 Nc1d9084a381b45e88614ecb5c38d0f1a schema:name doi
62 schema:value 10.1007/978-3-642-31662-3_9
63 rdf:type schema:PropertyValue
64 Nde5b998b35b246838809ddde27e3f50f rdf:first sg:person.014171561755.37
65 rdf:rest rdf:nil
66 Ne49eb896f00545f18bbd872a8a4da780 rdf:first N76db1b8a936e4e1e896ff8de910ddc28
67 rdf:rest rdf:nil
68 Necf0c72ab9d64b119c0471f81fdad444 schema:name Intel Corporation, Israel Development Center, Haifa, Israel
69 rdf:type schema:Organization
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computer Software
75 rdf:type schema:DefinedTerm
76 sg:person.01343073557.40 schema:affiliation https://www.grid.ac/institutes/grid.18098.38
77 schema:familyName Gueron
78 schema:givenName Shay
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01343073557.40
80 rdf:type schema:Person
81 sg:person.014171561755.37 schema:affiliation Necf0c72ab9d64b119c0471f81fdad444
82 schema:familyName Krasnov
83 schema:givenName Vlad
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014171561755.37
85 rdf:type schema:Person
86 sg:pub.10.1007/3-540-36400-5_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053463230
87 https://doi.org/10.1007/3-540-36400-5_5
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/3-540-45760-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039182300
90 https://doi.org/10.1007/3-540-45760-7_3
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/3-540-48059-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040330126
93 https://doi.org/10.1007/3-540-48059-5_9
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/s13389-012-0031-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041407203
96 https://doi.org/10.1007/s13389-012-0031-5
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1017/cbo9780511921698 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098776070
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1049/el:19991230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056788977
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1093/comjnl/bxm099 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059479898
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1109/itng.2012.61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094365024
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1109/tc.2004.100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533917
107 rdf:type schema:CreativeWork
108 https://www.grid.ac/institutes/grid.18098.38 schema:alternateName University of Haifa
109 schema:name Department of Mathematics, University of Haifa, Israel
110 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...