C++
algorithm
C++11

C++でマイナンバーのチェックデジットを計算する


追記:はじめに

@MaverickTse, @mtfmk, @YSRKEN 氏の格闘の結果、超高速されたものが登場しました。

SPROUT_CXX14_CONSTEXPR sprout::array<std::uint8_t, 1000> make_mod_table_ysr() {

sprout::array<std::uint8_t, 1000> re{};
for (size_t i = 0; i < 1000; ++i) {
size_t mod = i % 11;
re[i] = static_cast<std::uint8_t>(mod <= 1 ? 0 : 11 - mod);
}
return re;
}
static inline bool validate(const __m128i& x)
{
__m128i t = _mm_sub_epi8(x, _mm_min_epu8(x, _mm_set1_epi8(9)));
return _mm_test_all_zeros(t, _mm_setr_epi32(-1, -1, 0x00FFFFFF, 0)) == 1;
}
uint8_t calc_check_digit_mtfmk_ysrken(const std::string& str) noexcept
{
static SPROUT_CXX14_CONSTEXPR auto mod_table = make_mod_table_ysr();
if (str.size() != 11) {
return 0xFE;
}

__m128i p_n = _mm_loadu_si128(reinterpret_cast<const __m128i*>(str.c_str()));
p_n = _mm_sub_epi8(p_n, _mm_set1_epi8('0'));
if (!validate(p_n)) {
return 0xFF;
}

__m128i sum = _mm_maddubs_epi16(p_n, _mm_setr_epi8(6, 5, 4, 3, 2, 7, 6, 5, 4, 3, 2, 0, 0, 0, 0, 0));
sum = _mm_sad_epu8(sum, _mm_setzero_si128());
sum = _mm_add_epi32(sum, _mm_srli_si128(sum, 8));
return mod_table[_mm_cvtsi128_si32(sum)];
}

詳細は

を参照してください。


初めに

どうももうすぐマイナンバーの仮カードが配られるらしい。セキュリティがものすごく不安だ。

まあそんな話はさておき

Ruby - マイナンバーのチェックデジットを計算する - Qiita

が目についた。どうやらマイナンバーにはチェックデジット(検査用数字)なるものがあるらしい。


行政手続における特定の個人を識別するための番号の利用等に関する法律施行令

http://law.e-gov.go.jp/announce/H26SE155.html

(個人番号とすべき番号の構成)

第八条  法第八条第二項の規定により生成される個人番号とすべき番号は、機構が同条第三項の規定により設置される電子情報処理組織を使用して、作為が加わらない方法により生成する次に掲げる要件に該当する十一桁の番号及びその後に付された一桁の検査用数字(個人番号を電子計算機に入力するときに誤りのないことを確認することを目的として、当該十一桁の番号を基礎として総務省令で定める算式により算出される零から九までの整数をいう。第三号において同じ。)により構成されるものとする。

一  住民票コードを変換して得られるものであること。

二  前号の住民票コードを復元することのできる規則性を備えるものでないこと。

三  他のいずれの個人番号(法第七条第二項の従前の個人番号及び個人番号とすべき番号を含む。)を構成する検査用数字以外の十一桁の番号とも異なること。


で検査用数字はどうやって求めるのさ?というと


行政手続における特定の個人を識別するための番号の利用等に関する法律の規定による通知カード及び個人番号カード並びに情報提供ネットワークシステムによる特定個人情報の提供等に関する省令

http://law.e-gov.go.jp/announce/H26F11001000085.html

(検査用数字を算出する算式)

第五条  令第八条の総務省令で定める算式は、次に掲げる算式とする。

算式

 11―(n=1(シグマ)11(Pn×Qn))を11で除した余り)

 ただし、(n=1(シグマ)11(Pn×Qn))を11で除した余り≦1の場合は、0とする。

算式の符号

 Pn 個人番号を構成する検査用数字以外の十一桁の番号の最下位の桁を1桁目としたときのn桁目の数字

 Qn 1≦n≦6のとき n+1 7≦n≦11のとき n―5



検査用数字の導出法

つまり



  • 検査用数字 : $11 - \Bigl( \displaystyle\sum_{n=1}^{11} P_n \times Q_n \Bigr) \% 11$


    • ただし $\Bigl( \displaystyle\sum_{n=1}^{11} P_n \times Q_n \Bigr) \% 11 ≦1 $の場合は、$0$とする




  • $Pn$と$Qn$の定義


    • $Pn$ : 個人番号を構成する検査用数字以外の十一桁の番号の最下位の桁を $1$ 桁目としたときの $n$ 桁目の数字

    • $Qn$ : $1≦n≦6$ のとき $n+1$、 $7≦n≦11$ のとき $n-5$



ということらしい。

計算式を見たってわかんね~、という人は

マイナンバー(個人番号)の12桁の数字の下一ケタがチェックデジット... - Yahoo!知恵袋

をみるといいと思います。(質問者もBANされていないし取り消したような痕跡もないにもかかわらずなぜか質問が消されているのでWebArchiveにリンク張替え)


C++11での実装

というわけで実装していく。例外のエラーメッセージ適当すぎんだろとか言わない。


数式に忠実に

#include <string>

#include <utility>
#include <numeric>//std::accumulate()
#include <stdexcept>
#include <cctype>//std::isdigit()
int calc_check_digit(const std::string& num) noexcept(false) {
if (11 != num.length()) throw std::runtime_error("num.digit must be 11");
const int remainder = std::accumulate(num.rbegin(), num.rend(), std::pair<int, int>{}, [](const std::pair<int, int>& s, const char& e){
if(!std::isdigit(e)) throw std::runtime_error("num.digit must be 11");
const int n = s.second + 1;
const int p = e - '0';
const int q = (6 < n) ? n - 5 : n + 1;
return std::pair<int, int>{s.first + p * q, n};
}).first % 11;
return (0 == remainder || 1 == remainder) ? 0 : 11 - remainder;
}



短く書くwithC++14

#include <string>

#include <utility>
#include <numeric>
#include <stdexcept>
#include <cctype>
int calc_check_digit(const std::string& n) noexcept(false) {
if (11 != n.size()) throw std::runtime_error("n.digit must be 11");
const int r = std::accumulate(n.rbegin(), n.rend(), std::pair<int, int>{}, [](const auto& s, const char& e) -> std::pair<int, int>{
if(!std::isdigit(e)) throw std::runtime_error("n.digit must be 11");
return {s.first + (e - '0') * ((5 < s.second) ? s.second - 4 : s.second + 2), s.second + 1};
}).first % 11;
return (0 == r || 1 == r) ? 0 : 11 - r;
}

numericヘッダーにあるものだから忘れられがちなstd::accumulateですが無茶めちゃ便利です。単に合計を求めるだけでなく、第3, 4引数を工夫することでかなりいろいろできます。

ただしstd::accumulateの第3引数の型と第4引数で指定する関数の第1引数の型から参照とcv修飾子を除いた型とその戻り値の型、さらにstd::accumulateの戻り値を受ける変数の型は一致させましょう。あと第1,2引数で指定したイテレータが指すコンテナの要素型と第4引数で指定する関数の第2引数の型から参照とcv修飾子を除いた型もですね。結果が謎になります。

//イメージ

Ret result = std::accumulate(Container<Elem>::iterator begin, Container<Elem>::iterator end, Ret init, [](const Ret& r, const Elem& e) -> Ret{});

検査用数字の導出法が下桁からみていくようだったのでリバースイテレータを使ってます。ruby版だとreverseしてますがそんなことする必要は無いですからね。

このcalc_check_digit関数は例外を投げうるので、呼ぶときはちゃんと例外処理してください。


実行例

http://melpon.org/wandbox/permlink/CNrdqxw1MbD0r4bI


各言語実装まとめ

言語
リンク

Ruby
マイナンバーのチェックデジットを計算する

Ruby
マイナンバーを検証する gem を作った

C++
C++でマイナンバーのチェックデジットを計算する

Python
Python マイナンバー検証用モジュールを公開

PHP
マイナンバーのチェックデジットを計算する PHP版

C#
C#でマイナンバーのチェックデジットを計算する

C#
C#でマイナンバーのチェックデジットを計算する - YDiary

SQL
マイナンバーのチェックデジットを計算する(SQLで)

Perl
Perl5,Perl6でマイナンバーのチェックデジットを計算する

PowerShell
WindowsPowerShell & C#マイナンバーのチェックデジットを計算する

JavaScript, Groovy
JavaScriptとGroovyでマイナンバーのチェックデジットを計算する

JavaScript, Ramda
マイナンバーのチェックデジットを JavaScript で計算する

Haskell
Haskellでマイナンバーのチェックデジットを計算する

Haskell
マイナンバー数字列の確認

Haskell
マイナンバーのチェックデジットを Haskell で計算してみる

Java
マイナンバーのチェックデジットを計算する(Java編)

Java
マイナンバーチェックデジット用Javaコード

Go
マイナンバーのチェックデジットをGoで計算する

Go
go-mynumber/mynumber.go at master · koron/go-mynumber

C, Go, Bash, Excel etc...
マイナンバーのチェックデジットの検算をざっくり1割くらい高速化する(計ってないので知らんけど)

Swift
マイナンバーのチェックデジットをSwiftで計算する

Vim script
Big Sky :: Vim からマイナンバーを検証出来るプラグイン書いた。

Vim script
mattn/vim-mynumber: Check your MyNumber

Scheme(Gauche)
Scheme(Gauche)でマイナンバーのチェックデジットを計算する

Scheme (R7RS+SRFI)
Scheme (R7RS+SRFI) でマイナンバーのチェックデジットを計算する

OCaml
OCaml でマイナンバーのチェックデジットを計算する

Rust
Tomohiro/mynumber GitHub

TeX
TeXで簡単プログラミング♪ - 0番染色体

Kotlin
Kotlinでマイナンバーのチェックディジットを計算する

Objective-C
マイナンバーのチェックディジットをObjective-Cで計算する

Elixir
Elixirでマイナンバーのチェックデジットを計算する

Agda
【速報】マイナンバーの全域性とチェックディジットの一意性が証明された!?

Crystal

マイナンバーのチェックディジットをCrystalで計算する 

D
D 言語でコンパイル時にマイナンバーの妥当性をチェックするテンプレート

Emacs Lisp
syohex/emacs-mynumber: Mynumber validation in Emacs

Scala
マイナンバーのチェックデジットをScalaで計算する

Bat(コマンドプロンプト)
Windowsバッチファイルでマイナンバーのチェックデジットを計算 - 沖の雑記帳

Awk
awkでマイナンバーのチェックデジットを検証・集計 - 沖の雑記帳

Awk
マイナンバーチェッカー用シェルawkスクリプト - 日々之迷歩

ClojureScript
knjname/validate-my-number.cljs

AppleScript
マイナンバーのチェックデジットをAppleScriptで計算する

Bat,awk,Fortran77,Brainfuck
色々な言語でマイナンバーのチェックデジットを計算したかった

C++
SIMD intrinsicでチェックディジットを計算してみる

C++
SIMD intrinsicでチェックディジットを計算してみる その2

C++
yumetodo/benchmark_calc_check_degit: C++でマイナンバーのチェックデジットを計算する

Fortran2003
マイナンバーのチェックデジットを計算する Fortran 2003

Qiitaでは一番上のRuby版が最初だと思います。

python版が出てる!これは勝ち確定です!(何に対する?)

Swift版も出たとかついにApple信者(偏見)もマイナンバー対応に動いたのか(違う)。

そして驚くべき言語展開。なんでこんなに流行ってるのさ。

ここまでみて分かる通りすべて文字列として数値を受け取るものばかりです。なぜなら先頭が0のマイナンバーを判別できないからです。数値でやってる人もいた。

ところで「Groovyって何?」となって

http://codezine.jp/article/detail/3757

を見るまで知らなかった件

なんか @h_oki 氏によるBrainfuck版が出てるけど控えめに言って頭おかC・・・いや、なんでもない。


追記


http://qiita.com/rana_kualu/items/f36275032bbc6a3f18b4

チェックディジットは一意に決まるので、実質11桁、たった1000億通りしかありません。

現時点でも適当に1000回撃てば一回通ってしまいます。

IPv6とまでは言わないが、せめて16桁くらい取っておいてもよかっただろ。


お、せやな(棒読み)


実際にマイナンバーが届いた

というわけで実際に実行例のプログラムで試したところ、ちゃんとチェックデジットはあってました。良かった。


追記:ベンチマーク

なんか

ただマイナンバー計算しても面白くないから最速を目指してみた。

なる記事がでた。どう考えても私の記事を煽っている(注:という妄想です)

で、その記事を読んでみたが、4点気に入らない


  1. 引数がconst array<int, 12>&だが、常識的に考えて、入力は文字列だろうから、const std::string&でなければ困る

  2. 無駄にキャストするな、可読性もくそもありゃしねぇ

  3. helper関数としてQという名の関数があるがなんでconstexprじゃねーんだ。constexprは市民の義務だろ!


  4. clock()とかいうC++においてはとっととdeprecatedになるべき関数を時間計測に用いている。ありえない。しかも大抵の環境では分解能が低い。std::chrono::high_resolution_clock::nowを使おう(ただしVSの場合VS2013までは分解能が高くない)

というわけで書き換えて、ついでに私のコードと勝負させることにした。

ちなみに私のコードもstd::isdigitは使わないように書き換えている。わざわざlocale依存の関数を使う必要はよく考えて見ればないからな。ついでにエラー処理と計算部分を分離した。


対決コード

std::uint8_t calc_check_digit_yumetodo(const std::string& n) noexcept(false) {

if (11 != n.size()) throw std::runtime_error("n.digit must be 11");
for(auto e : n) if(e < '0' || '9' < e) { throw std::runtime_error("in function calc_check_digit_yumetodo : iregal charactor detect.(" + n + ')'); }
const std::uint8_t r = std::accumulate(n.rbegin(), n.rend(), std::pair<int, int>{}, [](const auto& s, const char& e) -> std::pair<int, int>{
return {s.first + (e - '0') * ((5 < s.second) ? s.second - 4 : s.second + 2), s.second + 1};
}).first % 11;
return (0 == r || 1 == r) ? 0 : 11 - r;
}
constexpr unsigned short Q(unsigned char n) {
return (1 <= n && n <= 6) ? n + 1 : n - 5;
}
std::uint8_t calc_check_digit_ryogaelbtn(const std::string& P) {
if (11 != P.size()) throw std::runtime_error("P.digit must be 11");
for(auto e : P) if(e < '0' || '9' < e) { throw std::runtime_error("in function calc_check_digit_ryogaelbtn : iregal charactor detect.(" + P + ')'); }
unsigned int sum = 0;
sum += static_cast<unsigned short>(P[10]) * Q(1);
sum += static_cast<unsigned short>(P[9]) * Q(2);
sum += static_cast<unsigned short>(P[8]) * Q(3);
sum += static_cast<unsigned short>(P[7]) * Q(4);
sum += static_cast<unsigned short>(P[6]) * Q(5);
sum += static_cast<unsigned short>(P[5]) * Q(6);
sum += static_cast<unsigned short>(P[4]) * Q(7);
sum += static_cast<unsigned short>(P[3]) * Q(8);
sum += static_cast<unsigned short>(P[2]) * Q(9);
sum += static_cast<unsigned short>(P[1]) * Q(10);
sum += static_cast<unsigned short>(P[0]) * Q(11);

return sum % 11 <= 1 ? 0 : 11 - sum % 11;
}


計測は一発勝負、ループ回数は元記事の10倍の10000000(10^7)回、環境はだれでも利用できるwandboxを用いる。


clang3.8-O2

generating inputs...done.

start vench mark:
calc_check_digit_ryogaelbtn : 251[ms] (251311496[ns])
calc_check_digit_yumetodo : 265[ms] (265814777[ns])
vench mark finish!

http://melpon.org/wandbox/permlink/4LuMFnk99W7FWHnz


clang3.8-O3

generating inputs...done.

start vench mark:
calc_check_digit_ryogaelbtn : 247[ms] (247027803[ns])
calc_check_digit_yumetodo : 244[ms] (244624077[ns])
vench mark finish!

http://melpon.org/wandbox/permlink/XsElyq6t55khBdR0


gcc6.1.0-O2

generating inputs...done.

start vench mark:
calc_check_digit_ryogaelbtn : 255[ms] (255793658[ns])
calc_check_digit_yumetodo : 475[ms] (475591886[ns])
vench mark finish!

http://melpon.org/wandbox/permlink/3qAjDExuRERlh419


gcc6.1.0-O3

generating inputs...done.

start vench mark:
calc_check_digit_ryogaelbtn : 203[ms] (203583920[ns])
calc_check_digit_yumetodo : 202[ms] (202423769[ns])
vench mark finish!

http://melpon.org/wandbox/permlink/d4i5QjDprvrRho2U

両者差はないかな。GCCの-O2だけ差がついたのは、std::accumulatestd::pairをうまく消せてないからかな?

結論としては、コンパイラの最適化は鬼がかっているので、無理に読みづらくしてまでコードを書き換えなくていいというありきたりなものになるでしょうか。むしろエラー処理のほうが時間かかっている気がする。実際今回私のコードのエラー処理を分離するだけで350msくらい縮んでいます。

追記:うわ、typoしとる、なにがvench markじゃい!benchmarkだわ!戒めとして残しておきます。


追記:税務署でアルバイトしてみて

諸事情あって税務署で短期アルバイトしたんですが、まだまだマイナンバーの混乱は続いていますね~。とりあえずシステムくんだけどマニュアルなんてなかった的なアレ。あと、マイナンバー通知書だけ送ってきて(マイナンバーカードじゃないと本人証明にならない)身分証明書送ってこない人とか多かった。

マイナンバー導入後最初の確定申告が2017/3/15に終わり、電子証明書をほしいがためにマイナンバーカードを申請する人も一段落し、今ならそんなに時間がかからずにマイナンバーカードが手に入るんじゃないかなぁ・・・。


追記:個人情報保護委員会の言論弾圧に物申す

というわけで、普通にJavaScriptで書くのはもうたくさんの人がやっている気がするので、C++で書いてWebassemblyに変換してブラウザ上で実行できるようにした。

マイナンバーのチェックデジットをWebassemblyで計算する

Webassembly初めて触ったけどC++からやるのだいぶだるいなぁという印象。