練習プログラム（課題１のプログラムを作成するための）　 (電気通信大学情報理工学域 II類情報通信工学プログラム/電子情報学プログラム)

(Updated 2022/8/15)

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

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

以下に，課題 1 のRSA暗号のプログラムを作成するための方針例を示すので，項目順に、説明を読み、そして、プログラムを作成した上で、次の項目に進むように作業をしてみよう．途中を省くと、理解できなくなる場合があるので注意して下さい。

参考プログラムの取得方法

西9号館2階の計算機実験室(CED)の計算機において，次の手順でファイルを入手できる：
（「参考プログラムの取得方法の実行例」を参照）
1. ホームディレクトリに移動する：
2. 作業用のディレクトリを作成する：
3. 作業用のディレクトリに移動する：
4. ファイルをカレントディレクトリにコピーする：
5. 入手したファイルを確認：

参考プログラムは、見るだけでなく、コンパイルし、実行して、その動作を確認して下さい。

そして、プログラムの一部を変更した場合の動作を観察してみてください。プログラムの記述内容と動作の関係を確認、理解できるようになると思います。

プログラムの実行途中の経過内容を知りたいときは、printf を追加して、変数にどのような値が代入されているのかを画面（端末（ターミナル））に表示させて確認しましょう。

簡単にはプログラムを書くことはできないと思います。一つひとつの丁寧な試行錯誤が大切と思います。

コンパイル方法とデータの入出力についての練習プログラム
1. コンパイルの方法と実行方法
  
  「コンソール画面に，「Hello!」という文字を表示させるプログラムを作成する」
  
  (ヒント：コンパイル方法と実行方法がコメントに記載されているプログラム prog1.c を参照)
```
$ ls　// 用意されているファイルを確認
256byte.dat  prog2.c  prog_convert.c  rsa.out     shift.out
foo          prog3.c  prog_copy.c     rsa128.out  uecoo
prog1.c      prog4.c  prog_shift.c    shift.c
$ 
$ gcc -o prog1.out prog1.c    //オプション -o で実行ファイル名を prog1.out として、gccでコンパイル
$ ls -l | grep prog1
-rw-r--r-- 1 ka103019 faculty   744 Oct 22  2021 prog1.c
-rwxr-xr-x 1 ka103019 faculty 16696 Aug 15 10:05 prog1.out
$ ./prog1.out   //プログラムの実行
Hello!
$ 
```
2. データの入出力の練習プログラム（その１）
  
  「コンソール画面とキーボードから，整数 $a$ と $b$ を入力すると，和 $a+b$ を計算し，コンソール画面に，計算結果を出力（表示）するプログラムを作成する」
  
  (ヒント：プログラム prog2.c　を参照)
```
$ gcc -o prog2.out prog2.c    //コンパイル
$ ls -l | grep prog2
-rw-r--r-- 1 ka103019 faculty  2406 Oct 23  2021 prog2.c
-rwxr-xr-x 1 ka103019 faculty 16856 Aug 15 10:06 prog2.out
$ ./prog2.out 7 15   //プログラムの実行
7 + 15 = 22
$  
$ ./prog2.out    //入力値が足らない場合のプログラムの実行(利用方法が表示される)
 Error 
 usage  : ./prog2.out a b
 example: ./prog2.out 7 13
 ./prog2.out is an adder function such that a+b
$ 
```
3. データの入出力の練習プログラム（その２）
  
  正整数 $n$ を法としたべき乗計算についての練習プログラム(RSA暗号でのべき乗計算の準備)
  
  「整数 $M, e, n$ を入力すると，べき乗 $M^e$ (mod $n$) を計算し，出力するプログラムを作成する」
  
  (ヒント : プログラム prog2.c を修正したプログラム prog3.c を参照)
```
$ gcc -o prog3.out prog3.c    //コンパイル
$ ls -l | grep prog3
-rw-r--r-- 1 ka103019 faculty  4367 Oct 23  2021 prog3.c
-rwxr-xr-x 1 ka103019 faculty 16864 Aug 15 10:07 prog3.out
$ ./prog3.out 288 29 323   //プログラムの実行
(288)^(29) (mod 323) = 67
$ 
$ ./prog3.out    //入力値が足らない場合のプログラムの実行(利用方法が表示される)
Error 
 usage  : ./prog3.out M e n
 example: ./prog3.out 67 5 323
 ./prog3.out is a power function such that M^e (mod n)
$ 
```
  修正のキーポイントは、主に以下の2点：
  1. 入力する整数の個数を1個増やす。
    prog2.c での入力は「$a, b$」の2個であるが、prog3.c の場合、入力は「$M, e, n$」の3個であるから。
  2. 算術演算を変更する。
    prog2.c での演算は加法「$a+b$」であるが、 prog3.c での演算はモジュロのあるべき乗「$M^e$ (mod $n$)」となる。
  動作の確認では，($M,e,n$)=($288,29,323$) のとき，$288^{29}=67$ (mod $323$)となることを確認する．
  大きな値を扱う場合、べき乗を計算する pow関数などの既存の関数を用いたのでは，正しく計算できない場合がありますので注意して下さい．プログラム prog3.c を参照して下さい。
4. （チャレンジ練習プログラム）データの入出力の練習プログラム（その3）
  （注意：課題1を目標としている場合は、この練習プログラムを飛ばし、次の項目へ進んで下さい。課題2を実施する際に、改めて、この練習プログラムを実施して下さい。）
  
  2進展開法を用いた $n$ を法としたべき乗計算についての練習プログラム(高速版RSA暗号でのべき乗計算の準備)
  
  「整数 $M, e, n$ を入力すると，べき乗 $M^e$ (mod $n$) を2進展開法を用いて計算し，出力するプログラムを作成する」
  
  (2進展開法については本課題のテキストの例6.2を参照して下さい)
  (ヒント : プログラム prog3.c を修正したプログラム prog4.c を参照)
```
$ gcc -o prog4.out prog4.c    //コンパイル
$ ls -l | grep prog4
-rw-r--r-- 1 ka103019 faculty  6102 Aug 14 12:30 prog4.c
-rwxr-xr-x 1 ka103019 faculty 16864 Aug 15 10:09 prog4.out
$ ./prog4.out 288 29 323   //プログラムの実行
(M,e,n)=(288, 29, 323) -> (288)^(29)(mod 323)
(q,r,t,x,y)=(   0,    0,   29,    1,  288)
(q,r,t,x,y)=(  14,    1,   14,  288,  256)
(q,r,t,x,y)=(   7,    0,    7,  288,  290)
(q,r,t,x,y)=(   3,    1,    3,  186,  120)
(q,r,t,x,y)=(   1,    1,    1,   33,  188)
(q,r,t,x,y)=(   0,    1,    1,   67,  188)
the total number of multiplications of x*y in step 3 is  4
the total number of multiplications of y*y in step 4 is  4
(288)^(29) (mod 323) = 67
$ 
```

ファイル操作の練習プログラム

ファイルをコピーする練習プログラム

「指定したファイルからデータを読み出し、そして、指定したファイルにデータを書き込むプログラムを作成する」

$ gcc -o prog_copy.out prog_copy.c    //コンパイル
$ ls -l | grep copy
-rw-r--r-- 1 ka103019 faculty  4687 Oct 25  2021 prog_copy.c
-rwxr-xr-x 1 ka103019 faculty 17032 Aug 15 10:24 prog_copy.out
$ cat uecoo
The University of Electro Communications
$ ./prog_copy.out uecoo goo   //プログラムの実行
$ ls -l | grep oo
-rw-r--r-- 1 ka103019 faculty    25 Jul 23  2020 foo
-rw-r--r-- 1 ka103019 faculty    41 Aug 15 10:25 goo
-rw-r--r-- 1 ka103019 faculty    41 Jul 23  2020 uecoo
$ cat goo
The University of Electro Communications
$ diff -s uecoo goo   //オプション -s を設定し、diffコマンドでファイルを比較する
ファイル uecoo と goo は同一です
$ 
$ ./prog_copy.out     //入力値が足らない場合のプログラムの実行(利用方法が表示される)
 Error
 usage : ./prog_copy.out InputFILE OutputFILE
 Example : ./prog_copy.out foo goo
$

ファイル内の文字列中で英語の大(小)文字を小(大)文字に変換する練習プログラム

「（整数値 32 を指定すると）指定したファイル中にある大文字を小文字に変換する，または，その逆の小文字を大文字に変換するプログラムを作成する」

実行「 $ ./prog_convert.out 32 uecoo goo」

$ gcc -o prog_convert.out prog_convert.c     //コンパイル
$ ls -l | grep convert
-rw-r--r-- 1 ka103019 faculty  8192 Oct 25  2021 prog_convert.c
-rwxr-xr-x 1 ka103019 faculty 17088 Aug 15 10:29 prog_convert.out
$ cat uecoo
The University of Electro Communications
$ ./prog_convert.out 32 uecoo goo    //値32を指定してプログラムを実行
$ cat goo
tHE uNIVERSITY OF eLECTRO cOMMUNICATIONS
$ ./prog_convert.out 17 uecoo goo    //間違った入力によるプログラムの実行
 Error : Your input number 17 is wrong, please input 32. 
$ ./prog_convert.out         //入力値が足らない場合のプログラムの実行(利用方法が表示される)
 Error
 usage : ./prog_convert.out 32 InputFILE OutputFILE
 Example : ./prog_convert.out 32 foo goo
$

odコマンドの使い方を確認しよう

暗号のプログラムを作成する前に，ひら文や暗号文の内容を確認する方法について確認しよう。そこで、ファイルの内容を指定したフォーマットで表示する odコマンドについての実行例を以下に示す。
1. シフト暗号の暗号化鍵 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」
```
$ cat foo
WEWILLMEETATCHOFUSTATION
$ 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
$ ./shift.out -e 5 foo goo1   // shift暗号の実行ファイル shift.out で暗号化
$ cat goo1
BJBNQQRJJYFYHMTKZXYFYNTS
$ od -t u1 goo1   // オプション「-t u1」でodコマンドを実行
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
$ 
```
2. 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」
```
$ cat foo
WEWILLMEETATCHOFUSTATION
$ 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
$ ./rsa.out -e 5 323 foo goo2   // rsa暗号の実行ファイル rsa.out で暗号化
$ cat goo2
SgSc���gg2
          2 ���W2
                 2c�l�$ 
$ 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
$ od -t u2 goo2    // オプション「-t u2」でodコマンドを実行
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
$ 
```

シフト暗号のプログラム作成

前記までに作成したプログラムを参考に、シフト暗号のプログラムを作成する。

課題テキストにて説明したシフト暗号では，分かりやすい例として、人が読める大文字の英字の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.out -e 130 256byte.dat goo」
復号化「$ ./prog_shift.out -d 130 goo hoo」
ファイルの比較「$ diff -s 256byte.dat hoo」

$ gcc -o prog_shift.out prog_shift.c   //コンパイル
$ ls -l | grep prog_shift
-rw-r--r-- 1 ka103019 faculty  8706 Oct 24  2021 prog_shift.c
-rwxr-xr-x 1 ka103019 faculty 17160 Aug 15 10:49 prog_shift.out
$ ./prog_shift.out -e 130 256byte.dat goo   //暗号化
$ ./prog_shift.out -d 130 goo hoo           //復号化
$ od -t u1 256byte.dat 
0000000   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0000020  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
0000040  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
0000060  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
0000100  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
0000120  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
0000140  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
0000160 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
0000200 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
0000220 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
0000240 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
0000260 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
0000300 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
0000320 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
0000340 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
0000360 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
0000400
$ od -t u1 goo
0000000 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
0000020 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
0000040 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
0000060 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
0000100 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
0000120 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
0000140 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
0000160 242 243 244 245 246 247 248 249 250 251 252 253 254 255   0   1
0000200   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
0000220  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33
0000240  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49
0000260  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65
0000300  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81
0000320  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97
0000340  98  99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
0000360 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
0000400
$ diff -s 256byte.dat hoo    //ファイルの比較
ファイル 256byte.dat と hoo は同一です
$ 
$ ./prog_shift.out          //入力値が足らない場合のプログラムの実行(利用方法が表示される)
 Error
 usage : ./prog_shift.out -[ed] k InputFILE OutputFILE
 Example(encoding) : ./prog_shift.out -e 5 foo goo
        (decoding) : ./prog_shift.out -d 5 goo hoo
$

（制約のある）RSA暗号のプログラム作成

「前記で扱ったシフト暗号のプログラム　prog_shift.c を修正して、次項に示す制約条件下で動作するRSA暗号のプログラムを作成する。」

修正のキーポイントは、主に以下の2点：
1. 入力する鍵の整数の個数を1個増やす。
  シフト暗号の鍵は「$k$」であるが、RSA暗号の場合、公開鍵は「$e, n$」、または、秘密鍵は「$d,n$」であるから。
2. 暗号化と復号化の算術演算を変更する。
  例えば、prog_shift.c のシフト暗号の符号化の演算は、「 $C = M + k$ (mod $256$)」であるが、 RSA暗号の場合、「 $C = M^e$ (mod $n$)」となる。

（制約条件）　メッセージの文字は128種類(7ビット)，暗号文の文字は $n$ 種類( $128 \leq n \leq 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\times 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」

)

$ ls -l | grep rsa
-rwxr-xr-x 1 ka103019 faculty 13232 Jul 23  2020 rsa.out
-rwxr-xr-x 1 ka103019 faculty 13240 Jul 23  2020 rsa128.out
$ cat foo
WEWILLMEETATCHOFUSTATION
$ ./rsa128.out -e 59 187 foo goo    //暗号化
$ ./rsa128.out -d 19 187 goo hoo    //復号化
$ ls -l | grep oo
-rw-r--r-- 1 ka103019 faculty    25 Jul 23  2020 foo
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 11:02 goo
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 10:42 goo1
-rw-r--r-- 1 ka103019 faculty    50 Aug 15 10:44 goo2
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 11:02 hoo
-rw-r--r-- 1 ka103019 faculty    41 Jul 23  2020 uecoo
$ diff -s foo hoo    //ファイルの比較
ファイル foo と hoo は同一です
$ 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
$ od -t u1 goo
0000000  76 103  76  96  87  87  66 103 103 118  10 118  67  13 182  25
0000020  51 145 118  10 118  96 182 122  54
0000031
$ od -t u1 hoo
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
$ 
$ ./rsa128.out      //入力値が足らない場合のプログラムの実行(利用方法が表示される)
usage : ./rsa128.out -[ed] e/d n InputFILE OutputFILE
Try  `./rsa128.out -h' for more information.
$ 
$ ./rsa128.out -h    //オプション「-h」を指定して詳しい利用法を表示
Encryption : (e,n) is an encryption key.
           : ./rsa128.out -e e n InputFILE OutputFILE
Example    : (e, n, InputFILE, OutputFILE)=(59, 187, foo, goo)
           : ./rsa128.out -e 59 187 foo goo
           : 
Decryption : (d,n) is a decryption key.
           : ./rsa128.out -d d n InputFILE OutputFILE
Example    : (d, n, InputFILE, OutputFILE)=(19, 187, goo, hoo)
           : ./rsa128.out -d 19 187 goo hoo
$

（鍵が制約条件を満たさない場合）　
参考の実行ファイル rsa128.out は、制約のあるRSA暗号である。実際に、制約条件を満たさない公開鍵 $(e,n)=(5,323)$, 秘密鍵 $(d,n)=(29,323)$ で試し、foo と hoo が一致しないことを確認してみよう。つまり、正しく復元できないことを確認してみよう。ここで、　$255 < n=323$ としていることで、条件「 $128 \leq n \leq 255$ 」を満たさない。
(
実行方法の例：

暗号化「$ ./rsa128.out -e 5 323 foo goo」
復号化「$ ./rsa128.out -d 29 323 goo hoo」
ファイルの比較「$ diff -s foo hoo」

)

$ ./rsa128.out -e 5 323 foo goo    //暗号化
$ ./rsa128.out -d 29 323 goo hoo    //復号化
$ ls -l | grep oo
-rw-r--r-- 1 ka103019 faculty    25 Jul 23  2020 foo
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 11:05 goo
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 10:42 goo1
-rw-r--r-- 1 ka103019 faculty    50 Aug 15 10:44 goo2
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 11:05 hoo
-rw-r--r-- 1 ka103019 faculty    41 Jul 23  2020 uecoo
$ diff -s foo hoo   //ひら文ファイル foo と復号したファイル hoo が一致しないことが確認できる
1c1
< WEWILLMEETATCHOFUSTATION
---
> WEWILLMEETAT�HOFUSTATION
$ cat foo
WEWILLMEETATCHOFUSTATION
$ cat goo
SgSc���gg2
          2!���W2
                 2c�l�$ 
$ cat hoo
WEWILLMEETAT�HOFUSTATION
$ 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
$ od -t u1 goo
0000000  83 103  83  99 247 247 229 103 103  50  12  50  33  21 129 185
0000020 187  87  50  12  50  99 129 108 193
0000031
$ od -t u1 hoo
0000000  87  69  87  73  76  76  77  69  69  84  65  84 203  72  79  70
0000020  85  83  84  65  84  73  79  78  10
0000031
$

（ひら文（メッセージ）が制約条件「メッセージ集合 $\{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 -s 256byte.dat hoo」

)

$ ./rsa128.out -e 59 187 256byte.dat goo    //暗号化
$ ./rsa128.out -d 19 187 goo hoo            //復号化
$ ls -l | grep 256byte
-rw-r--r-- 1 ka103019 faculty   256 Jul 23  2020 256byte.dat
$ ls -l | grep oo
-rw-r--r-- 1 ka103019 faculty    25 Jul 23  2020 foo
-rw-r--r-- 1 ka103019 faculty   256 Aug 15 11:11 goo
-rw-r--r-- 1 ka103019 faculty    25 Aug 15 10:42 goo1
-rw-r--r-- 1 ka103019 faculty    50 Aug 15 10:44 goo2
-rw-r--r-- 1 ka103019 faculty   256 Aug 15 11:11 hoo
-rw-r--r-- 1 ka103019 faculty    41 Jul 23  2020 uecoo
$ diff -s 256byte.dat hoo   //ひら文ファイル 256byte.dat と復号したファイル hoo が一致しないことが確認できる
バイナリーファイル 256byte.dat とhoo は異なります
$ 
$ cat 256byte.dat 
	


�123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~��������������������������������������������������������������������������������������������������������������������������������$
$ 
$ cat goo
\/�Z��16�H���D4�~b
                  8tF�.Jj;:@Ok�h X
                                  �	eU]m�-'0$��?(&
`IRWBz�}���v3�L���5���,o2�E*>Aydir[�p�T�xn���|����7N^�fV�)���c�S%Pl{������Qq��uG��Y=��ws���a9�_<�\/�Z��16�H���D4�~b
                                   8tF�.Jj;:@Ok�h X
                                                   �	eU]m�-'0$��?(&
MC$ 
$ 
$ cat hoo
	


�123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~�����������������������������������������������������������


�123456789:;<=>?@ABCD$ 
$ 
$ 
$ od -t u1 256byte.dat 
0000000   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0000020  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
0000040  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
0000060  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
0000100  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
0000120  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
0000140  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
0000160 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
0000200 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
0000220 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
0000240 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
0000260 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
0000300 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
0000320 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
0000340 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
0000360 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
0000400
$ od -t u1 goo
0000000   0   1 127  92  47 130  90 184 172  49  54 165  23  72 180 179
0000020 152  68  52 161 126  98  11  56 116  70 168  20  46  74 106  27
0000040  43  33  34 171  59  58  64  79 107 150 104  32  88  12   6   4
0000060 146   9 101  85  18  93 109 132  45  39  48  36 185 156  63  40
0000100  38  10  77  67  17 103  25  75  13  96  73  82  87  66 122 182
0000120 125 157 163 145 118  51 137  76 143 166  28 158  14  53 134 173
0000140  29 159  21  44 111  50 136  69  42  24  30  62   5  65 121 100
0000160 105 114  91 174 112 162  84 170 120 110 177 149 147 124  31   2
0000200 151 139 148 142  55  78  94 169 102  86 178  41 183 181 175  99
0000220 155  83  37  80 108 123 129 128  16 153 154 144 160  81 113 141
0000240 167  19 117  71 131 176  89  61  26 135 119  35   8   7 115 164
0000260  22 133 138  15   3  97  57 140  95  60 186   0   1 127  92  47
0000300 130  90 184 172  49  54 165  23  72 180 179 152  68  52 161 126
0000320  98  11  56 116  70 168  20  46  74 106  27  43  33  34 171  59
0000340  58  64  79 107 150 104  32  88  12   6   4 146   9 101  85  18
0000360  93 109 132  45  39  48  36 185 156  63  40  38  10  77  67  17
0000400
$ od -t u1 hoo
0000000   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0000020  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
0000040  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
0000060  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
0000100  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
0000120  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
0000140  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
0000160 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
0000200 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
0000220 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
0000240 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
0000260 176 177 178 179 180 181 182 183 184 185 186   0   1   2   3   4
0000300   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
0000320  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36
0000340  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52
0000360  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68
0000400
$

上記で確認したように制約のあるRSA暗号のプログラムでは、メッセージ集合が1バイトで表現できる256種類の場合に対応できないことが分かる。その問題を解決するために、次の「ふりかえりと確認」の項目を読んで下さい。

ふりかえりと確認（バイトデータの取り扱い注意）

（説明文は長いですが、有限長のデータしか扱えない計算機を操るには大切なことです）
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 \sim 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\sim255$ の 256 通りのメッセージを区別できなくてはならないから。したがって、一般に、メッセージ $m$ に対する暗号文 $c$ は、暗号化の計算処理 $c = m^e$ ( mod $n$ ) により得られることより、暗号文 $c$ の 10 進数表示は，必ずしも　$0\sim 255$ の範囲には収まらない。つまり、暗号文 $c$ の　10　進数表示は、$0$ から　$n-1$ の範囲に収まるとことになる。なぜなら、mod $n$ は、$n$ で割った余りだから。
  
  例えば、暗号化鍵 $(e,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. 「ふりかえりと確認」の説明は、ここで終了。以下、本題のRSA暗号のプログラム作成に戻ります。

RSA暗号のプログラム作成

（この時点で、制約のあるRSA暗号のプログラムを作成できていることと、上記項目の「ふりかえりと確認（バイトデータの取り扱い注意）」を確認しているものとする。）

「作成した制約のあるRSA暗号のプログラムにおいて，メッセージの文字として， 1 バイトのデータを扱えるプログラムに改良し，以下の仕様を満たすRSA暗号のプログラムを作成する」 (このプログラムが、テキストの「課題 1」になります)．

メッセージ集合 $\{0,1,...,255\}$
暗号文集合 $\{0,1,...,n-1\}$

具体的には，メッセージの文字は 256 種類( 1 バイト= 8 ビット)，暗号文の文字は $n$ 種類( $2^{8} = 256 \leq n \leq 2^{15} - 1 = 32767$ ) となるようにする．つまり，暗号文の文字は 2 バイトで表現できるサイズとする．
(
上記の仕様を満たすプログラムの例：実行ファイル rsa.out を実行し、 diffコマンドで foo と hoo の差分を調べ、差分がなく一致することを確認してみよう。さらに、foo, goo, hoo のファイルサイズをを比較してみよう。
実行方法の例：

暗号化「$ ./rsa.out -e 5 323 256byte.dat encoded256byte.dat」
復号化「$ ./rsa.out -d 29 323 encoded256byte.dat decoded256byte.dat」
ファイルの比較「$ diff -s 256byte.dat decoded256byte.dat」
ファイルサイズの比較「$ ls -la | grep 256byte」

)
以下のような動作をするプログラムを作ることが課題１の目的となる。

$ ./rsa.out -e 5 323 256byte.dat encoded256byte.dat          //暗号化
$ ./rsa.out -d 29 323 encoded256byte.dat decoded256byte.dat  //復号化
$ diff -s 256byte.dat decoded256byte.dat    //ファイルの比較
ファイル 256byte.dat と decoded256byte.dat は同一です
$ ls -la | grep 256byte
-rw-r--r-- 1 ka103019 faculty   256 Jul 23  2020 256byte.dat
-rw-r--r-- 1 ka103019 faculty   256 Aug 15 11:32 decoded256byte.dat
-rw-r--r-- 1 ka103019 faculty   512 Aug 15 11:31 encoded256byte.dat
$ cat 256byte.dat 
	


�123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~��������������������������������������������������������������������������������������������������������������������������������$ 
$ cat encoded256byte.dat 
 �7�
    ���z�v0'Y��+��@.�C2��8&���X��yT�V�6/�`*nJ�5
                                               � fg�|c�q��l��/�W2�3S��0����9��?���:(=��r��"�Bj\O�s�5�U"1k�
��?�����{�(�o���a4e���H�9>;)��$�>�!x����	}<6b�!�����:=]���-���4��RK
M[pQ����Zt��^L���.����$ 
$ cat decoded256byte.dat
	


�123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~��������������������������������������������������������������������������������������������������������������������������������$ 
$ od -t u1 256byte.dat 
0000000   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0000020  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
0000040  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
0000060  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
0000100  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
0000120  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
0000140  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
0000160 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
0000200 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
0000220 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
0000240 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
0000260 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
0000300 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
0000320 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
0000340 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
0000360 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
0000400
$ od -t u2 encoded256byte.dat     //暗号化したファイルに対し、「-t u2」として２バイト単位で表示する
0000000     0     1    32   243    55   218    24    11
0000020   145   263   193   197   122   166    29     2
0000040   118   272    18   304    39    89   167   245
0000060    28    43   144   278   282     3    64    46
0000100   223    67   306   137   253    56    38   286
0000120   279   300   264   161   176   163    88   149
0000140   250   121    84   204    86   287   175   310
0000160   303   228    96   298   110    74   180   309
0000200    30    12   206   288   102   103   185   124
0000220    21    99   177   113   247   229   108   129
0000240   207    47   233    87    50   187   307    83
0000260   141   242    48   211   232   196   246    57
0000300   248   241   319   131   104   271    68    69
0000320   168    22   140    65   109   181   230    42
0000340     6   265   190   115   165    53   169    85
0000360   290    49   107   225   269     7   198   128
0000400   314    40    61   139   132   114   172   203
0000420    34   188    66     5   106    31    92    79
0000440    26     8   261    10   173   251    63   189
0000460   152   153   222    15   226   123   252   296
0000500   164   111   212   159    27    71   200    97
0000520   308   101   170   171   134   260    72   150
0000540   313    62   315   297   244   231   292   217
0000560   318   257   135   289   120   151   209   191
0000600   184   262   283     9   195   125   316    54
0000620    98   216   274    33   238   154   270   158
0000640   208   133    58   317   281    93   142   214
0000660   258   183   301   155   254   255    52   219
0000700   192     4    82    75   266    77   127    91
0000720   112   275    81   182   240    16   136   273
0000740   236    90   276   116   194   215    94    76
0000760   210   146   224   302   199   138   220   221
0001000
$ od -t u1 decoded256byte.dat
0000000   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0000020  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
0000040  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
0000060  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
0000100  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
0000120  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
0000140  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
0000160 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
0000200 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
0000220 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
0000240 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
0000260 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
0000300 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
0000320 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
0000340 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
0000360 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
0000400
$

以上

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

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

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