工學碩士學位論文 Paldromc 다항식을이용한 역수연산에관한연구 A Study o the Multplcatve Iverses Usg Paldromc Polyomals 005 年 月 仁荷大學校大學院 컴퓨터 情報工學科 李東烈
工學碩士學位論文 Paldromc 다항식을이용한 역수연산에관한연구 A Study o the Multplcatve Iverses Usg Paldromc Polyomals 005 年 月 指導敎授 柳亨善 이論文을碩士學位論文으로提出함. 仁荷大學校大學院 컴퓨터 情報工學科 李東烈
이論文을李東烈의碩士學位論文으로認定함. 005 年 月 主審 印 副審 印 委員 印
요 약 암호시스템의효율은암호화, 복호화과정의곱셈연산과역수연산에달려있다고잘알려져있다. 본논문은 Galos feld GF( m ) 에서 paldromc 다항식표현을사용한효율적인역수연산알고리즘을제안하였다. 효율적인산술알고리즘은기저의특성에따라좌우되고, 이전에많은논문들은다항식과최적정규기저를사용하였다. 본논문에서는최적정규기저형 Ⅱ와밀접하게관계가있는 paldromc 표현을사용한새로운역수알고리즘을제안하였다. 수정된 Gaussa 소거법은역수계산에사용하였다. 새로운알고리즘은기존의알고리즘보다더효율적이다. - -
Abstract It s well ow that the effcecy of a crytosystem depeds o basc operato algorthm such as multplcato ad verso. Ths paper proposes a effcet verso algorthm for Galos feld GF ( m ) whose elemets are represeted by paldromc polyomals. The effcecy of arthmetc algorthms depeds o the bass ad may foregog papers use ether polyomal or optmal ormal bass. I ths paper we suggested a ew verso algorthm usg paldromc represetato that s closely related wth the optmal ormal bass type Ⅱ. A modfed Gaussa elmato method s employed to calculate the verse. The ew algorthm s more effectve tha covetoal algorthm. - -
목 차 요약 ⅰ Abstract ⅱ 제 장서론 제 장기저들 4. 유한체 GF ( ) 4. 다항식기저 6. 3 최적정규기저 7. 3. 최적정규기저형 Ⅰ 8. 3. 최적정규기저형 Ⅱ 9. 4 캐노니컬기저 제 3 장역수연산 4 3. 확장유클리드알고리즘 4 3. Paldromc 다항식 6 - -
제 4 장구현 0 4. 구현환경및프로그램구성 0 4. 역수연산알고리즘 0 4. 3 실험결과 제 5 장결론 34 참고문헌 35 - v -
제 장서론 Galos Feld( 체 ) GF( m ) 에서산술연산은대수학, 암호학, 코딩이론등에서연구되어왔다. 대부분의공개키암호시스템들은큰차수의유한체 (Fte Feld) 들에서설계되어진다. 더욱이, 암호화와복호화의실행시간은곱셈과나눗셈에의해좌우된다. 이러한산술연산들을계산하기위한빠른알고리즘을개발하는것이중요하다 []. 특히최근에동일한안전도를유지하면서기타다른공개키암호시스템보다짧은길이의키를갖는타원곡선을이용한암호시스템이암호학적으로여러분야의기능적프로토콜에응용되고있다. 이러한타원곡선암호기법을사용하는전자서명프로토콜을수행하는과정과암호화, 키등의프로토콜에서도역시유한체의효율적인연산은중요한역할을한다 []. 유한체연산중에서덧셈, 뺄셈의경우에는각각의비트논리연산만을사용하기때문에하드웨어의효율성은 AND 와 XOR 논리연산이복합적으로결합된형태의곱셈연산에의해좌우한다. 유한체에서곱셈연산의효율적인구현은암호시스템의효율성에많은영향을미치기때문에구조적으로간단하고, 연산하는시간이효율적으로개선되도록하는연구가진행되고있다. 이연산들의효율은요소기저를표현하는방법과밀접한관계가있다. GF( m ) 에서가장많이쓰이는기저들로다항식기저 - -
(Polyomal Bass) 와정규기저 (Normal Bass) 가있다. 다항식기저는유한체상의기약다항식 (Irreducble Polyomal) 으로계산한다 [3]. 계산시간은기약다항식에의해결정된다. 기약다항식의 o-zero elemet 의개수가적은경우더좋은성능을나타내는것을알수있다. 확장체 (Eteso feld) GF( q m ) 에서 Itoh 와 Tsuj 의역수알고리즘은매우효율적인알고리즘이며 [4, 5], Koc 등은유한체에서의곱셈알고리즘들에관해논문을발행했으며 [6, 7], Paar 등도이에관한논문을냈다 [8]. Paldromc 표현을사용하고있는논문도있으며 [9], Rosg 에의해서소프트웨어적인구현문제가다루어졌다 [0]. GF ( m ) 에서역수연산을효율적으로수행하는몇개의알고리즘이제안되었다. 가장많이사용되는두가지방법으로확장유클리드 (Eteded eucldea) 알고리즘과 Fermat의정리이다. Fermat의정리를이용하여역수를구할경우 Wag등이제시한 알고리즘은 GF( m ) 에서 m- 번의자승과 m- 번의곱셈들이 필요하다 []. 하지만유클리드알고리즘을이용할경우두번의곱셈시간만소요되며, 이는다른알고리즘에비하여빠르다 []. 본논문에서는 ECC(ellptc curve cryptography) 에서응용가능한 40-0 사이의비트를대상으로곱셈에대한역원을구할때 AOPs(All-Oe-Polyomals) 을포함하는다른옵션을사용하여실험하였다. 첫번째실험은 GF( m ) 에서 AOPs와삼항다항식 (tromal polyomal) 을그리고, 삼항다항식과오항다항식 (petaomal polyomal) 을이용하여역수연산시확장 - -
유클리드알고리즘을사용하여실험하고비트수에대한시간의감소율을비교하였다. 두번째실험은기존의역수연산알고리즘과수정된 Gaussa 소거법을사용하여실험하고비트수에대한시간의감소율을비교하였다. 본논문에서는 paldromc 표현을사용할수있다면, 다항식형태의문제를사용할수있다는것이며, 진데이터타입을고려하여수정된 Gaussa 소거법을사용하여역수연산을쉽게구현할수있게하였다. - 3 -
제 장기저들 GF( m ) 에서가장널리사용되는기저는크게다항식기저 (Polyomal Bass) 와정규기저 (Normal Bass) 가있다. 체의덧셈과뺄셈연산은 OR(XOR) 에의해구현되어진다. 그러나, 곱셈과역수연산은선택한기저에따라달라진다. 타원곡선알고리즘의효율은선택한기저에의해영향을받는다 [0].. 유한체 GF ( m ) 유한체는덧셈과곱셈에대해서결합법칙과교환법칙, 분배법칙이성립하고덧셈에대한항등원과역원, 곱셈에대한항등원과역원을가지는유한개의원소로구성된집합이다 []. 유한체 GF( m ) 는 GF () 위의 m차기약다항식 f () 에대해 GF( )[ ]/( f ( )) 로생각할수있다. 그러므로유한체 GF( m ) 의임의의원소는 m-차다항식으로표현된다. 즉, 유한체의두원소 m A( ), B( ) GF( ) 는 A( ) = a a () m m m am a 0 B( ) = b b () m m m bm b 0 으로표현된다. 여기에서 0, j m 에대해 a, b GF() 이다. j - 4 -
또한이를간단히벡터형식으로다음과같이표현한다. A = a, a,, a, ) (3) ( m m a0 기약다항식으로는통상구현상의효율을위해 3개의항으로구성된 (4) 번식형태의삼항다항식을가장널리사용하며, m f ( ) =, (0 < < m) (4) 기약인삼항다항식이없는 m 에대해서는 (5) 번식형태의오항 다항식을사용한다. f ( 3 m ) 3 =, (0 < < < < m ) (5) 그리고 (6) 번식을차수가 m인 AOPs 이라한다. m 3 f ( ) = (6) - 5 -
. 다항식기저 다항식기저의표현은다음과같다. m m {,,,, } (7) 다항식기저의모든연산들은그기저에서정의된기약다항식 f () 로나누어야한다 [7]. 모듈계산시에이기약다항식으로 계산하는것이다. 다항식기저를이용한 A, B 의곱셈은다음과같다. A = B = = 0 m j = 0 a b j j (8) (9) A B m = c c =, a b (0) = 0 j 다항식기저 A 의역수를 B 라했을때역수계산은 () 번식에의해서계산한다. A B mod f ( ) () - 6 -
.3 최적정규기저 4 집합 M 의요소들 { β, β, β,, β } 이 GF( m ) m 의기저가 되면, 기저 M 을정규기저라고하고요소 β 를정규요소라한다 [3]. 정규기저의 A, B 의곱셈은다음과같다. A = a β () B = b j j β (3) C = A B = m m = 0 j = 0 j j a b β β (4) (4) 번식을정규기저의형태로바꾸면 (5) 번식이된다. m = C cβ (5) = 0 j m = β β λj β (6) = 0 λj 계수를 λ 행렬이라부른다. (5) 번, (6) 번식에의하여 c 계수는다음과같다. m m c = a b λ (7) = 0 j= 0 j j - 7 -
(7) 번식은우변의 항을소거시킨 (8) 번식으로변환이가능하다 [8]. m m c = a b λ (8) = 0 j= 0 j j0 최적정규기저는 0 이아닌최소의 λj 항을가지고있다. 최적 정규기저는두가지의형태를가지고있는데이들을최적정규기저형Ⅰ과최적정규기저형 Ⅱ라부른다. 두형의차이점은 λ 행렬을다르게계산하는것이다. 최적정규기저형 Ⅰ은 λ 행렬을계산하는데하나의벡터공간을이용한다. 반면에최적정규기저형 Ⅱ는두개의벡터공간을이용한다 [7].. 3. 최적정규기저형 Ⅰ GF( m ) 에서최적정규기저형 Ⅰ은아래의조건을만족시켜야한다. m 이소수 는환 Zm 에서생성자가된다. - 8 -
최적정규기저형 Ⅰ에서곱셈은 (6) 번식에서 = 0 고려한다. 일때만 β β = β j (9) 여기에는한가지특별한경우가존재한다. j β β = (0) (9) 번식과 (0) 번식을풀기위해지수만살펴보면다음과 같다. j = mod m j = 0 mod m () () () 번식과 () 번식을이용하여 λ 행렬을구한다.. 3. 최적정규기저형 Ⅱ GF( m ) 에서최적정규기저형 Ⅱ은아래의조건을만족시켜야한다. m 이소수 이며다음두가지조건들중한가지를만족시켜야한다 [9]. - 9 -
는환 Z m 에서생성자가된다. m = 3 mod 4 는환 Z m 에서이차잉여 (Quadratc Resdue) 의생성자가된다. GF( m ) 에서최적정규기저형 Ⅱ의정규요소 β 는 (4) 번식을만족하는생성자 γ 로바꾸어쓸수있다. = γ β γ (3) m γ =, r, < m (4) GF( m ) 의특성중 (5) 번식의특성에의해다음 (6) 번, (7) 번식이성립한다. p p p ( α β ) = α β (5) = γ β γ (6) M β = γ γ (7) 최적정규기저형 Ⅱ 에서의곱셈은다음과같다. j j β β = ( γ γ )( γ γ ) (8) j j j ( ) ( ) = ( γ γ ) ( γ γ ) (9) j j - 0-
Kuth 등은 (30) 번식이성립됨을증명하였다. γ γ = ( γ γ ) (30) 위식에의하여다음을얻을수있다. j ' j β β = β β, mod m (3) j = β, mod m (3) = 0 일때다음 4개의식을이용하여 λ 행렬을구한다. j = (33) j = (34) j = (35) j = (36) - -
.4 캐노니컬기저 GF( m ) 의정규기저는다음의식과같다 M m = { β, β, β,, β }, β GF( m ) (37) 이영역내의최적정규기저형 Ⅱ 의정규요소 β 는 (3) 번식과 같다. 이기저에서요소의자승은기저의순환이동과같다. 정규요소를사용한정규기저 M 은다음의식과같다. M ( m ) ( m ) = { γ γ, γ γ, γ γ,, γ γ } (38) 그러므로정규요소 γ γ 는 j j γ γ 로쓸수있다 [7]. 따 라서다음두개의기저 M 과 N 은동등하다. 3 3 m m N = { γ γ, γ γ, γ γ,, γ γ } (39) 이것은 β = γ γ 의관계를이용한캐노니컬기저의이동형태 이다. N = β, β, β,, β } (40) { 3 m (7) 번식은다음과같이쓸수있다. - -
β j j = γ γ γ γ (4) β β j (4) β j 의요소의집합을캐노니컬기저라부른다 [3]. - 3-
제 3 장역수연산 타원곡선에서암호화와복호화의연산시간은역수연산시에가장오래걸리기때문에역수연산을효율적으로하는것이매우중요하다. 암호화나복호화하는데걸리는시간을단축해야만효율을높일수있다. 3. 확장유클리드알고리즘 다항식기저는유한체상의역수연산에서자주선택된다. 주어진다항식 r() 와기약다항식 f () 를가지고 r() p() 를구하는식은다음과같다 [0]. 의역수 r( ) p( ) mod f ( ) (43) 다음변수들을초기화하면서알고리즘을시작된다., r, p, p, q, q r (44) r, p, q 를 r = 0 일때까지계속해서계산한다. 다음과같이초기화한다. r r p = f ( ) = r( ) = 0 (45) - 4-
p q q = = = 0 (46) (47) 번식으로반복실행한다. r q p = r = r = q mod / r p r p (47) 모듈러단계는나눗셈한나머지로쉽게계산된다. 만일나머지가 0이아니면변수들을바꾼다. r = r, r = r q = q, q = q p = p, p = p (48) 예상했던것처럼모든변수들은갱신된다. 최소의 o-zero 요소를가진기약다항식이최선이라는것은명백하지않다. 유한체에서역수연산구현은적절한기약다항식을선택해야한다. GF( m ) 의산술연산에서 o-zero 입력값이낮을수록더효율적이다. 확장유클리드알고리즘에서기약다항식은 (47) 번식의처음에사용된다. - 5-
3. Paldromc 다항식 Paldromc 다항식 (49) 번식의 GF () 영역내의모든 다항식벡터공간에둔다. 덧셈은일반적인다항식으로정의되며, 두개의 paldromc 다항식의곱은식 mod p, p = 로 유일하게얻어진다 [3]. a( ) = = a, a = a p, =,, K,. (49) a() 에서 를 γ 로치환하면, (50) 번식을얻는다. γ ) = a γ = a ( γ ) (50) = = a( γ 그러므로 (50) 번식의기저는 (40) 번식의기저와같다. a() 의계수와 a(γ ) 의정규기저표현사이의관계는단순하다. Paldromc 표현이최적정규기저수로사용될수있다는것을 의미한다. 두개의 paldromc 요소 a( ), b( ) 의곱은다음 (53) 번식에의해계산된다. a a a (5) a( ) = a b b b (5) b( ) = b - 6-
- - 7. ) ( ) ( 4 3 3 3 a b b a b a a b a b b a b a a b a b b a b a a b b a = (53) 항목을재정리한후 (54) 번식에의해 ) ( c 를얻는다.. ) (mod ) ( ) ( ) ( a b b a b a b a a b b a b a b a a b b a c (54) Paldromc 성질을고려할때, 이식의반쪽만을고려해도만족한다. 의오름차순으로항을재배열하여 (55) 번식을얻을수있다. ( ) ( ) ( ) b a a b b a b a a b a b b a b a c 3 3 ) ( (55)
a() 와 b() 는각각 (55) 번식의모든계수들의곱셈에대한역원이다. 이방정식에서 조건을얻을수있고, 그것은대칭계수행렬의선형방정식 (56) 번식으로변경할수있다. a ( a a ) a 4 3 Sym. M ( a ( a a a M a ) b ) b = M M b (56) Paldromc 경우에서역수알고리즘을선택할수있으며, 하나는유클리드알고리즘이고다른하나는 Gaussa 소거법이다. 유클리드알고리즘의선택이성공률이높지만, 이번의경우는 달랐다. 필드길이는종래의케이스의두배인 이고, 수행시간 이훨씬길었다. Gaussa 알고리즘은미정의 차원에서계산시간이길어진다고알려져있지만, 고려해보아야할두가지의특이점이있다. 하나는행렬내에서 진 data를다루고있다는점이며, 다른하나는 paldromc 속성을사용하여크기를 으로줄일수있다는것이다. 진 data의대칭행렬을다루는이유로, 계산시간은실수경우에서와다를수있다. 소거법중에서는피벗의방법을적용시키는것이일반적이다. - 8-
만일 zero 속성을가지면, 소거단계는가속되며, 계산시간은최적정규기저경우와비교된다. 희소성은 진성질로부터비롯되며, 엔트리들은 개의입력계수들의합이다. 만약속성의반이 zero 이라면, 소거단계시간은반으로줄게될것이다. - 9-
제 4 장구현 4. 구현환경및프로그램구성 구현환경 - Petum Ⅳ.5 GHz - Memory 5 MB 프로그램구성 - 입력부분 : 최적정규기저에해당하는비트를입력 - 역수연산계산 : 가우스소거법을사용하여상삼각행렬을구한다음후진대입법 (bac-substtuto) 을수행 - 출력부분 : 역수연산결과를출력 4. 역수연산알고리즘 역수연산알고리즘은 paldromc 표현을사용하여다항식의크기를 으로줄여서부분피벗팅에의한가우스소거법을사용하여대각원소가 인상삼각행렬을구한다음후진대입법을수행한다. 기존의알고리즘은역수연산시곱셈연산을정규기저에서캐노니컬기저로변환하여계산하는알고리즘과자승연산시졍규기저를이용하는알고리즘을혼합하여사용하였다. - 0-
4.3 실험결과 본논문에서타원암호문제에적용할수있도록낮은차수다항식을고려하고있다. 첫번째실험은확장유클리드알고리즘을사용하여 AOPs와삼항다항식을그리고삼항다항식과오항다항식을실험하고비교하였다. 실험결과는 Rosg등이제시한프로그램을각각,000번반복시켜얻은시간을비교하였다. 40-0bt 사이의 7 개의 AOPs(48, 6, 7, 78, 80, 96, 0) 가있다. 표 은 3개의 o-zero 요소의역수연산계산결과를나타낸다. o-zero 요소의포인트는 (0, 64, 8) 이다. AOPs 가삼항다항식대부분의경우보다더효율적이다. 더욱이 AOPs의경우다른비트값들보다변화폭이적다. 그계산시간은 4.09~3.0% 감소시켰다. - -
표. 삼항다항식과 AOPs 의역수계산시간 8 64 A = (m sec) No. of bts Tromal AOP % decrease 48.39 0.5359 43.53 6.75 0.78 4.09 7 0.88 0.63 76.807 78.09 0.575 5.65 80 0.5093 0.665 3.0 96 0.4578 0.48 05. 0.0703 0.6656 6.88 표 에서도비슷한패턴을볼수있다. 5 개의 o-zero 요소는 (0, 3, 64, 96, 8) 이다. 여기서는시간의변화가 4.539~7.85% 감소시켰다. 표. 삼항다항식과 AOPs 의역수계산시간 8 96 64 3 A = (m sec) No. of bts Tromal AOP % decrease 48.0468 0.4453 4.539 6 0.756 0.38 50.40 7 0.6703 0.4687 69.94 78.056 0.664 6.867 80 0.706 0.475 67.6 96.3656 0.9359 68.534 0.6796.06 7.85 - -
표 3 에서보여주는 0개의 o-zero 요소는 (0, 6, 3, 48, 64, 80, 96,, 8, 44) 이다. 계산시간은 9.883~.838 감소시켰다. 감소율은 AOPs와삼항다항식의계산시간의비율로정의된다. 표 3. 삼항다항식과 AOPs 의역수계산시간 44 8 96 80 64 48 3 6 A = (m sec) No. of bts Tromal AOP % decrease 48.05 0.45 37.449 6.87 0.3343 9.883 7 0.4359 0.4875.838 78 0.8703 0.488 55.475 80 0.767 0.63 8.84 96.453 0.7656 66.847 0.7468 0.8453 48.39 그림 은모든경우에대하여비트수에대한감소율을보여준다. 이실험에서 AOPs는삼항다항식보다좋다는것을보여준다. - 3-
% decrease 40 0 00 80 60 40 0 0 48 6 7 78 80 96 0 Bts o-zero pot 3 o-zero pot 5 o-zero pot 0 그림. 삼항다항식과 AOPs 의비트수에대한감소율 또한 6 개의삼항다항식과오항다항식을포함한다. (46, 55, 6, 86, 96, 0) 모든입력값은전처럼사용된다. 표 4 는 3 개의 o-zero 요소의역수연산계산결과를 나타낸다. 삼항다항식이낮은비트에서는오항다항식보다낫다. 그러나다른비트의경우에따라계산시간이변화한다. - 4-
표 4. 삼항다항식과오항다항식의역수계산시간 8 64 A = (m sec) No. of bts Tromal Petaomal % decrease 46.3906 0.939 67.53 55 0.7843.375 45.034 6.7375.353 77.876 86 0.603 0.975 57.8 96 0.4734 0.906 9.44 0.075.455 35.03 표 5 는표 4 와거의같은패턴을볼수있다. 계산시간은 45.45 에서 56.3 까지변한다. 표 5. 삼항다항식과오항다항식의역수계산시간 8 96 64 3 A = (m sec) No. of bts Tromal Petaomal % decrease 46.434 0.675 47.4 55.67 0.58 45.49 6 0.756 0.578 75.65 86 0.787.34 56.30 96.3734.756 7.87 0.6796.4484 86.35-5-
표 6 은전처럼 0 개의 o-zero 입력값이다. 입력값 ozero 요소는 44bt 보다더작다. 표 6. 삼항다항식과오항다항식의역수계산시간 44 8 96 80 64 48 3 6 A = (m sec) No. of bts Tromal Petaomal % decrease 46.467 0.8406 57.97 55.365 0.34 5.790 6.8 0.4859 43.34 86.096 0.9843 95.600 96.437.0656 80.607 0.7656.009 3.893 그림 는모든경우의실험에대한비트수와감소율을 보여준다. 이실험에서삼항다항식이오항다항식보다좋다는 것은명확하지않다는것을보여준다. - 6-
50 00 % decrease 50 00 50 0 46 55 6 86 96 0 Bts o-zero pot 3 o-zero pot 5 o-zero pot 0 그림. 삼항다항식과오항다항식의비트수에대한감소율 - 7-
두번째실험에서첫번째제안은 paldromc 표현을사용할수있다면다항식형태의문제를사용할수있다는것이며, 두번째제안은 진데이터타입을고려하여수정된 Gaussa 소거법을사용한다면속도를향상시킬수있다는것이다. 타원곡선암호에서의비트수의범위는일반적으로 50~00사이이다. 이범위안에서 5개의최적정규기저와 0개의형 II 를구성할수있다. 형 II 수들은 55, 58, 73, 74, 79, 83, 86, 89, 9, 94이다. 이중 73,79와 9 은소수이며, Itoh-Tsuj의알고리즘처럼필드를축소하는알고리즘들을사용하는것이불가능하다. 그알고리즘은다른입력값에대해다른결과를보인다. 그래서 4개의다른비트의세트, o-zero 요소가 4, 5, 6, 개인경우를테스트하여, 4개의입력경우를지닌 0개의비트수에대한수치적결과를얻었다. - 8-
표 7은 4개의 o-zero 요소의역수연산계산결과이다. ozero 입력값은 (3,63,95,7) 이다. 새로운알고리즘은시간을 8.369~ 5.305% 감소시켰으며, 이는기대되었던행렬의희소성에서비롯된결과이다. 표 7. No-zero 요소가 4 개일때역수계산시간 A = 7 95 63 β β β β 3 (m sec) No. of bts Covetoal algorthm New algorthm % decrease 55.55 0.9 5.305 58.33 0.64 0. 73.506 0.347 3.030 74.744 0.30 8.369 79.634 0.34 0.937 83.747 0.34 9.589 86.044 0.363 7.739 89.86 0.386 0.743 9.89 0.398.055 94.85 0.40.000-9-
표 8에서도거의같은패턴을볼수있다. 5개의 o-zero 입력값은 (0,3,64,96,8) 이다. 여기서는시간의변화가 57.90~69.% 를보인다. 이감소비율은이전과새로운방법의계산시간비율이다. 표 8. No-zero 요소가 5 개일때역수계산시간 8 96 64 A = β β β β β (m sec) 3 No. of bts Covetoal algorthm New algorthm % decrease 55.50 0.8 65.75 58.463 0.847 57.90 73.59 0.99 65.33 74.758.005 57.57 79.683.070 63.60 83.883.4 59.67 86.684.66 69.0 89.895.69 6.668 9.93.9 63.73 94.59.38 57.308-30-
표 9 에서보여주는 6 개의 o-zero 입력값은 (0, 3, 64, 96, 8, 54) 이다. 계산시간은 67.654~76.84% 감소하였다. 표 9. No-zero 요소가 6 개일때역수계산시간 54 8 96 A = β β β β β β (m sec) 64 3 No. of bts Covetoal algorthm New algorthm % decrease 55.7 0.94 76.84 58.405 0.986 70.93 73.684.86 70.45 74.758.9 69.33 79.697.78 75.34 83.847.344 7.760 86.97.39 7.533 89.933.48 73.888 9.73.470 67.654 94.03.53 75.697-3-
표 0 에서는 개의 o-zero 입력값은 (0, 6, 3, 48, 64, 80, 96,, 8, 44, 54) 를테스트하고유사한결과를얻었다. 이경우는 60.94 ~ 7.807% 감소하였다. 표 0. No-zero 요소가 개일때역수계산시간 A = β β 54 3 β β 44 6 β β 8 β β 96 β 80 β 64 β 48 (m sec) No. of bts Covetoal algorthm New algorthm % decrease 55.358 0.975 7.807 58.595 0.977 6. 73.700.7 68.99 74.948.97 6.45 79.038.56 6.659 83.53.303 60.57 86.67.349 6.3 89.053.43 68.798 9.336.44 60.940 94.064.467 7.08-3-
그림 3 에서모든경우의테스트에대한비트수와감소율을 보여준다. 90 80 70 60 % decrease 50 40 30 0 0 0 No. of o-zero pots : 4 : 5 : 6 : 55 58 73 74 79 83 86 89 9 94 Bts 그림 3. 비트수와감소율 - 33-
제 5 장결론 정보화및디지털화의시대적흐름에서정보보호및암호에대한관심은필연적인요소가되었고, 그에따른문제해결이현실화되었다. 따라서공개키암호에대한연구가여러방면에서활발히진행되고있다. 공개키암호시스템은소인수분해문제를이용한 RSA 시스템이있고, 이산대수문제를이용한 ElGamal과타원곡선암호시스템이있다. 이들중에서타원곡선암호시스템은적은키길이를가지고다른공개키암호시스템과같은안전도를가지는장점을가지고있다. 본논문에서는첫번째로역수연산시확장유클리드알고리즘을사용하여실험했을때 AOPs는삼항다항식보다뛰어나고삼항다항식은오항다항식과거의비슷하다는것을알았다. AOPs는 40-0 사이의비트를대상으로역수연산시에효율적이라는것을알았다. 두번째는최적정규기저형 Ⅱ와밀접하게관계가있는 paldromc 표현을사용한새로운역수알고리즘을구현하였다. 수정된 Gaussa은계수행렬의 진성질때문에가능하지만기존의유클리드알고리즘은 paldromc 표현이두배의필드길이 을가지므로제안되지않는다. 결과비교를통하여최적정규기저형 Ⅱ 에서곱셈연산에서는캐노니컬기저를자승연산에서는정규기저를혼용하여이용하는것보다 Gaussa 소거법을사용하는것이더효율적이라는것을알았다. - 34-
Refereces [] R. dl ad H. Nederreter, Itroducto to fte felds ad ther applcatos, Cambrdge Uversty Press, Cambrdge, 986 [] IEEE P363. Stadard for Publc-Key Cryptosystem, 999, Draft Verso 3 [3] S. Gao ad D. Paaro, Tests ad costructos of rreducble polyomal over fte feld, Cotemporary Mathematcs, vol. 5, 43-54, 999 [4] T. Itoh ad S. Tsuj, A fast algorthm for computg multplcatve verses GF ( m ) usg ormal bases, vol. 78, 7-77, 998 [5] J. Juajardo ad C. Parr, Itoh-Tsuj verso stadard bass ad ts applcato cryptography ad codes, vol. 5, 07-6, 00 [6] Ḉ. K. Koḉ ad T. Acar, Motgomery multplcato GF ( ), Desg, codes ad Cryptography, vol 4, 57-69, 998 [7] B. Suar ad Ḉ. K. Koḉ, A effcet optmal ormal bass type Ⅱ multpler, IEEE Tras. O Computers, vol 50, 83-87, 00 [8] D. V. Baley ad C. Paar, Optmal eteso felds for fast arthmetc publc-ey algorthms, CRYPTO 98, NCS 46, 47-485, 998-35-
[9] I.F. Blae, R.M. Roth ad G. Serouss, Effcet Arthmetc GF ( ) through Paldromc Represetato, Hewlett- Pacard, HP-98-34, 998 [0] M. Rosg, Implemetg Ellptc Curve Cryptography, Mag Publcatos Co. 999 [] C. C. Wag, T. K. Truog, H. M. Shao,. J. Deutsch, J. K. Omura, ad I. S Reed, VSI Archtecture for Computg Multplcatos ad Iverses GF ( m ), IEEE Trasacto Computers, vol. 34, o. 8, 709-76, Aug. 985 [] Y. Jeog, W. Burleso, VSI Array Sythess for Polyomal GCD Computato ad Applcato to Fte Feld Dvso, IEEE Trasacto o Crcuts ad Systems, 89-897, Dec. 994 [3] R. C. Mull, I. M. Oyszchu, S. A. Vastoe, ad R. M. Wlso, Optmal Normal Bases GF ( p ), Dscrete Appled Math, vol., 49-6, 998/89-36-
감사의글 년동안의짧고도긴대학원생활동안공부하고연구한결과를토대로본논문을작성하였습니다. 부족하기만했던저에게끊임없는관심과충고, 질책과조언을아끼지않았던분들에게조금이나마이글을빌어감사의마음을띄우고자합니다. 철부지학생이었던저를아낌없는마음으로지도와격려를보내주시고, 무한한가르침을주시고저를위해많은시간을할애해주셨던유형선교수님께깊은감사를드립니다. 또한저의논문의문제점과개선사항을지적해주시며보다나은결실을맺게해주신이필규교수님, 이정현교수님께감사를드립니다. 힘들고어려운일이있을때마다격려와용기를주시며모범이되어주신큰형님김의선님께깊은감사를드립니다. 이미졸업했지만대학원생활동안큰힘이되어준석웅형, 그리고대학원생활을함께한인주누나, 정호, 환규, 그리고정보시스템연구실의덕만, 희재등모두에게감사드립니다. 모든분들에게깊은감사드리며마지막으로저를지금의자리까지있게해주신부모님과누나들에게도깊은감사드리며저의논문을이모든분들에게바칩니다. 004년 월 0일이동렬 - 37-