Cryptography

なぜ素因数分解が必要か？

あなたは気付かないかもしれないが暗号というものが身の周りに溢れている。 暗号(cryptography)とは情報の交換や記憶集積に際して、 第三者にそれが知られること、あるいはさらに当事者も含めて故意による情報の改変を防ぐため、 その対象となる情報を秘匿する技術や方法のことである。 いくつも発表された暗号の中でも比較的優れていてかつ実用的なものの一つがRSA暗号(Rivest,Shamir,Adleman,1977)である。 このRSA暗号の強度を保証しているのが非常に大きな二つの素数(200桁あるいはそれ以上)の積の素因数分解の困難さであり、 強度検証のために素因数分解の研究が必要なのである。

RSA暗号とは？

公開鍵暗号系の代表的な暗号システムがRSA暗号である。
(送信者 A、受信者 B)

• まず B は2つの大きな素数(200桁あるいはそれ以上) pとqを選ぶ。 そしてN=pqを計算する。
  
• λ=lcm(p-1,q-1)を計算し、gcd(d,λ)=1となるようなdを1つ選ぶ。
  
• 次に、条件ed≡1(mod λ)0＜e＜λ、を満たす整数eを計算する。 eは一意に決まる。B は eとNを公開し、d は B のみの秘密の鍵とする。 Bの準備は終了。

次に暗号化と復号化の手順を示す。
• A は B によって公開された e と N を得る。
  
• 暗号化メッセージ c を次のように計算する。
  　　　　　x^e≡ c (mod N)
  
• B は c を受けとり、次の方法で復号化する。
  　　　　　c^d≡ x (mod N)
  

盗聴者は、N と e を入手できる。 そこで、N を素因数分解して素数 p と q を求めれば d を求められるが、 N が 10^300 程になると素因数分解は簡単ではない。

素因数分解法の最も原始的な方法はBrute Force Methd という方法であるが、 300桁程度の整数をパソコン1台(Celeron300MHz)で素因数分解すると、 最悪の場合 10^136 年程かかるという結果が得られ、 この方法での素因数分解がいかに非現実的であるかがよくわかる。 これは、1万倍の性能を持つ CPU で素因数分解させたとしても10^82 年かかる ことを意味し、そのため、多くの研究者によっていろいろな素因数分解法が 発見されてきた。

どんな素因数分解法があるの？

• 力まかせ法

• ２次ふるい法