●●● JAVA를 이용한 RSA 암호 시스템의 구현 ●●●
>>> 본 강좌는 RSA 암호화와 JAVA에 대한 기본적인 지식이 있는 분들을 위한
강좌이므로 이론적인 부분들은 따로 공부하기 바립니다.
(이 강좌는 제가 절대 자바나 암호학에 대하여 해박한 지식이 있어서 쓰는 것이
아니라는 것을 먼저 밝혀두는 바입니다.
그냥 요번 방학동안 배운 것을 한번 정리하는 차원에서 적는 것입니다.)
■ 요약
>>> RSA 공개키 암호화 알고리즘은 1977년에 Riverst, Shamir 그리고 Adleman 이라는 세 명의
수학자들에 의해 제안된 방식이다. 이 알고리즘은 현재 공개키 암호 기법들 중에서 가장 널리
사용되고있다. RSA 암호화는 아주 큰 소수(large prime number)로 된 합성수를 인수분해
하는것이 어렵다는데 그 기반을 두고 있다.
그 기본 원리는 다음과 같다.
>>> RSA 공개키 암호에 사용될 공개키 {N,E}와 개인키{N,D}를 생성하기 위해서는 먼저 모든
사용자들은 각각 다음의 작업을 수행하여야 한다.
① 두 개의 큰 소수 p와 q를 선정한 다음에 Modulus N = p * q와 PI(N)을 계산한다.
② 공개키 E는 PI(N) = (p - 1)(q - 1)과 서로 소의 관계가 되게 임의로 선정한다.
③ E * D mon PI(N) = 1의 관계에 있는 개인키 D를 "확장된 유클리드 알고리즘"으로 구한다.
④ {E,N}을 공개키로 공개하고, {D,N}을 개인키로 자신이 안전하게 보관한다.
>>> 그 다음 RSA 암호의암호화를 위해서는 먼저 암호화된 메시지를 받을 수신자의 공개키 {E, N}을
취득한 후에 암호화 할 평문M을 정수 M으로 전환하여 다음과 같은 암호화 작업을 수행한 결과인
암호문 C를 수신자에게 보내고, 수신자는 자신의 개인키를 이용한 복호화 작업을 통해서 원래의
평문M을 복원하게 된다.
RSA암호화 : E(M) = M ^ E mod N = C
RSA복호화 : D(C) = C ^ D mod N = ((M ^ E) ^ D) mod N = M
■ 자바를 이용한 실용적 구현
>>> RSA 공개키 암호화를 구현하기 위하여는 대략 4가지 정도의 암고리즘이 필요하다.
① 큰 두 소수를 찾기위한 Miller-Rabin 판정법
② 공개키를 구하기 위한 유클리드 알고리즘의 변형
③ 개인키를 구하기 위한 확장된 유클리드 알고리즘
④ 법 연산을 위한 빠른 법-지수 연산 알고리즘
>>> 자 그러면 프로그램의 흐름을 하나하나 생가해보면서 출발해 보자구요^^
가장 먼저 해야할 일은 당연히 평문을 입력받아서 그것을 계산하기 위하여 10진수로 바꾸는
작업이겠지요
char charArray[];
charArray=plainText.toCharArray();
long temp=(long)charArray[i]; // 이 작업을 평문의 길이 만큼 반복하면 되겠지요^^
>>> 이제 평문은 구했으니까 법N을 구해봅시다.
법N은 두 소수의 곱으로 이루어 졌으니까 소수를 두개 구하여 곱하면 되겠네요(당연한소리!!!)
이를 위하여 있는 것이 큰 소수를 구한는 알고리즘인 밀러-라빈 판정법입니다.
while(1==1)
{
count=1;
while(1==1)
{
// 자바에서 소수 p와 q가 서로 비슷하게 5자리이상을 가지도록 설정하는 것은 불가능하다.
// 그래서 여기서는 4자리고 사용하였다.
randomNum=(long)(Math.random() * 10000);
if(randomNum<=1000) // 4자리로 제한하기 위하여
continue;
prime=millerRabin(randomNum); // 밀러-라빈 판정법을 거친다.
if(prime==false) // 소수가 아니면 다시 루프를 반복한다.
{
count++; // 몇번 루프를 반복하는지 카운터한다.
continue;
}
else // 소수이면 루프를 빠져 나온다.
break;
}
bub[bubCount]=randomNum; // 선택된 난수를 저장
textarea.append(" ▶ 소수" + (bubCount+1) + " : " + bub[bubCount] + "n");
textarea.append(" >>> " + count + "개의 난수를 검사하였습니다.n");
bubCount++; // 두번째 난수를 위한 카운터
if(bubCount == 2) // 난수가 2개 선정 되었으면 루프를 빠져나온다
break;
}
// 밀러-라빈 알고리즘은 그냥 책에 나와있는데로 하시면 되기 때문에
// 자세한 설명은 생략하기로 하겠습니다.
public static boolean millerRabin(long n)
{
long r=n-1;
long k=0;
long j=0;
long y=0;
boolean isPrime=true;
long s=0;
/* s가 하나 증가하면 r은 반으로 감소해야 균형이 이루어 지므로
s가 증가할때마다 r은 반으로 감소시키고, 밀러-라빈 조건에서
r이 홀수 일때 이것이 만족하므로 r이 홀수이면 이 루프를
빠져 나온다.*/
while(r%2==0)
{
r=r/2;
s++;
}
// k =(long)Math.log(n)/2;
/* 이 부분이 이론적으로는 중요한 부분인데 실제적으로 그렇지 않더군요
위에서 카운터를 한 것도 이것을 비교하기 위해서였는데...쩝쩝쩝
이론상으로 10진수 100자리 정도의 소수를 찾기위해서는 위의 계산되로(k=115)
나와야 하는데 실제적으로는 택도 없습니다.
10자리만 하여도 위의 카운터가 1000을 넘기가 다반수입니다.
그것은 어떻게 보면 당연한 것이지만... 왜 당연한 것인지 모르겠는분은
확률과 통계를 공부좀 하시기 바랍니다.
여하튼 그래서 아래에 그냥 100번 루프를 도는 것으로 임의로 정하였습니다.*/
for(int i=0;i<100;i++)
{
long a=(long)(Math.random()*(n-2));
y = fastExp(a,r,n); // 빠른 법-지수 연산을 위한 알고리즘. 뒤에 나오거든요...
if(y != 1 && y!=n-1)
{
j=1;
while(j<=s-1&&y!=n-1)
{
y=(y*y)%n;
if(y==1)
{
isPrime=false;
return isPrime;
}
j=j+1;
}
if(y!=(n-1))
{
isPrime=false;
return isPrime;
}
}
}
return isPrime;
}
>>> 자 일단 한 고비는 넘겼으니까 숨 한번 쉬고 다음으로 넘어갑시다.
휴~~~
그럼 소수를 정하였으니까 이제 공개키를 선정해야겠지요.
공개키 선정은 간단합니다. 임의의 소수를 하나 선정하여 그것이 pi(n)과
서로 소의 관계에 있는지(최대 공약수가 1인지)를 검사만 하면됩니다.
// 공개키를 구하는 함수
public static long publicKeyMaker(long temp)
{
long ee=0;
while(1==1)
{
ee=(long)(Math.random()*10000);
long gcd = gcd(ee, temp);
if(gcd==1)
break;
}
return ee;
}
// 최대 공약수를 구하는 함수
public static long gcd(long a, long b)
{
long s = a;
long t = b;
long r=0;
while(t>0)
{
r = s % t;
s = t;
t = r;
}
return s;
}
>>> 자 이제 확장된 유클리드 알고리즘을 거쳐서 개인키만 구하면 되는군요
저도 이부분이 가장 힘들었는데 인터넷에서 누군가가 C로 구현해 놓은것이 있어서
그것을 자바로 바꾸어 보았습니다.
자세한 알고리즘을 알고 싶으시면 자료실의 RSA자료를 참조하시기 바랍니다.
// 개인키 d를 구하기 위한 확장된 유클리드 알고리즘
// 첫 번째 매개변수는 공개키이고, 두 번째는 pi(n) 입니다.
public static long extendUclide(long first, long second)
{
long b,p,x,s,q,e,w,a;
b = second;
a = first;
x = 0;
s = 1;
while(a != 1)
{
q = b/a;
e = b - a*q;
w = x - s*q;
b = a;
a = e;
x = s;
s = w;
}
if(s < 0)
s = s + second;
return s;
}
>>> 으흐흐흐... 드디어 개인키까지 다 구하였군요. 감기가 무량(?)하군요...(아닌가?)
자 마지막으로 할 일은 빠른 법-지수 연산을 거쳐서 암호화만 수행하면 되는군요.
// 빠르게 m^e mod n 을 구하기 위한 알고리즘
public static long fastExp (long m, long e, long n)
{
long z = 1 ;
while (e != 0) //지수의 비트수와 일치할때까지 반복한다.
{
while (e % 2 == 0) // 지수의 특징 비트가 1일때
{
e = e / 2 ; // 이렇게 함으로써 지수의 비트수가 한 자리 줄어든다
m = (m * m) % n ;
}
e--; // 지수의 특징 비트가 0이 되도록 한다.
z = (z * m) % n ; // 지수가 0일때 계산
}
return z;
}
>>> 본 강좌는 RSA 암호화와 JAVA에 대한 기본적인 지식이 있는 분들을 위한
강좌이므로 이론적인 부분들은 따로 공부하기 바립니다.
(이 강좌는 제가 절대 자바나 암호학에 대하여 해박한 지식이 있어서 쓰는 것이
아니라는 것을 먼저 밝혀두는 바입니다.
그냥 요번 방학동안 배운 것을 한번 정리하는 차원에서 적는 것입니다.)
■ 요약
>>> RSA 공개키 암호화 알고리즘은 1977년에 Riverst, Shamir 그리고 Adleman 이라는 세 명의
수학자들에 의해 제안된 방식이다. 이 알고리즘은 현재 공개키 암호 기법들 중에서 가장 널리
사용되고있다. RSA 암호화는 아주 큰 소수(large prime number)로 된 합성수를 인수분해
하는것이 어렵다는데 그 기반을 두고 있다.
그 기본 원리는 다음과 같다.
>>> RSA 공개키 암호에 사용될 공개키 {N,E}와 개인키{N,D}를 생성하기 위해서는 먼저 모든
사용자들은 각각 다음의 작업을 수행하여야 한다.
① 두 개의 큰 소수 p와 q를 선정한 다음에 Modulus N = p * q와 PI(N)을 계산한다.
② 공개키 E는 PI(N) = (p - 1)(q - 1)과 서로 소의 관계가 되게 임의로 선정한다.
③ E * D mon PI(N) = 1의 관계에 있는 개인키 D를 "확장된 유클리드 알고리즘"으로 구한다.
④ {E,N}을 공개키로 공개하고, {D,N}을 개인키로 자신이 안전하게 보관한다.
>>> 그 다음 RSA 암호의암호화를 위해서는 먼저 암호화된 메시지를 받을 수신자의 공개키 {E, N}을
취득한 후에 암호화 할 평문M을 정수 M으로 전환하여 다음과 같은 암호화 작업을 수행한 결과인
암호문 C를 수신자에게 보내고, 수신자는 자신의 개인키를 이용한 복호화 작업을 통해서 원래의
평문M을 복원하게 된다.
RSA암호화 : E(M) = M ^ E mod N = C
RSA복호화 : D(C) = C ^ D mod N = ((M ^ E) ^ D) mod N = M
■ 자바를 이용한 실용적 구현
>>> RSA 공개키 암호화를 구현하기 위하여는 대략 4가지 정도의 암고리즘이 필요하다.
① 큰 두 소수를 찾기위한 Miller-Rabin 판정법
② 공개키를 구하기 위한 유클리드 알고리즘의 변형
③ 개인키를 구하기 위한 확장된 유클리드 알고리즘
④ 법 연산을 위한 빠른 법-지수 연산 알고리즘
>>> 자 그러면 프로그램의 흐름을 하나하나 생가해보면서 출발해 보자구요^^
가장 먼저 해야할 일은 당연히 평문을 입력받아서 그것을 계산하기 위하여 10진수로 바꾸는
작업이겠지요
char charArray[];
charArray=plainText.toCharArray();
long temp=(long)charArray[i]; // 이 작업을 평문의 길이 만큼 반복하면 되겠지요^^
>>> 이제 평문은 구했으니까 법N을 구해봅시다.
법N은 두 소수의 곱으로 이루어 졌으니까 소수를 두개 구하여 곱하면 되겠네요(당연한소리!!!)
이를 위하여 있는 것이 큰 소수를 구한는 알고리즘인 밀러-라빈 판정법입니다.
while(1==1)
{
count=1;
while(1==1)
{
// 자바에서 소수 p와 q가 서로 비슷하게 5자리이상을 가지도록 설정하는 것은 불가능하다.
// 그래서 여기서는 4자리고 사용하였다.
randomNum=(long)(Math.random() * 10000);
if(randomNum<=1000) // 4자리로 제한하기 위하여
continue;
prime=millerRabin(randomNum); // 밀러-라빈 판정법을 거친다.
if(prime==false) // 소수가 아니면 다시 루프를 반복한다.
{
count++; // 몇번 루프를 반복하는지 카운터한다.
continue;
}
else // 소수이면 루프를 빠져 나온다.
break;
}
bub[bubCount]=randomNum; // 선택된 난수를 저장
textarea.append(" ▶ 소수" + (bubCount+1) + " : " + bub[bubCount] + "n");
textarea.append(" >>> " + count + "개의 난수를 검사하였습니다.n");
bubCount++; // 두번째 난수를 위한 카운터
if(bubCount == 2) // 난수가 2개 선정 되었으면 루프를 빠져나온다
break;
}
// 밀러-라빈 알고리즘은 그냥 책에 나와있는데로 하시면 되기 때문에
// 자세한 설명은 생략하기로 하겠습니다.
public static boolean millerRabin(long n)
{
long r=n-1;
long k=0;
long j=0;
long y=0;
boolean isPrime=true;
long s=0;
/* s가 하나 증가하면 r은 반으로 감소해야 균형이 이루어 지므로
s가 증가할때마다 r은 반으로 감소시키고, 밀러-라빈 조건에서
r이 홀수 일때 이것이 만족하므로 r이 홀수이면 이 루프를
빠져 나온다.*/
while(r%2==0)
{
r=r/2;
s++;
}
// k =(long)Math.log(n)/2;
/* 이 부분이 이론적으로는 중요한 부분인데 실제적으로 그렇지 않더군요
위에서 카운터를 한 것도 이것을 비교하기 위해서였는데...쩝쩝쩝
이론상으로 10진수 100자리 정도의 소수를 찾기위해서는 위의 계산되로(k=115)
나와야 하는데 실제적으로는 택도 없습니다.
10자리만 하여도 위의 카운터가 1000을 넘기가 다반수입니다.
그것은 어떻게 보면 당연한 것이지만... 왜 당연한 것인지 모르겠는분은
확률과 통계를 공부좀 하시기 바랍니다.
여하튼 그래서 아래에 그냥 100번 루프를 도는 것으로 임의로 정하였습니다.*/
for(int i=0;i<100;i++)
{
long a=(long)(Math.random()*(n-2));
y = fastExp(a,r,n); // 빠른 법-지수 연산을 위한 알고리즘. 뒤에 나오거든요...
if(y != 1 && y!=n-1)
{
j=1;
while(j<=s-1&&y!=n-1)
{
y=(y*y)%n;
if(y==1)
{
isPrime=false;
return isPrime;
}
j=j+1;
}
if(y!=(n-1))
{
isPrime=false;
return isPrime;
}
}
}
return isPrime;
}
>>> 자 일단 한 고비는 넘겼으니까 숨 한번 쉬고 다음으로 넘어갑시다.
휴~~~
그럼 소수를 정하였으니까 이제 공개키를 선정해야겠지요.
공개키 선정은 간단합니다. 임의의 소수를 하나 선정하여 그것이 pi(n)과
서로 소의 관계에 있는지(최대 공약수가 1인지)를 검사만 하면됩니다.
// 공개키를 구하는 함수
public static long publicKeyMaker(long temp)
{
long ee=0;
while(1==1)
{
ee=(long)(Math.random()*10000);
long gcd = gcd(ee, temp);
if(gcd==1)
break;
}
return ee;
}
// 최대 공약수를 구하는 함수
public static long gcd(long a, long b)
{
long s = a;
long t = b;
long r=0;
while(t>0)
{
r = s % t;
s = t;
t = r;
}
return s;
}
>>> 자 이제 확장된 유클리드 알고리즘을 거쳐서 개인키만 구하면 되는군요
저도 이부분이 가장 힘들었는데 인터넷에서 누군가가 C로 구현해 놓은것이 있어서
그것을 자바로 바꾸어 보았습니다.
자세한 알고리즘을 알고 싶으시면 자료실의 RSA자료를 참조하시기 바랍니다.
// 개인키 d를 구하기 위한 확장된 유클리드 알고리즘
// 첫 번째 매개변수는 공개키이고, 두 번째는 pi(n) 입니다.
public static long extendUclide(long first, long second)
{
long b,p,x,s,q,e,w,a;
b = second;
a = first;
x = 0;
s = 1;
while(a != 1)
{
q = b/a;
e = b - a*q;
w = x - s*q;
b = a;
a = e;
x = s;
s = w;
}
if(s < 0)
s = s + second;
return s;
}
>>> 으흐흐흐... 드디어 개인키까지 다 구하였군요. 감기가 무량(?)하군요...(아닌가?)
자 마지막으로 할 일은 빠른 법-지수 연산을 거쳐서 암호화만 수행하면 되는군요.
// 빠르게 m^e mod n 을 구하기 위한 알고리즘
public static long fastExp (long m, long e, long n)
{
long z = 1 ;
while (e != 0) //지수의 비트수와 일치할때까지 반복한다.
{
while (e % 2 == 0) // 지수의 특징 비트가 1일때
{
e = e / 2 ; // 이렇게 함으로써 지수의 비트수가 한 자리 줄어든다
m = (m * m) % n ;
}
e--; // 지수의 특징 비트가 0이 되도록 한다.
z = (z * m) % n ; // 지수가 0일때 계산
}
return z;
}
