IEICE TRANSACTIONS on Fundamentals
Practical Application of Lattice Basis Reduction Algorithm to Side-Channel Analysis on (EC)DSA
Summary :
In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1],[2],[5],[34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EC)DSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w=4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1255-1262
- Publication Date
- 2006/05/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.5.1255
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Katsuyuki TAKASHIMA, "Practical Application of Lattice Basis Reduction Algorithm to Side-Channel Analysis on (EC)DSA" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 5, pp. 1255-1262, May 2006, doi: 10.1093/ietfec/e89-a.5.1255.
Abstract: In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1],[2],[5],[34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EC)DSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w=4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1255/_p
Copy
@ARTICLE{e89-a_5_1255,
author={Katsuyuki TAKASHIMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Practical Application of Lattice Basis Reduction Algorithm to Side-Channel Analysis on (EC)DSA},
year={2006},
volume={E89-A},
number={5},
pages={1255-1262},
abstract={In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1],[2],[5],[34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EC)DSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w=4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1255},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Practical Application of Lattice Basis Reduction Algorithm to Side-Channel Analysis on (EC)DSA
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1255
EP - 1262
AU - Katsuyuki TAKASHIMA
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1255
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1],[2],[5],[34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EC)DSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w=4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.
ER -
English
