電気通信大学 情報理工学部 情報通信工学科
情報通信システム実験第二B / 電子情報システム実験第二B

実験課題「情報通信（情報セキュリティ）」

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

以下に，課題 1 のRSA暗号のプログラムを作成するための方針例を示すので， 説明を順に読み進め，練習プログラムを作成してみよう.
cedにおいて，次の手順で以下に示すファイルを入手できる.
ただし，下記の手順において入手するファイルは， 「参考プログラム」 のページで入手したものと同じです．

1. 作業用のディレクトリを作成する：
>mkdir ~/jikkenRSA
2. 作業用のディレクトリに移動する：
>cd ~/jikkenRSA/
3. ファイルをコピーする：
>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 )
   2. 上記のべき乗を計算するプログラムにおいて、 乗算回数をカウントし、その値を出力する機能を付加したプログラムを作成せよ。
      (上記仕様のプログラムの例: 実行ファイル prg3cnt.out )
3. 練習プログラム(課題 2 に関連したプログラム(べき乗の高速計算))
   1. テキストの 例4.3 に示した二進展開法を採用した場合の次のプログラムを作成せよ.
      「整数 M, e, n を入力すると，べき乗 M^e (mod n) を計算し，出力するプログラムを作成せよ」
      (上記仕様のプログラムの例: 実行ファイル prg3bin.out )
   2. 上記のべき乗を計算するプログラムにおいて、 乗算回数をカウントし、その値を出力する機能を付加したプログラムを作成せよ。
      (上記仕様のプログラムの例: 実行ファイル prg3bincnt.out )
4. 参考プログラム (ファイルデータの入出力と1バイトデータの処理)
   1. 次のプログラムを説明する前に， ファイルデータの入出力と 1バイトデータの取り扱いの理解を補助する プログラム a2av4.c を示す． このプログラムは，ファイルコピーを実行する プログラム a2a.c を改編したものである．
      プログラム a2av4.c をコンパイルし，実行してみよ. そして，プログラムソースと実行結果を比較し， ファイルデータの入出力と 1バイトデータがどのように処理されているか確認せよ。
5. ふりかえりと確認（バイトデータの取り扱い注意 ）(2016/09/16 追記)
   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 (= c + 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 以上ではなくてはならい。 したがって、一般に、メッセージ m に対する暗号文 c は、暗号化の計算処理 c = m^(e) ( mod n ) により得られることより、暗号文 c の 10 進数表示がかならずしも　0～255 の範囲に収まらない。
      
      例えば、暗号化鍵 (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 関数を実行すればよい。（詳しくは、テキストの 6 節を参照せよ。）
   7. 「ふりかえりと確認」の説明は、ここで終了。以下、本題の練習プログラムの作成に戻ります。

6. 練習プログラム(シフト暗号)
   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 )

7. 練習プログラム(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 )
      (さらに，上記の仕様を満たすRSA暗号で，途中結果を表示するプログラムの例： 実行ファイル prg5RSA.out )