RSA暗号をMaximaでやってみる
公開鍵(e,n)=(97,9577)が与えられた状況を考える。(Maximaでは:が代入演算子)
e : 97 n : 9577
後で使うので拡張ユークリッドの互除法を計算する関数を定義しておく
xeuc(x,y,a,b) := if y=1 then b else (c:fix(x/y),xeuc(y,x-y*c,b,a-b*c))
e,nを使って平文4649(夜露死苦のつもり)を暗号化してみる。
mod(4649^e,n) => 4954
公開鍵nを因数分解して素数対p,qを求める(本当はここが大変な計算量)
factor(n) => 61 157
素数対p,qと公開鍵eから拡張ユークリッドの互除法を使って秘密鍵dを求める。
d : xeuc((61-1)*(157-1),e,0,1) => 193
秘密鍵dを使って暗号文4954を復号する。
ちゃんと4649になった!
mod(4954^d,n) => 4649
秘密鍵dを使って平文4649に署名する。
mod(4649^d,n) => 3734
公開鍵eを使って署名文3734を検証する。
ちゃんと4649になった!
mod(3734^e,n) => 4649
おぼえがき
Maxima Manual: 色々な演算子
演算子: ":"
割当を行う演算子。例えば、A:3で変数Aに3を割当てる。
演算子: "::"
割当を行う演算子。::は一つの原子変数や下添字付けられた変数に対して評価しなけ ればならない左辺の値として右辺の式の値を割当てる。
演算子: "::="
":="の代りに関数の定義では無く、マクロの定義が続く事を示す為に用いられる。 DESCRIBE(MACROS)を参照せよ。
演算子: ":="
関数定義の演算子。例えば、F(x):=SIN(x)で関数Fを定義する。
演算子: "="
MACSYMAでの等号を示す。MACSYMAのパターン照合機能に対し、等号で結ばれる二つの 式の間に存在する全ての関係が構文的に同一であり、その時に限る事を示す。関数: FIX (x)
http://www.bekkoame.ne.jp/~ponpoko/Math/maxima/maxima_19.html
ENTIER(X)と同じ働きをし、Xが実数の場合はXを越えない最大の整数を返す。
Maxima Manual: 関数定義
http://www.bekkoame.ne.jp/~ponpoko/Math/maxima/maxima_7.html
関数の右手側は式である。それ故、式の列が欲しければ次の様にする。
f(x):=(expr1,expr2,....,exprn);
すると、exprnの値が関数によって返される値となる。
追記
ん？ここでは拡張ユークリッド互除法は使わずにやってるな。これでもいいのか。
pq = p*q
http://itpro.nikkeibp.co.jp/article/COLUMN/20071004/283832/?P=4&ST=oss
k = n*(p-1)*(q-1)+1 ただしnは任意の正の数
e,d = e*dがkとなる任意の正の数
今回の例でいうとこういう関係か。
pq = 9577 = 61*157 k = 2*(61-1)*(157-1)+1 = 18721 d = 18721/97 = 193
