현대암호편: RC5,ElGamal,Rabin 곽인범

RC5 - 배경 1994년 RSA Security사의 Ronald Rivest에 의해 고안됨. 보안제품 BSAFE, JSAFE, S/MAIL등에 사용

RC5 – 특성(1/3) 블록 암호 다양한 크기의 키, 블록, 라운드를 가질 수 있다. 다른 블록 암호화 알고리즘들과 달리 라운드도 가변적임. 블록의 크기는 32, 64, 128 비트. 키의 크기는 0~2040 비트. 라운드는 0~255회. 하드웨어 및 소프트웨어에의 적합성 ->CPU에서 일반적으로 사용되는 기본 연산만 사용

RC5 – 특성(2/3) 빠른 속도 ->간단한 알고리즘을 사용 ->기본 연산이 한번에 full word를 처리 단순성 ->간단한 구조로 구현이 용이 ->알고리즘 강도 결정(보안 허점 탐지)이 용이

RC5 – 특성(3/3) 데이터 의존적인 순환 이동 ->데이터의 양에 따라 결정되는 회전 이동(순환비트이동)을 채용 ->알고리즘 강도에 기여 낮은 메모리 요구량 ->스마트 카드나 한정된 메모리를 사용하는 장치에 적당

RC5 – 알고리즘(키 확장[1/2]) t 개의 서브키(w 비트 단위) 개념 - 각 라운드별 2 개의 서브키 + 별도 연산적용 2 개 (t=2r+2); S[0], S[1], … S[t-1] 배열 S의 초기화 - S[0]=Pw; for i=1 to t-1 do S[i]=S[i-1] + Qw; - Pw, Qw : 2 단어 길이의 상수 키 변환 - ‘b’ byte 키 K[0], …, K[b-1] 를 ‘c’ word 배열 L[0], …L[c-1]로 변환 (byte -> word) 최종 배열 S생성 - L의 내용을 S의 초기화된 값 에 혼합(Mix) 연산 수행

RC5 – 알고리즘(키 확장[2/2])

RC5 – 알고리즘(암호화[1/3])

RC5 – 알고리즘(암호화[2/3]) +: 덧셈, 2w(W,단어 비트수)을 법으로한 덧셈 x>>>y: 단어 x의 y비트 우측 순환이동 x<<<y: 단어 x의 y비트 좌측 순환이동 DES 2회 반복이 RC5의 1회와 같음. 각 라운드에서 좌우 양쪽 치환. 순열, 키 의존치환 함. : 비트 XOR 연산

RC5 – 알고리즘(복호화) 역순으로 이루어짐 - 덧셈은 뺄셈으로, 좌측순환이동은 우측순환이동으로 변경.

ElGamal - 배경 기존의 비밀키 방식은 현재의 거미줄 같은 통신 방식에 부적당.

ElGamal – 특성(1/3) 공개 키의 특성인 암호화할 때와 복호화할 때 사용하는 키가 다르다. 이산대수 문제를 이용함. y  gx mod p ( g : 원시원소 p : 소수 )

ElGamal – 특성(2/3) p가 소수이고, g를 법 p에 관한 원시근이라고 하면,임의의 y에 대해 y≡0 (mod p)이고, y≡ gx 을 만족하는 x(0~(p-1))가 존재한다. p가 홀수인 소수이면, 항상 ф(p-1)개의 원시근 존재.

ElGamal – 특성(3/3) g가 p의 원시근이라면 g i≡ g j (mod p)  i≡j (mod ф(p)) 집합 {g1,g2…gф(p)}는 법 p에 관한 기약 잉여계.

ElGamal – 알고리즘 (이산대수의 예) 이산대수 문제 예 Z23 51  5 58  16 515  19 mod 23 52  2 59  11 516  3 mod 23 53  10 510  9 517  15 mod 23 54  4 511  22 518  6 mod 23 55  20 512  18 519  7 mod 23 56  8 513  21 520  12 mod 23 57  17 514  13 521  14 mod 23

ElGamal – 알고리즘 큰 소수 p, 법 p에 관한 원시근 g를 결정하여 공개. 사용자는 자신의 개인 비밀키( x ) 선정후 공개키 y를 계산하여 공개함.

ElGamal – 알고리즘 암호화 복호화 k  RZp (p : 소수) K  yBk (yB  g XB mod p) - 임의의 k(0<k<p)를 선정 C1  g k mod p C2  KM mod p (M : 평문) C = C1 || C2 복호화 K  (g k) XB mod p  C1 XB mod p – XB 는 자신만 알고 있으므로 쉽게 계산 M  C2 / K mod p – 평문을 구함.

ElGamal - 암호 방식 ElGamal 암호 방식의 구성 C 가입자 A 공개정보 g , p, yA, yB 가입자 B yA  gXA mod p k  R Zp – 1 K  yBk mod p C1  gk mod p C2  KM mod p C = C1 || C2 yB  gXB mod p K  C1XB mod p M  C2 /K mod p C

ElGamal - 암호 방식 예 C = (21, 18) 송신자 A 공개정보 p = 23, g = 7 , yA = 17, yB = 15 수신자 B XA = 5 yA  gXA = 75  17 mod 23 r = 3  R Z22 K  yBr = 153  17 mod 23 C1  gr = 73  21 mod 23 M = 20 C2  KM = 17  20  18 mod 23 C = (C1 , C2) = (21, 18) XB = 9 yB  gXB = 79  15 mod 23 C1 = 21 C2 = 18 K  C1XB  219  17 mod 23 M  C2 /K = C2 K –1  18  19  20 mod 23 C = (21, 18) 19

Rabin - 배경 소인수 문제의 어려움에 기반.

Rabin - 특성 2차 잉여문제 - 알려지지 않은 서로 다른 두 소수 p,q의 곱으로 이루어진 합성수 n=pq가 주어졌을떄, 임의의 a가 법 n에 관한 잉여류인지 아닌지 결정하는 것 Rabin 암호는 2차 잉여문제를 이용. 암호화 알고리즘에서 제곱의 연산만 하면 되므로 RSA보다 훨씬 계산이 빠름.

Rabin – 알고리즘 준비 - n = pq (서로수 p,q를 선택) - n을 공개키로 함. - p,q를 비밀키로 함. 암호화 - C  M 2 (mod n )- n보다 작은 평문 M을 법 n에 관해 제곱하여 C 작성 복호화 - 암호문 C를 비밀키 {p,q}를 이용하여 법 n에 관해 2차 잉여의 제곱근을 계산하면 M을 얻음. - C는 법 n의 2차 잉여가 되므로, 법 p와 q에 관한 2차 잉여가 됨. - 이들중 의미 있는 것이 평문임.

Rabin - 알고리즘