🐉

SSH認証で使う”復号してからの暗号化”を実際にしてみたお話

2023/08/06に公開

公開鍵認証、普段はノリとパターンでやっているのだけれど、ちょっと調べ直してまとめてみようと思い立った
というか、公開鍵方式で本当に署名できるのか気になったので、実際にどんな計算をしているか調べてみた。そんな記事

認証に使う公開鍵と秘密鍵

コマンドプロンプトなんかでssh-keygenコマンドを使うとSSHキーを生成できる
ここで、拡張子が.pubなのがpublicな公開鍵で、拡張子がないものが秘密鍵。ペアになってる1組の鍵が生成される
そして公開鍵で暗号化、秘密鍵で復号という動作がセットだから、暗号化のための鍵が通信中にバレても安心ということで使われているわけだ

実戦の動きを踏まえて、実際の動きを見ていこう

公開鍵認証の手順

簡単に手順を書くと、こんな感じ

前準備

  1. 接続するPC(クライアント)で秘密鍵、公開鍵のペアを生成する
  2. サーバーに公開鍵を登録する
  3. 対応する秘密鍵は秘匿する

接続する

  1. 接続要求があったら、サーバーはセッション識別子(その場限りで使う値)を送信
  2. クライアントがセッション識別子を受け取ったら…
    1. 秘密鍵を使ってセッション識別子を署名
    2. 署名と公開鍵を送信
  3. サーバーが署名を受け取ったら…
    1. 受け取った公開鍵は自分の持っている公開鍵かを確認
    2. 署名を公開鍵でセッション識別子に戻し、1. で送信したものと一致するかを確認
    3. 確認できれば認証完了。対応する秘密鍵を持っている相手なので信用できる

実際に公開鍵認証をするとき、Githubなんかではユーザー設定ページから、Linuxでは.ssh/authernized_keysファイルに公開鍵を登録、追記するのが事前準備です
つまり、サーバー側は公開鍵のみを持っているという状況なので、公開鍵で署名を検証(元の文に戻)していることになる
"公開鍵で暗号化、秘密鍵で復号する"とは逆の扱いをしているわけです
暗号化、復号の操作を逆でおこなってもちゃんと元通りになるの?というと、そこはちゃんと元通りになるらしい
と、ここまでが余談で、実際にRSA暗号を作って、どんな動作をしているのか確かめてみました。というのが本題。このあとから

実際にRSA暗号を作ってみた

公開鍵で暗号化したものを公開鍵では復号できないが、秘密鍵では復号できる。不思議
暗号化して復号したら元に戻るのは当たり前として、復号してから暗号化しても元に取って署名として使える。なんか不思議

不思議に思ったので、実際にRSA暗号を作ってみた。ものがコレ(Githubにアップした.ipnbファイルへのリンク)
適当に素数の組と公開鍵を設定して、がしがしと計算してみたらこんな感じになった

項目
素数の組 p=2677q=1433
暗号化できる最大値 n=3836141
公開鍵 k_{pub}=41
生成できた秘密鍵 k_{sec}=467321

データMを暗号化してCにする式はコレ
C=M^{k_{pub}}\%n

Cを復号してM’にするための式はコレ
M’=C^{k_{sec}}\%n

んでもって、実際に数値を暗号化→復号したものがコレ

平文 暗号文 復号した暗号文
2 1460994 2
29 2658572 29
296 933055 296
2962 2493606 2962
29629 3366494 29629
296296 1854845 296296

なるほど。確かに暗号化したものをちゃんと復号できている
しかもちゃんと暗号文がわけわからん数値になってくれている

ここで公開鍵で暗号化したものを公開鍵で復号しようとしても、%演算での計算で答えの部分が無くなってしまっているので戻れなさそうだ。なるほど
296^{41}なんて、10^{101}とかそのくらいのケタ数です。答えの値を1から総当たってみようにも、どうしたものか......
(あと鍵の値乗の根とか考えたくない。この簡単な場合でも41乗根??Newton法でも使えばいいのかしら?その数値計算を100ケタ数の総当たり????)

ちなみに署名の方もちゃんとできてて、平文を復号の式で署名にしたものを暗号化の式でちゃぁんと検証できてる

平文 署名 検証結果
2 185458 2
29 911709 29
296 3282946 296
2962 740002 2962
29629 1137171 29629
296296 2870974 296296

ほえー、順番が変わっても逆操作で元に戻せるの、なんだか微分積分みたい(変な感性)

実際に計算させてみてわかったのだけど、こんなのナイーブに何も考えずに実装したら、計算に時間がかかってしょうもない。実用化させてるの、ふつうにすごい
しかも1つの鍵だけでは復号ないし検証できないの、実際に見てみると改めてすげーって思った。そんな感じですげーってなったところで、この記事はおしまい
(ちなみに、"公開鍵と秘密鍵を入れ替えてもできるじゃん!"ということでその辺のサービスに公開鍵っぽい形にした秘密鍵を登録しようとしたら、”フォーマット(長さ)が違うので登録できません”だってさ。しょんぼり)

おまけ: AWSのEC2での認証

AWSでEC2を作るときにキーペア作ったのだけど、その時にAWSのページで秘密鍵をダウンロードしたんです
あら?秘密鍵を通信で送るのってどうなんだろう?と思ったんですが、あんまし疑ってる記事みかけないですね
一応、AWSのコマンドラインツールでaws ec2 import-key-pairコマンドを使えば、ローカルで鍵を作って、公開鍵だけをインポートさせることができるみたいです。ほぇー

Discussion