(updated 2021/08/17)

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

課題 1 のプログラムを作成するためのヒント（練習プログラム）

• まず、「参考プログラム」を参照して、参考プログラムを取得する。 参考プログラムの実行ファイルが a.out の場合、引き数なしに、「$ ./a.out」と実行することで、利用方法が表示される。

  $ ./rsa.out　 <--- （実行ファイルがrsa.outの場合の例）
  usage : ./rsa.out -[ed] e/d n InputFILE OutputFILE
  Try  `./rsa.out -h' for more information.
  $ 
  $ ./rsa.out -h　　<---（さらに、オプション「-h」を付けると、もう少し詳しい情報が得られる実行ファイルもある）
  Encryption : (e,n) is an encryption key.
             : ./rsa.out -e e n InputFILE OutputFILE
  Example    : (e, n, InputFILE, OutputFILE)=(9893, 32399, foo, goo)
             : ./rsa.out -e 9893 32399 foo goo
             : 
  Decryption : (d,n) is a decryption key.
             : ./rsa.out -d d n InputFILE OutputFILE
  Example    : (d, n, InputFILE, OutputFILE)=(7457, 32399, goo, hoo)
             : ./rsa.out -d 7457 32399 goo hoo
  $ 
  



• 以下に，課題 1 のRSA暗号のプログラムを作成するための方針例を示すので， 説明を順に読み進め，各練習プログラムを作成してみよう.


1. コンパイル方法とデータの入出力についての練習プログラム
   1. 「コンソール画面に，「Hello!」 という文字を表示させるプログラムを作成せよ」 ( ヒント：プログラム prg1.c を参照せよ)
   2. 「コンソール画面とキーボードから，整数 a と b を入力すると，和 a+b を計算し，コンソール画面に，計算結果を出力（表示）するプログラムを作成せよ」 ( ヒント：プログラム prg2.c　を参照せよ )
2. ふりかえりと確認（バイトデータの取り扱い注意 ）
   （説明文は長いですが、有限長のデータしか扱えない計算機を操るには大切なことです）
   1. 我々が計算機の入力装置として利用するキーボードの各キーに記されている 英数字や記号などは、 ASCII に記載されている英数字や記号のコードに対応し、7ビットで表現されていることに注意する。
   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. 「ふりかえりと確認」の説明は、ここで終了。以下、本題の練習プログラムの作成に戻ります。
   
   
3. 練習プログラム(シフト暗号)
   1. 課題テキストにて説明したシフト暗号では， 分かりやすい例として、人が読める大文字の英字の26文字のみを対象にしているため、 メッセージと暗号文の 文字はいずれも26種類で，以下のように設定した．
      • メッセージ集合 {A,B,...,Z}={65,67,...,90}
      • 暗号文集合 {A,B,...,Z}={65,67,...,90}
      • 鍵集合 {0,1,...,25}
   
   
   2. 「上記のシフト暗号を実現するプログラムを作成せよ。」
      （上記仕様のプログラムの例として、実行ファイル shift.out を実行してみよ．
      実行方法の例：
      • 暗号化「$ ./shift.out -e 5 foo goo」
      • 復号化「$ ./shift.out -d 5 goo hoo」
      ）
   
   
   3. プログラム作成の方針が分からない場合は、実行ファイル shift.out　のソースファイル　shift.c を 参考にしてよい。そのソースファイルは、以下のようにして得ることができる。（CEDの計算機にログインしている場合）

      >cp  /ced-home/staff/kurihara/prog2/shift.c  ./
      

   4. 情報基盤センターの sol.edu.cc.uec.ac.jp にリモートログインしている場合は、 以下の手順(wgetコマンド)でファイルを入手できる．
      

      >wget http://www.code.cei.uec.ac.jp/Class/jikken-cei/prog2/shift.c
      

   5. 次に、上記プログラム（shift.out）を 1 バイトのデータを扱えるプログラムに変更することを考える。 つまり， メッセージと暗号文の文字をいずれも次のような256種類とする．
      • メッセージ集合 {0,1,...,255}
      • 暗号文集合 {0,1,...,255}
      • 鍵集合 {0,1,...,255}
   
   
   6. 「上記の1バイトのデータを扱えるシフト暗号のプログラムを作成せよ。」
      (上記仕様のプログラムの例として、 実行ファイル shift-1byte.out を実行してみよ。
      実行方法の例：
      • 暗号化「$ ./shift-1byte.out -e 30 foo goo」
      • 復号化「$ ./shift-1byte.out -d 30 goo hoo」
      
      「 shift.out と shift-1byte.out　の実行結果の比較例」 を参照） )
      
      プログラムを作成したら、必ず、 具体的に，暗号化，復元の操作を行い，正しく動作するか確認せよ.
      また， メッセージファイルfoo, 暗号化ファイルgoo, 復元ファイルhoo の3種類のファイルサイズを比較せよ.
   
   
4. n を法としたべき乗計算についての練習プログラム(RSA暗号でのべき乗計算の準備)
   1. 「整数 M, e, n を入力すると，べき乗 M^e (mod n) を計算し，出力するプログラムを作成せよ」 (ヒント : 前記のプログラム prg2.c を改良し作成してみよ)
      例えば，(M,e,n)=(288,29,323) のとき，(288)^(29)=67 (mod 323)となることを確認せよ．
      注意：べき乗を計算する pow関数を用いたのでは，正しく計算できない．
      (上記仕様のプログラムの例: 実行ファイル prg3.out を実行してみよ。
      実行方法の例
      • 「$ ./prg3.out 288 29 323」
      )


5. 練習プログラム(RSA暗号)
   （以下のようにRSA暗号のプログラムを2タイプに分類している意図が理解できていると、課題1のRSA暗号のプログラムを書くことができると思います。）
   
   
   1. 以下の仕様を満たすRSA暗号のプログラムを作成せよ．
      メッセージの文字は128種類(7ビット)， 暗号文の文字は n 種類( 128 <= n <=255 ) となるように制限をして，以下のように設定する． つまり，この設定条件による制限により，暗号文の文字は 1 バイトで表現できるサイズとする．
      • メッセージ集合 {0,1,...,127}
      • 暗号文集合 {0,1,...,n-1}
      
      メッセージ集合 {0,1,...,127} に対応する具体的な文字は、 ASCII に記載された英数字、記号、制御コードなどのすべてに対応する。 したがって、正しく動作するか確認する際のメッセージは、英数字で作成すればよいことに注意する。
      
      具体的に， 公開鍵(e,n)=(59,187), 秘密鍵(d,n)=(19,187) で正しく動作するか確認せよ. ここで、187=11*17.
      また， メッセージファイルfoo, 暗号化ファイルgoo, 復元ファイルhoo の3種類のファイルサイズを比較せよ.
      (上記仕様のプログラムの例: 実行ファイル rsa128.out を実行してみよ。
      実行方法の例：
      • 暗号化「$ ./rsa128.out -e 59 187 foo goo」
      • 復号化「$ ./rsa128.out -d 19 187 goo hoo」
      )
   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.out -e 9893 32399 foo goo」
      • 復号化「$ ./rsa.out -d 7457 32399 goo hoo」
      ここで、32399=179*181.)

以上