工學碩士學位論文 역수연산에서의효율적인멀티쉬프팅알고리즘 The Efficient Multi-bit Shifting Algorithm in Multiplication Inverion Problem 2005 年 8 月 仁荷大學校大學院 컴퓨터 情報工學科 蔣仁周
工學碩士學位論文 역수연산에서의효율적인멀티쉬프팅알고리즘 The Efficient Multi-bit Shifting Algorithm in Multiplication Inverion Problem 2005 年 8 月 仁荷大學校大學院 컴퓨터 情報工學科 蔣仁周
工學碩士學位論文 역수연산에서의효율적인멀티쉬프팅알고리즘 The Efficient Multi-bit Shifting Algorithm in Multiplication Inverion Problem 2005 年 8 月 指導敎授柳亨善 이論文을碩士學位論文으로提出함 仁荷大學校大學院 컴퓨터 情報工學科 蔣仁周
本論文을蔣仁周의碩士學位論文으로認定함 2005 年 8 月 主審 印 副審 印 委員 印
국문요약 본논문에서는타원곡선암호시스템의효율향상을위한한방법을제안하 고자한다. 타원곡선암호알고리즘을구성하는핵심은유한체 GF2 n 에서의연 산이다. 유한체연산은덧셈, 곱셈그리고역수연산으로이루어져있다. 그중역수연산은긴수행시간과구현의복잡함때문에유한체연산의효율향상에있어가장민감한요소이다. 따라서효율적인역수연산알고리즘의연구는중요한관심사항이다. 대표적인역수연산알고리즘에는 Fermat' theorem, 확장유클리드알고리즘 etended Euclid algorithm 과몽고메리역수연산알고리즘이있다. 암호화, 복호화과정의효율을좌우하는곱셈연산과역수연산에관한연구는다양한방면으로계속되어오고있으며, 특히 Optimal Normal bai 나 Polynomial bai를사용한연구와그기저에서의연산적알고리즘의효율성은잘알려져왔다. 본논문에서는멀티쉬프팅방법을이용한 Galoi field GF2 n 에서의역수 연산알고리즘의효과적인방법을제안하고자몽고메리알고리즘에기반을두고, 3-bit hifting 기법을수정한 continuou multi-bit hifting 알고리즘에관한효율성을비교평가하였다. 역수연산을위한기약다항식으로는 Trinomial 과 AOP 를사용하였다. 이연산결과수행시간은 ~26% 의감소를보였다. 이러한연산결과를통해 Multi-bit hifting 기법은역수연산의효율향상을위한한방법으로사용가능함을확인하였다. 이실험에서는기약다항식의종류에따른결과에큰영향을보이지않았으나아직데이터특성에따른기약다항식과연산효율에대한연구가좀더진행되어야할것으로기대된다. i
ABSTRACT Thi tudy propoe an efficient inverion algorithm for Galoi field GF2 n by uing a modified multi-bit hifting method. For the implementation uing a computer, the arithmetic in the GF2 n ha a tructural advantage. Thi tudy i alo dealing with an arithmetic in the GF2 n. An arithmetic in the GF2 n conit of addition, multiplication, and invere arithmetic. The invere arithmetic i the mot of thoe. Therefore, a tudy for the efficient invere arithmetic algorithm i important. Among the repreentative of invere algorithm, there are Fermat' Little Theorem, etended Euclidean algorithm, and Montgomery inverion algorithm. A reearch for multiplication arithmetic and invere arithmetic governing the efficiency of cryptography, ha been continued in the variou way, and epecially, a tudy uing Optimal Normal Bai or polynomial bai and the efficiency of arithmetic algorithm on the bai of thoe ha been well nown. In thi tudy, to propoe an efficient invere arithmetic algorithm in the Galoi Field GF2 n uing multi-bit hifting algorithm, a continuou multi-bit hifting algorithm, which i modified from 3-bit hifting, wa evaluated and computed with Montgomery algorithm. Trinomial and AOP wa ued for an invere arithmetic a an irreducible polynomial. A a reult of tet, it i found that the computation time wa reduced to 26% in the maimum. Therefore, it i hown that multi-bit hifting algorithm can be ued a an algorithm to increae the efficiency of a invere arithmetic. Following thi tudy, the tudie for the irreducible polynomial with the characteritic of data and the efficiency of arithmetic are epected to be continued. ii
차례 국문요약 i ABSTRACT ii 차례 iii 그림차례 v 표차례 v 제 장서론 제 2 장유한체 3 2. 유한체 5 2.2 유한체연산 3 제 3 장역수연산 7 3. Fermat' Little Theorem 7 3.2 확장유클리드알고리즘 9 3.3 몽고메리알고리즘 제 4 장 Multi-bit hifting 5 4. Multi-bit hifting 5 4.2 cz-bit hifting 7 제 5 장구현 20 iii
제 6 장실험결과 22 6. 3 non-zero term의역수연산 24 6.2 5 non-zero term의역수연산 26 6.3 9 non-zero term의역수연산 28 6.4 3 non-zero term의역수연산 30 6.5 Trinomial 에서의역수연산 32 6.6 AOP 에서의역수연산 33 제 7 장결론 34 참고문헌 35 iv
그림차례 그림. 3non-zero term에서의역수연산에대한효율성비교 25 그림 2. 5non-zero term에서의역수연산에대한효율성비교 27 그림 3. 9non-zero term에서의역수연산에대한효율성비교 29 그림 4. 3non-zero term에서의역수연산에대한효율성비교 3 그림 5. Trinomial을이용한역수연산의효율성비교 33 그림 6. AOP를이용한역수연산의효율성비교 35 표차례 표. 허용비트에따른사용 Trinomial 22 표 2. 3non-zero term에서의역수연산시간 24 표 3. 5non-zero term에서의역수연산시간 26 표 4. 9non-zero term에서의역수연산시간 28 표 5. 3non-zero term에서의역수연산시간 30 표 6. Trinomial을이용한역수연산시간 32 표 7. AOP를이용한역수연산시간 34 v
제 장서론 암호학의응용분야에서주로사용되는연산은덧셈, 뺄셈, 곱셈과역수의모듈러연산으로구성되어있다. 이중에서도모듈러역수연산은 Diffe-Hellman 키교환알고리즘이나 RSA알고리즘의복호화과정, 타원곡선암호법그리고전자서명에이르기까지암호학의많은응용분야에있어서근간이되는연산이다. 역수연산과정이모든분야에서중요함에도불구하고연산과정에소요되는구현시간이길고, 구현과정이복잡하여이를이용하는암 복호화과정에큰장애가되어왔다., 따라서암 복호화과정의수행효율을높이기위하여역수연산에대한많은연구가진행되어오고있다 [,2,3,8,9]. 암호학에있어서의역수연산은일반적으로유한체 Galoi Field 인 GFp 또는 GF2 n 상에서정의된다. 특히 985년 Miller와 Kobliz에의하여타원곡선 암호법이제안된이후, 유한체 Galoi Field 가타원곡선암호화, coding 이론및여러산업분야에응용되었고, 이는타원곡선암호화연산의바탕이되는유한체연산에대한관심을증대시켜많은관련연구가이루어지고있다 [,2,3,4,5,6]. 유한체의연산은유한체의표현방법, 즉유한체표현의기저가무엇인지그리고유한체를구성하는기약다항식이무엇인지에의하여효율에영향을끼친다. 지금까지의유한체역수연산에관한많은연구는효율적인알고리즘과성능향상을위한방법들을제시하여왔다. 그중 Fermat little theorem 이나확장유클리드알고리즘을응용한역수연산알고리즘이효율적인알고리즘으로입증되어왔으며, 이를응용한알고리즘의개선을통한성능향상노력이계속되고있다. [,2,3,4,5,6] Itoh 와 Tujii는확장된갈로아필드 GF q m 에서의역수연산알고리즘을발전시키고, 구체화시켰으며 [2,3], 확장유클리드알고리즘에서유도된몽고메리 - -
기법이 Kalii 등에의하여 GF 2 m 에서의역수연산구현을위해응용되었고, 이를분석함으로좀더효율적인연산기법임이보여졌다 [5,6]. Koc 등의연구진은 Kalii의방법에 multi-bit hifting 기법을적용하고, 이를하드웨어로구현하는연구를진행함으로모듈러역수연산의효율성을증가시켰다. 이들의연구에서는하드웨어구현으로발생하는제약을고려하였다. 이로써쉬프팅기법에이용되는최대적용비트수는 3-bit 라고제시하였으며, 그효율성을실험을통해밝혔다 [5, 6, 8, 9]. 본연구에서는 Koc 등의 multi-bit hifting 알고리즘을응용, 수정한 cz continuou Zero-bit hifting 알고리즘을제안하고, 그에대한실험을수행하여기존의 multi-bit hifting 알고리즘과비교검토하고자한다. 실험은하드웨어구현을배제한프로그램으로만구현하였으며, 50 ~ 250 비트를데이터허용범위로하여역수연산을수행하였다. 실험결과본연구에서제안된 cz-bit hifting 알고리즘이비교대상인기존의 multi-bit hifting 알고리즘에비하여효율적인역수연산방법임을알수있었다. - 2 -
제 2 장 유한체 2. 유한체 차수가 n 인다항식 f 가 GF2 에서기약일때, 유한체는 2 n 개의원소를 갖게되며, 이때의유한체는식 2. 과같이표현할수있으며, GF 2 n GF2[ ]/ f 2. 이를다항식기저에서표현하면식 2.2 와같이나타낼수있다 [,3,,2]. 즉 f α 0 이면, n 2 n GF2 { a0 + aα + a2α + L + an α ai GF2} 2.2 이러한다항식기저의유한체에관하여는아래와같은정의가있다. 정의 2. 식 2.3 과같이표현되는다항식기저의유한체를차수가 n인 All One PolynomialAOP 이라한다. f + 2 3 n + + + + L 2.3-3 -
정리 2. 식 2.3 과같이표현되는 AOP 가 GF2 위에서기약이기위한 필요충분조건을만족하기위하여 n + 이소수이고 2가유한체 Z n+ 원시원소 primitive element 이어야한다. 식 2.3 이 GF2 위에서기약다항식이면이때 n은짝수이고이것을 의 만족하는 n 의값으로는 L 62, 72, 78, 80, 96, L등이있다 []. 정의 2.2 2 3 { α, α, α, L, α n } B 2.4 식 2.4 가 GF2 위에서 GF 2 n 의기저일때, B 를변형된다항식기저라 한다. 최적정규기저를사용하는유한체의연산은하드웨어구현에매우효율적이고 [2], AOP 다항식은타입 I 의최적정규기저를형성한다 []. - 4 -
2.2 유한체연산 유한체 GF 2 n 는 GF2 상에서 n 차원의벡터영역으로확장한형태로표현 된다. 여기서 GF2 는 0 과 의두원소로구성되고, GF 2 n 의각각의원소 는독립적으로다음과같은형식으로표현된다 [,3,4,,2]. α a 0 α 0 + a α + + a n - α n -, 2.5 여기서 a i {0,} { α 0,α,, α n - } 는 GF2 상에서 GF 2 n 의 bai 이다. 이러한기 저가주어지면유한체원소는 a 0 a a n - 의비트열로표현된다. 유한체연산은유한체덧셈, 곱셈, 그리고역수의계산이필요하다. 유한체원소의덧셈은 bitwie XOR연산에계산되어지고, 유한체곱셈은선택한기저에의해서결정되어진다. ANSI X9.62에서는다항식기저와정규기저를인정하고있다. 본논문에서는다항식기저를사용하고있으며유한체곱셈은다음과같이계산된다. C A B modp a n - a a 0 b n - b b 0 c n - c c 0 2.6-5 -
이때 A,B,C GF 2 n 이고, P{ p n p n - p p 0, p n, p i GF2} 는기약다항식으로서 GF 2 n 의모든원소는 P 에의해서표현된다. 유한체의역수연산은 Fermat' Little Theorem 과확장유클리드알고리즘을응용한방법으로계산할수있다. 각각의역수연산알고리즘에관하여는다음장에서자세히설명한다. - 6 -
제 3 장 역수연산 유한체의역수연산은 Diffe-Hellman 키교환알고리즘이나 RSA 알고리즘의복호화과정, 그리고타원곡선암호법과전자서명에이르기까지대부분의암호학응용분야에있어서기본과정을이루는연산이다. 그러나역수연산과정의구현함은복잡할뿐만아니라, 처리시간도길다. 따라서단순화및처리시간단축이 실용화구현에매우중요한요소이며, 이러한효율적인역수연산알고리즘은 암 복호화과정의효율향상에있어핵심적인요소가된다 [3,4,5]. 이에많은연구가진행되었고, 그중효율적인유한체역수연산기법으로인정받는대표적인알고리즘으로는페르마정리를응용한알고리즘, 확장유클리드알고리즘과그응용인몽고메리알고리즘이다. 각알고리즘의자세한내용은다음과같다. 3.. Fermat' Little Theorem 큰 유한체역수를구하기위해많이사용하는방법중의하나가 Fermat' Little Theorem 이다. 이것을유한체 GF2 n 의역수연산에이용하면식 3. 과 같이나타낼수있으며 [0], 이때식 3. 은 A 가 GF2 n 의원소이고, P 가기약다항식인조건일때만족한다 [2,3,4,7]. A GF 2 n 인경우, A - A 2 n -2 modp 3. - 7 -
식 3. 과같이 Fermat' Little Theorem 을이용한역수연산은반복적인곱 셈연산으로계산할수있으며, 사용되는연산과정으로는 n 회의자승연산과정 과 n 회의곱셈연산과정이필요하다 [7]. - 8 -
- 9-3.2 확장유클리드알고리즘유한체의역수연산을위한방법연구에확장유클리드알고리즘이많이응용된다. 주어진다항식 S 와기약다항식 P 를가지고 S 의역수 T 를유클리드알고리즘을이용하여구하는식은식 3.2 와같다 [7,]. mod P T S 3.2 확장유클리드알고리즘은다음변수들을초기화하면서시작된다. 2 2 2,,,,, q q t t 변수들의초기값은식 3.3 와같다. 0, 0,, 2 2 2 q q t t S P 3.3 0 을만족할때까지식 3.4 의계산을반복수행한다. 2 2 2 / mod + t t q t q 3.4 모듈러연산을사용하므로나눗셈의나머지값만을가지고쉽게연산과정을수행할수있다. 이연산과정중나머지가 0 이외의값을가지는경우는변수의
- 0 - 값이식 3.5 의과정을거처변경된다. p q q q t t t t 2 2 2,,, 3.5 식 3.5 의수행으로모든변수는갱신되며식 3.4 의연산과정을다시반복수행하며, 의값이 0 을만족할때까지계속된다. 유한체에서의역수연산구현은식 3.2 에서보이는바와같이기약다항식 P 의형태에따라효율에큰영향을받는다.
3.2 몽고메리알고리즘 유한체연산에있어서확장유클리디안알고리즘을응용한몽고메리알고리즘은하드웨어적인표현이간단하며, 그처리시간또한타알고리즘보다단축된다는이점때문에많은연구가이루어지고있다 [8.9]. 몽고메리알고리즘은식 3.6 과같이정의된다 [4,5,6,8]. n b a 2 mod p, p > a > 0 3.6 여기서 p 는소수이며, n log2 p 이다. 몽고메리역수알고리즘은두개의단계로이루어진다. 첫단계에서는 a의 almot Montgomery inverion 인정수 r을식 3.7 과같이구한다. r a 2 mod p, n 2n 3.7 r, : AlmMonInv a a 2 mod p 3.8 두번째단계는 correction 단계라고할수있다. 첫단계에서구해진몽고메리 역수의유사값을이용하여정확한역수값을식 3.9 과같이구한다. n n b MonInv a2 a 2 mod p 3.9 몽고메리알고리즘에는다음과같이중요한두개의정리가있으며, 구현은다 음의 Algorithm MonInv 와같다 [4,6]. - -
정리 3. p > 2 인소수 p 와 a > p > 인정수 a 에대하여 AlmMonInv 에 사용된변수 r,, u 는항상조건 r,, u [0, 2p ] 을만족한다. 정리 3.2 p > 2 인소수p 와 a > p > 인정수a 에대하여 AlmMonInv 에서 나타나는색인변수 는다음의조건을만족한다. [n, m + n ] 3. 이때값변수의값은조건 n log 2 p, m w, w < n w을만족한다. Algorithm MonInv Phae I Input : a [, ] Output : r [, ] p and p p and, where r a 2 mod p and n 2n : u : p, v : a, r : 0, and _ : 2: : 0 3: while v > 0 4: if u i even then u : u / 2, : 2 5: ele if v i even then v : v / 2, r : 2r 6: ele if u > v then u : u v / 2, r : r +, : 2-2 -
7: ele if v u then u : v u / 2, : + r, r : 2r 8: : + 9: if r p then r : r p 0: return r : p r and Phae II Input : r [, ] Output : [, ] p and p, and from PhaeI p, where n a 2 mod p : for i to n do 2: if r i even then r : r / 2 3: ele then r : r + p / 2 3: return : r 몽고메리알고리즘을이진확장체 GF2 n 의표현식으로나타내면식 3.2 과 같다. 이때 p 는 GF2 의기약다항식을나타내게되며, a 원소로식 3.3 과같은의미를지닌다. 는 GF2 n 의 2n b a mod p 3.2 p a a n n + p n n + a n n2 + p n2 n2 n2 + L+ p + p + L+ a + a 0, i 0 a {0,} 3.3 이표현식을이용하여 Algorithm A 이하 Alg.A 라표기한다 와같이구현할 수있다. - 3 -
- 4 - Algorithm A Phae I :, / : 0 5 : :, / : 0 4 : 0 3: 0 : 2 : : 0, :, :, : : deg,deg mod, : deg deg, : 0 0 r r v v then v ele if u u then u if u while and r a v p u p p a where and Output p a where p and a Input < < and return p then if p then if r r r u v v ele r r v u u then v u ele if n n : : 0 : : 9 : : 8 : :, :, / : 7 : :, :, / : deg deg 6 : + + + + + + + + Phae II : 4 : : 3: 2 2 : mod : : 2 b return p do n to i for p a b where b Output I Phae from and Input n n +
제 4 장 Multi-bit hifting 4. Multi-bit hifting 알고리즘 확장유클리드알고리즘에바탕을둔몽고메리알고리즘은데이터최하위비트의값에따라 add and hift의작업을반복한다. 이러한반복작업의양을줄여효율을높이고자. 반복되는작업의일괄처리를통한수행횟수감소의노력이계속되고있다. 이에 E. Sava 와 C. K. Koc등은기존의몽고메리알고리즘을수정하여효율적인 multi-bit hifting기법을 Algorithm A- 이하 Alg.A-이라표기한다 과같이제안하였다 [8,9]. Algorithm A- 4 : 4.: 4.: 5 : 4.: 4.: if if if if if if u u u 2 2 2 2 2 2 u u u u u u v v v 0 v v v 0 0 0 v v v 0 0 000 then { u ShiftR u,3; hiftl,3; + 2} 00 then { u ShiftR u,2; hiftl,2; + } X0 then { u ShiftR u,; hiftl,} 000 then { v ShiftR v,3; r hiftl r,3; + 2} 00 then { v ShiftR v,2; r hiftl r,2; + } X0 then { v ShiftR v,; r hiftl r,} Algorithm A-에서는최하위세비트를일괄처리를위한변수값으로받아들인다. 이최하위의세비트값에따라일괄처리의과정을설정하고, 이과정을통하여몽고메리알고리즘의역수연산과정중에발생하는연산의수행횟수를줄이고자하였다. 이알고리즘에서는하드웨어적인구현을일차적인연구대상으로삼은까닭에 - 5 -
세비트를일괄처리의최적입력값으로제안하였다. 한비트를추가로일괄처리대상으로삼기위하여구성해야하는하드웨어적인추가소자로인한발생비용과일괄처리로일어나는효율값간의관계로세비트가최적의일괄처리비트수로설명되었다. - 6 -
4.2 cz-bit hifting 알고리즘 cz continuou Zero-bit hiftinf 알고리즘은몽고메리알고리즘의다음과같은특성을이용하여고안되었다. 몽고메리알고리즘은최하위비트값이 0 또는 인가에따라 Algorithm MonInv의구현에서보는바와같이 4, 5, 6, 7번의작업과정을반복적으로수행하는알고리즘이다. 이때최하위비트가 인경우는다음의 Algorithm MonInv의 6, 7번의작업과정을반복한다. Algorithm MonInv 6: ele if u > v then u : u v / 2, r : r +, : 2 7: ele if v u then u : v u / 2, : + r, r : 2r 이수행과정은반복되는매회수마다, 수행결과얻어지는결과값들이각각 의변수값으로갱신된다. 이때갱신되는변수의값은실제의수행과정을통해 서만얻을수있을뿐, 예측이불가능하다. 즉, 매회반복되는과정임에도반복 되는작업을묶어일괄처리로수행할수없다. 한편, 최하위비트가 0 인경우는다음과같이 Algorithm MonInv 의 4, 5 번의 작업과정이반복된다. Algorithm MonInv 4: if u i even then u : u / 2, : 2 5: ele if v i even then v : v / 2, r : 2r - 7 -
4, 5번의수행과정에서는단순한 hift 연산만이좌, 우방향으로일어남을알수있다. 즉, 변수의최하위비트로부터 0 값이연속될경우, 수행되는작업은단순한 hift 연산만이며, 이결과갱신되는변수값은최하위비트로부터연속적으로존재하는 zero비트의수에의하여예측할수있다. 즉, 반복수행되는작업을연속된 zero비트수에의하여일괄처리한뒤에얻어지는결과값과동일함을알수있다. 하드웨어적인구현을고려할경우는일괄처리할 hifting의수가증가할수록구현에필요한소자가증가하여구현에필요한비용증가를가져오며, 구성의복잡도를높인다. 이는얻어지는효율성향상에비해큰부담을준다. 그러나하드웨어구현을배제할경우가져올효율성에관한연구결과는정리되어있지않다. 따라서본연구에서는최하위비트값이 zero인경우반복수행하게되는스텝 4, 5번을다음의 Algorithm B 이하 Alg.B 라표기한다 와같이수정하여구현함으로연속되는최하위의 zero 비트수만큼의일괄처리를구현하였다. Algorithm B 4 : 4. : 4.2 if u 0 0; then while u u : u / i 0; cz ; update cz ; 5 : 5. : 5.2 : eleif : v 0 cz 0; then while ; v v : v / i 0; cz ; update cz ; r : cz r ; - 8 -
위의알고리즘B 에서는최하위의비트값에연속적으로 0 값이존재할경우연속되는 zero값의비트수를세어나간다. 값이나타나연속성이깨어질때, 최종적인비트수를변수 czcontinuou Zero bit 값으로갱신한다. 이갱신된 cz 값으로반복수행될 hift연산을일괄처리한다. 이와같이변수 cz의추가저장장소를이용하여, 작업의일괄처리를얻어수행시간을단축하게된다. 이때일괄처리할 zero비트의최대수는구현하는시스템이나프로그램에서설정한한워드의크기가된다. - 9 -
제 5 장구현 수행후의효율성향상을비교평가하기위하여, 기존의몽고메리역수연산알고리즘을 Alg.A로, 최하위 3-bit 의값에따라일괄처리가수행되는 multi-bit hifting은 Alg.A-으로구현하여실험하였다. 본논문에서제안된수정 multi-bit hifting알고리즘은 Alg.B로구현하였다. Alg.B에서는연속적으로존재하는최하위의 zero비트수를찾아일괄처리할크기를정하고, 4장에서제시한 Algorithm B의스텝 4, 5번의작업을수행하여그결과를비교평가함으로효율성을보였다. 이후 Alg.B에의하여수행되는작업을 cz-bit hifting이라한다. 구현환경및프로그램구성은다음과같다. 환경 : Pentium IV 2.0 GHz Memory 52 MB Compiler Viual C++ 프로그램구성입력값 : 허용비트에따른 trinomial타입과 AOP 타입의기약다항식 [7] 과임의의 non-zero term. 역수연산 : 각데이터마다 Alg.A, Alg.A-, Alg.B을수행한다. 출력부분 : 연산결과얻어지는역수와수행시간을출력한다. - 20 -
실험을위하여구현한프로그램의구조는아래의그림 5 와같다. from Field 2 n Input Data p & a p ; prime polynomial a ;3,5,9,3 non zero data ptrinomial or AOP? typeof prime polynomial a3,5,9,or 3? 2 type of non zeroterm Algorithm type Alg.A Alg.A- Alg.B Original Montgomery Inverion eecution time & inverion value value of 3-bit 3-bit hifting chec the continuou zero-bit cz Multi-bit hifting 그림 5. 구현프로그램의구조 - 2 -
제 6 장실험결과 타원암호알고리즘의응용분야에서이용되는범용적인데이터의사용범위 는 50 에서 250 비트이다. 이에본연구에서도이적용범위내의데이터들을사 용하여실험하였다. 50~250 비트범위의데이터들중 trinomial 과 AOP 모두 고려될수있는실험환경을위해설정할허용비트로다음의수 { 48, 56, 62, 78, 80, 96, 20, 228, 250 } 를선택하였다 [,7]. 각비트별로사용한 trinomial 은표 과같다. 표. 허용비트에따른사용 Trinomial[7] 최대허용비트 역수연산에사용된 Trinomial, P 48 48 + 27 + 0 56 56 + 9 + 0 62 62 + 27 + 0 78 78 + 3 + 0 80 80 + 3 + 0 96 96 + 3 + 0 20 20 + 7 + 0 228 228 + 3 + 0 250 250 + 03 + 0-22 -
데이터값으로는 3, 5, 9, 3 non-zero term을지니는값을선택하여실험하였으며, non-zero term의위치가편중되는것을막기위하여 non-zero bit를최대허용비트의전범위에걸쳐넓게분포시켰다. 그러나임의의데이터로서의가치를지니기위해등간격을피하여 non-zero term을분포시켰다. 실험을위한프로그램은 Roing 등이 제시한프로그램방법 [7] 을수용하고 이를수정하여 C++ 로구현하였으며, 각실행알고리즘별로동일데이터에의 한역수연산수행시간을얻었다. 수행시간은각작업을공히 0,000 번반복시 켜얻었다. - 23 -
6. 3 non-zero term 의역수연산 표2는각각의최대허용비트 { 48, 56, 62, 78, 80, 96, 20, 228, 250 } 에따라임의로선택된 3 non-zero term 데이터에대하여각각의알고리즘 Alg.A, Alg.A-, 그리고 Alg.B를적용하여역수연산을수행한결과얻어진수행시간이다. 다항식 Trinomial 과 AOP 를에대하여각데이터의역수연산을모두수행을하였으며, 얻어진결과는 m ec 단위로표2와같다. 표 2. 3non-zero term 에서의역수연산시간 종류 Trinomial AOP m ec 범위 Alg.A Alg.A Alg.B Alg.A Alg.A Alg.B 48 3.64 3.3 2.98 3.97 3.84 3.83 56 3.55 2.97 2.84 3.9 3.6 3.44 62 4.7 3.56 3.4 4.42 4.6 4.4 78 3.9 3.30 3.3 4.78 4.69 4.70 80 4.06 3.67 3.55 4.8 4.80 4.77 96 4.34 3.95 3.86 5.77 5.00 4.69 20 4.64 4.23 4.4 6.9 5.4 5.08 228 4.28 3.39 3.4 6.05 5.22 4.83 250 5.95 5.45 5.3 6.02 5.27 4.9-24 -
그림. 3 non-zero term 의역수연산수행시간감소율 3 non-zero term 에대한역수연산결과는그림에서보는바와같이전체허용범위에대하여본논문이제안하는 Alg.B의적용결과성능향상을보였다. 특히 96비트범위이상에서는기약다항식 AOP에대한역수연산에서그효율향상이두드러지게나타났다. 그림에나타난것처럼허용범위 96비트이상에서는허용범위가증가하여도같은양의수행시간의감소율을보였다. 이는허용비트가큰 특히 96비트이상 경우 AOP에서의 Alg.B를적용한역수연산이유리함을보여준다. - 25 -
6.2 5 non-zero term 의역수연산 표 3 은각각의최대허용비트에따라임의로선택된 5 non-zero term 데이터 에대하여각각의알고리즘 Alg.A, Alg.A-, 그리고 Alg.B 를적용하여역수연산 을수행한결과얻어진수행시간이다. 다항식 Trinomial 과 AOP 를에대하여 각데이터의역수연산을모두수행을하였으며, 그결과는 m ec 단위로표 3 과 같이나타났다. 표 3. 5 non-zero term 에서의역수연산시간 종류 Trinomial AOP m ec 범위 Alg.A Alg.A Alg.B Alg.A Alg.A Alg.B 48 4.00 3.66 3.58 3.8 3.48 3.45 56 3.9 3.45 3.42 3.98 3.77 3.78 62 4.08 3.44 3.36 4.5 3.73 3.69 78 4.45 3.80 3.67 4.55 4.44 4.44 80 5.02 4.58 4.53 4.88 4.83 4.83 96 5. 4.69 4.63 4.95 4.66 4.63 20 5.6 5.09 5.00 5.3 4.83 4.80 228 5.55 4.94 4.84 5.75 5.55 5.52 250 5.88 4.47 4.25 6.83 6.33 6.25-26 -
그림 2 5 non-zero term 의역수연산수행시간감소율 5 non-zero term 에대한역수연산결과는그림2에서보는바와같이전체허용범위에대하여본논문이제안하는 Alg.B의적용결과성능향상을보였다. 특히 62비트범위이상에서는기약다항식 AOP에대한역수연산에서그효율향상이두드러지게나타났다. 그림2에나타난것처럼허용범위 6비트이상의경우 AOP에서의 Alg.B를적용한역수연산이유리함을보여준다. - 27 -
6.3 9 non-zero term 의역수연산 표 4 는각각의최대허용비트에따라임의로선택된 9 non-zero term 데이터에 대하여각각의알고리즘 Alg.A, Alg.A-, 그리고 Alg.B 를적용하여역수연산을 수행한결과얻어진수행시간이다. 다항식 Trinomial 과 AOP 를에대하여각 데이터의역수연산을모두수행을하였으며, 그결과는 m ec 단위로표 4 와같 이나타났다. 표 4. 9non-zero term에서의역수연산시간 m ec 종류 Trinomial AOP 범위 Alg.A Alg.A Alg.B Alg.A Alg.A Alg.B 48 3.94 3.66 3.63 3.88 3.64 3.67 56 3.98 3.6 3.59 4.23 4. 4.06 62 4.45 4.08 4.02 4.47 4.36 4.36 78 4.38 4.00 4.00 4.83 4.66 4.69 80 4.73 4.39 4.39 4.94 4.60 4.59 96 4.98 4.5 4.42 5.3 4.70 4.70 20 5.50 5.09 5.09 5.66 5.3 5.34 228 5.72 5.22 5.7 6.3 5.75 5.75 250 6.53 5.83 5.8 6.69 6.9 6.7-28 -
그림 3 9 non-zero term 의역수연산수행시간감소율 9 non-zero term 에대한역수연산결과는그림3에서보는바와같이전체허용범위에대하여본논문이제안하는 Alg.B의적용결과성능향상을보였다. 5 non-zero term에대한실험결과에서와같이 62비트범위이상에서는기약다항식 AOP에대한역수연산에서그효율향상이두드러지게나타났다. 그림3에나타난것처럼허용범위 6비트이상의경우 AOP에서의 Alg.B를적용한역수연산이유리함을보여준다. 그러나 228 비트부터의결과곡선변화는향후 250비트이상의허용범위에대한연구의필요성을보여준다. - 29 -
6.4 3 non-zero term 의역수연산 표 5 는각각의최대허용비트에따라임의로선택된 3 non-zero term 데이터에 대하여각각의알고리즘 Alg.A, Alg.A-, 그리고 Alg.B 를적용하여역수연산을 수행한결과얻어진수행시간이다. 다항식 Trinomial 과 AOP 를에대하여각 데이터의역수연산을모두수행을하였으며, 그결과는 m ec 단위로표 5 과같 이나타났다. 표 5. 3non-zero term 에서의역수연산시간 종류 Trinomial AOP m ec 범위 Alg.A Alg.A Alg.B Alg.A Alg.A Alg.B 48 3.94 3.6 3.6 3.77 3.53 3.53 56 3.88 3.52 3.48 4.4 3.86 3.86 62 4.36 4.02 3.98 4.34 4.02 4.02 78 4.36 3.98 3.95 4.73 4.53 4.52 80 4.86 4.47 4.48 4.97 4.66 4.58 96 5.02 4.58 4.58 5.33 4.89 4.90 20 5.52 4.9 4.86 5.67 5.3 5.32 228 5.53 4.94 4.86 5.75 5.7 5. 250 6.58 5.97 5.89 6.8 6.23 6.22-30 -
6.5 Trinomial 에서의역수연산 그림 4. 3 non-zero term 의역수연산수행시간감소율 3 non-zero term 에대한역수연산결과에서도그림4에서보는바와같이전체허용범위에대하여본논문이제안하는 Alg.B의적용결과기존의알고리즘인 Alg.A-의경우보다성능향상을보였다. 특히기약다항식 Trinomial을적용한경우의효율향상이더좋은결과가나타났다. - 3 -
6.5 Trinomial 에서의역수연산 30.00 % 25.00 Trinomial 3non_zero Trinomial 5non_zero Trinomial 9non_zero Trinomial 3non_zero 20.00 5.00 0.00 5.00 0.00 48 56 62 78 80 96 20 228 256 bit 그림 5 Trinomial 을이용한역수연산의효율성비교 그림 5 는 Trinomial 에 Alg.B 를적용한역수연산결과얻어진수행시간의감소 율을각데이터별로정리한것이다. 실험결과 3 non-zero term 와 5 non-zero term 의경우는 0% 이상의감소율을보였다 - 32 -
25.00 % 20.00 AOP 3non_zero AOP 5non_zero AOP 9non_zero AOP 3non_zero 5.00 0.00 5.00 0.00 bit 48 56 62 78 80 96 20 228 256 그림 6 AOP 를이용한역수연산의효율성비교 그림6은 AOP 에 Alg.B를적용한역수연산결과얻어진수행시간의감소율을각데이터별로정리한것이다. 실험결과 3 non-zero term의경우 96비트이상에서 5% 이상의좋은결과가나타났다. 그외의경우는실험데이터의 non-zero term에대하여큰영향을받지않음을알수있다. - 33 -
제 7 장결론 현실적으로정보보호및암 복호화의문제는해결해야하는사회필수적인요소가되었다. 이에많은관련연구가있었고, 그중타원곡선암호기법이적은키로도안전성을높일수있는암호기법임이입증되었다. 본논문에서는타원곡선암호기법구현에있어서근간이되는유한체연산중가장수행시간이길고구현에복잡한역수연산의효율향상을위한기법을제시하고실험결과를통하여입증하였다. 이논문에서는제안된 cz-bit hifting 알고리즘 Alg.B 이몽고메리역수연산에대하여기존의몽고메리알고리즘 Alg.A 이나, 3-bit로제안된 multi-bit hifting 알고리즘 Alg.A- 보다효율적인연산기법임을보였다. 실험결과를분석해볼때 Alg.B로수행된몽고메리역수연산은 Trinomial 타입의기약다항식에대하여기존의역수연산보다 7.4 26.65% 의수행시간단축을가져왔으며, AOP 타입에대해서는 20.5% 정도의수행시간을단축하였다. 이논문에서실험한허용비트범위인 50 250사이의경우실험결과는 3 non-zero term의경우나 5, 9, 및 3 non-zero term 인경우공히 trinomial 과 AOP에따라역수연산의효율에특이성을보이지않았다. 즉, 기약다항식의형태에큰영향이없이제안된 cz-bit hifting은향상된성능을보였다. 본논문과관련하여향후허용비트가 250 이상인큰데이터와다양한기저의데이터에관하여도관련연구가필요하다. 이연구를통하여하드웨어의구현없이, multi-bit hifting 만으로도어느정도의성능향상을꾀할수있을것으로기대된다. - 34 -
참고문헌 []. T. Itoh and S. Tujii, A fat algorithm for computing multiplicative invere in GF2 m uing normal bae, Information and Computation, 78, 7 77, 988 [2]. J. Juajardo and and C. Paar, Itoh Tujii inverion in tandard bai and it application in cryptography and code, 25, 207 26, 2002 [3]. D. V. Bailey and C. Paar, Optimal etenion field for fat arithmetic in public ey algorithm, CRYPTO 98, LNCS 462, 472 485, 998 [4]. B.S. Kalii Jr., The Montgomery invere and it application, IEEE Tran. on Computer, 44, 8, 064 065, 995 [5]. C. K. Koç and T. Acar, Montgomery multiplication in GF2, Deign, Code and Cryptography, 4,, 57 69, 998 [6]. E. Sava and C. K. Koç, The Montgomery modular invere reviited, IEEE Tran. On Computer, 49, 7, 763 766, 2000 [7]. M. Roing, Implementing elliptic curve cryptography, Manning Publ. Co., Greenwich, CT, 999 [8]. E. Sava, A.F. Tenca, M.E. Ciftcibai and C. K. Koç, Multiplier architecture for GFp and GF2 n, IEE Proc. Computer and Digital Tech., 5, 2, 2004 [9]. E. Sava, M. Naeer, A. A A. Gutub, and C. K. Koç, Efficient unified montgomery inverion with multibit hifting, Proceeding Computer and Digital Tech.,, 2004 [0]. D.E. Knuth, Seminumerical Algorithm Reading, MA: Addition Weley, - 35 -
98 []. A.J.Meneze, "Application of finite field," Kluwer academic publiher, Boton, 993. [2]. M.A. Haan, M.Z. Wang, and V.K. Bhargava, "A modified Maey-Omura parallel multiplier for a cla of finite field," IEEE Tranaction on Computer, 420, pp278-280, October 993. [3]. A.Meneze, P. van Oorchot, and S. Vantone, "Applied Cryptography," CRC Pre, 996 [4]. H. Reiel, "Prime Number and Computer Method for Factorization-2d ed," Birhauer, Boton, 987 [5]. Peter L. Montgomery, "Modular multiplication without trial diviion,", Mathematic of Computation, 4470:50-52, April 985 [6]. Jean-Claude Bajard, Laurent-Stephane Didier, and Peter Komerup, "An RNS Montgomery modular multiplication algorithm," IEEE Tranaction on Computer, 477:766-776, July 998 [7]. Gadiel Seroui, "Table of Low-Weight Binary Irreducible Polynomial," Hewlett-Pacerd Company, HPL-98-35, Augut 998-36 -