Chienomi

パスワード生成器 (初級プログラミング)

初級プログラミングの記事への要望が非常に高い。

それに応えずにいるのは、いくつか理由がある。

最大の理由は労力に見合わない、ということだ。 初級プログラミングの要望は、実は 要望が多いのに、実際に書くと読まれない

あと、初級プログラマが本当に有効な知識を説明しようとしても、やっぱり読まれない。 初級プログラミングの話は、非常に予定調和の要求が高くて、他のサイトや本に書いてあることとまるで同じようなことを書かないと読まれない。 それは最高に意味がないので、書く意義を見いだせない。

また、Chienomiはどちらかというとエッジなものを扱う考え方であるためあまりそぐわないということもあるのだが、 Mimir Yokohamaの記事で書こうとすると、コンテンツを学習として有効なコンテンツ群の一部として書く必要があるため執筆コストが非常に高く、 それでいてあまり読まれない上にプログラミング記事はプロモーション効果も薄いので非常に書きにくい。

ただ今回一応ではあるが、beginnersというカテゴリを作ったので、(記事が読まれれば)今後こうした初級者向け記事は増えていくかもしれない。

ただし、Mimir Yokohamaでは「すべての固有概念は一度は説明される」が、Chienomi的には一般的な用語の説明などはあまりしない。 意味を正しく理解していなくても、文脈から読み取ることが可能であるはずだからだ。

概要

ウェブサービスやログインなど様々な場面で実に多くのパスワードが要求される。

もちろん、 同じパスワードを使い回すなどということは極めて脆弱な行いでやってはならない し、毎回十分なエントロピーをもったパスワードを作るのは骨が折れる。 Linuxではパスワードを生成するプログラムはいくつかあるが、比較的大きなプログラムの一部だったり、エントロピーに不満があったり、なんらかの不満があったので作ってみた。

ここで紹介するコードは、一度作ったあと、この記事のために説明的に書き直したものだ。

See into code.

Code

Gist

#!/usr/bin/ruby
# -*- mode: ruby; coding: utf-8 -*-

pwlength = ARGV.shift&.to_i || 64
pwlength = 64 if pwlength < 1

converter_symbols = ARGV.shift&.each_char

converter = converter_symbols ? ("a" .. "z").to_a + ("A" .. "Z").to_a + ("0" .. "9").to_a +  converter_symbols : ('!' .. '~').to_a

convloops = 255 / converter.length
convlength = converter.length * convloops

File.open("/dev/urandom", "r") do |f|
  pwlength.times do |i|
    c = f.readbyte
    redo if c >= convlength
    print(converter[c % converter.length])
  end
end

解説

shebang

#!/usr/bin/ruby

Shebang行である。

今回は初回なので、ここも説明しておこう。

Unixシステムにおいては「実行可能なテキストファイル」を実行するとき、その一行目を読んでそのテキストファイルを解釈させるプログラムを決定する。

これはシステム自体が持っている機能であり、シェルが持っている機能ではないが、シェルもそのような機能を持っている可能性がある。 シェルがその機能を持っている場合は、実行した場合に「システムに対してそのプログラムを実行する」という振る舞いではなく、「引数としてそのファイルを渡す」という振る舞いになるから、システムのその機能に頼ることはない。 実はperl(1)が同様の機能を持っており、perl(1)はPerlでないshebangを持つスクリプトを起動できる。

この場合、shebangは#!/usr/bin/rubyであるから、これが~/bin/mkpwd.rbというファイルだとすれば

/usr/bin/ruby ~/bin/mkpwd.rb

という形式で起動されることを意味する。このため、shebang行には引数やオプションを含めることができる。

shabang行がない場合、システムはデフォルトのシェルに対する引数としてそのテキストファイルを渡す。

もちろん、これは「実行可能なテキストファイルを実行した場合」の振る舞いであり、このテキストファイルを引数として渡した場合には関係ない。 また、その場合にはそもそもこのテキストファイルが実行可能である(パーミッション的にexecutable flagを持っている)必要がない。

なお、この仕組みであるから起動された処理系はshebang行を含むテキストファイルをソースにすることがある。 多くのスクリプト処理系では#はコメントであるから、コメントとして読み飛ばすことができる。が、中には#がコメントになっていない処理系もある。 例えばLispとか…と言いたいところだが、clispsbclもちゃんとshebangは読み飛ばすようになっている。Luaも同様である。 理由は、もちろんそうでないと困るから。

ruby マジックコメント

# -*- mode: ruby; coding: utf-8 -*-

Shebang行につづいてRubyはマジックコメントを書くことができる。 これは、スクリプトエンコーディングを指定することができる。

# coding: utf-8

と書けばスクリプトエンコーディングがUTF-8で書かれていることを明示できる。 これが必要なのはRuby 1.9だけであり、Ruby 2.0からはUTF-8がデフォルトだが、明示することでいくつかのトラブルが回避できる可能性が示されている。

# -*- mode: ruby; coding: utf-8 -*-
```は

というのはEmacsの形式で、Emacsは`var: value`という形式で変数を指定できる。[(公式ドキュメント翻訳版)](https://ayatakesi.github.io/emacs/25.1/Specifying-File-Variables.html){rel="external"}
つまり、Emacsの変数として書いておきながらRubyはそれをうまく解釈する、ということである。

もちろんそれは`coding: utf-8`という文字列を含むから、と考えられるが、Rubyはvim形式で次のように書かれていたとしても

```ruby
# vim:set fileencoding=utf-8:

正しく認識する。これは、vimに対してUTF-8のファイルエンコーディングを明示するものだが、これを正しく解釈する。 なお、Vim自身Emacs形式で書かれているものもある程度解釈するようである。

ここでスクリプトエンコーディングを明示するのはそれほど重要なことではないが、文字の順序が影響するコードなので、ASCII非互換の文字集合だと解釈されると困る。 だから、ここでは別にus-asciiでも構わない。

パスワードの長さ

pwlength = ARGV.shift&.to_i || 64
pwlength = 64 if pwlength < 1

ARGVはコマンドライン引数オブジェクトである。ARGV.shiftで引数オブジェクトの先頭の値を削除し、このメソッドの返り値としてその値を返す。 ARGVArrayインスタンスであり、shiftというメソッドはArrayに属している。

Array#shiftは配列の長さが0である(つまりからっぽである)場合、nilを返す。 nilはRuby独特の言葉で1、一般的にはnullとかundefinedと呼ばれることが多い。

つまり、ARGV.shiftは潜在的には(コマンドライン引数を与えられていなければ)nilを返す。後続するメソッドが値が存在することを前提に進めるとエラーになる可能性がある。

&.というのはRubyの「ぼっち演算子」である。これはRuby 2.3から登場したものである。 このぼっち演算子は後続のメソッドを、レシーバ(この場合ARGV.shiftの結果)がnilでない場合だけ起動する。 レシーバがnilだった場合、メソッドは起動されることなくnilを返す。

つまり、引数があればそれをto_iによって整数化した結果がpwlengthとなるが、引数がなければnilになるので論理ORによって右辺64が代入される。

次行では1以下である場合、つまり、引数が0だったり-1だったり、hogehogeだったり(この場合.to_iすると0になる)する場合にデフォルト値にリセットしている。

この記述は説明的なもので、実は そもそもぼっち演算子が必要な状況ではない 。 なぜならば、nilが所属するNilClassには#to_iメソッドが存在し、なおかつ0を返すからだ。だから

pwlength = ARGV.shift.to_i
pwlength = 64 if pwlength < 1

で事足りる。私の好みとしてはこちらのほうがいい。 ただし、to_iが0以下を返すような引数を許さないのであれば扱いが違うため、

pwlength = ARGV.shift&.to_i || 64
if pwlength < 1
  abort "You must set password length as $1."
end

のように書くことになるからぼっち演算子が必要になる。

だが、今回の場合は「任意性のある2つの引数」をとるため、そのようなことはないはずだ。

記号集合の定義

converter_symbols = ARGV.shift&.each_char

converter_symbols変数はパスワードで使用される記号を定義している。Arrayインスタンスである。

ここで再びARGV.shiftが登場している。既に一度shiftしているから2番目の引数だ。 結果は、nilStringインスタンスである。

String#each_charはブロックを与えるかどうかで挙動が異なる。 ブロックを与えた場合、ブロック変数に対して1文字ずつ(1バイトではなく、エンコーディングで定義された1文字ずつである)代入しながらループする。 ブロクを与えなかった場合、Enumeratorインスタンスが返る。

Enumeratorクラスはイテレータクラスである。イテレータクラスは「反復可能なコレクション」のクラスである。 Ruby 1.8では標準ライブラリだったが、Ruby 1.9から組み込みになり、扱いも少し変わった。

例えば

[1, 2, 3].each do |i|
  puts i
end

というのは配列に対するイテレーションであり、eachメソッドがイテレータということになるのだが、配列は配列であって繰り返しのためだけに存在しているわけではない。 これを

enum = [1, 2, 3].each

とすると、enumEnumratorインスタンスとなり、繰り返しのための存在に変わる。

Enumratorクラスにする大きな理由は外部イテレータにすることである。例えば

arg1 = enum.next

のようにして1要素ずつ取り出して処理できる。 要素の1番目だけ扱いが違う、というような時に

enum = lines.each
title = enum.next
while i = enum.next
  #...
end

みたいなことができる。

もうひとつ、有用な用法が、「反復可能な要素を配列にできる」ことである。これは、Enumerator#to_aという配列化のメソッドがあり、反復される要素を配列にしたものになるからだ。 元要素が配列の場合は全く意味がないが、今回の場合文字列であるため、「1文字ずつ分離して配列にする」という簡単かつ速い方法になる。

ちなみに、他の方法としては

converter_symbols = ARGV.shift.split(/(.)/)

というやり方もあるが、こっちのほうがわかりにくいだろう。

候補文字配列

さて、ぼっち演算子を使用しているため、第2引数がなかった場合はeach_charされることなくnilを返す。

converter = converter_symbols ? ("a" .. "z").to_a + ("A" .. "Z").to_a + ("0" .. "9").to_a +  converter_symbols : ('!' .. '~').to_a

で三項演算子を使って、nilかどうかによって処理が分かれるようになっている。('!' .. '/')というのはRangeリテラルだ。

Rangeはそのまま、「範囲」を表すものであり、範囲に含まれているかどうかという判定ができたり、イテレータを利用可能であったりする。 この範囲はsuccというメソッドを使って作られるようになっており、左の要素をsuccしていって、右の要素になったら終了だ。 String#succは文字集合的に「次の文字」を返すようになっている。正確には、アルファベットはアルファベットで「次」を返すし、「数値の文字列」の場合は数値的な「次」を返すが。

だが、実際には

("A" .. "~")("A" .. "ZZ")も正しく動作するので、もうちょっと複雑かつ器用にこなしてくれる。

そして、!はASCIIにおける最初の記号、~は最後の記号である。 このあたりはシステムと文字エンコーディングに関する知識が必要になる。

そして、ASCIIを知っていれば ('!' .. '~')が「すべてのASCII可視文字」になることがわかるはずだ。この間にはアルファベットや数字が全て含まれている。 Range#to_arange.each.to_a的な結果を返す。だから、('!' .. '~').to_aですべてのASCII可視文字からなる配列が得られる。

左辺の場合はその方法でアルファベット、数字の文字列を作って指定された記号に連結している。

実はこれは書き方はかなり様々あるのだが、逆に「使用禁止する記号を指定する」形式だと

converter = ('!' .. '~').to_a ^ (ARGV.shift&.each_char || []).to_a

という方法でまとめて1行で書けたりする。 配列を集合として扱う方法があるのは比較的珍しい。

余剰の計算

convloops = 255 / converter.length
convlength = converter.length * convloops

これらは生成時に無駄が起きたり偏りが発生しないように調整するためのものだ。

1バイトの最大値は0xffであり、255である。 例えば候補文字が50あるとすると、

byte[converter % 50]

で50以上の値は出なくなる(%で商の余りであり、50以上は50で割れるので余りが50以上になることはない)のだが、これだと先頭の6つ(0から数えるから)だけ出る確率が上がる。 かといって、

next if 50 <= byte

とかやると50から255までの随分大きな範囲がスキップされることになってしまい、「ものすごくサイコロを振り直すランダム」みたいになる。

まず1行目で/によって割っているが、RubyにおいてInterger#/は余りを捨てる。 だから、255 / 505になる。 そして、50 * 5によって得られる250は正確にループ可能な最大数であり、配列としての最大インデックスは249である(0から始まるから)。 だから、250以上を割った余りは先頭から中途半端なところで終わるということがわかるので、

next if 250 <= byte

が最小の「振り直し」ということになる。

これを変数化したものである。

urandom

File.open("/dev/urandom", "r") do |f|
  #...
end

/dev/urandomはUnixシステムにある疑似乱数生成器である。 暗号論的擬似乱数生成器であり、ちゃんと安全なエントロピーを持っている。/dev/randomは真乱数生成器だが、パスワードに使える長さの乱数を得るのはものすごく大変なのでここでは/dev/urandomで十分。

/dev/urandomはLinux発祥だが、FreeBSD, OpenBSD, NetBSD, DragonflyBSD, Solaris, Mac OS Xといったデスクトップで一般的に使われるUnixシステムには備わっているので問題ないはずだ。 Windowsにはないが、そもそもWindowsには暗号論的擬似乱数生成器となるファイルというものがない。

このファイルから読み出すと暗号論的擬似乱数生成器によるランダムな内容が返ってくる。

これまたシステムに関する知識が必要な部分である。

出力

pwlength.times do |i|
  c = f.readbyte
  redo if c >= convlength
  print(converter[c % converter.length])
end

pwlength.timesでパスワードの長さ分だけ繰り返す。

c = f.readbyte

はurandomファイルから1バイトを読み出す。IO#readbyteは1バイトを読むのだが、返り値はその1バイトを数値で表したIntegerである。

redo if c >= convlength

先に出てきた通り、途中までで終わってしまう余りが出る部分の値である場合はやり直す。ここでnextでループを繰り返してしまうと文字数が減ってしまうのでredoでこのループをやり直す。 ループをやり直しても新たに1バイトを読むようになっている(f.readbyteをもう一度通過する)から問題ない。

print(converter[c % converter.length])

これも先に出てきた通りで、cがちゃんとすべての文字で公平な分配になる数であることが前行で保証されているので、配列の長さで割った余りを求めれば配列の添字として使える数だけが返る。 c/dev/urandomで得たランダムな値であるから結果的には候補文字のうちランダムな1文字が出力される。

なお、

pwlength.times do |i|
  c = Random.rand convlength
  print(converter[c % converter.length])
end

と書けば/dev/urandomを使わない(Windowsでも動作する)実装に変更できるが、 Random#randが使う乱数生成器はメルセンヌ・ツイスタであり、暗号論的擬似乱数生成器ではない ので、エントロピーが下がる。 (暗号鍵としては十分でないが、パスワードとして十分かどうかは別問題)。

おまけ Perlで実装

Perlだといささかクセが強いコードになる。 その理由は、Perlの独特な部分である「スカラー型とリスト型の特性」をものすごく活用することになるためだ。

例えば、リスト変数をスカラーコンテキストで評価すると「リストの長さ」になるし、リストにはスカラー値しか格納できないので多次元配列にはならず、そのため「リストのリスト」は自動的に平坦なリストになったりする。

#!/usr/bin/perl

my $plen = int(shift);
$plen = 64 if $plen lt 1;

my @csym = split(//, shift);
my @converter;
if (0 < @csym) {
  @converter = (("a" .. "z"), ("A" .. "Z"), (0 .. 9), @csym);
} else {
  @converter = map { chr $_ } (33 .. 126);
}
my $cloop = int(255 / @converter);
my $clen = @converter * $cloop;

open(FH, "<", "/dev/urandom") or die $!;
for (my $outlen = 0;$outlen < $plen; $outlen++) {
  my $c;
  read(FH, $c, 1);
  $c = ord($c);
  redo if $c >= $clen;
  print $converter[($c % @converter)];
}

おまけ2 Luaで実装

Luaはショートハンドが少なくて、機能的にも少ないので、(私のLua力が低いのもあるにせよ) すごく素直な、というか、回りくどい、というかそういう書き方になる。

JavaScreipt同様にいわゆるHashとArrayが同一型(table)なのがLuaの特徴的なところだが、それ以上に配列としてtableを使うと1 originであるというのが混乱を招く。 あと、ライブラリに属する関数を呼ぶときは.で、インスタンスメソッド的なものは:になっているのも慣になる。れが必要。

#!/usr/bin/lua

pwlength = tonumber(arg[1])
converter_symbols = arg[2]

if not(pwlength) or pwlength < 1
then
  pwlength = 64 
end

converter={}
if converter_symbols
then
  for c in converter_symbols:gmatch(".") do
    table.insert(converter, c)
  end
  for asc=48,57 do
    table.insert(converter, string.char(asc))
  end
  for asc=65,90 do
    table.insert(converter, string.char(asc))
  end
  for asc=97,122 do
    table.insert(converter, string.char(asc))
  end
else
  for asc=33,126 do
    table.insert(converter, string.char(asc))
  end
end

convloops = math.floor(255 / #converter)
convlength = #converter * convloops
outlength = 0

urandom = io.open("/dev/urandom", "r")
while outlength < pwlength
do
  c = urandom:read(1)
  c = c:byte()
  if not(c >= convlength)
  then
    io.write(converter[(c % #converter) + 1])
    outlength = outlength + 1
  end
end

続編

この記事には続編がある

おまけの宣伝

Mimir Yokohamaではプログラミングの学習に適したサービスを提供している。

家庭教師サービスは(条件は限定されるが)こうした内容をより踏み込んだものや、体系化された知識を授業として受講可能だ。

また、開発サービスに“Educational Code”オプションがあり、そのオプションはオーダーメイドのソフトウェアに、この記事のような解説がコメントとして入ったコードを入手することができる。

もちろん、これらの組み合わせも可能だ。


  1. そもそもNILというの自体はLispから拝借しているのだが、LispではNILはnullじゃなくてfalseである↩︎

Wrote on: 2019-10-19 15:12:00 +09:00