An efficient CRT-RSA algorithm secure against power and fault attacks

Sung Kyoung Kim; Tae Hyun Kim; Dong Guk Han; Seokhie Hong

doi:10.1016/j.jss.2011.04.026

An efficient CRT-RSA algorithm secure against power and fault attacks

Sung Kyoung Kim, Tae Hyun Kim, Dong Guk Han, Seokhie Hong

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

Abstract

RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.

Original language	English
Pages (from-to)	1660-1669
Number of pages	10
Journal	Journal of Systems and Software
Volume	84
Issue number	10
DOIs	https://doi.org/10.1016/j.jss.2011.04.026
Publication status	Published - 2011 Oct

Bibliographical note

Funding Information:
This research was supported by the MKE (The Ministry of Knowledge Economy), Korea, under the “ITRC” support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2011-C1090-1001-0004).

Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

Keywords

Checking procedure
Chinese Remainder Theorem (CRT)
Differential power analysis
Factorization attack
Fault attack
Simple power analysis

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

Access to Document

10.1016/j.jss.2011.04.026

Cite this

@article{d8ab126d756340f78db6ab8bbdb12c6e,

title = "An efficient CRT-RSA algorithm secure against power and fault attacks",

abstract = "RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.",

keywords = "Checking procedure, Chinese Remainder Theorem (CRT), Differential power analysis, Factorization attack, Fault attack, Simple power analysis",

author = "Kim, {Sung Kyoung} and Kim, {Tae Hyun} and Han, {Dong Guk} and Seokhie Hong",

note = "Funding Information: This research was supported by the MKE (The Ministry of Knowledge Economy), Korea, under the “ITRC” support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2011-C1090-1001-0004). Copyright: Copyright 2018 Elsevier B.V., All rights reserved.",

year = "2011",

month = oct,

doi = "10.1016/j.jss.2011.04.026",

language = "English",

volume = "84",

pages = "1660--1669",

journal = "Journal of Systems and Software",

issn = "0164-1212",

publisher = "Elsevier Inc.",

number = "10",

}

TY - JOUR

T1 - An efficient CRT-RSA algorithm secure against power and fault attacks

AU - Kim, Sung Kyoung

AU - Kim, Tae Hyun

AU - Han, Dong Guk

AU - Hong, Seokhie

N1 - Funding Information: This research was supported by the MKE (The Ministry of Knowledge Economy), Korea, under the “ITRC” support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2011-C1090-1001-0004). Copyright: Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2011/10

Y1 - 2011/10

N2 - RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.

AB - RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.

KW - Checking procedure

KW - Chinese Remainder Theorem (CRT)

KW - Differential power analysis

KW - Factorization attack

KW - Fault attack

KW - Simple power analysis

UR - http://www.scopus.com/inward/record.url?scp=79960840652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960840652&partnerID=8YFLogxK

U2 - 10.1016/j.jss.2011.04.026

DO - 10.1016/j.jss.2011.04.026

M3 - Article

AN - SCOPUS:79960840652

SN - 0164-1212

VL - 84

SP - 1660

EP - 1669

JO - Journal of Systems and Software

JF - Journal of Systems and Software

IS - 10

ER -

An efficient CRT-RSA algorithm secure against power and fault attacks

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this