자바 암호 프로그래밍 Java Cryptography Programming

Slides:



Advertisements
Similar presentations
멘토링 2 주차 장 프로그래밍을 위한 자바의 자료형  값이 변하지 않는 상수  메모리 기억공간인 변수.
Advertisements

5 장 조건과 반복 ②. Contents Counting and Looping [while 문 사용 ] Powers of 2 [while 문 사용 ] More Guessing [do 문 사용 ] Election Day [do 문 사용 ] Finding Maximum &
명품 JAVA Programming 제 3 장 반복문, 배열, 예외처리.
어서와 Java는 처음이지! 제3장선택과 반복.
15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
제 7주 2015년 1학기 강원대학교 컴퓨터학부 담당교수: 정충교
컴퓨터 응용 및 실습 Part1. OOP&Java Programming data type Review
Recursion SANGJI University KO Kwangman
IntArray[0] int length 5 intArray 객체 제 3 장 반복문, 배열, 예외처리.
현대암호편: RC5,ElGamal,Rabin
어서와 Java는 처음이지! 제2장 자바 프로그래밍 기초.
7장 배열 ②.
어서와 Java는 처음이지! 제4장 배열.
Java Seminar 6.
제 4장 문 장 배정문 혼합문 제어문 표준 입출력.
제 5 장 암호학의 수학기초 Network Security Lab Mun Hyung Jin.
자바란 무엇인가? JDK의 다운로드 및 설치 방법 Hello, Java 프로그램의 작성 자바 프로그램의 작동 원리
윤 홍 란 제3장 클래스와 객체의 사용-1 윤 홍 란
Chapter 02 자바 기본구조 자바 프로그래밍의 기초적인 문법을 소개
[INA470] Java Programming Youn-Hee Han
명품 JAVA Programming 제 7 장 제네릭과 컬렉션.
명품 JAVA Essential.
명품 JAVA Essential.
명품 JAVA Programming 제 4 장 클래스와 객체.
Power Java 제4장 자바 프로그래밍 기초.
1.정보보호 개론(1).
Power Java 제10장 배열.
암호프로토콜 중부대학교 정보보호학과 이병천 교수 전자상거래보안
객체지향 언어와 클래스, 객체 ㅎㅎ 개요 클래스의 선언, 객체의 생성 및 속성 참조 방식 멤버 변수 메소드 한빛미디어(주)
Choi, Namseok Java 기초 (Java의 제어문과 배열) Choi, Namseok
08장 암호의 이해: 숨기고자 하는 이들의 싸움.
명품 JAVA Essential.
명품 Java Programming.
2장 자바환경과 자바 프로그램 2.1 자바 개발 환경 2.2 자바 통합환경 2.3 자바 응용 프로그램과 애플릿 프로그램
2주차 – 수학적 배경 주교재 2장.
공개키 암호화 프로그래밍 전자상거래보안.
5장 조건과 반복 ①.
주소록 프로그램.
6장 객체-지향 설계 ①.
제 4주 2014년 1학기 강원대학교 컴퓨터학부 담당교수: 정충교
12 검색.
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
3. while문 반복문의 종류 while 문 while( 조건식 )        문장;.
5장 조건과 반복 ②.
제2장 데이터 및 수식.
6장 객체-지향 설계 ①.
어서와 Java는 처음이지! 제4장 배열 IT응용시스템공학과 김형진 교수.
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
03. 안드로이드를 위한 Java 문법 제목. 03. 안드로이드를 위한 Java 문법 제목.
WAP Java Seminar
Ch.1 Iterator Pattern <<interface>> Aggregate +iterator
[INA470] Java Programming Youn-Hee Han
자바 암호 프로그래밍 Java Cryptography Programming
[INA470] Java Programming Youn-Hee Han
자바 5.0 프로그래밍.
5장 조건과 반복 ①.
제 5장 공개키 암호.
Chapter 02. 소프트웨어와 자료구조.
Java 3장. 자바의 기본 구조 I : 변수, 자료형, 연산자 public class SumTest {
JVM의 구조와 메모리 모델 JVM의 내부 구조 클래스 파일 클래스 로더 메소드(method) 영역 힙(heap) 영역
자바 암호 프로그래밍 Java Cryptography Programming
Chapter 4 공개키 암호 Knapsack RSA Diffie-Hellman 키 교환 방식
컴퓨터 프로그래밍: 실습 1 제 1장 . 서론.
Chapter 3. Public Key Infrastructure
정보보호 개론 Chapter 04 암호화 기술.
자바 암호 프로그래밍 Java Cryptography Programming
제 1장 프로그래밍 언어 소개 1.1 프로그래밍 언어란 무엇인가 1.2 프로그래밍 언어를 배워야 하는 이유
Choi Younghwan CSE HUFS
Chapter8 : 인터페이스와 패키지 8.1 인터페이스 개요와 인터페이스 정의 8.2 인터페이스의 사용
(c) Byoungcheon Lee, Joongbu Univ.
Presentation transcript:

자바 암호 프로그래밍 Java Cryptography Programming 2017. 3. 중부대학교 정보보호학과 이병천 교수

차례 1. 강의 개요 2. 자바프로그래밍 기초 3. 자바 네트워크 프로그래밍 4. 자바 GUI 프로그래밍 5. JCA/JCE 암호 프로그래밍 6. 해쉬함수, MAC, 패스워드 기반 키생성 7. 대칭키 암호, 파일 암호화/복호화 8. 공개키 암호 9. 전자서명 10. 인증서와 공개키기반구조(PKI) 11. 암호 알고리즘/프로토콜 구현

11. 암호 알고리즘/프로토콜 구현

공부의 목표 RSA 알고리즘의 동작을 직접 테스트해보자. JCA/JCE에 구현되어 있지 않은 암호 알고리즘을 직접 구 현해보자.

차례 1. 잉여계에서의 사칙연산 2. Java.math.BigInteger 클래스 3. 암호 알고리즘 구현 잉여계와 모듈러 연산 최대공약수, 역수 계산 모듈러승산 테이블 만들기 2. Java.math.BigInteger 클래스 큰 수들의 사칙연산 3. 암호 알고리즘 구현 RSA 알고리즘 구현 ElGamal 알고리즘 구현 Schnorr 서명 알고리즘 구현 4. 암호 프로토콜 구현 디피-헬만 키 합의 (Diffie-Hellman Key Agreement) 은닉서명 (Blind Signature) 영지식증명 (Zero-knowledge Proof)

1. 잉여계에서의 사칙연산 잉여계와 모듈러 연산 최대공약수 계산 역수 계산 모듈러승산 테이블 만들기

모듈러 연산 (Modular Arithmetic) 모듈러스로 나누어 나머지만 취하는 연산 공개키 암호의 기반이 되는 수학 시계에서의 mod 6 연산 7 mod 6 = 1 10 mod 6 = 4 100분 = 1시간 40분 2 1 5 4 3 arithmetic mod 6

잉여계와 모듈러 연산 잉여계 (residue system) 모듈러 연산 (modular arithmetic) 모듈러스를 소수로 선택해야 사칙연산이 가능. Z7 = {0,1,2,3,4,5,6}에서의 덧셈, 뺄셈, 곱셈, 나눗셈은 a+b (mod 7), a-b (mod 7), axb (mod 7), a/b (mod 7) 로 계산한다. 4+6 mod 7 = 3 3-5 mod 7 = -2+7 = 5 4x5 mod 7 = 6 a의 역수는 ab (mod 7) = 1 이 만족되는 숫자 b 4와 2는 서로 역수 (4x2 mod 7 = 1) 3과 5는 서로 역수 (3x5 mod 7 = 1) 1의 역수는 1 (1x1 mod 7 = 1) 6의 역수는 6 (6x6 mod 7 = 1) 나눗셈을 하려면 먼저 분모의 역수를 구하여 분자에 곱해준다. 3/4 mod 7 = 3x2 mod 7 = 6 (4의 역수는 2, 4x2 mod 7 = 1)

두 정수의 최대공약수 계산 최대공약수란? 예제: a=510과 b=62의 최대 공약수를 구하라 두 수의 약수란 두 수를 모두 나누는 수 최대공약수란 약수 중에서 가장 큰 수 유클리드의 호제법 (Euclidean algorithm)을 이용 예제: a=510과 b=62의 최대 공약수를 구하라 최대공약수는 2가 된다.

최대공약수 계산하기 예제: GCD.java 임의의 두 정수를 입력하시오>> 45 80 최대 공약수는 5 임의의 두 정수를 입력하시오>> 46 24 최대 공약수는 2 임의의 두 정수를 입력하시오>> 54 71 최대 공약수는 1 import java.util.Scanner; public class GCD { public static void main (String[] args) { Scanner sin = new Scanner(System.in); System.out.print("임의의 두 정수를 입력하시오>> "); int num1 = sin.nextInt(); int num2 = sin.nextInt(); int divisor, remainder; if (num1 < num2) { // num1이 큰 수, num2가 작은 수가 되게 한다. int tmp = num2; num2 = num1; num1 = tmp; } divisor= num2; // 작은 수를 나눗수로 한다. while ((remainder = num1 % divisor) != 0) { //0으로 나누어 떨어지면 나눗수가 최대 공약수 num1 = divisor; // 나눗수를 나뉨수로 한다. divisor = remainder; // 나머지를 나눗수로 한다. System.out.println("최대 공약수는 " + divisor);

역수 계산하기 a^(-1) mod n 계산하기 법 n(=1759)에서 a(=550)의 곱셈에 대한 역수를 구하라. ab mod n = 1인 정수 b를 구하는 문제 a와 n이 서로 소인 경우에만 역수를 계산할 수 있음 확장유클리드 (Extended Euclid) 알고리즘 이용 법 n(=1759)에서 a(=550)의 곱셈에 대한 역수를 구하라. 550∙355 + 1759∙(-111) ≡ 1 mod 1759 550^(-1) mod 1759 = 355

역수 계산하기 예제: ExtendedEuclid.java 122^(-1) mod 321 = 50 ======= 확장유클리드 알고리즘 계산 ======= 첫 번째 자연수 >> 3243 두 번째 자연수 >> 24334 gcd(3243, 24334) = 23 -15(3243) + 2(24334) = 23 첫 번째 자연수 >> 122 두 번째 자연수 >> 321 gcd(122, 321) = 1 50(122) + -19(321) = 1 122^(-1) mod 321 = 50

모듈러 승산 알고리즘 RSA 암호화, 복호화는 모듈러 승산으로 계산 고속승산알고리즘 (Square and Multiply) 이용

모듈러 승산 알고리즘 예제: SquareMultiply.java ======= a^b mod p 계산 ======= import java.util.Scanner; public class SquareMultiply { public static void main(String[] args) { Scanner s = new Scanner(System.in); System.out.println("======= a^b mod p 계산 ======="); System.out.print("a = "); int a = s.nextInt(); System.out.print("b = "); int b = s.nextInt(); System.out.print("p = "); int p = s.nextInt(); long x=1; long y=a; while(b > 0){ if(b%2 == 1) x=(x*y)%p; y = (y*y)%p; // squaring the base b /= 2; } long ans=x%p; System.out.print("답 = "+ans); ======= a^b mod p 계산 ======= a = 39 b = 41 p = 11 답 = 6

Z23에서의 모듈러 승산 테이블 ^ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1

모듈러 승산 테이블 만들기 예제: ExpTable.java // a^b mod c 를 계산하는 함수 public static int modulo(int a, int b, int c) { long x=1; long y=a; // Square-and-Multiply 방법을 이용 while(b > 0){ if(b%2 == 1){ // bit가 1이면 a를 곱해줌 x=(x*y)%c; } y = (y*y)%c; // 제곱을 계산 b /= 2; return (int) x%c; Scanner sc = new Scanner(System.in); System.out.println("모듈러 승산 테이블 만들기"); System.out.print("modulus로 사용할 소수를 선택하세요>> "); int p = sc.nextInt(); int i, j, k; System.out.println(); System.out.printf("Modulus = %d \n\n", p); System.out.printf(" ^"); for (i=1; i<p; i++) { System.out.printf("%4d", i); } System.out.printf("\n"); for (j=1;j<p;j++) { k = modulo(i,j,p); System.out.printf("%4d",k);

2. BigInteger 클래스 Java.math.BigInteger 소수 생성 매우 큰 자릿수의 정수연산을 구현한 클래스 공개키 암호 등에 유용하게 이용됨 소수 생성 BigInteger p = b.nextProbablePrime(); b보다 큰 첫 번째 소수를 출력 BigInteger c = BigInteger.probablePrime(bit,rnd); 특정 비트수의 임의의 소수 생성

모듈러 연산 예제: BIMath.java r=a.gcd(b); // r=gcd(a,b) System.out.println("gcd("+a+","+b+") = "+r); r=a.modPow(b, p); // r=a^b mod p System.out.println(a+"^"+b+" mod "+p+" = "+r); int k=a.bitLength(); System.out.println(a+"의 비트수 = "+k+" bit"); BigInteger r; r=a.add(b).mod(p); // r=a+b mod p System.out.println(a+" + "+b+" mod "+p+" = "+r); r=a.subtract(b).mod(p); // r=a-b mod p System.out.println(a+" - "+b+" mod "+p+" = "+r); r=a.multiply(b).mod(p); // r=a*b mod p System.out.println(a+" * "+b+" mod "+p+" = "+r); r=a.divide(b).mod(p); // r=a/b mod p System.out.println(a+" / "+b+" mod "+p+" = "+r+" ??? 이렇게 계산하면 안됨!"); r=b.modInverse(p); // r=b^(-1) mod p System.out.println(b+"^(-1) mod "+p+" = "+r); r=a.multiply(b.modInverse(p)).mod(p); // r=a/b mod p System.out.println(a+" * "+b+"^(-1) mod "+p+" = "+r);

모듈러 연산 예제: BIMath.java ======= 두개의 숫자를 고르세요 ======= 첫 번째 자연수 a = 321 ======= 두개의 숫자를 고르세요 ======= 첫 번째 자연수 a = 321 두 번째 자연수 b = 123 123보다 큰 첫번째 소수 p = 127 321 + 123 mod 127 = 63 321 - 123 mod 127 = 71 321 * 123 mod 127 = 113 321 / 123 mod 127 = 2 ??? 이렇게 계산하면 안됨! 123^(-1) mod 127 = 95 321 * 123^(-1) mod 127 = 15 gcd(321,123) = 3 321^123 mod 127 = 80 321의 비트수 = 9 bit 임의 길이의 소수 생성하기 소수를 생성할 비트수 = 100 100비트 소수 생성 = 882515581098361764902971014803

3. 암호 알고리즘 구현 RSA 공개키 암호 ElGamal 공개키 암호 Schnorr 서명

NP-problem (nondeterministic polynomial time) 소인수분해 문제(Factorization Problem) 주어진 합성수 n의 소인수들을 찾는 문제, n의 자리수가 매우 큰 경우(10150이상)에는 n의 소인수를 효율적으로 찾는 알고리즘이 아직까지 존재하지 않음 이산대수 문제(Discrete Logarithm Problem) 소수 p가 주어지고 y = gx (mod p)인 경우,  역으로 x = loggy·(mod p)인 x를 계산하는 문제,  여기서 x를 법 p상의 y의 이산대수라 하고, y, g, p가 주어졌을 때, x를 구하는 문제는 어려움.    

RSA 알고리즘 RSA 알고리즘 키생성 암호화 복호화

RSA 알고리즘 특정 비트수의 임의의 소수 p, q 생성 키생성 BigInteger one = new BigInteger("1"); Random rnd = new Random(); int bitLength = 1024; // RSA 키 길이 int certainty = 10; BigInteger p = new BigInteger(bitLength/2, certainty, rnd); BigInteger q = new BigInteger(bitLength/2, certainty, rnd); 키생성 System.out.println("Key Generation"); System.out.println("p = "+p); System.out.println("p의 bit수 = "+p.bitLength()); System.out.println("q = "+q); System.out.println("q의 bit수 = "+q.bitLength()); BigInteger n = p.multiply(q); // n=p*q System.out.println("n = p*q = "+n); System.out.println("n의 bit수 = "+n.bitLength()); BigInteger pin = (p.subtract(one)).multiply(q.subtract(one)); // pin = (p-1)(q-1) System.out.println("pi(n) = (p-1)*(q-1) = "+pin); BigInteger e = new BigInteger("65537"); // e는 고정된 값 이용: 2^1+1=3, 2^2+1=5, 2^4+1=17, 2^16+1=65,537 System.out.println("e = "+e); // gcd(pin,e)=1이 되어야 함. 이것이 만족하지 않는 경우 n을 다시 선택... System.out.println("gcd(pin,e) = "+pin.gcd(e)); BigInteger d = e.modInverse(pin); // d = e^(-1) mod pi(n) System.out.println("d = "+d); System.out.println();

RSA 알고리즘 암호화 복호화 // Encryption System.out.println("Encryption"); BigInteger m = new BigInteger("1111111111111111112222222"); // message System.out.println("Plaintext: m = "+m); BigInteger c = m.modPow(e, n); System.out.println("ciphertext: c = m^e mod n = "+c); System.out.println(); // Decryption System.out.println("Decryption"); BigInteger mm = c.modPow(d, n); System.out.println("Recoverd: m = c^d mod n = "+mm);

RSA 알고리즘 예제: RSABI.java

ElGamal 암호 이산대수문제의 어려움을 이용하는 공개키 암호 이산대수문제(Discrete Logarithm problem, DLP) g, p, y 가 주어졌을 때 x를 구하는 문제

이산대수문제 이산대수 문제의 예 Z23 51  5 58  16 515  19 mod 23 18은 5의 몇제곱수인가?  12 위 표가 없다면 어떻게 알아낼 수 있겠는가?

Z23의 모듈러 승산표

ElGamal 암호 키생성 (수신자) 암호화 (송신자) 복호화 (수신자) RSA와의 비교 큰 소수 p를 선택하고 생성자 g를 선택. 비밀키 x를 선택하고 공개키 y = g^x mod p를 계산. 공개키: [y, g, p], 개인키: x 암호화 (송신자) 메시지 m을 암호화하기 위해 난수 k 선택 r = g^k mod p, s = m y^k mod p 암호문 [r, s]를 수신자에게 전달 복호화 (수신자) m = s/r^x mod p 로 메시지 복구 RSA와의 비교 난수를 이용하므로 암호문이 난수화됨 (RSA 암호화의 경우 동일한 암호문이 출력되므로 난수화 패딩 적용 필요) 암호문의 길이가 메시지의 2배가 됨

ElGamal 암호 송신자(A) 수신자(B) 공개키 𝑦를 공개 𝑥 ∈ 𝑅 𝑍 𝑝−1 𝑦= 𝑔 𝑥 𝑚𝑜𝑑 𝑝 키생성 𝑥 ∈ 𝑅 𝑍 𝑝−1 𝑦= 𝑔 𝑥 𝑚𝑜𝑑 𝑝 키생성 𝑘 ∈ 𝑅 𝑍 𝑝−1 𝑟= 𝑔 𝑘 𝑚𝑜𝑑 𝑝 𝑠=𝑚 𝑦 𝑘 𝑚𝑜𝑑 𝑝 암호화 𝑟,𝑠 𝑠 𝑟 𝑥 𝑚𝑜𝑑 𝑝=𝑚 복호화 𝑦 𝑘 𝑚𝑜𝑑 𝑝= 𝑟 𝑥 𝑚𝑜𝑑 𝑝= 𝑔 𝑘𝑥 𝑚𝑜𝑑 𝑝 송신자와 수신자가 공유하는 비밀정보를 이용하여 메시지를 숨김

예제: ElGamalBI.java 1. 키생성 (Key Generation) q의 비트수를 입력하세요 (1000비트 이하)>> 100 loop = 116 q = 660538669937162329671019445669 소수 p = 2*q+1 = 1321077339874324659342038891339 p의 bit수 = 101 생성자 g는 g^q mod p = 1 인 수를 선정 loop = 2 g = 796917503013762129604435956421 개인키 x 는 임의로 선정 x = 655581759845177090865858884653 공개키 y = g^x mod p y = 230937086949196817004209073889 2. 암호화 (Encryption) 평문을 정수로 입력하세요 >>> 111111111 평문 M = 111111111 암호문 C1 = 806871049416881996688977785189 암호문 C2 = 436817157945620804697925816413 3. 복호화 (Decryption) 복호화된 평문 M = C2/C1^x mod p = 111111111

ElGamal 암호 안전한 소수 p 선택 생성자 g 선택 소수 q에 대하여 p=2q+1인 p가 소수가 되도록 선택 g^q mod p = 1 이 되도록 g를 선택 q = new BigInteger(bitLength, certainty, sr); // 첫번째 난수 i=0; do { p = q.multiply(two).add(one); // p = 2*q+1 을 계산 if (p.isProbablePrime(certainty)) break; // p가 소수인지 검사 q = q.nextProbablePrime(); // 다음 소수 q를 선택하여 다시 시도 i++; } while (true); i=0; do { g = new BigInteger(bitLength, certainty, sr); // 생성자 g를 소수 난수로 선택 if (g.modPow(q, p).equals(one)) break; // g^q mod p = 1 인지 검사 i++; } while (true);

ElGamal 암호 개인키 x는 난수로 선택 공개키는 y=g^x mod p 계산 x = new BigInteger(bitLength, certainty, sr); // 개인키 x를 난수로 선택 y = g.modPow(x, p); // 공개키 계산 y=g^x mod p System.out.println("개인키 x 는 임의로 선정 "); System.out.println("x = "+x); System.out.println("공개키 y = g^x mod p "); System.out.println("y = "+y); System.out.println();

ElGamal 암호 암호화 복호화 // ------------------- 암호화 ---------------------- System.out.println("\n2. 암호화 (Encryption) "); BigInteger M, C1, C2, k; System.out.print("평문을 정수로 입력하세요 >>> "); M = s.nextBigInteger(); k = new BigInteger(bitLength, certainty, sr); C1 = g.modPow(k, p); C2 = y.modPow(k, p).multiply(M).mod(p); System.out.println("평문 M = "+M); System.out.println("암호문 C1 = "+C1); System.out.println("암호문 C2 = "+C2); // ------------------- 복호화 ---------------------- System.out.println("\n3. 복호화 (Decryption) "); BigInteger temp = C1.modPow(x,p); BigInteger MM = C2.multiply(temp.modInverse(p)).mod(p); System.out.println("복호화된 평문 M = C2/C1^x mod p = "+MM);

Schnorr 서명 이산대수 기반의 전자서명 안전성이 증명된 간단한 전자서명 Schnorr group (안전한 그룹) q: (p-1)/2을 나누는 작은 사이즈의 소수 (160비트) p=q*r+1 을 만족하는 q 찾기 g: 위수가 q인 생성자 h^r mod p 가 1이 아닌 어떤 수 h를 선택 g=h^r mod p 를 생성자로 선택 Claus-Peter Schnorr

Schnorr 서명 키생성 비밀키 xA 공개키 yA 서명 생성 는 m에 대한 서명 서명 검증

Schnorr 서명 서명자 검증자 공개키 𝑦를 공개 𝑥 ∈ 𝑅 𝑍 𝑞 𝑦= 𝑔 𝑥 𝑚𝑜𝑑 𝑝 키생성 𝑘 ∈ 𝑅 𝑍 𝑝−1 𝑥 ∈ 𝑅 𝑍 𝑞 𝑦= 𝑔 𝑥 𝑚𝑜𝑑 𝑝 키생성 𝑘 ∈ 𝑅 𝑍 𝑝−1 𝑈= 𝑔 𝑘 𝑚𝑜𝑑 𝑝 𝑉=(𝑘+𝑥𝐻 𝑚,𝑈 )𝑚𝑜𝑑 𝑞 서명생성 𝑈,𝑉 서명검증 𝑔 𝑉 𝑚𝑜𝑑 𝑝=?𝑈 𝑦 𝐻(𝑚,𝑈)

예제: SchnorrSig.java

Schnorr 서명 안전한 파라메터 p, q 생성 생성자 g 선택 q: 160 bit 소수 p: 1024 bit 소수 p-1|q=0 (p-1을 q로 나누어 떨어지는 수 p를 선택) 생성자 g 선택 g^q mod p = 1 을 만족하는 g 선택

비밀서명 (Secret Signature) 일반 전자서명 서명은 공개된 정보임. 서명자가 개인키를 이용하여 생성한 것이며 서명자의 공개키를 알고 있으면 누구나 유효성 검증 가능 비밀서명(secret signature) 서명자가 특정 수신자만 검증할 수 있도록 서명을 생성 서명자는 자신의 개인키와 수신자의 공개키를 이용하여 서명 생성 수신자는 자신의 개인키와 송신자의 공개키를 이용하여 서명 검증 송신자, 수신자간의 개인적인 업무에 사용 가능 필요시 제3자에게 비밀서명의 유효성을 증명할 수 있음

http://cris.joongbu.ac.kr/publication/SS-WISA2007.pdf

비밀서명 𝑊= 𝑦 𝐵 𝑘 𝑚𝑜𝑑 𝑝 = 𝑈 𝑥 𝐵 𝑚𝑜𝑑 𝑝 서명자 A 검증자 B 𝑥 𝐴 ∈ 𝑅 𝑍 𝑞 공개키 𝑦 𝐴 , 𝑦 𝐵 를 공개 𝑥 𝐴 ∈ 𝑅 𝑍 𝑞 𝑦 𝐴 = 𝑔 𝑥 𝐴 𝑚𝑜𝑑 𝑝 𝑥 𝐵 ∈ 𝑅 𝑍 𝑞 𝑦 𝐵 = 𝑔 𝑥 𝐵 𝑚𝑜𝑑 𝑝 키생성 𝑘 ∈ 𝑅 𝑍 𝑝−1 𝑈= 𝑔 𝑘 𝑚𝑜𝑑 𝑝 𝑊= 𝑦 𝐵 𝑘 𝑚𝑜𝑑 𝑝 𝑉=(𝑘+ 𝑥 𝐵 𝐻 𝑚,𝑈,𝑊 )𝑚𝑜𝑑 𝑞 𝑚,𝑈,𝑉 서명생성 𝑊= 𝑈 𝑥 𝐵 𝑚𝑜𝑑 𝑝 𝑔 𝑉 𝑚𝑜𝑑 𝑝=?𝑈 𝑦 𝐵 𝐻(𝑚,𝑈,𝑊) 서명검증 𝑊= 𝑦 𝐵 𝑘 𝑚𝑜𝑑 𝑝 = 𝑈 𝑥 𝐵 𝑚𝑜𝑑 𝑝 서명자 A와 검증자 B가 공유하는 비밀정보

예제: SecretSig.java

4. 암호 프로토콜 구현 디피-헬만 키 합의 (Diffie-Hellman Key Agreement) 은닉서명 (Blind Signature) 영지식증명 (Zero-knowledge Proof)

키 합의 (Diffie-Hellman Key Agreement) 디피-헬만 키합의 비밀채널을 이용하지 않고도 키를 안전하게 합의하는 방법 SSL/TLS에서 브라우저와 서버 사이의 비밀채널 생성에 사용

예제: DH.java

은닉서명 (Blind Signature) 은닉서명이란? 사용자 A가 서명자 B에게 자신의 메시지를 보여주지 않고 서명 을 얻는 방법 메시지의 비밀성을 지키면서 타인의 인증을 받기 위해 사용 1982년 David Chaum이 제안 응용분야 고객이 은행에서 전자화폐를 인출 소유자가 누구인지 모르도록 서명된 화폐를 발행 투표자가 투표용지를 발급받음 투표자의 기표 내용은 볼 수 없는 상태에서 선거관리자는 투표용지에 서명함

전자화폐 발행

은닉서명 (Blind Signature) RSA 기반 은닉서명

예제: BlindSig.java

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

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

영지식증명 알리바바와 40인의 도적 암호 보안 실패 영지식증명을 위한 가상실험

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

이산대수값을 알고 있다는 것을 증명 𝑌= 𝑔 𝑥 𝑚𝑜𝑑 𝑝, 𝑥= log 𝑔 𝑌 𝑚𝑜𝑑 𝑝 증명자 A는 공개키 y에 대한 개인키 x를 알고 있다는 것 을 x를 노출시키지 않고 증명하고자 함 𝑌= 𝑔 𝑥 𝑚𝑜𝑑 𝑝, 𝑥= log 𝑔 𝑌 𝑚𝑜𝑑 𝑝

예제: ZKPSchnorr.java

상호 통신이 필요 없는 영지식증명 상호 통신의 부담을 줄이는 영지식증명 Non-interactive Zero-knowledge (NIZK) proofs using Fiat- Shamir Heuristics Challenge u값을 해쉬함수를 이용하여 선택 증명자가 검증자를 속이려면 해쉬값을 조작할 수 있어야 함 개인키를 이용한 서버 로그인에 사용 가능

예제: ZKPSchnorrNI.java

Q&A 한 학기 동안 수고 많았습니다.