RSAなら、自分の好きな文字列を含む公開鍵が作れる件

はじめに

背景

※注: これは秘密鍵を10億個作れば、高確率で自分の名前を含む公開鍵が作れる件にインスパイアされて書いたネタ記事です

今、意識高い人向けにのSSH認証鍵(公開鍵/秘密鍵)はやはり ed25519 ですが、RSAであれば、なんと! 次のように自分の好きな文字列を含む公開鍵が作れてしまいます!

そう、つまりRSA最大のメリットは好きな文字列を含む自分だけの鍵をカスタマイズできることだったのです! ということで、RSAの魅力を見直そうという記事になります。( ウソです )

TL;DR;

• 好きな文字列を公開鍵に埋め込めるネタツール(Rubyスクリプト)を作ったよ!
  ※ https://github.com/angel-p57/qiita-sample/blob/master/rsa/rsa-genmykey.rb
• RSAでは、公開鍵の主要パラメータ $n$ の値の範囲をコントロールできるので、結果として文字列埋め込みにつなげることができるよ!
• RSAの鍵データを決めるのは、秘密鍵のパラメータ$p,q$ ( 2つの巨大素数 ) だけど、ランダムに作った $p$ に応じて $q$ の範囲を絞ることで、積 $n=pq$ の範囲をコントロールするよ!

※注: 「好きな文字列を埋め込む」ことが鍵の脆弱性にはつながらないと考えていますが、なにかあっても責任とれないので、あくまでネタということでお願いします。

作成したツール

仕様

• 単一のRubyスクリプトです。
  ※ https://github.com/angel-p57/qiita-sample/blob/master/rsa/rsa-genmykey.rb にあります
• コマンドライン引数で好きな文字列を指定することで、RSA SSH秘密鍵 ( OpenSSH形式の新しくないやつ ) を出力します。
  ※リダイレクト等でファイルに保存してください
• 鍵長は4,096固定にしています。
• 文字列に指定できる文字種は英数および +/ の64種です。( つまりbase64の文字種 )
• 原理的に、埋め込める文字列の長さはかなり長くできると思いますが、ツール上では64文字を上限にしています。
• 特にチューニングしていないので、実行には数十秒～分単位で時間がかかるとお考え下さい。( 同じ環境でも結構ブレが出ます )

使用例

以下に、実際に作って試してみた時の例を挙げます。

1. 秘密鍵生成
   ruby rsa-genmykey.rb 埋め込む文字列 > 保存先ファイル名 のようにして保存しています。
2. 公開鍵抽出
   ツールはあくまで秘密鍵データを作るだけなので、公開鍵は ssh-keygen -y -f 秘密鍵ファイル > 保存先ファイル名 で抽出します。
3. 試用
   実際に ssh-copy-id で接続先に公開鍵を登録し、公開鍵認証で使えることを確認しています。

からくり

公開鍵の内容

今回作った公開鍵のデータ ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDF/angelp57/a+cat+of+Flanders/… ですが、先頭のssh-rsaを除くと、次の図が示すようなバイナリ(一部テキスト)をbase64変換した文字列になっています。

この中で、埋め込まれた文字列/angelp57/a+cat+of+Flanders/を決めているのは、巨大整数パラメータ $n$ ( n=0xc5fde9e07a5a79eff6be71ab7e… ) のうち、最上位の c5 を除いた上位桁です。
逆に言えば、パラメータ $n$ をある程度の大きさの範囲に絞り込むことができれば、好みの文字列を埋め込むことができるのです。
※なお、最上位の桁はある程度の範囲でランダムに決めています。

鍵のパラメータの調整

さて、RSAの場合にはいくつかの鍵のパラメータ ( いずれも整数 ) があります。
※詳細は公開鍵暗号RSAの数的構造をご覧ください

• 秘密鍵
  • 素数 $p$(prime1), $q$(prime2)
  • 指数 $d$(privateExponent)
  • 派生パラメータ $d_p$(exponent1), $d_q$(exponent2), $q_{inv}$(coefficient)
• 公開鍵
  
  • 積 $n$(Modulus)
  • 指数 $e$(publicExponent)

この中で $e$ は現在 65537 ( 0x10001 ) の固定値が一般的であり、それ以外のパラメータは $n=pq$ を含め、全て素数 $p,q$ によって決まります。
つまり、$n$をどう決めるかは$p,q$をどう決めるかの話に帰着するのです。

一般には、$n=pq$ が鍵長 ( ここでは4,096bit ) に合うように、$p,q$ がそれぞれ同じ桁数( 2,048bit )になるように、$p,q$が近すぎないように ( 少なくとも上位100bitで違いが出るくらい )、ランダムに素数を選びます。
ここで、$p$をランダムに選ぶのはあまり変えず、$q$をnの範囲から逆算して調整することで、最終的に$n$の範囲を調整することができます。

計算内容

今回作成したツールの計算内容は、ざっくりと次のようなことをしています。

1. 埋め込む文字列から $n$ の範囲を決定
2. 素数 $p$ の範囲を決定 ( $\sqrt{n}$ よりある程度以上大きくなる範囲 )
3. 範囲内でランダムな素数 $p$ を決定
4. $p$の値および$n$の範囲から、素数$q$の範囲を決定
5. 範囲内でランダムな素数 $q$ を決定
6. $p,q$ の値に基づき鍵データを生成

なので、「いかに素数を探すか」が計算の中心であり、以下の2つを実装しました。

• 素数判定
  ミラー・ラビン判定法をそのまま実装しました。試行40回としているので、誤判定の確率 $1/2^{80}$ ということで、実用上問題にならないと思います。
  詳しくはFIPS186-4のAppendix C、C.3.1をご覧ください。
• 素数候補探索
  小さめの素数2つから目的のサイズの素数の候補を探索する方法を実装しました。 詳しくはFIPS186-4のAppendix C、C.9をご覧ください。
  詳しくは精査していませんが、闇雲に候補を探すよりも効率が良いのではないかと思います。OpenSSLもbn_rsa_fips186_4.cで、関数bn_rsa_fips186_4_derive_prime()としてこの方法を採用しているようです。
  なお、小さな素数は普通にランダムに探します。サイズは171bitとしており、この数値はOpenSSLのbn_rsa_fips186_4.cの関数bn_rsa_fips186_4_aux_prime_min_size()を参考にしています。

鍵の安全性

RSAにおいて鍵の安全性は「$n$の素因数分解の困難性」として数体ふるい法の計算量が支配的であり、素数候補の無差別探索は攻撃者にとって割りに合わない方法です。
なので、素数の範囲にせいぜい数百bit程度の制限を設ける今回の手法であれば、鍵の安全性はほとんど低下しない…と考えています。
しかし、ツールにどんな瑕疵があるかは分かりませんので、あくまで「ネタ」としての利用にとどめることをお勧めします。

終わりに

秘密鍵を10億個作れば、高確率で自分の名前を含む公開鍵が作れる件がなければ、「公開鍵に文字列埋め込めるじゃん」と思いつくこともありませんでした。感謝です。
なお、このツールでは鍵データの出力 ( ASN1 )、素数判定等全部自前で簡易的に書いてるのですが、素直にOpenSSLの機能使った方が楽でかつ性能も良かったのではないかという気もしてます。
そこらへんの書き換えなんかも含め、RSAの応用として、今年の夏休みの自由研究にいかがでしょうか?