はじめに

マイナンバーとは、国から日本人ひとりひとりに交付される、12桁の数字からなる番号である。この番号を用いて、男女間などである占いができるが、マイナンバーを無闇に他人へ教えてはならない。この記事ではまず、“マイナンバー占い”について解説し、マイナンバー占いをマイナンバーを公開せずに行う方法について説明する。

概要

マイナンバー占いとは、マイナンバーを持つ人物$A$と$B$の間で行う占いである。まず、$A$と$B$のマイナンバーをそれぞれ$N_A$と$N_B$とする。また、$N_A$の1桁目を$N_{A_1}$、2桁目を$N_{A_2}$とする。同様に$N_B$の1桁目を$N_{B_1}$、2桁目を$N_{B_2}$とする。
マイナンバー占いは次のように相性を決める。

1. $N_{A_i} = N_{B_i} (i = 1, 2, \dots, 12)$となる$i$を紙にメモする
2. メモされた数字のかぞえ、メモされた数字が$0$個だったら相性はよくなく、$12$に近ければ近いほど相性がよい¹

しかし、この占いをナイーブに二者間で実行しようとすると、$N_{A_1}$や$N_{B_5}$などを相手に公開しなければならず、他者にマイナンバーが流出する。そこでこの記事では各桁を公開することなく、マイナンバー占いを実行する方法について解説する。

ハッシュ関数

この占いを達成するには、ハッシュ関数と呼ばれる関数が必要になる。この関数は、入力された値から決った値を計算する関数であるが、出力された値から入力された値を計算するような逆関数が作れない関数である。このようなハッシュ関数として有名なアルゴリズムにSHA256やMD5といったものがあるが、これらは人間が紙やペンを使って計算するにはやや難しすぎるので、マイナンバー占いというカジュアルさにあわせたハッシュ関数を使う。
まず、素数$p$とその素数の生成元$g$を用意する。生成元とは、$1$から$p-1$までの全ての$x$について、$g^x \bmod p$が全て異なる値になるような$g$のことを指す。
これらを用いて、ハッシュ関数$H$を次のように定義する。

H(x) = g^x \bmod p

この関数によって得られたハッシュ値$H(x)$から$x$を求めることは、離散対数問題と呼ばれ困難なことが知られている。

電子署名

この占いではブラインド署名と呼ばれる技術が必要になる。ブラインド署名を解説する前に、それを構成するための署名について計算がシンプルなRSA署名を例に説明する。

RSA署名

電子署名とはそもそも、ある文書が確実にその署名鍵を持つ人が生成したことを示すための技術である。RSA署名では次のように署名を行う。
まず、署名者は素数$p, q$を生成し、検証鍵$(e, n = pq)$と署名鍵$d$を生成する。ただし、この検証鍵$e$と署名鍵$d$を全てのメッセージ$m$について、次が成り立つ。

(m^e)^d = (m^d)^e \equiv m \pmod{n}

この特徴を用いて、次のように$A$と$B$の間で署名をすることができる。

1. $A$は素数$p, q$を生成し、検証鍵$(e, n = pq)$を$B$へ送信する
2. $B$は検証鍵$(e, n)$を保存する
3. $A$は署名したいメッセージ$m$について、その署名$x = m^d \bmod n$を計算し$(m, x)$送信する
4. $B$は検証鍵$(e, n)$を用いて、$m = x^e \bmod n$が等しいことを調べる

このRSA署名は、素数$p, q$を知っている署名者は署名鍵$d$を容易に作れる反面、素因数分解の困難さから合成数$n$しか知らない検証者は署名鍵$d$を計算するのが困難であるという性質の上に成り立っている。

ブラインド署名

ブラインド署名はRSA署名とはやや異なり、「署名者が署名しているメッセージが分からない」という特徴を持つ。ブラインド署名は一般的な用途として電子投票などで使われている。さきほどのRSA署名を次のように改造することで得られる。

1. $B$はメッセージ$m$に検証鍵$(e, n)$と乱数$r$を用いて$x = r^e m \bmod n$を計算し$x$を$A$へ送信する

2. $A$は$x$に対して、署名鍵$d$を用いて$y = x^d \bmod n$を計算し$y$を$B$へ送信する

   y = x^d = (r^e m)^d = (r^e)^d m^d \equiv r m^d \pmod{n}
   

3. $B$は乱数²$r$を用いて$y / r \bmod n$を計算する

   y / r = (r m^d) / r \equiv m^d \pmod{n}
   

このようにすることで、$B$（検証者）は$A$（署名者）にメッセージ$m$を知られることなく$m^d \bmod n$を計算できている。

秘密共通集合計算によるプロトコル

ハッシュ関数$H$とブラインド署名を用いることで、マイナンバーを知られることなくマイナンバー占いができるようになる。次のようにする。

1. $A$はRSA署名の鍵生成を行い、検証鍵$(e, n)$を$B$へ送信する
2. $B$は乱数$r$を生成し、$s_i = r^e M_{B_i} \bmod n$を計算し、集合$\{s_i\}$を$A$へ送信する
3. $A$は$t_i = (s_i)^d \bmod n$を計算して、集合$\{t_i\}$を$B$へ送信する
4. $A$は$u_i = H\left((N_{A_i})^d \bmod n\right)$を計算して、集合$\{u_k\}$を$B$へ送信する
5. $B$は$v_i = H\left(t_i / r \bmod n\right)$を計算する
6. $B$は$u_i = v_i$となるか検証し、等しい$i$を紙にメモする
7. $B$はメモされた$i$を$A$に公開し、数をかぞえる

このようにすることで、マイナンバーを知られることなくマイナンバー占いを行うことができる。

まとめ

暗号技術を使うことで、マイナンバーを秘密にしたままマイナンバー占いを行うことができることを示した。この占いを応用すれば、たとえばマイナンバーを教えることなくマイナンバーの共通の約数を共有することなどができる。