公開鍵暗号方式について

1/7 公開鍵暗号方式について

2/7 暗号の歴史 ・暗号の歴史とは、暗号開発者と暗号解読者の知恵比べの歴史 ・紀元前20～19世紀頃から使われた「換字式暗号」が最古の暗号といわれる MARKERISE ４文字ずらす IWNGANEOA ・18世紀頃に電子機器が大きく発達し、暗号もより高度に進歩した。 ・やがて、暗号化と複合化に異なる鍵を利用する大革命が起きた

3/7 公開鍵暗号方式の考案 ・暗号化には誰でも入手できる公開鍵を使い、 複合化には本人しか知らない秘密鍵を使う方式が考案された 送信者 受信者 複合化 秘 秘 共 共 暗号化 この案によって鍵の交換を秘密裏に行う必要性がなくなり、 公衆の面前でも機密性を確立できると考えられた。

4/7 公開鍵暗号方式の実用化に向けて モジュラー算術と呼ばれる一方向関数(※)を用いることで、 公開鍵暗号方式の理論の雛形をつくった。 ※y=f(x)において、yからxを求められるが、 xからyを求めることができない関数 X Y = A (mod B) ・・・ AのX乗をBで割った余りがY ①. 送信者と受信者の間で、AとBを共有する (A = 4、B = 11とする) ②. 送信者と受信者は、それぞれ自分しか知らないX、xを決める (X = 3、x = 7とする) ③. 共有したAとB、それぞれのX、xからY、yが決まる (Y = 9、y = 5) ④. 自分のXを使い、Aに相手のYを代入して再びモジュラー算術を解く 3 7 5 (mod 11) = 4 9 (mod 11) = 4 得られた共通の解を公開鍵として使う この理論を実用化するべく、RSA暗号が考案された

5/7 RSA暗号 ・現代における、代表的な公開鍵暗号化アルゴリズム ・非常に大きな数値の素因数分解が困難であることを安全性の根拠とする e 平文mから暗号文cを作成 d 暗号文cから平文mを作成 暗号化：c = m (mod n) 複合化：m = c (mod n) 公開鍵{e, n}を知っていれば、自分の持っている秘密鍵dと合わせて、 平文mを容易に得ることができる。 秘密鍵dが不明な場合、nの素因数を知らなければmの計算は難しい。 そこで、nに膨大な数値を入れることで、素因数分解を困難にしている。

6/7 素因数分解の難しさ ・現在、RSAは最大4096ビット(約1200桁)の整数を扱える。 これを素因数分解するには、途方もない時間がかかる。 ・2020年8月時点で、世界最高レベルのコンピュータを用いても 829ビットの整数までしか素因数分解できなかった。 ・現在は、世界最高性能のスパコンを用いれば、RSA-1024を 1年未満で解読できるだろうと言われている ・例として、256×256の画像データ(約65000ピクセル)を暗号化する場合は 各ピクセルごとに暗号化するため、外部からの複合化は不可能に近い。

7/7 公開鍵暗号方式のこれから ・公開鍵暗号方式はRSA暗号化が主流となっているが、 より強固なアルゴリズムである楕円曲線暗号も実用化されている。 ・量子コンピュータは、素因数分解を高速に行うための高度な アルゴリズムを持つことができると期待されている。 ・RSA暗号化と楕円曲線暗号化はどちらも素因数分解が重要なので、 新しい手法に成り代わられる日が来る可能性が高いと考えられる