(19) 대한민국특허청(KR) (12) 공개특허공보(A)
(11) 공개번호 10-2008-0052364 (43) 공개일자 2008년06월11일 (51) Int. Cl.
G06F 17/10 (2006.01)
(21) 출원번호 10-2007-0106211 (22) 출원일자 2007년10월22일 심사청구일자 2007년10월22일 (30) 우선권주장
1020060122606 2006년12월05일 대한민국(KR)
(71) 출원인
한국전자통신연구원
대전 유성구 가정동 161번지 (72) 발명자
한동국
인천 계양구 작전2동 772번지 타임빌라 가동 201 호
김호원
대전 유성구 신성동 210-43 102호 정교일
대전 유성구 신성동 한울아파트 107-1102 (74) 대리인
리앤목특허법인 전체 청구항 수 : 총 8 항
(54) 단순전력분석에 안전한 ＵｎｓｉｇｎｅｄＬｅｆｔ－ｔｏ－Ｒｉｇｈｔ 리코딩 방법 및 통합된 지수승알고리 즘 방법
(57) 요 약
고정된 연산 패턴을 지원하는 비밀키에 대한 부호 없는 리코딩 과정과 지수승 과정을 하나로 통합하여 리코딩 된 결과를 따로 저장하지 않고도, 단순전력분석에 안전한 Left-to-Right 리코딩을 이용한 지수승 방법이 개시되어 있다. 이진법으로 표현된 비밀키 k를 {1,2}를 이용해 Left-to-Right 방향으로 리코딩한다. 상기 리코딩 단계를 활용하여, 주어진 비밀키 k와 밑 g에 대한 지수승 gk를 계산하는 과정에서, 상기 리코딩 단계와 지수승 과정을 분리해서 처리하지 아니하고 Left-to-Right 방향으로 리코딩과정을 동시에 수행하여 지수승 결과 값을 산출한다.
대표도 - 도1
이 발명을 지원한 국가연구개발사업 과제고유번호 2005-S-088-02
부처명 정보통신부 및 정보통신연구진흥원 연구사업명 IT차세대핵심기술개발
연구과제명 안전한 RFID/USN을 위한 정보 보호 기술 개발 주관기관 한국전자통신연구원
연구기간 2005년 01월 01일 ~ 2009년 02월 28일
특허청구의 범위 청구항 1
(i) 이진법으로 표현된 비밀키 k를 {1,2}를 이용해 Left-to-Right 방향으로 리코딩하는 단계; 및
(ii) 상기 리코딩 단계를 활용하여, 주어진 비밀키 k와 밑 g에 대한 지수승 gk를 계산하는 과정에서, 상기 리코 딩 단계와 지수승 과정을 분리해서 처리하지 아니하고 Left-to-Right 방향으로 상기 리코딩 단계를 동시에 수행 하여 지수승 결과 값을 산출하는 단계를 포함하는 통합형 Left-to-Right 리코딩 및 지수승 방법.
청구항 2
제1 항에 있어서, 상기 이진법으로 표현된 비밀키 k는 이진수 (n+2)-비트 (1,0,kn-1,,k0)2 비밀키인 통합형 Left-to-Right 리코딩 및 지수승 방법.
청구항 3
제1 항에 있어서, 단계 (i)는
(i-1) kn+1 = 1, kn = 0을 만족하는 (n+2)-비트 비밀키 k를 입력하는 단계;
(i-2) 입력된 (n+2)-비트 정보에서 kz = 0을 만족하는 최하위 비트의 인텍스 값을 z에 대입하고, j값에는 n을 대입하는 단계;
(i-3) 상기 인텍스 값 j와 kj의 값에 따라서, ej를 1 또는 2에 설정하는 단계;
(i-4) 상기 j를 j-1로 갱신하고 상기 j값을 하나씩 차감하는 단계;
(i-5) 상기 j값이 0보다 작은 지를 판단하는 단계;
(i-6) 상기 j값이 -1이 될 때까지 단계 (i-3) 내지 (i-4)를 반복 수행하는 단계;
(i-7) 상기 j값이 -1이 되면, (en,,e1,e0)를 출력하는 단계를 포함하는 Left-to-Right 리코딩을 이용한 지수승 방법.
청구항 4
제3 항에서, 단계 (i-3)에서, j > z 이고 kj = 0이면, ej = 1로 설정하고, j > z 이고 kj ≠ 0이면, ej = 2로 설 정하고, j = z 이면 ej = 2로 설정하고, j < z 이면 ej = 1로 설정하는 Left-to-Right 리코딩을 이용한 지수승 방법.
청구항 5
제1 항에 있어서, 단계 (ii)는 상기 이진법으로 표현된 비밀키 k와 밑 g 에 대한 지수승 gk의 계산을 리코딩 과 정과 통합된 방식으로 Left-to-Right 방향으로 수행하는 Left-to-Right 리코딩을 이용한 지수승 방법.
청구항 6
제1 항에 있어서, 단계 (ii)는
(ii-1) (n+2)-비트 비밀키 k, (1,0,kn-1,,k0)2, 와 밑 g값을 입력받는 단계;
(ii-5) 상기 j 값을 j-1로 갱신하여 j값을 하나씩 차감하는 단계;
(ii-6) 상기 j값이 0보다 작은 지를 판단하는 단계;
(ii-7) 상기 j값이 -1이 될 때까지 단계 (ii-4) 내지 (ii-6)를 반복 수행하는 단계;
(ii-8) 상기 j값이 -1이 되면, c = gk를 출력하는 단계를 포함하는 Left-to-Right 리코딩을 이용한 지수승 방법.
청구항 7
제6 항에 있어서, 단계 (ii-4)에서, j > z 이고 kj = 0이면, c*g[1]을 c에 갱신하고, j > z 이고 kj ≠ 0이면, c*g[2]을 c에 갱신하고, j = z 이면 c*g[2]을 c에 갱신하고, j < z 이면 c*g[1]을 c에 갱신하는 단계를 포함하 는 Left-to-Right 리코딩을 이용한 지수승 방법.
청구항 8
제1 항에 있어서,
n-비트로 표현된 비밀키 k = (kn-1,,k1,k0)2 를 (1,0,kn-1,,k0)2의 형태로 변환하는 단계를 더 포함하는 Left-to- Right 리코딩을 이용한 지수승 방법.
명 세 서
발명의 상세한 설명 기 술 분 야
본 발명은 RSA 암호시스템 및 전자서명 DSA에 관한 것으로, 더욱 상세하게는 이진법으로 표현된 비밀키를 부채
<1>
널 공격에 안전한 고정된 패턴의 연산이 수행되도록 리코딩하는 방법들과 이 방법을 지수승 알고리즘에 적용할 경우 리코딩 과정과 스칼라 곱셈 과정을 동시에 수행하는 Left-to-Right 지수승 방법에 관한 것이다.
본 발명은 정보통신부 및 정보통신연구진흥원의 IT차세대핵심기술개발사업의 일환으로 수행한 연구로부터 도출
<2>
된 것이다[과제관리번호: 2005-S-088-02, 과제명: 안전한 RFID/USN을 위한 정보보호 기술 개발].
배 경 기 술
대표적인 공개키 암호 시스템과 응용 프로토콜은 RSA와 전자서명 DSA이다. 이 두 시스템에서 비밀키가 사용되어
<3>
서 이루어지는 공통적인 연산은 지수승 연산으로 키 k와 밑 g에 대해 gk를 계산하는 것이다. 대표적인 지수승 알 고리즘은 다음과 같다.
표 1
이진 Left-to-Right 방법
<4>
입력:
출력: gk 1. Q[0] ← g.
2. For i = n-2 to 0 by -1 do:
2.1 Q[0] = (Q[0])2.
2.2 if ki = 1 then Q[0]= Q[0]ㆍg.
3. Return Q[0].
표 2
이진 Right-to-Left 방법
<5>
입력:
출력 gk
1. Q[0] ← g, Q[1] ← 1.
2. For i = 0 to n-1 by 1 do:
2.1 if ki = 1 then Q[1] ← Q[0]ㆍ Q[1]
2.2 Q[0] ← (Q[0])2.
3. Return Q[1].
계산 능력이나 메모리 같은 자원이 제한된 환경(예를 들면, 스마트 카드, 모바일 폰, 센서 노드)에서 지수승
<6>
연산을 구현하기 위해서 효율성을 증대시키기 위한 많은 방법들이 제안되었다. 그러나 이러한 제한된 환경에서 암호 알고리즘을 구동하는 장비에서 발생되는 다양한 부가정보를 활용해 내부에 숨겨진 비밀 정보를 알아내는 부채널 공격(Side Channel Attacks)이 가능하다. 부채널 공격 중 전력분석 공격은 크게 단순전력분석 (SPA)과 차분전력분석(DPA)으로 구분되며, SPA는 전력소모량의 통계적인 분석 없이 전력소모량으로부터 직접적으로 비 밀 정보를 찾아낼 수 있기 때문에 간단하면서도 쉬운 공격이다. DPA는 여러 개의 전력 소모량의 표본으로부터 비밀 정보와 전력 소모량의 상관관계를 찾기 때문에 SPA에 안전하게 만들어진 암호 시스템의 공격에도 사용할 수 있다. 비밀키가 사용되는 환경에 따라서는, 예를 들어 DPA의 경우, SPA에만 안전하게 대응방법이 고려되어 지면된다. 그리고 DPA 까지 고려해야 하는 환경에서 만약 SPA에 대한 대응법을 고려하지 않는다면 DPA 대응법 은 큰 의미를 갖지 못하게 된다. 따라서 비밀키가 적용되는 어떤 환경에 대해서도 SPA에 대한 대응법은 반드시 고려되어 져야 한다.
일반적으로 곱셈 연산과 제곱 연산을 계산할 때 소모되는 전력의 차이가 발생하고 이런 정보를 이용하여 지수승
<7>
에서 사용된 키를 찾는 것이 가능하다. 앞에서 설명한 두개의 지수승 알고리즘 방법들도 비밀키 k의 각 비트 (또는 digit)에 의존하여 곱셈 연산이 선택적으로 수행되도록 하는 조건 분기 문이 포함되어 있다. 따라서 곱셈 의 전력 소모량이 관찰되어지는 비트가 0인지 아닌지에 의존하여 다르게 나타나므로 SPA에 취약함을 알 수 있다.
SPA의 대응 방법 중 스칼라를 새로운 표현 방법으로 리코딩하여, 일정한 연산 패턴이 나타나도록 하는 방법이
<8>
있다. 예를 들어, 타원곡선 암호시스템에서는 고정된 연산패턴을 만들어 내기 위하여 부호가 있는 리코딩 기법 을 도입한다. 즉, 이진수로 표현된 비밀키를 1,-1만을 이용해 표현하면, 항상 타원곡선 위의 점에 대한 두배하 는 연산과 더하기 연산 또는 빼기 연산이 고정적으로 일어난다. 이때, 타원곡선 위에서의 연산의 특성상, 더하 기 연산과 빼기 연산은 거의 구분이 불가능 할 정도의 연산 차이가 있기 때문에 SPA 공격에 안전하게 된다. 하 지만, RSA 와 DSA 와 같은 환경에서는 역원 계산이 많은 연산을 요구하는 함수이기 때문에 타원곡선 암호에서 사용되었던 부호있는 리코딩기법을 SPA 대응법으로 활용하기 힘들다. 따라서, RSA와 DSA 와 같은 환경에서는 고 정된 연산 패턴을 만들어 내는 부호없는 리코딩 기법이 필요하다.
최근에 SPA의 대응 방법으로 Vuillaume-Okeya이 리코딩 방법을 제안하였다. 이 방법은 역원 연산의 비용이 큰
<9>
RSA와 DSA 같은 시스템에서 효율적으로 구성 될 수 있게 부호가 없는 스칼라로 변형하는 리코딩 방법이다. 이 방법은 Moller가 제안한 리코딩 방법을 부호가 없는 방법으로 확장하여 윈도우 크기가 w일 경우 부호가 없는 디 짓 셋(digit set)인 1,2,,2w를 이용해 비밀키를 표현하는 것이다. 이 방법은 리코딩 된 값의 비트 길이가 고정
딩 방법을 사용할 경우 Left-to-Right 방향 지수승 연산되는 방법에 적용하기 위해서는 리코딩이 먼저 선행된 후에 스칼라 곱셈이 실행될 수밖에 없다. 바꾸어 말하면, 리코딩 된 값을 저장할 추가 공간이 (즉, O(n)-size RAM) 필요하다는 것이다. 여기서 n은 키의 비트 길이이다. 하지만, 리코딩이 좌-투-우 방향으로 이루어진다면, 리코딩된 결과 값을 따로 저장하지 않고도 리코딩 알고리즘과 지수승 알고리즘이 하나로 통합될 수 있어서 효율 적인 지수승 알고리즘을 얻게 된다. 따라서 Left-to-Right 리코딩을 설계하는 것은 메모리 제약을 받는 다양한 환경에 적합하게 구성될 수 있다.
발명의 내용
해결 하고자하는 과제
본 발명은 이와 같이 종래의 제품의 문제점을 해결하기 위한 것으로, 그 목적은 고정된 연산 패턴을 지원하는
<11>
비밀키에 대한 부호 없는 리코딩 과정과 지수승 과정을 하나로 통합하여 리코딩 된 결과를 따로 저장하지 않고 도, 단순전력분석에 안전한 Left-to-Right 리코딩을 이용한 지수승 방법을 제공함에 있다.
과제 해결수단
상기 목적을 달성하기 위하여, 본 발명에 따른 Left-to-Right 리코딩을 이용한 지수승 방법(i) 이진법으로 표현
<12>
된 비밀키 k를 {1,2}를 이용해 Left-to-Right 방향으로 리코딩하는 단계; 및 (ii) 상기 리코딩 단계를 활용하여, 주어진 비밀키 k와 밑 g에 대한 지수승 gk를 계산하는 과정에서, 상기 리코딩 단계와 지수승 과정을 분리해서 처리하지 아니하고 Left-to-Right 방향으로 상기 리코딩 단계를 동시에 수행하여 지수승 결과 값을 산 출하는 단계를 포함하는 것을 특징으로 한다.
바람직하게는, 단계 (i)는 (i-1) kn+1 = 1, kn = 0을 만족하는 (n+2)-비트 비밀키 k를 입력하는 단계; (i-2) 입
<13>
력된 (n+2)-비트 정보에서 kz = 0을 만족하는 최하위 비트의 인텍스 값을 z에 대입하고, j값에는 n을 대입하는 단계; (i-3) 상기 인텍스 값 j와 kj의 값에 따라서, ej를 1 또는 2에 설정하는 단계; (i-4) 상기 j 값을 j-1로 갱신하고 상기 j값을 하나씩 차감하는 단계; (i-5) 상기 j값이 0보다 작은 지를 판단하는 단계; (i-6) 상기 j값 이 -1이 될 때까지 단계 (i-3) 내지 (i-4)를 반복 수행하는 단계; (i-7) 상기 j값이 -1이 되면, (en,,e1,e0)를 출력하는 단계를 포함한다. 더욱 바람직하게는, 단계 (ii)는 (ii-1) (n+2)-비트 비밀키 k, (1,0,kn-1,,k0)2, 와 밑 g값을 입력받는 단계; (ii-2) g[1] = g, g[2] = g2, 그리고 c = g대입하고, kz = 0을 만족하는 최하위 비트 의 인텍스 값을 z에 대입하는 단계; (ii-3) j값에는 n를 대입하고, c 에 c2값을 대입하는 단계; (ii-4) 인텍스 j와 kj 의 값에 따라서, c*g[1] 또는 c*g[2]을 c에 갱신하는 단계; (ii-5) 상기 j 값을 j-1로 갱신하여 j값을 하나씩 차감하는 단계; (ii-6) 상기 j값이 0보다 작은 지를 판단하는 단계; (ii-7) 상기 j값이 -1이 될 때까지 단계 (ii-4) 내지 (ii-6)를 반복 수행하는 단계; (ii-8) 상기 j값이 -1이 되면, c = gk를 출력하는 단계를 포함 한다.
효 과
본 발명은 단순 전력 분석에 안전하면서, 비밀키의 리코딩과 지수승 연산을 동시에 수행할 수 있도록 설계된
<14>
방법으로 메모리의 제약을 받는 환경, 예를 들면 스마트 카드, 센서 노드, RFID 칩 등에 적합한 것으로, 메모 리의 제약을 받는 환경에서 RSA 또는 DSA 암호 시스템을 부채널 공격에 안전하면서 메모리의 사용을 최대한 줄 일 수 있다.
발명의 실시를 위한 구체적인 내용
이하, 첨부된 도면에 의하여 본 발명의 바람직한 실시 예를 상세하게 설명한다.
<15>
먼저, 2진법으로 표현된 (n+2)-비트 비밀키 (1,0,kn-1,,k0)2를 {1,2}의 원소를 이용해 (n+1)-비트로 Left-to-
<16>
Right 리코딩하는 과정을 도 1을 참조하여 설명한다.
임의의 n-비트로 표현된 비밀키 k = (kn-1,,k1,k0)2 를 (1,0,kn-1,,k0)2의 형태로 먼저 변환한다. RSA의 경우 비밀
<17>
키 k 대신에 k+rΦ(N)을 이용한다. 이때 Φ는 오일러 파이(Phi) 함수이고 r은 랜덤 한 값, 그리고 N은 RSA에서
사용하는 모듈러 값인 두 소수의 곱이다. Φ(N)을 k에 더하는 과정을 반복하면 k < Φ(N) < 2N 이 성립하므로 n 비트의 k의 경우 kn+1 = 1, kn = 0 을 항상 만족한다. 그리고 gk+rΦ(N) = gk mod N 이 성립하기 때문에 스칼라 길 이가 확장된 스칼라를 이용하여 계산하더라도 기존의 값의 결과와 같게 된다. 본 발명에서는 이와 같은 방법으 로 얻어진 (n+2)-비트 (1,0,kn-1,,k0)2를 {1,2}의 원소를 이용해 (n+1)-비트로 Left-to-Right 리코딩하는 과정을 수행한다.
도 1은 본 발명의 실시 예에 따른 (n+2)-비트 (1,0,kn-1,,k0)2를 입력할 경우, 1,2의 원소를 이용해 (n+1)-비트
<18>
로 Left-to-Right 리코딩하는 과정을 나타내는 흐름도이다. 본 발명의 중심되는 아이디어는 다음의 수학식 1로 부터 도출되었다. 입력값의 가정에서 처럼, kn+1 = 0, kn = 0이다. 그리고, z 는 k 을 이진수로 표현했을 경우 kz
= 0이 되는 최하위 비트의 인텍스 값으로 정의하자. 그럼, 다음과 같은 수학식 1을 얻을 수 있다.
수학식 1
<19>
수학식 1에서 알 수 있듯이, (n+2)-비트로 표현된 이진수 표현을 1,2의 원소들을 가지고 (n+1)-비트로 표현이
<20>
가능함을 알 수 있다.
도 1을 참조하면, kn+1 = 1, kn = 0을 만족하는 (n+2)-비트 비밀키 k를 입력한다(단계 S110). 입력된 (n+2)-비트
<21>
정보에서 kz = 0을 만족하는 최하위 비트의 인텍스 값을 z에 대입한다(단계 S115). j값에는 n을 대입한다 (S120). 단계 S125에서 j > z인 지의 여부를 판단한다.
단계 S125의 판단 결과 j > z인 경우, kj = 0인 지의 여부를 판단한다(단계 S130). 단계 S130의 판단 결과 kj =
<22>
0인 경우 ej = 1로 대입한다(S140). 즉 j > z이고 kj = 0이면 ej = 1이다.
단계 S130의 판단에서 kj ≠ 0이면 ej = 2(단계 S145)가 되게 한다. 단계 S125의 판단 결과 j≤z인 경우, j = z
<23>
인 지의 여부를 판단한다(단계 S135).
단계 S135의 판단 결과, j = z이면, ej = 2(단계 S150), 그렇지 않으면 ej = 1(S155)로 대입한다. 이어서, j를
<24>
j-1로 갱신하여 j값을 하나씩 차감하며(단계 S160), j값이 0보다 작은지를 판단한다(S165), j값이 -1이 될 때까 지 단계 S125으로 회귀하여 루프를 반복한다. j값이 -1이 되면, (en,,e1,e0) 를 출력한다(단계 S170).
이하, 2진법으로 표현된 비밀키 k와 밑 g에 대한 지수승 gk의 계산을 리코딩 과정과 통합된 방식으로 Left-to-
<25>
Right 방향으로 수행하는 알고리즘을 도 2를 참조하여 설명한다.
앞으로 살펴 볼 도면 2에서는 기존의 Left-to-Right 스칼라 곱셈 알고리즘과 도면 1에서 제안된 Left-to-Right
<26>
리코딩을 통합하여 동시에 수행하는 알고리즘을 설명한다.
도 2 는 본 발명의 실시 예에 따른 이진법으로 표현된 비밀키 k와 밑 g 에 대한 지수승 gk의 계산을 리코딩 과
<27>
정과 통합된 방식으로 Left-to-Right 방향으로 수행하는 알고리즘의 일 예를 나타내는 흐름도이다. 이 방법을 단순전력분석 공격에 안전한 통합된 이진법 Left-to-Right 지수승 알고리즘(SPA-resistant Unified binary Left-to-Right Exponentiation Algorithm)이라 한다.
단한다(단계 S235).
단계 S235의 판단 결과 kj = 0인 경우, 즉 j > z이고 kj = 0이면 c 에 c*g[1]을 대입하고(S245), 만약 kj ≠ 0
<30>
이면 c*g[2]를 c 에 대입한다(S250). 단계 S230의 판단 결과 j≤z인 경우 j = z인 지를 판단한다(단계 S240).
단계 S240의 판단 결과, j = z이면, c*g[2]를 c 에 대입하고 (S225), 그렇지 않으면 c*g[1]를 c 에 대입한다
<31>
(S260).
이어서, j를 j-1로 갱신하여(S265) j값을 하나씩 차감하며, j값이 0보다 작은지를 판단한다(단계S270).
<32>
j값이 -1이 될 때까지 단계 S225으로 회귀하여 루프를 반복한다. j값이 -1이 되면, c를 출력한다(단계 S275).
<33>
도면의 간단한 설명
도 1은 본 발명에 따른 2진법으로 표현된 (n+2)-bit 비밀키를 {1,2}의 원소를 이용해 (n+1)-bit으로 Left-to-
<34>
Right 리코딩하는 과정을 나타내는 흐름도이다.
도 2는 본 발명에 따른 2진법으로 표현된 비밀키 k와 밑 g에 대한 지수승 gk의 계산을 리코딩 과정과 통합된 방
<35>
식으로 Left-to-Right 방향으로 수행하는 알고리즘의 일 예를 나타내는 흐름도이다.
도면 도면1
도면2
