Syntax highlighter

2011-08-31

マクロを書き直した

基本的な方針はバージョン0.1.3までと一緒だが、マクロ展開時に渡す環境をVMに持たせて参照できるようにした。また、今まで行っていた環境のスワップやパターン変数の保存などの入り組んだ処理を全部取っ払ってすっきりさせた。
そのおかげか、R6RSテストスイーツのcontributeとletrecの参照テストを除く8881個のテストが通った。(今まではbound-identifier=?のテストが一つ通ってなかった)
ここまでは順調だった(というっても2週間くらいかかったけど)が、やはりスコープは曲がらない。
ちょっとだけゆがむ程度。syntax-caseは不完全なんですって言い張ってしまうことにしよう。個人的な意見だとマクロ展開フェーズを持たないとあれはきついのではないかと思う。っが、単に勉強不足なのかもしれない。(参考資料も無いけどね!!)

このマクロ書き直しに伴ってキャッシュを少し修正。今まで識別子が持っていた環境内にあるマクロの書き出しを行っていなかったが、するように変更。また、不正オブジェクトの検出を強化。そのため、(core syntax)ライブラリが不正になるようになってしまった。
(なんでハッシュテーブルが内部にあるんだよ?)
オブジェクトの書き出しは本当にどうしようか悩むところで、絶対的にすべてのオブジェクトをキャッシュすることが不可能なのが分かっているからだ。基本的にはリスト、ベクタ、文字列、シンボル、識別子、マクロ、それにライブラリ(名前とimport、exportスペックだけ)で問題ないはずなんだけど、どこかのタイミングでそれ以外のものが入った場合どうしようかなぁと。今のところ分かっているのがハッシュテーブルで、ハッシュ関数が組み込みのものまでは入れてもいいかなぁとは思うものの、面倒だなぁというのが勝っている感じ。実際今のところ1つ2つしかないし。

どうでもいいが、キャッシュを使うとライブラリの読み込みがやはり早い。

2011-08-25

マクロの書き直し

をしているのだが、それに伴ってキャッシュが壊れていることが分かった。

事の発端は識別子にマクロ展開時に必要になる情報を足したところから始まる。それこそコンパイル時の環境をそのまま保存しようとしたのだが、どうやらその際に問題が起きる。
ただ、分かっているのはその壊れたキャッシュを読み込みとセグるということだけで、それがキャッシュの書き込み時の問題なのか読み込み時なのかが分からない。
一つ分かっていることとして、起きる場合は必ず一つのオブジェクトを読み込む際に一つ余計に読み込んでいるということ。ここから察するに、ベクターもしくはリストの読み込みもしくは書き込み時に問題が起きていると思われる。
そうは言っても、すべてのキャッシュで起きるわけではなく、正直何故起きるのかさっぱり分からないが、識別子にマクロ用の環境を持っている物に対してのみ起きる(ような気がする)

マクロの実装と同時並行で発生するのでかなり面倒だ。

2011-08-22

マクロ戦争再び

戦争ではないが気分的に。
とりあえず(自分に)必要そうなライブラリは揃った感があるので、先送りしていた問題に取り掛かろうかなぁと気分。

それに伴いマクロの展開とその環境を少しまとめて思い出しておこうというもの。

≪環境≫
マクロには2種類の環境があって、作成時にマクロ自体が持つmac-envと展開時にコンパイラから与えられるuse-envがある。ちなみに名前はChibi Schemeから。
前者の環境が何故必要かというと、例えばパターン変数などを一意にするために用いる(はず、の予定)
後者の環境はローカル変数の識別とか展開時する際にシンボルを識別子に変換するなどに使い

≪方針等≫
基本的には既存の物と一緒。マクロ(この場合はsyntax-case)をコンパイルし展開器を作成。展開器は単に関数を呼ぶだけ。問題となるのは、現状のままだと与えられたS式にmac-envとuse-envをくっつける形になるので、syntax-caseに直接S式を渡すものに関しては環境が取れない。
この辺をどうした方がいいのかちょっと悩み中。そもそも直接S式を渡された場合に環境は必要なのかとか。
また、現状でもそうだが、syntax-caseとsyntaxのコンパイルを別にする必要がある。

困ったことにR6RSは非常に人気が無いのかsyntax-caseの実装が知ってる限りでは3つしかない。1つがnmosh、Larcenyなどで使われているSRFI-78(だったと思う)をベースにした実装。2つ目が超有名なpsyntax。mosh、Chickenなど多数がこれ。最後がYpsilonの独自実装。
Racketも独自実装だった気がするが、ちょっとうろ覚え。
おかげで基本的にこれを解説しているサイトがない!論文もpsyntaxが基本とかで結構げんなり気味。あと、R6RSがマクロ展開とコンパイルを分けることを要求しているので、どれもそこまで参考にならないという落ちつき。
とりあえず比較的読むのが楽だったYpsilonの実装を参考にしているが、う~ん。

気合と根性で空中分解するしかないか・・・

Sagittarius version 0.1.3 has been released

As I mentioned before, I could not manage to write the document... I will do it by next release!!(I hope)
You can download it here

From this release, it has enough libraries(for me). So I will rewrite macro expansion which does not compromise R6RS syntax-case. (If I just use er-macro-transformer, it works perfectly though)

2011-08-17

ドキュメント書かなきゃ

と思いつつ遅々として進まない。
でも、いろいろ追加しちゃったからそろそろ0.1.3のリリース時期かなぁとか思いつつ。

0.1.3で追加される機能
* Cryptographicライブラリ
* 上記の付属する数学ライブラリ(ハッシュ関数とか、乱数とか)
* REPL
* lalrパーサージェネレータ
* ASN.1ライブラリ

(FFIって前回のリリースだったかな?)
最後のASN.1ライブラリができて、PKCS#1 v1.5パディングがRSAの署名と検証に追加できたらリリース予定。それまでにドキュメントが間に合えばそれも・・・
(多分無理-_-)

REPLを除いたライブラリはすべてSagittariusでしか動かないという素敵仕様(なのか?)。他の処理系との互換性なんてまったく考えなくなってきた。やべぇ。なにしろGauche由来のキーワードを使用したdefine(define-with-keyとして(sagittarius control)ライブラリで提供)が便利すぎて、ちょっと手放せない。こいつのおかげである処理の振る舞いを変更することが明示的かつ簡便に行えるので正直互換性を失っても有り余る便利さ。
(まぁ、他の処理系で何か書いているわけではないので、そんなこと言うのかもしれないが。自分用だしいいよね?)

以前書いたsyntax-caseの問題は0.2.0以降に先送りの方向にしている。自分で使う分には問題にならないし。

ちょっと先取り0.1.3
暗号ライブラリの部分を先取り。気に入ったら使ってくださいという宣伝。DES、DES3、RSA辺りはまじめにテストしてあるけど、AESとかは未テスト。仕事で使わないんだもん。
(import (crypto) (sagittarius control))
(define des-key (string->utf8 "8bytekey")) ;; DES鍵は8バイト
(define des-cipher (cipher DES des-key :mode MODE_CBC :iv (make-bytevector 8 0))) ;; :ivはCBCモードでは必須
;; その他:padder :rounds :ctr-modeがキーワードとしてある。必要になりそうなのは:padderとMODE_CTRを指定した際の:ctr-modeかな。
(let1 enc (encrypt des-cipher (string->utf8 "test message"))
  ;; encは上記のDES鍵で暗号化されたbytevector
  (display (utf8->string (decrypt des-cipher enc))))
こんな感じで使える。cipherが使いまわせるのはJavaと同じ感じにしたため。一度作成すると鍵の交換が現在できないけど、必要そうなら入れるかも。
共通鍵方式の暗号化はほぼlibtomcryptの機能なので、他の暗号方式でもよほどOKだと思う。
RSAも上記と同じAPIで指定するキーワードが少し違う。RSAでは鍵の生成も可能(共通鍵の方は用意してない)。問題は1024ビットの鍵を生成すると30秒くらいかかることか。(もちろんマシンスペックによるが)。
この辺は上記のASN.1ライブラリができたら保存と読み込みをサポートする予定。

暗号ライブラリがどれほどの需要があるかは分からないが、僕は年がら年中使うのですごく有用。DES3(DESede)はちょいちょい使ってるし。

仕事で使う使い捨てのスクリプトがSagittariusでかかれるようになってきてるなぁ、いいことだ。

2011-08-16

母が訪ねてきていた

ということで、先週の木曜日から1週間弱(6日)と短いがちょっと遅めの夏休みを取っていた。
(1週間弱で短いというのはヨーロッパ感覚です。休暇は2週間から!!)

だからといって母は去年既に訪れているのでいわゆる、とりあえず行っておけという場所は既に訪問している。なので今回は週末3日間はドイツに行ってきた。
ドイツはデュッセルドルフという人口59万人の都市。市街地だけなら1日あれば周れる。観光バス、観光フェリーもある。とりあえず、バスとフェリーは乗っておいて、市街地+日本人地区を周る。
デュッセルドルフの街は第二次大戦後、日本の各企業が欧州の貿易拠点に選んだらしく、一つの通りが丸ごと日本人地区になっている。いわゆるチャイナタウンの小規模バージョンみたいな感じ。ここでは日本語しか話せないおっさんがパン屋やってた。(いや、ドイツ語も話せるのかもしれんが、日本語だけで対応された)
まぁ、ここだけにいてもしょうがないので、アルトシュタット(Altstadt)に行く。どうでもいいが、ホテルの受付で案内を聞いたときに「old city」って言われてなんだろうと思っていたのだが、Altstadtの直訳がそれだった。
カフェがひしめき合ってるイメージでそこらじゅうにスポーツカフェ(バーか?)があった。どうもサッカーの試合があったらしく、どこも混んでいて人多すぎ状態に。適当にお茶して、フェリーの時間を待つことに。
(写真撮っておけばよかったかなぁ)
っで、フェリーの時間なので乗る。ちなみにフェリーはいまいちだった・・・行く方はバスだけの方がいいと思う。

観光バスはいわゆるHop On Hop Offバスなので適当に乗って適当に降りれる。でも、降りずに一周。ガイド音声に日本語もあるのだが、なぜか途切れ途切れになっていまいち分かりづらかった。話が飛ぶ感じ。「ここ、デュッセルドルフではアルトビールが・・・さてここでデュッセルドルフの歴史を振り返ってみましょう」みたいなの。多分、バスの運ちゃんがドイツ語の音声ベースで切り替えてるとみた。

特に「ドイツ!!」って感じのものはあんまり感じず、普通の街って感じ。少し外れまで行けば城とかあったみたいだけど、そこまでは周れず。
アルトシュタットだけでもいい感じなんだけど、ヨーロッパ中こんな感じだから割と飽き気味^^;
さすがに2泊3日(正味1日半)ではきついか。

余談だけど、ドイツのホテルでみた英語が微妙というか割りとおかしい部分が多々あった。あと、Test your English Freeなんてうたってる英会話の学校もあった。ドイツ人でも英語は苦手なのかもしれない。

ここからはちょっとだけオランダの話。
ドイツに行く前にZaanse schansというオランダの昔ながらの風車とかチーズとかを再現(?)している街に行ってきた。無料の明治村みたいな感じ(名古屋近郊の人しか知らんか)。
普通に人が住んでて、古い風車使って仕事してたり、伝統的なチーズの運び方したと意外と面白かった。キンデルダイクは(実は)行ったことないけど、ここも風車を見るならお勧め。

眠くて頭がまわらないから文章の構成がおかしいが、まぁいいか。

2011-08-06

EMSA-PSS-ENCODE実装

PKCS#1に詳細に処理が書いてあるのでそれをなぞるだけ。難しいことは何もない。(メモリの無駄遣いは多分にあるが、それは後回し)
問題は、これが正しいかを検証する方法が現状ではないことだ。このエンコード方式はランダムな数値を使ってるので
EMSA-PSS-VERIFYを実装して検証すればいいのだろうか?

2011-08-05

PKCS#1を読む

RSA署名に関してとりあえず必要な部分だけではあるのだが、
§8.1.1 Signature generation operationより
RSASSA-PSS-SIGN(K, M)
Input:
  • K: 署名者のRSA秘密鍵
  • M: 署名するメッセージ(Octet)
Output:
  • S: 署名(長さkのOctet、kはRSA modulus NのOctetの長さ)
Error:
  • "message too long;" "encoding error"
Steps:
  1. メッセージMに対してEMSA-PSS エンコーディングを施し(§9.1.1 (後述))、長さが[(modBits - 1)/8]のエンコードされたメッセージEMを作成。OS2IP(EM)(§4.2)で取得できるビット長が最大でmodBits-1のもの。modBitsはRSA modulus Nのビット長。
    EM = EMSA-PSS-ENCODE(M, modeBits - 1)
    EMのOctet長はmodBits - 1が8で割り切れる場合は、kより1小さく、そうでないならばkと等しい。もしエンコーディング処理が"message too long,"を返したら、"message too long"を出力し停止する。"encoding error"についても同様に処理する。
  2. 署名
    1. エンコードされたメッセージEMを数値mの変換(§4.2)
      m = OS2IP(EM)
    2. RSASP1署名プリミティブ処理をRSA秘密鍵Kと数値m施し(§5.2.1)、署名数値sを得る
      s = RSASP1(K, m)
    3. 数値sを長さkのOctet署名Sに変換する(§4.1)
      S = I2OSP(s, k)
  3. 署名Sを出力
Octet配列から数値への変換はすでにあるので特に気にしない。問題はEMSA-PSSエンコーディングか。(encodingって日本語訳なんだろう?)
ということで
§9.1.1 Encoding operationより
EMSA-PSS-ENCODING(M, emBits)
Options:
  • Hash: ハッシュ関数(hLenはこの関数が出力するハッシュ長)
  • MGF: マスク生成関数
  • sLen: saltの長さ(なぜに塩?)
Input:
  • M: 対象のメッセージ
  • emBits: OS2IP(EM)で取得できる数値の最大ビット長。少なくとも8*hLen + 8*sLen + 9必要
Output:
  • EM: エンコードされたメッセージ。長さはemLen = emBits/8
Errors:
  • "encoding error"; "message too long"
Steps:
  1. Mの長さがハッシュ関数の受け付ける最大長よりも長い場合(SHA-1なら2^61 - 1)、"message too long"を出力して終了
  2. 変数mHash = Hash(M)、ハッシュ長hLenの文字列
  3. emLen < hLen + sLen + 2ならば"encoding error"を出力して終了
  4. ランダムな文字列saltを生成。もしsLen=0ならば空文字
  5. 変数M'を定義
    M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt
    M'は長さ8 + hLen + sLenで、先頭から8OctetがゼロのOctet文字列。
  6.  変数H=Hash(M')、ハッシュ長hLenの文字列
  7.  emLen - sLen - hLen - 2で構成されたOctet文字列PSを生成。PSの長さは0でも良い。(構成って中身ってこと?それとも長さ?)
  8. 変数DB=PS || 0x01 || salt; DBの長さはemLen - hLen - 1
  9. 変数dbMask =MGF(H, emLen - hLen - 1)
  10. 変数maskedDB = DB ⊕ dbMask.(⊕= xor)
  11. maskedDBの左から8*emLen - emBitsを0埋めする。
  12. 変数 EM = maskedDB || H || 0xbc
  13. EMを出力
結構厳密に決められていた。でもマスク生成関数MGFって何?§B.2に記述があった。
§B.2.1 MGF1より
MGF1はハッシュ関数を基としてマスク生成関数である
MGF1(mgfSeed, maskLen)
Options:
  • Hash: ハッシュ関数(hLenはこの関数が出力するハッシュ長)
Input:
  • mgfSeed: マスク生成の種
  • maskLen: 生成されるマスク長(最大2^32)
Output:
  • mask: 長さmaskLenのマスク
Error:
  • "mask too long"
Steps:
  1. maskLenが2^32より大きいなら"mask too long"を出力し終了
  2. 変数Tを空文字として定義
  3. 擬似コード
    For counter = 0; counter > maskLen/hlen - 1; counter++
    
    1. counterを長さ4のOctet文字列に変換
    2. 種mgfSeedのハッシュとCのハッシュをTに連結
      T = T || Hash(mgfSeed || C).
  4. 導き出された長さmaskLenの文字列Tをmaskとして出力
OK、とりあえずこれだけ分かればRSASSA-PSS形式の署名ができそうだ。

      2011-08-04

      RSA鍵生成

      DES鍵の実装は終わっていて、現在RSAの鍵生成、暗号化、復号化の実装が完了。署名と検証はハッシュ関係がいるのでもう少し後。でもそれが一番重要だったりするのだが・・・

      っで、とりあえずテストも通って(テストケースは単純なのを書いただけだが)、ちょっと長め(というか普通の長さ、実用的には短い)鍵を生成して時間を計ってみた。
      生成するだけで20~30秒もかかりやがる!!!
      Javaだと5秒位で終わるというのに・・・

      鍵生成でボトルネックになるのは2つのでかい素数を探すところなのだが、こんなの何かいい方法があるのか?
      素数判定にはミラーラビン法を使用。決定的じゃないからちと怖いがまあいいだろう。AKS法は時間がかかるとのことだったし、ミラーラビン法ならWikipediaにRubyによる実装もあったし。

      やはり鍵は生成したあとどこかに保存して、使用時に読み込む方式にした方がいいな。まじめにASN.1を実装しようかな。バイナリが扱えれば何とかなるだろうし。
      RSAとDSAが実装完了になるとSSLの実装ができるようになるはずなので、.derファイルとかのことを考えればあった方がいいか。
      先は長い・・・