Hatena::ブログ(Diary)

hnwの日記 このページをアンテナに追加 RSSフィード

[プロフィール]
 

2014年7月5日(土) GitHubユーザーのSSH鍵6万個を調べてみた このエントリーを含むブックマーク このエントリーのブックマークコメント

GitHub APIを利用して、GitHubの31661アカウントに登録されているSSH公開鍵64404個を取得してみました。抽出方法*1が適当すぎて偏りがあるような気もしますが、面白い結果が得られたと思うのでまとめてみます。

SSH鍵の種類

鍵の種類 個数 割合
RSA 61749 (95.88%)
DSA鍵 2647 (4.11%)
ECDSA鍵 8 (0.01%)

約6万個の鍵のうち、8個だけECDSA(楕円DSA)鍵が見つかりました!常用しているのか試しに登録してみただけなのかはわかりませんが、何にせよ意識高い感じでステキですね。


SSH鍵のbit長

RSA
鍵長 個数 割合
800bit 1 (0.00%)
1024bit 2034 (3.29%)
1026-2046bit 15 (0.02%)
2048bit 58773 (95.18%)
2050-4094bit 25 (0.04%)
4096bit 827 (1.34%)
4098bit- 74 (0.12%)

2048bit鍵が多数派という結果になりました。これは多くのSSH実装がデフォルトで生成する鍵長だと思うので、当然の結果ではあります。


1024bit鍵の人もボチボチ見つかります。最短の鍵長はなんと800bitでした。あとで触れますがよろしくないですね。

続きを読む

*1GitHubのユーザID1番から1万番、100万番から101万番、…800万番から801万番の人のうちSSH鍵を登録している人の全ての公開鍵を先月末に取得しました

matokenmatoken 2014/07/07 21:26 2/10に試した時はECDSA(ecdsa-sha2-nistp256)は弾かれてしまいました><
なので多分GitHubがECDSAに対応したのが最近でそのため登録者が少ないのではないかと思います.
現在もed25519はダメですね

hnwhnw 2014/07/08 08:20 なるほど、そんな最近に対応したんですね。てっきり保守的な人が多いのかと思ってました。Ed25519鍵への対応も待たれますね。

2014年6月29日(日) Console Componentを利用したメモ このエントリーを含むブックマーク このエントリーのブックマークコメント

Console Componentを使った感想を記録しておきます。雑なメモですが、どなたかの参考になれば。


Console Componentとは

Console ComponentはPHPコマンドラインアプリケーションライブラリです。コマンドラインオプション解析や、出力に簡単に色をつける機能などを提供しています。


ちなみに、このライブラリSymfony Componentsに含まれています。SymfonyPHPの有名フレームワークですが、多くの機能をスタンドアロンライブラリとして切り出しています。Console Componentもその一つということになります。


コマンドラインオプション解析ライブラリとしての特徴

  • 標準的なコマンドラインオプションに対応している
    • short option/long option両対応
    • 値を取らないshort optionを圧縮して指定できる(-v -a -xを-vaxと指定できる)
    • オプションが値を取らない/値が必須/値を指定してもしなくても良い/複数指定できるに対応
  • サブコマンドに対応している
  • ヘルプメッセージ(--helpで出力される内容)を勝手に作ってくれる
  • テストが書きやすい

イマイチな点

  • コマンドラインオプション解析だけしたい場合には巨大かつ冗長
    • 必ずCommandクラスを継承したクラスを作らなくてはならない
  • サブコマンド無しのコマンドが標準では作れない
    • 単機能のツールを作る場合でも必ずサブコマンド指定をさせることになる
  • --with-foo,--without-fooのようなオプション指定に標準で対応していない
    • 他言語の同等ライブラリでは真偽値を返してくれるものがあって便利
  • 値を取るオプションの場合に、型の指定ができない

上記のうちいくつかは簡単に対応できそうな気もしていますが、「巨大かつ冗長」はどうにもならんと思います。


サンプルコード

以下、Commandクラスを継承したクラスの例です。これをApplicationクラスからadd()で登録して使います。

続きを読む

トラックバック - http://d.hatena.ne.jp/hnw/20140629

2014年6月10日(火) RSA鍵の生成時に確率的素数判定法を使って問題ないのか このエントリーを含むブックマーク このエントリーのブックマークコメント

前回記事「RSA公開鍵から素数の積を取り出す方法」でも紹介しましたが、RSA鍵の生成には巨大な2つの素数p,qが必要です。近年一般的に使われている2048bit鍵の場合なら、p,qの大きさは1024bit、10進で約308桁の数になります。


このRSAアルゴリズム中ではpとqを法としたフェルマーの小定理(正確にはその拡張であるオイラーの定理)を利用しています。つまり、pとqが合成数だとRSA暗号の大前提が狂ってしまいますので、pとqには確実に素数を選ぶ必要があります。


ところで、OpenSSLRSA鍵生成の実装では、pとqの素数判定にMiller-Rabin素数判定法を用いています。Miller-Rabin素数判定法は片側誤りの確率的アルゴリズムで、「たぶん素数」「確実に合成数」の判定ができるようなものです。pとqの素数性が重要なのに、その判定に確率的アルゴリズムを使っても問題ないのでしょうか?


合成数のp,qでRSA鍵を作ってみる

ものは試しで、合成数のp,qでRSA鍵を作ってみましょう。OpenSSLRSA鍵生成の実体はbn_prime.cのBN_generate_prime_ex関数にあります。

続きを読む

トラックバック - http://d.hatena.ne.jp/hnw/20140610

2014年5月17日(土) RSA公開鍵から素数の積を取り出す方法 このエントリーを含むブックマーク このエントリーのブックマークコメント

RSA暗号HTTPSSSHの通信で利用されている暗号化方式です。公開鍵として巨大な素数の積を交換しあって暗号に利用しており、この素因数分解が困難であることにより安全性が担保されています。このことは教科書にも載っているような内容で、ご存じの方も多いかと思います。


ところで、その素数の積を実際に見たことってありますか?少なくとも僕は見たことがありませんでしたし、大抵の人は見たことが無いのではないでしょうか。本稿ではこの公開鍵の情報を見る方法を紹介します。


OpenSSH公開鍵の中身を見る

まずはOpenSSHの公開鍵の情報を取り出してみます。OpenSSHの公開鍵は次のようなものです。

続きを読む

人はいずれ死ぬ人はいずれ死ぬ 2014/05/18 04:16 Miller-Rabin素数判定法は確率的判定法なので,「確実に合成数です」はちょっといい過ぎかと思います.

甕星亭主人甕星亭主人 2014/05/18 07:06  言い切ちゃう処が工学的かと。 Wikiを覗いたけど、元はFermatの定理なんだから素数候補を探すにゃ役に立ちそうな判定法ですね。尤も特定の型の素数しか興味は湧か無いけれど。 Hardyが識ったら絶望で自殺しそうな方法論だなあ。

hogehoge 2014/05/18 07:58 >人はいずれ死ぬ
Miller-Rabin素数判定法は片側誤りアルゴリズムですから「合成数だ」と言われたら確実に合成数のはずですよ

hnwhnw 2014/05/18 08:41 人はいずれ死ぬさん、甕星亭主人さん、hogeさん:
コメントありがとうございます。
内容についてはhogeさんのおっしゃる通りで、
アルゴリズムとして確実だと伝えたかったんですが、
僕の日本語力と知識が足りなかったようです。
乱択アルゴリズムの分類に片側誤りと両側誤りというのがあるんですね。
今後は「片側誤りなので」と書きたいと思います。

甕星亭主人甕星亭主人 2014/05/18 08:45  然うですね。 此のtestは素数候補の中から、赤裸様な合成数を除外する為の物ですから、必然的に撥ねられた物は合成数と成りますね。 因数の素性情報としては役立た無いにしても。 失礼しました。

Glass_sagaGlass_saga 2014/05/18 15:23 合成数である事の判定にはopenssl primeコマンドも便利です。

openssl prime -hex B0F977574AB8...
を実行すると
B0F977574AB8417... is not prime
と返ってきます。

hnwhnw 2014/05/18 16:26 Glass_sagaさん:
コメントありがとうございます。
こんなサブコマンドがあるんですね!知りませんでした。
やはり中身はMiller-Rabinのようで、
openssl prime -checks 1 3825123056546413051
など意地悪な例を試すと時々「is prime」と誤判定しますね。

2014年5月3日(土) 平方数かどうかを高速に判定する方法 このエントリーを含むブックマーク このエントリーのブックマークコメント

平方数とは、ある整数の平方(=二乗)であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。


ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。


<?php
function is_square($n)
{
    $sqrt = floor(sqrt($n));
    return ($sqrt*$sqrt == $n);
}

しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。


多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します(PHPでもgmp_perfect_square関数として利用できます)。本稿ではこの実装で使われている工夫を紹介します。

続きを読む

甕星亭主人甕星亭主人 2014/05/03 20:22 相互法則を使うと却って速度が落ちるのでしょうかね?

甕星亭主人甕星亭主人 2014/05/04 01:04 PS  まとめで奇数がmod.8 で剰余が1で無けりゃ非平方数とすべきでは?

hnwhnw 2014/05/04 07:56 甕星亭主人さん:
コメントありがとうございます。

1つめのコメントはGNU MPの実装に関する内容だと思うのですが、mod 5,7,13,17などをバラバラに計算しない方が高速なのではないか、というご指摘でしょうか。これは、説明上分けて書いたもので、実装としてはmod 91やmod 85など適宜組み合わせて行っています。ご指摘とズレた回答でしたらごめんなさい。

2つめのコメントについては、mod 4でさえ50%の非平方数を判定できるという豆知識を伝えたかっただけで、特にmod 4をオススメするような意図はありませんでした。結局、mod pとして何を選ぶかは状況次第なのかなと考えています。平方根が十分速い環境であればいきなり平方根を求めた方が有利な可能性さえありますし、GNU MPのように平方根が相対的に遅い状況であればmodを何度も取るのが最適解かもしれません。modを1回だけ取るのであれば、mod 32(判定率78.2%)やmod 48(同83.4%)が候補になりうるかと思いますが、言語によっては効率よく実装できないかもしれません。解きたい問題と環境ごとにベンチマークテストを経て決めることなのかなと考えています。

甕星亭主人甕星亭主人 2014/05/04 09:08  確かに、余程大きな数で無ければ平方剰余の相互法則は力を発揮せぬかも知れません。御教示有難う御座いました。

kun4kun4 2014/05/04 10:24 興味深いお話でした ありがとうございます

お尋ねします
>奇素数pについて考えると盤面のマス目の総数はp-1と必ず偶数になり、一方で平方数は偶数マス目になるわけですから

という箇所なのですが、偶数マス目の一部ではなく必ず全ての偶数マス目に及ぶわけですよね

hnwhnw 2014/05/04 12:39 kun4さん:
はい、その通りです。マス目のたとえで言うと、平方根はどのマス目でもよいので、その平方は全ての偶数マス目になりえます。

ご指摘の通り、元の文章は厳密さを欠いていると感じたので、引用部付近の文章を書き直してみました。ありがとうございます。

トラックバック - http://d.hatena.ne.jp/hnw/20140503
 
ページビュー
1110166