秘密鍵と公開鍵、RSA暗号の仕組み
公開鍵と秘密鍵とは
普段スマホアプリをGooglePlayに公開するときにデジタル証明書を使いますが、このあたりの勉強をしている時に暗号の分野で公開鍵と秘密鍵の話が出てきました。
過去に大学の代数学で勉強したことを思いだし、これらの暗号を勉強しなおしながらコードを書いてみようと思いました。
では早速ですが、公開鍵と秘密鍵とは何でしょうか。
そもそも暗号化する目的は、相手とのやり取りを第三者に知られないように違う文字(暗号)などに置き換えて送付、受け取った側はそれを複合し正しい文章を読むためです。この2人には互いに暗号複合するための鍵を持っており、この鍵を知らない第三者は読むことができなくなります。
この鍵の仕組みには今回紹介する公開鍵と秘密鍵以外にも共通鍵というものも存在していますが、共通鍵はセキュリティの問題から公開鍵と秘密鍵を使うことの方が多いようです。
そこで、本題の公開鍵と秘密鍵ですが、今回は文章を受診するA社と文章を送付するB社について公開鍵と秘密鍵を説明していきます。
公開鍵はその名前の通り、公開している鍵でA社B社以外の第三者に見られても問題ない鍵のことで、逆に秘密鍵は一切公開しない鍵で、暗号されたものを複合するときに使います。
これだけ聞くと「鍵を第三者に知られたらセキュリティ的に問題では？」と思うかもしれませんが、B社の公開鍵で暗号化されたものはA社の持つ秘密鍵でしか複合できません。そのため公開鍵を使って暗号化した文章をA社以外が確認することはできません。
間違えて違う会社に送付しても大丈夫！！（だからって誤送信は絶対ダメ）
RSA暗号を使ったやり取り
先ほど説明した公開鍵と秘密鍵に使われているアルゴリズムはRSA暗号というものです。
RSA暗号とは素因数分解の難しさを利用した暗号アルゴリズムのことです。素数も素因数も中学生の時に習うものですが、この素数は規則性などが分かっておらず「約数がその数と1しかない」という情報以外ありません。そのため暗号を解読するためには一つ一つ素因数を探さなくてはならず膨大な時間がかかります。
- 鍵の作成
- 送信者が暗号化
- 受信者が複合
まずは公開鍵と秘密鍵の作成を行います。
1. 異なる2つの素数p, qを任意に用意する。
2. pとqの積をnとする。
3. (p-1), (q-1)と互いに素な自然数xを任意に設定する。
4. x × y - n × m = 1となるyとmを求める。
上記の「n」と「x」が公開鍵となります。また、「y」が秘密鍵となります。
送信者は公開鍵である「n」と「x」を使い文章を暗号化します。
1. 送りたい文章を自然数kとする。ただし「a < n」
2. aをx乗して、これをnで割ったあまりをbとする。
3. 暗号化されたbを送付する。
受信者は送られてきた「b」を秘密鍵である「n」と「y」で複合する。
1. bをd乗する。
2. これをnで割ったあまりが送られてきた文章aである。
実際の数値で試す
先ほど説明した手順を実際の数値を使って確かめたいと思います。
- 鍵の作成
- 送信者が暗号化
- 受信者が複合
1. p=7, q=11
2. n = 77
3. x = 7
4. 7 × 43 - 60 × 5 = 1
よって、公開鍵は7, 77で、秘密鍵は43です。
1. 送りたい文章の自然数を3とする。
2. 3の7乗を77で割ったあまりは31となる。
3. 31を送信する。
1. 受信した31を43乗する。
2. これを77で割りあまりは3となる
秘密鍵を知らない第三者は「31」であることしか分からないので解読できません。
まとめ
ということで、今回は公開鍵と秘密鍵、RSA暗号についてまとめました。名前はよく聞くものばかりでしたが詳しく調べたのは初めてでした。素数が解明できていないことを利用して安全性を確保するとはすごい考えだと思います。
今回は仕組みについてまとめましたが次回はこれらのアルゴリズムを実際にコードで書いて動かしてみたいと思います。
では、また！