べき乗暗号 - Mae向きなブログ

練習問題7.5

問2

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

解答

平文を ${x = 19282828282828282828}$ とする。但し ${1\lt x \lt p}$
30桁の素数 ${p}$ を準備する。
暗号化鍵 ${e}$ を選ぶ*1。但しgcd ${(e, p-1)=1}$
暗号文 ${y}$ の計算。 ${y=x^{e} \bmod p}$
復号鍵の計算。 ${d=e^{-1} \bmod (p-1)}$
平文の復元。 ${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桁としました