위키원
레인달
레인달(Rijndael)은 벨기에의 암호학자 존 대먼(Joan Daemen)과 빈센트 라이먼(Vincent Rijmen)에 의해 개발된 대칭 키 알고리즘이다. 미국 국립표준기술 연구소에서 진행한 차세대 암호 알고리즘 공모에서 마지막으로 선정되어 AES으로 채택되었다. 따라서 AES라고도 부른다.
목차
개요
1997년 1월 2일에, 미국 국립표준기술 연구소는 DES를 대체할 새로운 암호 기법의 필요성을 느꼈다. 따라서 3DES와 같거나 더 뛰어난 보안성을 갖고 개선된 암호 기법을 공모했는데, 공모에서 선정될 암호의 정식적인 이름은 1997년 9월 2일에 AES로 정해졌다. 총 세 차례의 대회는 1차에서 21개의 알고리즘이 제안되었고, 2차에서 15개의 알고리즘이 통과된 후, 3차에는 5개의 알고리즘만이 후보 알고리즘으로 남겨져 최후에는 하나만 남았다. 여기서 살아남아 AES로 선정된 알고리즘이 존 대먼과 빈센트 라이먼이 개발한 레인달 알고리즘이다. 레인달 알고리즘의 명칭은 존 대먼과 빈센트 라이먼의 이름에서 따온 것이다. 128비트 평뭉르 128비트 암호문을 출력하는 알고리즘으로, 논파이스텔 알고리즘에 속한다. 암호화 키의 길이에 따라서 실행되는 라운드의 수 또한 다르며, 이들 각각은 10, 12, 14 라운드를 실행한다. 암호화 키는 128, 192, 256 세 가지 중 하나가 될 수 있으며, 각각은 AES-128, AES-192, AES-256으로 불린다. 그러나 어떤 경우에서라도 키 확장 알고리즘으로부터 생성되는 라운드 키의 크기는 평문과 암호문의 크기와 동일한 128비트이다. S-box를 간단히 설명하자면, 입력 데이터를 지정된 숫자로 바꿔서 암호를 깨기 어렵게 만드는 기법이라고 할 수 있다. AES는 이를 새롭게 재발명하여, 만약 암호화 속도를 높이고 싶다면 S-box를 메모리에 넣어두고, 프로그램 메모리 양을 줄이고 싶다면 S-box를 연산으로 구해내는 기법을 사용한다. 레인달 알고리즘은 크게 네 단계로 나뉜다.
- 키 확장 : 키 스케줄이라고도 부른다. 128, 192, 256비트 길이인 하나의 주 암호화 키를 받아서 아래의 라운드 들에서 사용할 128비트 라운드 키를 여러 개 생성한다.
- 0 라운드 : 위 단계에서 생성한 라운드 키들 중 첫 번째 킬를 사용하며, AddRoundKey키를 한 번 실행한다.
- 1~(9, 11, 13) 라운드 : SubBytes, ShiftRows, MixColumns, AddRoundKey를 순서대로 실행한다. 이 과정을 AES-128, 192, 256에 따라 각각 9번, 11번, 13번씩 반복한다.
- 마지막 10, 12, 14번째 라운드 : SubBytes, ShiftRows, AddRoundKey를 차례대로 실행한다.
배경
1997년 1월 2일 미국 국립표준기술 연구소는 DES를 대체할 새로운 암호 기법의 필요성을 느끼고, 보안성이 3DES와 비슷하거나 더 뛰어나게 개선된 암호 기법을 공모했다. 1997년 9월 2일, 공모에서 마지막으로 선정될 암호의 이름이 AES로 정해졌다. 미국 국립표준기술 연구소는 암호론의 케르코프 원리에 의하여 128비트 블록을 128 혹은 192 혹은 256비트 키 길이로 처리할 수 있고, 무료로 배포할 수 있어야 한다는 제한 조건이 있었다. 공모에서 제시한 평가 기준은 총 5가지로, 각각 보안, 메모리 요구량, 계산적 효율성, 하드웨어와 소프트웨어 면에서의 적합성, 유연성이었다. 1998년 1월 15일 마감일을 기준으로 하여 총 21개의 알고리즘이 제안되었으며, 이들 중에 단 15개의 알고리즘만이 AES 후보로 선정되어 안전성을 평가받았다. 1998년 8월 20일, 미국 국립표준기술 연구소는 선정된 15개의 암호 알고리즘에 대해 제1차 AES 후보 대회를 개최했다. 그리고 1999년 3월에 제2차 AES 후보 대회가 개최되었고, 1999년 8월에 총 5개의 후보 알고리즘만을 최종 후보로 선정하여 많은 암호학자들로부터 안전성 평가를 받도록 하였다. 이 과정에서 남은 5개의 알고리즘의 이름은 MARS, RC6, 레인달, Serpent, Twofish이다. 2000년 4월에 제3차 AES후보 대회가 개최되고, 심사 끝에 2000년 10월 2일에 AES 알고리즘으로 선정된 것이 존 대먼과 빈센트 라이먼이 개발한 레인달 알고리즘이다. 국 국립표준기술 연구소는 이에 뒤이어 2001년 2월 28일에 연방 정보 처리 표준으로서 AES를 공개 및 리뷰하고, 배포하면서 기밀성 있는 정보에 DES를 대체하여 AES를 사용하기 시작했다. 2001년 11월 16일에는 레인달 알고리즘, 즉 AES가 표준으로 채택되었으며, 2001년 12월 4일에는 FIPS 197로 등록되었다.
AES 선정 과정에서 주목해야 할 점은 개방성과 국제 흐름이 반영되었다는 것이다. 세 차례의 대회와 많은 사람들의 의견을 수렴하여 공개하여 반영하였으며, 이 과정에서 전문가와 비전문가의 의견을 가리지 않고 받아들여 다양한 의견을 수집했다. 피드백의 기회를 부여하고 다함께 그 이슈에 대해 토론하는 과정이 있었으며, 이뿐만 아니라 다양한 분야의 전문가들의 의견도 반영되었다. 수학자, 암호학자, 공학자, 컴퓨터 학자 등 다양한 분야의 전문가들이 의견을 적극적으로 반영하여, 뛰어난 성능을 갖춘 동시에 안전성도 개선된 알고리즘을 선택할 수 있었다. 국제화 측면에서 AES 선정 과정을 분석하면, 선정된 알고리즘들은 15개의 후보 알고리즘의 개발자이 가진 다양한 국적만큼 다양한 국가의 평가를 받았다. 당시 알고리즘의 안전성 평가에 적극적으로 참가했던 국가들은 대한민국을 비롯하여 노르웨이, 독일, 미국, 벨기에, 영국, 이스라엘, 일본, 캐나다, 코스타리카, 프랑스, 호주가 있었다.
제2차 AES 후보 대회는 이례적이게도 미국이 아니라 이탈리아 로마에서 개최되었다. 평가에서 AES 후보 알고리즘들은 다음과 같은 세 가지 조건을 만족해야 했다. 하나는 안전성으로, 후보 알고리즘들이 절대적으로 갖춰져야하는 부분이었고, 특히 대칭키 암호를 분석하는 대표적인 방법인 선형 공격과 차분 공격에 대한 안전성 증명이 주를 이루었다. 두 번째는 비용으로, 스마트카드, 하드웨어, 소프트웨어의 구현을 위한 다양한 형태의 계산효율성을 참고하여 평가되었다. 여기서 계산 효율성이라고 하는 것은 속도 및 메모리 요구량 등을 의미한다. 세 번째는 알고리즘 및 구현 특성으로, 이 기준은 유연성과 알고리즘의 단순성에서 주로 평가하였다. 마지막 평가 과정에서 남았던 5개의 알고리즘 중에서 레인달 선정되고 나머지 4개의 알고리즘은 탈락했지만, 모두 안전성이 떨어지는 알고리즘은 절대 아니었다. 다만 레인달 알고리즘이 안전성과 속도, 효율성, 구현 및 유연성이 다른 후보 알고리즘들 보다 우수했을 뿐이다.[1]
특징
AES, 즉 레인달 알고리즘의 특징 중 하나는 파이스텔 구조가 아니라는 점이다. 전형적인 파이스텔 구조는 데이터 블록의 반쪽을 다른 반쪽을 수정하는 데 사용하고, 그 두 반쪽을 서로 교환했다. AES는 파이스텔 구조를 사용하지 않고 각 라운드에서 대체와 치환을 이용하여 데이터 블록의 전체를 병렬 처리한다. 또, 입력으로 사용하는 키를 44개의 32비트 워드 배열로 확장한다. 4개의 서로 다른 128비트 워드를 각 라운드에서 라운드 키로 사용한다. 다음의 네 가지 단계를 이용하는데, 치환 한 번과 대체 세 번이다.
- 바이트 대체 : S-box 표를 이용하여 바이트 단위 형태로 블록을 교환한다.
- 행 이동 : 단순히 행과 행을 치환한다.
- 열 섞기 : 열에 속한 모든 바이트를 순환 행렬을 이용하여 함수로 열에 있는 각 바이트를 대체해서 변형시킨다.
- 라운드 키 더하기 : 확장된 키의 일부와 현재 블록을 비트별로 XOR한다.
암호와 복호를 위하여 라운드 키 더하기 단계에서 시작하며, 각 라운드에서는 네 단계를 모두 포함하는 9라운드를 수행하고, 세 단계로 구성된 열 번째 라운드를 수행한다. 주의해야 할 점은 오직 라운드 키 더하기 단계에서만 키를 사용해야 한다는 것이다. 그래서 암호화와 복호화 과정의 시작과 끝은 항상 라운드 키 더하기 단계이다. 시작이나 끝에 수행되는 다른 단계들은 키 없이 역방향 계산이 가능하기 때문에, 보안을 강화하는 데는 별다른 역할을 하지 못한다. 라운드 키 더하기 단계는 그 자체는 강력하지 않으나, 세 단계와 같이 작동하여 비트를 뒤섞는 역할을 수행한다. 그러나 각각은 키를 사용하지 않기 때문에 보안성을 제공하는 것은 아니다. 이 암호 단계를 살펴보면 블록에 XOR 암호화를 하고, 그 다음 블록을 뒤섞고, 그 뒤에 다시 XOR 암호화를 하는 것으로 이를 번갈아서 적용하는 것을 볼 수 있다. 이 구조는 효과적이고 보안성을 매우 강화시킨다.
각 단계를 역으로 계산하는 것은 쉽다. 바이트 대체, 행의 이동, 열 섞기 단계는 복호화 알고리즘에서 사용되는 역함수이다. 라운드 키 더하기 단계에서는 같은 라운드 키를 블록에 XOR 수행해서 역을 계산한다. 대부분의 블록 암호처럼 복호화 알고리즘에서는 확장 키를 순서를 뒤집어서 적용하는데, 복호화 알고리즘과 암호화 알고리즘이 동일한 것은 아니다. 이것이 바로 AES의 구조가 가지고 있는 특성이다. 네 단계가 모두 역 계산이 가능하기 때문에 복호화를 하면 평문을 얻을 수 있는 것이 당연하다. 암호화와 복호화의 마지막 라운드는 세 단계로만 구성된다. 이러한 특성들은 AES암호가 역으로 잘 작동되도록 하기 위해 필요한 조치이다.[1]
안전성
미국 정부에서 채택해서 정부의 기밀문서를 암호화한 알고리즘이다. 즉, 한 나라의 정부가 신용하는 알고리즘이다. 현재까지는 아직 AES보다 전반적으로 월등한 암호 알고리즘이 나오지 않았고, 현존하는 최강의 암호화 알고리즘이며, 키 없이 해독하는 것이 거의 불가능하다고 믿겨지고 있다. 심지어 다른 최신 암호와 마찬가지로, 기지 평문 공격을 이용한 해킹 기술로도 해독이 불가능하다고 알려져 있다. 소수를 사용한 암호화의 특성을 이용한 공개키 암호화 방식 등이 양자 컴퓨터에 취약할 가능성을 보여주지만, SPN을 기반으로 하는 AES의 특성상으로는 상대적으로 양자컴퓨터에 안전하다. 시간이 지남에 따라 컴퓨팅 기술이 급속하게 발전하여, 현재 권장되는 암호화 수준은 192비트 이상이다. 대다수의 금융기관이나 웹사이트들은 256비트 이상의 암호화 체계로 전환했다.[2]
알고리즘
Sub Bytes
ShiftRows
Mix Column
Add Round Key
각주
- ↑ 1.0 1.1 고급 암호화 표준 위키백과 - https://ko.wikipedia.org/wiki/%EA%B3%A0%EA%B8%89_%EC%95%94%ED%98%B8%ED%99%94_%ED%91%9C%EC%A4%80
- ↑ AES 나무위키 - https://namu.wiki/w/AES
참고자료
- 고급 암호화 표준 위키백과 - https://ko.wikipedia.org/wiki/%EA%B3%A0%EA%B8%89_%EC%95%94%ED%98%B8%ED%99%94_%ED%91%9C%EC%A4%80
- AES 나무위키 - https://namu.wiki/w/AES
- thenine, 〈AES와 Rijndael〉, 《이글루스》, 2008-05-22
- Moserware, 〈A Stick Figure Guide to the Advanced Encryption Standard (AES)〉, 《디스커스》, 2009-11-22
- Ho_use, 〈AES암호화 (Rijndael 알고리즘)〉, 《티스토리》, 2018-01-25
- Ho_use, 〈AES복호화 (Rijndael 알고리즘)〉, 《티스토리》, 2018-01-26
- 와이준Nye, 〈(암호학) 대칭키 암호 - AES(Advanced Encrytion Standard)〉, 《티스토리》, 2019-11-15
같이 보기
