Nim and RSA(6)

ある調査によると、男性の5%が、女性の10%がストーカーに狙われた経験が有るそうな。 ストーカーをするには、相手の事を良く知らなくてはならない。。。これ以上書くと、某所から 目を付けられるので控えておく。

いささか旧聞になるが、 Cookieなしでユーザー特定が可能、ブラウザー・フィンガープリントとは なんてのが出てた。オイラーの古い知識をひっくり返すような記事にちょいとびっくらしてますよ。 それぞれのクッキーは、指紋と同じでユーザーを特定可能。だから、クッキーはブラウザーに 保存しないようにしてたんだけどね。

相手は、そうきましたか。ビックデータの勝利と言うか何と言うか。。。

ブラウザでアクセスするだけでどんな情報が相手に渡る か、調べてみた。TESTMEって挑発ボタンを押すだけ。

オイラーの場合、Browser Plugin が、ちょっと特殊なんで、際立つだろうな。 User Agentを偽るってできたっけかな？ 後で調べてみようかな。木は森に隠せってのが 鉄則だから、利用が一番多いブラウザーを名乗ってとけだな。

遊びの材料が増えたわい。赤ボタンを押した時にどうなったか、ログを追跡してみた。

[sakae@fedora z]$ grep -E 'GET|POST' log.txt
GET /index.php?action=log&js=yes HTTP/1.1
GET /resources/jquery.flash.js HTTP/1.1
GET /resources/plugin-detect-0.6.3.js HTTP/1.1
GET /resources/deployJava.js HTTP/1.1
GET /resources/fetch_whorls.js HTTP/1.1
POST /index.php?action=ajax_log_clientvars HTTP/1.1
POST /index.php?action=ajax_log_clientvars HTTP/1.1
POST /sub/class2/server/ca HTTP/1.1
GET /sites/all/themes/frontier/images/social/email.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/digg.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/reddit.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/identica.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/delicious.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/facebook.gif HTTP/1.1
GET /sites/all/themes/frontier/images/social/twitter.gif HTTP/1.1

ブラウザーが手を変え品を変えて、操られてますなあ。で、コントロール元は何処よ？

[sakae@fedora z]$ grep Host log.txt | uniq -c
      7 Host: panopticlick.eff.org
      1 Host: ocsp.startssl.com
      7 Host: www.eff.org
[sakae@fedora z]$ grep Server log.txt | uniq -c
      7 Server: nginx/1.2.1
      1 Server: Apache/2.2.3 (StartCom)
      7 Server: nginx

さすがに、送信機は、無料で手に入る標準品か。

ここには書かないけど、常にRefererとCookieでトレースされてますなあ。X-Powered-By: PHP/5.4.36-0+deb7u3 なんてのを誤送信してたり、いや自慢だろうな。

この他、アクセスしてきた、IPアドレスを頼りに、どの国のどの地域って所まで分かっちゃうから、 困りものですなあ。いっそ、javascript拒否、画像拒否ってブラウザを、秘密トンネル経由で 使うのが良いかな。これぞ、忍法、隠れ身の術。

でも日頃からお世話になってるググル様は、 移動履歴・あなたの趣味をGoogleは全部知っている 状態だからなあ。手入れを察知して自分のPCをクリーニングしても、FBIから手を回して もらえば、悪行が一目瞭然だぞ。

Nim言語でRSA暗号

前回はRSA暗号の事をちょっと調べた。そして、nimlangでGNU MP すなわち、多倍長演算が 出来る事を知った。GMPには、RSA暗号を実装するに足る関数 が揃っている事も知った。 これはきっと神が、お前もNim語でRSA暗号をやってみろとの啓示をしてるんだろう。 そんな訳で、やってみる。

目標は、公開鍵と秘密鍵を自作し、そしてそれを使って、暗号化、復号化してみる事だ。 この目標を、Pythonでやった先例があった。 また、参考資料として、RSA暗号体験入門 を挙げておく。勿論、以前に買った、『素数夜曲』も大事な資料だ。

実装する中で、拡張ユークリッド法が出て来る。上の資料には無かったので、軽くnim-gmpの 中をgrepしたら、mpz_gcdextなんてのが引っかかってきた。extってきっと拡張って意味だろうな。 どんな事が出来るの？ 調べてみたらgmpのマニュアルが見つかった。 どうも、こういう事らしい。でも、引数が沢山で、何をどうしたら、どうなったってのがいまいち不明。 そりゃ、引数にconstが付いているのが、入力ってのは理解できますけどね。

mpz_gcdext ( g,  s,  t,  a,  b)
Function: void mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, const mpz_t a, const mpz_t b)

    Set g to the greatest common divisor of a and b, 
    and in addition set s and t to coefficients satisfying 
    a*s + b*t = g. The value in g is always positive, 
    even if one or both of a and b are negative (or zero if both inputs are zero). 
    The values in s and t are chosen such that normally, 
    abs(s) < abs(b) / (2 g) and abs(t) < abs(a) / (2 g), 
    and these relations define s and t uniquely. 
    There are a few exceptional cases:

    If abs(a) = abs(b), then s = 0, t = sgn(b).

    Otherwise, s = sgn(a) if b = 0 or abs(b) = 2 g, and t = sgn(b) if a = 0 or abs(a) = 2 g.

    In all cases, s = 0 if and only if g = abs(b), i.e., if b divides a or a = b = 0.

    If t is NULL then that value is not computed. 

そこで、カンニングする事にした。学業の世界ではまずいだろうけど、実業の世界では、中韓なんて 得意中の得意ですからね。最近は日の大学でも流行っているしね。

虫は無視できねぇぞ

[sakae@fb10 ~/nim/gmp]$ nim c rsa.nim
    :
rsa.nim(49, 19) Error: type mismatch: got (File, int literal(36), mpz_t)
but expected one of:
gmp.mpz_out_str(a2: ptr File, a3: cint, a4: mpz_t): csize
gmp.mpz_out_str(a2: ptr File, a3: cint, a4: mpz_srcptr): csize

nim_gmpは、Fileのポインターを要求してる。 今まで明にファイルを読み書きはしてなかったので、良い機会と思って、nimのFile型ってどうなってる か、関連も含めて調べてみる。 system.nimに有ったぞ。

File* = ptr CFile

FileMode* = enum 
  fmRead,                     ## Open the file for read access only.
  fmWrite,                    ## Open the file for write access only.
  fmReadWrite,                ## Open the file for read and write access.
                              ## If the file does not exist, it will be
                              ## created.
  fmReadWriteExisting,        ## Open the file for read and write access.
                              ## If the file does not exist, it will not be
                              ## created.
  fmAppend                    ## Open the file for writing only; append data
                              ## at the end.

File型って既にptrになってるじゃん。それのptrを要求するって、そりゃハンドル型が欲しいの？ そんな難しい物を要求することはおかしいぞ。GMPのマニュアルはファイル型だし。 (最新のやつだと、char型になってるんで便利そう。）

gmp/pure.nimを見る

proc mpz_out_str*(a2: ptr FILE; a3: cint; a4: mpz_srcptr): csize {.
    importc: "__gmpz_out_str", dynlib: libgmp, cdecl.}
proc mpz_out_str*(a2: ptr FILE; a3: cint; a4: mpz_t): csize {.
    importc: "__gmpz_out_str", dynlib: libgmp, cdecl.}

この部分のptrを削除。（他にも有ったけど、取り合えず使う分だけ） これで、コンパイルが成功して、実行ファイルが作成できたぞ。

試運転

[sakae@fb10 ~/nim/gmp]$ ./rsa
seed: c11b16a3ea2bb11fb522615f9c8e7515
p: 1102439311136943874117432549288399948698543308561
q: 1215372434740099341474139770111245571951604131692030523901694287659745916195443463591348455891109
n: 1339874349729705391795150042791836898641828739955314589524683594114054839569346905610336300912316097873837570991231094805439022895945852403484149
e: 65537
d: 567356654704198457782736604322997173721857719493815819666188899757906022554108195396878308747105724998622871859733553109765831063983604769432513

Hello World 987654321000000000000000000000123456789
m: 8774209015060724364391639978587180311587930192621341160844537856098753433369
c: 539736728512676627146416562697896941182778553252860631925638146417500653656560196907839839962195493501657315965622277260610824612897177794927673
a: 8774209015060724364391639978587180311587930192621341160844537856098753433369
helloworld987654321000000000000000000000123456789

もう一度、実行

seed: 68a59817b0d6d935deb04ca7d981f83a
p: 597427912252452614414442360829107589618309381979
q: 356920110338324220680855127073655783037080209113815940136712760329719384159683969105252929957287
n: 213234036360340067732391683988504242084657848301997452090211961832271011572525124147503321618464817159080431499708144654814766275412099837530973
e: 65537
d: 177255246149121359689838817034800534118590642196394014705151836419760137525241474968762017879060693167700737779218098874141975067716189279351909

Hello World 987654321000000000000000000000123456789
m: 8774209015060724364391639978587180311587930192621341160844537856098753433369
c: 100430203744736895591914327573774006724009044142786603174003039392902434728505844808440360184283193901145734076669381930228250592721056706884531
a: 8774209015060724364391639978587180311587930192621341160844537856098753433369
helloworld987654321000000000000000000000123456789

どうやら動いてる。 Hellow World 987... てのが平文。それを、暗号化して、復号化。結果は、スペースが 除去されちゃってる。このままの形で使うなら、スペースを他の文字列に置き換えないと いけないな。どんなのが良いだろう？

/usr/share/dictの中にある、世界の単語帖(英語版)に無いものなら、大丈夫。思い付いたのを調べてみると、 zqとかqzと言う文字並びは無い。また、頭文字がｚで始まる単語の方がqで始まるものより 少ないから、zqを使えばいいか。

nim用のRSA暗号code

ソースはベタに書いてあるので、段階的に表示する。まずは、素数を得る為の、ランダムな 値（乱数）を決める。

## RSA using GMP

import gmp
import gmp/utils
import times
import md5

let one: mpz = 1   # convert int to mpz_t
var p = init_mpz() # initialized to zero
var q = init_mpz()
var n = init_mpz()
var e: mpz = 65537
var d = init_mpz()
var t = init_mpz() # (p - 1) * (q - 1)
var seed = getMD5($(getTime())) # seed for random
echo "seed: ", seed

最初はgmpで使う変数の宣言。ｐ、ｑは素数。ｎは、両者の積。ｅは公開鍵。sslとかに習って、 この値は固定にした。ｄは秘密鍵。ｔは、コメントの通り。

RSA用の鍵は、利用者に公開されるものとして、(e, n)のペアーになり、秘密にしなきゃならないのは、(d, n)の ペアー。

乱数を得るのはGMPが提供してる関数を使えばそれで済むんだけど、今回はあえて、自作 してみた。

毎度お馴染みの方法。現在時刻を得る。それを文字列化。今となっては古めかしくなったMD5 ハッシュを通す。nimがsha2-512とかをサポートしてればいいんだけど、無いからしょうがなくMD5です。 結果は、128Bitになるんだけど、それの16進表現の文字列が得られる。

mpz_nextprime(p, init_mpz(seed & "deadbeef", 16))
mpz_pow_ui(q, p, 2)
mpz_nextprime(q, q)
mpz_mul(n, p, q)
echo "p: ", p
echo "q: ", q
echo "n: ", n

得られた乱数に塩を振る。deadbeafを公開しちゃったら意味ないけど、まあいいか。そして、 その文字列(16進数)をinit_mpzで数値に変換し、それより大きい素数をｐに得る。

もう一個素数ｑが欲しいんだけど、それの元は、やっちゃいけないと承知の上、ｐを２乗したものの近辺 から見繕ってくる(単にmpz_pow_uiを使ってみたかっただけ)。よって、ｑの桁数の方がｐに比べて大幅に大きくなる。本来は、同程度の 桁数が安全上望ましい。

最後は、二つの素数の積を取る。この積が、鍵の一部（実質的には、ユーザーに公開される 鍵そのものになる。だって、鍵の片割れ、ｅはほとんど、公然の秘密だから）

var p1 = init_mpz()
var q1 = init_mpz()
mpz_sub(p1, p, one)
mpz_sub(q1, q, 1)
mpz_mul(t, p1, q1)
echo "e: ", e
mpz_gcdext(p1, d, q1, e, t)
if d < 0:
    mpz_add(d, d, t)
echo "d: ", d

次は、得られた２つの素数から、それぞれマイナス１した値を求め、それの積、ｔを得る。 ed = 1 (mod t)なる関係のdを求める。eは決め打ち（新たにeなる素数を決めてもよいけど) してるんで、拡張ユークリッド法の関数に、eとtを渡す。第二引数に求めるdが得られる (p1,q1はダミー)。 dが負の場合は、tを加える。

var M = "Hello World 987654321000000000000000000000123456789"
echo "\n", M
var m = init_mpz(M, 36)
echo "m: ", m
var c = init_mpz()
mpz_powm(c, m, e, n)
echo "c: ", c
var a = init_mpz()
mpz_powm(a, c, d, n)
echo "a: ", a
#var fd: File
#discard open(fd, "zzz.txt", fmWrite)
#defer close(fd)
discard mpz_out_str(stdout, 36, a)
stdout.write "\n"

次は、求まった鍵を使って、暗号化/復号化します。平文は、何らかの方法で数値に変換 する必要が有ります。

平文を数値に変換するのに、GMPのinit_mpzを使ってみます。こやつ、(36+26)進数まで扱って くれるので、数字とアルファベット26文字（と、無視されるけど、スペースも可）を 受付ます。 平文Mを入力して、GMP仕様の数値mを得る。秘密キーとこのmを与えて、暗号化された数値ｃを得る。 普通は、これをメールとかで、送るわけだ。

で、暗号化された数値ｃを受け取ったとして、今度は、公開キーを使って複合化します。結果は、 aに返ってくるんだけど、これはただの数値。人間が読めるように、36進数と看做して、 文字列変換・表示をします。 ふー、長かったけど無事に動いた。

上記は手抜きなんで、英数字しか使えない。man asciiすると、他にも使いたい記号が 有ったりする。日本語はどうよって声があるな。とか、思っていたら、 fedoraでman asciiしようとしたがman原稿が入っていなかったんで、man-pages(-ja)を入れた。

上でGMPは、(36+26=)62進数まで扱えるって書いたけど、62進数を選ぶと、英字の大文字・小文字が 区別出来ます。これを使えば、キャメルケースで簡易的にスペースが表現出来ますな。-36進数 なんてのも指定出来たりして、これは英大文字の世界になります。

暗号化・復号化でも同じ関数を使い、鍵だけが違っていた。と言う事は、秘密鍵で暗号化して、 それを公開鍵で復号化してもいいわけだ。そんなの意味ないじゃんって言われそう。でも、 ちゃんと使い道があります。

そう、印鑑証明の代わりになります。陰影を村役場とか町役場（決して、秋葉原の昭和通り口 近くにある居酒屋の事ではありません）に届けとく。重要書類に印を押す時は、印鑑証明を 添えるんだった。その印鑑は、本人しか持っていないはずだから、本人証明に利用される。

秘密鍵（印鑑相当）で暗号したのは、それとペアーになる公開鍵でしか正しく復号化出来ない。 よって、公開鍵を公的機関相当へ届けておけば、秘密鍵を持ってる人の本人証明に使える。 なかなか便利な機能だな。

以下、ちょっとした余談。 先にファイルの扱いを調べたので、コメントを外して、stdoutの代わりにfdを使えば、出力が ファイルに落ちる。openの所が、discardになってるのは手抜き。本来なら成功/失敗が論理地で 返ってくるので判定しましょう。普通、openの結果はfdとかで受け取って、それが負なら失敗 って書くけど、nim流は、ちとまごつくぞ。

これらを実験してる時、mpz_out_strにstdoutを渡さず、代わりにnilを渡しても、表示して くれる事に気付いた。その場合は、上で騒いだ、pure.nimの中のptrを外さなくても大丈夫 だったよ。作者さんは、こういう使い方を想定してんのかなあ。

tccは困ったちゃん

fedoraでnimhsを使うと困ったちゃんになる。

[sakae@fedora gmp]$ nimhs rsa.nim
/home/sakae/.nimble/pkgs/nim-gmp-0.2.1/gmp/pure.nim(67, 2) Hint: 'GMP_RAND_ALG_LC' is declared but not used [XDeclaredButNotUsed]
SIGSEGV: Illegal storage access. (Try to compile with -d:useSysAssert -d:useGcAssert for details.)
Error: execution of an external program failed

仰せに従ってコンパイル実行してみると、少し詳細が出てきた。何とmd5の中で落ちていますよ。

[sakae@fedora gmp]$ ./rsa
Traceback (most recent call last)
rsa.nim(15)              rsa
md5.nim(229)             getMD5
md5.nim(203)             md5Final
md5.nim(184)             md5Update
md5.nim(95)              transform
md5.nim(51)              FF
md5.nim(47)              rot
SIGSEGV: Illegal storage access. (Try to compile with -d:useSysAssert -d:useGcAssert for details.)

proc rot(x: var int32, n: int8) {.inline.} =
  x = toU32(x shl ze(n)) or (x shr toU32(32 -% ze(n)))

proc FF(a: var int32, b, c, d, x: int32, s: int8, ac: int32) =
  a = a +% F(b, c, d) +% x +% ac
  rot(a, s)
  a = a +% b

いかにもtccコンパイラには解決が難しそうなコードだ事。はて、どうすべ？ まずはMD5のお勉強から。そしてmd5.nimをじっと眺める。 眺めてばかりいてもしょうがないので、md5.nimをtestme.nimとかして俎上に乗せよう。

その前に、上のコードに見慣れないのが有ったので調べておく。仮引数の型の前に有るvarは、 参照呼出しだな(指定されたアドレスから値を受け取り、演算後、そのアドレスに結果を置く)。varが無ければ、値呼び出し。

+%    treats x and y as unsigned and multiplies them. The result is truncated to 
      fit into the result. This implements modulo arithmetic. No overflow errors
      are possible. 
ze    zero extends a smaller integer type to int. This treats x as unsigned. 
toU32 treats x as unsigned and converts it to an int32 by taking the last
      32 bits from x.

コードの一番最後に、テストコードが付いていたので、ちょっと改造。

when isMainModule:
  echo getMD5("")

ついでに、関数FFの所で、rotの前後でどうなるか、echoした。

[sakae@fedora t]$ nim c -r testme.nim
  :
/home/sakae/t/testme
-680876809 7
-1252885525
-1231747242 12
1349872489
   :
[sakae@fedora t]$ nimhs testme.nim
-680876809 7
SIGSEGV: Illegal storage access. (Try to compile with -d:useSysAssert -d:useGcAssert for details.)
Error: execution of an external program failed

うん、どんなデータでもBug再現。

先に、手回しよく、gdbに賭けられるように、簡単なコンパイラスクリプトを用意しとこう。

[sakae@fedora t]$ cat ~/.nim/bin/nim4g
#!/bin/sh
nim  --debuginfo  --lineDir:on -d:release c $*

ちょいと実験コードを書く

proc rot(x: var int32, n: int8) {.inline.} =
  x = toU32(x shl ze(n)) or (x shr toU32(32 -% ze(n)))

var x: int32 = -680876809
var n: int8 = 7

x = toU32(x shl ze(n)) or (x shr toU32(32 -% ze(n)))
#rot(x, n)
echo x

rotを呼ぶのをやめて、手動展開してあげると、落ちる事なく、正しい結果を返す。しかし、 rotを呼ぶと、やはり落ちる。落ちた時の逆アセンブラ結果。

Dump of assembler code for function rot_88003:
   0x0804845d <+0>:     push   %ebp                ; save ebp
   0x0804845e <+1>:     mov    %esp,%ebp           ; sp -> ebp
   0x08048460 <+3>:     sub    $0x18,%esp          ; for temp
   0x08048466 <+9>:     mov    0x8(%ebp),%eax      ; x addr
   0x08048469 <+12>:    mov    0x8(%ebp),%ecx      ; x addr
   0x0804846c <+15>:    movsbl 0xc(%ebp),%edx      ; n
   0x08048470 <+19>:    and    $0xff,%edx          ; uint8
   0x08048476 <+25>:    mov    %eax,-0x4(%ebp)     ; x adr
   0x08048479 <+28>:    mov    (%ecx),%eax         ; x
   0x0804847b <+30>:    mov    %edx,%ecx           ; n
   0x0804847d <+32>:    shl    %cl,%eax            ; shl
   0x0804847f <+34>:    mov    %eax,%ecx
   0x08048481 <+36>:    sar    $0x1f,%ecx          ; 
   0x08048484 <+39>:    mov    0x8(%ebp),%edx      ; x addr
   0x08048487 <+42>:    movsbl 0xc(%ebp),%ecx      ; n
   0x0804848b <+46>:    and    $0xff,%ecx          ; uint8
   0x08048491 <+52>:    mov    %ecx,-0x8(%ebp)     ; temp save
   0x08048494 <+55>:    mov    $0x20,%ecx          ; 32
   0x08048499 <+60>:    mov    %ecx,-0xc(%ebp)     ; save ecx
   0x0804849c <+63>:    mov    -0x8(%ebp),%ecx     ; restore
   0x0804849f <+66>:    mov    %ecx,-0x10(%ebp)    ; save
   0x080484a2 <+69>:    mov    -0xc(%ebp),%ecx     ; restore ecx
=> 0x080484a5 <+72>:    sub    %edx,0xa(%ecx)      : SEGV ! Why ecx ?
   0x080484a8 <+75>:    mov    %ecx,-0x14(%ebp)
   0x080484ab <+78>:    mov    -0x14(%ebp),%ecx
   0x080484ae <+81>:    sar    $0x1f,%ecx
   0x080484b1 <+84>:    mov    (%edx),%ecx
   0x080484b3 <+86>:    mov    %ecx,-0x18(%ebp)
   0x080484b6 <+89>:    mov    -0x14(%ebp),%ecx
   0x080484b9 <+92>:    mov    -0x18(%ebp),%edx
   0x080484bc <+95>:    shr    %cl,%edx            ; shr
   0x080484be <+97>:    or     %edx,%eax
   0x080484c0 <+99>:    mov    -0x4(%ebp),%edx     ; x address
   0x080484c3 <+102>:   mov    %eax,(%edx)         ; store result
   0x080484c5 <+104>:   leave
   0x080484c6 <+105>:   ret

cdecl とかを見て、 IA32（x86）汎用命令一覧 を、参照の事。それにしてもこの糞石は、疲れるから、もう止めよう。