戻る / 次へ

はじめに

• この授業では公開鍵暗号の理論を題材にして、アルゴリズムとその計算量の理論の勉強をします。
• 公開鍵暗号では10進数で数百桁の整数を扱いますので、多倍長整数の計算をするプログラミング課題を出します。 （ Python や、java の BigInteger 等、多倍長整数の扱える言語を何かひとつ使えるようになりましょう。）
• 今日は、計算量理論の基礎である、ビット長や、四則演算（加減乗除）の計算量のお話です。

公開鍵暗号とは

「ネットワーク論」等で知識はあると思いますが、公開鍵暗号のポイントを押さえておきましょう：

• 公開鍵暗号では、暗号化に使う鍵（錠前）と復号に用いる鍵（キー）の２種類の鍵を使います。
• 送信者は、受信者が公開した暗号化鍵を用いて暗号文を作成し、受信者は、自分が秘密に保持している復号鍵を用いて復号を行います。
• 第三者に解読されないためには、暗号化鍵から復号鍵を計算できないことが必要です。
• 暗号化関数は一対一写像なので理論的には逆写像が存在するのですが、その計算には天文学的な時間が掛かるので事実上解読されない、という仕組みです。 多くの公開鍵暗号では、その仕組みを、整数関数を組み合わせて実現しています。

戻る / 次へ