JaLCDOI 10.18926/14126
FullText URL Mem_Fac_Eng_OU_40_1_84.pdf
Author Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract This paper particularly deals with elliptic curves in the form of E(x, y) = y(2) − x(3) −b = 0, b ∈ F(* q) , where 3 divides q−1. In this paper, we refer to the well-known twist technique as x-twist and propose y-twist. By combining x-twist and y-twist, we can consider six elliptic curves and this paper proposes a method to obtain the orders of these six curves by counting only one order among the six curves.
Keywords elliptic curve twist third power residue/non-residue
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2006-01
Volume volume40
Issue issue1
Start Page 83
End Page 94
ISSN 0475-0071
language 英語
File Version publisher
NAID 120002308548
JaLCDOI 10.18926/14156
FullText URL Mem_Fac_Eng_39_1_71.pdf
Author Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract This paper proposes an algorithm for generating prime order elliptic curves over extension field whose extension degree is a power of 2. The proposed algorithm is based on the fact that the order of the twisted elliptic curve is able to be a prime number when the extension degree for the twist operation is a power of 2. When the definition field is F(2(40)−87)(4) , the proposed algorithm can generate a prime order elliptic curve within 5 seconds on PentiumIII (800MHz) with C language.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2005-01
Volume volume39
Issue issue1
Start Page 71
End Page 81
ISSN 0475-0071
language 英語
File Version publisher
NAID 120002308036
JaLCDOI 10.18926/14157
FullText URL Mem_Fac_Eng_39_1_82.pdf
Author Wang, Feng| Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract In this paper, we focus on developing a high-speed square root (SQRT) algorithm required for an elliptic curve cryptosystem. Examining Smart algorithm, the previously well-known SQRT algorithm, we can see that there is a lot of computation overlap in Smart algorithm and the quadratic residue (QR) test, which must be implemented prior to a SQRT computation. It makes Smart algorithm inefficient. The essence of our proposition is thus to present a new QR test and an efficient SQRT algorithm to avoid all the overlapping computations. The authors devised a SQRT algorithm for which most of the data required have been computed in the proposed QR test. Not only there is no computation overlap in the proposed algorithm and the proposed QR test, but also in the proposed algorithm over GF(p(2)) (4 | p − 1) some computations can be executed in GF(p); whereas in Smart algorithm over GF(p(2)) all the computations must be executed in GF(p(2)). These yield many reductions in the computational time and complexity. We implemented the two QR tests and the two SQRT algorithms over GF(pm) (m=1, 2) in C++ language with NTL (Number Theory Library) on Pentium4 (2.6GHz), where the size of p is around 160 bits. The computer simulations showed that the proposed QR test and the proposed algorithm over GF(p(m)) were about 2 times faster than the conventional QR test and Smart algorithm over GF(p(m)).
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2005-01
Volume volume39
Issue issue1
Start Page 82
End Page 92
ISSN 0475-0071
language 英語
File Version publisher
NAID 120002308422
JaLCDOI 10.18926/15380
FullText URL Mem_Fac_Eng_OU_35_197.pdf
Author Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract Modern communication engineerings, such as elliptic curve cryptographies, often requires algebra on finite extension field defined by modulus arithmetic with an irreducible polynomial. This paper provides a new method to detemine the minimal (irreducible) polynomial of a given proper element in finite extension field. In the conventional determination method, as we have to solve the simultaneous equations, the computation is very involved. In this paper, the well known "trace" is extended to higher degree traces. Using the new traces, we yield the coefficient formula of the desired minimal polynomial. The new method becomes very simple without solving the simultaneous equations, and about twice faster than the conventional method in computation speed.
Keywords finite field minimal polynomial irreducible polynomial higher degree trace trace cryptography
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2001-03-27
Volume volume35
Issue issue1-2
Start Page 197
End Page 205
ISSN 0475-0071
language 英語
File Version publisher
NAID 120002307992
JaLCDOI 10.18926/17849
FullText URL Mem_Fac_Eng_OU_43_99.pdf
Author Kato, Hidehiro| Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract A square root (SQRT) algorithm in extension field F(p(m))(m = r(0)r(1)・・・r(n−1)・2(d), r(i) : odd prime, d : positive integer) is proposed in this paper. First, a conventional SQRT algorithm, the Tonelli-Shanks algorithm, is modified to compute the inverse SQRT in F(p(2d)), where most of the computations are performed in the corresponding subfields F(p(2i)) for 0 ≤ i ≤ d-1. Then the Frobenius mappings with addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field F(p(m)) are also reduced to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. The Tonelli-Shanks algorithm and the proposed algorithm in F(p(6)) and F(p(10)) were implemented on a Core2 (2.66 GHz) using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerated the SQRT computation by 6 times in F(p(6)), and by 10 times in F(p(10)), compared to the Tonelli-Shanks algorithm.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2009-01
Volume volume43
Start Page 99
End Page 107
ISSN 1349-6115
language 英語
File Version publisher
NAID 120002308980
JaLCDOI 10.18926/17851
FullText URL Mem_Fac_Eng_OU_43_108.pdf
Author Nekado, Kenta| Kato, Hidehiro| Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract Recently, pairing-based cryptographies such as ID-based cryptography and group signature have been studied. For fast pairing calculation, not only pairing algorithms but also arithmetic operations in extension field must be efficiently carried out. The authors show efficient arithmetic operations of extension field for Xate pairing especially with Freeman curve.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2009-01
Volume volume43
Start Page 108
End Page 112
ISSN 1349-6115
language 英語
File Version publisher
NAID 120002308904
JaLCDOI 10.18926/17853
FullText URL Mem_Fac_Eng_OU_43_113.pdf
Author Sakemi, Yumi| Kato, hidehiro| Nogami, Yasuyuki| Morikawa, Yoshikawa|
Abstract Barreto–Naehrig (BN) curve has been introduced as an efficient pairing-friendly elliptic curve over prime field F(p) whose embedding degree is 12. The characteristic and Frobenius trace are given as polynomials of integer variable X. The authors proposed an improvement of Miller's algorithm of twisted Ate pairing with BN curve by applying X of small hamming weight in ITC–CSCC2008; however, its cost evaluation has not been explicitly shown. This paper shows the detail of the cost evaluation.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2009-01
Volume volume43
Start Page 113
End Page 116
ISSN 1349-6115
language 英語
File Version publisher
NAID 120002308945
JaLCDOI 10.18926/19960
FullText URL Mem_Fac_Eng_OU_44_60.pdf
Author Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract This paper proposes a method for generating a certain composite order ordinary pairing–friendly elliptic curve of embedding degree 3. In detail, the order has two large prime factors such as the modulus of RSA cryptography. The method is based on the property that the order of the target pairing–friendly curve is given by a polynomial as r(X) of degree 2 with respect to the integer variable X. When the bit size of the prime factors is about 500 bits, the proposed method averagely takes about 15 minutes on Core 2 Quad (2.66Hz) for generating one.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2010-01
Volume volume44
Start Page 60
End Page 68
ISSN 1349-6115
language 英語
File Version publisher
NAID 120002309063
JaLCDOI 10.18926/19961
FullText URL Mem_Fac_Eng_OU_44_69.pdf
Author Nekado, Kenta| Kato, Hidehiro| Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract Recently, pairing–based cryptographies have attracted much attention. For fast pairing calculation, not only pairing algorithms but also arithmetic operations in extension field should be efficient. Especially for final exponentiation included in pairing calculation, squaring is more important than multiplication. This paper proposes an efficient squaring algorithm in extension field for Freeman curve.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2010-01
Volume volume44
Start Page 69
End Page 72
ISSN 1349-6115
language 英語
File Version publisher
NAID 120002309070
JaLCDOI 10.18926/44499
FullText URL mfe_045_046_053.pdf
Author Nogami, Yasuyuki| Yanagi, Erika| Izuta, Tetsuya| Morikawa, Yoshitaka|
Abstract Recently, composite order pairing–based cryptographies have received much attention. The composite order needs to be as large as the RSA modulus. Thus, they require a certain pairing–friendly elliptic curve that has such a large composite order. This paper proposes an efficient algorithm for generating an ordinary pairing–friendly elliptic curve of the embedding degree 1 whose order has two large prime factors as the RSA modulus. In addition, the generated pairing–friendly curve has an efficient structure for the Gallant–Lambert–Vanstone (GLV) method.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2011-01
Volume volume45
Start Page 46
End Page 53
ISSN 1349-6115
language 英語
Copyright Holders Copyright © by the authors
File Version publisher
NAID 120002905955
JaLCDOI 10.18926/44500
FullText URL mfe_045_054_059.pdf
Author Nekado, Kenta| Takai, Yusuke| Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract Recently, pairing–based cryptographies have attracted much attention. For fast pairing calculation, not only pairing algorithms but also arithmetic operations in extension field should be efficient. Especially for final exponentiation included in pairing calculation, squaring is more important than multiplication. This paper considers squaring algorithms efficient for cubic extension field which is often used for pairing implementaions.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2011-01
Volume volume45
Start Page 54
End Page 59
ISSN 1349-6115
language 英語
Copyright Holders Copyright © by the authors
File Version publisher
NAID 80021759252
JaLCDOI 10.18926/46982
FullText URL mfe_37_2_073_087.pdf
Author Nogami, Yasuyuki| Morikawa, Yoshitaka|
Abstract Public key cryptosystem has many uses, such as to sign digitally, to realize electronic commerce. Especially, RSA public key cryptosystem has been the most widely used, but its key for ensuring sufficient security reaches about 2000 bits long. On the other hand, elliptic curve cryptosystem(ECC) has the same security level with about 7-fold smaller length key. Accordingly, ECC has been received much attention and implemented on various processors even with scarce computation resources. In this paper, we deal with an elliptic curve which is defined over extension field F(p2c) and has a prime order, where p is the characteristic and c is a non negative integer. In order to realize a fast software implementation of ECC adopting such an elliptic curve, a fast implementation method of definition field F(p2c) especially F(p8) is proposed by using a technique called successive extension. First, five fast implementation methods of base field F(p2) are introduced. In each base field implementation, calculation costs of F(p2)-arithmetic operations are evaluated by counting the numbers of F(p)-arithmetic operations. Next, a successive extension method which adopts a polynomial basis and a binomial as the modular polynomial is proposed with comparing to a conventional method. Finally, we choose two prime numbers as the characteristic, and consider several implementations for definition field F(p8) by using five base fields and two successive extension methods. Then, one of these implementations is especially selected and implemented on Toshiba 32-bit micro controller TMP94C251(20MHz) by using C language. By evaluating calculation times with comparing to previous works, we conclude that proposed method can achieve a fast implementation of ECC with a prime order.
Publication Title Memoirs of the Faculty of Engineering, Okayama University
Published Date 2003-03
Volume volume37
Issue issue2
Start Page 73
End Page 87
ISSN 0475-0071
language 英語
File Version publisher