コンピュータにおいて、
全てデータは2進の数値になっています。
よって平文も数値として捉えることができます。
本来の平文や鍵は、非常に大きな多倍長整数になりますが、
考え方が同じなので、簡単な数値で説明します。
なお、ここで示す考え方の基本は法の世界の理論に基づいています。
適当な2つの素数 P と Q を選びます。
これが秘密鍵の生成元です。(保持しなくてもよい秘密鍵といえます)
このP と Q の積Mを、
公開鍵の一つにします。
(P-1)×(Q-1)の
値Zに対して、
「互いに素となる関係」の値Eを選び、
それを、もう一つの公開鍵とします。
(たくさんある中より適当に選びます。)
「Zを法とした世界」で、
Eの逆数になる値Dを選び、
それを秘密鍵とします。
(
D×E≡1(mod Z)となる値で、
たくさんある中より適当に選びます。)
なお modは、余りを意味してます。上記は、左辺をZで割った余りが1になること表しています。
例
適当な2つの素数 P と Q を選びます。
これが秘密鍵の生成元です。(保持しなくてもよい秘密鍵といえます)
このP と Q の積Mを、
公開鍵の一つにします。
(P-1)×(Q-1)の
値Zに対して、
「互いに素となる関係」の値PEを選び、
それを、もう一つの公開鍵とします。
(・・・より適当に選びました。)
「Zを法とした世界」で、
PEの逆数になる値Dを選び、
それを秘密鍵とします。
(・・・より適当に選びました。)
これより、平文Xを暗号化したYは、
Y≡XE(mod M)の関係と
X≡YD(mod M)の関係とがあります。(公開鍵がE、秘密鍵がD)
Y≡XE(mod M)の式は
「Yは、Mを法としてXEと合同」と言います。
これは、YをMで割った余りと、XEをMで割った余りが
同じということです。
よって、Y<Mの関係であれば、
Yは、XEをMで割った余りとして求められます。
平文XをXとして、上記例を適用します。
公開鍵のMをM、EをEとすると、
XEをMで
割った余りのYが暗号文になります。
また、秘密鍵のDをDとすると、
YDをMで
割った余りのCが復号した平文になります。
最大公約数が 1 になる2つの整数の関係を「互いに素となる関係」と言います。
言い替えると、互いに素となる値とは、共通の素因数を持たない値です。
(その2つの値の最大公約数は1になります。)
また、Eの数を法にした世界で、(Z × D) mod E=1 となる D を、
Z の逆数と言います。
まとめ
P,Qを秘密キー生成用の秘密の素数とし、平文をNとすると
N(P-1)×(Q-1)≡1( mod (P×Q)) の関係があります。
m=(P×Q)と、
「(P-1)×(Q-1)」と互いに素となる適当な値eの2つを公開鍵とします。
また、e×d≡1( mod (P-1)×(Q-1) )を
満たすdを秘密鍵とします。
上記のmとeが公開鍵で、dを秘密鍵とした時、
平文Nから暗号文Cは、C=Ne(1 mod m) で求めららます。
暗号文Cから復号文Nは、N=Cd(1 mod m) で求めららます。