IT pass HikiWiki - [Exp2017]シェルスクリプト課題問題 2 のヒント Diff

{{toc}}

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

= アフィン暗号は, アルファベットを数字へ変換し("a"=0, "b"=1, ...., "z"=25), ある数 x (0-25) を以下の式で暗号化することをいいます.
  y =(a * x + b) mod 26
ただし, a, bは暗号化の鍵であり, γとF(γ)が1対1で対応付けられるために, aと26は互いに素になることが条件です. mod 26 は 26 で割った余りを表します. 暗号とは

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

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

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

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

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

# RT
文字,,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
x,,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

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

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

# RT
x,,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
y,,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??,??

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

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

アフィン暗号の復号は, 暗号化されたある数 y (0-25) から以下の式を用いて x を求めることにより行われます.
   x = a^{-1}(y α^{-1}(y - b) β) mod 26    ...(*)...(**)
ここで, a, b α, β は暗号化の鍵, a^{-1} α^{-1} は α a * a^{-1} α^{-1} ≡ 1 mod 26 を満たす数です.
# 例えば, a=3 α=3 の場合, a^{-1} α^{-1} は 9 になります(3 * 9 / 26 = 27 / 26 = 1 あまり 1).

= a^{-1} == α^{-1} の求め方

以下では, a^{-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} が今回知りたい a^{-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)=3, 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) が求まります. つまり, a^{-1} α^{-1} が求まったことになります.

= == 最後に

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