Ontology type: schema:Chapter Open Access: True
2014
AUTHORS ABSTRACTModular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes, etc.). In this paper, we describe basic software techniques to improve the performance of Montgomery modular multiplication on 8-bit AVR-based microcontrollers. First, we present a new variant of the widely-used hybrid method for multiple-precision multiplication that is 10.6% faster than the original hybrid technique of Gura et al. Then, we discuss different hybrid Montgomery multiplication algorithms, including Hybrid Finely Integrated Product Scanning (HFIPS), and introduce a novel approach for Montgomery multiplication, which we call Hybrid Separated Product Scanning (HSPS). Finally, we show how to perform the modular subtraction of Montgomery reduction in a regular fashion without execution of conditional statements so as to counteract Simple Power Analysis (SPA) attacks. Our AVR implementation of the HFIPS and HSPS method outperforms the Montgomery multiplication of the MIRACL Crypto SDK by up to 21.58% and 14.24%, respectively, and is twice as fast as the modular multiplication of the TinyECC library. More... »
PAGES215-234
Progress in Cryptology – AFRICACRYPT 2014
ISBN
978-3-319-06733-9
978-3-319-06734-6
http://scigraph.springernature.com/pub.10.1007/978-3-319-06734-6_14
DOIhttp://dx.doi.org/10.1007/978-3-319-06734-6_14
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1038724880
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/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"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 Luxembourg",
"id": "https://www.grid.ac/institutes/grid.16008.3f",
"name": [
"Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L\u20131359, Luxembourg"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Zhe",
"id": "sg:person.013144776623.84",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013144776623.84"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Luxembourg",
"id": "https://www.grid.ac/institutes/grid.16008.3f",
"name": [
"Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L\u20131359, Luxembourg"
],
"type": "Organization"
},
"familyName": "Gro\u00dfsch\u00e4dl",
"givenName": "Johann",
"id": "sg:person.011275441722.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011275441722.34"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-45353-9_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003392034",
"https://doi.org/10.1007/3-540-45353-9_15"
],
"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": "https://doi.org/10.1145/359340.359342",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013337011"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45708-9_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022469698",
"https://doi.org/10.1007/3-540-45708-9_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45708-9_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022469698",
"https://doi.org/10.1007/3-540-45708-9_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-28632-5_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023019534",
"https://doi.org/10.1007/978-3-540-28632-5_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-28632-5_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023019534",
"https://doi.org/10.1007/978-3-540-28632-5_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-46877-3_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031645149",
"https://doi.org/10.1007/3-540-46877-3_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-46877-3_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031645149",
"https://doi.org/10.1007/3-540-46877-3_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-35416-8_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034940906",
"https://doi.org/10.1007/978-3-642-35416-8_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45203-4_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037088512",
"https://doi.org/10.1007/978-3-540-45203-4_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45203-4_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037088512",
"https://doi.org/10.1007/978-3-540-45203-4_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45203-4_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037088512",
"https://doi.org/10.1007/978-3-540-45203-4_32"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0025-5718-1985-0777282-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041482767"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-39881-3_22",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041966434",
"https://doi.org/10.1007/978-3-540-39881-3_22"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-39881-3_22",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041966434",
"https://doi.org/10.1007/978-3-540-39881-3_22"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11545262_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044926321",
"https://doi.org/10.1007/11545262_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11545262_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044926321",
"https://doi.org/10.1007/11545262_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23951-9_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047137953",
"https://doi.org/10.1007/978-3-642-23951-9_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23951-9_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047137953",
"https://doi.org/10.1007/978-3-642-23951-9_30"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/jagm.1997.0913",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047704368"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-47721-7_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052590106",
"https://doi.org/10.1007/3-540-47721-7_24"
],
"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.1049/ip-cdt:20020235",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1056845284"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/40.502403",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061168196"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tit.1976.1055638",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061647862"
],
"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.7763/ijcce.2013.v2.183",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1074030815"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/ipsn.2008.47",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093251515"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/iccsnt.2011.6181997",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094496856"
],
"type": "CreativeWork"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "Modular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes, etc.). In this paper, we describe basic software techniques to improve the performance of Montgomery modular multiplication on 8-bit AVR-based microcontrollers. First, we present a new variant of the widely-used hybrid method for multiple-precision multiplication that is 10.6% faster than the original hybrid technique of Gura et al. Then,\u00a0we discuss different hybrid Montgomery multiplication algorithms, including\u00a0Hybrid Finely Integrated Product Scanning (HFIPS), and introduce a novel approach for Montgomery multiplication, which we call Hybrid Separated Product Scanning (HSPS). Finally, we show how to perform the modular subtraction of Montgomery reduction in a regular fashion without execution of conditional statements so as to counteract Simple Power Analysis (SPA) attacks. Our AVR implementation of the HFIPS and HSPS method outperforms the Montgomery multiplication of the MIRACL Crypto SDK by up to 21.58% and 14.24%, respectively, and is twice as fast as the modular multiplication of the TinyECC library.",
"editor": [
{
"familyName": "Pointcheval",
"givenName": "David",
"type": "Person"
},
{
"familyName": "Vergnaud",
"givenName": "Damien",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-06734-6_14",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-06733-9",
"978-3-319-06734-6"
],
"name": "Progress in Cryptology \u2013 AFRICACRYPT 2014",
"type": "Book"
},
"name": "New Speed Records for Montgomery Modular Multiplication on 8-Bit AVR Microcontrollers",
"pagination": "215-234",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-06734-6_14"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"b878084a33ce8a65f45c648c0ee47fb57f43f5a7663fc7591bb5f3b5638c3082"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1038724880"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-06734-6_14",
"https://app.dimensions.ai/details/publication/pub.1038724880"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T23:53",
"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_8697_00000267.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-06734-6_14"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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-319-06734-6_14'
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-319-06734-6_14'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-06734-6_14'
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-319-06734-6_14'
This table displays all metadata directly associated to this object as RDF triples.
158 TRIPLES
23 PREDICATES
50 URIs
20 LITERALS
8 BLANK NODES