ぺんぎんさんのおうち

トリトリトリ

ラーメンに大蒜を投入しすぎてスープの味が変わってしまうことがある

はじめに

今の時代, 公開鍵のビット数がどうであろうとRSAを使うことは推奨されない. が, 今でもRSAの利用を続ける人はいる. ssh-keygenを叩くとデフォルトで出てくるのはRSA(2048 [bits])の鍵ペアだ. (2019-09-09 現在)

ビット数の大きな素数の積を素因数分解するのが困難という話は有名で, 10進数10桁と10進数1000桁なら後者の方が大変そうというのは予想できる. ビット数を大きくすることで安全性を強化できるなら, 今のビット数を2倍, 4倍, ..., としていけば安全なままにしておける. しておけるのだが, 公開鍵をネットワークに流すことを考えると大きなビット数の鍵は適切ではない.

今回は「もうRSAを使うのはやめないか」という話をしようと思う.

ビット数を大きくして嬉しいこと

  • 素因数分解の計算量が大きくなる
    先述した通り.

  • 素数の再利用が起きにくくなる
    あまり触れられることはないが実は大事な要素. もし再利用されていれば \(N_{1} := p*q_{1} \), \(N_{2} := p*q_{2} \)で\(GCD(N_{1}, N_{2}) = p \)なので簡単に素因数分解できてしまう. 公開鍵を大量に収集, もしくは自分で公開鍵を作りGCDを取り続けるという攻撃ができる.

これだけ見ると「GCDを取り続けるのは, 頑張って素因数分解するのとかかる時間にそこまで差異はないのでは?」と思われるかもしれないが, 特定の公開鍵(Moduli)を狙って素因数分解を試すのではなく, ネットワーク上の公開鍵全てに対してGCDが取れることを考えると脅威だと言える. つまり, 自分の公開鍵は簡単に素因数分解されないかもしれないが, 自分以外の誰かが共通の素数を使った公開鍵(素数の片方だけを共有)を所持していれば安全性は崩壊する.

2048 [bits]の素数より4096 [bits]の素数の方が個数が多いのだから, ビット数が大きくなれば再利用が起きにくいのは当然である.

再利用による影響

3192962個の(証明書の)公開鍵を調査し, 103のModuliがGCDによって素因数分解できた[1]. また, ある素数が46回利用されていることもわかっている. 頻度的には相当小さいが, これから同じパターンのビット列を持つ素数が他にもあるのではないかと予想が立つ. 鋭い読者はもう気づいているかもしれないが, 目当ての素数を\(p\), パターンを\(a\), 下位ビットに相当する変数\(x\)を使って多項式\(f_{p}(x) := a + x\)を構成し, coppersmith's attackによって\(N = p*q\)が素因数分解できてしまう可能性がある(上の多項式の解が求められる).

適当なパターンを取り, 持っている公開鍵全てに対してcoppersmith's attackを試し解が得られれば攻撃成功となる. 実際に[1]ではこの方法で新しく素数を得ること(素因数分解)に成功している.

この実験では素数が512 [bits]なので現行のRSAとはビット数が大きく異なるが, 成功確率が下がるだけで本質的には同じである. 4096 [bits]ということは素数のビット数は2048程度なので, 1200 [bits]くらいのパターンがあればsageMathのsmall_rootsで残りの800 [bits]がすぐに求まる.

方針としては
1. 大量の公開鍵を収集, 生成
2. 共通の素数が複数見つかったら, 上位ビットをパターンとして持っている公開鍵に対してcoppersmith's attackを試す

実際に試そうとしても, GCDで素数を見つけることが大変なので現実的な攻撃とは言えない. しかしながら”素数が再利用されていない”ことを示せない限りは脅威になり得る. 今のところRSAは「(GCD以外の方法によって)素因数分解されるかもしれない」「公開鍵をたくさん集めればGCDを取ることによって素数が得られるかもしれない」という危険性を持っている. また最初に述べたように強度のわりにビットサイズが大きい.

おわりに

ここまで言えば「RSAの公開鍵は公開しても大丈夫ではない」ことがわかってもらえたと思う.
RSAを使うのをいい加減やめよう.

本項と全く関係ないが, openssl(修正済み)でRSAの鍵を生成するときに(かなり限られた条件下で)cache-timing attackができるという報告もある.

参考

[1] Factoring RSA Keys from Certified Smart Cards: Coppersmith in the Wild

ラーメンを完飲してはいけない、旧約聖書にもそう書いてある

はじめに

SSHの鍵を作るときに, 「いまどきRSAだなんて(たとえ4096bitsだとしても)! Ed25519を使うのが常識よ!!」というような文言を耳にするかと思います. 実際僕もGitHubではEd25519を使っています(ykm11).

しかしよく考えてみてください. みなさんはちゃんとEd25519を使うことの意味を理解していますか?「楕円曲線だからRSAよりビット数が少ない上に強度もいい感じ〜」とか「Ed25519を使ってる人は意識高いよね〜」とか, そんな感じで使っていませんか? それでいいと思います.

が, せっかく使うなら「どうして安全なの?」とか「どうして速いの?」とかそういう話にも興味を持ってみると面白いかもしれません. 言い忘れてましたが, Ed25519って高速で動くんですよ. ”楕円曲線だから” ではなくて ”Ed25519だから” ですね. djb氏は神. (一般的に, 楕円曲線RSAよりもビット数が少なく済み, また速いとされていますが, ここでは楕円曲線を使ったアルゴリズムの中でも特にEd25519が優れているということを強調しました)

今回は実際にopensslのEd25519実装や元となっている論文を読みながらアルゴリズムの紹介をしようと思います. もしかすると間違えている部分があるかもしれないので, 気になる方は論文を読んでみてください.


用語の整理

  • curve25519 (Curve25519)
    GF(2255 - 19)を定義体とする楕円曲線の総称.

  • Ed25519
    twisted Edwards curveを使ったEC"DSA" 署名アルゴリズム. X25519(後述)と混同しないよう注意.

  • X25519
    ECDHE. 鍵共有アルゴリズム. X448とよく一緒に出てくる(はず). TLS1.3ではこれが使われている. (2019.08.24現在)

この記事ではEd25519のみを扱う. (曲線方程式や加算法については余力があれば)(余力がなかったのでいつか更新)


EdDSA key generation and make signature

M: message
H: hash function, H(a, b, c) means H(a|b|c); concatenate
k: private_key (b-bit)
h: H(k) (2b-bit, h[0:2b-1])
A: public key
B: base point of curve25519
ellcard: cardinality of the curve

\( a := 2^{b-2} + \sum_{3 \le i \le b-3} {2^{i}h_{i}} \)
\( r := H(h[b:2b-1], M) \)
\( A := [a]B \)
\( R := [r]B \)
\(S := (r + H(R, A, M)*a) \, mod \,\, ellcard \)

\((R, S) \) が署名となる. Sはscalarとして出てくるが, Rは曲線上の点で, y_coordinateを使う. 通常の楕円曲線はx_coordinateから対応するy_coordinateを取得するが, Ed25519ではy_coordinateからx_coordinateを決定するので逆であることに注意.
余談だが, x_coordinateがあればy_coordinateはすぐに求められるので, \((x, y)\)を送るのは冗長である(x_coodinateとy_coodinateの偶奇の情報だけあればよい).

opensslのcurve25519.cを確認するとED25519_sign()は概ねこの通りに実装されていることがわかる.


Verify signature

検証者は\((R, S) \)を受け取る. \(H(R, A, M)\)を計算し,

\begin{eqnarray} [8S]B = [8]R + [8H(R, A, M)]A \end{eqnarray} を満たすことを確認する.

\( S = (r + H(R, A, M)*a) \, mod \,\, ellcard \) なので,

\begin{eqnarray} [S]B &=& [r]B + [H(R, A, M)*a]B \newline &=& R + [H(R, A, M)]A \end{eqnarray}

\( A := [a]B \), \( R := [r]B \) を使った.

実装としては8倍されていなかったが, 論文では8倍されている. おそらくcofactorの8.


実際のopensslのED25519_verify()は, この方法とは異なるのでこれから示す.

openssl implementation

検証者は\((R, S) \)を受け取り, \(h := H(R, A, M)\)を計算.

\begin{eqnarray} \overline{A} &:=& [-1]A \newline
\overline{R} &:=& [h]\overline{A} + [S]B \newline
&=& [r]B + [h*a]B - [h]A \newline
&=& [r]B + [h]A - [h]A \newline
&=& [r]B \newline
&=& R \end{eqnarray}

\( y(R) = y(\overline{R}) \) を満たしていれば検証成功.

Ed25519では署名アルゴリズムでよくある"乱数生成"が出てこない. 秘密鍵のハッシュを取ると, 暗号学的ハッシュ関数の定義よりハッシュ値から秘密鍵を特定できないのでハッシュ値を推測不可能な乱数とみなせる. 乱数を使わないので署名が決定的になってしまうが, PlayStation3の例もあり乱数を使うことを避けているのだろう. これについても論文内で触れられている.


おわりに

opensslの実装を読むと, scalar倍の計算量を落とすためにmod |E|していたり(落としている関数の実装が面白い), 逆元を求めるのにFermat's Little Threoremを高速で動くように実装していたり. \(\bf{P}^{3}\)の射影座標で実装されていたりするので楽しい.


参考文献

近況

前の 電通大に編入して半期が過ぎたので - ぺんぎんさんのおうち

 

ついこの間までセキュリティキャンプ2019全国大会にチューターとして参加していました。参加記を書こうとしたのですが、2行くらい書いたところで手を止めてしまいました。キャンプの参加者で僕のブログ見てますという人を見かけました。嬉しい限りです。恥ずかしいですけど。ひっそりやってるので外に出しても恥ずかしくないような内容/文章をかけるようになりたいなと思います。

来年は院試がキャンプの日程と被るので関わることはないのかなと思っています。編入生にも推薦をポンっと出してもらいたいものですね。

 

このブログは僕の近況報告とか技術的(笑)な話とか色々と混ざってるので、そろそろ分けた方がいいかなぁと思ってるんですが面倒なのでずっとこのままです。すでにエントリ数が400超えてるので今更な気もします。

読む側からすると分けてくれって感じなんでしょうか、自分だったらそう思いますね。書く側からすると「いや知らねえよ」ですが。

 

 

そういえば何年振りだろうか?というくらいの間で体調を崩しました。風邪ですかね。耳鳴りがずっとしていて頭痛もひどく。ずっと寝てたらいい感じによくなったので病院へは行かなくてよさそうです。せっかくの休みを寝て過ごす羽目になりつれえなぁとなってましたが、最近嬉しいこともありました。まだ内緒です。そのうち。

 

夏休みはあっという間に終わりそうですね。後期の後半でようやく研究室配属の話が動き出すので楽しみです。技術的な話、特に自分が勉強したものを記事として書くのが最近面倒になってきているのでやめるかちゃんと書くかしたいなぁと。

電通大に編入して半期が過ぎたので

前期末試験が終わり, レポートの提出も済み, 夏休みになりました.

電通大は8月の上旬くらいに夏休みが始まるので, これを他大の人に話すと「遅くない?」という反応をされることが何度かありました. 遅いんですかね?

授業料に対してコスパは良いので得したと思いましょう.

 

ykm11.hatenablog.com

 

 

さて, 前期の振り返りや所感とかを書いていきたいと思います.

 

 

大学について

 

電通大の良いところと悪いところ

良いところ

 - IEEEとSpringerLinkの論文が読める

 - etc..

 

悪いところ

- 単位認定(後述)

 

電通大の悪いところ, 単位認定以外には特に思い浮かばないですね. 良いところは”それ以外”というかなり適当な答えになるんですが, 現在特に不満などはないです(単位認定以外).

 

 

 

その他

大学以外, 主に生活面について. 

 

ごはん

調布駅や大学の近くに多くの飲食店があるので食べるところには困らないと思います.

去年度までは学校付近にローソンしかなかったのでだいぶ変わりました.

 

ミスタードーナツ

調布駅から大学に向かうまでの道にあります. やばいですね. 車で片道30分かけて買いに行っていたのが馬鹿らしくなるほどに. 僕はダブルチョコレートとエンゼルフレンチが好きなので, 僕に相談したいことがあるときはこの2つを差し入れに持ってくるといいんじゃないですかね(適当). 

 

単位認定

もうやりたくないですね. 4月はこれやってたら終わりました.

 

総合コミュニケーション科学

来年も是非, 編入生に受講させてください.

 

研究室

編入生だから配属が優先される ということはなく, 内部生と同様に3年の終わり頃に仮配属が決まります. 遅いですね. GPAで殴り合うお祭りになるかどうかは研究室によるみたいです.

 

 

この記事を書く前とかは結構ノリノリだったんですが, 途中で飽きてしまいました. 何か聞きたいことがあるときは僕を探してください.

タイトルは後で考える

いくつか命題を証明していきたい.

素数pを法とすると平方剰余の個数は(p-1)/2個となる

\(A := \{x^{2} \, mod \, p \mid x \in GF(p) \} \) としたときに, \( \#A = \frac{p-1}{2} \) となることを示したい.

まず\(GF(p) = \{1, 2, ..., p-1 \}\), \(\#GF(p) = p-1\)であり, \(\forall a \in A, a^{\frac{p-1}{2}} \equiv 1 \, mod \, p\)


\(x^{2} \equiv (p-x)^{2} \, mod \, p\) であるため,

\begin{eqnarray} 1^{2} &\equiv& (p-1)^{2} \, mod \, p \newline 2^{2} &\equiv& (p-2)^{2} \, mod \, p \newline . \newline . \newline ({\frac{p-1}{2}})^{2} &\equiv& ({\frac{p+1}{2}})^{2} \, mod \, p \newline \end{eqnarray}

したがって\( \#A = \frac{p-1}{2} \)である. \(GF(p)\)の半分の元は平方剰余, もう半分は平方非剰余であることを言っている.


p ≡ 2 mod 3 のとき, x3 = a mod pはただ一つのみ解を持つ

\(f_p(x) = x^{3}\) が全単射であることを示せばよく, \( f: GF(p) \rightarrow GF(p) \)であるため単射であるならば全射でもある. 単射であることを示そう.

単射の定義より, \(f_p(x) = f_p(y) \) なら \(x = y\)である.

\begin{eqnarray} x^{3} &\equiv & y^{3} \, (mod \, p) \newline (xy^{-1})^{3} & \equiv & 1 \newline \end{eqnarray}

ここで一旦置いておく.
先に, \(z^{3} \equiv 1 \, mod \, p; z \in GF(p) \) なら\( z \equiv 1 \, mod \, p\) を示す.

\(z^{3} = 1\)であるから \( \#G(z) \mid 3 \). これは\((1, 3)\)のどちらかである.

またラグランジュの定理より, \(G(z)\)は\(GF(p)\)の部分群であるため \( \#G(z) \mid \#GF(p) \)でなければならない.

\(p \equiv 2 \, mod \, 3\)より \(p = 3k + 2\)
\(\#GF(p) = p - 1 = 3k + 1 \)

\( \#G(z) \mid \#GF(p) \) となる\(\#G(z)\)は1のみであるから \( z^{3} \equiv 1 \, mod \, p\) なら \( z \equiv 1 \, mod \, p\)

これを踏まえて上の式を考える.
\begin{eqnarray} (xy^{-1})^{3} & \equiv & 1 \newline xy^{-1} & \equiv & 1 \newline x & \equiv & y \, mod \, p \end{eqnarray}

\(x, y \in GF(p)\)なので \(x \equiv y\)から\(x = y\)が言える.
\(f_p(x) = f_p(y) \) なら \(x = y\)を示せたので, \(f_p(x) = x^{3}\)は単射である.

したがって\(f_p(x) = x^{3}\)は全単射であり, p ≡ 2 mod 3のとき, x3 = a mod pはただ一つのみ解を持つ.

以下参考:
If 𝑝≡2 mod 3, 𝑥3≡𝑎 mod 𝑝 has only one solution modulo 𝑝.


上の2つは, 楕円曲線\(E_p(0, b); p \equiv 2 \, mod \, 3\) の位数が\(p+1\)であることを示すために使われる.

\(K := \{x^{3} + b \mid x \in GF(p), b \neq 0 \} \) のとき, \(K = \{ 0 \} \cup GF(p) \backslash \{b\} \neq GF(p) \) であるが, これは\(x^{3} + b \equiv 0 \, mod \, p\) の解が存在することを示している. この場合でも位数は変わらない.