p、qが小さい素数の場合に、公開鍵と秘密鍵を求めてみましょう。
(2)N=33(p=3、q=11)の場合
N=p×q=3×11と因数分解できる場合を考えます。(p-1) (q-1)=2×10=20です。N=33を法とする場合、剰余値には0~32までの33個の数しか現れません。表2にべき乗の法を33とした値を示します。2と10の最小公倍数(LCM)は10ですから、
・ n・LCM+1=11、21、31、41、51、61、・・・(n=1.2.3.・・・)
となります。21=3×7、51=3×17、91=7×13、111=3×37ですが、鍵の候補は、20以下の自然数なので、
・ (公開鍵、秘密鍵)=(3、7)、(3、17)、(7、13)
となります。公開鍵と秘密鍵を入れ替えても構いません。例えば、平文値が17の場合、公開鍵3を用いて17を法33の下で3乗して暗号値29を得ます。復号時には、秘密鍵7を用いて、29を法33の下で7乗すると元の値17に戻ります。3乗して7乗するので、平文値mが21乗され、元の値mに戻ります。
表2 べき乗の法を33とした値
(3)N=35(p=5、q=7)の場合
N=p×q=5×7と因数分解できる場合を考えます。(p-1) (q-1)=4×6=24です。N=35を法とする場合、剰余値には0~34までの35個の数しか現れません。表3にべき乗の法を35とした値を示します。4と6の最小公倍数(LCM)は12ですから、表3の暗号値は周期12で変化していることが分かります。
・ n・LCM+1=13、25、37、49、61、73、85、97・・・(n=1.2.3.・・・)
となります。鍵の候補は、24未満の自然数なので
・ (公開鍵、秘密鍵)=(5、5)、(7、7)、(5、17)(11、11)(7、19)
となります。公開鍵と秘密鍵を入れ替えても構いません。
表3 べき乗の法を35とした値
(4)N=85 (p=5、q=17)の場合
N=p×q=5×17と因数分解できる場合を考えます。(p-1) (q-1)=4×16=64です。N=85を法とする場合、剰余値には0~84までの85個の数しか現れません。表4にべき乗の法を85とした値を示します。4と16の最小公倍数(LCM)は16ですから、表4の暗号値は周期16で変化していることが分かります。
・ n・LCM+1=17、33、49、65、81、97、113、129・・・
となります。鍵の候補は、64未満の自然数なので
・ (公開鍵、秘密鍵)=(3、11)、(7、7)、(5、13)、(3、43)、(5、29)、(7、23)、(3,59)
となります。公開鍵と秘密鍵を入れ替えても構いません。実際の暗号にはもっと大きな数が用いられます。
表4 べき乗の法を85とした値
(5)N=20190707(p=4567、q=4421)の場合
2019年の七夕の日にちなみ20190707という比較的大きい数字を考えましょう。
・ N=20190707=4567×4421
と素因数分解できます。つまりN=20190707、p=4567、q=4421です。
・ (p-1)(q-1)=4566×4420=20181720
(=2 * 2 * 2 * 3 * 5 * 13 * 17 * 761)
を法(mod)とする剰余計算を行います。剰余計算とは、法で割った余りを与える計算です。
法(p-1)(q-1)と互いに素な自然数C(公開鍵)に対して、
・ C×D≡1 mod (p-1)(q-1) かつ 0≦D≦(p-1)(q-1)
を満たす数D(秘密鍵)が存在します。例えばC=707(=101×7)に対して、
・ 707×D≡1 mod 20181720 かつ 0≦D≦20181720
なる自然数Dは997525043です。なぜなら
・ 707×997525043=705250205401
・ 20181720×34945=705250205400
より
・ 707×997525043=20181720×34945+1
が成り立っているからです。受信者は、(N、C)=(20190707、707)を公開し、D=997525043は秘密鍵として非公開にします。送信者は、送りたいメッセ-ジを数字m(0≦m≦N)に変換し、公開鍵Cを用いて
・ K=m^C mod N
なる暗号文Kを送信します。暗号文Kは公開鍵から復号することはできません。受信者は、秘密鍵Dを用いて暗号文Kを復号し
・ m=K^D mod N
元のメッセ-ジmを得ることができます。代入すると
・ (m^C mod N)^D mod N=m^CD mod N=m ・・・(3)
となります。最後の等式(3)は、次に示すオイラ-の定理より、
・ CD≡1 mod (p-1)(q-1) かつ 0≦D≦(p-1)(q-1)
を満たす秘密鍵Dであれば、成り立ちます。Nを因数分解し、pとqを得られれば、(p-1)(q-1)を法として、公開鍵Cに対する秘密鍵Dを求めることができます。
(6)オイラ-の定理とは
オイラ-の定理とは、正整数m、Nに対して、m、Nが互いに素であるとき、
・ m^φ(N)≡1 mod N ・・・(4)
が成り立つというものです。ここでオイラー関数φ(N) は「Nより小さい正の整数のうち、Nと互いに素な数の個数」を表す関数です。素数Pの場合φ(P)=P-1となります。
・ φ(N)=φ(pq)=(p-1)(q-1)
となります。(2)式をv乗して、両辺にmをかけると
・ m^(φ(N)v+1)≡m mod N ・・・(5)
(3)と(5)を比較すると
・ CD=φ(N)v+1
を満たす整数Dとvが存在しれば、復号できることが分かります。一次不定方程式の整数解の定理により、Cとφ(N)が互いに素であれば、整数Dとvが存在します。もしDが負なら、
・ C(D+kφ(N))-φ(N)(v+kC)=1
と変形し、十分大きい数kを用いて、Dを正数D+kφ(N)に置き換えることができます。