電気通信大学 情報理工学域 II類
情報通信工学プログラム/電子情報学プログラム
情報通信工学実験B / 電子情報学実験B
実験課題「情報通信（情報セキュリティ）」

課題 1 のプログラムを作成するためのアプローチ例

以下に，課題 1 のRSA暗号のプログラムを作成するための方針例を示すので， 説明を順に読み進め，練習プログラムを作成してみよう.
cedにおいて，次の手順で以下に示すファイルを入手できる.
ただし，下記の手順において入手するファイルは， 「参考プログラム」 のページで入手したものと同じです．
  1. 作業用のディレクトリを作成する：
    2. >mkdir  ~/jikkenRSA
  2. 作業用のディレクトリに移動する：
    3. >cd  ~/jikkenRSA/
  3. ファイルをコピーする：
    4. >cp  /ced-home/staff/kurihara/prog/*  .
以上．
  1. コンパイル方法とデータの入出力についての練習プログラム
    1. 「コンソール画面に，「Hello!」 という文字を表示させるプログラムを作成せよ」 ( ヒント prg1.c を参照せよ)
    2. 「コンソール画面とキーボードから，整数 a と b を入力すると，和 a+b を計算し，コンソール画面に，計算結果を出力（表示）するプログラムを作成せよ」 ( ヒント prg2.c　を参照せよ )

  2. n を法としたべき乗計算についての練習プログラム
    1. 「整数 M, e, n を入力すると，べき乗 M^e (mod n) を計算し，出力するプログラムを作成せよ」 (ヒント : 上記の prg2.c を改良し作成してみよ)
      例えば，(M,e,n)=(288,29,323) のとき，(288)^(29)=67 (mod 323)となることを確認せよ．
      注意：べき乗を計算する pow関数を用いたのでは，正しく計算できない．
      (上記仕様のプログラムの例: 実行ファイル prg3.out を実行してみよ)

  3. ふりかえりと確認（バイトデータの取り扱い注意 ）
    1. 我々が計算機の入力装置として利用するキーボードの各キーに記されている 英数字や記号などは、 ASCII の 7ビット(または8ビット)英数字のコードに対応する。
    2. 例えば、大文字のゼット「 Ｚ 」は、ASCII での 16 進表示では 5A であり、 これを 7 ビット長の 2 進数表示すると 1011010 となる。 さらに、これを 10 進数表示すると、90(=64+16+8+2)となる。
    3. 計算機が処理するデータの単位は、バイト単位であることは知られている。 我々の実験でも 1 バイト単位でデータ処理できるプログラムの作成が目標であるが、 必ずしも簡単ではない。 データの扱いに工夫が必要となる。
    4. 工夫が必要になる場面は、データをファイルに書き出したり、読み込むときの処理である。 具体的には、C 言語では、ファイルからデータを読み込む関数 fgetc は 1 度に 1 バイトのデータしか 処理できない。同様に、ファイルにデータを書き込む関数 fputc　も 1 度に 1 バイトのデータしか 処理できない。
    5. 下方にある項目「練習プログラム(シフト暗号)」では、扱える文字の範囲を「大文字の英字」から 「 1 バイトで表現できる文字（データ）」に拡張するプログラムを作成せよ、というものである。 1 バイトで表現できるデータを 10 進数で表すと 0 から 255 の範囲に収まる。 ここで、注意することは、シフト暗号の暗号化や復号での計算手続きの性質上、 256 を法とした加法のみの演算であることより、 メッセージを暗号化した暗号文も、暗号文を復号したメッセージも 0～255 の範囲で正しく処理できることに注意する。

      たとえば、メッセージ　m ＝「Ｚ(=90)」、鍵　k＝「231」とすると、暗号文　c (= m + k (mod 256) ) は、
      　c = 90+231 (mod 256) = 65 (mod 256)
      となる。一方、復号では、
      　c+(-k) (mod 256) = 65+(-231) (mod 256) = -166 (mod 256) = 90 (mod 256)

      この事実より、暗号化の計算結果である暗号文は 1 バイトに収まるデータであることより、 そのまま fputc 関数を用いることで、暗号文ファイルに書き出すことができる。 一方、復号する際にも、暗号文は 1 バイトに収まるデータであることより、 暗号文ファイルから暗号文を　fgetc 関数で読み出して、復号の処理をする。 復号したデータは、 もともと 1 バイトに収まるデータであったはずであるから、fputc 関数を用いて復号データを書き込む ファイルに書き出せばよい、ということになる。
    6. 一方、RSA暗号の場合では、 1 バイトのメッセージを暗号化した暗号文は暗号化鍵 (e,n) の数値 n に依存する。 1 バイトのメッセージを暗号化するためには、数値 n の値は少なくとも、256 以上ではなくてはならい。 何故ならば，1 バイトのメッセージを表す 0～255 の 256 通りのメッセージを区別できなくてはならないから。 したがって、一般に、メッセージ m に対する暗号文 c は、暗号化の計算処理 c = m^(e) ( mod n ) により得られることより、暗号文 c の 10 進数表示は，必ずしも　0～255 の範囲には収まらない。 つまり、暗号文　c の　10　進数表示は、0 から　n-1 の範囲に収まるとことになる。 なぜなら、mod n は、n で割った余りだから。

      例えば、暗号化鍵 (5,323) の RSA 暗号において、メッセージ m を 具体的に大文字のシー「C」(10進数表示で67になる)として、暗号化すると、
      　c = m^(e) (mod n) = (67)^(5) (mod 323) = 288 (mod 323)
      となる。 （ここで、暗号化する具体的なメッセージの「大文字の C」 と暗号文を表す「 c （小文字）」の 両方が出現し、少しややこしいが、区別して下さい。）

      暗号文の 288 の値を 1 度の fputc 関数で暗号文ファイルに書き出そうとしても正しくデータを書き込むことはできない。 なぜなら、288 という数値データは、2 バイト以上のバイト数を用いて計算機内で表現されているデータであるから。 この問題をクリアーするには、2 バイト以上のデータを正確に幾つかの 1 バイトデータに分割し、それぞれを fputc 関数を用いて、暗号文ファイルに書き出せばよい。すなわち、分割したデータの個数分、 fputc 関数を実行すればよい。 （詳しくは、テキストの 「 8 節 プログラミング」 を参照せよ。 さらに，参考資料の ( fgetc, fputc 関数について(PDF)) を参照せよ。）
    7. 「ふりかえりと確認」の説明は、ここで終了。以下、本題の練習プログラムの作成に戻ります。

  4. 練習プログラム(シフト暗号)
    1. 課題テキストにて説明したシフト暗号では，メッセージと暗号文の 文字はいずれも26種類で，以下のように設定した．
      　メッセージ集合 {A,B,...,Z}={65,67,...,90}
      　暗号文集合 {A,B,...,Z}={65,67,...,90}
      　鍵集合 {0,1,...,25}
      このような仕様の参考プログラムの例としてシフト暗号の プログラムソース shift.c を参照せよ．

      上記のプログラムを 1 バイトのデータを扱えるプログラムに改良し， 以下の仕様を満たすシフト暗号のプログラムを作成せよ． つまり， メッセージと暗号文の文字はいずれも256種類とする．
      　メッセージ集合 {0,1,...,255}
      　暗号文集合 {0,1,...,255}
      　鍵集合 {0,1,...,255}

      具体的に， 暗号化，復元の操作を行い，正しく動作するか確認せよ.
      また， メッセージファイルfoo, 暗号化ファイルgoo, 復元ファイルhoo の3種類のファイルサイズを比較せよ.
      (上記仕様のプログラムの例: 実行ファイル shift-1byte.out を実行してみよ)

  5. 練習プログラム(RSA暗号)
    （以下のようにRSA暗号のプログラムを2タイプに分類している意図が理解できていると、課題1のRSA暗号のプログラムを書くことができると思います。）
    1. 以下の仕様を満たすRSA暗号のプログラムを作成せよ．
      メッセージの文字は128種類(7ビット)， 暗号文の文字は n 種類( 128 <= n <=255 ) となるように，制限を課した，以下のように設定する． つまり，この設定条件による制限により，暗号文の文字は 1 バイトで表現できるサイズとする．
      　メッセージ集合 {0,1,...,127}
      　暗号文集合 {0,1,...,n-1}

      具体的に， 公開鍵(e,n)=(59,187), 秘密鍵(d,n)=(19,187) で正しく動作するか確認せよ.
      また， メッセージファイルfoo, 暗号化ファイルgoo, 復元ファイルhoo の3種類のファイルサイズを比較せよ.
      (上記仕様のプログラムの例: 実行ファイル rsa128.out を実行してみよ)

    2. 上記のプログラムにおいて，メッセージの文字として， 1 バイトのデータを扱えるプログラムに改良し， 以下の仕様を満たすRSA暗号のプログラムを作成せよ(この練習プログラムが、テキストの「課題 1」になる )．
      　メッセージ集合 {0,1,...,255}
      　暗号文集合 {0,1,...,n-1}

      具体的には，メッセージの文字は 256 種類( 1 バイト= 8 ビット)， 暗号文の文字は n 種類( 2^8 = 256 <= n <= 2^(15) - 1 ) となるようにする． 暗号文の文字は 2 バイトで表現できるサイズとする．
      (上記の仕様を満たすプログラムの例： 実行ファイル rsa.out を実行してみよ)

(2018/10/2 update) owncloud~/home-uec/class/jikken/jikken2018/web/