KR970009022A - 암호화 통신 처리 - Google Patents

Abstract

암호화, 서명 및 입증을 위해 사용될수 있는 신규한 비대칭 암호화 시스템. 이 시스템은 유한 링 K에 있어서 값을 갖는저 차수 일반 다항식에 기초한다.

이 시스템은 반드시 전단사적이지는 않다. 보안 키는 링 K의 확장에 있어서 값을 갖는 다항식을 비밀로 할수 있도록 한다. 이들 방정식을 푸는 것은 보안 키를 갖고 있을 경우에 가능하며, 이는 공용 키만으로 실행할수 없는 연산을 행한다.

Description

암호화 통신 처리

본 내용은 요부공개 건이므로 전문내용을 수록하지 않았음

제1도는 메시지를 처리하기 위해 사용되는 연속적인 변환들을 나타낸 도면이다, 제2도는 메시지의 부호화/해독을 실행하기 위해 사용되는 통신 장치를 보인 도면이다, 제3도는 메시지의 서명 및 그의 검증을 실행하기 위해 사용되는 상기 장치를 보인 도면이다.

Claims (12)

1. 유한 링(K)의 (n)개 요소들로 표현된 값 (X)를 링 (K)의 (n') 요소들로 표현된 가상 치(Y)로 변환하는 암호화 통신 처리에 있어서, a) 상기 가상 치(Y)의 각 요소(n')는 값 (X)의 요소(n)들로 구성된 2 이상의 낮은 차수 D를 갖는 일반 다항식의 형태이고: b) 상기 가상 치 (Y)는 다음 스텝들(그들중 적어도 몇몇은 암호화 비밀의 지식을 요함)을 포함하는 변환에 의해 값 (X)로부터 얻어질수 있으며: b1) (n) 개의 요소들을 갖는 제 1 이미지(I1)를 얻기 위해 값 (X)의 (n)개 요소들로 구성된 차수 1의 제 1 비밀 다항 변환 (s)를 값 (X)에 가하는 스텝; b2) 상기 제 1 이미지(I1)의 (n)개 요소들은 W*k = ne의 링 (K)의 차수 W를 갖는 확장(LW)에 속하고 다음과 같이 정의된변환을 상기 제 1 이미지(I1)에 가하는 변수 또는 소수(k)의 변수 (x, x', x", ..., xk)를 나타내는 것으로 간주되고:

   f : L_W ^k→L_W ^k

   (x, x', x", …, x^k)→(y, y', y", …, y^k)

   상기 식에서 (y, y', y", …, y^k)는 변환 f로 부터의 (x, x', x", …, x^k)의 이미지이고, 이 때 f는 다음과 같은 두 특성들을 입증한다.

   -b2.1) 상기 링 확장(L_W)의 베이스(B)에 있어서, 이미지(y, y', y", …, y_k)의 각 성분은 이 베이스에 있어서 (x, x',x", …, x_k)의 성분들로 구성된 다항의 형태로 표현되며 이 다항은 상기 일반 다항식의 차수 (D) 미만 또는 이와 동일한전체 차수를 갖고; -b2.2) 링 확장(L_W)으로 표현되며, 상기 변환은,(그의 수가 전체 엔트리수에 대해 무시할수 있는 어떤 엔트리들을 제외하고) 전항들이 존재할때 이 전항들을 계산할수 있도록 되며; b3) 상기 변환된 제 1 이미지(I1)는 제 2 이미지(I2)를 구성하고; b4) 소정 수의 요소들을 갖는 제 3 이미지(I3)를 얻기 위해 상기 제 2 이미지(I2)의 요소들로 구성된, 차수 1을 갖는 제2 비밀 다항 변환 (t)를 상기 제 2 이미지 (I2)에 가하는 스텝; 및 b5) 상기 가상 치(Y)를 형성하기 위해 상기 제 3 이미지(I3)의 요소들중에서 (n') 요소들을 선택하는 스텝을 포함하는 것을 특징으로 하는 암호화 통신 처리.
2. 제1항에 있어서, 상기 일반 다항식의 낮은 차수(D)는 2인 것을 특징으로 하는 암호화 통신 처리.
3. 제1항에 있어서, 상기 변수의 수는 1인 것을 특징으로 하는 암호화 통신 처리.
4. 제3항에 있어서, 상기 일반 다항식의 저 차수(D)는 2이고, (K)는 유한계이며, 상기 변환 (F)는 다음 형태를 갖는 것을 특징으로 하는 암호화 통신 처리.

   f : L_W…→L_W

   x…→

   이 때, q는 계 (K)의 기수; Q=q^θij, P=q^ψij, S = q^ζi, β_i,j, α_i, 및 μ₀는 L_W의 요소들, θ^i,j, φ^i,j, 및 ξ^i,j는 정수이며, 다항 f의 x의 차수는 1000 이하이다.
5. 제1항에 있어서, 항수가 적은 일반식의 적의 선형 조합이외의 (x, x', x", …, x^k) 및 (y, y', y", …, y^k)의 성분으로 구성된 낮은 전 차수를 갖는 다항식이 존재하지 않도록 한 것을 특징으로 하는 암호화 통신 처리.
6. 제1항에 있어서, 계수 γ_ij, α_i, β_j또는 δ₀중 적어도 하나가 영이 아닌 상태에서, ∑γ_ij, x_iy_i+ ∑α_ix_i∑β_iy_j+ δ₀=0인 형태를 갖는 다항식이 존재하지 않도록 하고, 이는 계수 y_j가 암호화된 메시지의 성분인 경우 항상 입증되며, 상기 계수 x_i는 비암호화 메세지의 성분인 것을 특징으로 하는 암호화 통신 처리.
7. 제1항에 있어서, 상기 링 (K)는 유한계이고 링의 확장(L_W)은 링 (K)의 차수 W를 갖는 확장이며, 이는 (L_W)가 K[X]/g(X)를 갖는 동형이고, 이때 g는 K에 대한 W의 차수를 갖는 부정 다항식인 것을 특징으로 하는 암호화 통신 처리.
8. 입증자(verifier)로 불리우는 첫번째 사람에 의해, 증명자(prover)로 불리우는 다른 사람의 비대칭 암호화를 위한 처리에 있어서, -상기 입증자는 제1값(Y)을 증명자세 보내고; -상기 증명자는 제1항에 명시된 인버스 변환에 대응하는 변환을 제1값(Y)에 가하여 얻어지는 제2값(X)를 상기 입증자에 반송하며; 상기 입증자는 제1항으로 부터의 변환을 제2값(X)에 가하고 그 결과를 상기 제1값(Y)에 링크된 소정 관계에 맞는 것을 입증하는 것을 특징으로 하는 처리.
9. 유한 링(K)의 (n) 요소들로 표시된 값 (X)를 링(K)의 요소(n)들로 표시된 가상치(Y)로 변환하는 암호화 통신 처리에 있어서, a) 가상 치(Y)의 각 요소(n')는 값 (X)의 요소(n)들로 구성된 2 이상의 낮은 차수 D를 갖는 일반 다항식의 형태이고: b) 상기 가상 치 (Y)는 다음 스텝들(그들중 적어도 약간은 암호화 보안의 지식을 요함)을 포함하는 변환에 의해 값 (X)로부터 얻어질수 있으며: b1) (n) 개의 요소들을 갖는 제 1 이미지(I1)를 얻기 위해 값 (X)의 (n)개 요소들로 구성된 차수 1의 제 1 비밀 다항 변환 (s)를 값 (X)에 가하는 스텝; b2) 각 브랜치가 제 1 이미지(I1)의 요소들로 구성되는, 하나 이상의 브랜치를 형성하는 스텝; 및 상기 브랜치들의 적어도 하나 (e)에 있어서, 브랜치들의 (n_e) 요소들은 W*k = n_e의 링 (K)의 차수 W를 갖는 확장(L_W)에속하고 다음과 같이 정의된 변환을 적어도 상기 브랜치 (e)에 가하는 변수 또는 소수(k)의 변수 (x, x', x", …, x^k)를 나타내는 것으로 간주되고;

   f : L_e ^k→L_e ^k

   (x, x', x", …, x^k)→(y, y', y", …, y^k)

   상기 식에서 (y, y', y", …, y^k)는 변환 f_e로 부터의 (x, x', x", …, x|^k)의 이미지이고, 이 때 f_e는 다음과 같은 두 특성들을 입증한다.

   -b2.1) 상기 링 확장(L_W)의 베이스(B)에 있어서, 이미지(y, y', y", …, y^k)의 각 성분은 이 베이스에 있어서 (x, x',x", …, x^k)의 성분들로 구성된 다항식의 형태로 표현되며 이 다항식은 상기 일반식의 차수 (D) 미만 또는 이와 동일한 전체 차수를 갖고; -b2.2) 링 확장(L_W)으로 표현되며, 상기 변환 (f_e)는, 전항들이 존재할때 (그의 수가 전체 엔트리수에 대해 무시할수 있는어떤 엔트리들을 제외하고) (f_e)의 전항들을 계산할수 있도록 하며; 다른 가능한 브랜치에 상기 링(K)에 있어서의 값을 갖는 성분들로 구성된 상기 차수 (D)와 같거나 그 미만의 차수를 갖는 다항 변환을 인가하는 스텝; b3) 상기와 같이 변환된 브랜치 또는 이와 같이 변환된 복수의 브랜치가 연쇄화된 다음, 제 2 이미지(I2)를 구성하고; b4) 소정 수의 요소들을 갖는 제 3 이미지( I3)를 얻기 위해 상기 제 2 이미지(I2)의 요소들로 구성된 차수 1을 갖는, 제2 비밀 다항 변환 (t)를 상기 제 2 이미지(I2)에 가하는 스텝; 및 b5) 상기 가상 치(Y)를 형성하기 위해 상기 제 3 이미지(I3)의 요소들중에(n')개의 요소들을 선택하는 스텝을 포함하는 것을 특징으로 하는 암호화 통신 처리.
10. 제9항에 있어서, (D)와 같거나 그 미만의 차수를 갖는 다항식이 변환된 브랜치 또는 다른 브랜치의 출력에 부가되며, 다항식은 이 브랜치의 직전에 위치된 브랜치들의 변수에만 의존하는 것을 특징으로 하는 암호화 통신 처리.
11. 제9항에 있어서, 상기 제 1 이미지(I1)는 몇개의 브랜치를 가지며, 이들 브랜치중 하나는 적어도 32비트의 값을 처리하는 것을 특징으로 하는 암호화 통신 처리.
12. 메시지 (X)의 비대칭 서명 및 이 서명의 입증을 위한 처리에 있어서, 상기 서명은, 제1항 또는 9항에 기재된 인버스 변환에 상응하는 변환을, 메시지 또는 메시지의 일반 변환에 가하여 얻어지며, 또한 그 입증은, 결과 (Y)가 사인될 메시지에 연관된 소정 관계에 따라 얻어지는 것을 체크하는 것으로 구성되는 처리.

    ※ 참고사항 : 최초출원 내용에 의하여 공개하는 것임.