Pebble Coding

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

RSA暗号の原理を理解するための数学知識

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、
色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

まずモジュラー演算記号(mod)を覚えましょう。
 a = b \mod n
これは整数aを整数nで割った余りとbを整数nで割った余りが等しいことを表します。
例:
 9 \mod 4 = 1
 107 \mod 10 = 7

モジュラー演算には以下の性質があります。

 a = b \mod n, \\
c = d \mod n 

のとき、

 a + c = b + d \mod n

 a * c = b * d \mod n

 a^{m} = b^{m} \mod n

である。

 ef = eg \mod n で gcd(e, n) = 1 ならば
 f = g \mod n
である。
ここで gcd(a, b) は整数a,bの最大公約数(Greatest Common Divisor)を表します。

合同式の意味とよく使う6つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、  a^{\phi(n)} = 1 \mod n である。
 \phi(n) は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 \phi(p) = p-1 となる。

また、p, qが素数の場合、2つをかけた合成数 pq に対して \phi(pq) = (p-1)(q-1)が成り立つ。

RSA暗号の世界 – まいとう情報通信研究会

RSAのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
 m = n \mod p
 m = n \mod q
であれば
 m = n \mod pq   である。

中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語