ATmega128L上でのペアリング暗号の高速実装

IR IPSJ HANDLE

Bibliographic Information

Other Title
  • Efficient Implementation of the Pairing on ATmega128L
  • セキュリティ基盤技術

Search this article

Abstract

近年，ユビキタス社会の発達にともない，無線センサネットワーク（WSN）が実用化され始めており，鍵共有問題やプライバシの保守などのセキュリティ問題が議論されている．一方，従来の公開鍵暗号では構築が困難であった新たな暗号アプリケーションを実現できる次世代の公開鍵暗号方式として，ペアリング暗号が注目されている．センサノードとして広く研究されているMICAzは，CPUがATmega128Lであり，ワード長が8ビット，クロック周波数は7.37MHzである．Oliveiraらによって実装された，512ビットの有限体を用いたTateペアリングは，MICAz上で約30 secの時間が必要である．本稿ではMICAz上でTinyOSを用いて97次の標数3の体上でのTateペアリングの実装評価を行った．高速化にあたりATmega128Lに特化した有限体の乗算や既約多項式の選択，有限体の演算回数の削減を行った．新たな高速化手法として，事前計算による並べ替えテーブルを用いた有限体の3乗算の高速化，最小の加算回数を有する既約3項式による乗算および3乗算のリダクションの高速化を提案した．その結果，Tateペアリングの計算時間が約5.8 secに改善された．また，拡大次数m = 167，193，239においても実装を行い速度を評価した．

The technology of wireless sensor network (WSN) has been implemented in practical applications of ubiquitous society. However, the problems of security in WSN have also been discussed, for instances, key establishment, trust setup, privacy issue and so on. One of the methods for solving them is to use a public key cryptosystem. Especially, pairing based cryptosystems can achieve novel cryptographic applications such as efficient broadcast encryption. A platform fluently used for the research of sensor network is MICAz which equips an 8-bit CPU ATmega128L at 7.37MHz. Oliveira, et al. implemented the Tate pairing of a supersingular elliptic curve over a finite field of 512-bit on ATmega128L, whose timing is about 30 seconds. In this paper, we evaluated an efficient implementation of Tate pairing over a finite field of characteristic 3 of degree 97 on ATmega128L. In order to achieve a more efficient implementation we deploy an 8-bit Comb method, an efficient reduction trinomials (ROTs), and an improved multiplication on an extension field of the field. Indeed we proposed a faster cubing with a pre-computed table with ROTs optimized for ATmega128L. Then our implementation achieved about 5.8 seconds for computing Tate pairing over the finite field. We also presented and evaluated the pairing with extension degrees 167, 193, and 239.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top