KR100330503B1

KR100330503B1 - 서명 검증 방법

Info

Publication number: KR100330503B1
Application number: KR1020000014255A
Authority: KR
Inventors: 이필중; 심상규
Original assignee: 정명식; 학교법인 포항공과대학교
Priority date: 2000-03-21
Filing date: 2000-03-21
Publication date: 2002-04-01
Also published as: KR20010092190A

Abstract

서명 검증 방법{Signature verification method}이 개시된다. 본 서명 검증 방법은 정수 p, g, y, a, 및 b가 주어질 때 이항 멱승를 계산함을 필요로 하는 서명 검증 방법에 있어서, (a) n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 승 연산을에 따라 계산하는 단계를 포함한 이항 멱승 계산 단계를 포함하는 것을 특징으로 한다.

본 서명 검증 방법에 따르면, 이항 멱승 계산을 빠르게 수행함으로써 서명 검증에 소요되는 시간을 줄일 수 있다

Description

서명 검증 방법{Signature verification method}

본 발명은 서명 검증 방법에 관한 것으로, 더 상세하게는 이산 대수 문제 또는 타원 곡선 이산 대수 문제의 어려움에 기초한 전자 서명 시스템 내에서 수행되는 이항 멱승 연산을 사용하는 서명 검증 방법에 관한 것이다.

도 1 및 도 2에는 일반적인 전자 서명값을 구하는 과정을 도시하였다. 도 1 및 도 2를 참조하면, 다음과 같은 수학식으로 표현되는 전자 서명값()을 얻는다.

도 3 및 도 4에는 도 1 및 도 2의 과정에 의하여 구한 전자 서명값을 기초로 서명 검증을 수행하는 과정을 도시하였다. 도 3 및 도 4를 참조하면, 서명 계산부에서, 승인부는 도 1 및 도 2의 과정에 의하여 구한 전자 서명값()의 R 값과 메시지 M의 일부인 M2로부터 T 값 및 R 값을 얻고, 얻어진 결과값 T 와 S를 사용하여, Y는 서명자의 서명에 대한 공개 검증키, N은 도메인값으로 정의되어 있는 법, V는 검증 지수, T는 승인값이라 할 때,

로 나타내어지는 선서명값(pre-signature)값을 얻는다. 여기서,또는을 계산하는 과정은 멱승 연산에 해당하고,을 계산하는 과정은 이항 멱승 연산에 해당한다.

상기와 같은 수학식 1 및 2는 이산 대수 문제의 어려움에 기초한 전자 서명일 때의 계산식에 해당하고, 타원 곡선 이산 대수 문제의 어려움에 기초한 전자 서명에 이에 대응하는 수학식은,

과 같이 나타낼 수 있다. 여기서, T와 S는 정수이고, Y와 V는 타원 곡선 상의 점에 해당한다. 따라서, TY와 SV는 타원 곡선상의 정수 배 연산에 해당한다. 따라서, TY + SV는 타원 곡선상의 이상 멱승 연산에 해당한다고 할 수 있다.

이산 대수 문제 또는 타원 곡선 이산 대수 문제의 어려움에 기초한 전자 서명에서 멱승 연산은 가장 시간이 많이 소요되는 연산이다. 서명 검증 과정에서는 이항 멱승 형태의 멱승이 필요하기 때문에, 일반적인 멱승 형태의 단항 멱승의 방법을 사용하면 서명 검증이 비효율적으로 수행된다는 문제점이 있다.

본 발명이 이루고자 하는 기술적 과제는 이항 멱승을 효율적으로 계산하는 방법을 포함하는 서명 검증 방법을 제공하는 것이다.

도 1 및 도 2은 일반적인 전자 서명값을 구하는 과정을 도시한 도면이다.

도 3 및 도 4는 도 1 및 도 2의 과정에 의하여 구한 전자 서명값을 기초로 서명 검증을 수행하는 과정을 도시한 도면이다.

도 5는 본 발명의 일실시예에 따른 서명 검증 방법의 주요 단계들을 나타낸 흐름도이다.

도 6은 본 발명의 타실시예에 따른 서명 검증 방법의 주요 단계들을 나타낸 흐름도이다.

상기 과제를 이루기 위하여 본 발명의 일측면에 따른 서명 검증 방법은 정수 p, g, y, a, 및 b가 주어질 때 이항 멱승를 계산함을 필요로 하는 서명 검증 방법에 있어서, (a) n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 승 연산을에 따라 계산하는 단계;를 포함한 이항 멱승 계산 단계를 포함하는 것을 특징으로 한다.

또한, 상기 소정의 양의 수 n은 2 일 수 있다.

또한, 상기 (a) 단계는, (a-1) 정수 a 및 b, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는 단계; (a-2)는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를정의하는 단계; (a-3) 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 두는 단계; (a-4)는 A와 B 중에서 작지 않은 값을 선택하는 함수로써 정의할 때,이고,인 것을 기초로 이항 멱승을,에 따라 계산하는 단계;를 포함하는 것이 바람직하다.

또한, 상기 과제를 이루기 위한 본 발명의 다른 측면에 따른 서명 검증 방법은 타원곡선 E가 주어지고, 타원 곡선 E 상의 점 G, Y와 정수 a, b가 주어질 때,를 계산함을 필요로 하는 서명 검증 방법에 있어서, (a) n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 배 연산을에 따라 계산하는 단계;를 포함하는 이항 멱승 계산 단계를 포함하는 것을 특징으로 한다.

또한, 상기 (a) 단계는, (a-1) 지수 a 및 b와, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는 단계;(a-2)는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를 정의하는 단계; (a-3) 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 두는 단계; (a-4)는 A와 B 중에서 작지 않은 값을 선택하는 함수로써 정의할 때,이고,인 것을 기초로, 이항 멱승를,

에 따라 계산하는 단계;를 포함하는 것이 바람직하다.

이하 첨부된 도면들을 참조하여 본 발명의 바람직한 실시예들을 상세히 설명하기로 한다.

이항 멱승 연산은 대표적으로 다음과 같은 두 가지 경우로 구분될 수 있다. 즉, 첫 번째 경우는, 정수 p, g, y, a, 및 b가 주어지고,를 계산하는 경우이고, 두 번째 경우는, 타원곡선 E가 주어지고, 타원 곡선 E 상의 점 G, Y와 정수 a, b가 주어질 때,를 계산하는 경우이다.

도 5에는 본 발명의 일실시예에 따른 서명 검증 방법의 주요 단계들을 흐름도로써 나타내었다. 도 5에 나타낸 본 발명의 일실시예에 따른 서명 검증 방법은첫 번째 경우의 이항 멱승 연산을 처리하기 위한 것이다. 도 5를 참조하면, 본 발명의 일실시예에 따른 서명 검증 방법에 따르면, 먼저, 이항 멱승를 계산하기 위한 정수 p, g, y, a, 및 b가 주어진다(단계 502). 다음으로, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는다(단계 504). 다음으로,는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를 정의한다(단계 506).

대부분의 경우,과는 다른 값을 가진다고 할 수 있으나, 본 발명의 실시예에 따르면, 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하는 단계를 포함함으로써과의 길이를 동일하게 할 수 있으므로, 이하에서이라 둔다. 다시 말하면, 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 둔다(단계 508).

다음으로,는 A와 B 중에서 작지 않은 값을 선택하는 함수로써 정의할 때,

이고,

인 것을 기초로

이항 멱승을,

에 따라 계산한다(단계 510).

이제, 단계(510)에서 구한 이항 멱승값을 사용하여 서명 검증을 수행한다(단계 512).

상기와 같은 본 발명의 실시예에 따른 서명 검증 방법을 일반화하면 n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 승 연산을에 따라 계산하는 단계를 포함하는 이항 멱승 계산 단계를 포함하는 것을 특징으로 한다. 다만, 이상에서는 상기 소정의 양의 수 n은 2 인 경우를 실시예로써 설명하였다.

또한, 정수 e 및가 주어지고 주어진 정수는 윈도우의 크기이고, l은 연산 사슬의 길이이며, 수열는,,...,를 만족하는 수열이라 할 때,이고,이며의 관계를만족하는 수열을 정의할 때 사용되는 수열은를 만족하는 덧셈 사슬의 수열 또는를 만족하는 덧셈/뺄셈 사슬일 수 있다. 이러한 두 경우에서, 수열은 각각의 경우에 덧셈 사슬에 대한 연산사슬 또는 덧셈/뺄셈 사슬에 대한 연산사슬이라 칭할 수 있다.

또한, 정수 e 및가 주어지고 주어진 정수는 윈도우의 크기이고, l은 연산 사슬의 길이이며, 수열는,,...,를 만족하는 수열이라 할 때,이고,이며의 관계를 만족하는 수열을 정의할 때 사용되는 수열은를 만족하는 덧셈 사슬의 수열 또는를 만족하는 덧셈/뺄셈 사슬의 수열일 수도 있다. 이러한 두 경우에서, 수열은 각각의 경우에 덧셈 사슬에 대한 연산사슬 또는 덧셈/뺄셈 사슬에 대한 연산사슬이라 칭할 수 있다.

도 6에는 본 발명의 타실시예에 따른 서명 검증 방법의 주요 단계들을 흐름도로써 나타내었다. 도 6에 나타낸 본 발명의 타실시예에 따른 서명 검증 방법은 두 번째 경우의 이항 멱승 연산을 처리하기 위한 것이다. 도 6을 참조하면, 본 발명의 타실시예에 따른 서명 검증 방법에 따르면, 먼저, 타원곡선 E가 주어지고, 이항 멱승를 계산하기 위한 타원 곡선 E 상의 점 G, Y와 정수 a, b가 주어진다(단계 602).

다음으로, 지수 a 및 b와, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는다(단계 604).

는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를 정의한다(단계 606).

다음으로, 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 도 5를 참조하여 설명한 바와 동일하게 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 둔다(단계 608).

이고,

인 것을 기초로, 이항 멱승를,

에 따라 계산한다(단계 610).

이제, 단계(610)에서 구한 이항 멱승값을 사용하여 서명 검증을 수행한다(단계 612).

또한, 정수 e 및가 주어지고 주어진 정수는 윈도우의 크기이고, l은 연산 사슬의 길이이며, 수열는,,...,를 만족하는 수열이라 할 때,이고,이며의 관계를 만족하는 수열을 정의할 때 사용되는 수열은를 만족하는 덧셈 사슬의 수열 또는를 만족하는 덧셈/뺄셈 사슬일 수 있다. 이러한 두 경우에서, 수열은 각각의 경우에 덧셈 사슬에 대한 연산사슬 또는 덧셈/뺄셈 사슬에 대한 연산사슬이라 칭할 수 있다.

상기와 같은 본 발명의 실시예에 따른 서명 검증 방법을 일반화하면, 타원곡선 E가 주어지고, 타원 곡선 E 상의 점 G, Y와 정수 a, b가 주어질 때,를 계산함을 필요로 하는 서명 검증 방법에 있어서, n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 배 연산을에 따라 계산하는 단계를 포함한 이항 멱승 계산 단계를 포함한다. 다만, 이상에서는 상기 소정의 양의 수 n은 2 인 경우를 실시예로써 설명하였다.

첫 번째 경우에, 종래 기술에 따르면,와를 계산한 다음,를 계산함으로써 구하고자 하는 결과값을 얻는 것과 같이 단항 멱승을 두 번 계산하는데 반하여, 본 발명의 실시예에 의한 서명 검증 방법에 따르면, 주어진 정수들에 대하여 연산 사슬이라고 칭할 수 있는 수열을 정의하고, 정의된 수열들을 병합하여 이항 멱승 연산을 수행한다.

또한, 두 번째 경우에, 종래 기술에 따르면,와를 계산한 다음,를 계산함으로써 구하고자 하는 결과값를 얻는 것과 같이 단항 멱승을 두 번 계산하는데 반하여, 본 발명의 실시예에 의한 서명 검증 방법에 따르면, 주어진 정수들에 대하여 연산 사슬이라고 칭할 수 있는 수열을 정의하고, 정의된 수열들을 병합하여 이항 멱승 연산을 수행한다.

따라서, 본 발명에 의한 서명 검증 방법에 따르면 서명 검증과정에서 수행되는 이항 멱승 연산에서 제곱 연산 및 두 배 연산의 양이 현저하게 줄어들기 때문에 서명 검증의 속도를 향상시킬 수 있다.

또한, 이항 멱승을 계산하는 다른 방법인 옌-레이(Yen-Laih)의 방법에 비하여 더 큰 윈도우 크기를 사용할 수 있기 때문에 큰 정수에 대한 곱셈이나 타원 곡선 점의 덧셈 연산의 계산량을 현저하게 줄일 수 있다.

이상의 실시예에서는 덧셈/뺄셈 사슬을 사용하는 것을 실시예로써 설명하였으나, 예를 들어, 덧셈 사슬에 대한 연산 사슬과 덧셈/뺄셈에 대한 연산 사슬을 병합하여 사용하는 것과 같이 첨부된 청구항들에 의하여 정의되는 본 발명의 범위내에서 당업자에 의하여 적절히 변경하여 사용하는 것이 가능하다. 따라서, 청구항들에 의하여 정의되는 본 발명의 범위는 상기 실시예들에 한정되지 않는다.

또한, 상기와 같은 본 발명에 따른 서명 검증 방법은 개인용 또는 서버급의 컴퓨터내에서 실행되는 프로그램으로 작성 가능하다. 상기 프로그램을 구성하는 프로그램 코드들 및 코드 세그멘트들은 당해 분야의 컴퓨터 프로그래머들에 의하여 용이하게 추론될 수 있다. 또한, 상기 프로그램은 컴퓨터 독취 가능 기록 매체에 저장될 수 있다. 상기 기록 매체는 자기기록매체, 광기록 매체, 및 전파 매체를 포함한다.

또한, 상기와 같은 본 발명에 따른 서명 검증 방법은 예를들어 상기 프로그램이 수록된 롬으로부터 상기 프로그램을 읽어 상기 서명 검증 방법을 수행하는 디지털 신호 처리기(digital signal processor)로 구현됨으로써, 서명 검증 장치로써 구현될 수 있다. 상기와 같은 서명 검증 장치는 전자 서명 시스템 내에 구비된다.

상술한 바와 같이 본 발명에 따르면 이항 멱승 계산을 빠르게 수행함으로써서명 검증에 소요되는 시간을 줄일 수 있다.

Claims

정수 p, g, y, a, 및 b가 주어질 때 이항 멱승를 계산함을 필요로 하는 서명 검증 방법에 있어서,

(a) n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 승 연산을에 따라 계산하는 단계;를 포함한 이항 멱승 계산 단계를 포함하는 것을 특징으로 하는 서명 검증 방법.
제1항에 있어서,

상기 소정의 양의 수 n은 2 인 것을 특징으로 하는 서명 검증 방법.
제2항에 있어서, 상기 (a) 단계는,

(a-1) 정수 a 및 b, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는 단계;

(a-2)는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를 정의하는 단계;

(a-3) 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 두는 단계;

(a-4)는 A와 B 중에서 작지 않은 값을 선택하는 함수로써 정의할 때,

이고,

인 것을 기초로

이항 멱승을,

에 따라 계산하는 단계;를 포함하는 것을 특징으로 하는 서명 검증 방법.
타원곡선 E가 주어지고, 타원 곡선 E 상의 점 G, Y와 정수 a, b가 주어질 때,를 계산함을 필요로 하는 서명 검증 방법에 있어서,

(a) n을 소정의 양의 수라 할 때를 계산하는데 사용되는 중간값과를 계산하는데 사용되는 중간값에 대하여 각각의 n 배 연산을에 따라 계산하는 단계;를 포함한 이항 멱승 계산 단계를 포함하는 것을 특징으로 하는 서명 검증 방법.
제4항에 있어서, 상기 소정의 양의 수 n은 2 인 것을 특징으로 하는 서명 검증 방법.
제5항에 있어서, 상기 (a) 단계는,

(a-1) 지수 a 및 b와, 윈도우의 크기가 주어질 때, a의 길이인 연산 수열과 b의 길이인 연산 수열을 얻는 단계;

(a-2)는 수열에서를 만족하는 j의 개수를 나타내는 함수이고,는 수열에서를 만족하는 j의 개수를 나타내는 함수를 정의하는 단계;

(a-3) 연산 수열의 길이과 연산 수열의 길이를 동일하게 만들기 위하여 작은 값에 해당하는 연산 사슬의 시작 부분, 즉,또는의 앞 부분에 0을 부가하여이라 두는 단계;

(a-4)는 A와 B 중에서 작지 않은 값을 선택하는 함수로써 정의할 때,이고,인 것을 기초로, 이항 멱승를,

에 따라 계산하는 단계;를 포함하는 것을 특징으로 하는 서명 검증 방법.