微分形式による解析力学
木村利栄、菅野礼司著
吉岡書店
広告

微分形式による解析力学

RSA暗号

法33でのべき乗の表。

この表を見るとRSA暗号の構成が分かりやすい。A列に平文が、2行にべき乗数を並べてある。交点には平文をべき乗した値の、33を法として計算した値が入っている。21列目に平文が現れるのが暗号、復号の原理。平文を3乗して暗号化し、暗号を7乗すると平文に戻ることになる。7乗して暗号化、暗号を3乗しても同じ。21の約数は1、3、7と21なのでこうなるが、1と21の組み合わせでは暗号ができない。11列目と31列目にも平文が現れるが、どちらも約数が1と11しかないので暗号にならない。

33は二つの素数3と11の積になっている。11乗、21乗と31乗は、(3-1)=2と(11-1)=10との公倍数10、20、30それぞれに1を足した11、21と31に由来する。

二つの素数p,qの積p*qを法とする。(p-1)と(q-1)の最小公倍数をL=lcm((p-1),(q-1))とする。n* L+1の約数のうち、1とその数を除く約数uと、u*v= n* L+1となるv,nを取ると、uとvが暗号鍵、復号鍵となる。

vとnとは、不定方程式u*v- n* L = 1の解なので、拡張ユークリッドの互除法で特異解v0, n0を求めることができ、一般解はv0+k*L, n0+k*uとなる。

P=3,q=11の場合、L=10。,u=3とすると3v-10n=1の特異解は、7,2なので、暗号鍵u=3の時、復号鍵はv=7と確認できる。この時n=2でべきは21になることも確認できる。一般解は、v=7+10*k,n=2+3*k。暗号鍵が3の時、17も復号鍵になる。この時のべきは51。

この表はexcelで作成しており、二つの素数をp,q、A列の平文x、2行のべきuとすると、交点の暗号はy=mod(x^u,p*q)で計算でき、mod(y^v,p*q)で復号できることになる。但し、x^u,y^vはすぐに大きな数になるので、u=10あたりから先はオーバーフローしてしまう。u,vを2進数で表現してx,x^2,x^4,x^8,x^16・・・の法を取った積を計算することでp*qの範囲の積に収まる。べきの小さな項から計算すれば前の計算結果が使えるので計算量も激減する。

この表はこちらのページにあったもの。数式で理解していたつもりのところが、実感できてよかった。証明はこちらのページのが分かりやすかった。あらすじは以下。
p*qより小さな正の数xが暗号化、復号化して、x=x^(u*v) mod(p*q) となる必要十分条件を考える。
変形して、x*(x^(u*v-1)-1)=0 mod(p*q)
すなわちx* (x^(u*v-1)-1)はp*qの倍数。ここでpとqは素数なのでpの倍数且つqの倍数となる。
x*(x^(u*v-1)-1)=0 mod(p) 且つx*(x^(u*v-1)-1)=0 mod(q) —(1)
ここでxがp,qのどちらかの倍数の時は自明。以下はxはp,qと素である場合を考える。
Xは0でなく、且つp,qの倍数でないので、これはxで割っても成立する。
両式を変形して、x^(u*v-1)=1 mod(p) 且つ x^(u*v-1)=1 mod(q)
xとp,qが素なので、フェルマーの小定理(aとpが素な時、a^(p-1)=1 mod(p))より、
u*v-1=mod(p-1) 且つ u*v-1=mod(q-1)
p,qとそれぞれ素なk,lについて
u*v-1=k(p-1), u*v-1=l(q-1)
の時、(1)の両式が成立する。
L=lcm((p-1),(q-1))とすると、u*v-1=0 mod(L) が必要十分条件となる。
すなわち、u*v=n*L+1となれば良い。

復号鍵17のケース(普通7とするところ)をMaximaで計算すると、次のような感じ。15を3乗して33で法を取り暗号9を得、17乗して法を取って復号化して15に戻る。拡張ユークリッド互除法の仕様の関係で、k=1のところ、2のように見える。

(%i21)

p:3;
q:11;
factor((p-1)*(q-1));
load(gcdex);



(%i43)

u:3;
igcdex(u,lcm((p-1),(q-1)));



(%i45)

v:%[1]+2*lcm((p-1),(q-1));
x:15;
y:mod(x^u,p*q);
mod(y^v,p*q);


CindyJS

幾何作図ツールシンデレラは、HTMLに埋め込まれてWEBで表示可能なCindyJSのコードを作成できる。

基本的な作図例を作成して、Azureサーバに載せてみた。シンデレラで作成した図形の構成要素、構成方法が保存されている。移動可能な要素を移動しても図形の構成情報が保存されるており、動かすことで作図意図が直観的に理解できる。
幾何図形を使ったWEBページの作成に適している。

シンデレラの作図機能が完全にはサポートされていないが、おいおい機能追加されるらしい。
円以外の二次曲線はまだサポートされていないらしいのが、やや不満ではある。

幾何学ソフト(シンデレラ)

シンデレラと言うソフトを見つけて試してみる。

平面幾何学の作図が易しくできて感激。さっそく、円の幾何学、アルべロスなどをトライ。

アポロニウスの問題など、つい、夢中になってしまった。

パップスチェイン、とても他の手段では書けない。

パップスチェイン

Maximaのdrawパッケージの練習にフォローしてみる。

 ほんの序の口だけだが、苦労した。

網掛け部分が、アルベロス。


アルキメデスの研究: 面積が等しい


アルキメデスの(双子の)円


パップスチェイン(2まで)


バンコフの円


バンコフの研究。もう一つのアルキメデスの円

アルベロス