手作りSSH の2 - 演算プリミティブ(exptmod),DH鍵交換

series security

以後、R6RSを使ってSSHを実装していく。

最初のステップ

本当の最初のステップはSSHのバージョンや、使用するアルゴリズムを同意することになるが、これは後回しにする。
最初のステップは、ホストとクライアントの間で"安全な"接続を確立することにある。これはDH鍵交換で行われる(RFC 4253,section 7)。
DH鍵交換(やRSA)には以下のアルゴリズムが必要になる。

  • a^b (mod p)
    • a * b (多倍長、以下同じ)
    • a >> 1
    • a mod p
  • ハッシュ(次回)
  • 乱数の生成

普通に接続、シェルセッションを使用するだけでは素数を生成する必要は無い。素数の生成は鍵を生成するときにだけ必要となる。
多倍長とは通常CPUで扱う整数よりも長い整数を処理することを言う。典型的なCPUは32bit単位の演算しか出来ないため、演算結果が32bitを超えたときに問題となる。schemeは多倍長(bigint)の演算を標準で備えていることが多いので、多倍長の乗算等を自分で実装する必要は無い。
乱数の生成も多倍長でなければならない。

乱数の生成(pre)

とりあえずSRFI-27を用いる。乱数は安全性の議論が必要になるため、より正確な実装が望ましい。
現時点ではmoshはSRFI-27をサポートしていないため、SRFI-19を用いた実装をとりあえず用意した(リファレンス実装を元にしている)。

a^b (mod p) (べき剰余)

RSA演算やDH鍵交換では、この形の演算を基本としている。

このアルゴリズムを単純にschemeで実装する。

(define (exptmod a b p)
  (define (exptmod-itr cur a b p)
      (if (= b 0) 
        cur
        (exptmod-itr 
          (if (odd? b) (mod (* a cur) p) cur) ;cur
          (mod (* a a) p) ;a
          (bitwise-arithmetic-shift-right b 1) ;b
          p ;p
          ))) (exptmod-itr 1 a b p))

一般に、schemeの数値は1/2といった分数を許すので、この手の演算をCから持ってくるときは注意する必要がある。

DH鍵交換

DH鍵交換は『公開された通信路で、2者が安全に乱数を共有できる』手順。
実際のアルゴリズムはRFC 4253 section 8に書かれているように、

  • x,y = 適切な数(乱数を使う)
  • g = generator (公開する : SSHでは一般にOrkley group 2を使う)
  • p = 大きな素数(公開する : SSHでは一般にOrkley group 2を使う)
  • e = g^x mod p
  • f = g^y mod p

としたときに、

  • K = f^x mod p = e^y mod p

であることを利用している。
Kが両者で一致することを実験してみる。

直接xやyを共有できるわけではないことに注意する。RSAは直接的に値を共有できる。

以降

このDH鍵交換により、仮に他人が通信路を覗いていたとしても、安全にある数Kを共有することが出来たことになる。
Kは直接鍵には使用せず、他の情報と連結して適当な長さにしたうえでhashを取り、そのhashの値を具体的な鍵とする(RFC 4253 section 8)。