트랩도어 기능

트랩도어 기능의 개념입니다.알고리즘 Gen. f에 의해 트랩도어 t를 갖는 트랩도어 함수 f를 확률적 다항식 시간으로 효율적으로 산출할 수 있다.그러나 트랩도어 t가 ^[1]주어지지 않는 한 f의 역수 계산은 일반적으로 어렵다.

이론 컴퓨터 과학 및 암호학에서 트랩도어 함수는 "트랩도어"라고 불리는 특별한 정보 없이 한 방향으로 계산하기는 쉽지만 반대 방향으로 계산하기는 어려운 함수이다.트랩도어 함수는 단방향 함수의 특수한 경우로 공개키 ^[2]암호화에 널리 사용됩니다.

수학적인 용어로 f가 트랩도어 함수일 경우, f(x)와 t가 주어지면 x를 계산하기 쉽도록 비밀 정보 t가 존재합니다. 자물쇠와 그 키를 생각해 보십시오.잠금 장치에 걸쇠를 밀어넣어 키를 사용하지 않고 자물쇠를 열림에서 닫힘으로 변경하는 것은 간단한 일입니다.그러나 자물쇠를 쉽게 열려면 키를 사용해야 합니다.여기서 키 t는 트랩도어, 자물쇠는 트랩도어 기능입니다.

간단한 수학 트랩도어의 예는 "6895601은 두 소수의 곱이다.그 숫자는 무엇입니까?"일반적인 "중력" 솔루션은 답을 찾을 때까지 6895601을 소수 몇 개로 나누어 보는 것입니다.그러나 1931이 숫자 중 하나라고 하면 어느 계산기에든 6895601 1931을 입력하면 답을 찾을 수 있다.이 예는 견고한 트랩도어 함수는 아닙니다.현대 컴퓨터는 가능한 모든 답을 1초 안에 추측할 수 있습니다.그러나 이 샘플 문제는 훨씬 큰 소수점 2개를 곱하면 개선될 수 있습니다.

트랩도어 함수는 1970년대 중반 Diffie, Hellman 및 Merkle에 의한 비대칭(또는 공개키) 암호화 기술의 발표와 함께 암호학 분야에서 두드러졌다.실제로 Diffie & Hellman(1976)이 이 용어를 만들었다.몇 가지 함수 클래스가 제안되었고, 트랩도어 함수는 처음에 생각했던 것보다 찾기 어렵다는 것이 곧 분명해졌다.예를 들어, 초기 제안은 부분집합 문제에 기초한 체계를 사용하는 것이었다.이것은, 즉, 부적절한 것으로 판명되었습니다.

2004년 현재^[update] 가장 잘 알려진 트랩도어 함수(패밀리) 후보는 RSA 및 Rabin 함수 패밀리입니다.둘 다 합성수로 지수 모듈로 쓰이고 둘 다 소인수분해 문제와 관련이 있다.

이산 로그 문제의 경도와 관련된 함수(소수 모듈 또는 타원 곡선에 대해 정의된 그룹 내)는 이산 로그의 효율적인 계산을 가능하게 하는 그룹에 대한 알려진 "트랩도어" 정보가 없기 때문에 트랩도어 함수로 알려져 있지 않다.

암호학에서의 트랩도어는 전술한 매우 구체적인 의미를 가지며 백도어와 혼동해서는 안 됩니다(이러한 트랩도어는 자주 서로 교환할 수 있지만 올바르지 않습니다).백도어는 암호화 알고리즘(예를 들어 키쌍 생성 알고리즘, 디지털 서명 알고리즘 등) 또는 운영체제에 추가되는 의도적인 메커니즘으로, 하나 이상의 권한이 없는 당사자가 어떤 방식으로든 시스템의 보안을 우회하거나 전복시킬 수 있습니다.

정의.

트랩도어 함수는 단방향 함수 {f_k : D_k → R_k }(k k K)의 집합이며, 여기서 K, D_k, R은_k 모두 다음 조건을 충족하는 이진 문자열 {0, 1)의 ^*하위 집합입니다.

k k K { {0, ⁿ1) 및_k t { {0, 1)를 갖는 확률론적 다항식 시간(PPT) 샘플링 알고리즘 Gen s.t. Gen(1ⁿ) = (k, t_k)이 존재하며, t { {0, ^*1)은 t < p (n)를 만족하며_k, 여기서 p는 다항식이다.각_k t는 k에 대응하는 트랩도어라고 불립니다.각 트랩도어는 효율적으로 샘플링할 수 있습니다.
입력 k를 지정하면 x µ_k D를 출력하는 PPT 알고리즘도 존재합니다.즉_k, 각 D를 효율적으로 샘플링할 수 있습니다.
임의의 kµK에 대해 f를 올바르게 계산하는_k PPT 알고리즘이 존재합니다.
임의의 k µ K에 대해 임의의 x µ_k D에 대해 PPT 알고리즘 A s.t.가 존재하며, y = A ( k, f_k(x, t_k )라고 하면 f(y) = f_k(x)가_k 됩니다.즉, 트랩도어를 지정하면 반전하기 쉽습니다.
트랩도어_k t가 없는 임의의 k µ K에 대하여, PPT 알고리즘에 대하여 f를 정확하게 반전할_k 확률(즉_k, f(x)가 주어지면 f(x') = f_k(x)가_k 무시해도 ^[3]^[4]^[5]될 정도로 사전 이미지 x'를 찾는다).

위의 컬렉션의 각 함수가 단방향 치환일 경우 이 컬렉션은 트랩도어 ^[6]치환이라고도 합니다.

예

다음 두 예에서는 항상 큰 합성 수를 인수 분해하는 것이 어렵다고 가정합니다(정수 분해 참조).

RSA의 전제 조건

이 예에서는e {\ $displaystyle$ $\phi (n)$ e $}$ modulo $e$ $\phi (n)$ $\phi (n)$ ） { $displaystyle$ \ $phi ( n$ ) $n$ （ Uler ）の ientient of of of of of of of of of of of of （ n $）$ $の$ \ $displaystyle$ 가 트랩도어입니다.

f(x)=x^{e}\mod n

$n=pq$ $n=pq$ $n=pq$ q { $displaystyle$ n $= pq$ }의 인수분해를 알고 $\phi (n)=(p-1)(q-1)$ 경우, $\phi (n)=(p-1)(q-1)$ ( $\phi (n)=(p-1)(q-1)$ ) $\phi (n)=(p-1)(q-1)$ ( $\phi (n)=(p-1)(q-1)$ - $\phi (n)=(p-1)(q-1)$ { $displaystyle \phi$ ( n ) = ( $p-1)($ q-1)}을 $계산$ 할 $\phi (n)=(p-1)(q-1)$ 수 있다.이를 통해 $e$ 의 $e$ $(\$ $displaystyle$ d $)$ 는 $d$ d $d=e^{-1}\mod {\phi (n)}$ - $d=e^{-1}\mod {\phi (n)}$ $d=e^{-1}\mod {\phi (n)}$ $d=e^{-1}\mod {\phi (n)}$ ( $d=e^{-1}\mod {\phi (n)}$ ) { $displaystyle$ d = $e^$ { - 1 $d=e^{-1}\mod {\phi (n)}$ } \ $mod$ { $phi ($ $y=f(x)$ ) $y=f(x)$ } 、 $y=f(x)$ $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ $y=f(x)$ $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ $y=f(x)$ ( $x$ ) \ $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ x d $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ n $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ $display style$ x d mod n = mod n mod n $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ = $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ n = mod n = n mod n $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ n display n $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ n 。\ $mod$ n $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ 그 경도는 RSA의 ^[7]전제조건에 따라 달라집니다 $.$

라빈의 2차 잔차 가정

$n$ ${displaystyle$ n $}$ 은 $n$ n $n=pq$ $n=pq$ q {\ $displaystyle$ n $=pq$ 과 같이 큰 합성수입니다. $p$ 서p {\ $displaystyle$ p $}$ 와 $p$ $q$ $q$ $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ q $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ 3 ( $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ 4 $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ )는 p $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ 3 ( $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ 4 $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ q \ $equiv$ 3 $pmod { 4$ 의 큰 소수입니다.문제는 $a\equiv z^{2}{\pmod {n}}$ $a\equiv z^{2}{\pmod {n}}$ ( $a\equiv z^{2}{\pmod {n}}$ n $a\equiv z^{2}{\pmod {n}}$ ) {\ $displaystyle z^{2}$ {\ $pmod {n$ 이 $a\equiv z^{2}{\pmod {n}}$ z{\ $displaystyle$ z $}$ 를 $a$ $a$ 하는 $z$ 것입니다.트랩도어는 n $(\displaystyle$ n $n$ 의 인수분해입니다.트랩도어를 사용하면 z의 $cx+dy,cx-dy,-cx+dy,-cx-dy$ 는 $cx+dy,cx-dy,-cx+dy,-cx-dy$ c x + $x$ - $dy$ c $cx+dy,cx-dy,-cx+dy,-cx-dy$ + $cx+dy,cx-dy,-cx+dy,-cx-dy$ , c x $cx+dy,cx-dy,-cx+dy,-cx-dy$ + $,$ c $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ + dy $cx+dy,cx-dy,-cx+dy,-cx-dy$ $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ 2 $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ y $cx+dy,cx-dy,-cx+dy,-cx-dy$ ( $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ 2 $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ )로 지정할 수 있습니다 $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ 1 ( $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ q $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ ) { $style$ a \ $equiv$ x^ {2 $}$ {\ $pmod$ { $p}$ , c \ $equiv$ 1 { \ $pmod {$ q } , $c$ \ $equiv$ 0 { \ $pmod$ { $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ } , d \ $equiv$ 0 \ $pmod {p$ } , d \ $equiv 1 .pmod$ { $pmod$ } } } $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ } $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ 。 $소수$ p{ $displaystyle$ p $}$ $q$ q { $displaystyle$ $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ $q$ 를 지정하면 $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ pr a p $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ + $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ 4 ( $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ p $){$ $display$ x \ $equiv$ a^ { \ $frac { p$ + $1$ }{ 4 $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ 를 $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ 수 있습니다. $}}{\pmod$ {p $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ }} $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ y $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ ≡ $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ + $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ ( $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ mod $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ ){ $displaystyle y\equiv$ a $^{\frac {q+1$ }{4} $}}{\pmod$ {q $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ 여기서 $p\equiv 3{\pmod {4}}$ p $p\equiv 3{\pmod {4}}$ 3 ( $p\equiv 3{\pmod {4}}$ 4 ){ $display$ p \ $equiv$ $p\equiv 3{\pmod {4}}$ 3 { \ $pmod$ { $p\equiv 3{\pmod {4}}$ 4 $}및$ q $3$ 3 ( $q\equiv 3{\pmod {4}}$ 4 ){ $q\equiv 3{\pmod {4}}$ $display$ style x $x$ } $y$ { $display$ style y $y$ }를 $q\equiv 3{\pmod {4}}$ ^[8]적절히 정의할 수 있습니다.

「」를 참조해 주세요.

단방향 함수

메모들

^ 오스트롭스키, 페이지 6-9
^ Bellare, M (June 1998). "Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems". Advances in Cryptology.
^ 패스 노트, def. 56.1
^ 골드워서의 강의 노트, def. 2.16
^ 오스트롭스키, 페이지 6-10, 방어 11
^ 패스의 노트 def 56.1, 도디스의 def 7, 강의 1.
^ 골드워서의 강의 노트, 2.3.2; 린델의 노트, 17페이지, Ex.1.
^ Goldwasser의 강의 노트, 2.3.4

레퍼런스

Diffie, W.; Hellman, M. (1976), "New directions in cryptography" (PDF), IEEE Transactions on Information Theory, 22 (6): 644–654, CiteSeerX 10.1.1.37.9720, doi:10.1109/TIT.1976.1055638
Pass, Rafael, A Course in Cryptography (PDF), retrieved 27 November 2015
Goldwasser, Shafi, Lecture Notes on Cryptography (PDF), retrieved 25 November 2015
Ostrovsky, Rafail, Foundations of Cryptography (PDF), retrieved 27 November 2015
Dodis, Yevgeniy, Introduction to Cryptography Lecture Notes (Fall 2008), retrieved 17 December 2015
Lindell, Yehuda, Foundations of Cryptography (PDF), retrieved 17 December 2015

[1] 오스트롭스키, 페이지 6-9

[2] Bellare, M (June 1998). "Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems". Advances in Cryptology.

[3] 패스 노트, def. 56.1

[4] 골드워서의 강의 노트, def. 2.16

[5] 오스트롭스키, 페이지 6-10, 방어 11

[6] 패스의 노트 def 56.1, 도디스의 def 7, 강의 1.

[7] 골드워서의 강의 노트, 2.3.2; 린델의 노트, 17페이지, Ex.1.

[8] Goldwasser의 강의 노트, 2.3.4

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

트랩도어 기능

네임스페이스

더

목차

정의.

예

RSA의 전제 조건

라빈의 2차 잔차 가정

「」를 참조해 주세요.

메모들

레퍼런스

Search

트랩도어 기능

정의.

예

RSA의 전제 조건

라빈의 2차 잔차 가정

「 」를 참조해 주세요.

메모들

레퍼런스

「」를 참조해 주세요.