この記事は FUJITSU Advent Calendar 2020 の11日目の記事です。
素因数分解問題や離散対数問題などの数学的な問題を利用して公開鍵暗号が構成されているのは有名です。数学的問題を解くことの難しさが暗号解読の難しさを保証しているのです。今回の記事では、素因数分解問題を解く難しさと、暗号解読の難しさが等価になる(つまり、素因数分解問題が解ければ暗号が解読でき、逆に暗号が解読できれば素因数分解問題が解ける)ような公開鍵暗号を紹介します。具体的には、Rabin 暗号, Williams 暗号, 逆数暗号の3つの公開鍵暗号について取り上げます。全てを理解するには初等整数論の知識が必要となるので、大学の講義１コマ分では厳しいかもしれません。しかし流れだけなら理解頂けるのではないかと期待しています。
はじめに (RSA暗号の場合)
素因数分解問題を利用した公開鍵暗号として RSA 暗号が有名です。しかし RSA 暗号の場合、素因数分解問題の難しさと RSA 暗号の解読の難しさは等価ではありません。以下、RSA 暗号のアルゴリズムを復習した後で、素因数分解問題と暗号解読問題を考察します。
鍵生成 (RSA 暗号)
- 奇素数 $p$, $q$ を生成し、合成数 $n=p \times q$ を計算する。
- 自然数 $(p-1)(q-1)$ と互いに素な自然数 $e$ を選択する。
- $de \equiv 1 \pmod{(p-1)(q-1)}$ となる自然数 $d$ を計算する (この計算は拡張 Euclid 互除法により簡単に計算できる)。
- ${\sf pk}=(n,e)$ を公開鍵、${\sf sk}=(p,q,d)$ を秘密鍵として出力する。
補足1
素数 $p,q$ は奇数なので、$(p-1)(q-1)$ は偶数になります。従って、鍵生成の手順により、自然数 $e$ も必ず奇数になります。
暗号化 (RSA 暗号)
暗号化したい(自然数で表された)平文 $m \in (Z/nZ)^{*}$ に対し $c = m^e \bmod{n}$ を計算し、自然数 $c \in (Z/nZ)^{*}$ を暗号文として出力する。
復号 (RSA 暗号)
復号したい(自然数で表された)暗号文 $c \in (Z/nZ)^{*}$ に対し $m = c^d \bmod{n}$ を計算し、自然数 $m \in (Z/nZ)^{*}$ を復号文として出力する。
安全性に関する検討 (RSA 暗号)
まず、攻撃者が素因数分解問題を解ける、つまり与えられた自然数を効率的に素因数分解するアルゴリズム F を利用可能である場合を考えます。攻撃者は公開鍵 ${\sf pk}=(n,e)$ を入手できるので、アルゴリズム $F$ に合成数 $n$ を入力することで、素数 $p, q$ を得られます。すると攻撃者は鍵生成と同じ手順により、$de \equiv 1 \pmod{(p-1)(q-1)}$ を満たす自然数 $d$、つまり秘密鍵を求められるので、結局、攻撃者は任意の暗号文 $c$ を復号(解読)することが可能になります。このように RSA 暗号では、素因数分解問題を解ければ暗号文を解読できることがわかります。
逆に攻撃者は RSA 暗号を解読できる、つまり与えられた RSA 暗号の暗号文 $c$ を効率的に解読するアルゴリズム B が利用可能である場合を考えます。このときアルゴリズム B の能力を考えてみましょう。まず、アルゴリズム B が素因数分解できる能力を持っていれば、アルゴリズム B に入力された任意の暗号文を解読できます。しかし素因数分解する能力を持たずとも(素因数分解せずに)暗号文を解読する可能性が残ります。このように RSA 暗号では、暗号を解読できたからと言っても、素因数分解できるとは限りません。
まとめると、 RSA 暗号では素因数分解の難しさと暗号解読の難しさは等価ではないことがわかりました。(ただし、アルゴリズム B が素因数分解をすることなく暗号解読する方法は知られていませんし、そもそも困難だろう考えられているので、これら2つの問題は限りなく等価であると考えられています。)
以下では、素因数分解の難しさと暗号解読の難しさが等価であるような公開鍵暗号として、Rabin 暗号, Williams 暗号, 逆数暗号を紹介します。Rabin 暗号はこのような安全性を保証された最初の公開鍵暗号ですが、復号が一意性を持たない (復号において、復号文の候補が複数得られる)という問題点があります。Williams 暗号は Rabin 暗号における復号が一意的になるように改良した暗号ですが、なおも制限が残っています。逆数暗号は一意性を保ちつつ、Williams 暗号の課題を解消した公開鍵暗号です。
Rabin 暗号
鍵生成 (Rabin 暗号)
- 奇素数 $p, q$ を生成し、合成数 $n=p \times q$ を計算する。
- ${\sf pk}=n$ を公開鍵、${\sf sk}=(p,q)$ を秘密鍵として出力する。
暗号化 (Rabin 暗号)
暗号化したい(自然数で表された)平文 $m \in (Z/nZ)^{*} $ に対し $c=m^2 \bmod{n}$ を計算し、自然数 $c \in (Z/nZ)^*$ を暗号文として出力する。
復号 (Rabin 暗号)
- 復号したい(自然数で表された)暗号文 $c \in (Z/nZ)^{*}$ に対し、二次方程式 $x^2 \equiv c \pmod{p}$ の解 $m_p$, $p-m_p$ と、$x^2 \equiv c \pmod{q}$ の解 $m_q$, $q-m_q$ を求める。
- 拡張 Euclid 互除法を用いて、$pX + qY = 1$ となる整数 $X, Y$ を求める。
- $m_1 = (pX m_q + qY m_p) \bmod{n}$, $m_2 = n-m_1$, $m_3 = (pX m_q - qY m_p) \bmod{n}$, $m_4 = n-m_3$ を計算する。(このとき $m_1^2 \equiv m_2^2 \equiv m_3^2 \equiv m_4^2 \equiv c \pmod{n}$ となり、$m_1, m_2, m_3, m_4$ は $x^2 \equiv c \pmod{n}$ の 4 つの解になっている。)
- 平文に関する何らかの補助情報を利用して、$m_1, m_2, m_3, m_4$ のいずれかを復号文 $m$ として選択し、出力する。
補足2
Rabin 暗号の提案論文では、暗号化関数は $c = m(m+b) \pmod{n}$ ($b$ は定数で、公開鍵として扱われる) となっているのですが、簡単のために本記事では $b=0$ として説明します。$b=0$ でも Rabin 暗号の本質は何も失われませんので、ご安心下さい。
補足3
Rabin 暗号における暗号化の操作は、RSA 暗号において $e=2$ とした場合に相当しています。しかし補足1で指摘したように、RSA 暗号においては $e \ne 2$ なので、RSA 暗号と Rabin 暗号の重なりはありません。
補足4
法 $p,q$ での二次方程式の解は 2 個存在することと、$\gcd((p-1)(q-1),2)=2$ であることから、二次方程式 $x^2 \equiv c \pmod{n}$ の解は 4 個存在します。復号の操作で得られる $m_1,m_2,m_3,m_4$ が復号文の候補となることは以下のようにして確認できます。
- $m_1^2 \equiv (pX m_q + qY m_p)^2 \equiv p^2 X^2 m_q^2 + q^2 Y^2 m_p^2 \equiv p^2 X^2 (c^2 + sq) + q^2 Y^2 (c^2 + tp) \equiv (p^2 X^2 + q^2 Y^2 ) c^2 \equiv (p^2 X^2 + 2pqXY + q^2 Y^2) c^2 \equiv (pX+qY)^2 c^2 \equiv c^2 \bmod{n}$ (ただし、$m_p^2 = c^2 \bmod{p}, m_q^2 = c^2 \bmod{q}$ となるを用いた)
- $m_2^2 \equiv (n-m_1)^2 \equiv m_1^2 \equiv c^2 \bmod{n}$
- $m_3, m_4$ も同様
補足5
素数 $p$ に対し、法 $p$ における平方根 $x^2 \equiv c \bmod{p}$ は効率的に解けることが知られています。しかし、合成数 $n=p \times q$ の素因数分解を知らない場合、法 $n$ における平方根 $x^2 \equiv c \bmod{n}$ の効率的な解き方は知られていません。Rabin 暗号はこのギャップを利用して暗号を構成しています。
数値例 (Rabin 暗号)
-
鍵生成: $p=43$, $q=47$ とします。このとき $=p \times q = 43 \times 47 = 2021$ です。よって公開鍵は ${\sf pk}=n=2021$, 秘密鍵は ${\sf sk}=(p,q)=(43,47)$ となります。
-
暗号化: 例として $m=126$ を暗号化をしてみましょう。公開鍵は ${\sf pk}=n=2021$ なので、定義により、暗号文は $c=m^2 \bmod{n}=126^2 \bmod{2021} = 1729$ となります。
-
復号: 秘密鍵 ${\sf sk}=(p,q)=(43,47)$ と暗号文 $c=1982$ に対し、二次方程式 $x^2 \equiv c \pmod{p}$ の解 $x = 3, 40$, $x^2 \equiv c \pmod{q}$ の解 $x=15,32$ が得られます (以下、$m_p=3$, $m_q=15$ とおきます)。拡張 Euclid 互除法により $pX+qY=1$ の解として $X=-12, Y=11$ とおくと
\begin{align}
m_1 & = (pXm_q+qYm_p) \bmod{n}=(43\times (-12)\times 15 + 47 \times 11 \times 3) \bmod{2021} = 1895 \\
m_2 & = n-m_1=126 \\
m_3 & = (pXm_q-qYm_p) \pmod{n}=(43\times(-12)\times 32 - 47 \times 11 \times 40) \pmod{2021} = 1207 \\
m_4 & = n-m_3 = 814
\end{align}
が得られます。よって、確かにもとの平文 $m=126$ が $m_2$ として求められていることがわかります。
安全性に関する検討 (Rabin 暗号)
それでは Rabin 暗号の安全性について考えていきます。
まず、攻撃者が素因数分解問題を解ける、つまり与えられた自然数を効率的に素因数分解するアルゴリズム F を利用可能である場合を考えます。攻撃者は公開鍵 ${\sf pk}=n$ を入手できるので、アルゴリズム F に合成数 $n$ を入力することで素数 $p,q$ を得られます。すると任意の暗号文 $c$ を復号し、平文の全ての候補 $m_1, m_2, m_3, m_4$ を求めることができます。つまり Rabin 暗号では、素因数分解ができれば暗号を解読することが可能であることがわかります。
逆に攻撃者は Rabin 暗号を解読できる、つまり与えられた Rabin 暗号の暗号文 $c$ を効率的に解読し、復号文として4つの平文候補のいずれかを出力するアルゴリズム B が利用可能である場合を考えます。素因数分解したい合成数 $n$ に対し、攻撃者は自分で適当に平文 $m$ を生成し、暗号文 $c = m^2 \bmod{n}$ を求め、アルゴリズム B に入力し、復号文 $\tilde{m}$ を得ます。このとき、$\gcd(m-\tilde{m},n)$ は確率 $1/2$ で $n$ の素因数 (つまり $p$ または $q$) を出力します。例えば
\begin{align}
\gcd(m_1-m_1,n) &= \gcd(0,n) = n \\
\gcd(m_1-m_2.n) &= \gcd(2m_1,n) = 1 \\
\gcd(m_1-m_3,n) &= \gcd(2qYm_p,n) = q \\
\gcd(m_1-m_4,n) &= \gcd(2pXm_q,n) = p
\end{align}
となっているので、平文 $m$ が Rabin 暗号の復号操作で説明した $m_1$ のタイプの平文であったとすると、確かに確率 $1/2$ で $n$ の素因数分解が得られることがわかります。$m$ が他のタイプになる場合も同様です。$n$ の素因数分解ができてなかった場合、他の平文 $m$ に対して同じ操作を繰り返すことで、高い確率で $n$ の素因数分解を求めることができます。
まとめると、Rabin 暗号では素因数分解の難しさと暗号解読の難しさは等価、つまり素因数分解できれば暗号は解読できるし、暗号が解読できれば素因数分解ができることがわかります。
数値例 (Rabin 暗号の続き)
さきほどの数値例では、平文 $m=126$ に対し、復号文の候補は $m_1=1895, m_2=126, m_3=1207, m_4=814$ となります。このとき
\begin{align}
\gcd(m-m_1,n) &= \gcd(1769,2021) = 1 \\
\gcd(m-m_2.n) &= \gcd(0,2021) = 2021 \\
\gcd(m-m_3,n) &= \gcd(688,2021) = 43 \\
\gcd(m-m_4,n) &= \gcd(1081,2021) = 47
\end{align}
となり、確かに確率 $1/2$ で $n$ の素因数が得られることがわかります。
(なお $m=126$ は $m_2$ タイプなので、$\gcd$ のパターンはさきほどの例と異なっていることに注意して下さい。)
まとめ (Rabin 暗号)
Rabin 暗号は、解読の難しさが素因数分解問題の難しさと等価である公開鍵暗号ですが、復号が一意的ではないため、現実的な利用には適しません。そこで、Williams 暗号と逆数暗号は、Rabin 暗号が持つ安全性を保持しつつ、復号が一意的となるような工夫を盛り込んできます。
Williams 暗号
Williams 暗号は、復号の一意性を確保するために、Rabin 暗号の使用するパラメータに制限を加えます。
準備 (Legendre 記号)
素数 $p$ に対し、法 $p$ の二次方程式 $x^2 \equiv a \pmod{N}$ の解が存在するとき、$a$ は法 $p$ において平方剰余であるといい、逆に解が存在しないとき、$a$ は法 $p$ において平方非剰余であるといいます。
素数 $p$ と、$p$ に互いに素な自然数 $a$ に対し、Legendre 記号 $\left( \frac{a}{p} \right)$ を以下のように定めます。
\left( \frac{a}{p} \right) = \left\{
\begin{array}{ll}
1 & a が平方剰余 \\
-1 & a が平方非剰余
\end{array}
\right.
このとき $\left( \frac{a}{p} \right) = a^{(p-1)/2} \bmod{p}$ という関係式が成立します。これを Euler 規準と呼びます。
準備 (Jacobi 記号)
Legendre 記号を合成数の場合に拡張したのが Jacobi 記号です。合成数 $N=p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$ と、$N$ と互いに素な自然数 $a$ に対し、Jacobi 記号 $\left( \frac{a}{N} \right)$ を以下のように定めます。
\left( \frac{a}{N} \right) = \left( \frac{a}{p_1} \right)^{e_1} \left( \frac{a}{p_2} \right)^{e_2} \dots \left( \frac{a}{p_n} \right)^{e_n}
特に、$n=p \times q$ のときは
\left( \frac{a}{n} \right) = \left( \frac{a}{p} \right) \left( \frac{a}{q} \right)
となります。
定義より、自然数 $a$ が法 $N$ において平方剰余ならばそのヤコビ記号の値は 1 になりますが、Jacobi 記号の値が 1 でも平方剰余になるとは限らないことに注意して下さい。
準備 (Blum 素数)
2 以外の素数は奇数なので、4 で割った余りは 1 または 3 となります。素数の内、4 で割った余りが 3 になる素数を Blum 素数と呼びます。
$p$ が Blum 素数であるとき、以下のような性質が成り立ちます:
- 法 $p$ の二次方程式 $x^2 \equiv c \pmod{p}$ の解が存在するとき、その解は $x \equiv \pm c^{\frac{p+1}{4}} \pmod{p}$ で与えられる。
- 法 $p$ の二次方程式 $x^2 \equiv -1 \pmod{p}$ の解は存在しない。つまり $\left( \frac{-1}{p} \right) = -1$ である。
鍵生成 (Williams 暗号)
- Blum 素数 $p,q$ を生成し、合成数 $n=p×q$ を計算する。
- ${\sf pk}=n$ を公開鍵、${\sf sk}=(p,q)$ を秘密鍵として出力する。
暗号化 (Williams 暗号)
暗号化したい(自然数で表された)平文 $m \in (Z/nZ)^{*}$ は $\left( \frac{m}{n} \right)=1$ かつ $0 < m < n/2$ を満たすとするとき、$c=m^2 \bmod{n}$ を計算し、自然数 $c \in (Z/nZ)^*$ を暗号文として出力する。
復号 (Williams 暗号)
- Rabin 暗号の復号と同じ手順により、復号文の 4 つの候補 $m_1, m_2, m_3, m_4$ を求める。
- これら候補の中から、条件 $\left( \frac{m}{n} \right)=1$ かつ $0 < m < n/2$ を満たすものを見つけ、復号文 $m$ として出力する。
補足6
まず
\left( \frac{m_1}{n} \right) \left( \frac{m_2}{n} \right)
= \left( \frac{m_1}{n} \right) \left( \frac{n-m_1}{n} \right)
= \left( \frac{m_1}{n} \right) \left( \frac{-m_1}{n} \right)
= \left( \frac{-1}{n} \right) \left( \frac{m_1}{n} \right)^2
= \left( \frac{-1}{p} \right) \left( \frac{-1}{q} \right) = 1
より $\left( \frac{m_1}{n} \right)$ と $\left( \frac{m_2}{n} \right)$ は同じ値であることがわかります。同様に $\left( \frac{m_3}{n} \right)$ と $\left( \frac{m_4}{n} \right)$ も同じ値です。
他方で
\left( \frac{m_1}{n} \right) \left( \frac{m_3}{n} \right)
= \left( \frac{pXm_q+qYm_p}{n} \right) \left( \frac{pXm_q-qYm_p}{n} \right)
= \left( \frac{pXm_q+qYm_p}{p} \right) \left( \frac{pXm_q+qYm_p}{q} \right) \left( \frac{pXm_q-qYm_p}{p} \right) \left( \frac{pXm_q-qYm_p}{q} \right) = \left( \frac{qYm_p}{p} \right) \left( \frac{pXm_q}{q} \right) \left( \frac{-qYm_p}{p} \right) \left( \frac{pXm_q}{q} \right)
= \left( \frac{-1}{q} \right) \left( \frac{qYm_p}{p} \right)^2 \left( \frac{pXm_q}{q} \right)^2 = -1
より $\left( \frac{m_1}{n} \right)$ と $\left( \frac{m_3}{n} \right)$ は異なる値であることもわかります。
また、$m_2=n-m_1$, $m_4=n-m_3$ という定義から、$m_1, m_2$ のどちらか一方と $m_3, m_4$ のどちらか一方は $0 < m_i < n/2$ を満たすことがわかります。
これらのことから、$m_1,m_2,m_3,m_4$ のうち、条件 $\left( \frac{m}{n} \right)=1$ かつ $0 < m < n/2$ を満たすものは必ず 1 つ存在することがわかり、Williams 暗号の復号は一意的であることがわかります。
数値例 (Williams 暗号)
Rabin 暗号の数値例で用いた素数 $p=43$, $q=47$ はどちらも Blum 素数です。また、平文 $m=126$ は法 $n = p \times q = 2021$ のもとで平方剰余となっており、$0 < m < n/2$ を満たしています。従って、Rabin 暗号の数値例は Williams 暗号の数値例にもなっています。
平文の候補 $m_1=1895, m_2=126, m_3=1207, m_4=814$ に対しては、$0<m<n/2$ になることから $m_2, m_4$ に絞り込まれ、それぞれ
$$
\left( \frac{m_2}{n} \right) = \left( \frac{126}{2021} \right) = 1
$$
$$
\left( \frac{m_4}{n} \right) = \left( \frac{814}{2021} \right) = -1
$$
となることから、復号文として $m_2=126$ が出力されます。
安全性に関する検討 (Williams 暗号)
Williams 暗号の安全性について考えます。
攻撃者が素因数分解問題を解ける場合は、Rabin 暗号の場合と全く同じ議論によって、Williams 暗号の解読が可能になります。
逆に攻撃者は Williams 暗号を解読できる、つまり与えられた Williams 暗号の暗号文を効率的に解読し、平文 $m$ を出力するアルゴリズム B が利用可能である場合を考えます。この場合、Williams 暗号の復号は一意的なので、攻撃者が自分で生成した平文 $m$ をもとに暗号文を計算し、それをアルゴリズム B に入力して復号文 $\tilde{m}$ を入手できますが、$m=\tilde{m}$ となるため、素因数分解ができません。そこで攻撃者は平文 $m$ を選択する際に、条件 $\left( \frac{m}{n} \right)=1$ や $0 < m < n/2$ を満たさないように選択します。このとき、攻撃者が入手する出力 $\tilde{m}$ は $m$ とは異なりますので、攻撃者は素因数分解が可能となります。なお、攻撃者がこのように正規でない平文 $m$ を使用したとしても、対応する暗号文と、正規な平文から生成される暗号文は同じになるため、アルゴリズムはもともとの平文が正規かどうかを判定することはできません。
以上より、Williams 暗号においても、素因数分解の難しさと暗号解読の難しさの透過性が維持されていることがわかります。
まとめ (Williams 暗号)
Williams 暗号は、復号が一意的となるように Rabin 暗号の欠点を克服した公開鍵暗号り、解読の難しさが素因数分解問題の難しさと等価になっています。しかし平文に対して条件が課されているため、利便性に劣ります (特に平文の Jacobi 記号の値が 1 であるべしという条件は使い勝手が悪いです)。
逆数暗号
逆数暗号は、Rabin 暗号の欠点を (Williams暗号とは別の方法で) 克服した公開鍵暗号です。復号の一意性を確保するために、Williams 暗号は平文に対して条件を課したのに対し、逆数暗号は平文を特定するための情報も受信者に送るというアプローチをとっています。
鍵生成 (逆数暗号)
- 奇素数 $p,q$ を生成し、合成数 $n=p \times q$ を計算する。
- $\left( \frac{\alpha}{p} \right) = \left( \frac{\alpha}{q} \right) = -1$ を満たす自然数 $\alpha \in (Z/nZ)^{*}$ を選ぶ。
- ${\sf pk}=(n,\alpha)$ を公開鍵、${\sf sk}=(p,q)$ を秘密鍵として出力する。
暗号化 (逆数暗号)
暗号化したい(自然数で表された)平文 $m \in (Z/nZ)^{*}$ に対し $r = \left( m + \frac{\alpha}{m} \right) \bmod{n}$ を計算する。また、以下の定義に従ってパラメータ $s,t$ を求め、$c=(r,s,t)$ を暗号文として出力する。
s = \left\{
\begin{array}{ll}
0 & {\rm if}~\left( \frac{m}{n} \right)=1 \\
1 & {\rm if}~\left( \frac{m}{n} \right)=-1
\end{array}
\right.
t = \left\{
\begin{array}{ll}
0 & {\rm if}~\left( \frac{\alpha}{m} \bmod{n} \right) > m \\
1 & {\rm if}~\left( \frac{\alpha}{m} \bmod{n} \right) < m
\end{array}
\right.
復号 (逆数暗号)
-
法 $p$ における二次方程式 $x^2 - rx + \alpha \equiv 0 \pmod{p}$ の解 $a_1, a_2$ を求める。このとき解と係数の関係から $a_1 a_2 \equiv \alpha \pmod{p}$ となるので、
$$ \left( \frac{a_1}{p} \right) \left( \frac{a_2}{p} \right) = \left( \frac{\alpha}{p} \right) = -1$$
が成立する。そこで $\left( \frac{a_1}{p} \right)=1$, $\left( \frac{a_2}{p} \right)=-1$ となるように $a_1, a_2$ を定める。同様に法 $q$ における二次方程式 $x^2 - rx + \alpha \equiv 0 \pmod{q}$ の解 $b_1, b_2$ を求める。同様にして、
$\left( \frac{b_1}{p} \right)=1$, $\left( \frac{b_2}{p} \right)=-1$ となるように $b_1, b_2$ を定める。 -
拡張 Euclid 互除法により、$pX+qY=1$ となる自然数 $X,Y$ を求める。このとき、平文の 4 つの候補 $m_1, m_2, m_3, m_4$ は以下のように表すことができる。
\begin{align}
m_1 &= pXb_1 + qYa_1 \\
m_2 &= pXb_2 + qYa_2 \\
m_3 &= pXb_2 + qYa_1 \\
m_4 &= pXb_1 + qYa_2
\end{align}
このとき
\begin{align}
\left( \frac{m_1}{n} \right) &= \left( \frac{m_1}{p} \right) \left( \frac{m_1}{q} \right) = \left( \frac{a_1}{p} \right) \left( \frac{b_1}{q} \right) = 1 \\
\left( \frac{m_2}{n} \right) &= \left( \frac{m_2}{p} \right) \left( \frac{m_2}{q} \right) = \left( \frac{a_2}{p} \right) \left( \frac{b_2}{q} \right) = 1 \\
\left( \frac{m_3}{n} \right) &= \left( \frac{m_3}{p} \right) \left( \frac{m_3}{q} \right) = \left( \frac{a_1}{p} \right) \left( \frac{b_2}{q} \right) = -1 \\
\left( \frac{m_4}{n} \right) &= \left( \frac{m_4}{p} \right) \left( \frac{m_4}{q} \right) = \left( \frac{a_2}{p} \right) \left( \frac{b_1}{q} \right) = -1
\end{align}
となるので、$s=0$ ならば平文の候補は $m_1$ または $m_2$ に、
$s=1$ ならば平文の候補は $m_3$ または $m_4$ に絞り込まれる。
$s=0$ の場合を考えると、$m_1, m_2$ は法 $n$ の二次方程式 $x^2-rx+\alpha \equiv 0
\pmod{n}$ の解なので、解と係数の関係より $m_1 m_2 \equiv \alpha \pmod{n}$、つまり $m_2 = \frac{\alpha}{m_1} \bmod{N}$ となる。よって $t=0$ なら $m=m_1$ が、$t=1$ なら $m=m_2$ が復号文として一意的に定まる。$s=1$ の場合も同様である。
まとめ
素因数分解の難しさと解読の難しさが等価な暗号として、Rabin暗号, Williams暗号, 逆数暗号の 3 つを紹介しました。