Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

RSA暗号化方式を紐解く その(2)

前回

RSA暗号化方式を紐解く その(1) - Pebble Coding

からの続きです。
暗号化は
c = {m} ^ {e} \mod n の式によって行い、
復号化は
m = {c} ^ {d} \mod n の式によって行います。
これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。
理論の根幹をなす定理がフェルマーの小定理を一般の整数に拡張したオイラーの定理です。

オイラーの定理
a>0, n>0 を互いに素な整数とした時、 {a} ^ { \phi (n) } = 1 \mod nが成り立つ。
ここで\phi (n)オイラーのファイ関数と呼び、1以上n未満の整数に対し、nと違いに素な数字の個数です。

a,bが違いに素な整数というのはa,bが2以上の同じ素因数を持たないということです。
言い換えるとa,bの最大公約数が1とも言えます。
整数a,bに対してa,bの最大公約数(greatest common divisor)をgcd(a,b)と表現します。
つまりgcd(a,b) = 1とも書けます。

唐突ですが、オイラーの定理でnを二つの素数p,qを掛けた値としておきましょう。
つまり、n=pqです。 このときのオイラーのファイ関数の値を算出してみます。
nが一般の整数の場合、ファイ関数の値を求めるのは大変ですが、条件がついた値なら値を求めるのは簡単です。
cが素数のとき、  {\phi ( c )} の値はc-1です。
なぜなら、cは素数なのでそれ未満の整数{1, 2, 3, ..., c-1}はcを割り切れないからです。
nが2つの素数p, qの積(n=pq)の場合の \phi(n)はどうなるでしょうか。
1以上でn=pq未満の整数は全部でpq-1個あります。
1以上でpの倍数である集合P{p, 2p, 3p, ... , (q-1)p}はpqと互いに素ではありませんからq-1個は取り除く必要があります。
同様に1以上、qの倍数である集合Q{q, 2q, 3q, ..., (p-1)q}はpqと互いに素ではありませんからp-1個は取り除く必要があります。
ここでp,qを違いに素とするとこの集合P,Qは重複しないことがわかるので、結局
ファイ関数の値は \phi(pq) = pq-1-(q-1)-(p-1)=pq-q-p+1=(p-1)(q-1)となります。

ここで一つの定理を証明しておきます。

aを整数、p,qを異なる素数のとき、
 a \mod p = 1
 a \mod q = 1
であるとき、
 a \mod pq = 1 である。

証明:
k,lを整数とし、
a = pk +1 式(A)
a = ql + 1
と書けます。
したがって、pk=qlが成り立つ。
p,qは異なる素数なので、kはqの素因数を持ちます。つまり、mを整数とし、
k=qmと書けます。
式(A)に入れると
a = pqm + 1
つまり
 a \mod pq = 1
証明終わり。

eを、2以上(p-1)(q-1)未満で(p-1)(q-1)と互いに素な整数として選びます。
通常はeとして素数ではない数 65576={2}^{16} + 1= 2 * 2 * 2 * 7 * 1171 が使われます。
なぜこの値を使うのかに関してはさらに説明が必要なのでここでは省略します。
実装するときは、(p-1)(q-1)が65576と互いに素となるように素数p,qを選びます。

次にdを、2以上(p-1)(q-1)未満で
ed=1 mod (p-1)(q-1)となるように選びます。
つまり、kを整数として、ed = (p-1)(q-1)k +1と書けるようにd,kを選びます。
これが可能なことは次の定理が示しています。

定理
a,bを整数とするとき、
ax+by = gcd(a,b)
を満たす整数x,yが存在する。

この定理で、a=e, b=-(p-1)(q-1)と置くと、gcd(a,b)=1であり、 ex-(p-1)(q-1)y = 1を満たすxが存在するということです。
xが負の値になってしまった場合は、fと整数として
e(x + (p-1)(q-1)f)-(p-1)(q-1)(y + ef)=1
のように変形できるので、x'=x + (p-1)(q-1)fを正の値にできます。
この求めたxをdとします。

({m} ^ {e}) ^ {d} \mod p = {m} ^ {ed} \mod p = {m} ^ {(p-1)(q-1)k + 1} \mod p = {({m} ^ {(q-1)k})} ^ {p-1} m \mod p
オイラーの定理{a} ^ {p-1} \mod p = 1を用いると最後の式は、
 = 1 m \mod p = m \mod p
となります。 同様に、
 ({m} ^ {e}) ^ {d} \mod q = m \mod q
が成り立ち、少し前で証明した定理を用いると、
 ({m} ^ {e}) ^ {d} \mod pq = m \mod pq
これは、c= {m} ^ {e} \mod pqとしたときに、
 {c} ^ {d} = m \mod pq
となることを示しています。ここでn=pqで最初の暗号化が正しいことが分かりました。

実装する際はnのビット数が2048になるようにするので、p,qそれぞれが1024ビットの素数擬似乱数とミラーラビン法で選び、 p-1,q-1 がe=65537と互いに素であるようにし、pとqの値が異なるように選びます。
dはただ一つに決まります。