読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

べき乗暗号

応用代数学入門 Ruby Book

練習問題7.5

問2

数式処理システムを用いて30桁の素数を生成して、ベキ乗暗号を試しなさい。

解答

  1. 平文を{x = 19282828282828282828}とする。但し{1\lt x \lt p}
  2. 30桁の素数{p}を準備する。
  3. 暗号化鍵{e}を選ぶ*1。但しgcd{(e, p-1)=1}
  4. 暗号文{y}の計算。{y=x^{e} \bmod p}
  5. 復号鍵の計算。{d=e^{-1} \bmod (p-1)}
  6. 平文の復元。{z=y^{d} \bmod p}

$ ruby modcrypt.rb
(1) x = 19282828282828282828
(2) p = 260856859417737166367332790431
(3) e = 9127
(4) y = 20807464111788263516835937299
(5) d = 183345760180210794592575857413
(6) z = 19282828282828282828

実行してみると、(1)と(6)の値が等しいことから、ベキ乗暗号を利用して暗号化、復号化が成功していることが分かります。小さい数を用いて手計算で試したことはあるのですが、実際に自分でプログラムを作成し、巨大な数で試してみると、なんとも不思議で興味深い世界だなと実感できますね。

応用代数学入門―暗号・符号・バーコードの仕組みが分かる

応用代数学入門―暗号・符号・バーコードの仕組みが分かる

  • 作者: ダレル・W.ハーディ,キャロル・L.ウォーカー,Darel W. Hardy,Carol L. Walker,鈴木治郎
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2005/12
  • メディア: 単行本
  • クリック: 3回
  • この商品を含むブログ (10件) を見る

*1:今回は4桁としました