Hatena::ブログ(Diary)

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

[プロフィール]
 

2016年9月18日(日) 続・世界最小のRSA鍵ペアは何bitか このエントリーを含むブックマーク このエントリーのブックマークコメント

前回の記事「世界最小のRSA鍵ペアは何bitか」でp=3, q=5(つまりn=15)の場合のRSA鍵ペアを紹介しましたが、kazuhookuさんからこんなブックマークコメントを頂きました。


面白い。n=4(あるいは2)はダメなのかな


もっと小さいnを採用できないのか?という指摘かと思います。前回記事では普段RSA暗号のノリで「p,qは異なる奇素数」という前提を置いていましたが、既に非常識なくらい短い鍵長の話をしている中で常識にとらわれるのは無意味というものでしょう。


本稿では15未満のnでRSA暗号らしきものが構成できるのかどうかを探ります。

n=1の場合

RSA暗号の平文mに対して m^(e*d) = m (mod n)が成り立つ最小のnを考えると、n=p=q=e=d=1が見つかります。これは1bit RSA鍵ということになりますので、もし認められるなら世界最小なのは間違いありません。


n=1のRSA暗号というのは、平文も暗号文も0しか無い世界ということになります。文字が一種類しか無い世界での暗号とは何なのか?という哲学的な問いはいったん忘れて、まずはこのような鍵に対してopensslコマンドが動作するのかを調べることにしましょう。


$ cat /tmp/public-key-n1.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAQIBAQ==
-----END PUBLIC KEY-----
$ openssl asn1parse -strparse 17 < /tmp/public-key-n1.pem
    0:d=0  hl=2 l=   6 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim: INTEGER           :01
    5:d=1  hl=2 l=   1 prim: INTEGER           :01
$ perl -e 'print "\x00"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n1.pem | base64
RSA operation error
140735149846608:error:04068065:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:bad e value:rsa_eay.c:169:

暗号化しようとすると「bad e value」と怒られてしまいました。OpenSSLソースコードを確認したところ、n<=eだとエラーになるようです。これが必須のチェックだとは思いませんが、変な鍵なのは間違いないでしょう。


n=2の場合

次はn=2,e=1が候補になります。同様にOpenSSLで動作確認してみましょう。


$ cat /tmp/public-key-n2.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAgIBAQ==
-----END PUBLIC KEY-----
$ perl -e 'print "\x01"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n2.pem | base64
RSA operation error
140735149846608:error:0306E06C:bignum routines:BN_mod_inverse:no inverse:bn_gcd.c:525:

今度は「no inverse」というエラーで怒られました。どうやら多倍長演算の前準備としてmod nで0x10000000000000000のモジュラ逆数を計算する処理が走るようで、nが偶数だと必ず死ぬようです。OpenSSLバグといえばバグだと思いますが、仕方がないというものでしょう。


n=3の場合

n=3,e=1の場合はどうでしょうか。


$ cat /tmp/public-key-n3.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAwIBAQ==
-----END PUBLIC KEY-----
$ perl -e 'print "\x02"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n3.pem | base64
Ag==
$ cat /tmp/private-key-n3.pem
-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAQMCAQECAQECAQMCAQECAQECAQECAQE=
-----END RSA PRIVATE KEY-----
$ echo "Ag==" | base64 -D | openssl rsautl -raw -decrypt -inkey /tmp/private-key-n3.pem | od -tx1 -Ax
0000000    02
0000001

何もトラブルなく動いてしまいました。なんと2bit鍵というわけです。


とはいえ、個人的にはこれをRSA暗号だと言うのには抵抗があります。e=1のときは平文と暗号文が完全に一致するので、そもそも暗号になっていません。


また、RSA暗号ではサイズの大きい合成数nの素因数分解が困難であるということが暗号強度の根拠になっています。しかし、nが素数だとこの前提が崩れてしまい、誰でも秘密鍵を復元できてしまいます。また、公開鍵に含まれるnが素数かどうかはミラー・ラビン素数判定法で高速に判定できるので、攻撃者は弱い鍵を容易に探すことができます。


逆に言うと、nが素数だったりe=1であったりする非常に弱い鍵ペアであってもOpenSSLで正常動作するというのは意外な結果かもしません。


まとめ

  • OpenSSLはnが偶数RSA鍵を想定しておらず、エラー終了する
  • OpenSSLで動作する最小のRSA鍵ペア(らしきもの)はn=3のときである
  • OpenSSLは弱いRSA鍵に対して寛容
トラックバック - http://d.hatena.ne.jp/hnw/20160918

2016年9月11日(日) 世界最小のRSA鍵ペアは何bitか このエントリーを含むブックマーク このエントリーのブックマークコメント

「理論上最短のRSA鍵の鍵長は何ビットなのか?」という疑問が湧いてきたので、RSA鍵の長さに関する制約について調べてみました。とにかく小さいRSA鍵ペアを作ろうと思ったらp=3,q=5の4bit RSA鍵というのが作れそうですが、本当にそんな鍵が作れるのでしょうか?


本稿ではRSA暗号およびRSA署名のパディングに関する仕組みを紹介し、最短の鍵長となるRSA鍵について検討します。


RSAES-PKCS1-v1_5 におけるパディング


鍵長最短となるRSA鍵ペアを作る上で障害になるのが、RSA暗号のパディングと呼ばれる仕組みです。


RSA暗号における暗号化および復号処理は整数の累乗演算ですから、仮に平文mが1だった場合、暗号文も1ということになってしまい暗号として機能しなくなってしまいます。このような問題への対策として、受け取った平文をそのまま使うのではなく、パディング文字列を付加して暗号化するのがRSA暗号では一般的です。復号時には、単にパディング文字列を無視すれば元の平文を取り出せます。


現在もっともよく用いられているRSA暗号の方式は RSAES-PKCS1-v1_5 と呼ばれるもので、与えられた平文にパディングとして固定の3バイトおよびランダムの8バイトを付加します。元の平文が1バイトだとしても計12バイトになってしまうので、RSA暗号が成立するには最低でも96bit必要ということになります。


実際に96bit RSA鍵を作って公開鍵で暗号化してみると、1バイトの平文は暗号化できますが、2バイトの平文を与えると「data too large for key size」と怒られてしまいます。


$ openssl genrsa 96 > private-key.pem
Generating RSA private key, 96 bit long modulus
.+++++++++++++++++++++++++++
..+++++++++++++++++++++++++++
e is 65537 (0x10001)
$ openssl rsa -in private-key.pem -pubout -out public-key.pem
writing RSA key
$ perl -e 'print "a"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
XQRoJI+EJRN73cs9
$ perl -e 'print "ab"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
RSA operation error
140735114489936:error:0406D06E:rsa routines:RSA_padding_add_PKCS1_type_2:data too large for key size:rsa_pk1.c:153:
$

RSA署名だと最短でも368bit鍵が必要

次にRSA署名について考えてみます。署名というのは、対象となる文書ハッシュ値を取り、ハッシュ値RSA秘密鍵暗号化するようなものです。今回は、ハッシュ関数としてSHA1を使うRSASSA-PKCS1-v1_5 with SHA1を考えてみます。


先ほど、RSA 96bit鍵では最長1バイトの平文しか暗号化できないことがわかりました。SHA1は160bitですので、SHA1値をRSA暗号化するのに96bitでは全然足りません。いったいどれほどの長さが必要になるのでしょうか。


調べてみると46バイト(368bit)が最短だとわかりました。パディングの11バイトと、SHA1値の20バイトに加え、ASN.1のヘッダ類で15バイトを消費しますので、これらの合計である46バイトより短い鍵長では署名時にエラーが出てしまいます。実際、360bit鍵でRSA署名を試すとエラーが出ることが分かります。


$ echo foo > foo.txt
$ openssl genrsa 360 > private-key.pem
Generating RSA private key, 360 bit long modulus
.++++++++++++++++++
.....++++++++++++++++++
e is 65537 (0x10001)
$ openssl dgst -sha1 -sign private-key.pem foo.txt
Error Signing Data
140735114489936:error:04075070:rsa routines:RSA_sign:digest too big for rsa key:rsa_sign.c:122:

当然ですが、SHA256などサイズの大きいハッシュ関数を使う場合はより長いRSA鍵が必要になります。


パディング無しで最短のRSA鍵を作る

パディングの存在を考えると、現実の実装が取り扱ってくれそうなRSA鍵は案外長いということがわかりました。では、パディング無しの条件で短い鍵に対する制約があるのでしょうか?


実際にOpenSSLで実験してみることにします。以下はn=15,e=3の公開鍵です。


-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBDwIBAw==
-----END PUBLIC KEY-----

この鍵で「0x0d」1文字の暗号化を行います。パディング無しにするためopenssl rsautlに「-rawオプションを指定しています。


$ perl -e 'print "\x0d"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
Bw==

短すぎる暗号文ができました。今度はこれを復号してみます。秘密鍵は下記です。


-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAQ8CAQMCAQMCAQUCAQMCAQMCAQECAQI=
-----END RSA PRIVATE KEY-----

$ echo "Bw==" | base64 -D | openssl rsautl -raw -decrypt -inkey shortest-private-key.pem | od -tx1 -Ax
0000000    0d
0000001

このように、特にトラブルもなく復号できました。4bit RSA鍵での暗号化および復号がOpenSSLで機能したわけです。


補足ですが、この鍵ペアはn=15であるので、15以上の平文・暗号文は扱えません。「0x0f」1文字を暗号化しようとするとエラーで死にます。


$ perl -e 'print "\x0f"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
RSA operation error
140735114489936:error:04068084:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:data too large for modulus:rsa_eay.c:221:

先ほど紹介したRSAES-PKCS1-v1_5でのパディングの1文字目は0x00になっているのですが、これはnを超える平文を作らせないための仕様なのでしょう。


鍵の強度に関する注意

念のため補足ですが、短いRSA鍵は素因数分解による解読の危険性があります。256bit以下であれば、家庭のPCで一瞬で素因数分解が完了します。512bit鍵も個人が十分解読できる時代です。


2048bit RSA鍵であれば2030年頃までは安全とされていますので、実際に使うのであれば2048bit以上の鍵を使ってください。本稿で紹介した4bit RSA鍵を実用するなどは論外です。


まとめ

  • 世界最小の鍵ペアである4bit RSA鍵がOpenSSLで動作した(全く実用的ではない)
  • 通常の条件であれば暗号化には96bit以上のRSA鍵が、署名には368bit以上のRSA鍵が必要

うめうめ 2016/09/12 21:16 筆算できますかね?

hnwhnw 2016/09/12 22:01 この記事でいう4bit RSAの暗号化および復号処理は15未満の整数の累乗とmod 15の計算だけで構成されるので当然手計算可能ですし、15文字しか無い換字式暗号だと考えれば計算すら必要ないとも言えますね。

hnwhnw 2016/09/12 22:13 鍵長が短ければ筆算によるRSA公開鍵の素因数分解が可能か?という意味であれば当然Yesです。とはいえ、本稿で指摘した通り鍵長が短いとマトモな暗号化ができないので、そのような仮定は厳しいと言えるでしょう。

2016年8月28日(日) Language Update PHP編(LLoT補足) このエントリーを含むブックマーク このエントリーのブックマークコメント

昨日8/27にLLoTの「Language Update」の10分枠でPHPの話をしました。発表資料は以下です。



会場にPHPの人はほとんどいない前提だったので、他の言語の人に「最近のPHPってこんな感じですよ」をお伝えするつもりで資料作成しました。言いたかったことはだいたい言えたつもりですが、補足と感想などを書いてみます。


PHP 7.0でのトピック

プレゼン資料にも書いたんですが、PHP 7についてお伝えしたかったことは、メジャーバージョンアップながら移行のハードルは低いこと、また高速化チーム(PHPNGチーム)が高速化を達成したことの意義、という2点になります。


メジャーバージョンアップといえばPerl 4→5やPython 2→3の混乱が連想されると思うんですが、それに比べるとPHP 5→7は内部構造のみの大変更であり、他の言語で言えばマイナーバージョンアップと同レベルの変更だと思う、というのは他の言語の方々にも十分伝わったのかなと思います。


また、PHP 7で高速化チームが無事高速化を達成したこと自体はPHPユーザーでなくても知っている内容だったと思うんですが、この意義は大きかったと個人的には考えています。というのは技術面よりも政治面です。


PHPは絶対的なリーダーがものごとを決めるような運営方針ではないため、これまでは横断的な変更をかけにくい雰囲気があったように思います。今回の高速化は既存コード全体に影響するようなものであり、このような大変更の前例が作れたという意味で今後に繋がるものだと感じています。


PHP 7.1でのトピック

今回発表に向けて7.1でのトピックを探したんですが、7.0に比べると劇的な成果とまでは言えないような変更が多い印象を持ちました。


たとえば、PHPプログラム最適化処理(OPcache内の処理)にコンパイラ最適化でよく用いられるSSA静的単一代入形式)を作るような処理が入っていますが、いまのところ全然役に立っていないように見えます。7.2以降での最適化に繋がっていくことを期待したいですね。


PHP 7.1が11月か12月リリースだろう、というのは下記資料が根拠です。いまのところ順調に進んでいますが、多少の波乱は当然あるでしょう。ちょうど今beta3でBC breakがあったとかいう議論をしていたりします。



動的型付けと静的型付け

今回のイベントでは型の話題が多かったような印象を持ちました。


私のプレゼンでも紹介した通り、動的型付け言語であるPHPでもIDE型推論を利用して実行前に型エラーを検出するような仕組みが身近になってきています。PythonJavaScriptについても近いニーズがあるという印象を受けました。


一方で、SwiftC#など昨今のモダンな静的型付け言語では単相型の型推論を取り入れているものが多くあります。静的型付けが好きな人も、自明な型を書かずに済むなら当然書きたくないわけです。


つまり、両方の陣営が近いゴールを目指しており、その共通の道具は型推論なのだと最近考えていましたが、似た認識を持った方が会場には何人もいらしたように感じました。


個人としては、これから型推論を利用した言語がもっと身近になっていき、最終的にF#が世界制覇したら楽しいなぁと妄想しております。


感想など

会場撤収のタイミングで竹迫さんが「このイベントは全員アウェーなのが面白いんですよ」という話をされていて、なるほどなと思いました。私自身アウェーの楽しさを再認識したイベントでした。


目の前の仕事でさえ学ぶことが多すぎる中でアウェーの場に来るというのは多くの人にとってハードルの高いことだと思うんですが、特に若い人にはアウェーの場に積極的に出て行って多くを吸収してほしいと思います。


最後に、運営のみなさまお疲れさまでした。来年以降も若者を引きつけられるような、魅力あるコンテンツ作りを期待しております。

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

2016年8月20日(土) multi-prime RSAとは何か このエントリーを含むブックマーク このエントリーのブックマークコメント

RSAは現在主流と言える公開鍵暗号の方式で、SSHHTTPSなど重要プロトコルで利用されています。我々が普段利用しているRSA暗号では2つの巨大素数p,qを生成し、2素数の積nを公開鍵として利用します。万一nが素因数分解されてしまうと秘密鍵を計算で求めることが可能になりますが、nが2048bitであれば2030年くらいまで素因数分解は非現実的だろうと言われています。


ところで、入手したRSA公開鍵に含まれるnの素因数が3個以上だった場合に、対応する秘密鍵は存在するのでしょうか?また、その秘密鍵素因数分解の結果から計算できるのでしょうか?筆者はこの疑問に長らく答えが出せずにいたのですが、RFC3447(PKCS #1)に「multi-prime RSA」として定義されていることを知りました。本稿ではこの multi-prime RSA について紹介します。


RSA暗号の原理

RSA暗号では公開鍵として(n,e)という整数のペアを利用します。nはすでに紹介した通り巨大素数p,qの積です。eは都合の良い固定値(65537など)がよく使われます。


教科書的な秘密鍵としては(n,d)が使われます。ここでのdは次のような性質を持つ値です。


  • 任意のxに対して x^(e*d)=x (mod n) … (1)

このe,d,nを使うと、RSA暗号化処理・復号処理は次のように表せます。


  • 暗号
    • 平文をiとする、ただしi<n
    • 暗号文 c = i^e (mod n)
  • 復号
    • 暗号文 c に対して c^d (mod n)で平文が得られる

このように、秘密鍵に含まれるdさえバレなければ、暗号化に必要なeは公開することができるという仕組みになっています。


このdはオイラー関数φを用いて次のように表すことができます。


  • e*d = 1 (mod φ(n)) … (2)

つまり、eのモジュラ逆数を取ればdが計算できるというわけです。


たとえばn=3*5の場合について考えてみると、e=3,d=3のときに(2)式を満たします。(1)式で実際に試してみましょう。


Prelude> map (\x -> x^(3*3) `mod` 15) [0..14]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

n未満の全ての平文が復元できていますので、RSAとして正しく機能することがわかります。


multi-prime RSAの実例

さて、実は上記の説明においてnの素因数が2つである必然性はありません。nとして3素数以上の積を使ったRSAをmulti-prime RSAと呼びます。


仮にn=3*5*7=105とすると、e=5,d=29のときに(2)式を満たします。先ほどと同様に(1)式を確認してみましょう。


Prelude> map (\x -> x^(5*29) `mod` 105) [0..104]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104]

やはり期待通りに動いています。このように、multi-prime RSAが機能すること自体は間違いありません。


現実の秘密鍵

ところで、先ほど「教科書的な秘密鍵」という説明をしましたが、現実のRSA実装では上の計算をそのまま行うことはありません。我々が普段使っている秘密鍵には次のような値が含まれています。


  • n
  • e
  • d
  • p
  • q
  • d mod (p-1)
  • d mod (q-1)
  • q^-1 mod p

dはnと同じくらいの大きさになるので、暗号文cの復号c^dは重い処理となります。現実の実装ではc^dをマジメに計算する代わりに、中国の剰余定理を利用してc^(d mod (p-1))とc^(d mod (q-1))の計算に変形し、教科書的な実装より4倍高速に計算を行っています。


ちなみに、nが3素数や4素数の積だった場合は中国の剰余定理を利用することで9倍、16倍と高速になっていきます。このように復号処理を軽量化できる点がmulti-prime RSAのメリットになります。


しかし、実際にmulti-prime RSAでの計算量低減メリットを受けるには秘密鍵のフォーマットを変えてd mod (p1-1),d mod (p2-1),…を持っておかなくてはなりません。このようなフォーマットに対応している実装は存在しないように思います[要出典]。


また、素因数の数を増やせば増やしただけ素因数分解による攻撃可能性も増えていきますので、多くすれば良いというものではありません。適用するとしても3素数が現実的だと考えられているようです。


最初の疑問に対する答え

最初の疑問「入手した公開鍵に含まれるnの素因数が3個以上だった場合に、対応する秘密鍵は存在するのでしょうか?また、その秘密鍵素因数分解の結果から計算できるのでしょうか?」に対する答えは以下のようにまとめられるでしょう。


  • 対応する秘密鍵は存在する(eとφ(n)が素である場合に限る)
  • 理屈上の秘密鍵は計算で求められる
  • 既存の実装に適用できるような秘密鍵はおそらく作れない*1

そもそも筆者がこのような疑問を持ったきっかけは、2015年頃にgithub.com上のSSH公開鍵の素因数分解を試みていた際(参照:「江戸前セキュリティ勉強会でgithub.comの弱い鍵を探す話をしました」)に3つ以上の素因数を持つSSH公開鍵がいくつか見つかったためです。これらの公開鍵はおそらくコピペミスで作られてしまったもので、アカウントの持ち主も対応する秘密鍵を持っていないと考えられますが、このような鍵に対しても素因数分解さえできれば攻撃可能だというのは面白い結論だと感じます。


参考URL

*1:と思ったんですが、 http://xrekkusu.hatenablog.jp/entry/2015/08/17/001939 を見ると正しく動作する秘密鍵が作れているようにも見えますね。どういう理屈なんだろ…。

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

2016年7月2日(土) PHPのround関数とは一体なんだったのか このエントリーを含むブックマーク このエントリーのブックマークコメント

(7/3 14:05追記)Javaに関する記述について誤認があったので盛大に書き換えました。Java 6、Java 7、Java 8それぞれで実装が変わっていたようです。

(7/13 23:55追記)本記事中ではroundを四捨五入と言い切ってしまっています。これは筆者がC99のroundを基準に考えているためですが、言語によっては偶数丸めになっているround関数も珍しくありません。ご注意ください。


PHPのround関数について、ネット上で次のような記述を見つけました。


PHP

四捨五入の計算を間違える唯一の言語として畏れられていましたが、そのバグは治っているかもしれません(治ってないかもしれません)


主要なプログラミング言語8種をぐったり解説 - 鍋あり谷あり


各言語を面白おかしく紹介する内容とはいえ、ずいぶん雑な理解だなーという印象です。ゆるふわな話だけでPHPdisられ続けるのもどうかと思うので、一連のround関数の話題について僕なりの総括をしてみたいと思います。


以下、こんなあらすじで紹介していきます。


  • PHP以外でも四捨五入関数バグっぽい挙動は珍しくない
    • RubyPythonの四捨五入はエッジケースで間違っていた
    • Javaの四捨五入にはバグなのか仕様なのか微妙なエッジケースがJava 7まで存在していた
    • 四捨五入で小数点以下n位に丸める仕様がそもそも難しい
  • PHPの現在の実装は整数への丸めについては他の言語と同じ
    • 当時話題になったround関数の実装は2009年リリースのPHP 5.3.0でリプレース済

経緯など

元ネタを知らない人向けに経緯を紹介します。


僕が2007年にPHPソースコード中の四捨五入関数の実装に気持ち悪いマジックナンバーを見つけて「PHPの奇妙なround関数」という記事にしたところ、なぜかRubyのまつもとさんの日記に拾われてバズったという事件がありました。


問題になったround関数の実装は率直に言ってやっつけ感あふれるもので、disられても仕方ない内容だったと思います。そもそも僕自身も「PHP気持ち悪いよね、ひどいよね」というつもりで記事を書いたわけです。しかし、非PHPユーザーが安全地帯からPHPを叩くためだけに乗っかってくるのに若干イラっとしたので、「お前らが安全地帯だと思ってる土台も実は脆いんだぜ」と言いたいがために他言語の浮動小数点数周りのバグを探してみました。


そうして調べていく中で、浮動小数点数の四捨五入について何個かエッジケースがあることに気づきました。また、各種プログラミング言語中の人が必ずしも浮動小数点数に詳しくないこともわかってきました*1。まずはround関数のエッジケースと各言語の対応状況について紹介します。


四捨五入のエッジケース1:0.49999999999999994

0.5より小さい倍精度浮動小数点数の中で最大の数が0.49999999999999994です。これを四捨五入すると、なぜか繰り上がって1になってしまう実装があります。



上記記事で紹介した時点では、RubyPythonがそのような実装になっていました。これは四捨五入が「引数が正なら0.5足して小数点以下を切り捨てる」という実装になっている場合に発生します。この問題を回避する実装は「引数が正のとき小数点以下を切り捨てて元の数との差が0.5以上なら1.0を足す」です。いやー浮動小数点数って難しいですね。


四捨五入の挙動がマニュアル通りとは言えない処理系PHP以外にもあった、というのはこの例だけ見ても明らかでしょう。


ちなみに、本件はRubyPythonとも最新版では修正済みとなります(かなり前から修正されているはずですが詳細な時期は把握していません)。


四捨五入のエッジケース2:9007199254740991.0

9007199254740991.0を四捨五入するとなぜか繰り上がって9007199254740992.0になってしまう実装があります。この数は倍精度浮動小数点数仮数部全bitが1であるような数になります。詳細は下記の記事をご覧ください。



これも先ほどの0.49999999999999994と同じく、「引数が正なら0.5足して小数点以下を切り捨てる」という実装のときに問題になる例です。上記記事のタイミングではPythonだけが該当しましたが、その直前くらいまではRubyも同様の実装でした。


もちろん、現在ではPythonの実装も修正されています。


Javaの四捨五入にはバグなのか仕様なのか微妙なエッジケースがJava 7まで存在していた

さて、上記2つのエッジケースについてですが、Java 6のround関数は2つとも間違いっぽい方に丸めます。


public class RoundTest {
    public static void main(String[] args) {
        double d1 = 0.49999999999999994d;
	double d2 = 9007199254740991.0d;
        System.out.println("d1: " + d1); // 0.49999999999999994
	System.out.println("round(d1): " + Math.round(d1)); // Java 6: 1, Java7-8: 0
        System.out.println("d2: " + d2); // 9.007199254740991E15
	System.out.println("round(d2): " + Math.round(d2)); // Java 6-7: 9007199254740992, Java8: 9007199254740991
    }
}

しかし、Java6の挙動はバグとも言い切れません。Java 6のマニュアルには下記のような記述があります。


public static long round(double a)


Returns the closest long to the argument. The result is rounded to an integer by adding 1/2, taking the floor of the result, and casting the result to type long. In other words, the result is equal to the value of the expression:


(long)Math.floor(a + 0.5d)


http://docs.oracle.com/javase/6/docs/api/java/lang/Math.html#round%28double%29


先ほどからイマイチな実装として紹介してきた「0.5足して小数点以下を切り捨てる」が内部実装だと書いてありますので、上の挙動は仕様なのかもしれません。この記述だけでエッジケースの分かるJavaプログラマがどれほどいるかは疑問ですが、文書化されていること自体は素晴らしいと僕は当時から絶賛していました。


ところで、Java 7以降のマニュアルからはこの内部実装に関する記述が消えているようです。トラックバック頂いた記事「JavaのMath.roundがバグっていないと言える可能性について - What will be done tomorrow?」によれば、Java 7で実装が変わったタイミングでマニュアルの記述も変わったということのようです。ただ、このタイミングではd1のみ正しく丸めるようになったようで、d2は繰り上がってしまう実装だったようです。これはマニュアルの記述「the value of the argument rounded to the nearest long value」に反していると言えるでしょう。


Java 8でさらに実装が変わったようで、Java 8からはエッジケース2件とも正しい方向に丸めるようになっています。


本件、OSCPUにも依存すると考えられるので環境によって再現できたりできなかったりあると思いますが、MacOSX環境のOracle JDKでの実験結果を添付しておきます。



四捨五入で小数点以下n位に丸める仕様がそもそも難しい


良い関数の条件の一つに「挙動が直感的である」ということがあるように思います。特に言語の標準関数であれば、長々説明しないと使えないような関数は害の方が多いくらいだと言えるでしょう。


その意味で、round関数小数点以下(n+1)位を四捨五入して小数点以下n位に丸める実装は危険です。n=0のとき、つまり普通の整数への丸めについて言えば2進の浮動小数点数でも0.5や1.5などが誤差無く表現できるので問題とはなりませんが、n>0の場合について言えば四捨五入の境界線(0.05や0.005)も丸まった後の数(0.1や0.01)もピッタリ表現できないため、仕様を言語化すること自体が難しいと言えます。


容易に思いつく実装として、10^n倍して整数への丸めを行って10^nで割るというものがあります。しかし、浮動小数点数を不用意に10^n倍するのは誤差の蓄積を生みやすい処理です。実際、次の例ではRubyPythonが直感に反する結果を返してしまいます。


$ ruby -e 'x=5.015; print x.round(2), "\n";'
5.01
$ python -c 'x=5.015; print round(x, 2),"\n";'
5.01

こうした実装に対する問題点の指摘を3年ほど前に記事にしました。



その後、より良い実装はどのようなものか?という議論に発展してshiroさんの素晴らしい見解を読むことが出来たのは良かったと思っています。



詳細は記事を読んで頂くとして、やはり「2進の浮動小数点数を10進表記で小数点以下n位に丸める関数の直感的な仕様は存在しない」というのが結論かなと思います。


元々のPHPのround関数も、小数点以下n位に丸める挙動を直感的にしようとして失敗してしまったものです。この件から我々が学ぶべきことは採用された実装のまずさについてではなく、小数点以下n位に丸める仕様を採用したという仕様策定段階の失敗についてではないでしょうか。


余談:その後Ruby小数点以下n位に丸める仕様を採用した

ところで、PHPのround関数に関する議論をしていた2007年当時最新だったRuby 1.8系のround関数には小数点以下n位に丸める指定はありませんでした。つまり、PHPのような悩みは無かったことになります。僕としては、その平和な状態を維持して頂きたいと思っていました。


その後、2008年頃にまつもとさんと飲み会で同席させて頂く機会があり、「Rubyのround関数には小数点以下n位に丸める仕様は絶対に入れない方がいいですよ」的な進言をしたように記憶しています。前後の文脈も何もなくお伝えしたのでキョトンとされていたような気もしますが、僕としてもそんなキモい仕様が採用されちゃう言語はPHPくらいだろうと思っていたので、詳細の話をすることもありませんでした。


ところが、その後Ruby 1.9系のround関数小数点以下n位で丸める仕様が入ってくることになります。僕は経緯を追っていませんが、ユーザーの声に抗えなかったんでしょうか。これまで誰も不満なく使っているようならいいんですけど。


現在のPHPのround関数の実装

現在のPHPのround関数の処理は、問題のあった実装がPHP 5.3.0で改善されてから変わっていません。詳細は次の記事で紹介しています。



この頃からPHPの仕様変更に関する議論RFCと呼ばれるWiki文書ベースで行われるようになり、大きい変更は多くの人の目が入るようになりました。また、仕様がきっちりドキュメントとして残るようになったのも大きな利点です。この丸め処理も下記のRFCベースで議論されており、これを読めば誰でも仕様把握できる状態になっています。



ちなみに、新たな丸め処理では整数への丸めは他の言語と完全に同じでケチの付け所はありません。


一方、小数点以下n位に丸める処理は直感的とは言えません。丸め位置を変えながら2回丸めるような処理になっており、一部エッジケースでバグっぽい挙動をするような、ある意味PHPらしい処理になっています。


とはいえ、先ほどから繰り返しているように小数点以下n位に丸める仕様を採用した時点で失敗だというのが個人的見解です。既に紹介した通り他の言語も誤差上等で実装しているわけで、PHPだけが変というのも違う気がします。


そんなわけで、PHP 5.3.0以降のround関数は他の言語と同等と言ってしまって差し支えないでしょう。


ちなみに当時話題になったround関数が実装されていたのはPHP 5.2系ですが、2009年に5.3系がリリースされてリプレースがはじまり、2011年には5.2系のセキュリティサポートが切れている状況です。完全に昔話という感じですね。


おわりに

四捨五入くらい誰でも実装できるって思うでしょ?意外とそうでもないわけですよ。ホントに。

*1:もちろん平均的には詳しい人が多いですし、スーパー詳しい人もたくさんいます

yukobayukoba 2016/07/03 12:08 Javaを試してみたのですが、Java 1.8.0_91, _92 で
WindowsおよびLinux、Oracle JDKおよびOpenJDKで、
Math.round(d2)は9007199254740992ではなく
9007199254740991になります。

「Javaのround関数は2つとも間違いっぽい方に丸めます。」
ではなく、どちらも正しいのではないでしょうか?

hnwhnw 2016/07/03 13:39 失礼しました。こんな細かいところに修正が入る可能性は低いと思い込んでいたので、手元にたまたまインストールされていた1.7.0_80のみで確認しておりました。確かに私の手元もMacOSXでも1.8.0_92では9007199254740991に丸めます。

また、d1が0に丸まるのは元々正しい方向に丸めてますよね。すみません、完全におかしいことを書いていました。

このあたり本文に追記および修正させて頂きます。ご指摘ありがとうございました。

 
ページビュー
1948102