●学生部門の入賞の設計概要について

  優勝・準優勝の５チームの設計したＲＳＡ暗号デコーダについて概要をご紹介します。

１）優勝(電子情報通信学会ＳＩＳ賞) Garuda Parahyangan Team　

  Garuda Parahyangan Teamの設計の基本方針は、以下の式に示されるように、指数蒸散演算を２進数で分解して、繰り返し演算とする基本的な方法に従っています。
  
  この式では２種類の剰余乗算が含まれています。ひとつはa2で、もう一つはi=0からl-1回の剰余乗算です。 　　　　　　　　　　　　　　
  剰余乗算の一般形 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  S = X x Y mod M 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  を計算する場合、Garuda Parahyangan Teamは以下のコード１ようなforループによる実現方法を考えました。回路図で示すと、以下の回路図１がforループの１回分となります。図をみてわかるように、この実現方法ではループの中に加算が存在し、ＲＳＡ暗号の取り扱うビット幅が512bitのような大きな数になる場合に、通常のキャリー伝播型の加算器では加算の速度が低下し、高性能な回路を実現することができません。　　　　　　　　　　　　　　 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  （コード１） 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  （回路図１） 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  そこで、Garuda Parahyangan Teamはこのループ内の加算に処理ビット数に応じて演算速度が低下しにくいCarry Save Adder (CSA)を用いて実装しました。 　　　　　　　　　　　　　　
  以下のコード２がCSAでの実装を示すアルゴリズムで、forループの中の３行はCSAのループとなりますが、ここで、新たにＡを計算する必要が生じ、Ａの値を事前計算したＴＡＢＬＥから取り出す構成としています。要素回路ブロック図を回路図２に示します。 　　　　　　　　　　　　　　
  このような工夫により、５１２ビット程度の大きな平分の暗号化に対しても対応できる高性能な回路を実現しました。課題では、難易度を考慮して３２ビット程度の暗号化を例としていましたが、このような大きな平分の処理をトライしたことが審査員に評価されました。 　　　　　　　　　　　　　　
　　　　　　　　　　　　　　
  （コード２）


  （回路図２）