Profile
理学部 数理科学科
キーワード
情報を安全に伝える「暗号」の秘密をのぞいてみよう！
共通鍵暗号と公開鍵暗号
コンピュータなどの情報のやり取りで利用される暗号には、大きく分けて2種類あります。情報の送信者が暗号化する時と受信者が暗号を読む時（復号）に共通の鍵を使う「共通鍵暗号」と、受信者が公開している鍵を使って送信者が情報を暗号化し、それを受信者が異なる鍵で復号化する「公開鍵暗号」です。共通鍵暗号は、古くから使われていましたが、鍵の共有方法が問題になり、20世紀後半に公開鍵暗号が開発されました。
素因数分解の困難さを利用した暗号
公開鍵暗号のなかで特に有名なのが、「RSA暗号」です。これは、「桁数の大きい自然数の素因数分解は時間がかかる」という特性を使った暗号です。例えば、素数31と79の積は2449ですが、2449を素因数分解しようとしても、簡単には31と79を割り出すことはできません。ここで使った数は2桁の素数ですが、桁数がもっと多くなれば、素因数分解はより困難になるため、暗号も破られにくくなるわけです。ただし、将来、コンピュータやアルゴリズムの進歩で、素因数分解が速くできる可能性もあるため、RSA暗号に代わる暗号も必要だと考えられています。
ポストRSA暗号として注目される楕円曲線暗号
RSA暗号に代わる暗号として注目されているものの1つに、「楕円曲線暗号」があります。楕円曲線とは、yの2乗＝xの3乗+ax+bで表される滑らかな平面3次曲線をいい、この曲線上の点と点との計算ルールを決めて計算すると、素因数分解同様、ある方向とは逆方向の計算が非常に難しくなります。この特徴を使うのが楕円曲線暗号です。例えば、楕円曲線上の点QがPのn倍である場合、PとQを公開してもnが簡単にはわからないため、簡単に暗号が破られないのです。しかも、楕円曲線暗号は、素因数分解に比べると扱う数のサイズを小さくできるため、データサイズも小さくできるというメリットもあります。また最近では、ペアリング暗号のような、楕円曲線を用いた新たな暗号方式も開発され、さらなる研究が進められています。
暗号に使う素数を判定する方法とは？
素因数分解の困難さを利用した暗号
情報の暗号化の方法の1つにRSA暗号があります。これは、「桁数が大きい素数同士を掛け合わせた数の素因数分解は簡単にはできない」という特質を利用した暗号の1つで、インターネットのセキュリティ技術に広く利用されています。RSA暗号を作るには、巨大な素数が必要になりますが、それにはまず、候補となる巨大な数が本当に素数なのかを判定する必要があります。
素数の判定は難しい！
素数判定のもっとも素朴な方法は、その数を2から順番に割っていくことです。例えば、nが素数であるかどうかを調べるためには、ルートnまで割っていきますが、nが、100桁であれば、50桁まで計算しなければならず、計算に莫大な時間がかかってしまい、実用的ではありません。そこでこれに代わる素数の判定アルゴリズムとして、2種類のアルゴリズム（計算の手順）を紹介します。
ミラー・ラビン素数判定法とAKS素数判定法
その1つは、「ミラー・ラビン素数判定法」で、素数だということをほぼ確実に判定する方法です。「ほぼ確実」ということは、100％判定できるわけではないという意味ですが、判定に失敗する確率が極めて低い上に、瞬時に判定できるという利便性から、広く利用されています。
100％正しく、かつ時間も短い判定方法を探すというのが数学者の信条ですから、その方法も長年追究されてきました。そして今世紀の初頭、確実に素数判定が可能で理論的に高速な、もう1つの「AKS素数判定法」という方法が開発されました。少し難解な説明になりますが、この方法は、リーマン予想などの仮説を用いることなく、決定性多項式時間（与えられた自然数nが素数であるかどうかの判定にかかる時間がlog(n) の多項式を上界とする時間）で判定できる初めてのアルゴリズムです。ただ、多項式の次数が高すぎることから、従来判定が不可能だった素数を高速に判定できるようになったわけではないという課題があります。
高校生・受験生の皆さんへのメッセージ
私の専門は整数論です。古くから研究されている素数の性質や方程式の整数解がどれくらいあるかといった問題を研究しています。昔はこうした問題は、手でたくさん計算して調べていましたが、最近は、コンピュータを使い、いろいろな実験をもとに予想を立てたり問題を解いたりできます。また、コンピュータの進歩にともない、「暗号理論」という新たな整数論の応用もできるようになってきました。数学やコンピュータに興味がある人は、東京都立大学で一緒に整数の世界を学んでいきましょう。
夢ナビ編集部監修
