유한체 $GF(2^n)$에서 낮은 공간복잡도를 가지는 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기

장남수,한동국,정석원,김창한,Chang Nam-Su,Han Dong-Guk,Jung Seok-Won,Kim Chang Han 대한전자공학회 2004 電子工學會論文誌-SC (System and control) Vol.41 No.1

유한체 $GF(2^n)$에서 두 원소의 곱셈을 수행하는 공간 복잡도가 낮은 병렬 처리 곱셈기의 구현에 있어서 divide-and-conquer 방법은 유용하게 사용된다. 이를 이용한 가장 널리 알려진 알고리듬으로는 카라슈바 (Karatsuba-Ofman) 알고리듬과 다중 분할 카라슈바(Multi-Segment Karatsuba) 알고리듬이 있다. Leo ne은 카라슈바 알고리듬의 최적화된 반복 횟수를 제안하였고, Ernst는 다중 분할 카라슈바 방법을 이용한 일반적이고 확장 가능한 유한체 곱셈기를 제안하였다. 본 논문에서는 Ernst가 제시한 다중 분할 카라슈바 병렬 처리 곱셈기의 복잡도를 제시한다. 또한 기존 방법의 병렬 처리 곱셈기와 시간 복잡도는 같지만 공간 복잡도는 낮은 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기를 제안하며 그에 따른 최적화된 반복 횟수를 제안한다. 나아가서 제안하는 곱셈기가 몇몇 유한체에서 카라슈바 방법의 병렬 처리 곱셈기 보다 공간 복잡도에서 효과적임을 제시한다. The divide-and-conquer method is efficiently used in parallel multiplier over finite field $GF(2^n)$. Leone Proposed optimal stop condition for iteration of Karatsuba-Ofman algerian(KOA). Ernst et al. suggested Multi-Segment Karatsuba(MSK) method. In this paper, we analyze the complexity of a parallel MSK multiplier based on the method. We propose a new parallel MSK multiplier whose space complexity is same to each other. Additionally, we propose optimal stop condition for iteration of the new MSK method. In some finite fields, our proposed multiplier is more efficient than the KOA.

고속 RSA 하드웨어 곱셈 연산과 하드웨어 구조

장남수(Nam Su Chang),임대성(Daesung Lim),지성연(Sung Yeon Ji),김창한(Chang Han Kim),윤석봉(Suk Bong Yoon) 한국정보보호학회 2007 정보보호학회논문지 Vol.17 No.1

몽고메리 곱셈 방법을 이용한 고속 연산은 RSA 암호 시스템의 설계에 중요한 부분을 차지한다. 몽고메리 곱셈은 두번의 덧셈 연산으로 구성되며 CSA를 이용한 방법과 RBA를 이용한 방법이 있다. CSA의 경우 4-2 CSA 또는 5-2 CSA를 이용하여 구현하며, RBA의 경우 기존 이진 방법과 달리 잉여 이진체계를 이용한다는 특징을 가진다. [1]에서는 기존의 RBA와 다른 새로운 이진 체계와 하드웨어 구조를 제안하고 몽고메리 곱셈에 적용하였다. 본 논문에서는[1]에서 제안한 RBA의 로직 구조를 재구성하여 시간 복잡도 뿐만 아니라 결합기가 필요하지 않도록 구성하여 공간 복잡도를 크게 줄였다. 또한 입?출력 값을 변형시켜 지수승 연산에 적합하도록 설계하였다. 그 결과 제안하는 RBA는 삼성 STD130 0.18㎛ 1.8V 표준 셀 라이브러리에서 지원하는 게이트들을 사용하여 설계하는 환경에서, 기존의 4-2 CSA 보다 공간과 시간 복잡도를 각각 18.5%와 25.24%를, 기존의 RBA 보다 6.3%와 14%를 감소시킨다. 또한[1]의 RBA와 비교시 44.3%, 2.8%의 감소된 복잡도를 갖는다. A fast Montgomery multiplication occupies important to the design of RSA cryptosystem. Montgomery multiplication consists of two addition, which calculates using CSA or RBA. In terms of CSA, the multiplier is implemented using 4-2 CSA or 5-2 CSA. In terms of RBA, the multiplier is designed based on redundant binary system. In[1], A new redundant binary adder that performs the addition between two binary signed-digit numbers and apply to Montgomery multiplier was proposed. In this paper, we reconstruct the logic structure of the RBA in[1]for reducing time and space complexity. Especially, the proposed RB multiplier has no coupler like the RBA in[1]. And the proposed RB multiplier is suited to binary exponentiation as modified input and output forms. We simulate to the proposed NRBA using gates provided from SAMSUNG STD130 0.18㎛ 1.8V CMOS Standard Cell Library. The result is smaller by 18.5%, 6.3% and faster by 25.24%, 14% than 4-2 CSA, existing RBA, respectively. And Especially, the result is smaller by 44.3% and faster by 2.8% than the RBA in[1].

반복 기약다항식 기반의 효율적인 비트-병렬 다항식 기저 곱셈기

장남수(Nam Su Chang),김창한(Chang Han Kim),홍석희(Seokhie Hong) 한국정보보호학회 2009 정보보호학회논문지 Vol.19 No.6

최근 Wu는 효율적인 비트-병렬 곱셈기를 위한 세 가지 종류의 이진체 제안하였다. 제안된 곱셈기는 오항 기약다항식을 사용하는 기존의 결과보다 효율적이다. 본 논문에서는 비트-병렬 곱셈에서 효율적인 이진체 위의 새로운 반복다항식(Repeated Polynomial:RP)을 제안한다. 제안하는 RP를 case 1, case 2와 case 3 3가지로 구분할 때, 제안하는 RP를 위한 비트-병렬 곱셈기는 기존의 오항 기약다항식의 결과보다 효율적이다. 유한체의 차수가 1,000이하에서 EPS 또는 삼항 기약다항식이 없는 차수를 고려할 때, Wu의 단지 11개의 유한체만 존재한다. 그러나 제안하는 결과는 case 1에서 181, case 2에서 232 그리고 case 3에서 443개의 유한체가 존재한다. Recently, Wu proposed a three small classes of finite fields F2ⁿ for low-complexity bit-parallel multipliers. The proposed multipliers have low-complexities compared with those based on the irreducible pentanomials. In this paper, we propose a new Repeated Polynomial(RP) for low-complexity bit-parallel multipliers over F2ⁿ. Also, three classes of Irreducible Repeated polynomials are considered which are denoted, respectively, by case 1, case 2 nad case3. The proposed RP bit-parallel multiplier has lower complexities than ones based on pentanomials. If we consider finite fields that have neither a ESP nor a trinomial as an irreducible polynomial when n ≤ 1,000. Then, in Wu’'s result, only 11 finite fields exist for three types of irreducible polynomials when n ≤ 1,000. However, in our result, there are 181, 232, and 443 finite fields of case 1, 2 and 3, respectively.

고속 비트-직렬 유한체 곱셈기

장남수(Nam Su Chang),김태현(Tae-Hyun Kim),이옥석(Ok Suk Lee),김창한(Chang Han Kim) 대한전자공학회 2008 電子工學會論文誌-SD (Semiconductor and devices) Vol.45 No.2

유한체 연산 기반의 암호시스템에서 곱셈 연산은 가장 주된 연산부로 구성된다. 또한 곱셈기 설계 환경의 자원이 제약적인 경우 비트-직렬 구조가 많이 고려된다. 본 논문은 기존의 비트-직렬 곱셈기에 비하여 작은 시간 복잡도를 가지는 삼항 기약 다항식 기반의 유한체 고속 비트-직렬 곱셈기를 제안한다. 제안하는 두 가지 타입의 곱셈기는 기존의 곱셈기에 비하여 시간 복잡도면에서는 모두 효율적이고, Interleaved 곱셈기의 mㆍMUL+2mㆍADD 시간지연 보다 작은 (m+1)ㆍMUL+(m+1)ㆍADD 시간 지연만으로 수행이 가능하다. 따라서 확장체의 표수가 작은 타원곡선 암호 시스템, 페어링 기반의 암호시스템에서 고속 동작가능하며, 표수가 2 또는 3인 경우 기존의 곱셈기 보다 대략 2배 빠르게 동작한다. In cryptosystems based on finite fields, a modular multiplication operation is the most crucial part of finite field arithmetic. Also, in multipliers with resource constrained environments, bit-serial output structures are used in general. This paper proposes two efficient bit-serial output multipliers with the polynomial basis representation for irreducible trinomials. The proposed multipliers have lower time complexity compared to previous bit-serial output multipliers. One of two proposed multipliers requires the time delay of (m+1)ㆍMUL+(m+1)ㆍADD which is more efficient than so-called Interleaved Multiplier with the time delay of mㆍMUL+2mㆍADD. Therefore, in elliptic curve cryptosystems and pairing based cryptosystems with small characteristics, the proposed multipliers can result in faster overall computation. For example, if the characteristic of the finite fields used in cryprosystems is small then the proposed multipliers are approximately two times faster than previous ones.

GF(3<SUP>m</SUP>)의 Digit-Serial 유한체 곱셈기

장남수(Nam Su Chang),김태현(Tae-Hyun Kim),김창한(Chang Han Kim),한동국(Dong-Guk Han),김호원(Ho Won Kim) 대한전자공학회 2008 電子工學會論文誌-SD (Semiconductor and devices) Vol.45 No.10

최근 페어링 기반의 암호시스템에 대한 연구가 활발히 진행되고 있으며, 암호시스템의 효율성은 기존의 공개키 암호시스템과 같이 유한체에 의존한다. 페어링 기반의 암호시스템의 경우 주로 GF(3<SUP>m</SUP>)에서 고려되며 유한체 연산에서 곱셈 연산이 효율성에 가장 큰 영향을 미친다. 본 논문에서는 삼항 기약다항식 기반의 새로운 GF(3<SUP>m</SUP>) MSD-first Digit-Serial 곱셈기를 제안한다. 제안하는 MSD-first Digit-Serial 곱셈기는 모듈러 감산 연산부를 병렬화하여 공간복잡도는 기존의 결과와 거의 같으나 Critical Path Delay가 기존의 1MUL+(log「n」+1)ADD에서 1MUL+(log「n+1」)ADD으로 감소한다. 따라서 Digit이 2<SUP>k</SUP>가 아닌 경우 1번의 덧셈에 대한 시간 지연이 감소한다. Recently, a considerable number of studies have been conducted on pairing based cryptosystems. The efficiency of pairing based cryptosystems depends on finite fields, similar to existing public key cryptosystems. In general, pairing based ctyptosystems are defined over finite fields of chracteristic three, GF(3<SUP>m</SUP>), based on trinomials. A multiplication in GF(3<SUP>m</SUP>) is the most dominant operation. This paper proposes a new most significant digit(MSD)-first digit-serial multiplier. The proposed MSD-first digit-serial multiplier has the same area complexity compared to previous multipliers, since the modular reduction step is performed in parallel. And the critical path delay is reduced from 1MUL+(log「n」+1)ADD to 1MUL+(log「n+1」)ADD. Therefore, when the digit size is not 2k, the time delay is reduced by one addition.

페어링 기반 암호시스템의 효율적인 유한체 연산기

장남수(Nam Su Chang),김태현(Tae Hyun Kim),김창한(Chang Han Kim),한동국(Dong-Guk Han),김호원(Ho Won Kim) 한국정보보호학회 2008 정보보호학회논문지 Vol.18 No.3

페어링 기반의 암호시스템의 효율성은 페어링 연산의 효율성에 기반하며 페어링 연산은 유한체 GF(3<SUP>m</SUP>)에서 많이 고려된다. 또한 페어링의 고속연산을 위하여 삼항 기약다항식을 고려하며 이를 기반으로 하는 하드웨어 설계방법에 대한 연구가 활발히 진행되고 있다. 본 논문에서는 기존의 GF(3) 연산보다 효율적인 새로운 GF(3) 덧셈 및 곱셈 방법을 제안하며 이를 기반으로 새로운 GF(3<SUP>m</SUP>) 덧셈-뺄셈 unified 연산기를 제안한다. 또한 삼항 기약다항식을 특징을 이용한 새로운 GF((p<SUP>m</SUP>) MSB-first 비트-직렬 곱셈기를 제안한다. 제안하는 MSB-first 비트-직렬 곱셈기는 기존의 MSB-first 비트-직렬곱셈기보다 시간지연이 대략 30%감소하며 기존의 LSB-first 비트-직렬 곱셈기보다 절반의 레지스터를 사용하여 효율적이며, 제안하는 곱셈 방법은 삼항 기약다항식을 사용하는 모든 유한체에 적용가능하다. The efficiency of pairing based cryptosystems depends on the computation of pairings. pairings is defined over finite fileds GF(3<SUP>m</SUP>) by trinomials due to efficiency. The hardware architectures for pairings have been widely studied. This paper proposes new adder and multiplier for GF(3) which are more efficient than previous results. Furthermore, this paper proposes a new unified adder-subtractor for GF(3<SUP>m</SUP>) based on the proposed adder and multiplier. Finally, this paper proposes new multiplier for GF(3<SUP>m</SUP>). The proposed MSB-first bit-serial multiplier for GF(p<SUP>m</SUP>) reduces the time delay by approximately 30 % and the size of register by half than previous LSB-first multipliers. The proposed multiplier can be applied to all finite fields defined by trinomials..

유한체 GF(2ⁿ)에서 낮은 공간 복잡도를 가지는 새로운 다중 분할 카리슈바 방법의 병렬 처리 곱셈기

장남수(Nam-Su Chang),한동국(Dong-Guk Han),정석원(Seok-Won Jung),김창한(Chang Han Kim) 大韓電子工學會 2004 電子工學會論文誌-CI (Computer and Information) Vol.41 No.1

삼항 기약다항식 기반의 저면적 Shifted Polynomial Basis 비트-병렬 곱셈기

장남수(Nam Su Chang),김창한(Chang Han Kim) 한국정보보호학회 2010 정보보호학회논문지 Vol.20 No.5

최근 Fan과 Dai는 이진체 곱셈기의 효율성을 개선하기 위하여 Shifted Polynomial Basis(SPB)를 제안하고 이를 이용한 non-pipeline 비트-병렬 곱셈기를 제안하였다. SPB는 PB에 {1,α,…,α<SUP>n-1</SUP>}에 α<SUP>-ν</SUP>를 곱한 것으로, 이둘 사이는 매우 적은 비용으로 쉽게 기저 변환이 된다. 이후 삼항 기약다항식 f(χ)=χ<SUP>n</SUP>+χ<SUP>κ</SUP>+1을 사용하여 Modified Shifted Polynomial Basis(MSPB) 기반의 SPB 비트-병렬 Mastrovito type Ⅰ과 type Ⅱ 곱셈기가 제안되었다. 본 논문에서는 SPB를 이용한 비트-병렬 곱셈기를 제안한다. n≠2κ 일 때 제안하는 곱셈기 구조는 기존의 모든 SPB 곱셈기와 비교하여 효율적인 공간 복잡도를 가진다. 또한, 기존의 가장 작은 공간 복잡도를 가지는 곱셈기와 비교하여1≤κ≤(n+1)/3 인 경우 항상 효율적이다. 또한, (n+2)/3≤κ<n/2 인 경우에도 일부 경우를 제외하고 기존 결과 보다 항상 작은 공간 복잡도를 가진다. Recently, Fan and Dai introduced a Shifted Polynomial Basis and construct a non-pipeline bit-parallel multiplier for f2ⁿ. As the name implies, the SPB is obtained by multiplying the polynomial basis 1,α,…,α<SUP>n-1</SUP> by α<SUP>-ν</SUP>. Therefore, it is easy to transform the elements PB and SPB representations. After, based on the Modified Shifted Polynomial Basis(MSPB), SPB bit-parallel Mastrovito type I and type II multipliers for all irreducible trinomials are presented. In this paper, we present a bit-parallel architecture to multiply in SPB. This multiplier have a space complexity efficient than all previously presented architecture when n≠2κ. The proposed multiplier has more efficient space complexity than the best-result when 1≤κ≤(n+1)/3. Also, when (n+2)/3≤κ<n/2, the proposed multiplier has more efficient space complexity than the best-result except for some cases.

삼항 기약다항식을 위한 효율적인 Shifted Polynomial Basis 비트-병렬 곱셈기

장남수(Nam Su Chang),김창한(Chang Han Kim),홍석희(Seokhie Hong),박영호(Young-Ho Park) 한국정보보호학회 2009 정보보호학회논문지 Vol.19 No.2

유한체 연산중에서 곱셈 연산은 중요한 연산중 하나이다. 또한, 최근에 Fan과 Dai는 이진체 곱셈기의 효율성을 개선하기 위하여 Shifted Polynomial Basis(SPB)와 이를 이용한 non-pipeline 비트-병렬 곱셈기를 제안하였다. 본 논문에서는 삼항 기약다항식 χⁿ+χ<SUP>κ</SUP>+1에 의하여 정의된 F2n 위에서의 새로운 SPB 곱셈기 type Ⅰ과 type Ⅱ를 제안한다. 제안하는 type Ⅰ 곱셈기는 기존의 SPB 곱셈기에 비하여 시간 및 공간 복잡도면에서 모두 효율적이다. 그리고 type Ⅱ 곱셈기는 제안하는 type I 곱셈기를 포함하여 기존의 모든 결과보다 작은 공간 복잡도를 가진다. 그러나 type Ⅱ 곱셈기의 시간 복잡도는 n과 κ에 따라 최대 1 xor time-delay 증가한다. Finite Field multiplication operation is one of the most important operations in the finite field arithmetic. Recently, Fan and Dai introduced a Shifted Polynomial Basis(SPB) and construct a non-pipeline bit-parallel multiplier for F2n. In this paper, we propose a new bit-parallel shifted polynomial basis type Ⅰ and type Ⅱ multipliers for F2n defined by an irreducible trinomial χⁿ+χ<SUP>κ</SUP>+1. The proposed type I multiplier has more efficient the space and time complexity than the previous ones. And, proposed type Ⅱ multiplier have a smaller space complexity than all previously SPB multiplier(include our type Ⅰ multiplier). However, the time complexity of proposed type Ⅱ is increased by 1 XOR time-delay in the worst case.

$GF(2^m)$에서 삼항 기약 다항식을 이용한 약한 쌍대 기저 기반의 효율적인 지수승기

김희석,장남수,임종인,김창한,Kim, Hee-Seok,Chang, Nam-Su,Lim, Jong-In,Kim, Chang-Han 대한전자공학회 2007 電子工學會論文誌-SD (Semiconductor and devices) Vol.44 No.8

유한체 $GF(2^m)$에서의 다항식의 지수승 연산은 암호학(Cryptography), DSP(digital signal processing), 에러 정정 코드에서 기본적인 연산으로 사용되어진다. 기존의 방법들은 지수승 연산을 병렬처리가 가능한 Right-to-Left 이진 방법으로 구성하여 연산시간을 줄이는 방법을 사용하였다. 본 논문에서는 기존의 다항식 기저에서 Right-to-Left 이진 방법으로 구성되었던 다항식의 지수승기를 약한 쌍대 기저 기반에서 삼항 기약다항식을 이용한 Left-to-Right 이진 형태로 구성한다. 제안하는 방법은 Left-to-Right는 고정된 다항식을 곱한다는 점에 착안, 사전계산을 이용하여 연산량을 감소시킨다. 본 논문에서 제안하는 방법은 제곱기(squarer)와 곱셈기(multiplier)를 모두 수행하는 시간이 기존 지수승기의 곱셈기의 연산 시간보다 같거나 작아 Left-to-Right 형태와 Right-to-Left 형태의 기존 지수승기보다 각각 기약 다항식이 $x^m+x+1$의 경우 약 17%, 10%, $x^m+x^k+1(1<k<m/2)$의 경우 약 21%, 9%, $x^m+x^{m/2}+1$의 경우 15%, 1%의 시간이 단축된다. An exponentiation in $GF(2^m)$ is a basic operation for several algorithms used in cryptography, digital signal processing, error-correction code and so on. Existing hardware implementations for the exponentiation operation organize by Right-to-Left method since a merit of parallel circuit. Our paper proposes a polynomial exponentiation structure with a trinomial that is organized by Left-to-Right method and that utilizes a weakly dual basis. The basic idea of our method is to decrease time delay using precomputation tables because one of two inputs in the Left-to-Right method is fixed. Since $T_{sqr}$ (squarer time delay) + $T_{mul}$(multiplier time delay) of ow method is smaller than $T_{mul}$ of existing methods, our method reduces time delays of existing Left-to-Right and Right-to-Left methods by each 17%, 10% for $x^m+x+1$ (irreducible polynomial), by each 21%, 9% $x^m+x^k+1(1<k<m/2)$, by each 15%, 1% for $x^m+x^{m/2}+1$.