わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

かけ算の記号は,何でもいい?

 いきなりですが問題です.以下の文章の【 1 】~【 5 】に当てはまる語句を答えなさい.

RSA暗号アルゴリズムにおいて,鍵は,事前に計算された3つの非負整数NEDで表される.暗号化と復号の関係は,任意の平文Mに対して【 1 】という式になる.Nは2つの素数の【 2 】であり,Eとともに公開鍵を構成する.Dは公開されない値であるが,Nを【 3 】できるならば,効率良く計算できてしまう.2つの素数pqを用いて,N=p\star qと表せるとき,pqの一方の値が過度に小さいと,【 4 】で特定できる可能性がある.p素数として生成したのち,【 5 】といった求め方では,別の方法でpqの値が特定できてしまう.これらは,RSA暗号アルゴリズムそのものの脆弱性というよりは,鍵生成の不適切さに起因する不具合である.

 さっそくですが解答例です.

  • 【 1 】(M^E \% N)^D \% N = M
  • 【 2 】積
  • 【 3 】素因数分解
  • 【 4 】ブルート・フォース・アタック
  • 【 5 】pの次に大きな素数qとする

 昨日実施した試験問題の抜粋です(解答番号は変更しています).「むかし,この科目の試験を受けたなあ」と懐かしがる人向けに,補足をしておくと,【 5 】を含む文は,RSAに対するフェルマー攻撃 - Qiitaとそこからのリンクによれば,今年報告された攻撃だそうです.また【 4 】も過去に出題したことはなく,ここは「Nを3, 5, 7, ...の順に割って割り切れるか調べること」と書いても正解です.
 【 1 】の正解に入れた「%」は剰余演算子です.科目を担当するようになった初年度から,スライドの文字数を減らすために,C言語由来のこの記号を使用しています.試験問題では,「剰余演算子を書く場合,授業で使用した「%」でも,書籍に見られる「mod」でもよい.」という断り書きを入れています.ということで(M^E \bmod N)^D \bmod N = Mも正解となります*1
 今回の問題で,少し手間をかけたのは,文中のN=p\star qの式です.多くのセキュリティの書籍では,N=pqと表記されます.
 RSA暗号アルゴリズムを詳しく説明するとなると,整数*2を対象とした演算,具体的には加減乗除と剰余から始めることになります.そこで授業資料ではx+yx-yx\star yx/y,そしてx\% yと表記していまして,これに基づき,N=pqと書きたいところでもN=p\star qとしていました.乗算記号は,PowerPointのスライドではArialのフォントを使用して「*」を書いているために,\starの字形になっています.
 試験の前日に,刷り上がった試験問題を見ながら,誤記がないか,どのような別解があるかと,チェックをしていく中で,剰余演算子と別に,乗算の表記について,案内をしておくとよいと考えました.
 Moodleで公開済みの,試験の前々日の授業*3の資料に,スライドを追加して,次のように記載しました.

  • 乗算記号の表記に関して,試験の答案では
    • 乗算記号は「\star」「*」「×」「・」のいずれでもよい.
    • 文字式について,例えば「37*x」に替えて「37x」でもよい.

 「文字式について」を入れているのは,102を法とした37の逆数が91であることの確かめを答案に書く際には,「37\star 91」「37*92」「37×92」「37・92」のいずれでもよいけれども,「3791」や「37 91」とするわけにはいかないためです.
 昨年度までは,特に意識していませんでしたし,授業で指示した書き方でないと×(バツ),といったこともしていませんでした.どれを採用しているかを,答案から集計するつもりも,ないのですが,上のように並べてみると,「\star」が最も手書きしにくく,「*」,「×」,「・」,そして省略の順に,書く手間が少なくなっていくようにも思います.

*1:一つの式で書くのも必須ではなく,「M^E \bmod N = CC^D \bmod N = M」も正解です.

*2:大部分は非負整数ですが,拡張ユークリッドの互除法アルゴリズム実行中に負の整数も出現します.

*3:「最後の講義の2日後に試験?」と驚いた方のために,補足をしておくと,試験の1週間前に,試験と同じ形式の「おさらい問題」を公開し,試験対策に使用してもらいました.試験の2日前の授業では,レポート課題で良い答案(スライド)を提出した3名の学生に口頭発表をしてもらってから,「おさらい問題」の解答と解説を説明しました.そして試験の実施要領を再アナウンスすると,ちょうどいい時間になったのでした.