2010/04/10

再帰 継続 末尾

再帰なら継続渡しで書き直して末尾再帰にできるヨ!!
そんなことを耳にしていたんですが
どうも継続というものが良く分かっていません
まぁ、関数渡すらしいな、程度の認識

再帰といえば fold なわけですが
Haskell だと foldr、OCaml だと List.fold_right です
まぁ、何でもいいんですが
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
とか
let fold_right f lst init = match lst with
| [] -> init
| x::xs -> f x (fold_right f xs init)
とかそういうのです
要するに
fold [] = v
fold (x:xs) = f x (fold xs)
みたいなことになってればいいんです

で、これ末尾再帰にはなってないわけですよ
することに意味があるかは知らないんですよ
したいんですよ、末尾再帰に
できないんですよ、まだ継続とか関数渡すとかの理解浅いから

ぐぐりました
反復的プロセス、末尾再帰、継続渡しスタイル : torus solutions!
append が末尾再帰の刑に処せられていますがまぁ fold も同じようなもんです

fold f v [] k = k v
fold f v (x:xs) k = fold f v xs (\y -> k (f x y))

let rec fold f lst v k = match lst with
| [] -> k v
| (x::xs) -> fold f xs v (fun y -> k (f x y))
でもね、
continuation(継続)は末尾再帰の最適化手段ではない : メカAG
飽くまで「継続を使うと再帰が末尾再帰に直せる」というだけなので
このままでは「継続」の入口にも立っていないのでした

付録:

で fold には left もありましてこっちは最初から末尾再帰でしたが
(最近 Haskell ご無沙汰なので Haskell だけにしよう、もぉ面倒だ)
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
こんなだったか
これは例えば
foldl (+) 0 [1,2,3]
= (((0+1)+2)+3)
= (\k -> k.(+1)) ((\k -> k.(+2)) (+3)) 0
= (\x k -> k.(+x)) 1 ((\x k -> k.(+x)) 2 (+3)) 0
= (\x k -> (\y -> k (y+x))) 1 ((\x k -> (\y -> k (y+x))) 2 (\x k -> (\y -> (y+x))) 3 id) 0
= (foldr (\x k -> (\y -> k ((+) y x))) id [1,2,3]) 0
ははは、欺瞞にも程がある
でもまぁ
foldl f v lst = (foldr (\x k -> (\y -> k (f y x))) id lst) v
と書けないこともないということで
何が嬉しいのかは分かりません

2010/04/05

openssl 接続 bio

SSL で証明書を取ってくるシリーズ
今回は何と C with OpenSSL
C なんて学部の頃に「独習 C」を友達に薦められ
読んだというか眺めた憶えはありますがそれっきりで
一生のうちで使うことは無かろうかと思っていたのですが

で、OpenSSL の各種 binding は散々いじってるので
  1. socket 用意する
  2. SSL Centext 用意する
  3. socket と Context で SSL 作る
  4. 繋ぎにいって証明書もらう
というのは分かっちゃいるんですが
そもそも C で socket 叩いたことないよボク!!

というわけでググるわけです
良い sample code でも無いものかと探してみました

OpenSSLライブラリを使ってプログラミング(1) - 再帰の反復
このページは OpenSSL や SSL に関する詳しいまとめが
Geekなぺーじ : getaddrinfo(単純な例)
getaddrinfo の使い方とか socket の張り方とか

で、ついでなんで getopt とか構造体のこともググりながら
どうにかとりあえず動くものは作れました。
でもあれだからね、素人が作ったからどこに穴があるか分からないからね。
#include <stdio.h>
#include <getopt.h>
#include <sys/socket.h>
#include <netdb.h>
#include <openssl/ssl.h>

typedef struct {
unsigned char *data;
int length;
} der_data;

char* x509_as_pem(X509 *x509) {
BIO *bio;
BUF_MEM *bptr;

bio = BIO_new(BIO_s_mem());
PEM_write_bio_X509(bio, x509);
bptr = BUF_MEM_new();
BIO_get_mem_ptr(bio, &bptr);

return bptr->data;
}

der_data* x509_as_der(X509 *x509) {
int len;
int i;
unsigned char *buf, *p;
der_data *data;

len = i2d_X509(x509, NULL);
buf = OPENSSL_malloc(len);
if (buf == NULL) {
printf("error\n");
exit(1);
}
p = buf;
i2d_X509(x509, &p);

data = (der_data *)malloc( sizeof(der_data) );
data->data = buf;
data->length = len;
return data;
}

int main(int argc, char *argv[]) {

int der = 0;
int c, s;
char *cmd = argv[0];

struct hostent *host;
char *service = "443";
struct addrinfo hints;
struct addrinfo *result;
int fd;

SSL_CTX *ctx;
SSL *ssl;
int ret;
X509 *x509;
BIO *bio;

void help() {
fprintf(stderr, "usage: %s [-d] hostname\n", cmd);
exit(1);
}

while ((c = getopt(argc, argv, ":d")) != -1) {
switch (c) {
case 'd':
der = 1;
break;
case '?':
help();
}
}
argc -= optind;
argv += optind;
if (argc < 1) {
help();
}

memset(&hints, 0, sizeof(struct addrinfo));
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if ((s = getaddrinfo(argv[0], service, &hints, &result)) != 0) {
printf("error %d : %s\n", s, gai_strerror(s));
exit(1);
}

fd = socket(result->ai_family, result->ai_socktype, result->ai_protocol);
if (fd < 0) {
perror("open socket error");
exit(1);
}

if (connect(fd, result->ai_addr, result->ai_addrlen) != 0) {
perror("connection error");
return 1;
}

free(result);

SSL_load_error_strings();
SSL_library_init();

ctx = SSL_CTX_new(SSLv23_method());
if ( ctx == NULL ){
ERR_print_errors_fp(stderr);
exit(1);
}

ssl = SSL_new(ctx);
if ( ssl == NULL ){
ERR_print_errors_fp(stderr);
exit(1);
}

ret = SSL_set_fd(ssl, fd);
if ( ret == 0 ){
ERR_print_errors_fp(stderr);
exit(1);
}

ret = SSL_connect(ssl);
if ( ret != 1 ){
ERR_print_errors_fp(stderr);
exit(1);
}

x509 = SSL_get_peer_certificate(ssl);
if (x509 == NULL) {
ERR_print_errors_fp(stderr);
exit(1);
}

if (der == 0) {
char *data;
data = x509_as_pem(x509);
printf("%s", data);
} else {
der_data *data;
int i;

data = x509_as_der(x509);
for (i=0; i < data->length; i++) {
printf("%c", (data->data)[i]);
}
}

return 0;
}
セキュリティーとか何も考えてないというか
セキュリティーの考え方を知らないので
それは誰か教えてくれると嬉しいヨ!!

で、
$ gcc -lssl -o get_cert get_cert.c 
$ ./get_cert www.google.com
-----BEGIN CERTIFICATE-----
MIIDITCCAoqgAwIBAgIQL9+89q6RUm0PmqPfQDQ+mjANBgkqhkiG9w0BAQUFADBM
MQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkg
THRkLjEWMBQGA1UEAxMNVGhhd3RlIFNHQyBDQTAeFw0wOTEyMTgwMDAwMDBaFw0x
MTEyMTgyMzU5NTlaMGgxCzAJBgNVBAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlh
MRYwFAYDVQQHFA1Nb3VudGFpbiBWaWV3MRMwEQYDVQQKFApHb29nbGUgSW5jMRcw
FQYDVQQDFA53d3cuZ29vZ2xlLmNvbTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkC
gYEA6PmGD5D6htffvXImttdEAoN4c9kCKO+IRTn7EOh8rqk41XXGOOsKFQebg+jN
gtXj9xVoRaELGYW84u+E593y17iYwqG7tcFR39SDAqc9BkJb4SLD3muFXxzW2k6L
05vuuWciKh0R73mkszeK9P4Y/bz5RiNQl/Os/CRGK1w7t0UCAwEAAaOB5zCB5DAM
BgNVHRMBAf8EAjAAMDYGA1UdHwQvMC0wK6ApoCeGJWh0dHA6Ly9jcmwudGhhd3Rl
LmNvbS9UaGF3dGVTR0NDQS5jcmwwKAYDVR0lBCEwHwYIKwYBBQUHAwEGCCsGAQUF
BwMCBglghkgBhvhCBAEwcgYIKwYBBQUHAQEEZjBkMCIGCCsGAQUFBzABhhZodHRw
Oi8vb2NzcC50aGF3dGUuY29tMD4GCCsGAQUFBzAChjJodHRwOi8vd3d3LnRoYXd0
ZS5jb20vcmVwb3NpdG9yeS9UaGF3dGVfU0dDX0NBLmNydDANBgkqhkiG9w0BAQUF
AAOBgQCfQ89bxFApsb/isJr/aiEdLRLDLE5a+RLizrmCUi3nHX4adpaQedEkUjh5
u2ONgJd8IyAPkU0Wueru9G2Jysa9zCRo1kNbzipYvzwY4OA8Ys+WAi0oR1A04Se6
z5nRUP8pJcA2NhUzUnC+MY+f6H/nEQyNv4SgQhqAibAxWEEHXw==
-----END CERTIFICATE-----
$ ./get_cert -d www.google.com | od -t x1
0000000 30 82 03 21 30 82 02 8a a0 03 02 01 02 02 10 2f
0000020 df bc f6 ae 91 52 6d 0f 9a a3 df 40 34 3e 9a 30
0000040 0d 06 09 2a 86 48 86 f7 0d 01 01 05 05 00 30 4c
0000060 31 0b 30 09 06 03 55 04 06 13 02 5a 41 31 25 30
0000100 23 06 03 55 04 0a 13 1c 54 68 61 77 74 65 20 43
0000120 6f 6e 73 75 6c 74 69 6e 67 20 28 50 74 79 29 20
0000140 4c 74 64 2e 31 16 30 14 06 03 55 04 03 13 0d 54
0000160 68 61 77 74 65 20 53 47 43 20 43 41 30 1e 17 0d
0000200 30 39 31 32 31 38 30 30 30 30 30 30 5a 17 0d 31
0000220 31 31 32 31 38 32 33 35 39 35 39 5a 30 68 31 0b
0000240 30 09 06 03 55 04 06 13 02 55 53 31 13 30 11 06
0000260 03 55 04 08 13 0a 43 61 6c 69 66 6f 72 6e 69 61
0000300 31 16 30 14 06 03 55 04 07 14 0d 4d 6f 75 6e 74
0000320 61 69 6e 20 56 69 65 77 31 13 30 11 06 03 55 04
0000340 0a 14 0a 47 6f 6f 67 6c 65 20 49 6e 63 31 17 30
0000360 15 06 03 55 04 03 14 0e 77 77 77 2e 67 6f 6f 67
0000400 6c 65 2e 63 6f 6d 30 81 9f 30 0d 06 09 2a 86 48
0000420 86 f7 0d 01 01 01 05 00 03 81 8d 00 30 81 89 02
0000440 81 81 00 e8 f9 86 0f 90 fa 86 d7 df bd 72 26 b6
0000460 d7 44 02 83 78 73 d9 02 28 ef 88 45 39 fb 10 e8
0000500 7c ae a9 38 d5 75 c6 38 eb 0a 15 07 9b 83 e8 cd
0000520 82 d5 e3 f7 15 68 45 a1 0b 19 85 bc e2 ef 84 e7
0000540 dd f2 d7 b8 98 c2 a1 bb b5 c1 51 df d4 83 02 a7
0000560 3d 06 42 5b e1 22 c3 de 6b 85 5f 1c d6 da 4e 8b
0000600 d3 9b ee b9 67 22 2a 1d 11 ef 79 a4 b3 37 8a f4
0000620 fe 18 fd bc f9 46 23 50 97 f3 ac fc 24 46 2b 5c
0000640 3b b7 45 02 03 01 00 01 a3 81 e7 30 81 e4 30 0c
0000660 06 03 55 1d 13 01 01 ff 04 02 30 00 30 36 06 03
0000700 55 1d 1f 04 2f 30 2d 30 2b a0 29 a0 27 86 25 68
0000720 74 74 70 3a 2f 2f 63 72 6c 2e 74 68 61 77 74 65
0000740 2e 63 6f 6d 2f 54 68 61 77 74 65 53 47 43 43 41
0000760 2e 63 72 6c 30 28 06 03 55 1d 25 04 21 30 1f 06
0001000 08 2b 06 01 05 05 07 03 01 06 08 2b 06 01 05 05
0001020 07 03 02 06 09 60 86 48 01 86 f8 42 04 01 30 72
0001040 06 08 2b 06 01 05 05 07 01 01 04 66 30 64 30 22
0001060 06 08 2b 06 01 05 05 07 30 01 86 16 68 74 74 70
0001100 3a 2f 2f 6f 63 73 70 2e 74 68 61 77 74 65 2e 63
0001120 6f 6d 30 3e 06 08 2b 06 01 05 05 07 30 02 86 32
0001140 68 74 74 70 3a 2f 2f 77 77 77 2e 74 68 61 77 74
0001160 65 2e 63 6f 6d 2f 72 65 70 6f 73 69 74 6f 72 79
0001200 2f 54 68 61 77 74 65 5f 53 47 43 5f 43 41 2e 63
0001220 72 74 30 0d 06 09 2a 86 48 86 f7 0d 01 01 05 05
0001240 00 03 81 81 00 9f 43 cf 5b c4 50 29 b1 bf e2 b0
0001260 9a ff 6a 21 1d 2d 12 c3 2c 4e 5a f9 12 e2 ce b9
0001300 82 52 2d e7 1d 7e 1a 76 96 90 79 d1 24 52 38 79
0001320 bb 63 8d 80 97 7c 23 20 0f 91 4d 16 b9 ea ee f4
0001340 6d 89 ca c6 bd cc 24 68 d6 43 5b ce 2a 58 bf 3c
0001360 18 e0 e0 3c 62 cf 96 02 2d 28 47 50 34 e1 27 ba
0001400 cf 99 d1 50 ff 29 25 c0 36 36 15 33 52 70 be 31
0001420 8f 9f e8 7f e7 11 0c 8d bf 84 a0 42 1a 80 89 b0
0001440 31 58 41 07 5f
0001445
$
という感じに der とか pem とかで取れるようになりました。

openssl s_client の劣化版じゃん!!
や、そうなんですけどね。

ocaml ssl

SSL で繋いで証明書を取ってこようシリーズ
今回は OCaml でいってみようと思います
OCaml に関してはプログラミング in OCaml など見ると良いのかも

とりあえずググりますと
http://sourceforge.net/projects/savonet/files/ocaml-ssl/
こちらに OpenSSL の binding があったのでこれを使おうかと思いまして
っていうかね、
OCamlで簡易SSLクライアント - komamitsu.log
こんな素敵なまとめページが見つかってしまいました

OCaml-SSL をインストールしようとすると
「findlib が無いよ」
って言われたので findlib から入れました
で、使い方は上記ページを参考にしつつ試して動いた感じです

OCaml-SSL のソースをザザっと眺めてみたんですが
証明書をいじる関数があまり用意されていないらしく
というか subject と issuer を抜くものしかありませんでした
あらら

とりあえず minimal かと思われる証明書取ってくるのがこれ
open Unix;;

Ssl.init ();;
let hostent = gethostbyname "www.google.com";;
let addr = hostent.h_addr_list.(0);;
let sockaddr = ADDR_INET(addr, 443);;

let sock = Ssl.open_connection Ssl.SSLv23 (ADDR_INET(addr, 443));;
let cert = Ssl.get_certificate sock;;
Printf.printf "%s%!" (Ssl.get_subject cert)
っていうか何というコード
変数に欲しいもの列記して実行してるだけです
って OpenSSL をいじってるわけだから仕方ないのかな?

でまぁこんなのを show_subject.ml として用意して
ocamlfind c -package ssl -thread -linkpkg -o show_subject show_subject.ml
と打つとコマンドができました

findlib っていうのがあるのだというのを知ったのが
今回の最大の成果となっております