ツッコミ - 186 @ hatenablog

(前略)
公開鍵暗号方式、例えばRSA方式では、暗号化の逆の操作で署名を行うわけですが、やっていることは単なる掛け算（ただし「剰余系」の上での乗算）です。
署名したい文章（文字列＝数列）に秘密鍵を乗じたものを「署名」とし、署名を受け取った者は、公開鍵を乗ずることによって、（公開鍵は秘密鍵の「逆数（ただし剰余系での）」なので、掛けると「1」になって元の文章が出てくることで）真正な署名であることが確かめられます。
つまり、署名s （平文aのd乗＝ad）を受け取った者は、公開鍵r を乗ずることによって、nを法とする剰余系上で、
$s^r \pmod{n} \equiv (a^d)^r \pmod{n} \equiv a^{dr} \pmod{n} \equiv a$
というように、もとの文章aが復元されるため、秘密鍵dの保有者が、この文章aに署名をしたことがわかります。
(略:図)
RSA方式の署名は暗・復号化の処理スピードが対称鍵暗号に比べて千倍程度遅いため、暗号・署名の製品の実装では、文章を「ハッシュ関数」という関数で「要約」して、それに署名を行います。一方向性ハッシュ関数とは、不定長の文字列を、ある一定の長さの文字列(128bitなど)に要約する関数。128bitというのは、漢字わずか8文字程度の情報量しかないのに対して、要約する元の文書は無限に存在するわけですから、理論上はまったく同じ128bitの文字列に要約される文章は無限に存在します。
(中略)
ところが、RSAのように「剰余系上の素数の積が因数分解できるか」、といった話になると、大学の数学科以上のレベルのお話であり、言ってる意味の理解まではなんとかできたとしても、その技術でホントにセキュリティが確保されてるのかどうか、というと、それを証明できる人は世界でも一握り、といったレベルになってきます。
(後略)

適当にツッコミ.

公開鍵は秘密鍵の剰余系 (Z_n) での逆数ではありません. 肩の世界 (Z_{φ(n)}上) での逆数です ( $e d \equiv 1 \pmod{\phi(n)}$ ).
ハッシュ関数を使うのは, 遅いため?
- ハッシュ関数を使わずにメッセージ2mに署名を行った場合どうなるか考えてみましょう. (2m, σ)と公開鍵(e,n)を見て, メッセージmに関する署名が作れます. 署名オラクルに1回問い合わせるだけで, 誰でも存在的偽造が可能になります. (EUF-CMAが破れる.)
- ハッシュ関数を使うことによって, ある程度のセキュリティが期待できる. (が, 今のところRSA仮定+CRHFでEUF-CMAな署名ってあるけど実用的じゃなかったような.)
- ついでに言うと, One-way Hash Function (OWHF) じゃなくって, Collision-Resistant Hash Function (CRHF) じゃないとダメ.
- 更に言うと, RSA仮定+ROでEUF-CMA安全なのがRSA-PSS. 強RSA仮定+CRHFでEUF-CMA安全なのがCS署名.
- あと, 改竄防止ってのもある. 一回署名付けたあと, メッセージだけ変えちゃうとか.
剰余系上の素数の積が因数分解できるかというのは不思議な設定. n=pqの演算はZ上なので, Z上で素因数分解したいんじゃないの? もしくは素元分解.
- 剰余環Z_n上の何を何で割るの?
証明できる人は世界でも一握り，といったレベルになってきます今のところ, 成功した人はいません. RSA仮定が真であることが示せると, それはOne-way Trapdoor Permutationの存在を言っているので, P!=NP(ry
- ついでに言うと, RSA問題は素因数分解問題よりも今のところ易しいので, 素因数分解問題が(ry
- RSA仮定+ROでEUF-CMAなら高校生でも理解出来ると思うよ.
- 確かにRSA暗号を思いつくのは誰でもできることではありませんが、その肝となる、「素数を掛け算して合成数を作るのは簡単だが、その合成数を因数分解して元の素数を割り出すのは格段に難しい」というのは小学生でもわかります。
  - 難しいっぽいのが分かるというのが正しい. 本当に格段に難しい (Pに入らない) というのは証明出来ていない.

google:電子署名ハッシュ関数
遅いためって説明はたまにあるな.