1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

2026年!初アウトプットをしよう
@embermaverick05

AESになれなかったRC6アルゴリズム

1
Posted at

1. はじめに

この記事では、RC6というアルゴリズムについて解説をする。

RC6とは、AES 選定コンペのファイナリストに選ばれた暗号アルゴリズムの一つであり、RSA 暗号で有名な Ron Rivest 氏らが設計したブロック暗号である。

1つのブロックを3つ以上に分割して、ラウンド処理を行う一般化フェイステル構造を取り、鍵長とブロック長が自由に変更できる柔軟性に富んでいるアルゴリズムである。

RC6のバージョンは、RC6-w/r/bで表す。ここで、$w$ は、処理の単位となるワード長（ビット）、$r$ はラウンド数、および $b$ は秘密鍵の長さ（バイト）である。この記事では、単位をビットに統一するため、以降は秘密鍵長をビット単位で表す。

この記事では、AESの候補として提出された、

  • $w = 32$
  • $r = 20$
  • $b = 128$

の時について述べる。そのため、以降 $w、r、b$ と書く場合は、上記の値を想定している。

ブロック暗号の歴史は 1977 年に始まる。同年、アメリカ合衆国の連邦情報処理標準規格（FIPS）として Data Encryption Standard （DES）が選定され、以後 20 年以上にわたり標準暗号として利用されてきた。後に脆弱性が見つかり、これを受け NIST は次世代ブロック暗号を選定するために Advanced Encryption Standard（AES）コンペティションを開催した。

このコンペでファイナリストに残った暗号の一つが RC6 である。

最終的に、AES 暗号として選出されたのは、 Rijndael というアルゴリズムで現在の標準的なブロック暗号である。ブロック暗号の AES というと、こちらの Rijndael を指す。

2. アルゴリズムの概要

ここでは、RC6 の暗号化処理の全体像を示す。詳細な数式やラウンド鍵を導出するラウンド関数の内部構造については、次章以降で説明する。

RC6 は、以下の3つのフェーズから構成される。

  1. 初期化処理
  2. ラウンド処理
  3. 最終処理

以降で用いる加算、減算、乗算演算は、$2^w$ を法とする剰余加算（mod $2^w$）を意味する。また、$a <<< t$ は左に $t$ ビットシフトを、$a >>> t$ は右に $t$ ビットシフトすることを意味している。

2.1. 初期化処理

ここでは、128 ビットの入力を、4つ（A、B、C、D）に分割する。そのうち $B$ と $D$ に対して、最初のラウンド鍵である $S[0]$、$S[1]$ を加算する。

\begin{cases}
B = B + S[0] \\
D = D + S[1]
\end{cases}

2.2. ラウンド処理

各ラウンドでは、$B$ と $D$ から中間値 $t$、$u$ を計算し、$A$ と $C$ を回転・加算して更新した後、（A、B、C、D）を巡回シフトする。

\forall i = 1, \dots, r:
\begin{cases}
t &= B \times (2B+1) <<< log_{2}{w} \\
u &= D \times (2D+1) <<< log_{2}{w} \\
A &= ((A \oplus t) <<< u) + S[2i] \\
C &= ((C \oplus u) <<< t) + S[2i+1] \\
(A,B,C,D) &\gets (B,C,D,A)
\end{cases}

2.3. 最終処理

最後に、$A$ と $C$ にラウンド鍵 $S[2r + 2], S[2r + 3]$ を加算し、（A、B、C、D）を連結したものを暗号文とする。

\begin{cases}
A = A + S[2r + 2] \\
C = C + S[2r + 3]
\end{cases}

3. 鍵スケジュールの処理

ここでは、2. アルゴリズム概要で出てきたラウンド鍵の導出法について述べる。

はじめに、$\mathrm{e}$ をネイピア数、$\phi$ を黄金比 $\dfrac{1+\sqrt{5}}{2}$ とする。

RC6 では、以下で定義される定数 $P_w$ および $Q_w$ を用いる。

\begin{cases}
P_w = \left\lfloor 2^w (\mathrm{e} - 2) \right\rfloor \\
Q_w = \left\lfloor 2^w (\phi - 1) \right\rfloor
\end{cases}

これらはそれぞれ $w$ ビットの奇数定数として用いられる。

特に $w = 32$ のとき、

\begin{align*}
2^{32}(e - 2) &= 3084996962.5426807 \dots \\
2^{32}(\phi - 1) &=2654435769.4972305 \dots
\end{align*}

であるから、

\begin{cases}
P_{32} = \texttt{3084996963} = \texttt{0xb7e15163} \\
Q_{32} = \texttt{2654435768} = \texttt{0x9e3779b9}
\end{cases}

となる。

次に、秘密鍵 $K$（128ビット）を $w$ ビット語の列として分割し、リスト $L = (L[0], L[1], \dots)$ に格納する。

今回のケースでは、$w = 32$ なので、$\dfrac{128}{32} = 4$より、$K = L[0]L[1]L[2]L[3]$ として扱う。

そのあと、ラウンド鍵を格納する配列 $S$ を、定数 $P_w$ および $Q_w$ を用いて初期化する。

// c = 鍵のワード数
// 今回のケースでは、b をビットとして定義しているので、c = b / w となる
// b をバイトでとった場合は、c = b / (w / 8) が正しい計算になる
c = b / w

// Step1. Pw/Qw で初期化
// 初項 Pw、公差 Qw の等差数列を作る
S[0] = Pw

for i=1 to 2r+3
    S[i] = S[i-1] + Qw

// Step2. S と L の混ぜ込み
A = B = 0
i = j = 0
v = 3 * max(2r + 4, c)

for s=1 to v
    A = S[i] = (S[i] + A + B) <<< 3
    B = L[j] = (L[j] + A + B) <<< (A + B)
    i = (i + 1) % (2r + 4)
    j = (j + 1) % c

Step1 の処理

ここでは、初項 Pw、公差 Qw の等差数列を作る。これにより、作成される $S$ のサイズは、今回のケース（$r = 20$ ）の場合 $2 \times 20 + 4 = 44$ である。

Step2 の処理

ここでは、作成した $S$ と $L$ の混ぜ込みを行う。はじめに、累算変数として用いられる $A$、$B$ と、配列のインデックス $i$、$j$ を0に初期化する。

この混ぜ込み処理のループ回数 $v$ は、配列 $S$ の要素数 $2r + 4$ と、秘密鍵 $K$ のワード数 $c = \dfrac{b}{w}$ のうち、大きいほうの値の3倍と定義されている。

v = 3 * max(2r + 4, c)

この3倍という設定は、秘密鍵のすべてのビットが $S$ の各要素に十分に拡散されるために実験的に導き出された値である。

また、$A$ の回転シフトは固定値（$= 3$ ）であるのに対して、$B$ はデータ依存の変数値（$=A + B$）が使われている。これにより、単純な線型処理ではない複雑な拡散を行うことができる。

4. 復号処理

復号は暗号化の逆の手順で行う。暗号化で使用した加算や左回転シフトの逆演算（減算、右回転シフト）を逆順で適用していく。

復号のプロセスは、次のとおりである。

  1. 最終処理の逆
  2. ラウンド処理の逆
  3. 初期化処理の逆

4.1. 最終処理の逆

暗号文の $A$、$C$ から $S[2r + 2]$、$S[2r+3]$ を減算する。

\begin{cases}
A = A - S[2r + 2] \\
C = C - S[2r + 3]
\end{cases}

4.2. ラウンド処理の逆

$i = r$ から $1$ まで、以下の処理を繰りかえす。

\forall i = r, \dots, 1:
\begin{cases}
(A,B,C,D) &\gets (D,A,B,C) \\
u &= D \times (2D+1) <<< log_{2}{w} \\
t &= B \times (2B+1) <<< log_{2}{w} \\
C &= ((C-S[2i+1]) >>> t) \oplus u \\
A &= ((A-S[2i])  >>> u) \oplus t
\end{cases}

1行目の以下の操作、

$$(A,B,C,D) \gets (D,A,B,C)$$

これは、暗号化時に各ラウンドの最後で行った巡回シフト

$$(A,B,C,D) \gets (B,C,D,A)$$

の逆操作に対応している。

4.3. 初期化処理の逆

最後に、$B$、$D$ から $S[0]$、$S[1]$ を減算し、結合して平文を得る。

\begin{cases}
B = B - S[0] \\
D = D - S[1]
\end{cases}

5. 実装例

Python による実装を次に示す。

split_block と join_block では、それぞれビッグエンディアンとリトルエンディアンに、リトルエンディアンをビッグエンディアンに変換している。これは、RC6の仕様がリトルエンディアンを基準として設計されているためである。

また、先ほど説明していない変数 LGW は、$\log_{2}{w} = \log_{2}{32} = 5$ を意味している。

# B = 128
# C = 4

class RC6:
  W = 32
  MOD = 1 << W
  R = 20
  LGW = 5
  Pw = 0xb7e15163
  Qw = 0x9e3779b9


  def __init__(self, key_128bit: int):
    self.key = key_128bit
    self.L = self.load_key_words(key_128bit)
    self.S = self.key_schedule()


  # –––––––––––––––––––––––––––––––––––––––––––
  # 32 bit 回転
  # –––––––––––––––––––––––––––––––––––––––––––
  def left_rotate(self, x, m):
    m = m % self.W
    left = x << m
    right = x >> (self.W - m)

    return (left | right) % self.MOD # 32 bit の出力にする

  def right_rotate(self, x, m):
    m = m % self.W
    left = x >> m
    right = x << (self.W - m)

    return (left | right) % self.MOD


  # –––––––––––––––––––––––––––––––––––––––––––
  # f-function  f(x) = x*(2x+1)  (mod 2^32)
  # –––––––––––––––––––––––––––––––––––––––––––
  def f(self, x):
    return (x * ((x << 1) + 1)) % self.MOD


  # –––––––––––––––––––––––––––––––––––––––––––
  # K(128 bit) -> L 配列（32bit x 4）
  # –––––––––––––––––––––––––––––––––––––––––––
  def load_key_words(self, key):
    b = key.to_bytes(16, 'big')
    L = []

    for i in range(0, 16, 4):
      L.append(int.from_bytes(b[i:i+4], 'little'))

    return L


  #––––––––––––––––––––––––––––––––––––––––––––
  # Key Schedule: S 配列の生成
  #––––––––––––––––––––––––––––––––––––––––––––
  def key_schedule(self):
    t = 2 * self.R + 4 # S の長さ
    S = [0] * t

    # Step 1: Pw/Qw で初期化
    S[0] = self.Pw
    for i in range(1, t):
      S[i] = (S[i - 1] + self.Qw) % self.MOD

    # Step 2: S と L の混ぜ込み
    a = b = 0
    i = j = 0
    v = 3 * max(t, len(self.L))

    for _ in range(v):
      a = S[i] = self.left_rotate((S[i] + a + b) % self.MOD, 3)
      b = self.L[j] = self.left_rotate((self.L[j] + a + b) % self.MOD, (a + b) % self.MOD)

      i = (i + 1) % t
      j = (j + 1) % len(self.L)

    return S # 完成したラウンド鍵


  #––––––––––––––––––––––––––––––––––––––––––––
  # 128bit → (A,B,C,D) 分割（little-endian）
  #––––––––––––––––––––––––––––––––––––––––––––
  @staticmethod
  def split_block(x128):
    b = x128.to_bytes(16, 'big')
    A = int.from_bytes(b[0:4], 'little')
    B = int.from_bytes(b[4:8], 'little')
    C = int.from_bytes(b[8:12],'little')
    D = int.from_bytes(b[12:16],'little')
    return A,B,C,D

  @staticmethod
  def join_block(A,B,C,D):
    return int.from_bytes(
        A.to_bytes(4,'little')+
        B.to_bytes(4,'little')+
        C.to_bytes(4,'little')+
        D.to_bytes(4,'little'),
        'big'
    )


  #––––––––––––––––––––––––––––––––––––––––––––
  # 暗号化
  #––––––––––––––––––––––––––––––––––––––––––––
  def encrypt(self, x128):
    A, B, C, D = self.split_block(x128)
    S = self.S

    B = (B + S[0]) % self.MOD
    D = (D + S[1]) % self.MOD

    for i in range(1, self.R + 1):
      t = self.left_rotate(self.f(B), self.LGW)
      u = self.left_rotate(self.f(D), self.LGW)

      A = (self.left_rotate(A ^ t, u % self.W) + S[2 * i]) % self.MOD
      C = (self.left_rotate(C ^ u, t % self.W) + S[2 * i + 1]) % self.MOD

      A, B, C, D = B, C, D, A

    A = (A + S[2 * self.R + 2]) % self.MOD
    C = (C + S[2 * self.R + 3]) % self.MOD

    return self.join_block(A, B, C, D)

  #––––––––––––––––––––––––––––––––––––––––––––
  # 復号
  #––––––––––––––––––––––––––––––––––––––––––––
  def decrypt(self, x128):
    A, B, C, D = self.split_block(x128)
    S = self.S

    C = (C - S[2 * self.R + 3]) % self.MOD
    A = (A - S[2 * self.R + 2]) % self.MOD

    for i in range(self.R, 0, -1):
      A, B, C, D = D, A, B, C

      u = self.left_rotate(self.f(D), self.LGW)
      t = self.left_rotate(self.f(B), self.LGW)

      C = self.right_rotate((C - S[2 * i + 1]) % self.MOD, t % self.W) ^ u
      A = self.right_rotate((A - S[2 * i])   % self.MOD, u % self.W) ^ t


    D = (D - S[1]) % self.MOD
    B = (B - S[0]) % self.MOD

    return self.join_block(A, B, C, D)


# 鍵の設定
key = 0x67452301efcdab893423120178675645  # Secret Key    秘密鍵

rc6 = RC6(key)

# 1. 文字列を16バイト → int に変換
text = "Good Morning!"
msg_bytes = text.encode("utf-8")
msg16 = msg_bytes.ljust(16, b"\x00")   # 16バイト化（RC6は固定長）

pt = int.from_bytes(msg16, "big")

# 2. RC6 で暗号化と復号
crypted_text = rc6.encrypt(pt)
decrypted_int = rc6.decrypt(crypted_text)

# 3. 復号結果
dec_bytes = decrypted_int.to_bytes(16, "big")
dec_text = dec_bytes.rstrip(b"\x00").decode("utf-8")

print("平文:", text)
print("暗号文:", hex(crypted_text))
print("元の平文:", dec_text)

実行結果を次に示す。

平文: Good Morning!
暗号文: 0xdba27ddf77b101272ae61e45444d7bc5
元の平文: Good Morning!

復号結果が平文と一致しているため、暗号化・復号処理が正しく行われたことが確認できる。

6. 参考資料

書籍

Webサイト・論文

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?