< 연구 결과요약서 >
소속학교 오성고등학교 책임 지도교사 전○성
참여학생 엄○필, 송○현, 전○형, 박○우
과 제 명 약수를 이용한 암호 설계 및 구현
연구목표 약수를 이용해 암호를 구현 및 설계한 후 암호가 실행되는지 검증한다. 그리고 실제 상황에서 제작한 암호가 효과적인지 실험해본다.
연구내용
□ 이론적 배경 및 선행 연구
◯ 이론적 배경
어느 자연수 의 모든 약수들의 집합 은 단 한 개밖에 존재하지 않으며, 임의의 자연수 에 대해서 의 모든 약수들의 집합 와 의 모든 약수들의 집합 는 서로 다르다. 또한, 어느 합성수 에 그 합성수의 소인수가 아닌 소수 를 곱하면 그 합성수
의 약수의 개수는 의 약수의 개수의 2배가 된다. 소수의 이런 점을 이용해서 새로운 암호를 만들고자 한다.
□ 연구 주제의 선정 및 필요성
◯ 최근 정보화가 확산되면서 보안에 대한 관심이 높아지고 있다. 또한, 빅데이터를 이용하 는 기업들도 많아지고 있는 추세다. 하지만, 기존의 암호 체계는 다량의 데이터를 암호화 하는데 부족한 면이 있다. 이를 해결하기 위해서 약수를 이용해 암호를 만들어 보기로 했다.
□ 연구 방법
◯ 암호의 설계
-> 암호를 수식적으로 간단하게 설계하고 가능한 범위 내에서 암호화가 된다는 것을 수학적 으로 증명한다.
◯ 암호 구현
-> 암호를 Visual Studio 2017을 이용해 C++언어로 구현한다.
◯ 암호가 빅데이터 암호화에 적합한지 평가
-> 코드를 분석해서 시간적/공간적 복잡도를 구한다.
-> 그 후 사용 가능성이 있다고 결론을 내린 암호를 결정한다. 그리고 상용되고 있는 암호와 1만 자의 장문의 암호화 속도를 각각 36회씩 구한다. 마지막으로 구한 시간의 평균과 신뢰구간을 구한 후 비교해서 실제 상황에서 적합한지 평가한다.
□ 연구 과정
◯ 총 세 개의 암호를 1차 선정했다.
-> 약수암호(I)는 평문의 각각 글자마다 배정된 수의 약수들의 합을 이용해서 암호화를 하도록 설계했다.
-> 약수암호(II)는 키의 약수들을 평문의 글자의 아스키코드에 각각 더한 후 모듈러 연산을 통해 아스키코드로 바꿔주는 암호이다.
-> 약수암호(III)는 나머지 정리와 등비수열의 합의 성질을 이용한 것이다.
◯ 세 암호를 C++로 코드를 작성한 후 시간적/공간적 복잡도를 분석했다.
-> 약수암호(I)와 (III)는 시간적/공간적 복잡도가 꽤 크기 때문에 빅데이터와 같은 방대한
자료를 암호화하기에 부적합하다고 판단했다. 한편, 약수암호(II)는 키와 알고리즘의 시간적/공간적 복잡도가 빅데이터를 암호화하기에 적합하고 형태보존암호이기 때문 에 얻는 이점도 많아서 약수암호(II)를 최종 선정하기로 했다.
◯ 1차 장문 암호화 비교 실험
-> AES와 비교 실험을 하기로 했다. AES를 비교 대상으로 설정한 이유는 약수암호(II)와 같은 대칭키 암호이며, 미국의 현재 표준 암호이기 때문이다.
-> AES가 평균 40ms가 소요된 반면, 약수암호(II)는 1000ms 이상 소요되었다.
◯ 암호 알고리즘 개선
-> 약수암호(II)에서 약수를 구하는 방식이 시간이 많이 걸린다고 판단하고 제곱근을 이용해 서 탐색 범위를 크게 줄이는 방법으로 개선했다.
◯ 2차 장문 암호화 비교 실험
-> AES의 장문 암호화 시간이 평균 36ms가 소요된 반면, 약수암호(II)는 평균 13ms가 소요되었다.
걸린 시간(ms)
걸린 시간(ms)
연구 성과
□ 연구 결과
◯ 알고리즘과 코드를 분석한 결과 약수암호(II)가 최종 선정되었다.
◯ AES와 장문 암호화 속도 비교 실험을 진행한 결과 AES는 평균 36ms, 약수암호(II)는 평균 13ms 정도의 암호화 시간이 소요되었다.
□ 해석 및 논의
◯ AES와의 비교 실험에서 약수암호(II)가 3배 정도 더 빨랐으므로 약수암호(II)는 다른 상용암호보다 빅데이터 암호화에 더 효율적이라고 볼 수 있다.
□ 결론 및 시사점, 추후계획
◯ 고등학생의 지식으로 암호를 제작하다보니 막히는 부분이나 암호 코드에서 비교적 효율적이지 못한 부분이 있었다. 하지만, 암호 알고리즘에 약수를 적용하면 키의 공간적 복잡도를 줄일 수 있으며, 약수를 이용한 암호가 장문 암호화 부분에서는 현재 미국의 표준 암호화 방식인 AES보다 빠르다는 것을 통해서 약수의 성질이 암호학에 도움을 줄 수 있다는 것을 알 수 있었다.
◯ UI를 구현한 후 주변의 지인들에게 피드백을 받아 수정해서 암호 프로그램을 완성할 것이다.
주요어 (Key words)
약수암호, 약수, 암호, 빅데이터
< 연구 결과보고서 >
1. 개요
□ 연구목적
○ 필요성 및 목적
- 최근 정보화의 확산으로 보안에 대한 관심이 늘고 있다. 또한, 기업이 소비자들의 욕구를 만족시키기 위해 빅데이터를 활용하는 경우가 많아지고 있다. 하지만 현재 상용되는 암호는 빅데이터의 방대한 양의 자료를 감당하기에는 조금 부족한 면이 있다고 생각했다. 그래서 우리는 “빅데이터“ 암호화라는 상황에 맞게 연구 주제를 선정했고, 그 해답으로써 약수를 지목했다. 합성수는 소수 분포의 역에 있다. 수가 늘어날수록 합성수의 분포가 늘어나는 것이다. 이를 활용하여 대량의 데이터도 충분히 큰 수가 존재한다면, 그 수의 약수로 암호화할 수 있게 만들어서 기존의 암호화 알고리즘보다 빅데이터 암호화에 효율적인 암호를 개발하는 것을 목표로 정했다.
□ 연구범위
○ 연구 분야
- 암호의 특성상 수학적 이론을 이해하고, 프로그램으로 구현하는 능력이 요구되기 때문에 수학 혹은 정보과에 속한다.
○ 연구 범위
- 2018년 5월부터 11월까지 약수의 성질을 이용해 암호의 알고리즘을 개발하고 현재 상용되는 암호인 AES와 비교 실험을 했다.
- 정보과에 속하는 프로그래밍은 중등교육과정에 있는 자료구조 및 알고리즘(스택, 큐, 배열)과 암호학에 필요한 최소한의 하드웨어 공학만을 연구에 적용했다.
또한, 멀티코어 사용과 GPU와 같은 병렬 처리 부분은 적용하지 않았다.
2. 연구 수행 내용
□ 이론적 배경 및 선행 연구
○ 소수 분포와 RSA를 비롯한 공개키 암호, AES와 같은 대칭키 암호
○ 어느 자연수 의 모든 약수들의 집합 은 단 한 개밖에 존재하지 않으며, 임의의 자연수
에 대해서 의 모든 약수들의 집합 와 의 모든 약수들의 집합 는 서로 다르다. 또한, 어느 합성수 에 그 합성수의 소인수가 아닌 소수 를 곱하면 그 합성수의 약수의 개수는 의 약수의 개수의 2배가 된다.
□ 연구주제의 선정
○ 먼저 주변에서 일어나는 여러 가지의 정보 계열 관련 문제를 탐색한 결과 현재 보안과 관련된 문제가 상당히 많이 일어나고 있음을 알게 되었다. 이후 빅데이 터와 관련된 소식을 접하였고 빅데이터의 보안에 대해서 연구를 해보면 어떨까 라는 생각을 가지게 되었다. 그래서 빅데이터를 안전하고 빠르게 암호화할 수 있는 암호를 구상하게 되었으며 약수와 그 관련 성질들을 암호 알고리즘의 핵심 으로 제시하게 되었다.
□ 연구 방법
○ 암호를 구상한 후 수학적으로 암호화가 가능한지를 증명한다.
○ Visual studio 2017을 통해 C++로 구현한다.
○ 암호의 코드를 분석해서 안전성과 시간적/공간적 복잡도를 검사한다. 그 후 암호를 최종 선정한다.
- 먼저 암호 프로그램이 실제 상황에서 어떻게 동작하는지 확인하기 위해 코드로 구현한 후 복잡도를 검사했다.
○ 현재 상용되는 암호와의 1만자 정도의 장문 암호화 속도 비교 실험을 통해 빅데이터 암호화에 적합한지 검증한다.
- 빅데이터는 자료의 크기가 방대하므로 1만자의 평문을 암호화하는 실험을 설계했다.
○ 실험 방법
1) 약수암호(II)는 int 자료형의 최대 범위에 근접한 수인 223092870(1부터 23까지의 소수계승)을 키로 하고 for문을 이용해서 1만 개의 배열을 채운다. (본 실험에서는 f로 평문을 채웠다.) 그 후 36회 암호화해서 걸린 시간의 평균과 신뢰구간(99%)을 구한 다. 이때, 평문을 채우는 시간은 구하지 않는다.
2) AES는 128비트의 키를 이용하고 for문을 이용해서 1만 개의 배열을 채운다. (본 실험에 서는 f로 평문을 채웠다.) 그 후 36회를 실행해서 걸린 시간의 평균과 신뢰구간(99%)을 구한다. 이때, 평문을 채우는 시간은 구하지 않는다. AES는 오픈소스를 이용하였다.
3) 두 암호 시스템의 암호화 시간의 평균을 비교하여 약수암호(II)가 실제 상황에서 효율적 인지 증명한다.
- 이때, 약수암호(II)가 느리다면 알고리즘을 개선한 후 다시 실험한다.
□ 연구 활동 및 과정
○ 암호 알고리즘 개발 - 약수 암호1 설계
⋅약수암호(I)는 평문의 각각 글자마다 배정된 수의 약수들의 합을 이용해서 암호화를 하도록 설계했다.
- 약수 암호2 설계
⋅약수암호(II)는 키의 약수들을 평문의 글자의 아스키코드에 각각 더한 후 모듈러 연산을 통해 아스키코드로 바꿔주는 암호이다.
- 나머지 정리(등비수열의 합) 암호 설계
⋅약수암호(III)는 나머지 정리와 등비수열의 합의 성질을 이용한 것이다.
- 개발된 것을 바탕으로 C++로 구현
○ 검증 및 분석
- 각 알고리즘의 공간적 복잡도 추론
- 각 알고리즘의 복호화, 암호화, 키가 없을 때의 복호화에 대한 시간복잡도 추론
○ 상용 암호(AES)와의 장문 암호화 속도 비교
○ 결론 도출
- 첫 실험에서는 AES가 평균 40ms, 약수암호(II)가 평균 1027ms 소요되었다.
- 약수 암호(II)의 알고리즘 중에서 키의 약수를 찾는 방법을 제곱근을 이용하는 방법으로 개선했다.
- 이후, 재 실험한 결과 AES가 평균 36ms, 약수암호(II)가 평균 13ms 소요되었다.
3. 연구 결과 및 시사점
걸린 시간(ms)
걸린 시간(ms)
□ 연구 결과
○ 약수암호(II)가 시간적/공간적 복잡도가 적고 형태보존암호화기 때문에 얻는 이점들이 많아서 선정되었다.
○ 2번의 실험 결과 약수암호(II)가 AES보다 평균 3배 정도 더 빨랐다. 그러므로 현재 상용되는 암호보다 빅데이터를 암호화하기에 적합하다는 결론을 내리게 되었다.
□ 시사점
○ 안전성
- 약수의 성질에 의해 암호의 해싱으로 인한 충돌 값을 찾기 매우 힘들고, 법 연산을 쓰기 때문에 암호의 규칙성을 가릴 수 있어서 충분히 안전하다고 할 수 있다.
○ 약수를 암호학에서 활용할 수 있는 가능성
- 약수 암호 구현을 통해서 암호 알고리즘에 약수를 적용하면 키의 공간적 복잡도를 줄일 수 있다. 또한, 약수를 이용한 암호가 장문 암호화 부분에서는 현재 미국의 표준 암호화 방식인 AES보다 빠르다는 것을 통해서 약수의 성질이 암호학에 도움을 줄 수 있다는 것을 알 수 있었다.
4. 홍보 및 사후 활용
□ 약수암호(II)에 UI구현 후 완성하기
○ UI를 구현하여 사용자가 편리하게 암호화 할 수 있도록 한다. 그리고 주변의 지인들에게 배포해서 피드백을 받은 후 암호를 완성한다.
5. 참고문헌 및 부록
□ 부록
○ 이상원(2014). 행렬을 이용한 공개키 암호 알고리즘의 설계 및 구현. 한국정보과학회 학술발표논문집, , 2015-2017.