암호프로토콜 2010. 10. 중부대학교 정보보호학과 이병천 교수 전자상거래보안 (c) Byoungcheon Lee, Joongbu Univ.

차례 1. 암호프로토콜이란? 2. 사례 2.1 동전던지기 게임 2.2 키합의 2.3 은닉서명 2.4 비밀 분산 2.5 영지식 증명 (c) Byoungcheon Lee, Joongbu Univ.

1. 암호 프로토콜이란? 프로토콜 암호 프로토콜 다자간에 특정 작업을 수행하기 위해 정해진 계산 및 통 신 절차 외교에서 사용되는 의전 절차 암호 프로토콜 암호기술을 사용하는 프로토콜 공개된 네트워크 환경에서 비대면 상황에서 신뢰할 수 없 는 상대들과 공정한 작업을 수행하기 위한 기술

암호알고리즘과 암호프로토콜 암호 알고리즘 암호 프로토콜 한 개체에 의해 수행되는 알고리즘 암호 기능을 수행하는 알고리즘 사례: 암호화, 해쉬, 전자서명 등 암호 프로토콜 복수의 개체들간에 특정 암호 기능을 수행하기 위해 정해 진 절차에 따라 수행되는 통신 프로토콜 신뢰할 수 없는 개체들간에 공정성을 담보하기 위한 기술 사례: 키합의, 비밀분산, 은닉서명, 게임 등 다자간의 복잡한 기능을 수행하기 위한 핵심 암호기술: 전자상거래, 전자투표, 전자경매 등

공정하게 빵 나누기 공평하게 빵을 나누려면?

통신 상대방을 믿을 수 있나? 시드니 셀던(Sidney Sheldon), “내일이 오면 (If Tomorrow Comes)” 사기꾼들의 이야기

암호프로토콜의 요구사항 공정성: 인증성: 정확성과 검증성: 프라이버시: 비대면 프로토콜에 참여하는 참여자들 사이에 어느 한쪽이 유리 하거나 불리하지 않도록 공정성을 보장해야 한다. 어느 한쪽이 불 리하다는 것이 알려지면 이런 비대면 프로토콜을 사용하려고 하 지 않을 것이다. 인증성: 비대면 프로토콜에서 상대방의 신분이 맞는지 주고받는 메시지가 위조되지는 않는지 확인할 수 있어야 한다. 상대방에 대한 신뢰는 프로토콜을 수행할 수 있는 가장 기본적인 전제가 된다. 정확성과 검증성: 통신 프로토콜을 통해 약속된 절차가 맞게 이루어지고 있는지 정 확성을 검증해 볼 수 있어야 한다. 프라이버시: 프로토콜 수행에 관한 정보가 제삼자에게 불필요하게 노출되지 않아야 한다. 이를 위해 암호화가 사용될 수 있다.

2. 암호프로토콜 사례 2.1 동전던지기 게임 2.2 키합의 2.3 은닉서명 2.4 비밀분산과 문턱암호 2.5 영지식 증명

2.1 인터넷으로 동전던지기 게임을? 인터넷상의 두 사람은 동전던지기 게임을 할 수 있 을까? A B 앞면, Alice 뒷면, Bob

인터넷으로 동전던지기 게임 블랙박스가 존재한다면? (한번 집어넣으면 마음대 로 열어볼 수 없고 내용을 바꿀 수도 없으며 나중 에 열어볼 수 있음) A는 임의의 숫자를 종이에 써서 블랙박스에 넣는다. 이 박스를 열 수 있는 키는 A만이 가지고 있다. 그리고 이 박스를 B에게 전송한다. B는 이 박스에 들어있는 숫자가 홀수인지, 짝수인지 추 측하여 A에게 말한다. A는 블랙박스를 열 수 있는 키를 B에게 제공한다. B는 블랙박스를 열어서 숫자를 확인한다. 홀수/짝수를 B가 맞추었으면 B가 이기는 것이고 아니면 A가 이기는 것이다.

인터넷으로 동전던지기 게임 해쉬함수를 이용한 동전던지기 A는 임의의 정수 x를 선택하여 이것의 해쉬값 H(x)를 계산하고 이 값을 B에게 전송한다. B는 정수 x가 홀수인지, 짝수인지 추측하여 A에게 말한 다. A는 원래의 정수 x를 B에게 전송한다. B는 H(x)를 계산하여 앞에서 받은 값과 같은지 확인한 다. 홀수/짝수를 B가 맞추었으면 B가 이기는 것이고 아 니면 A가 이기는 것이다. 앞면, Alice 뒷면, Bob

인터넷을 통한 동전던지기 게임 Alice Bob 전산망 2. B는 x가 짝수(앞면)인지 홀수(뒷면)인지 추측하여 A에게 통보 4. B는 y=f(x) 계산하여 확인 1. A는 랜덤한 수 x 를 선택하여 y=f(x) 계산 y를 B에게 전송 3. A는 x를 B에게 전송 y HEAD = x는 짝수 TAIL = x는 홀수 x

2.2 키합의 키합의: 만나지 않고도 비밀키를 공유할 수 있다 네트워크 상의 두 개체 A와 B가 암호알고리즘에 사용할 비밀키를 공유하는 방법 만나지 않고 공유하는 방법 Diffie-Hellman 프로토콜 이용

키합의 Diffie-Hellman의 키합의 A B (c) Byoungcheon Lee, Joongbu Univ.

키합의 (사례) Diffie-Hellman의 키합의 Entity A Entity B (c) Byoungcheon Lee, Joongbu Univ.

2.3 은닉서명 (Blind Signature) 사용자 A가 서명자 B에게 자신의 메시지를 보여주지 않 고 서명을 얻는 방법 메시지의 비밀성을 지키면서 타인의 인증을 받고자 하는 경우 사용 David Chaum 이 제안 은닉서명 응용 고객은 은행에서 전자화폐를 인출 투표자는 투표용지를 발급받음 (c) Byoungcheon Lee, Joongbu Univ.

은닉서명 비유 사용자 서명자 Signature Signature 1) 메시지를 먹지가 붙어있는 봉투에 넣어 보냄 2) 봉투위에 서명 Signature 3) 봉투를 열어서 서명된 메시지를 꺼냄

RSA 방식의 은닉서명 RSA 방식 은닉서명 사용자 A 서명자 B (c) Byoungcheon Lee, Joongbu Univ.

RSA 방식의 은닉서명 (사례) 은닉서명 구성 예 제공자 A 공개 정보 서명자 B r R Zn r = 6 n= 55, e = 7 서명자 B r R Zn r = 6 K1  reM mod n  67  5  40 mod 55   15 mod 55 n = p  q = 11  5 = 55  (n) =  (55) = 40 gcd (e,  (55)) = 1 e  d  1 mod  (n) d = 23 K2  K1d mod n  4023  35 mod 55 K1 = 40  Md mod 55 K2 = 35 (c) Byoungcheon Lee, Joongbu Univ.

2.4 비밀분산 중요한 비밀정보를 여러 개로 나눔 s1 s2 s3 sn 1 … shares … 2 3 n-1 n sn-1 … parties … 1 t-1 t 2 … Key Holes…

비밀분산과 문턱암호 필요성 비밀분산 문턱암호 매우 중요한 정보를 분산하여 보관해야 할 필요성 어느 한 사람의 결정으로 업무를 수행하기 보다 합의에 의해 업무를 수행 일부의 정보가 없어도 비밀정보를 복구 가능해야 함 예: 핵무기 발사, 루트인증기관의 키 보관 (예: 5명 중에 서 3명 이상이 합의하면 키복구 가능) 비밀분산 n명 중 t명 이상이 합의하면 복구할 수 있도록 키를 분산 문턱암호 n명 중 t명 이상이 합의하여 키를 복구하고 사용

비밀분산과 문턱암호 Shamir의 비밀분산 기법 Lagrange Interpolating Polynomial Scheme (t, n) 비밀 분산 n : share t 개 이상의 share가 모이면 정보 복원 가능 t – 1차 다항식 이용 (c) Byoungcheon Lee, Joongbu Univ.

비밀 분산 (계속) Lagrange Interpolating Polynomial Scheme 예 p = 17, K = 11일 때 a = 7, b = 8로 (3, 5) 구성 F(x) = ax2 + bx + K mod p K1 = F(1) = 712 + 8 1 + 11  9 mod 17 K2 = F(2) = 722 + 8 2 + 11  4 mod 17 K3 = F(3) = 732 + 8 3 + 11  13 mod 17 K4 = F(4) = 742 + 8 4 + 11  2 mod 17 K5 = F(5) = 752 + 8 5 + 11  5 mod 17 K1, K2, K3, K4, K5 : shadow (c) Byoungcheon Lee, Joongbu Univ.

비밀 분산 (계속) Lagrange Interpolating Polynomial Scheme 예 (계속) K2, K3, K4가 모이면 K = 11 복원 가능 K2 = a 22 + b 2 + K  4 mod 17 K3 = a 32 + b 3 + K  13 mod 17 K4 = a 42 + b 4 + K  2 mod 17 K 계산 가능 (c) Byoungcheon Lee, Joongbu Univ.

비밀 분산 (계속) 비밀키 K의 복구 방법 예: 인 경우 : 모여진 비밀값들의 집합 예: 인 경우 : 모여진 비밀값들의 집합 (c) Byoungcheon Lee, Joongbu Univ.

연습문제 Shamir의 비밀분산 예시 p=23, K=19일 경우 (5,7) 비밀분산 사례를 보여 라. 비밀값 분배: 7명에게 비밀값을 계산하여 분배하시오. 비밀값 복구: 5명이 모였다고 가정하고 비밀값 K를 계산 하시오.

2.5 영지식증명(Zero-knowledge Proof) 수학에서의 정리와 증명 자신이 주장하는 정리가 옳다는 것을 수학적으로 증명하 여 공개 피타고라스 정리 공개적인 증명 공개할 수 없는 증명 비밀정보는 한번 공개하면 더 이상 쓸 수 없음 알리바바와 40인의 도적 – 보물동굴의 문을 여는 암호

영지식증명(Zero-knowledge Proof) 내가 알고 있는 어떤 중요한 정보에 대하여 그것을 보여주지 않으면서 그것을 알고 있다는 것을 상대 방에게 증명해 보이는 방법 비밀정보를 노출시키지 않고 반복해서 사용하기 위한 방법

알리바바의 동굴 갑순이는 동굴의 문을 여는 암호를 알고 있지만 을돌이에게는 알려 주지 않고 자신이 암호를 알고 있다는 것을 증명하려고 한다. 을돌이는 동굴 입구에서 기다리게 하고 갑순이는 갈라지는 지점에서 A 또 는 B의 방향으로 임의로 선택하여 들어가서 비밀문 앞으로 간다. 이때 을돌 이는 갑순이가 어느 방향으로 갔는지 알 수 없다. 을돌이는 동굴이 갈라지는 지점까지 와서 갑순이에게 A 또는 B의 어느 한 방향으로 나오도록 큰 소리로 말한다. 갑순이는 을돌이의 요구에 따라 A 또는 B의 방향으로 을돌이에게 간다. 갑 순이는 필요한 경우 암호를 이용하여 비밀문을 열고 반대편으로 갈 수 있다. 1~3의 게임을 을돌이가 동의할 때까지 n회 반복한다.

이산대수값을 알고 있다는 것을 증명 증명자 A는 다음의 이산대수값 x를 알고 있다는 것을 x를 노출시키지 않고 증명하고자 함 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

^ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 (c) Byoungcheon Lee, Joongbu Univ.

사례 암호시스템 파라메터 p=23, g=7, q=22 키생성 x=13, y=20 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.