[Exp2017]シェルスクリプト課題問題 2 のヒント

アフィン暗号を復号するスクリプトを書くためのヒントです

アフィン暗号とは

アフィン暗号は, アルファベットを数字へ変換し("a"=0, "b"=1, ...., "z"=25), その数 x を以下の式に代入して暗号化したものです.

y = (α * x + β) mod 26 ...(*)

ただし, α, β は暗号鍵であり, x と y が1対1で対応付けられるために, α と 26 は互いに素になることが条件です. mod 26 は 26 で割った余りを表します.

アルファベットと数字の対応表

アルファベットを数字 x に変換したときの対応表です.

文字abcdefghijklmnopqrstuvwxyz
x012345678910111213141516171819202122232425

アフィン暗号の復号方法 ヒント I (簡単)

(*)式を用いて, x, y の対応表を作成してみてください.

x012345678910111213141516171819202122232425
y????????????????????????????????????????????????????

暗号鍵が分かっているときに有効な方法です.

アフィン暗号の復号方法 ヒント II (難しい)

アフィン暗号の復号は, 暗号化されたある数 y (0-25) から以下の式を用いて x を求めることにより行われます.

x = α^{-1}(y - β) mod 26    ...(**)

ここで, α, β は暗号化の鍵, α^{-1} は α * α^{-1} ≡ 1 mod 26 を満たす数です.

α^{-1} の求め方

以下では, α^{-1} を求める方法を示します. p(1)^{-1} は以下の式を満たします.

p(1) * p(1)^{-1} ≡ 1 mod q ...(1)

ここで, p(1) は数列 p(n) の 1 番目の要素, q は任意の数(今回は q=26)です. (1) 式より,

p(1) * p(1)^{-1} = q(1) * n + 1,
q(1) * (-n) + p(1) * p(1)^{-1} = 1,
q(1) * x(1) + p(1) * y(1) = 1 ...(2)

が得られます. ここで, n は (1) 式の商, x(1) = -n は配列 x(n) の 1 番目の要素, y(1) = p(1)^{-1} は配列 y(n) の 1 番目の要素です. したがって, p(1)^{-1} が今回知りたい α^{-1} になります.

次に, (2) 式を一般化し, n で表せば,

q(n) * x(n) + p(n) * y(n) = 1 ...(3)

となります. また,

d(n) = q(n) / p(n)            ...(4)
m(n) = mod(q(n), p(n))        ...(5)

とおく. つまり, d(n) は q(n) を p(n) で割った商, m(n) は q(n) を p(n) で割った余りを表すので,

q(n) = d(n) * p(n) + m(n)

を満たします. これを用いると, (3) 式は,

(d(n) * p(n) + m(n)) * x(n) + p(n) * y(n) = 1,
(d(n) * x(n) + y(n)) * p(n) + m(n) * x(n) = 1

となります. したがって,

x(n+1) = (d(n) * x(n) + y(n)) ...(6)
y(n+1) = x(n)                 ...(7)
q(n+1) = p(n)                 ...(8)
p(n+1) = m(n)                 ...(9)

と置けば,

q(n+1) * x(n+1) + p(n+1) * y(n+1) = 1

となり, n+1 での関係式を得ることができます.

今回の課題 2 では, p(1)=2, q(1)=26 であるので, (5) 式より m(1) が求まることを用いて, (9) 式より p(2) が得られる. (8) 式より q(2) が求まります. これを可能な限り繰り返せば, p(n), q(n) を求まります. このとき, x(n) = 1, y(n) = 0 になります. 次に, これを用いて, (7) 式より x(n-1) が求まり, (6) 式より y(n-1) が求まります. これを x(1), y(1) まで繰り返せば, y(1) が求まります. つまり, α^{-1} が求まったことになります.

最後に

こうして得られた α^{-1} を用いれば, (**) より x が求まり, 復号できます. こちらのヒントに関して質問があれば, 研究室の人に遠慮なく聞いてください.

Last modified:2017/08/04 13:45:39
Keyword(s):
References:[[Exp2017]シェルスクリプト課題]