Haskellの勉強 その3 : genD, gcdex
はじめに
色々あって更新に時間がかかりました…
勉強自体は進んでいるので書きたいことも増えているので頑張りたいです。
それでは今日も、Haskell で RSA暗号 を実装していきます。
処理がいい感じに複雑なので楽しいと思います！
実装内容
本エントリでは。鍵生成の
・ 秘密鍵 d の生成 : genD , gcdex
を実装します。
実装
genD
------------------------------------------- -- e * d ≡ 1 (mod φ(n)) -- e * d + m * φ(n) = 1 -- e * d + φ(n) * m = 1 ...1 -- 式 1 から拡張ユークリッド互除法より d を求める ------------------------------------------- genD :: Integer -> Integer -> Integer genD phn e = d `mod` phn where (_, d, _) = Multiplication.gcdex e phn
public static long GenD(long phn, long e) { return (Multiplication.GcdEx(e, phn)[1] + phn) % phn; }
どちらもほとんど同じ感じなソースですね！
Haskell で変な束縛がありますが、これはタプルに値を受け取るときに使わない要素がある場合は '_' と書いておくことで明示的にいらないと言ってます。
内容を比較してみます。
さっきほとんど一緒と言いましたが、微妙に違う場所がありますね。
Haskell では、戻ってきた値から直接剰余をとっていますが、 C# では剰余する値を足してからとっています。
これは、負数に対する剰余演算が違う挙動をするためです。
Haskell では、n, m を自然数とすると
\begin{eqnarray*}
-n \ {\rm mod} \ m = (m - n) \ {\rm mod} \ m
\end{eqnarray*}
という考え方*1になります。
一方 C# では
\begin{eqnarray*}
-n \ {\rm mod} \ m = - (n \ {\rm mod} \ m)
\end{eqnarray*}
という考え方*2となり、解が異なってしまいます。
どちらも考え方としてはあり*3なのですが、今考えたい世界では Haskell が正しい計算をしてくれています。
なので、C# では被除数が負数になることのないよう調整しています。
gcdex
ソースを載せる前に、拡張されたユークリッドの互除法について軽く説明を。
効率的に最大公約数を得るユークリッドの互除法というものがあるのですが、これに手を加えることで、a, b を既知の自然数として
\begin{eqnarray}
ax + by = gcd
\end{eqnarray}
となる x と y をついでに求めることができるよう拡張したものを拡張されたユークリッドの互除法とか呼んだりされています。
d の条件は、
\begin{eqnarray*}
ed&\equiv& 1\pmod {φ(n)} \newline
ed + mφ(n)&=& 1 \newline
\end{eqnarray*}
と表すことができます。
e 及び φ(n) が既知なので、式 (1) と同じ形となるため拡張されたユークリッドの互除法を適用でき、これから d を求めることができます。
具体的な手順は、
\begin{eqnarray*}
&r_0=ax_0+by_0 \\
&r_1=ax_1+by_1 \\
&\vdots \\
&r_n=ax_n+by_n \\
&\vdots \\
&r_{res}=ax_{res}+by_{res} \\
&r_{res+1}=ax_{res+1}+by_{res+1}=0 \\
\mbox{ただし}\\
&q_n=\lbrack r_{n-1} \div r_{n-2} \rbrack \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\\
&x_n=
\begin{cases}
1 & (n=0)\\
0 & (n=1)\\
x_{n-2}-p_n(x_{n-1})&(n\geqq2)
\end{cases}\\
\\
&y_n=
\begin{cases}
0 & (n=0)\\
1 & (n=1)\\
y_{n-2}-p_n(y_{n-1})&(n\geqq2)
\end{cases}\\
\end{eqnarray*}
です。
すると、${\rm r_{res}}={\rm gcd}(a,b)$ となっており、式(1)を満たす整数のペアが求まります。
意味を分かりやすくするため、同じ操作をする式を関数に抜き出しておきます。
\begin{eqnarray*}
\mbox{ここで}\\
&{\rm current}(n,m,q)=n-mq\\
\mbox{とおいて}\\
&x_n=
\begin{cases}
1 & (n=0)\\
0 & (n=1)\\
{\rm current}(x_{n-2},x_{n-1},q_n)&(n\geqq2)
\end{cases}\\
\\
&y_n=
\begin{cases}
0 & (n=0)\\
1 & (n=1)\\
{\rm current}(y_{n-2},y_{n-1},q_n)&(n\geqq2)
\end{cases}\\
\end{eqnarray*}
またこの時 $r_n = r_{n-2} \ {\rm mod} \ r_{n-1}$ となる性質もあり、実装にはこの式も使います。
これから書くソースを追いかけるために、手順だけ説明しました。
なぜこれで求まるかなどはここでは重要でないため、気になる方は参考のリンクを読んでみてください！
それでは実装に移ります。
Haskell
---------------------------- -- 拡張ユークリッド互除法 ---------------------------- gcdex :: Integer -> Integer -> (Integer, Integer, Integer) gcdex n m = gcdex' n m 1 0 0 1 where gcdex' :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer -> (Integer, Integer, Integer) gcdex' r0 r1 x0 x1 y0 y1 | r1 == 0 = (r0, x0, y0) | otherwise = gcdex' r1 r2 x1 x2 y1 y2 where (q, r2) = quotRem r0 r1 next n0 n1 = n0 - n1 * q x2 = next x0 x1 y2 = next y0 y1
public static long[] GcdEx(long a, long b) { long r0 = a, x0 = 1, y0 = 0, r1 = b, x1 = 0, y1 = 1, rw, xw, yw; long q; while(r1 > 0) { q = r0 / r1; rw = r0; xw = x0; yw = y0; r0 = r1; x0 = x1; y0 = y1; x1 = xw - x1 * q; y1 = yw - y1 * q; r1 = rw % r1; }
RSA暗号実装に当たり、書き方という点で最も差が出る関数だと感じています。
Haskell のソースを追いかけていきます。
gcdex n m = gcdex' n m 1 0 0 1
gcdex 関数そのものの定義はこれです。
怪しげな数字を入れて gcdex' 関数を呼び出していますね！
これは、実際の処理を隠すために where の下へ定義し、初期値を入れて呼び出しています。
ではその gcdex' の定義を見ていきましょう。
where 句の下に宣言されています。
where gcdex' r0 r1 x0 x1 y0 y1 | r1 == 0 = (r0, x0, y0) | otherwise = gcdex' r1 r2 x1 x2 y1 y2
なんか変なパイプができてきました。
これはガードと呼ばれ、条件を上から順番に評価していき True となった行の式を実行するものです。
崩してmax関数とか書いて数式と対比するとわかりやすいかも。
max a b | a > b = a | otherwise = b
これは、
\begin{eqnarray*}
{\rm max}(a,b)=
\begin{cases}
a & ( a > b ) \\
b & ( otherwise )
\end{cases}
\end{eqnarray*}
と同じ意味です。
見た目もほとんど一緒な感じ。
otherwise は論理値型の True と同じで、ここまで流れ込めば必ず実行されます。
switch 文の default と同じと思ってもいいかも！
これを頭に入れて読んでいきます。
gcdex' r0 r1 x0 x1 y0 y1
引数が多いですね…
でも、これが意味するところは数式からわかると思います。
\begin{align*}
&r_0=ax_0+by_0 \\
&r_1=ax_1+by_1
\end{align*}
でしたね！
この場合の $r_2,\ x_2,\ y_2$ は二つ手前までの式を持っていると求まるため、このような引数となっています。
次は、分かりやすさのため下の行から読みます。
| otherwise = gcdex' r1 r2 x1 x2 y1 y2
個人的に、最高に気持ちいい表現のできた行です！！
内容は、gcdex' を呼び出すだけの内容です。
つまり再帰してますね。
Haskell ではループ構文が基本的になく、再帰で繰り返しの処理を表現します。
再帰であるため、当然引数を変えて呼び出しています。
どのような再帰となっているかは一目瞭然ですね！
一つ添え字を進めて呼び出しています。
それでは飛ばした前の行に戻ってみます。
| r1 == 0 = (r0, x0, y0)
これは、再帰の終了条件となっています。
数式での $r_{res+1} = 0$ に当たります。
この一つ前の式に欲しい値が詰まっているので、添え字が 0 の値をまとめて返して終了となっています。
終了条件がはっきりと見えるため再帰でも読みやすくて安全！
何を返すのかも明確になってますね！
次は、添え字を進めるための定義を読みます。
where (q, r2) = quotRem r0 r1 next n0 n1 = n0 - n1 * q x2 = next x0 x1 y2 = next y0 y1
ここで出てくる quotRem 関数は、整数の除算と剰余を同時に得る関数です。
割ったついでに余りも取っとこうって関数です。
(割った結果, 余り) というタプルに入って返ってきます。
next関数は数式でのcurrent関数と一緒ですね。*4
これによって x と y を進め、$r_n = r_{n-2} \ {\rm mod} \ r_{n-1}$ だったので r はただ剰余をとるだけで進みます。
これに対する C# も少し見てみます。
めんどいのでソースは引っ張ってきませんが、ループの中でひたすらワーク変数に移しておいて加工して同じ変数にずらして代入して…といったよくある実装になっています。
考察
gcdex 関数が実装中も読んでいても面白い関数でした。
Haskell ではそもそも一つの関数につき一つの式が原則であるため、ループが基本的には表現できません。
それでもこの原則を貫くことで、見通しの良いソースとなるため、手続型の言語では読みづらいとされることの多い再帰処理の表現力が高まっているように感じました。
というか書かれてるのは数式そのものだから表現力は高いはず。
これに対して C# では、一応めいいっぱい読みやすく書いたつもりだけどやっぱりループでは同じ変数を違う意味に書き換えながらの処理となり、変数の数と比例して読みづらくなるように感じました。
また、式を与えられてない状況でこれだけを読んでも、どのような漸化式をたどっているか想像しづらいか、そもそも式を意識できないと思います。
メモリやスタックの制約が厳しい状態であれば C# のような実装にならざるを得ませんが、そうでなければループ（特に while のループ）を再帰にしてみると手続型でも場合によってはすっきりとしたスリムなソースになるかもしれません！
おわりに
RSA暗号自体はすでに実装済みですが、gcdex 関数が書いてる途中も読み直しても一番楽しいお気に入りの関数です。
再帰という表現方法は、以前から表現力が高い場面*5があると思っていましたが、こんな小さな関数でもここまでの差が出るのが面白いです。
手続型の言語において、なんでもかんでも再帰に書き直せばいいというものではないと思うけど、実装方法の一つに再帰もあると頭の片隅にでも置いておくと、動的な計算に芯が通りそうです。
参考
新潟大学 竹内照雄教授(2009) 拡張ユークリッド互除法
拡張されたユークリッド互除法について詳しく解説されております。
初めて実装したときに参考にさせていただきました。
rooooomania様(2015) Haskell で条件分岐 - Qiita
Haskell における分岐が、段階的かつシンプルにまとめられています。
ガード以外にも実行する式を変える方法の参考になります。
