공개키 암호화 프로그래밍 전자상거래보안

차례 1. 잉여계에서의 사칙연산 2. Java.math.BigInteger 클래스 이용하기 모듈러승산 계산 (Square-and-Multiply 알고리즘) 모듈러승산 테이블 만들기 두 수의 최대공약수 계산 확장유클리드 알고리즘으로 역수 계산 2. Java.math.BigInteger 클래스 이용하기 BigInteger 클래스를 이용한 사칙연산 RSA 알고리즘 구현 ElGamal 알고리즘 구현 Schnorr 서명 알고리즘 구현

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

모듈러 승산 테이블 만들기

두 수의 최대공약수 계산 ======= 최대공약수 ======= 첫 번째 자연수 >> 13 두 번째 자연수 >> 65 최대공약수: 13

확장 유클리드 알고리즘

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

모듈러 연산 r=a.gcd(b); // a와 b의 최대공약수 System.out.println("gcd("+a+","+b+") = "+r); r=a.modPow(b, p); // a^b mod p System.out.println(a+"^"+b+" mod "+p+" = "+r); r=a.modInverse(p); // a^{-1} mod p System.out.println(a+"^-1 mod "+p+" = "+r); BigInteger r; r=a.add(b).mod(p); // a+b mod p System.out.println(a+" + "+b+" mod "+p+" = "+r); r=a.subtract(b).mod(p); // a-b mod p System.out.println(a+" - "+b+" mod "+p+" = "+r); r=a.multiply(b).mod(p); // a*b mod p System.out.println(a+" * "+b+" mod "+p+" = "+r); r=a.divide(b).mod(p); // a/b mod p System.out.println(a+" / "+b+" mod "+p+" = "+r+" ???"); r=a.multiply(b.modInverse(p)).mod(p); // a*b^{-1} mod p System.out.println(a+" * "+b+"^(-1) mod "+p+" = "+r);

RSA 알고리즘 특정 비트수의 임의의 소수 p, q 생성 키생성 BigInteger one = new BigInteger("1"); Random rnd = new Random(); int bitLength = 1024; 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("q = "+q); BigInteger n = p.multiply(q); System.out.println("n = p*q = "+n); BigInteger pin = (p.subtract(one)).multiply(q.subtract(one)); System.out.println("pi(n) = (p-1)*(q-1) = "+pin); BigInteger e = new BigInteger("17"); System.out.println("e = "+e); System.out.println("gcd(pin,e) = "+pin.gcd(e)); BigInteger d = e.modInverse(pin); System.out.println("d = "+d); System.out.println(" ");

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

ElGamal 암호 이산대수 문제의 어려움을 이용하는 공개키 암호 y  gx mod p g : 원시원소 p : 소수 y 가 주어졌을 때 x를 구하는 문제

ElGamal 암호 방식 (계속) 이산대수 문제 예 Z23 51  5 58  16 515  19 mod 23 18은 5의 몇제곱수인가? - 12 위 표가 없다면 어떻게 알아낼 수 있겠는가?

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

ElGamal 암호 이산대수 문제의 어려움을 이용하는 공개키 암호

ElGamal 암호 1. 키생성 (Key Generation) q의 비트수를 입력하세요 (1000비트 이하)>> 100 q = 893969986680457324918139484461 소수 p = 2*q+1 p = 1787939973360914649836278968923 생성자 g는 g^q mod p != 1 인 수를 선정 g = 820174849967448717361379355251 개인키 x 는 임의로 선정 x = 1081656356240988029513654036663 공개키 y = g^x mod p y = 1494755450936895767639472657831 2. 암호화 (Encryption) 평문을 정수로 입력하세요 >>> 11111111111111 평문 M = 11111111111111 암호문 C1 = 1067955265774527936773629838650 암호문 C2 = 1257089196493716866579637835696 3. 복호화 (Decryption) 복호화된 평문 M = C2/C1^x mod p = 11111111111111

ElGamal 암호 좋은 소수 p 선택하기 생성자 g 찾기 소수 q를 선택. p=2q+1가 소수가 되는 경우를 찾음 난수 g를 선택하여 g^q mod p=1이 되는 수를 찾음 q = new BigInteger(bitLength, certainty, sr); // 첫번째 난수 do { p = q.multiply(two).add(one); if (p.isProbablePrime(1)) break; q = q.nextProbablePrime(); i++; } while (i<20); do { g = new BigInteger(bitLength, certainty, sr); if (!g.modPow(q, p).equals(one)) break; i++; } while (i<50);

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

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 서명 키생성 비밀키 xA 공개키 yA 서명 생성 는 m에 대한 서명 서명 검증

Schnorr 서명 1. 키생성 (Key Generation) q의 비트수를 입력하세요 (160)>> 30 p의 비트수를 입력하세요 (1024)>> 200 q = 785862709 loop = 71 p = 1575099955074729996735332870937559098373766739284997582249719 loop = 0 g = 904745875750278837202552822475586867599799335382239195889315 q|p-1 = 0 g^q mod p = 1 A의 개인키 = 256509342 A의 공개키 = 628276971617374031391797654344696306789765741109045988839154 2. 서명 생성 (Signing) 서명 = (m,U,V) m = This is a simple message for Schnorr signature. U = 336458072206080794537988899705062618778221672594125041907512 V = 489378877 3. 서명 검증 (Signature Verification) Left = 640040391421324111978016650741331607405215793265975221490882 Right = 640040391421324111978016650741331607405215793265975221490882 Schnorr signature is valid