Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Michael Hutter , Erich Wenger

ABSTRACT

Multi-precision multiplication is one of the most fundamental operations on microprocessors to allow public-key cryptography such as RSA and Elliptic Curve Cryptography (ECC). In this paper, we present a novel multiplication technique that increases the performance of multiplication by sophisticated caching of operands. Our method significantly reduces the number of needed load instructions which is usually one of the most expensive operation on modern processors. We evaluate our new technique on an 8-bit ATmega128 microcontroller and compare the result with existing solutions. Our implementation needs only 2,395 clock cycles for a 160-bit multiplication which outperforms related work by a factor of 10% to 23%. The number of required load instructions is reduced from 167 (needed for the best known hybrid multiplication) to only 80. Our implementation scales very well even for larger Integer sizes (required for RSA) and limited register sets. It further fully complies to existing multiply-accumulate instructions that are integrated in most of the available processors. More... »

PAGES

459-474

References to SciGraph publications

  • 2008. NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks in WIRELESS SENSOR NETWORKS
  • 2004. Instruction Set Extensions for Fast Arithmetic in Finite Fields GF(p) and GF(2m) in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2004
  • 2001-09. Selecting Cryptographic Key Sizes in JOURNAL OF CRYPTOLOGY
  • 2009. Energy-Efficient Implementation of ECDH Key Exchange for Wireless Sensor Networks in INFORMATION SECURITY THEORY AND PRACTICE. SMART DEVICES, PERVASIVE SYSTEMS, AND UBIQUITOUS NETWORKS
  • 2006. Efficient Implementation of Public Key Cryptosystems on Mote Sensors (Short Paper) in INFORMATION AND COMMUNICATIONS SECURITY
  • 2007. Enabling Full-Size Public-Key Algorithms on 8-Bit Sensor Nodes in SECURITY AND PRIVACY IN AD-HOC AND SENSOR NETWORKS
  • 2004. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2004
  • Book

    TITLE

    Cryptographic Hardware and Embedded Systems – CHES 2011

    ISBN

    978-3-642-23950-2
    978-3-642-23951-9

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-23951-9_30

    DOI

    http://dx.doi.org/10.1007/978-3-642-23951-9_30

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "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": "Graz University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.410413.3", 
              "name": [
                "Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology, Inffeldgasse 16a, 8010, Graz, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hutter", 
            "givenName": "Michael", 
            "id": "sg:person.014316344436.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014316344436.77"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Graz University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.410413.3", 
              "name": [
                "Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology, Inffeldgasse 16a, 8010, Graz, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wenger", 
            "givenName": "Erich", 
            "id": "sg:person.014436260023.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014436260023.15"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11935308_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000175039", 
              "https://doi.org/10.1007/11935308_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11935308_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000175039", 
              "https://doi.org/10.1007/11935308_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008174972", 
              "https://doi.org/10.1007/978-3-540-28632-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008174972", 
              "https://doi.org/10.1007/978-3-540-28632-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73275-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009898538", 
              "https://doi.org/10.1007/978-3-540-73275-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73275-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009898538", 
              "https://doi.org/10.1007/978-3-540-73275-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-001-0009-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021562387", 
              "https://doi.org/10.1007/s00145-001-0009-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03944-7_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037936174", 
              "https://doi.org/10.1007/978-3-642-03944-7_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-77690-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038588160", 
              "https://doi.org/10.1007/978-3-540-77690-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-77690-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038588160", 
              "https://doi.org/10.1007/978-3-540-77690-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043836382", 
              "https://doi.org/10.1007/978-3-540-28632-5_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043836382", 
              "https://doi.org/10.1007/978-3-540-28632-5_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/sj.294.0526", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063184115"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipsn.2008.47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093251515"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011", 
        "datePublishedReg": "2011-01-01", 
        "description": "Multi-precision multiplication is one of the most fundamental operations on microprocessors to allow public-key cryptography such as RSA and Elliptic Curve Cryptography (ECC). In this paper, we present a novel multiplication technique that increases the performance of multiplication by sophisticated caching of operands. Our method significantly reduces the number of needed load instructions which is usually one of the most expensive operation on modern processors. We evaluate our new technique on an 8-bit ATmega128 microcontroller and compare the result with existing solutions. Our implementation needs only 2,395 clock cycles for a 160-bit multiplication which outperforms related work by a factor of 10% to 23%. The number of required load instructions is reduced from 167 (needed for the best known hybrid multiplication) to only 80. Our implementation scales very well even for larger Integer sizes (required for RSA) and limited register sets. It further fully complies to existing multiply-accumulate instructions that are integrated in most of the available processors.", 
        "editor": [
          {
            "familyName": "Preneel", 
            "givenName": "Bart", 
            "type": "Person"
          }, 
          {
            "familyName": "Takagi", 
            "givenName": "Tsuyoshi", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-23951-9_30", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-23950-2", 
            "978-3-642-23951-9"
          ], 
          "name": "Cryptographic Hardware and Embedded Systems \u2013 CHES 2011", 
          "type": "Book"
        }, 
        "name": "Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors", 
        "pagination": "459-474", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047137953"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-23951-9_30"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e08cd6bae927f0688b5e0f958f9085857f56e6f6865896ef121f5d9260712fe8"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-23951-9_30", 
          "https://app.dimensions.ai/details/publication/pub.1047137953"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T09:35", 
        "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/0000000373_0000000373/records_13084_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-23951-9_30"
      }
    ]
     

    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-23951-9_30'

    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-23951-9_30'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23951-9_30'

    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-23951-9_30'


     

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

    111 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-23951-9_30 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author Naa632a249a84450aa41f76f7ecf3ca76
    4 schema:citation sg:pub.10.1007/11935308_37
    5 sg:pub.10.1007/978-3-540-28632-5_10
    6 sg:pub.10.1007/978-3-540-28632-5_9
    7 sg:pub.10.1007/978-3-540-73275-4_6
    8 sg:pub.10.1007/978-3-540-77690-1_19
    9 sg:pub.10.1007/978-3-642-03944-7_9
    10 sg:pub.10.1007/s00145-001-0009-4
    11 https://doi.org/10.1109/ipsn.2008.47
    12 https://doi.org/10.1147/sj.294.0526
    13 schema:datePublished 2011
    14 schema:datePublishedReg 2011-01-01
    15 schema:description Multi-precision multiplication is one of the most fundamental operations on microprocessors to allow public-key cryptography such as RSA and Elliptic Curve Cryptography (ECC). In this paper, we present a novel multiplication technique that increases the performance of multiplication by sophisticated caching of operands. Our method significantly reduces the number of needed load instructions which is usually one of the most expensive operation on modern processors. We evaluate our new technique on an 8-bit ATmega128 microcontroller and compare the result with existing solutions. Our implementation needs only 2,395 clock cycles for a 160-bit multiplication which outperforms related work by a factor of 10% to 23%. The number of required load instructions is reduced from 167 (needed for the best known hybrid multiplication) to only 80. Our implementation scales very well even for larger Integer sizes (required for RSA) and limited register sets. It further fully complies to existing multiply-accumulate instructions that are integrated in most of the available processors.
    16 schema:editor N5a25b3f1c2324d7dad55a1754309f8bc
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N8a5431ef644244358ec3bcbe553d2532
    21 schema:name Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors
    22 schema:pagination 459-474
    23 schema:productId N6ffe9e2b87604cba8ff1d2117e379a14
    24 N8f3bde6ad49f49beaf15fc3573ca3912
    25 Ne730d96b375c4d348a93e9eb80ef346f
    26 schema:publisher Ne4deff00c8a64494b0aadb7f3636ad55
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047137953
    28 https://doi.org/10.1007/978-3-642-23951-9_30
    29 schema:sdDatePublished 2019-04-16T09:35
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N71bd9fa9e2e747a6bd39b84e1a9360f5
    32 schema:url https://link.springer.com/10.1007%2F978-3-642-23951-9_30
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N34d6cad47bf9479bb428c2cd4b6d5efb rdf:first sg:person.014436260023.15
    37 rdf:rest rdf:nil
    38 N5a25b3f1c2324d7dad55a1754309f8bc rdf:first N97896319f81845dba764a32f5a7a9ef3
    39 rdf:rest Ne31bd63898d94eb9bda49f2e9a3f3ed9
    40 N638266c545ce4e41a414a78287bb8565 schema:familyName Takagi
    41 schema:givenName Tsuyoshi
    42 rdf:type schema:Person
    43 N6ffe9e2b87604cba8ff1d2117e379a14 schema:name doi
    44 schema:value 10.1007/978-3-642-23951-9_30
    45 rdf:type schema:PropertyValue
    46 N71bd9fa9e2e747a6bd39b84e1a9360f5 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N8a5431ef644244358ec3bcbe553d2532 schema:isbn 978-3-642-23950-2
    49 978-3-642-23951-9
    50 schema:name Cryptographic Hardware and Embedded Systems – CHES 2011
    51 rdf:type schema:Book
    52 N8f3bde6ad49f49beaf15fc3573ca3912 schema:name dimensions_id
    53 schema:value pub.1047137953
    54 rdf:type schema:PropertyValue
    55 N97896319f81845dba764a32f5a7a9ef3 schema:familyName Preneel
    56 schema:givenName Bart
    57 rdf:type schema:Person
    58 Naa632a249a84450aa41f76f7ecf3ca76 rdf:first sg:person.014316344436.77
    59 rdf:rest N34d6cad47bf9479bb428c2cd4b6d5efb
    60 Ne31bd63898d94eb9bda49f2e9a3f3ed9 rdf:first N638266c545ce4e41a414a78287bb8565
    61 rdf:rest rdf:nil
    62 Ne4deff00c8a64494b0aadb7f3636ad55 schema:location Berlin, Heidelberg
    63 schema:name Springer Berlin Heidelberg
    64 rdf:type schema:Organisation
    65 Ne730d96b375c4d348a93e9eb80ef346f schema:name readcube_id
    66 schema:value e08cd6bae927f0688b5e0f958f9085857f56e6f6865896ef121f5d9260712fe8
    67 rdf:type schema:PropertyValue
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Data Format
    73 rdf:type schema:DefinedTerm
    74 sg:person.014316344436.77 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
    75 schema:familyName Hutter
    76 schema:givenName Michael
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014316344436.77
    78 rdf:type schema:Person
    79 sg:person.014436260023.15 schema:affiliation https://www.grid.ac/institutes/grid.410413.3
    80 schema:familyName Wenger
    81 schema:givenName Erich
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014436260023.15
    83 rdf:type schema:Person
    84 sg:pub.10.1007/11935308_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000175039
    85 https://doi.org/10.1007/11935308_37
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/978-3-540-28632-5_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043836382
    88 https://doi.org/10.1007/978-3-540-28632-5_10
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/978-3-540-28632-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008174972
    91 https://doi.org/10.1007/978-3-540-28632-5_9
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-3-540-73275-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009898538
    94 https://doi.org/10.1007/978-3-540-73275-4_6
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/978-3-540-77690-1_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038588160
    97 https://doi.org/10.1007/978-3-540-77690-1_19
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/978-3-642-03944-7_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037936174
    100 https://doi.org/10.1007/978-3-642-03944-7_9
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/s00145-001-0009-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021562387
    103 https://doi.org/10.1007/s00145-001-0009-4
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1109/ipsn.2008.47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093251515
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1147/sj.294.0526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063184115
    108 rdf:type schema:CreativeWork
    109 https://www.grid.ac/institutes/grid.410413.3 schema:alternateName Graz University of Technology
    110 schema:name Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology, Inffeldgasse 16a, 8010, Graz, Austria
    111 rdf:type schema:Organization
     




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


    ...