(Updated 2022/5/20)（ 新しいバージョン 2022年度用の準備 ）
電気通信大学 情報理工学域 II類
情報通信工学プログラム/電子情報学プログラム
情報通信工学実験B / 電子情報学実験B
実験課題「情報通信（情報セキュリティ）」
課題 1 のプログラムを作成するためのヒント（練習プログラム）
以下に，課題 1 のRSA暗号のプログラムを作成するための方針例を示すので，
項目順に、説明を読み、そして、プログラムを作成した上で、次の項目に進むように作業をしてみよう.
途中を省くと、理解できなくなる場合があるので注意して下さい。
- 参考プログラムの取得方法
まずは、参考プログラムなどの資料を取得して下さい。
以下に示すプログラムのソースファイルと実行ファイルを，
実験課題のプログラム作成の参考に利用して構わない。
ただし，それらのファイルの利用は，コピーした本人が本課題を実施する場合のみに許可する。
コピーした本人以外に渡したり，ネット上に掲示し，二次配布することは禁止する．
-
西9号館2階の計算機実験室(CED)の計算機において，次の手順でファイルを入手できる：
（
「参考プログラムの取得方法の実行例」
を参照）
- ホームディレクトリに移動する：
$ cd
- 作業用のディレクトリを作成する：
$ mkdir ~/jikkenRSA2
- 作業用のディレクトリに移動する：
$ cd ~/jikkenRSA2
- ファイルをカレントディレクトリにコピーする：
$ cp /ced-home/staff/kurihara/prog4/* ./
- 入手したファイルを確認：
$ ls -l
-
参考プログラムは、見るだけでなく、コンパイルし、実行して、その動作を確認して下さい。
そして、プログラムの一部を変更した場合の動作を観察してみてください。
プログラムの記述内容と動作の関係を確認、理解できるようになると思います。
プログラムの実行途中の経過内容を知りたいときは、printf を追加して、変数にどのような値が代入されているのかを画面（ターミナル）に表示させて確認しましょう。
簡単にはプログラムを書くことはできないと思います。一つ一つの丁寧な試行錯誤が大切と思います。
- コンパイル方法とデータの入出力についての練習プログラム
- コンパイルの方法と実行方法
「コンソール画面に，「Hello!」 という文字を表示させるプログラムを作成する」
(ヒント：コンパイル方法と実行方法がコメントに記載されているプログラム prog1.c を参照)
- データの入出力の練習プログラム（その１）
「コンソール画面とキーボードから，整数 a と b を入力すると，和 a+b を計算し，コンソール画面に，計算結果を出力（表示）するプログラムを作成する」
(ヒント：プログラム prog2.c を参照)
- データの入出力の練習プログラム（その２）
n を法としたべき乗計算についての練習プログラム(RSA暗号でのべき乗計算の準備)
「整数 M, e, n を入力すると，べき乗 M^e (mod n) を計算し，出力するプログラムを作成する」
(ヒント : プログラム prog2.c を修正したプログラム prog3.c を参照)
修正のキーポイントは、主に以下の2点：
- 入力する整数の個数を1個増やす。
prog2.c での入力は「a, b」の2個であるが、prog3.c 場合、入力は「M, e, n」の3個であるから。
- 算術演算を変更する。
prog2.c での演算は加法「a+b」であるが、
prog3.c での演算はモジュロのあるべき乗「M^e (mod n)」となる。
動作の確認では，(M,e,n)=(288,29,323) のとき，(288)^(29)=67 (mod 323)となることを確認する．
大きな値を扱う場合、べき乗を計算する pow関数などの既存の関数を用いたのでは，正しく計算できない場合がありますので注意して下さい．
-
ファイル操作の練習プログラム
- ファイルをコピーする練習プログラム
「指定したファイルからデータを読み出し、 そして、指定したファイルにデータを書き込むプログラムを作成する」
（ヒント：ファイル操作の参考として、プログラム prog_copy.c を参照する）
- ファイル内の文字列中で英語の大(小)文字を小(大)文字に変換する練習プログラム
「（整数値 32 を指定すると）指定したファイル中にある大文字を小文字に変換する，または，その逆の小文字を大文字に変換するプログラムを作成する」
大文字から小文字への変換という文字の操作は算術演算で実現できます。prog_convert.c のコメント欄を参照して下さい。
（ヒント：ファイル中の文字操作の参考として、prog_copy.c を修正したプログラム prog_convert.c を参照）
(
プログラム prog_convert.c をコンパイルし、
実行ファイル prog_convert.out を作成する。そして、以下のように実行し、uecoo と goo の内容を比較し、変換できていることを確認してみよう。
実行方法の例：
-
実行
「$ ./prog_convert.out 32 uecoo goo」
)
-
odコマンドの使い方を確認しよう
暗号のプログラムを作成する前に，ひら文や暗号文の内容を確認する方法について確認しよう。
そこで、ファイルの内容を指定したフォーマットで表示する odコマンドについての実行例を以下に示す。
-
シフト暗号の暗号化鍵 k=5 を用いて暗号化したときの「ひら文」と「暗号文」の内容をodコマンド（オプション「 -t u1 」（1バイト単位））で表示する例を示す。
-
ひら文：「WEWILLMEETATCHOFUSTATION」
-
ひら文（整数表示）：「87 69 87 73 76 76 77 69 69 84 65 84 67 72 79 70 85 83 84 65 84 73 79 78」
-
暗号文：「BJBNQQRJJYFYHMTKZXYFYNTS」
-
暗号文（整数表示）：「66 74 66 78 81 81 82 74 74 89 70 89 72 77 84 75 90 88 89 70 89 78 84 83」
[sol:jikkenRSA]$
[sol:jikkenRSA]$ cat foo
WEWILLMEETATCHOFUSTATION
[sol:jikkenRSA]$ od -t u1 foo
0000000 87 69 87 73 76 76 77 69 69 84 65 84 67 72 79 70
0000020 85 83 84 65 84 73 79 78 10
0000031
[sol:jikkenRSA]$
[sol:jikkenRSA]$ ./shift.out -e 5 foo goo1
[sol:jikkenRSA]$ cat goo1
BJBNQQRJJYFYHMTKZXYFYNTS
[sol:jikkenRSA]$ od -t u1 goo1
0000000 66 74 66 78 81 81 82 74 74 89 70 89 72 77 84 75
0000020 90 88 89 70 89 78 84 83 10
0000031
[sol:jikkenRSA]$
-
RSA暗号の暗号化鍵 (e,n)=(5,323) を用いて暗号化したときの「ひら文」と「暗号文」の
内容をodコマンド（オプション「 -t u1 」（1バイト単位）と「 -t u2 」（2バイト単位））で表示する例を示す。
-
ひら文：「WEWILLMEETATCHOFUSTATION」
-
ひら文（整数表示）：「87 69 87 73 76 76 77 69 69 84 65 84 67 72 79 70 85 83 84 65 84 73 79 78」
-
暗号文：（catコマンドでは文字化けして表示される）
-
暗号文（整数表示）：「83 103 99 247 247 229 103 103 50 12 50 288 21 129 185 187 87 50 12 50 99 129 108」
[sol:jikkenRSA]$
[sol:jikkenRSA]$ cat foo
WEWILLMEETATCHOFUSTATION
[sol:jikkenRSA]$ od -t u1 foo
0000000 87 69 87 73 76 76 77 69 69 84 65 84 67 72 79 70
0000020 85 83 84 65 84 73 79 78 10
0000031
[sol:jikkenRSA]$
[sol:jikkenRSA]$
[sol:jikkenRSA]$ ./rsa.out -e 5 323 foo goo2
[sol:jikkenRSA]$ cat goo2
SgSc���gg2
2 ^A^U���W2
2c�l�[sol:jikkenRSA]$
[sol:jikkenRSA]$ od -t u1 goo2
0000000 83 0 103 0 83 0 99 0 247 0 247 0 229 0 103 0
0000020 103 0 50 0 12 0 50 0 32 1 21 0 129 0 185 0
0000040 187 0 87 0 50 0 12 0 50 0 99 0 129 0 108 0
0000060 193 0
0000062
[sol:jikkenRSA]$ od -t u2 goo2
0000000 83 103 83 99 247 247 229 103
0000020 103 50 12 50 288 21 129 185
0000040 187 87 50 12 50 99 129 108
0000060 193
0000062
[sol:jikkenRSA]$
- シフト暗号のプログラム作成
-
前記までに作成したプログラムを参考に、シフト暗号のプログラムを作成する。
-
課題テキストにて説明したシフト暗号では，
分かりやすい例として、人が読める大文字の英字の26文字のみを対象にしているため、
メッセージ集合、暗号文集合、鍵集合の
文字はいずれも26種類で，以下のように設定した．
ASCIIに対応させて、1バイトの8ビットを10進数の整数で表現する。
-
メッセージ集合 {A,B,...,Z}={65,67,...,90}
-
暗号文集合 {A,B,...,Z}={65,67,...,90}
-
鍵集合 {0,1,...,25}
- しかし、計算機で処理するデータは1バイト単位である。
そこで、26文字ではなく、1バイトで表現できる256種類の文字に対応する
シフト暗号のプログラムを作成する。つまり、
メッセージ集合、暗号文集合、鍵集合の
文字はいずれも256種類で，以下のように設定する．
1バイトの8ビットを10進数の整数で表現する。
-
メッセージ集合 {0,1,...,255}
-
暗号文集合 {0,1,...,255}
-
鍵集合 {0,1,...,255}
「上記の1バイトに対応するシフト暗号のプログラムを作成する」
（ヒント：シフト暗号のプログラムの例として、プログラム prog_shift.c を参照）
プログラム prog_shift.c は、前記までの項目
「1. コンパイル方法とデータの入出力についての練習プログラム」
「2. ファイル操作の練習プログラム」で作成した複数のプログラムを参考にして作成したものである。
(
プログラム prog_shift.c をコンパイルし、
実行ファイル prog_shift.out を作成する。そして、暗号化、復号化を実行し、diffコマンド（オプションの「-s」を付けるとよい）で 256byte.dat と hoo の差分を調べ、差分がなく一致することを確認してみよう。
実行方法の例：
-
暗号化「$ ./prog_shift.out -e 130 256byte.dat goo」
-
復号化「$ ./prog_shift.outt -d 130 goo hoo」
-
ファイルの比較「$ diff -s 256byte.dat hoo」
)
プログラム prog_shift.c を読んで、内容が分からない場合は、
前記までの項目で作成した複数のプログラムを読み返し、シフト暗号のプログラムを書く際に、
何がポイントになっているのかを考えてみよう。
- （制約のある）RSA暗号のプログラム作成
-
前記で扱ったシフト暗号のプログラム prog_shift.c を修正して、
次項に示す制約条件下で動作するRSA暗号のプログラムを作成してみよう。
修正のキーポイントは、主に以下の2点：
- 入力する鍵の整数の個数を1個増やす。
シフト暗号の鍵は「k」であるが、RSA暗号の場合、公開鍵は「e, n」、
または、秘密鍵は「d,n」であるから。
- 暗号化と復号化の算術演算を変更する。
例えば、prog_shift.c のシフト暗号の符号化の演算は、「 C = M + k (mod 256)」であるが、
RSA暗号の場合、「 C = M^e (mod n)」となる。
-
（制約条件）
メッセージの文字は128種類(7ビット)，
暗号文の文字は n 種類( 128 <= n <=255 )
となるように制限をして，以下のように設定する．
つまり，この設定条件による制限により，暗号文の文字は 1 バイトで表現できるサイズとする．
-
メッセージ集合 {0,1,...,127}
-
暗号文集合 {0,1,...,n-1}
メッセージ集合 {0,1,...,127} に対応する具体的な文字は、
ASCII
に記載された英数字、記号、制御コードなどのすべてに対応する。
したがって、正しく動作するか確認する際のひら文のファイルは、英数字で作成すればよいことに注意する。
- 上記の制約条件下で動作する参考プログラムの実行ファイル rsa128.out を
具体的に，公開鍵 (e,n)=(59,187), 秘密鍵 (d,n)=(19,187) で正しく動作するか確認してみよう.
ここで、187=11*17.
また，ひら文ファイル foo, 暗号化ファイル goo, 復元ファイル hoo の3種類のファイルサイズについても
比較してみる.
(
実行ファイル rsa128.out を実行し、diffコマンドで foo と hoo の差分を調べ、差分がなく一致することを確認してみよう。
つまり、正しく復元できることを確認してみよう。
実行方法の例：
-
暗号化「$ ./rsa128.out -e 59 187 foo goo」
-
復号化「$ ./rsa128.out -d 19 187 goo hoo」
-
ファイルの比較「$ diff -s foo hoo」
)
-
（鍵が制約条件を満たさない場合）
参考の実行ファイル rsa128.out は、制約のあるRSA暗号である。
実際に、制約条件を満たさない
公開鍵 (e,n)=(5,323), 秘密鍵 (d,n)=(29,323) で試し、foo と hoo が一致しないことを
確認してみよう。つまり、正しく復元できないことを確認してみよう。ここで、 255 < n=323 としていることで、条件「 128 <= n <= 255 」を満たさない。
(
実行方法の例：
-
暗号化「$ ./rsa128.out -e 5 323 foo goo」
-
復号化「$ ./rsa128.out -d 29 323 goo hoo」
-
ファイルの比較「$ diff -s foo hoo」
)
-
（ひら文（メッセージ）が制約条件「
メッセージ集合 {0,1,...,127}
」を満たさない場合）
また、
実行ファイル rsa128.out を用いて、
制約条件を満たさないメッセージ集合の文字を使用したひら文ファイルとして、256byte.dat を
暗号化し、そして、その暗号文を復号化して、正しく復元できないことを確認してみよう。
つまり、256byte.dat と hoo は一致しないことを確認してみよう。
ただし、鍵は、制約条件を満たす、公開鍵 (e,n)=(59,187), 秘密鍵 (d,n)=(19,187) とする。
(
実行方法の例：
-
暗号化「$ ./rsa128.out -e 59 187 256byte.dat goo」
-
復号化「$ ./rsa128.out -d 19 187 goo hoo」
-
ファイルの比較「$ diff 256byte.dat hoo」
)
-
上記で確認したように制約のあるRSA暗号のプログラムでは、メッセージ集合が1バイトで表現できる256種類の場合に対応できないことが分かる。その問題を解決するために、次の「ふりかえりと確認」の項目を読んで下さい。
-
ふりかえりと確認（バイトデータの取り扱い注意
）
（説明文は長いですが、有限長のデータしか扱えない計算機を操るには大切なことです）
-
我々が計算機の入力装置として利用するキーボードの各キーに記されている
英数字や記号などは、
ASCII
に記載されている英数字や記号のコードに対応し、7ビットで表現されていることに注意する。
-
例えば、大文字のゼット「 Ｚ 」は、ASCII での 16 進表示では 5A であり、
これを 7 ビット長の 2 進数表示すると 1011010 となる。
さらに、これを 10 進数表示すると、90(=64+16+8+2)となる。
-
計算機が処理するデータの単位は、バイト単位であることは知られている。
我々の実験でも 1 バイト単位でデータ処理できるプログラムの作成が目標であるが、
必ずしも簡単ではない。
データの扱いに工夫が必要となる。
-
工夫が必要になる場面は、データをファイルに書き出したり、読み込むときの処理である。
具体的には、C 言語では、ファイルからデータを読み込む関数 fgetc は 1 度に 1 バイトのデータしか
処理できない。同様に、ファイルにデータを書き込む関数 fputc も 1 度に 1 バイトのデータしか
処理できない。
-
下方にある項目「練習プログラム(シフト暗号)」では、扱える文字の範囲を「大文字の英字」から
「 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 関数を用いて復号データを書き込む
ファイルに書き出せばよい、ということになる。
-
一方、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))
を参照せよ。）
-
「ふりかえりと確認」の説明は、ここで終了。以下、本題のRSA暗号のプログラム作成に戻ります。
- RSA暗号のプログラム作成
（この時点で、制約のあるRSA暗号のプログラムを作成できていることと、
上記項目の「ふりかえりと確認（バイトデータの取り扱い注意）」を確認しているものとする。
）
作成した制約のあるRSA暗号のプログラムにおいて，メッセージの文字として，
1 バイトのデータを扱えるプログラムに改良し，
以下の仕様を満たすRSA暗号のプログラムを作成する(このプログラムが、テキストの「課題 1」になります)．
-
メッセージ集合 {0,1,...,255}
-
暗号文集合 {0,1,...,n-1}
具体的には，メッセージの文字は 256 種類( 1 バイト= 8 ビット)，
暗号文の文字は n 種類( 2^(8) = 256 <= n <= 2^(15) - 1 = 32767 )
となるようにする．
つまり，
暗号文の文字は 2 バイトで表現できるサイズとする．
(
上記の仕様を満たすプログラムの例：
実行ファイル rsa.out を実行し、
diffコマンドで foo と hoo の差分を調べ、差分がなく一致することを確認してみよう。
さらに、foo, goo, hoo のファイルサイズをを比較してみよう。
実行方法の例：
- 暗号化「$ ./rsa.out -e 5 323 foo goo」
- 復号化「$ ./rsa.out -d 29 323 goo hoo」
- ファイルの比較「$ diff -s foo hoo」
- ファイルサイズの比較「$ ls -la | grep oo」
)
以上