[課題31] 簡易RSA暗号プログラム

課題

この課題で作成するプログラムはごく簡易的なものであって，実用的な暗号として利用するのには適していません(作成するプログラムで「暗号化」しても安全とはいえません)．

プログラムは次のように動作させることを想定しています(ファイル名をtiny_rsa.rbとする)．

 # 平文のplain.txtを暗号化して，暗号データをリダイレクションしてencrypt.txtに送り込む
 $ ruby tiny_rsa.rb -e plain.txt > encrypt.txt

 # 暗号化されたencrypt.txtを平文化して(元に戻して)データを画面に表示する
 $ ruby tiny_rsa.rb -d encrypt.txt

コマンドラインの最初に「-e」か「-d」を入れることで暗号化処理を行うか，平文化処理を行うかを指定するようにします． 暗号化処理，平文化処理のどちらについても，プログラムでは変換した結果のデータは端末画面に出力(表示)することにします．

(以前に授業でも説明したように)端末の画面に表示するデータは上の暗号化の例のようにリダイレクション(> ファイル名)すればファイルに取り込むことができます． なおリダイレクションの処理はプログラムの外部(具体的には端末上で動いている「シェル(shell)」)で実行されます． 作成するプログラムでは，(暗号化・平文化の)結果は常に画面に出力する(表示する)ようにします(表示にはputs，printを使います)． プログラムでは，出力するデータをファイルに保存する処理は行いません． なおリダイレクション先として既存のファイルを指定した場合， ファイルは上書きされます．存在しないファイルを指定した場合，ファイルが作成されます．

プログラムが完成したら，次のファイルを平文化して， そこに書かれている「キーワード」をプログラムの先頭の説明部分(=begin ... =end)に追加して提出してください．

• e_message.txt (秘密のテキスト)

[参考] コマンドラインオプション

上のプログラムの実行例の「-e」「-d」のように， プログラムの動作を指定するコマンドライン引数のことを 「コマンドラインオプション」といいます． (Linux;Unixの文化では)コマンドラインオプションは習慣的に「-e」 あるいは「--encrypt」のように， 「-」(ハイフン)から指定します．

もくじ

1. プログラムテンプレート
2. コンピュータでの情報のデータ表現とRSA暗号への適用
1. コンピュータ内部のデータ表現，ビット，バイト
2. ビット列の解釈 --- 整数と文字列の相互変換
3. ビット列の暗号化処理の概観
3. RSAの処理の基本的な考え方
1. RSAの暗号化/平文化に使う鍵と処理の単位
4. 暗号化/平文化処理の流れ
1. 暗号化/平文化処理の詳細
5. RSA暗号プログラムのための技術情報
6. RSA暗号プログラムの処理過程の例
1. プログラムテスト用ファイル
7. デバグプリント ー プログラムの処理過程の確認
8. [参考] RSA公開鍵暗号の原理

プログラムテンプレート

次に示すプログラムのテンプレート(雛型)を使って下さい． このプログラムは名前を適宜変えた上で保存して利用してください．

• tiny_rsa_template.rb

コンピュータでの情報のデータ表現とRSA暗号への適用

RSA暗号はデータの暗号化と平文化の処理に課題「べき剰余」で作成したmodexpを用います． modexpとは次のように整数を整数に変換するメソッドでした．

  # y == xm % N  
  y = modexp(x,m,N) 

つまりRSA暗号での処理は本質的には整数から整数への変換です．

さて暗号化の対象とするのはファイルで， コンピュータのファイルは文字などさまざまなデータで構成されています． それでは文字データ等にRSA暗号(modexp)がどのようにして適用できるのでしょうか． 以下ではまずコンピュータの内部での文字と数値の表現と，その相互変換について説明します．

コンピュータ内部のデータ表現，ビット，バイト

コンピュータの内部ではあらゆる情報は0と1(と解釈可能な明確に区別できる2つの状態)を並べたデータで表現されています． つまりコンピュータの内部では，数値，文字，画像，音など全ての情報を2種類の記号(0,1)のみで表現しています． なお通常の言語で0,1は数字(数を表すための記号)ですが，コンピュータでは0,1があらゆる情報を表現する一般の文字(記号)として使われることに注意して下さい． このことには違和感があるかもしれません． しかしたとえば英語と日本語では使われる文字の集合(文字の種類)が異なっているように，コンピュータ内部では2種類の文字だけが使われているわけです．

実際，0,1という2種類の記号(文字)の並べ方にルールを決めておくことで， 数値，文字などを表現することができます． 具体的にはたとえば整数は2進法に基づいて表現されます． 文字については，まず各文字に番号をつけます． 番号がつけられれば，それらの番号に基づいて文字をデータとして表現できます．

1個の0,1を表すデータの単位をビット(bit)といいます． また(通常)8ビットをまとめて1バイト(byte)といいます(1バイトが8ビットでないこともあります．8ビットは正確には1オクテットといいます)． これらの用語を使えば，コンピュータの内部で情報はビット列，バイト列で表現されていると言えます．

1バイト(8ビット)のデータは2⁸=256通り存在します． それらを2進法で解釈すれば非負整数として0から255に対応させられます．

Rubyでは，数値や文字のデータがビット列で表されていることを簡単な処理で見てみることができます．

  # 整数aを2進表現したビット列(に対応する文字列)bに変換する
  a = 1234
  b = a.to_s(2) # b == "10011010010"

  # sの最初の文字('a')の番号を2進表現したビット列(に対応する文字列)に変換する
  s = "abc"
  x = (s.bytes)[0] # x == 97
  b = x.to_s(2)    # b == "1100001"

  # ビット列を表す文字列uを2進表現の整数として解釈する
  u = "10011101"
  y = u.to_i(2)  # y == 157

ビット列の解釈 --- 整数と文字列等の相互変換

さてビット列はそれ自体だけでは何の情報を表しているデータであるとは言えません． たとえば同一のビット列を数値として解釈することもできれば，文字(の番号)と解釈することもできます． このことはコンピュータでは数値データを文字データとして扱ったり，文字データを数値データとして扱ったりできることを意味しています．

  str = "Ruby"

  # ary == strの各文字の番号(バイト値)の配列
  ary = str.bytes 
  p ary # ==> [82, 117, 98, 121]

  # rby == sを""で初期化して，aryの要素(バイト値)xをそれぞれ文字番号として文字に変換(x.chr)してからsに順に連結した結果の文字列
  rby = ary.reduce("") { |s,x| s+x.chr }　
  p rby # ==> "Ruby"

  # "Ruby" <==> [82, 117, 98, 121]

  # 整数の列を一つの整数として解釈することもできる．
  # 82, 117, 98, 121 
  # → 01010010, 01110101, 01100010, 01111001  # 2進で表現(各8ビット)
  # → 01010010011101010110001001111001        # すべてを連結
  # → 1383424633                              # 32ビットで一つの整数として解釈
  
  # "Ruby" <==> [82, 117, 98, 121] <==> 1383424633

この例で見た通り，文字列(を表すビット列)を整数(を表すビット列)と解釈し直すことができます． また逆に整数(を表すビット列)を文字列(を表すビット列)に解釈し直すこともできます．

ビット列の暗号化処理の概観

上で見たように，コンピュータのデータとして文字列と整数は相互変換が可能です． さらに文字に限らずコンピュータのデータはすべてビット列ですので， コンピュータ内のどんなデータも整数として解釈することが可能です． そこでコンピュータのデータを整数として解釈することで， そのようなデータをRSA暗号の処理(modexp)の対象として扱えるであろうことが分かるでしょう． またmodexpで変換した後の整数を，再びビット列として扱うことも可能であることが分かるでしょう．

  平文のビット列b …→ 整数x ⇒(modexpで変換)⇒ 整数y …→ 暗号文のビット列s

RSAによるファイルの暗号化処理の基本的な考え方

どんなファイルでも暗号化する対象になりえます． さて暗号化処理とは暗号化するビット列を整数とみなしてmodexpによって変換する処理でした． modexpではN，整数x(0≦x＜Nを想定)，mを入力として，x^mを整数Nで割った余りを計算します．

  y = modexp(x,m,N) # y == xm % N

つまり一回の処理で扱うのはN未満の整数です． 任意のファイルについて，そのビット列全体を1つの整数と解釈することは数学的には可能です． しかし実際には一つのファイル全体に対応する整数が常にN未満であるようにしようとすれば， Nをとてつもなく巨大な数にしなければなりません． これは全く現実的ではありません．

そこでファイルを分割して，それぞれを変換することにします． Nを適宜定めて， ファイルを分割したバイト列をそれぞれ整数として解釈したときに， どれもN未満になるようにするわけです． また分割に都合のよいNを選ぶようにします．

RSAの暗号化/平文化に使う鍵と処理の単位

以上を踏まえて今回のプログラムではRSAで用いる鍵として次の値を用いることにします(テンプレートで定義済み)．

module Key
  P = 57037
  Q = 38011
  E = 1864990913
  D = 1649420777
  N = P*Q # N=2168033407
end

暗号化する処理では「Key::E」と「Key::N」を，平文化処理(元に戻す処理)では「Key::D」と「Key::N」をmodexpメソッドのパラメタとして用います．

  y = modexp(x, Key::E, Key::N) # 暗号化: x → y
  z = modexp(y, Key::D, Key::N) # 平文化: y → z(==x)

これらの鍵は一度に4バイトのデータを暗号化/平文化することを想定して設定しています． つまり今回は，modexpの第1引数(上の例ではx,y)には4バイトのデータを整数に変換して与えることにします． このときmodexpの結果として得られる値(上の例では左辺のy,z)は4バイトのデータに変換できるようになっています．

なお鍵{E,D,N(=PQ)}の決め方の詳細について「RSA公開鍵暗号の原理」に説明しています(課題のプログラムを実現するために参照する必要はありません)．

暗号化/平文化処理の流れ

すでに説明した通り，今回は一度に4バイトずつを基本単位として暗号化/平文化します． しかしファイルを簡単に処理するために，平文ファイルをそのまま4バイトずつ最初から最後まで処理するのではなく，次のような方針で処理することにします．

1. 暗号化処理
   • 平文ファイルをUNITバイトずつに分割して順に処理する
   • 平文UNITバイトのデータを暗号化する→暗号化済のテキスト1行を生成する
   • 暗号化済のテキストを画面(STDOUT)に逐次出力する


2. 平文化処理
• 暗号化済のファイルを1行ずつ順に処理する
• 暗号化済のテキスト1行を平文化する→UNITバイトのデータが得られる
• 平文化されたUNITバイトのデータを画面(STDOUT)に逐次出力する

暗号化処理では，平文ファイルからUNITバイトずつを読み込んで，それを(4バイトずつに分割してそれぞれ順に)暗号化して暗号化済のテキストを1行生成して出力する処理を繰り返すことになります． 平文化処理は暗号化の逆の処理になっています．

上の方針で処理したとき，平文ファイルと暗号化済みのファイルとの間に次のような対応関係があることになります．

  暗号化: 平文UNITバイト → 暗号化済みテキスト1行
  平文化: 暗号化済みテキスト1行 → 平文UNITバイト 

暗号化処理では「平文UNITバイト」が「暗号化済みテキスト1行」に変換され， 平文化処理では「暗号化済みテキスト1行」が「平文UNITバイト」に変換されます． これらの変換処理が今回の課題で実現する重要なポイントになります． 詳細については以下で説明します． またUNITの値をどう設定するのかについても以下で説明します．

ところで平文ファイルのサイズはUNITバイトの倍長であるとは限りません(UNIT > 1のとき)． そこでUNITバイトずつ処理していくと，最後に(1以上)UNITバイト未満のデータをファイルから読み込むことになりえますが，そのことをとくに気にする必要はありません． その場合も他と区別することなく処理できます． つまりファイルの長さがUNITの倍長でなくても，ファイルの末尾のデータを例外として特別に処理する必要はありません(以下の「ファイルの読み書き」を参照のこと)．

暗号化/平文化処理の詳細

上で説明したように，今回の課題では，平文ファイルと暗号化済みのファイルとの間で，次のような対応関係が作られることになります．

  平文UNITバイト ⇔ 暗号化済みテキスト1行

以下では「平文UNITバイト」の暗号化処理と「暗号化テキスト1行」の平文化処理について説明します．

平文UNITバイトの暗号化処理

「平文のUNITバイト」から「暗号化済みテキストの1行」を生成する過程を具体的に書くと次の通りになります．

  [平文UNITバイト]→(EnArmor変換)→(バイト列化)→(暗号化)→(文字列化)→(EnArmor変換)→[暗号済テキスト1行]

1. 入力: 平文ファイルからUNITバイトの文字列を読み込む．


2. EnArmor変換: 文字列を「EnArmor変換」する→4の倍数の長さの文字列が得られる(EnArmor変換については後述)．


3. バイト列化: EnArmor変換された文字列をバイト列(各文字の番号(0-255)の配列)に変換する(配列の要素数は4の倍数になっている)


4. 暗号化: バイト列を(暗号化済の)バイト列に変換する
   1. 4バイトのバイト列(0-255の配列)を整数1個に変換
   2. 得られた整数をmodexpで暗号化(鍵=Key::E，Key::N)
   3. 暗号化された整数を4バイトのバイト列(0-255の配列)に変換
   このようにして4バイト→4バイトの変換を繰り返すことで，平文から作られたバイト列を暗号化されたバイト列に変換する． このとき暗号化の前後でバイト列の長さ(配列の要素数)は変わらない．


5. 文字列化: 暗号化済みバイト列の各要素を文字に変換して文字列を生成する


6. EnArmor変換: 前のステップで得られた文字列を「EnArmor変換」する


7. 出力: 前のステップで得られた文字列をputsメソッドで端末の画面に出力する

暗号化済みテキスト1行の平文化処理

さて暗号化されたテキストを平文化する処理は要するに暗号化処理の逆変換です． 平文化処理においては次の処理を暗号ファイルの先頭から最後まで繰り返し適用します． 平文化処理されたデータは端末画面に書き出すものとします．

  [暗号済テキスト1行(※)]→(DeArmor変換)→(バイト列化)→(平文化)→(文字列化)→(DeArmor変換)→[平文UNITバイト]

  (※) 末尾の改行文字は削除する

1. 入力: 暗号ファイルから文字列を1行読む．行末の「改行文字」は削除する．


2. DeArmor変換: 文字列を「DeArmor変換」する→4の倍数の長さの文字列が得られる(DeArmor変換については後述)．


3. バイト列化: DeArmor変換された文字列をバイト列に変換する(配列の要素数は4の倍数になっている)


4. 平文化: バイト列を(復号済の)バイト列に変換する
   1. 4バイトのバイト列(0-255の配列)を整数1個に変換
   2. 得られた整数をmodexpで平文化(鍵=Key::D，Key::N)
   3. 平文化された整数1個を4バイトのバイト列(0-255の配列)に変換
   このようにして4バイト→4バイトの変換を繰り返すことで，暗号データから作られたバイト列を復号されたバイト列に変換する． このとき平文化の前後でバイト列の長さ(配列の要素数)は変わらない．


5. 文字列化: 復号済みバイト列の各要素を文字に変換して文字列を生成する


6. DeArmor変換: 前のステップで得られた文字列を「DeArmor変換」する


7. 出力: 前のステップで得られた文字列をprintメソッドで端末の画面に出力する．

UNITの設定

UNITは定数として定義済です(テンプレートの「require 'trsa/utils'」で定義を取り込んでいます)． プログラムでUNITの定数を参照するには次のように記述して下さい．

  # 「UNIT」の値を使うときは次のように記述する
  TRSAUtils::UNIT

なおUNITの値には制限があります．課題の設定に合わせて処理を行うためにUNITは9の倍数にしてあります． 平文UNITバイトに対して暗号化済テキストの長さは「16・UNIT/9」バイトとなります(末尾の改行を除く)．

[参考] 暗号化処理と平文化処理の類似性

上に示した暗号化処理と平文化処理が同じように構成されていることが分かるでしょう． 実際に各ステップでの処理を抽象化すれば暗号化と平文化は同一の処理とみなせます．

  暗号化: [平文UNITバイト]──→(EnArmor変換)→(バイト列化)→(暗号化)→(文字列化)→(EnArmor変換)→[暗号済テキスト1行]
  平文化: [暗号済テキスト１行]→(DeArmor変換)→(バイト列化)→(平文化)→(文字列化)→(DeArmor変換)→[平文UNITバイト]

  (※) 平文化で「暗号化済テキスト1行」の末尾の改行文字は削除する

暗号化と平文化の差異を見てみます．

• 処理の対象
  • 暗号化：平文UNITバイト
  • 平文化：暗号化済のテキスト1行(ただし末尾の改行文字を除く)


• 文字列の変換処理
  
  • 暗号化：EnArmor変換
  • 平文化：DeArmor変換


• べき剰余(modexp)に与える鍵
  
  • 暗号化：Key::E，Key::N
  • 平文化：Key::D，Key::N


• データの出力方法
  
  • 暗号化：putsメソッド
  • 平文化：printメソッド
  putsで出力すると最後に改行されます(それによって出力データが行単位で並ぶことになります)． 平文化処理では「print」で文字列のみを出力します．改行は付加しません． 平文化処理して得られるのは「暗号化処理の単位としたUNITバイト(以下)のデータ」です． 平文化処理で改行を付加してしまうと， UNITバイトごとに余計な改行が入って元の平文データを変更することになってしまいます．

このような類似性は，暗号化処理と平文化処理に用いるメソッドをうまく抽象化すれば，それらを同一のメソッドとして記述できることを意味します． つまり暗号化処理と平文化処理は異なるパラメタによる同一のメソッドで表現できます．

【補足】暗号化・平文化処理を抽象化して同一の処理として記述することは課題として は必須ではありません．

RSA暗号プログラムのための技術情報

以下に今回のプログラムの作成に関係する技術情報を示します． 全てを必ず使わなければならないわけではありません．

• EnArmor変換とDeArmor変換
• 文字列のバイト列への変換
• バイト列の文字列への変換
• 整数から0,1文字列への変換
• 0,1文字列から整数への変換
• 整数(0-255)→文字
• 配列の要素の集約(reduce)
• ファイルの読み書き
• 文字列末尾の改行文字の削除
• 繰り返し処理
• 文字列の分割，連結など
• 配列の各要素を変換した配列の生成(map)
• 部分文字列
• 商と余り(divmod)
• 条件演算子，条件修飾子
• 16進記法，ビット演算子(&，>>，<<)
• メソッドの実行(send)

• EnArmor変換とDeArmor変換
  

  
    str = "Ruby\n"
  
    estr = TRSAUtils.enarmor(str)  # estr == "UnVieQo="
  
    dstr = TRSAUtils.dearmor(estr) # dstr == str == "Ruby\n"
  
  

  EnArmor変換すると，任意の文字列が英数字などの表示可能な文字の列(具体的には英数字，「+」，「/」，「=」で構成される文字列)に変換される． たとえば上の例でstrの末尾の改行文字は表示される文字ではないが， 変換後にはそのような文字は含まれていない． EnArmor変換後は必ず4の倍数のバイト数の文字列が得られる． DeArmor変換はEnArmor変換の逆変換である． DeArmor変換する文字列に EnArmor変換の結果に含まれるはずがない文字が入っているとエラーが発生する．
[技術情報のトップへ]


• 文字列のバイト列への変換
  

  
    str = 'Ruby'
  
    # 文字列strをバイト列baryに変換する(バイト列＝0〜255の配列)
    bary = str.bytes # bary == [82, 117, 98, 121]
  
  

[技術情報のトップへ]


• バイト列の文字列への変換
  

  
    bary = [82,117,98,121]
  
    # バイト列baryを文字列strに変換する(バイト列＝0〜255の配列)
    str = bary.reduce('') { |s,x| s+x.chr } # str == "Ruby"
  
  

[技術情報のトップへ]


• 整数から0,1文字列への変換
  

  
    k = 108
  
    # 整数kを8桁の2進表現の文字列に変換する．  
    # 必要なら先頭に0を付す．  
    s = sprintf('%08b',k) # s == "01101100"  
  
  

[技術情報のトップへ]


• 0,1文字列から整数への変換
  

  
    s = '01101100'
  
    # 0,1文字列を整数の2進表現として解釈する
    k = s.to_i(2) # k == 108
  
  

[技術情報のトップへ]


• 整数(0-255)→文字
  

  
    a = [65,66,67]
    a[0].chr # ==> "A"
    a[1].chr # ==> "B"
    a[2].chr # ==> "C"
  
  

[技術情報のトップへ]


• 配列の要素の集約(reduce)
  reduceは配列の要素をブロックで指定された方法で集約してまとめた値を計算するメソッドである． reduceの引数は，集約を始めるときの初期値に使われる．

  
    ary = [1,2,3,4]
  
    a = ary.reduce(0) { |r,x| r + x } # a == 10 (== 0+1+2+3+4)
    b = ary.reduce(1) { |r,x| r * x } # b == 24 (== 1*1*2*3*4)
  
    num = [97,98,99]
    c = num.reduce("") { |s,x| s + x.chr } # c == "abc" (== "" + 97.chr + 98.chr + 99.chr)
  
    uby = ["u","b","y"]
    d = uby.reduce("R") { |s,x| s + x }    # d == "Ruby" (== "R" + "u" + "b" + "y")
  
  

[技術情報のトップへ]


• ファイルの読み書き
  

  
    # finは読込み用にopenされているストリームとする
    # finから文字列をnバイト読み取る．
    # 残りがnバイトに満たない場合は読み込めた分だけの長さの文字列が得られる．
    # ファイルの最後まで読み終えていた場合にはnil(つまり偽)が得られる．
    buff = fin.read(n)
  
    # finからbuffに1行読み取る(末尾に改行文字が入る)．
    buff = fin.gets
  
    # buffを画面に書き出す．最後に改行をつける．
    puts(buff)
  
    # buffを画面に書き出す．改行は付加しない．
    print(buff)
  
  

  readメソッドでは指定された長さ(n)の文字列を読み取ろうとしたとき， 残りのデータがnバイト未満であっても最後まで読み取って， 読み取った分だけの文字列を生成して返します．
  今回のプログラムでは，ファイルの最後の部分がUNITバイトに満たない可能性もありますが， それを気にしないで，まったく同様に処理して構いません．
  またすでにファイルの最後まで読み終えていたときにreadするとnilが得られます． これによってファイルの読込み終了を判定できます．
[技術情報のトップへ]


• 文字列末尾の改行文字の削除
  

  
   # buffの末尾に改行があれば，それを削除した文字列を生成してbuff1とする．
   # そうでなければ，buffそのものをコピーした文字列を生成してbuff1とする．
   # いずれにしてもbuffは変更されない．
   buff = "This is a test\n"
   buff1 = buff.chomp # ==> buff1 = "This is a test"
  
   # buffの末尾に改行があれば削除する(なければ何もしない)．
   # buff自身を書き換える．
   buff.chomp! # ==> buff = "This is a test"
  
  

[技術情報のトップへ]


• 繰り返し処理
  

  
   # aからbの範囲について，sずつ値を増やしながら繰り返す(bを越えたら終了)
   a.step(b,s) do |i| # i = a, a+s, a+2s, ...
  
   end
  
  

[技術情報のトップへ]


• 文字列の分割，連結など
  

  
    # 文字列の分割(split)
    # 文字列を「区切り文字」で分割して配列にする．
    # 区切り文字を空文字列にすれば1文字ずつ分割する．
  
    b = "01101011"
    s = b.split("") # ==> s == ["0","1","1","0","1","0","1","1"]
  
    # 配列の要素の文字列としての連結(join)
    # 配列の要素を「区切り文字」を挟んで文字列として連結する．
    # 「区切り文字」を指定しなければ，要素をそのまま連結する．
  
    c = s.join      # ==> c == "01101011"  
    d = s.join("+") # ==> d == "0+1+1+0+1+0+1+1"
    d = s.join(" ") # ==> d == "0 1 1 0 1 0 1 1"
  
    # 文字列同士の連結(+)
    s  = "A "
    s0 = "Programming"
    s1 = "Language"
    s = s + s0 + " " + s1 # ==> s == "A Programming Language"
  
    # 文字列の長さ(size)
    buff = "This is a test\n"
    n =  buff.size # ==> n == 15 (改行文字もカウントされる)
  
  

[技術情報のトップへ]


• 配列の各要素を変換した配列の生成(map)
  

  
    # 配列の各要素にブロックで指定した処理を施して，その結果を配列にする
    s = ["0","1","1","0","1","0","1","1"]
    v = s.map { |x| x.to_i } # ==> v == [0,1,1,0,1,0,1,1]
  
  

  [技術情報のトップへ]
  
  
• 部分文字列
  

  
    s = "abcdefg"
  
    # s[i,n] i番目の文字(i=0,1,...)からn文字
    s[0,2]  # ==> "ab"
    s[1,3]  # ==> "bcd"
    s[3,4]  # ==> "defg"
  
    # s[i..j] i番目の文字(i=0,1,...)からj番目の文字(j=0,1,...)まで
    s[0..2] # ==> "abc"
    s[2..5] # ==> "cdef"
  
  

[技術情報のトップへ]


• 商と余り(divmod)
  

  
    
    x = 258
  
    # q,r = x.divmod(a) q→商, r→余り
    q,r = x.divmod(256) # q==1, r==2
  
  

[技術情報のトップへ]


• 条件演算子，条件修飾子
  

  
    # (条件式) ? (式1) : (式2)
    # 条件が真なら「式1」偽なら「式2」を評価した結果が値となる．
    a = (b == 0) ? 1 : -1
  
    # 式 if 条件式
    # 条件が真なら「式」を評価する
    a = 1 if b == 0
  
    # 式 unless 条件式
    # 条件が偽なら「式」を評価する
    a = 1 unless b == 0
  
  

[技術情報のトップへ]


• 16進記法，ビット演算子(&，>>，<<)
  

  
    # 16進記法の整数データ
    # Rubyでは「0x」から始まる[0-9a-f]の列は16進記法の整数として扱われる
    # a=10,b=11,c=12,d=13,e=14,f=15を数字として使う
    # (参考:2進記法での4bitが16進記法での1桁に相当する)
  
    0x0a  # ==> 10
    0x2e  # ==> 2×16+14 = 46
    0xff  # ==> 15×16+15 = 255
    0x705 # ==> 7×162+0×16+5 = 1797
  
    # ビット演算子
    # x & y: 整数x,yのbitごとのAND(0&0 == 0, 0&1 == 0, 1&0 == 0, 1&1 == 1)
    # x>>n: 右シフト 整数xのビット列の各ビットを右にnビットずらす．上位ビットは0になる．下位ビットは消える．
    # x<<n: 左シフト 整数xのビット列の各ビットを左にnビットずらす．下位ビットは0になる．
  
    # サンプルデータ
    s = "01001100" # 整数に変換すれば「0x4c = 4×16+12 = 76」と解釈できる
  
    x = s.to_i(2) # x == 0x4c == 76;; 0,1の文字列.to_i(2)で0,1文字列を整数の2進表現として解釈
  
    # xの上位4ビットと下位4ビットの値をy,zとして取り出す
    y = x & 0x0f # 01001100 & 00001111 = 00001100 = 0x0c = 12
    z = (x & 0xf0)>>4 # (01001100 & 11110000)>>4 = (01000000)>>4 = 00000100 = 0x04 = 4
  
    # y,zからxの値を復元する(wに代入している)
    w = (z<<4) + y # (00000100)<<4 + 00001100 = 01000000 + 00001100 = 01001100 = x
  
  

[技術情報のトップへ]


• メソッドの実行(send)
  

  
    # send
    # 引数にメソッド名と，そのメソッドへの引数を並べて指定して，
    # 指定したメソッドを実行できる．
    # メソッド名は文字列かSymbolで指定する．
    
  
    ary = [0,1,2]
  
    # ary.push(3)と同じ
    ary.send(:push,3) # ==> ary == [0,1,2,3]
  
    # ary.insert(1,-1,-2,-3)と同じ
    # (insert = 対象の配列において第1引数で指定した位置から第2引数以降のデータを入れ込む)
    ary.send(:insert,1,-1,-2,-3) # ==> ary == [0,-1,-2,-3,1,2,3]
  
    str = ["0","1","1","0","1","0","1","1"]
    method = :join
  
    # str.joinと同じ
    str.send(method) # ==> "01101011" 
  
    # Math.cos(Math::PI)と同じ
    y = Math.send(:cos,Math::PI) # ==> y == -1.0
  
    # inc,decメソッドの定義(sendのテスト用) 
    def inc(x)
      x+1
    end
    
    def dec(x)
      x-1
    end
  
    c = 2
    a = send(:inc,c) # a == 3
    b = send(:dec,c) # b == 1
    
  

[技術情報のトップへ]

RSA暗号プログラムの処理過程の例

次にごく短いテキストデータを例として，RSAの暗号化処理をしたときに処理の過程でどのようなデータが得られるかを示します． 平文化する場合には，逆の順序でデータが変換されていくはずです． プログラムを作成するときの参考にしてください．

  # 平文として次のデータを読み込んだとする(5バイト)．
  # 「Ruby」の4文字と最後に改行が入ったファイルとみなせる．
  "Ruby\n"

  # "Ruby\n"をEnArmor変換した後の状態(8バイト)
  "UnVieQo="

  # "UnVieQo="をバイト列に変換した配列
  [85, 110, 86, 105, 101, 81, 111, 61]

  # バイト列を4バイトごとに区切って，それぞれを整数に変換したとすると次のようになる．
  1433294441 # [85, 110, 86, 105]を変換した結果
  1699835709 # [101, 81, 111, 61]を変換した結果

  # これらをmodexpで変換すると次のようになる．
  1361091994 #   modexp(1433294441,Key::E,Key::N) つまり「14332944411864990913 % 2168033407」
  2108684386 #   modexp(1699835709,Key::E,Key::N) つまり「16998357091864990913 % 2168033407」

  # modexpで変換した数値を並べてバイト列に変換した結果
  [81, 32, 157, 154, 125, 175, 248, 98]  # 前半4つが1361091994を変換した結果，後半4つが2108684386を変換した結果

  # 上のバイト列を文字列に変換した結果
  # この段階では文字としてそのまま表示できないデータが含まれている．
  # 当該のデータを「pメソッド」で表示するとバイト値がそのまま現れる．
  # バイト値は16進記法で表示される．
  #
  # (例) 「\x9D」＝バイト値が16進記法で「9d」であることを意味している(10進で157)．
  "Q \x9D\x9A}\xAF\xF8b" # [81, 32, 157, 154, 125, 175, 248, 98]を文字列に変換した後でpメソッドで表示したとする
  
  # 上の文字列をEnArmor変換した結果＝putsで出力すべき「暗号化済みテキスト」
  "USCdmn2v+GI=" # "Q \x9D\x9A}\xAF\xF8b")をEnArmor変換した結果(=平文"Ruby\n"を変換した暗号化済みテキスト)

プログラムテスト用ファイル

プログラムの動作テストに利用できるファイルを提供します．

• plain_test.txt (平文ファイル)
• encrypted_test.txt (plain_test.txtを暗号化したファイル)
• hello_plain.txt (平文ファイル その2)
• hello_encrypted.txt (hello_plain.txtを暗号化したファイル)
• onetwo_plain.txt (平文ファイル その3)
• onetwo_encrypted.txt (onetwo_plain.txtを暗号化したファイル)
• japan_constitute_preface.txt (平文ファイル その4; 日本国憲法前文)
• japan_constitute_preface_encrypted.txt (japan_constitute_preface.txtを暗号化したファイル)

いずれも平文から暗号化すること，逆に暗号文から平文化することができるはずです．

テスト方法

「plain_test.txt」と「encrypted_test.txt」について具体的にテストの方法を示します(ファイル名をtiny_rsa.rbとする)．

 # plain_test.txtを暗号化したデータをe.txtにリダイレクションして送り込む
 $ ruby tiny_rsa.rb -e plain_test.txt > e.txt

 # e.txtとencrypted_test.txtをcmpコマンドで比較する
 # →結果として何も表示されなければ，2つのファイルが同一であることが分かる
 $ cmp e.txt encrypted_test.txt 

 # encrypted_test.txtを平文化したデータをp.txtにリダイレクションして送り込む
 $ ruby tiny_rsa.rb -d encrypted_test.txt > p.txt

 # p.txtとplain_test.txtをcmpコマンドで比較する
 # →結果として何も表示されなければ，2つのファイルが同一であることが分かる
 $ cmp p.txt plain_test.txt 

 # p.txtは平文で読めるはずなので，catコマンドで表示して確認してみてもよい
 $ cat p.txt

「hello_plain.txt」と「hello_encrypted.txt」については以下のようにテストできます．

 # hello_plain.txtのデータを表示してみる
 $ cat hello_plain.txt

 # hello_plain.txtを暗号化したデータをe.txtにリダイレクションして送り込む
 $ ruby tiny_rsa.rb -e hello_plain.txt > e.txt

 # e.txtとhello_encrypted.txtをcmpコマンドで比較する
 # →結果として何も表示されなければ，2つのファイルが同一であることが分かる
 $ cmp e.txt hello_encrypted.txt 

 # hello_encrypted.txtを平文化したデータをp.txtにリダイレクションして送り込む
 $ ruby tiny_rsa.rb -d hello_encrypted.txt > p.txt

 # p.txtとhello_plain.txtをcmpコマンドで比較する
 # →結果として何も表示されなければ，2つのファイルが同一であることが分かる
 $ cmp p.txt hello_plain.txt 

 # p.txtは平文で読めるはずなので，catコマンドで表示して確認してみてもよい
 $ cat p.txt

「onetwo_plain.txt」と「onetwo_encrypted.txt」についても全く同様にテストできます．

デバグプリント ー プログラムの処理過程の確認

プログラム作成中には，さまざまな問題が生じることがよくあります． 問題が発生したときには，プログラムを眺めるだけではなく，実行中にさまざまなタイミングで変数がどんな値になっているかを確認することが原因を発見するヒントになります．

プログラムの問題(バグ)を解消することをデバグ， デバグのために変数の値を適宜表示することを「デバグプリント」といいます． Rubyでのデバグプリントには「pメソッド」を利用するのが簡便です．

  File.open(fname) do |fin|

    buff = fin.read(TRSAUtils::UNIT) # この処理の意味については「技術情報」を参照のこと

    # 配列としてデータを表す適当な名前(Symbol)とともに表示させると，表示される情報を把握するのに便利です
    # (buffは変数．変数の値が表示される．:readはSymbolでこのまま表示される)．
    p [:read,buff]

    a_buff = TRSAUtils.enarmor(buff) # この処理の意味については「技術情報」を参照のこと

    p [:enarmored,a_buff,:size,a_buff.size]

  end

なおプログラムが完成したらこのような表示処理は却って邪魔になりますので， 削除する，コメントアウトする(コメントにする)などします．

[参考] RSA公開鍵暗号の原理

インターネットで一般的に用いられているRSA暗号は，(適切に選ばれた)大きな素数の積については「素因数分解」が本質的に難しいであろうことを根拠として，「暗号化」する鍵を一般公開しても安全にデータをやりとりできる「公開鍵暗号」の一種です．

「公開鍵暗号」が発明される前の暗号(共通鍵暗号)では，暗号化のための鍵と復号(元に戻す)のための鍵が同一です． したがって，暗号化の鍵を公開してしまうと，第三者に暗号文を解読されることになります． 一般にインターネットでの通信は傍受される危険性があるため，鍵をネット上で安全にやりとりすることはできません． そのため共通鍵暗号は(単独では)インターネットで安全に使うことが困難です(※公開鍵暗号の技術と共通鍵暗号を組み合わせて使うのが一般的です)．

しかしRSA暗号では暗号化のための鍵は公開しても構いません． これは復号するときに暗号化の鍵(公開鍵)とは別の秘密鍵を用いるためです． 公開鍵と秘密鍵はペアで定義されます． このようにペアになる2つの鍵を使う暗号システムを一般に公開鍵暗号と呼びます．

さてRSA暗号では次のようなべき剰余計算を利用します．

  y = xE % N  # x --> y
  z = yD % N  # y --> z == x

「x」を守るべき秘密のデータとして，「y = x^E % N」という計算によって，「EとN」という「鍵」で秘密のデータ「x」を「y」に暗号化したものと考えることができます． またE,D,Nを適切に設定したとき「z = y^D % N」のように計算するとzがxと一致します． この計算により「DとN」という「鍵」で暗号データ「y」を復号して，元の秘密データ「x」を復元したものとみなせます．

実際にこの仕組みを使うには，まずデータ受信者が(E,D,N)を適切に決めて，送信者に(E,N)を渡します． (E,N)は第三者も知りうる公開鍵となります． 送信者は秘密のデータ「x」を公開鍵(E,N)で暗号化した結果の「y」を暗号データとして受信者に送ります． 秘密の「D」を知っている受信者は，暗号データ「y」から「z = y^D% N」と計算することで簡単に秘密データ「x」(== z)を得ることができます． しかしたとえ第三者が公開鍵(E,N)を知ったとしても， (E,D,N)を適切に決めた場合， (E,N)の情報のみでは復号の鍵「D」を計算することは極めて困難であると考えられています． このとき暗号データ「y」と公開鍵(E,N)を知られても，秘密鍵「D」を秘匿することで秘密データ「x」が守られることになります．

P,Qを相異なる素数として，E，D，Nを次の性質を満たすように定めれば， それらを「鍵」として使えることが知られています． これがRSA暗号の原理です．

   N = P・Q  (P≠Q) P,Qは素数
   E s.t. gcd(E,φ(N)) == 1 # gcdは最大公約数(つまりEとφ(N)は互いに素)
   D s.t. (E・D) % φ(N) == 1 
   φ(N)=(P-1)(Q-1)

十分大きなP,Qを適切に選ぶことで，(E,N)を公開しても，(D,P,Q)を秘密にしておけば，暗号文yからもとの秘密のデータxを得ることは極めて難しいと信じられています(すでに見ている通りP,Qは計算には使いません)． 一方秘密のDを知っていれば，今回のプログラムで実現したように元の秘密データを計算するのはごく簡単です．

公開されているNを素因数分解してP,Qを得ればRSA暗号を解読することができるのですが， 十分に大きな素数P,Qを適切に選んだ場合(大きなP,Qであれば何でもよいというわけではありません)，たとえN=P・Qであると分かっていても，現実的な時間でNをPとQに素因数分解する方法は知られていません． 原理的には素数Pの候補を2,3,5,7,...,と順に試していけば，いつかはNを割り切るPが見つかるはずなのですが，P,Qが大きい場合，この素朴な手法では絶望的に長い時間が必要となります． たとえば次のNを素因数分解することができるでしょうか．

 N = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

じつはこのNはすでに次のように素因数分解されている「とても小さな」数です(129桁)．

 N = P・Q
 P = 3490529510847650949147849619903898133417764638493387843990820577
 Q = 32769132993266709549961988190834461413177642967992942539798288533
 

現在使われている暗号では，Nとして600桁程度(2048bit)の数を使います．

なお素因数分解の効率的な方法は見つかっていませんが， 素因数分解が本当に難しいかどうかは証明されていません． また素因数分解以外の方法ではRSA暗号を解読できないかということも分かっていません．