RC5
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
RC5는 가변 블록 크기, 키 크기 및 라운드 수를 지원하는 블록 암호 알고리즘이다. 데이터 종속 회전을 사용하며, 모듈러 덧셈과 XOR 연산을 조합하여 구성된다. 64비트 블록, 128비트 키, 12라운드가 원래 제안된 매개변수였다. RC5는 암호화 및 복호화 루틴이 간단하지만, 키 스케줄은 복잡하며, 자연로그의 밑과 황금비의 이진 확장을 통해 키를 확장한다. 12라운드 RC5는 차분 공격에 취약하여 18~20라운드가 권장되며, 분산 컴퓨팅 프로젝트를 통해 56비트 및 64비트 키가 해독되었다.
더 읽어볼만한 페이지
- 블록 암호 - 데이터 암호화 표준
데이터 암호화 표준(DES)은 미국 국립표준기술연구소에서 개발되어 널리 사용되었던 대칭키 암호 알고리즘이지만, 짧은 키 길이와 취약점 때문에 고급 암호화 표준(AES)으로 대체되었고, 트리플 DES 형태로 일부 시스템에서 사용되며 암호학 발전에 기여한 역사적 의미가 있다. - 블록 암호 - 고급 암호화 표준
고급 암호화 표준(AES)은 미국 국립표준기술연구소에서 제정한 대칭 키 암호화 블록 암호 표준으로, 치환-순열 네트워크 구조에 기반하여 128비트 블록 크기와 다양한 키 크기를 지원하며, 빠른 속도와 효율성으로 널리 사용된다.
| RC5 | |
|---|---|
| 암호 | |
| 이름 | RC5 |
 | |
| 설계자 | 로널드 리베스트 |
| 발표 연도 | 1994 |
| 기반 | 해당 사항 없음 |
| 파생 | RC6 Akelarre |
| 키 크기 | 0에서 2040 비트 (128 권장) |
| 블록 크기 | 32, 64 또는 128 비트 (64 권장) |
| 구조 | Feistel 풍 네트워크 |
| 라운드 수 | 1-255 (원래 12 권장) |
| 암호 해독 | 244 개의 선택 평문 공격을 사용한 차분 해독법(12 라운드, 블록 크기 64 비트) |
2. 구조
RC5는 블록 암호의 일종으로, 블록 크기(32, 64, 128비트), 키 크기(0~2040비트), 라운드 수(0~255)를 조절할 수 있다. 일반적으로 64비트 블록 크기, 128비트 키, 12라운드가 권장된다.[1]
RC5의 핵심 기능은 데이터 종속 회전이다. 모듈러 덧셈과 XOR 연산을 사용하며, 파이스텔 네트워크 구조를 가진다. 암호화/복호화 과정은 단순하지만, 키 스케줄은 e와 황금비를 이용해 키를 확장하는 일방향함수를 포함하여 복잡하다. 이러한 특징 덕분에 RC5는 암호 분석가들의 연구 대상이 되었다.[1]
RC5는 RC5-w/r/b로 표현하며, w는 워드 크기(비트), r은 라운드 수, b는 키의 바이트 수이다.
2. 1. 기본 구조
RC5는 다양한 블록 크기(32, 64 또는 128비트), 키 크기(0~2040비트) 및 라운드 수(0~255)를 가질 수 있는 블록 암호이다. 원래 제안된 매개변수는 64비트 블록 크기, 128비트 키, 그리고 12라운드였다.RC5의 주요 특징은 데이터 종속 회전을 사용한다는 점이다. RC5는 모듈러 덧셈과 XOR 연산으로 구성되어 있으며, 알고리즘의 일반적인 구조는 파이스텔 네트워크와 유사하다. 암호화 및 복호화 루틴은 간단하지만, 키 스케줄은 e와 황금비의 이진 확장을 사용하여 키를 확장하는 일방향함수를 사용하기 때문에 더 복잡하다. 이러한 데이터 종속 회전과 알고리즘의 단순함은 RC5를 암호 분석가들에게 매력적인 연구 대상으로 만들었다.
RC5는 기본적으로 RC5-w/r/b로 표시되는데, 여기서 w는 워드 크기(비트), r은 라운드 수, b는 키의 바이트 수이다.
RC5는 라운드 함수에 사용되는 연산에 관한 연구와 평가를 촉진하기 위해 설계된 매우 단순한 구조를 가지고 있다. 데이터에 따라 회전 수가 변하는 것은 최대 차분(선형) 확률의 상한 평가를 복잡하게 만든다.[1]
다른 블록 암호와 달리 RC5는 3가지의 블록 길이(32, 64, 128비트), 임의의 키 길이(0부터 2040비트), 임의의 라운드 횟수(0부터 255)를 가진다. 원래 권장값은 블록 길이 64비트, 키 길이 128비트, 12 라운드이다.[1]
알고리즘의 기본 구조는 파이스텔 네트워크이다. 처음에 확장 키로 화이트닝한 후 라운드 함수를 지정 횟수만큼 반복한다. 키 스케줄은 복잡하지만, 암호화 및 복호화 루틴의 코드는 몇 줄 되지 않는다.[1]
라운드 함수는 XOR, 데이터 의존적 회전, 그리고 확장 키와의 나머지 덧셈의 세 가지 조합으로 구성된다.[1]
2. 2. 알고리즘 구성
RC5는 다른 많은 암호화 방식과 달리 블록 크기(32, 64, 128 비트), 키 크기(0~2040 비트), 라운드 수(0~255)를 가변적으로 설정할 수 있다. 원래 제안된 매개변수는 64비트 블록 크기, 128비트 키, 12라운드였다.RC5의 주요 특징은 데이터 종속 회전을 사용한다는 점이다. RC5는 모듈러 덧셈과 배타적 OR (XOR) 연산으로 구성된다. 알고리즘의 일반적인 구조는 Feistel 네트워크와 유사하다. 암호화 및 복호화 루틴은 몇 줄의 코드로 나타낼 수 있지만, 키 스케줄은 더 복잡하다. 키 스케줄은 e와 황금비의 이진 확장을 사용하여 키를 확장한다. 데이터 종속 회전과 알고리즘의 단순함은 암호 분석가들에게 RC5를 매력적인 연구 대상으로 만들었다.
RC5는 RC5-w/r/b로 표시된다. 여기서 w는 비트 단위의 워드 크기, r은 라운드 수, b는 키의 바이트 수이다.
2. 2. 1. 키 확장
RC5 암호화 및 복호화에서는 모두 임의 키를 2(r+1)개의 단어로 확장하며, 이 단어들은 암호화 및 복호화 과정에서 순차적으로 사용된다(각 단어는 한 번씩만 사용).[2] 키 확장 알고리즘은 의사 코드와 예시 C 코드로 설명할 수 있다.- 변수 설명
- : 단어의 비트 길이 (일반적으로 16, 32, 64). 암호화는 2단어 블록으로 수행된다.
- : 단어의 바이트 길이.
- : 키의 바이트 길이.
- : 바이트 배열로 간주되는 키 (0부터 시작하는 인덱스 사용).
- : 키의 단어 길이 (또는 b = 0인 경우 1).
- : 키 스케줄링 중에 사용되는 임시 작업 배열로, 단어 형식의 키로 초기화된다.
- : 데이터를 암호화할 때 사용할 라운드 수.
- : 필요한 라운드 서브키의 수.
- : 라운드 서브키 단어.
- : 첫 번째 매직 상수, 로 정의.
- 는 자연 로그의 밑
- 는 주어진 입력에 가장 가까운 홀수 정수
- : 두 번째 매직 상수, 로 정의.
- 는 황금비
- 는 주어진 입력에 가장 가까운 홀수 정수
- 에 따른 와 값 (16진수):
| 16 | 0xB7E1 | 0x9E37 |
| 32 | 0xB7E15163 | 0x9E3779B9 |
| 64 | 0xB7E151628AED2A6B | 0x9E3779B97F4A7C15 |
- 키 확장 알고리즘 의사 코드:
# K를 단어로 분해
# u = w / 8
c = ceiling(max(b, 1) / u)
# L은 처음에 0 값을 가진 c 길이의 w 길이 단어 목록입니다.
for i = b-1 down to 0 do:
L[i / u] = (L[i / u] <<< 8) + K[i]
# 키 독립적인 의사 난수 S 배열 초기화
# S는 처음에 정의되지 않은 w 길이 단어의 t=2(r+1) 길이 목록입니다.
S[0] = P_w
for i = 1 to t-1 do:
S[i] = S[i - 1] + Q_w
# 메인 키 스케줄링 루프
i = j = 0
A = B = 0
do 3 * max(t, c) times:
A = S[i] = (S[i] + A + B) <<< 3
B = L[j] = (L[j] + A + B) <<< (A + B)
i = (i + 1) % t
j = (j + 1) % c
# return S
- 예제 C 코드 (w = 32, r = 12, b = 16):
void RC5_SETUP(unsigned char *K)
{
// w = 32, r = 12, b = 16
// c = max(1, ceil(8 * b/w))
// t = 2 * (r+1)
WORD i, j, k, u = w/8, A, B, L[c];
for (i = b-1, L[c-1] = 0; i != -1; i--)
L[i/u] = (L[i/u] << 8) + K[i];
for (S[0] = P, i = 1; i < t; i++)
S[i] = S[i-1] + Q;
for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c)
{
A = S[i] = ROTL(S[i] + (A + B), 3);
B = L[j] = ROTL(L[j] + (A + B), (A + B));
}
}
2. 2. 2. 암호화
RC5는 가변 블록 크기(32, 64 또는 128비트), 키 크기(0~2040비트) 및 라운드 수(0~255)를 가진다. 원래 제안된 매개변수 선택은 64비트 블록 크기, 128비트 키 및 12라운드였다.RC5의 주요 기능은 데이터 종속 회전을 사용하는 것이다. RC5는 다양한 모듈러 덧셈과 XOR 연산으로 구성된다. 알고리즘의 일반적인 구조는 파이스텔 암호와 유사하다. 암호화 및 복호화 루틴은 몇 줄의 코드로 표현할 수 있다. 그러나 키 스케줄은 더 복잡하여, e와 황금비의 이진 확장을 사용하여 키를 확장한다.
RC5는 기본적으로 RC5-w/r/b로 표시된다. 여기서 w는 워드 크기(비트), r은 라운드 수, b는 키의 바이트 수이다.
암호화는 여러 라운드의 함수를 포함하며, 보안 및 시간 제약에 따라 12 또는 20 라운드가 권장된다. 이 알고리즘에서는 다음 변수가 사용된다.
- A, B: 암호화될 평문 블록을 구성하는 두 단어.
암호화 과정은 다음과 같다.
```
A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A ^ B) <<< B) + S[2 * i]
B = ((B ^ A) <<< A) + S[2 * i + 1]
# 암호문 블록은 A와 B로 구성된 두 단어 블록이다.
return A, B
```
Rivest가 제공한 C 코드 예시는 다음과 같다.
```c
void RC5_ENCRYPT(WORD *pt, WORD *ct)
{
WORD i, A = pt[0] + S[0], B = pt[1] + S[1];
for (i = 1; i <= r; i++)
{
A = ROTL(A ^ B, B) + S[2*i];
B = ROTL(B ^ A, A) + S[2*i + 1];
}
ct[0] = A; ct[1] = B;
}
```
RC5는 블록 길이를 32, 64, 128비트 중 선택 가능하고, 키 길이는 0부터 2040비트, 라운드 횟수는 0부터 255까지 임의로 설정할 수 있다. 원래 권장값은 블록 길이 64비트, 키 길이 128비트, 12 라운드였다.
알고리즘의 기본 구조는 파이스텔 네트워크이다. 라운드 함수는 XOR, 데이터 의존적 회전, 그리고 확장 키와의 나머지 덧셈의 세 가지 조합으로 구성된다.
2. 2. 3. 복호화
RC5의 복호화는 암호화 과정을 비교적 간단하게 되돌리는 방식으로 이루어진다. 아래는 복호화 과정을 나타내는 의사 코드이다.```python
for i = r에서 1까지 감소하면서 반복:
B = ((B - S[2 * i + 1]) >>> A) ^ A
A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]
return A, B
```
Rivest가 제공한 C 코드를 이용한 예시는 다음과 같다.
```c
void RC5_DECRYPT(WORD *ct, WORD *pt)
{
WORD i, B=ct[1], A=ct[0];
for (i = r; i > 0; i--)
{
B = ROTR(B - S[2*i + 1], A) ^ A;
A = ROTR(A - S[2*i], B) ^ B;
}
pt[1] = B - S[1]; pt[0] = A - S[0];
}
```
다른 블록 암호와 달리 RC5는 블록 크기(32, 64, 128비트), 키 길이(0부터 2040비트), 라운드 횟수(0부터 255)를 사용자가 임의로 설정할 수 있다. 원래 권장값은 블록 길이 64비트, 키 길이 128비트, 12 라운드였다.
알고리즘의 기본 구조는 파이스텔 네트워크이다. 처음에 확장 키로 화이트닝한 후 라운드 함수를 지정된 횟수만큼 반복한다. 암호화 및 복호화 루틴의 코드는 몇 줄로 간단하지만, 키 스케줄은 더 복잡하다.
라운드 함수는 XOR(배타적 논리합), RC5의 특징인 데이터 의존적 회전(rotation), 그리고 확장 키와의 나머지 덧셈의 세 가지 조합으로 구성된다.
3. 안전성
12라운드 RC5(64비트 블록)는 244개의 선택 평문을 사용한 차분 암호 분석에 취약하다.[3][9] 그러나 18~20라운드를 사용하면 충분한 보호를 제공할 수 있다고 알려져 있다.
RSA 시큐리티는 RC5 암호 해독에 대한 상금을 걸고 콘테스트를 진행했으나, 2007년 5월에 중단되었다.[4] 이후, distributed.net에서 이 상금을 후원하며 72비트 키 암호 해독을 계속 진행하고 있다.[8]
3. 1. 차분 공격
12라운드 RC5(64비트 블록 사용)는 244개의 선택 평문을 사용하여 차분 암호 분석에 취약하다.[3][9] 18~20 라운드가 충분한 보호를 제공하는 것으로 제안된다.3. 2. 암호 해독 콘테스트 및 분산 컴퓨팅
12라운드 RC5(64비트 블록 사용)는 244개의 선택 평문을 사용하여 차분 암호 분석에 취약하다.[3] 18~20 라운드가 충분한 보호를 제공하는 것으로 제안된다.이러한 도전 과제 중 다수는 분산 컴퓨팅을 사용하여 해결되었으며, 이는 Distributed.net에 의해 조직되었다. Distributed.net은 56비트 및 64비트 키로 암호화된 RC5 메시지를 무차별 대입했으며, 2002년 11월 3일부터 72비트 키를 크래킹하는 작업을 진행해 왔다.[4] 2023년 7월 26일 기준으로 키 공간의 10.409%가 검색되었으며, 해당 날짜에 기록된 속도를 기준으로 키 공간의 100%를 완료하는 데 59년 이상이 소요될 것으로 예상된다.[5] 이 작업은 클러스터 컴퓨팅 분야에서 많은 새롭고 참신한 발전을 이끌어냈다.[6]
알고리즘에 대한 (현재 만료된) 특허를 보유했던 RSA 시큐리티(RSA Security)[7]는 RC5로 암호화된 암호문을 해독하는 데 10000USD의 상금을 걸었지만, 이 대회는 2007년 5월을 기점으로 중단되었다.[4] 그 결과, distributed.net은 이 상금을 직접 후원하기로 결정했다. 승리 키를 발견한 개인은 1000USD, 해당 팀(있는 경우)은 1000USD, 그리고 자유 소프트웨어 재단(Free Software Foundation)은 2000USD를 받게 된다.[8]
4. 참고사항
RC5는 가변 블록 크기(32, 64 또는 128비트), 키 크기(0~2040비트), 라운드 수(0~255)를 갖는다. 원래 제안된 매개변수는 64비트 블록 크기, 128비트 키, 12라운드였다.
RC5의 주요 기능은 데이터 종속 회전을 사용하는 것이다. RC5는 다양한 모듈러 추가 기능과 XOR 연산으로 구성된다. 알고리즘의 구조는 파이스텔 네트워크와 유사하다. 키 스케줄은 e와 황금비의 이진 확장을 사용하여 키를 확장한다. 데이터 종속 회전과 알고리즘의 단순함은 RC5를 암호 분석가들에게 매력적인 연구 대상으로 만들었다. RC5는 보통 RC5-w/r/b로 표시되며, 여기서 w는 워드 크기(비트), r은 라운드 수, b는 키의 바이트 수이다.
참조
[1]
간행물
The RC5 Encryption Algorithm
http://theory.lcs.mi[...]
2004-12-18
[2]
웹사이트
http://people.csail.[...]
2018-09-21
[3]
간행물
Improved Cryptanalysis of RC5
https://link.springe[...]
1998-05-31
[4]
웹사이트
distributed.net: Project RC5
http://www.distribut[...]
2019-12-14
[5]
웹사이트
RC5-72 / Overall Project Stats
http://stats.distrib[...]
[6]
뉴스
PlayStation 3 supercomputer places UMass Dartmouth #1 in the world in code cracking challenge list
https://www.umassd.e[...]
University of Massachusetts Dartmouth
2024-01-24
[7]
특허
Block Encryption Algorithm With Data Dependent Rotation
1998-03-03
[8]
웹사이트
distributed.net: staff blogs – 2008 – September – 08
http://blogs.distrib[...]
2019-12-15
[9]
논문
Improved Cryptanalysis of RC5
[10]
간행물
The RC5 Encryption Algorithm
http://theory.lcs.mi[...]
2004-12-18
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com