なんで秘密鍵で復号してデジタル署名?
-
angel_p_57
- 1454
- 2
- 0
- 0
-
- いいね！0
angel (as ㌵㌤の猫)
@angel_p_57
この話、「(ハッシュ値を)秘密鍵で復号したらデジタル署名? ワケワカラン! 秘密鍵で暗号化なら分かる!」とか言い出す人かなりいるから、一応ちょっと説明あった方がいいのかな。 x.com/angel_p_57/sta…
2024-05-23 23:41:24
angel (as ㌵㌤の猫)
@angel_p_57
> ちゃんと理解できない 単なる事実に過ぎないので、把握だけできていれば ( それも必須ではないけど ) 別に理解するものではないような。 ※単に原初の論文"New Directions in Cryptography"の4章にそういうアイデアがあったのを、RSAは実現したってだけだし ee.stanford.edu/~hellman/publi… x.com/yu1c1yu1c1/sta…
2024-05-22 20:51:04
angel (as ㌵㌤の猫)
@angel_p_57
ま、書いている通り元々原初の論文で発表されていた最初期のデジタル署名実装アイデアとしてあったから、以外のことはないので。分かるも分からんも「事実を受け止めろ」という他はないんだけど。
2024-05-23 23:41:25
angel (as ㌵㌤の猫)
@angel_p_57
まあそれはそれとして「なんで『秘密鍵で復号して署名』なんて話が出てきたのか?」ってことだけど。ちょい数学の話入るので、数学用語にアレルギーがある人には辛いかもね。そんな大して難しい話じゃないとは言え。
2024-05-23 23:41:27
angel (as ㌵㌤の猫)
@angel_p_57
逆に、数学に馴染みある人だったら「あ、『逆写像(関数)いけるんちゃう?』って思ったからか」で終わる話だったりする。実際これで察した人はもう続き読まなくていいんじゃないかな。
2024-05-23 23:41:28
angel (as ㌵㌤の猫)
@angel_p_57
この「逆写像(関数)」って用語だけどそのまんま逆の写像(関数)。別に写像と関数って取り立てて意味に違いはなくて()つけるの面倒だからここでは写像で通す。
2024-05-23 23:41:29
angel (as ㌵㌤の猫)
@angel_p_57
逆ってどういうことかというと、2つの写像 f,g があって g(f(x))=x が全ての x で、f(g(y))=y が全ての y で成立するなら f,g はお互いにとって逆の関係になっていると、そういうこと。このとき、g は f の逆写像で、f は g の逆写像となる。
2024-05-23 23:41:30
angel (as ㌵㌤の猫)
@angel_p_57
なお、なんでわざわざ x,y と別の文字を使っているかと言うと x,y と写像にかける要素が同じ種類のモノとは限らないからだ。写像の用語で言うと「定義域と値域が同じと限らない」って話。
2024-05-23 23:41:30
angel (as ㌵㌤の猫)
@angel_p_57
もうちょっとちゃんと言うと、集合Xから集合Yへの写像 f ( f: X→Y という風に書く ) と、集合Yから集合Xへの写像 g ( g: Y→X ) に関しての話だけど、X=Y とは限らない、と。
2024-05-23 23:41:31
angel (as ㌵㌤の猫)
@angel_p_57
一応逆写像の具体例も出しておくと、非負実数の範囲で f(x)=x^2, g(y)=√y とするとこの f,g は逆写像。まあ、これは X=Y の例になるけど。
2024-05-23 23:41:32
angel (as ㌵㌤の猫)
@angel_p_57
X=Y でない具体例も出すなら…。X={0以上2π未満の実数}, Y={絶対値1の複素数} で f(x)=e^(ix)=cosx+isinx, g(y)=arg(y) ( yの偏角、0以上2π未満の値をとるようにする ) とか? まあ、なんか色々あるだろう。
2024-05-23 23:41:33
angel (as ㌵㌤の猫)
@angel_p_57
では公開鍵暗号(暗号化)と署名の話に戻る。そもそも公開鍵暗号において暗号化、復号はデータを変換する写像に他ならない。メッセージ m、暗号文 c に関して、暗号化 c=E(m)、復号 m=D(c) と。 ※違うパターンあるんだけどここでは一旦忘れておく
2024-05-23 23:41:34
angel (as ㌵㌤の猫)
@angel_p_57
暗号化して復号すれば元のメッセージが得られるわけだから D(E(m))=m これって先程の逆写像の時に出てきた g(f(x))=x と同じ形。だから D,E は逆写像の関係になっているだろうと。そういうこと。
2024-05-23 23:41:35
angel (as ㌵㌤の猫)
@angel_p_57
ただし注意が必要なのは、逆写像は g(f(x))=x, f(g(y))=y 両方の成立だから、D(E(m))=m だけでは実は逆写像とは限らないこと。だからあくまで「いけるんちゃう?」であって「いける」と断言できない。
2024-05-23 23:41:35
angel (as ㌵㌤の猫)
@angel_p_57
とは言え、前提を追加すれば逆写像であること、つまり E(D(c))=c も言える。それは何かというと、mの集合・cの集合が有限かつ同じ集合であること。さっき例に挙げた f,g の時の X=Y にさらに「有限」を追加したような状況。
2024-05-23 23:41:36
angel (as ㌵㌤の猫)
@angel_p_57
原初の公開鍵暗号の論文ではこの前提を仮定していたし、RSAもそれに則っている。だから E(D(c))=c が成立する。つまり E,D は逆写像になっている。で、同じ集合の要素なんだから別に c でなくて E(D(m))=m でいい。
2024-05-23 23:41:37
angel (as ㌵㌤の猫)
@angel_p_57
これが「メッセージを(暗号化してないけど)復号すると署名、暗号化して元に戻して検証」って話の真相というか。言ってしまえばなんてことはない。
2024-05-23 23:41:38
angel (as ㌵㌤の猫)
@angel_p_57
あ、ちなみに「ハッシュ値」を出してないのは、原初のアイデアの時期にそもそも暗号技術としてのハッシュは誕生してないので。だからあくまで「メッセージ」で説明している。
2024-05-23 23:41:40
angel (as ㌵㌤の猫)
@angel_p_57
さてここまでの話は「『秘密鍵で暗号化』が分かり易いはず!」っていうのが、的外れである理由にもなっている。背景完全無視じゃん、勝手に暗号化・復号を取り替えるなよ、と。
2024-05-23 23:41:41
angel (as ㌵㌤の猫)
@angel_p_57
ただ、注意が必要なのは、というかまあ何度も言ってるから分かると思うけど、あくまでここまでの話って最初の前提がそうだったってだけなので。そこは念押ししておく。
2024-05-23 23:41:41
angel (as ㌵㌤の猫)
@angel_p_57
だって、公開鍵暗号 E(m)=c, m=D(c) において m,c の集合が同じである必然性もないし、なんなら乱数を混ぜる形 c=E(m,r), m=D(c) も出てきていて、そっちだと g(f(x))=x の形にすらならない。
2024-05-23 23:41:42
angel (as ㌵㌤の猫)
@angel_p_57
つまり公開鍵暗号があっても、そういうのだと成立しない話になっちゃう。典型的なのは Elgamal暗号ね。なのであくまで「実現するためのアイデアの1つ」でしかなくて、それを例えば「原理」とか言っちゃうようなのは違うよね、ってことで。
2024-05-23 23:41:43
angel (as ㌵㌤の猫)
@angel_p_57
ところでちょっと補足しておくと、「mの集合・cの集合が有限かつ同じ集合であること」ってのは、これでなくちゃいけないってことはない。「有限かつ要素数(濃度)が等しい」でも良いから。ただ、アイデアとしてそういう前提が置かれていただけで。
2024-05-23 23:41:44
angel (as ㌵㌤の猫)
@angel_p_57
とは言え、「『有限』って条件要る? 同じ集合ならエエんちゃう?」と気になった方には一応反例を。つまり f,g を使って言うと、f: X→Y, g: Y→X (X=Y, X,Yは無限集合) があったときに、g(f(x))=x が成立するけど f(g(y))=y が成立しないことがある。
2024-05-23 23:41:45
angel (as ㌵㌤の猫)
@angel_p_57
まあ、めちゃ単純な例だから自力で見つけられそうな気はするけど。X=Y=Z (全整数) として f(x)=2x, g(y)=[y/2] ( [] はガウス記号、[] 内の値を越えない最大の整数値 ) とすれば g(f(x))=x だけ成立して f(g(y))=y は成立しない。f(g(y))=y-mod(y,2) だから。
2024-05-23 23:41:46