이진 필드 ECC에서 랜덤 포인트 표현을 이용하여 파워해독의 복잡도를 증가시키기 위한 암호화 방법 및 장치(Method and apparatus to increase complexity of poweranalysis based on random point representation in binaryfi..

(19) 대한민국특허청(KR)
(12) 등록특허공보(B1)
(45) 공고일자 2009년03월31일
(11) 등록번호 10-0891323
(24) 등록일자 2009년03월25일
(51) Int. Cl.

H04L 9/30 (2006.01) H04L 9/08 (2006.01)
H04L 9/32 (2006.01)
(21) 출원번호 10-2005-0039095
(22) 출원일자 2005년05월11일
심사청구일자 2007년04월17일
(65) 공개번호 10-2006-0116612
(43) 공개일자 2006년11월15일
(56) 선행기술조사문헌
JP2005055488 A
JP2003098962 A
(73) 특허권자
삼성전자주식회사
경기도 수원시 영통구 매탄동 416
(72) 발명자
바실조프 이고르
경기도 수원시 영통구 영통동 신나무실5단지아파
트 524동 1205호
손희관
경기 수원시 영통구 망포동 동수원엘지빌리지1차
114동 1601호
백유진
경기 용인시 죽전동 새터마을 현대홈타운아파트
723동 704호
(74) 대리인
리앤목특허법인, 이해영
전체 청구항 수 : 총 10 항 심사관 : 성인구
(54) 이진 필드 ＥＣＣ에서 랜덤 포인트 표현을 이용하여 파워해독의 복잡도를 증가시키기 위한 암호화 방법 및
장치
(57) 요 약
이진 필드 ECC에서 랜덤 포인트 표현을 이용하여 파워 해독의 복잡도를 증가시키기 위한 암호화 방법 및 장치가
개시된다. 상기 암호화 방법 및 장치는, 스칼라 곱 계산 과정 중에 랜덤화율, 랜덤 위치 값, 랜덤 선택 값에 따
라 다수 라운드에 걸쳐 랜덤하게 포인트 표현을 변경하여 이진 필드 ECC를 수행하므로, DPA에 강력한 대응책으로
제시될 수 있다. 랜덤 포인트 표현에 있어서, "Affine", "Ordinary Projective", "Jacobian Projective" 및
"Lopez-Dahab Projective"가 사용될 수 있다.
대 표 도 - 도2
- 1 -
등록특허 10-0891323
특허청구의 범위
청구항 1
입력 포인트 및 랜덤화율을 수신하는 단계;
상기 랜덤화율로부터 랜덤 선택 값 및 랜덤 위치 값을 생성하는 단계;
상기 입력 포인트 또는 다수 라운드들에 걸친 EC 연산에 의한 암호화된 포인트들 중 상기 랜덤화율 및 상기 랜
덤 위치 값에 따라 랜덤하게 적어도 하나를 선택하는 단계;
상기 선택된 포인트를 상기 랜덤 선택 값이 지시하는 포인트 표현으로 변환하는 단계; 및
상기 변환이 이루어지지 않은 포인트 또는 랜덤하게 이루어지는 상기 변환에 따라 변경된 포인트 중 어느 하나
를 다음 라운드에 적용하여, 상기 입력 포인트와 비밀 키로부터 상기 다수 라운드들에 걸친 상기 EC 연산의 수
행으로 최종 암호화된 출력 포인트를 생성하는 단계를 구비하는 것을 특징으로 하는 암호화 방법.
청구항 2
청구항 2은(는) 설정등록료 납부시 포기되었습니다.
제 1항에 있어서, 상기 선택 단계는,
상기 다수 라운드들 각각의 전후에서 상기 랜덤화율 및 상기 랜덤 위치 값을 비교하는 단계;
상기 비교 결과에 따라 포인트 표현을 변경할 것인지를 결정하는 단계; 및
상기 결정에 따라 해당 라운드 전 또는 후의 포인트를 선택하는 단계를 포함하는 것을 특징으로 하는 암호화 방
법.
청구항 3
청구항 3은(는) 설정등록료 납부시 포기되었습니다.
제 2항에 있어서, 상기 랜덤화율은,
유저에 의하여 0 내지 100 %까지 설정되는 것을 특징으로 하는 암호화 방법.
청구항 4
청구항 4은(는) 설정등록료 납부시 포기되었습니다.
제 3항에 있어서, 상기 랜덤 위치 값은,
상기 랜덤화율의 범위 내에서 랜덤하게 생성되는 것을 특징으로 하는 암호화 방법.
청구항 5
청구항 5은(는) 설정등록료 납부시 포기되었습니다.
제 4항에 있어서, 상기 랜덤 선택 값은,
다수의 포인트 표현들 중 어느 하나를 랜덤하게 지시하는 것을 특징으로 하는 암호화 방법.
청구항 6
청구항 6은(는) 설정등록료 납부시 포기되었습니다.
제 1항에 있어서, 상기 포인트 표현은,
"Affine", "Ordinary Projective", "Jacobian Projective" 및 "Lopez-Dahab Projective" 중 어느 하나인 것을
특징으로 하는 암호화 방법.
청구항 7
- 2 -
등록특허 10-0891323
청구항 7은(는) 설정등록료 납부시 포기되었습니다.
제 1항에 있어서, 상기 EC 연산은,
이진 필드에서 이루어지는 것을 특징으로 하는 암호화 방법.
청구항 8
청구항 8은(는) 설정등록료 납부시 포기되었습니다.
제 1항에 있어서, 상기 EC 연산은,
청구항 9
제 1항에 있어서, 상기 포인트 표현 변환은,
각 라운드에서 독립적인 하드웨어에 의하여 이루어지는 것을 특징으로 하는 암호화 방법.
청구항 10
제 1항에 있어서, 상기 포인트 표현 변환은,
각 라운드에서 공유되는 하나의 하드웨어에 의하여 이루어지는 것을 특징으로 하는 암호화 방법.
청구항 11
입력 포인트 또는 다수 라운드들에 걸친 EC 연산에 의한 암호화된 포인트들 중 랜덤화율 및 랜덤 위치 값에 따
라 랜덤하게 적어도 하나를 선택하고, 상기 선택된 포인트의 표현이 변경된 포인트를 다음 라운드에 적용하여,
상기 입력 포인트와 비밀 키로부터 상기 다수 라운드들에 걸친 상기 EC 연산의 수행으로 최종 암호화된 출력 포
인트를 생성하는 스칼라 곱 유니트;
상기 랜덤화율로부터 랜덤 선택 값 및 상기 랜덤 위치 값을 생성하는 난수 발생기; 및
상기 선택된 포인트를 상기 랜덤 선택 값이 지시하는 포인트 표현으로 변환하여 상기 변경된 포인트를 생성하는
포인트 표현 변환부를 구비하는 것을 특징으로 하는 암호화 장치.
청구항 12
제 11항에 있어서, 상기 스칼라 곱 유니트는,
상기 다수 라운드들 각각의 전후에서 상기 랜덤화율 및 상기 랜덤 위치 값을 비교하여, 포인트 표현을 변경할
것인지를 결정하고, 상기 결정에 따라 해당 라운드 전 또는 후의 포인트를 선택하여 상기 포인트 표현 변환부로
출력하는 것을 특징으로 하는 암호화 장치.
청구항 13
청구항 13은(는) 설정등록료 납부시 포기되었습니다.
제 12항에 있어서, 상기 랜덤화율은,
유저에 의하여 0 내지 100 %까지 설정되는 것을 특징으로 하는 암호화 장치.
청구항 14
청구항 14은(는) 설정등록료 납부시 포기되었습니다.
제 13항에 있어서, 상기 난수 발생기는,
상기 랜덤화율의 범위 내에서 랜덤하게 상기 랜덤 위치 값을 생성하는 것을 특징으로 하는 암호화 장치.
청구항 15
청구항 15은(는) 설정등록료 납부시 포기되었습니다.
제 14항에 있어서, 상기 난수 발생기는,
- 3 -
등록특허 10-0891323
다수의 포인트 표현들 중 어느 하나를 랜덤하게 지시하는 상기 랜덤 선택 값을 생성하는 것을 특징으로 하는 암
호화 장치.
청구항 16
제 11항에 있어서, 상기 포인트 표현은,
"Affine", "Ordinary Projective", "Jacobian Projective" 및 "Lopez-Dahab Projective" 중 어느 하나인 것을
특징으로 하는 암호화 장치.
청구항 17
제 11항에 있어서, 상기 EC 연산은,
이진 필드에서 이루어지는 것을 특징으로 하는 암호화 장치.
청구항 18
제 11항에 있어서, 상기 EC 연산은,
소수 유한 필드에서 이루어지는 것을 특징으로 하는 암호화 장치.
청구항 19
각 라운드에서 입력되는 포인트와 비밀 키로부터 EC 연산을 수행하는 EC 연산기가 다수개로 구성된 EC
연산기들;
각각이 상기 EC 연산기들 전후에 위치하여, 입력 포인트 또는 상기 EC 연산에 의한 암호화된 포인트들 중 적어
도 하나를 랜덤화율 및 랜덤 위치 값에 따라 랜덤하게 선택하고, 상기 선택된 포인트를 상기 랜덤 선택 값이 지
시하는 포인트 표현으로 변환하여 상기 변환된 포인트를 다음 라운드의 EC 연산기에 출력하는 다수의 포인트 표
현 변환기들; 및
상기 랜덤화율로부터 상기 랜덤 위치 값 및 상기 랜덤 선택 값을 생성하는 난수 발생기를 구비하는 것을 특징으
로 하는 암호화 장치.
청구항 20
제 19항에 있어서, 상기 다수의 포인트 표현 변환기들 각각은,
상기 랜덤화율 및 상기 랜덤 위치 값을 비교하여, 포인트 표현을 변경할 것인지를 결정하고, 상기 결정에 따라
해당 라운드 전 또는 후의 포인트를 선택하는 것을 특징으로 하는 암호화 장치.
명 세 서
발명의 상세한 설명
발명의 목적
발명이 속하는 기술 및 그 분야의 종래기술
본 발명은 하드웨어 암호화 장치(cryptographic apparatus)에 관한 것으로, 특히 이진 필드(binary field)<6>
ECC(Elliptic Curve Cryptography:타원 곡선 암호화)에서 파워 해독의 복잡도를 증가시키기 위한 암호화 방법
및 장치에 관한 것이다.
현대의 기밀(confidential) 데이터 통신의 문제를 해결하기 위하여, 잘 알려져 있는 암호화 알고리즘에 기반한<7>
하드웨어 암호화 시스템들이 널리 사용되고 있고, 계속적인 성능 향상 요구를 만족시키도록 하고 있다. 암호화
알고리즘으로서, RSA, ECC등과 같은 공개키 알고리즘 뿐만 아니라 DES(Data Encryption Standard),
AES(Advanced Encryption Standard)와 같은 대칭키 알고리즘이 잘 알려져 있다.
그러나, 하드웨어-중심적인 암호화 시스템의 개발과 함께, SCA(Side-Channel Analysis)와 같은 새로운 암호-해<8>
독 방법들도 나타났다. 이러한 공격(attack) 방법들에는 많은 다양한 기술들이 나타나고 있으나, 가장 일반적인
- 4 -
등록특허 10-0891323
것으로는, 타이밍 해독(Timing Analysis), 파워 해독(Power Analysis), 전자기 해독(Electro-Magnetic
Analysis) 및 오류 해독(Different Fault Analysis:DFA) 등이 있다. 이와 같은 방법들은 암호화 시스템에 성공
적으로 공격하여 적은 시간과 노력으로 비밀 키(secrete key)를 획득할 수 있는 것으로 알려져 있다.
따라서, 위와 같은 SCA에 대책을 위한 개발들이 향후 중요한 과제이다. 그러나, ECC는 상대적으로 새로운 방법<9>
의 암호화 기술로서, 이를 적용하는 데이터 보호 시스템에 SCA에 대책을 마련한 논문이나 특허가 아직 미흡한
실정이다.
특히, SCA 중 하나인 DPA(Differential Power Analysis)에서는 비밀 키에 대한 정보를 얻기 위하여 스칼라 곱<10>
계산 동안의 파워 트랙(track)을 해독한다. 이러한 DPA에 의한 정보의 누설을 방지하기 위하여, 비밀 지수의 랜
덤화(randomization of secret exponent)를 기반으로 한 대책 기술이 알려져 있다. 그러나, 이와 같은 방법도
아직 특별한 선택-메시지 파워 해독 공격(special chosen-message Power Analysis attack)에 취약하다. 이에
대비하기 위하여, 잘 알려진 입력 메시지의 랜덤화(randomization of input messages)가 적용될 수 있다.
도 1은 종래의 스칼라 곱 과정을 나타내는 도면이다. 도 1을 참조하면, 종래의 암호화 시스템에서는, 입력 포인<11>
트를 수신한 후(S11), 먼저 포인트 표현을 선택하고 변경한다(S12). 예를 들어, 입력 포인트가 "Affine" 표현으
로 된 경우에 "Projective" 표현으로 변경한 후, 해당 포인트 표현에서 스칼라 곱이 계산된다(S13). 잘 알려져
있는 바와 같이, ECC 알고리즘에 따라 비밀 키와 입력 포인트에 대한 스칼라 곱 계산에 따라, 암호화된 포인트
가 생성된다. 이와 같은 스칼라 곱 계산은 시스템 사양에 맞게 다수 라운드(round) 반복(iteration)될 수 있다.
스칼라 곱 계산이 완료되면, 암호화된 포인트는 다시 다른 포인트 표현(예를 들어, "Affine" 표현)으로 변경된
다(S14). 암호화된 포인트가 본래의 포인트 표현으로 변경된 출력 포인트는 서명이나 인증(sign/verification)
등을 위한 후속 프로세서로 전달된다.
이와 같이 DPA 공격에 대비한 종래의 암호화 시스템에서, 비밀키나 입력 포인트를 마스킹(masking)하는 방법이<12>
사용될 수 있다. 그러나, 이와 같은 종래의 암호화 시스템에서는, 보통 병렬적으로 다수 라운드에 걸친 복잡한
스칼라 곱 계산이 반복적으로(duplication) 이루어지므로, 비용 뿐만아니라 상당한 성능 저하가 문제이며, 이
로 인하여 실제 수많은 응용에서 사용되기에 부적합하다는 문제점이 있다.
발명이 이루고자 하는 기술적 과제
따라서, 본 발명이 이루고자하는 기술적 과제는, 파워 트랙으로부터 유용한 정보가 누설되는 것을 최소화하기<13>
위하여, 랜덤 포인트 표현을 이용하여 파워 트랙의 엔트로피를 증가시킴으로써, 파워 해독 공격의 효율성을 떨
어뜨릴 수 있는 암호화 방법을 제공하는 데 있다.
본 발명이 이루고자하는 다른 기술적 과제는, 상기 암호화 방법을 하드웨어로 구현하기 위한 암호화 장치를 제<14>
공하는 데 있다.
발명의 구성 및 작용
상기의 기술적 과제를 달성하기 위한 본 발명의 일면에 따른 암호화 방법은, 입력 포인트 및 랜덤화율을 수신하<15>
는 단계; 상기 랜덤화율로부터 랜덤 선택 값 및 랜덤 위치 값을 생성하는 단계; 상기 입력 포인트 또는 다수 라
운드들에 걸친 EC 연산에 의한 암호화된 포인트들 중 상기 랜덤화율 및 상기 랜덤 위치 값에 따라 랜덤하게 적
어도 하나를 선택하는 단계; 상기 선택된 포인트를 상기 랜덤 선택 값이 지시하는 포인트 표현으로 변환하는 단
계; 및 상기 변환이 이루어지지 않은 포인트 또는 랜덤하게 이루어지는 상기 변환에 따라 변경된 포인트 중 어
느 하나를 다음 라운드에 적용하여, 상기 입력 포인트와 비밀 키로부터 상기 다수 라운드들에 걸친 상기 EC 연
산의 수행으로 최종 암호화된 출력 포인트를 생성하는 단계를 구비하는 것을 특징으로 한다.
상기 선택 단계는, 상기 다수 라운드들 각각의 전후에서 상기 랜덤화율 및 상기 랜덤 위치 값을 비교하는 단계;<16>
상기 비교 결과에 따라 포인트 표현을 변경할 것인지를 결정하는 단계; 및 상기 결정에 따라 해당 라운드 전 또
는 후의 포인트를 선택하는 단계를 포함하는 것을 특징으로 한다.
상기의 기술적 과제를 달성하기 위한 본 발명의 다른 일면에 따른 암호화 장치는, 스칼라 곱 유니트, 난수 발생<17>
기, 및 포인트 표현 변환부를 구비하는 것을 특징으로 한다. 상기 스칼라 곱 유니트는 입력 포인트 또는 다수
라운드들에 걸친 EC 연산에 의한 암호화된 포인트들 중 랜덤화율 및 랜덤 위치 값에 따라 랜덤하게 적어도 하나
를 선택하고, 상기 선택된 포인트의 표현이 변경된 포인트를 다음 라운드에 적용하여, 상기 입력 포인트와 비밀
키로부터 상기 다수 라운드들에 걸친 상기 EC 연산의 수행으로 최종 암호화된 출력 포인트를 생성한다. 상기 난
- 5 -
등록특허 10-0891323
수 발생기는 상기 랜덤화율로부터 랜덤 선택 값 및 상기 랜덤 위치 값을 생성한다. 상기 포인트 표현 변환부는
상기 선택된 포인트를 상기 랜덤 선택 값이 지시하는 포인트 표현으로 변환하여 상기 변경된 포인트를
생성한다.
상기의 기술적 과제를 달성하기 위한 본 발명의 또 다른 일면에 따른 암호화 장치는, 다수개로 구성된 EC 연산<18>
기들, 다수의 포인트 표현 변환기들 및 난수 발생기를 구비하는 것을 특징으로 한다. 상기 다수개로 구성된 EC
연산기들은 각 라운드에서 입력되는 포인트와 비밀 키로부터 EC 연산을 수행한다. 상기 다수의 포인트 표현 변
환기들은 각각이 상기 EC 연산기들 전후에 위치하여, 입력 포인트 또는 상기 EC 연산에 의한 암호화된 포인트들
중 적어도 하나를 랜덤화율 및 랜덤 위치 값에 따라 랜덤하게 선택하고, 상기 선택된 포인트를 상기 랜덤 선택
값이 지시하는 포인트 표현으로 변환하여 상기 변환된 포인트를 다음 라운드의 EC 연산기에 출력한다. 상기 난
수 발생기는 상기 랜덤화율로부터 상기 랜덤 위치 값 및 상기 랜덤 선택 값을 생성한다.
본 발명과 본 발명의 동작상의 이점 및 본 발명의 실시에 의하여 달성되는 목적을 충분히 이해하기 위해서는 본<19>
발명의 바람직한 실시예를 예시하는 첨부 도면 및 첨부 도면에 기재된 내용을 참조하여야만 한다.
이하, 첨부한 도면을 참조하여 본 발명의 바람직한 실시예를 설명함으로써, 본 발명을 상세히 설명한다. 각 도<20>
면에 제시된 동일한 참조부호는 동일한 부재를 나타낸다.
타원 곡선(EC) E는 "Weierstrass" 형태에서의 타원 곡선 방정식 [수학식 1]을 만족하는 점들 (x,y)의 집합(se<21>
t)이다.
[수학식 1]<22>
<23>
암호화 응용에서, 타원 곡선은 소수 유한 필드(prime finite field) GF(p) 또는 이진 유한 필드(binary finite<24>
field) GF(2
n
) 상에서 이용될 수 있다. GF()는 갈로아 필드(Galois Field)를 나타내고, 소수 유한 필드는 소수
개의 원소를 가지는 필드이며, 이진 유한 필드는 2
n
개의 원소를 가지는 필드이다.
본 발명은 이진 유한 필드를 기반으로 한 ECC에 대한 것이다. 그러나, 이에 한정되는 것은 아니고, 이 분야에서<25>
통상의 지식을 가진 자라면, 약간의 수정을 가하여 소수 유한 필드 ECC에도 적용가능하고, 잘 알려져 있는 어떠
한 암호화 알고리즘에도 쉽게 적용될 수 있다.
만일, n≥1일 때, 2
n
개의 원소를 가지는 유일한 필드 GF(2
n
)가 존재한다. 이진 유한 필드에 대하여, 상기 [수학<26>
식 1]은 [수학식 2]와 같이 변경될 수 있다.
[수학식 2]<27>
<28>
EC 상에서 포인트 덧셈 연산(point addition operation)과, 그 중 특정한 경우인 포인트 이배 연산(point<29>
doubling operation)이 다음과 같이 이루어진다. 예를 들어, 두 개의 포인트 P(x1,y1) 및 Q(x2, y2)에서, R = P
Q = (x3, y3)를 얻기 위하여, 이진 유한 필드 GF(2
n
) 상에서 [수학식 3]과 같은 유한 필드 연산들이
요구된다.
[수학식 3] <30>
<31>
- 6 -
등록특허 10-0891323
포인트 이배 연산인 경우(P=Q)에는, 이진 유한 필드 GF(2
n
) 상에서 [수학식 4]와 같은 유한 필드 연산들이 요구<32>
된다.
[수학식 4] <33>
<34>
한편, ECC에서의 메인(main) 연산은 Q = kㆍP = P P ... P(k times)를 계산하는 스칼라 포인트 곱<35>
(scalar point multiplication)이다. k는 비밀 키이다. 스칼라 포인트 곱은 위의 수학식들과 같이 유한 필드 연
산들을 기반으로 한 포인트 연산들, 즉, 승산(multiplication in finite field), 합산(addition in finite
field), 제곱(square in finite field)으로 이루어진다. 이와 관련된 이산 대수(discrete logarithm) 연산에서
는, P와 Q=kㆍP로부터 k를 계산한다.
한편, 위와 같은 "Affine" 표현 이외에도, 타원 곡선 상의 포인트(점)를 나타내는 여러 가지 표현들이 있다.<36>
예를 들어, "Ordinary Projective", "Jacobian Projective" 및 "Lopez-Dahab Projective" 등이다. 이들 각각은
일정 공격에 더 강하거나 더 좋은 성능을 발휘할 수 있고, 시스템에 따라서 구현 상의 용이성에 차이가 있다.
먼저, GF(2
n
) 상의 "Ordinary Projective" 좌표계에서, [수학식 1]은 [수학식 5]와 같이 변형될 수 있다. [수학<37>
식 1]과 [수학식 5] 사이의 관계는 [수학식 6]과 같이 나타낼 수 있다.
[수학식 5]<38>
Y
2
Z XYZ = X
3
aX
2
Z bZ
3
<39>
[수학식 6]<40>
<41>
GF(2
n
) 상의 "Jacobian Projective" 좌표계에서, [수학식 1]은 [수학식 7]과 같이 변형될 수 있다. [수학식 1]<42>
과 [수학식 7] 사이의 관계는 [수학식 8]과 같이 나타낼 수 있다.
[수학식 7]<43>
Y
2
XYZ = X
3
aX
2
Z
2
bZ
6
<44>
[수학식 8]<45>
<46>
GF(2
n
) 상의 "Lopez-Dahab Projective" 좌표계에서, [수학식 1]은 [수학식 9]와 같이 변형될 수 있다. [수학식<47>
1]과 [수학식 9] 사이의 관계는 [수학식 10]과 같이 나타낼 수 있다.
- 7 -
등록특허 10-0891323
[수학식 9]<48>
Y
2
XYZ = X
3
Z aX
2
Z
2
bZ
4
<49>
[수학식 10]<50>
<51>
위와 같은 타원 곡선 표현의 "Weierestrass" 형태는 암호화 응용에서 가장 널리 사용되고 있고, 쉽고 빠른 포인<52>
트 표현의 변환을 위하여 [표 1]과 같이 요약될 수 있다. [표 1]에서 A(x,y)는 "Affine" 표현, P(X,Y,Z)는
"Ordinary Projective" 표현, J(X,Y,Z)는 "Jacobian Projective" 표현, 및 L(X,Y,Z)는 "Lopez-Dahab
Projective" 표현을 나타낸다.
[표 1]<53>
<54>
이진 유한 필드의 EC 연산에서 원소의 역(inversion)은 다음과 같이 간단히 이루어진다. 즉, 승산의 개수를 최<55>
소화하여 GF(2
n
)의 원소에 대한 역산을 수행하는 방법이 알려져 있다. 예를 들어, α∈GF(2
n
),α≠0일 때, [수학
식 11]이 만족된다.
[수학식 11]<56>
<57>
[수학식 11]에서, n이 홀수라면, [수학식 12]에 따라 [수학식 13]이 만족된다. 따라서, 제곱 계산을 제외하고,<58>
이 계산되면, [수학식 11]의 역산을 위하여 한번의 승산만이 필요하다.
[수학식 12]<59>
<60>
[수학식 13]<61>
<62>
[수학식 11]에서, n이 짝수라면, [수학식 14]가 만족된다. 따라서, 이 계산되면, [수학식 11]의 역산<63>
을 위하여 두번의 승산만이 필요하다.
- 8 -
등록특허 10-0891323
[수학식 14]<64>
<65>
이와 같은 역산의 과정은 여러번(recursively) 반복된다. 이와 같은 방법에 I(n)=[log2(n-1)] ω(n-1)-1 필드<66>
승산이 요구된다는 것이 알려져 있다. ω(n-1)는 (n-1)의 이진 표현에서 1(Hemming Weight)의 갯수를 나타낸다.
한편, DPA 공격에서는 파워 트랙이, 암호화 장치가 수행하는 명령어들(instructions) 뿐만아니라 수행 과정 중<67>
의 피연산자들(operands)의 값들과 상관성(correlated)이 있다는 가설(hypothesis)에 기반을 두고 있다.
따라서, 파워 트랙의 조사(examination)로부터, 수행되고 있는 명령어들과 데이터 레지스터들의 콘텐츠에 관한
정보가 누설될 수 있다. 암호화 장치가 비밀키 암호화 연산을 실행하는 경우에 있어서는, 비밀 키가 유출될 가
능성이 있다.
SPA(Simple Power Analysis) 공격에서는, 비밀 키에 대한 정보가 단 하나의 비밀 키 연산으로부터 파워 트랙을<68>
조사함으로써 추적(deduce)될 수 있다. EC 포인트 승산 알고리즘의 구현은, 포인트 덧셈 및 이배 연산 식들이
꽤 달라서 서로 구분될 수 있는 파워 트랙들을 가지기 때문에, 특히 취약한 구조를 가진다. 실행 경로가 비밀
키 비트들에 의하여 결정되는 구현은 잠재적인(potential) 취약성을 가진다.
DPA 공격에서는, 다루어지고 있는 데이터 값들과 상관 관계가 있는 파워 소비의 변화를 이용한다. 이와 같은 변<69>
화들은 다른 명령어 시퀀스들과 연합된(associated) 것들보다 일반적으로 훨씬 작아서, 노이즈나 측정 에러에
의하여 애매해진다(obfuscated). 노이즈를 줄이고 차분적 분석(differential analysis)을 강화하기 위하여, 통
계적인 방법들이 파워 트랙들의 수집에 이용된다.
상기 SPA 공격에 대비하기 위한 많은 대책들이 있다. 그러나, 대부분의 SPA 대책들은 DPA 공격에 약하다. DPA<70>
공격은 SPA에 비하여 상대적으로 훨씬 복잡하고, 많은 파워 트랙들의 분석을 필요로 하지만, 아직도 비밀 정보
를 유출하는데 적용될 수 있다. DPA 공격의 복잡도는 요청된 파워 트랙의 수 또는 하드웨어 자원에 의한 계산에
관련된 정도(measure)이다. DPA 공격을 자동적으로 수행하는데 요구되는 시간은, 때에 따라서 수 시간 내지 몇
주일까지 걸리지만, 아직도 적절한 공격 방법으로 적용될 수 있다.
스칼라 곱 계산이, "Always double-and-add"(항시 이배와 합산의 수행)과 같은 SPA 저지 방법 및 랜덤화된<71>
"projective" 좌표계, 타원 곡선(EC), 또는 필드 표현과 같은 DPA 저지 방법으로 보호된다하더라도, 스칼라 곱
계산은 아직도 암호해독자(cryptanalyst)가 기본 포인트 표현을 선택할 수 있는 상황에서는 DPA 공격에 취약하
다.
이리하여, 공격의 복잡도를 상당한 수준으로 증가시킬 수 있는 새로운 방법을 제안한다. 본 발명에서는, 스칼라<72>
곱 계산 과정 중에 포인트 표현을 랜덤하게 변경하여 파워 트랙의 값들도 랜덤하게 바뀌도록 한다. 다수 라운드
들에 걸친 EC 연산을 수행하는 스칼라 곱 계산에서, 랜덤하게 선택되는 일부 라운드의 암호화된 포인트들이 다
른 포인트로 변환되어 처리된다.
본 발명의 일실시예에 따라 입력 포인트 P를 암호화하기 위하여 스칼라 곱을 연산하는 계산 흐름도가 도 2에 도<73>
시되어 있다. 도 2를 참조하면, 먼저, 암호화 장치(도 3/도 4)는 외부에서 입력 포인트 P와 랜덤화율 r을 수신
한다(S41). 상기 입력 포인트 P는 암호화되려는 입력 정보이고, 상기 랜덤화율 r은 스칼라 곱 계산 과정 동안에
포인트 표현의 랜덤화의 레벨을 제어하는 값이다. 상기 랜덤화율 r은 유저에 의하여 0 내지 100 %까지 설정될
수 있다. 예를 들어, 상기 랜덤화율 r이 100% 인 경우에, 다수 라운드들에 걸친 EC 연산들의 입력 및 출력 포인
트들 모두가 다른 포인트 표현으로 변경됨을 나타낸다. 예를 들어, 상기 랜덤화율 r이 60% 인 경우에는, 다수
라운드들에 걸친 EC 연산들의 입력 및 출력 포인트들 중 60% 만이 다른 포인트 표현으로 변경됨을 나타낸다. 다
른 포인트 표현으로 변경되는 위치는 랜덤하게 결정된다.
다음에 암호화 장치는 상기 수신된 입력 포인트 P를 Q0으로 설정하고(S42), 단계 S43 내지 S48과 같이, 랜덤하<74>
게 포인트 표현 변경 위치를 선택하면서 다수 라운드들에 걸친 EC 연산을 통하여 최종 암호화된 출력 포인트 Q
를 생성한다. 즉, 암호화 장치는 난수 발생기(도 3의 220)에서 생성되는 랜덤 위치 값 r1을 수신하고(S43), 상
기 랜덤화율 r과 비교한다(S44). 상기 랜덤 위치 값 r1은 각 라운드에서 상기 랜덤화율 r의 범위 내에서 랜덤하
게 생성된다. 이때, 암호화 장치는 상기 랜덤화율 r이 상기 랜덤 위치 값 r1보다 크지 않으면, 이전 라운드의
EC 연산에서 암호화된 포인트 Qi-1의 표현 변경 없이 다음 라운드의 EC 연산을 수행하여 암호화된 포인트 Qi를 생
성한다(S45). EC 연산에서는, 이전 라운드에서 암호화된 포인트 Qi-1 와 해당 비밀 키 k로부터, GF(2
n
) 상의 도메
- 9 -
등록특허 10-0891323
인 파라메터들 a,b,n을 이용하여 스칼라 곱 Qi = kㆍP(Qi-1) = P P ... P(k times)를 계산한다. 비밀 키 k
는 소정 키 생성기에서 생성되고, 도메인 파라메터들 a,b,n은 소정 보호된(protected) 비휘발성 메모리로부터
입력될 수 있다.
상기 단계 S44에서, 상기 랜덤화율 r이 상기 랜덤 위치 값 r1보다 크다면, 암호화 장치는 난수 발생기(도 3의<75>
220)에서 생성되는 랜덤 선택 값 r2를 수신하고(S46), 이전 라운드의 EC 연산에서 암호화된 포인트 Qi-1을 상기
랜덤 선택 값 r2가 지시하는 포인트 표현으로 변환하여 변경된 포인트를 생성한다(S47). 상기 랜덤 선택 값 r2
는 각 라운드에서 [표 1]과 같이 다수의 포인트 표현들 중 어느 하나를 랜덤하게 지시하도록 생성된다. 이에 따
라, 암호화 장치는 상기 포인트 표현이 변경된 포인트를 다음 라운드에 적용하여 암호화된 포인트 Qi를 생성한다
(S45).
이와 같이, 상기 S43 내지 S48 단계에 따라, 스칼라 곱 계산이 모두 끝나면, 상기 최종 암호화된 출력 포인트 Q<76>
가 상위 계층(upper layer)의 후속 프로세서(processor)로 출력된다(S49).
도 2의 암호화 방법을 실현하는 암호화 장치(200)의 일실시예가 도 3에 도시되어 있다. 도 3을 참조하면, 상기<77>
암호화 장치(200)는 스칼라 곱 유니트(210), 난수 발생기(random number generator)(220), 및 포인트 표현 변
환부(230)를 구비한다.
먼저, 상기 스칼라 곱 유니트(210)는 입력 포인트 P 및 랜덤화율 r을 수신한다(도 2의 S41). 상기 난수 발생기<78>
(220)는 상기 랜덤화율 r로부터 각 라운드마다 랜덤하게 랜덤 위치 값 r1 및 랜덤 선택 값 r2를 생성한다.
상기 스칼라 곱 유니트(210)는 상기 랜덤화율 r과 상기 랜덤 위치 값 r1을 비교하고(도 2의 S44), 상기 랜덤화<79>
율 r이 상기 랜덤 위치 값 r1보다 크면, 입력 포인트 P를 선택한다. 상기 스칼라 곱 유니트(210)에서 선택된 입
력 포인트 P는 포인트 표현의 변경을 위하여 상기 포인트 표현 변환부(230)로 출력된다. 이에 따라, 상기 포인
트 표현 변환부(230)는 상기 스칼라 곱 유니트(210)에서 선택된 입력 포인트 Qi를 상기 랜덤 선택 값 r2가 지시
하는 포인트 표현으로 변환하여 변경된 포인트 Qi'를 생성한다(도 2의 S47). 이에 따라 상기 스칼라 곱 유니트
(210)는 상기 변경된 포인트와 해당 라운드의 비밀 키로부터 EC 연산의 수행으로 암호화된 출력 포인트 Q를 생
성한다. 상기 스칼라 곱 유니트(210)는 상기 랜덤화율 r과 상기 랜덤 위치 값 r1의 비교 결과, 상기 랜덤화율 r
이 상기 랜덤 위치 값 r1보다 크지 않으면, 포인트 표현의 변경 없이 이전 라운드에서의 포인트 표현에서 EC 연
산의 수행으로 암호화된 출력 포인트를 생성한다.
마찬가지로, 상기 스칼라 곱 유니트(210)는 이전 라운드에서 암호화된 출력 포인트를 다음 라운드에서 EC 연산<80>
을 수행하기 전에, 상기 랜덤화율 r 및 상기 랜덤 위치 값 r1을 비교하여, 포인트 표현을 변경할 것인지를 결정
하고, 상기 결정에 따라 해당 라운드 전 또는 후의 포인트를 선택하여 상기 포인트 표현 변환부(230)로 출력한
다. 상기 포인트 표현 변환부(230)는 각 라운드 EC 연산 전후에서 랜덤하게 포인트 표현을 변환하기 위하여 공
유된다.
이와 같이, 상기 스칼라 곱 유니트(210)는 입력 포인트 P 또는 다수 라운드들에 걸친 EC 연산에 의한 암호화된<81>
포인트들 중 랜덤하게 적어도 하나를 선택하여, 상기 선택된 포인트의 표현이 변경된 포인트를 다음 라운드에
적용한다. 포인트 표현의 변경은 상기 입력 랜덤화율 r과 상기 난수 발생기(220)에서 각 라운드마다 생성되는
랜덤 위치 값 r1에 따라 결정되고, 변경되는 포인트 표현 종류는 상기 난수 발생기(220)에서 각 라운드마다 생
성되는 랜덤 선택 값 r2에 의하여 결정된다.
도 2의 암호화 방법을 실현하는 암호화 장치(300)의 다른 실시예가 도 4에 도시되어 있다. 도 4를 참조하면, 상<82>
기 암호화 장치(300)는 다수의 EC 연산기들(211, 212, 213,...) 및 다수의 포인트 표현 변환기들(231, 232,
233,...)을 구비하고, 이외에 도 3과 같은 난수 발생기(220)를 구비하지만 이를 도시하지 않았다. 도 3에서 포
인트 표현 변환부(230)가 공유되는 것과는 달리, 상기 암호화 장치(300)에서는 포인트 표현 변환기가 각 라운드
EC 연산의 전후에 위치한다.
먼저, 상기 암호화 장치(300)는 입력 포인트 P 및 랜덤화율 r을 수신한다(도 2의 S41). 랜덤 위치 값 r1 및 랜<83>
덤 선택 값 r2는 상기 랜덤화율 r로부터 각 라운드 마다 랜덤하게 난수 발생기에서 생성된다.
상기 다수의 포인트 표현 변환기들(231, 232, 233,...) 중 제1 포인트 표현 변환기(231)는 제1 EC 연산기<84>
(211) 앞에서, 상기 랜덤화율 r과 상기 랜덤 위치 값 r1을 비교하고(도 2의 S44), 상기 랜덤화율 r이 상기 랜덤
위치 값 r1보다 크면, 입력 포인트 P를 선택한다. 다음에, 상기 제1 포인트 표현 변환기(231)는 선택된 입력 포
- 10 -
등록특허 10-0891323
인트 P를 상기 랜덤 선택 값 r2가 지시하는 포인트 표현으로 변환하여 변경된 포인트를 생성한다(도 2의 S47).
이에 따라 제1 EC 연산기(211)는 상기 변경된 포인트와 해당 라운드의 비밀 키 K로부터 EC 연산의 수행으로 암
호화된 출력 포인트 Q1을 생성한다. 상기 제1 포인트 표현 변환기(231)는 상기 랜덤화율 r과 상기 랜덤 위치 값
r1의 비교 결과, 상기 랜덤화율 r이 상기 랜덤 위치 값 r1보다 크지 않으면, 포인트 표현의 변경 없이 입력 포
인트 P를 상기 제1 EC 연산기(211)로 출력한다. 이때, 상기 제1 EC 연산기(211)는 상기 입력 포인트 P와 해당
라운드의 비밀 키 K로부터 EC 연산의 수행으로 암호화된 출력 포인트 Q1을 생성한다.
마찬가지로, 나머지 포인트 표현 변환기들(232, 233...) 각각은 나머지 EC 연산기들(212, 213,...) 전후에서,<85>
이전 라운드에서 암호화된 출력 포인트(Q1, Q2, ...)를 다음 라운드에서 EC 연산을 수행하기 전에, 상기 랜덤화
율 r 및 상기 랜덤 위치 값 r1을 비교하여, 포인트 표현을 변경할 것인지를 결정하고, 상기 결정에 따라 해당
라운드 전 또는 후의 포인트를 선택하여 상기 선택된 포인트를 상기 랜덤 선택 값 r2가 지시하는 포인트 표현으
로 변환한다. 상기 변환에 의하여 포인트 표현이 변경된 포인트(Q1', Q2', ...)가 해당 EC 연산기로 출력된다.
해당 EC 연산기는 각 라운드에서 입력되는 포인트 표현이 변경된 또는 변경되지 않은 포인트와 해당 비밀 키로
부터 EC 연산을 수행한다.
이와 같이, 상기 다수의 포인트 표현 변환기들(231, 232, 233...)은 입력 포인트 P 또는 상기 EC 연산에 의한<86>
암호화된 포인트들 중 적어도 하나를 랜덤하게 선택하고, 상기 선택된 포인트의 표현을 변환하여 변경된 포인트
를 다음 라운드의 EC 연산기로 출력한다. 포인트 표현의 변경은 상기 입력 랜덤화율 r과 상기 난수 발생기에서
각 라운드마다 생성되는 랜덤 위치 값 r1에 따라 결정되고, 변경되는 포인트 표현 종류는 상기 난수 발생기에서
각 라운드 마다 생성되는 랜덤 선택 값 r2에 의하여 결정된다.
위에서 기술한 바와 같이, 본 발명의 일실시예에 따른 암호화 방법 및 장치는, 스칼라 곱 계산 과정 중에 랜덤<87>
화율 r, 랜덤 위치 값 r1, 랜덤 선택 값 r2에 따라 다수 라운드에 걸쳐 랜덤하게 포인트 표현을 변경하여 이진
필드 ECC를 수행하므로, DPA에 강력한 대응책으로 제시될 수 있다. 랜덤 포인트 표현에 있어서, "Affine",
"Ordinary Projective", "Jacobian Projective" 및 "Lopez-Dahab Projective" 중 어느 하나가 사용될 수 있다.
본 발명에 따른 암호화 방법 및 장치는 스칼라 곱 계산 과정에서 포인트 표현을 변경하는 횟수 만큼 성능 저하<88>
(degradation)를 일으킬지 모르지만, 다른 한편으로 그 만큼 EC 연산에서의 파워 트랙이 마스킹(masking)되어
구별될 수 없도록 파워 해독 공격의 복잡도를 증가시킨다. 위에서 쉬운 역산(inversion) 방법 중의 하나를 이용
하는 이진 필드 ECC에 대하여 논의되었지만, 확장된 유클리드 알고리즘(Extended Euclidian Algorithm)을 이용
하는 소수 필드 ECC 등 약간의 수정을 통하여 다른 형태로 구현될 수 있고, 이와 같은 조심스러운 구현에서 파
워 해독 공격에 강력하게 대처할 수 있을 것이다.
본 명세서에서 개시된 방법 및 장치에서 사용되는 기능은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수<89>
있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록 매체는 컴퓨터 시스템에 의하여 읽혀질 수
있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록 매체의 예로는 ROM,
RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장장치 등이 있으며 또한 캐리어 웨이브(예를 들어 인터
넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결
된 컴퓨터 시스템에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.
이상에서와 같이 도면과 명세서에서 최적 실시예가 개시되었다. 여기서 특정한 용어들이 사용되었으나, 이는 단<90>
지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미한정이나 특허청구범위에 기재된 본 발명의 범위를 제
한하기 위하여 사용된 것은 아니다. 그러므로 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형
및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된
특허청구범위의 기술적 사상에 의해 정해져야 할 것이다.
발명의 효과
상술한 바와 같이 본 발명에 따른 암호화 방법 및 장치는, 랜덤하게 변경되는 포인트 표현에 따라 파워 트랙의<91>
엔트로피를 증가시켜서 파워 해독 공격의 효율성을 떨어뜨릴 수 있다. 또한, 포인트 표현의 랜덤화율을 유저가
콘트롤하는 것이 가능하여, 성능 저하 및 보안성 저지 레벨(security resistance level)의 설정도 가능하다. 따
라서, DPA 공격에 강하고 빠른 동작 스피드를 요하는 암호화 시스템에 적용하기 유리한 효과가 있다. 그리고,
약간의 수정을 가하여 소수 유한 필드 ECC에도 적용가능하고, 잘 알려져 있는 어떠한 암호화 알고리즘에도 쉽게
적용될 수 있다.
- 11 -
등록특허 10-0891323
도면의 간단한 설명
본 발명의 상세한 설명에서 인용되는 도면을 보다 충분히 이해하기 위하여 각 도면의 간단한 설명이 제공된다.<1>
도 1은 종래의 스칼라 곱 과정을 나타내는 도면이다.<2>
도 2는 본 발명의 일실시예에 따른 암호화 방법을 나타내는 흐름도이다.<3>
도 3은 도 2를 실현하는 본 발명의 일실시예에 따른 암호화 장치를 나타내는 블록도이다.<4>
도 4는 도 2를 실현하는 본 발명의 다른 실시예에 따른 암호화 장치를 나타내는 블록도이다.<5>
도면
도면1
- 12 -
등록특허 10-0891323
도면2
도면3
- 13 -
등록특허 10-0891323
도면4
- 14 -
등록특허 10-0891323