트랩도어 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 트랩도어 순열
3. 예시
- 3.1. RSA 가정
- 3.2. 라빈의 이차 잉여 가정
참조

1. 개요

트랩도어 함수는 일방향 함수 집합으로, 특정 트랩도어(비밀 정보)가 주어지면 역함수를 쉽게 계산할 수 있지만, 트랩도어가 없으면 역함수를 계산하는 것이 계산적으로 어려운 함수이다. 트랩도어 순열은 일방향 순열의 특별한 경우이다. RSA 암호 시스템과 라빈의 이차 잉여 가정은 트랩도어 함수의 예시로, 소인수분해의 어려움을 기반으로 한다.

더 읽어볼만한 페이지

암호학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
암호학 - 암호화
암호화는 정보를 보호하기 위해 사용되는 기술로서, 단순한 문자 치환 방식에서 시작하여 현대에는 강력한 암호화 표준과 다양한 종류로 발전했으며, IT 시스템 전반에 적용되지만, 사이버 공격과 양자 컴퓨팅의 발전에 대한 대응이 필요한 기술이다.

트랩도어 함수
기본 정보
트랩도어 함수의 예시. 함수 f는 트랩도어 정보 k가 없으면 계산하기 어렵지만, k가 있으면 쉽게 계산할 수 있다.
유형	암호학
정의	한 방향 함수이며, 비밀 정보를 알면 역방향 계산이 쉬움
관련 개념	한 방향 함수, 공개 키 암호 방식
상세 내용
설명	트랩도어 함수는 계산하기는 쉽지만, 추가적인 정보 없이는 역으로 계산하기 어려운 함수이다. 트랩도어 정보(trapdoor)를 가진 사람은 쉽게 역함수를 계산할 수 있다. Diffie, Whitfield; Hellman, Martin (1976)에 의해 암호학에 도입되었다.
응용 분야	공개 키 암호 방식
예시	큰 수의 곱셈은 쉽지만, 소인수 분해는 어렵다. RSA 암호
같이 보기
관련 항목	한 방향 함수 역함수 백도어 (컴퓨팅)

2. 정의

트랩도어 함수는 일방향 함수 f|에프^영어_{k|케이^영어} : D|디^영어_{k|케이^영어} → R|알^영어_{k|케이^영어} (k|케이^영어 ∈ K|케이^영어) 형태의 집합으로, 여기서 K|케이^영어, D|디^영어_{k|케이^영어}, R|알^영어_{k|케이^영어}는 모두 이진 문자열 집합 {0, 1}^*의 부분 집합이며, 다음 조건을 만족한다.

확률적 다항 시간(PPT) ''샘플링'' 알고리즘 Gen이 존재하여 Gen(1^''n'') = (''k'', ''t''_''k'')를 반환한다. ''k'' ∈ ''K'' ∩ {0, 1}^''n''이고, ''t''_''k'' ∈ {0, 1}^*이며, | ''t''_''k'' | < ''p''(''n'')이다. 여기서 ''p''는 어떤 다항식이다. ''t''_''k''는 ''k''에 해당하는 ''트랩도어''이며, 효율적으로 샘플링할 수 있다.
입력 ''k''가 주어지면 ''x'' ∈ ''D''_''k''를 출력하는 PPT 알고리즘이 존재한다. 즉, 각 ''D''_''k''는 효율적으로 샘플링할 수 있다.
모든 ''k'' ∈ ''K''에 대해 ''f''_''k''를 올바르게 계산하는 PPT 알고리즘이 존재한다.
모든 ''k'' ∈ ''K'', ''x'' ∈ ''D''_''k''에 대해 ''y'' = ''A'' ( ''k'', ''f''_''k''(''x''), ''t''_''k'' )일 때, ''f''_''k''(''y'') = ''f''_''k''(''x'')를 만족하는 PPT 알고리즘 ''A''가 존재한다. 즉, 트랩도어가 주어지면 역함수를 구하기 쉽다.
모든 ''k'' ∈ ''K''에 대해 트랩도어 ''t''_''k''가 없을 때, 모든 PPT 알고리즘에서 ''f''_''k''(''x'')가 주어졌을 때 ''f''_''k''(''x'' '') = ''f''_''k''(''x'')를 만족하는 역상 ''x'' ''를 찾을 확률은 무시할 수 있을 정도로 작다.

2. 1. 트랩도어 순열

트랩도어 함수가 일방향 함수이면서 일대일 대응인 경우, 이를 트랩도어 순열이라고 한다.^[1]

3. 예시

정수 인수분해가 어렵다는 가정 하에, RSA 암호 시스템과 라빈의 이차 잉여 가정과 관련된 트랩도어 함수의 예시를 들 수 있다.

3. 1. RSA 가정

RSA 암호 시스템에서 사용되는 트랩도어 함수는 다음과 같이 정의된다.

:

f(x) = x^e \mod n.

만약

n=pq

의 소인수분해가 알려져 있다면,

\phi(n)=(p-1)(q-1)

을 계산할 수 있다. 이를 통해

e

의 역

d

를 계산할 수 있으며,

d = e^{-1} \mod{\phi(n)}

이다.

y = f(x)

가 주어지면,

x = y^d \mod n = x^{ed} \mod n = x \mod n

을 찾을 수 있다.

이러한 계산의 어려움은 RSA 가정에서 비롯된다.^[7]

3. 2. 라빈의 이차 잉여 가정

n

이

n = pq

와 같이 큰 합성수이고,

p

와

q

가

p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}

를 만족하는 큰 소수이며, 적에게는 비밀로 유지된다고 가정한다.

a \equiv z^2 \pmod{n}

을 만족하는

a

가 주어졌을 때

z

를 계산하는 것이 문제이다. 함정(trapdoor)은

n

의 소인수분해이다. 함정이 주어지면,

z

의 해는

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}

이다. 더 자세한 내용은 중국인의 나머지 정리를 참조한다. 소수

p

와

q

가 주어지면

x \equiv a^{\frac{p+1}{4}} \pmod{p}

와

y \equiv a^{\frac{q+1}{4}} \pmod{q}

를 찾을 수 있다. 여기서 조건

p \equiv 3 \pmod{4}

와

q \equiv 3 \pmod{4}

는 해

x

와

y

가 잘 정의되도록 보장한다.^[8]

참조

_[1] 서적 Ostrovsky
_[2] 서적 Advances in Cryptology — CRYPTO '98 1998-06
_[3] 문서 Pass's Notes
_[4] 문서 Goldwasser's lecture notes
_[5] 서적 Ostrovsky
_[6] 문서 Pass's notes
_[7] 강의노트 Goldwasser's lecture notes
_[8] 강의노트 Goldwasser's lecture notes

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com