teruuuのブログスマートフォン用の表示で見るteruuuのブログ2019-05-24RSA暗号の仕組みを追ってみたRust最近では量子コンピュータの技術が発展してきて2030年頃には2048bitのRSA暗号が突破されると言われているらしいです。RSA暗号は馴染みが深いところでいうとhttpsでのssl・tls通信でも使われている技術になりますので改めて勉強してみようかと思います。確認の実装にはRustを使っています。公開鍵暗号の概念は1976年にデルフィ、ヘルマンにより発表されたがその時点では具体的な暗号の実現には至らなかった。翌年の1977年にリベスト、シャミア、エーデルマンが具体的な公開鍵暗号が提唱され3人の頭文字をとってRSA暗号と命名された。映画イミテーションゲームでも題材になったアラン・チューリングのナチス暗号機エニグマの解読の功績が有名です。鍵の生成(公開鍵と秘密鍵)鍵生成処理の流れまず素数pとqをランダムに生成する。ssh-keygenコマンドで鍵を生成するときに指定するbit数はここで決める素数p,qの値のものになります。1となるeを選択します。φ(N)とeが互いに素であることを意味しています。φ(N)はオイラーの関数というものでφ(N)は1からNの範囲でNに対して素な数の合計となります。オイラーの関数についてm、nが互いに素であるときφ(mn)=φ(m)φ(n)が成り立ち、これを乗法性と言います。(q-1)となります。(1~pの範囲で素数pに対して素な数はp-1になります。1を満たすeを見つけるのと同じになります。φ(N)となるdを見つけます。条件を満たすdを見つけるには拡張ユークリッドの互除法を使います。鍵の生成はこれで完了で公開鍵はNとeで秘密鍵はdとなります。e)、秘密鍵(d)を返すでは、これらについて確認のため一つずつ実装してみたいと思います。素数の一覧を返す関数として以下を実装しました。5(6n±1)であることから説明がつくと思います。実際に確認してみたところ大丈夫そうでした。59]素数の一覧を取得できたのでこれを元に素数p,qを以下のように求めておきます。}}実際はもっと大きな数値じゃないと使い物にならないはずですが、今回は確認ということで小さい数値で確認してみたいと思います。計算するこれはただ掛け合わせるだけです。実際は2048bitの数値とかを扱うので大きな数値の計算を考慮する必要がありそうです。1となるeを選択するここでは以下を確認してみたいと思います。対して素なeを拡張ユークリッドの互除法で求めるφ(p)=p-1となることはpが素数であることより自明ですが今回は確認のために地道に求めてみたいと思います。最小公倍数の確認として以下のユークリッド関数を作成しました。}}テストコードを実行してみたところ、正しく動いてそうです。1);}次にオイラー関数を以下のように実装しました。aの範囲の数値でaとの最小公倍数が1(互いに素)なものをVectorに追加していって長さとともに返すだけです。vec)}φ(p)=p-1となることについては以下で確認ができます。}}次に乗法性の確認にとして以下を実行します。対して素なeを見つけるについては拡張ユークリッドの互除法を使うのですが以下のように実装しました。byが最大公約数となるようなa,bを出力するので以下の関数で確認しました。1となるeを見つけるについてe=3や65537を固定で使うといった手法もあるようですが、今回は以下のようにランダムに求めてみたいと思います。1となるa,bを返すのでこれを使います。このとき返してくる数値が負の数の場合があるので、その時はφ(N)を足して0よりも大きくなるようにします。e)、秘密鍵(d)を返します。関数全体は以下のようになります。qの上限値を指定するようにしていますが、ここは実用的にするにはbit数を指定できるようにした方が良いのかと思います。生成されたので次は公開鍵で暗号化を試してみたいと思います。Nを求めたものになります。N以下のように実装します。Nしても結果が変わらないことがわかると思います。Nしたものが暗号化前の入力mと同一になります。N関数を分けていますが暗号化で使ったものと同じ内容です。result}全体としては以下の通りになり、テストコードもパスすることが確認できます。}}実際に試してみて大丈夫そうな感じではありましたが、念の為証明もしてみたいと思います。確認したい内容は復号化結果m'が入力mと同一になることなので以下の証明になります。k*φ(N)+1としています。pまたはqの場合で証明できれば十分になります。これより以下が成り立ちます。