楕円曲線暗号のための数学6（GLV法と自己準同型写像）
初めに 今回は、楕円曲線の数学的な性質を用いたスカラー倍算の高速化手法の一つ、GLV法（Gallant-Lambert-Vanstone）を紹介します。 GLV法は小さいマルチスカラー倍算を利用するので、まずそちらから解説しましょう。 マルチスカラー倍算 一般に、楕円曲線の点 P_1, \dots, P_n, 整数 a_1, \dots, a_n が与えられたときに Q=a_1 P_1 + \dots + a_n P_n を求める操作をマルチスカラー倍算 （MSM : multi-scalar multiplication）といいます。 zk-SNARKなどでは大きな n（数千~数万）に対するMSMが現れます。そのアルゴリズムはまたの機会に紹介するとして、ここでは n=2, つまり楕円曲線の点 P_1, P_2 と、整数 x_1, x_2 に対して Q=x_1 P_1 + x_2 P_2
暗号で使われる標数2の体の実装
多項式の加算 2個の多項式 a と b の加算を考えます。多項式の加算は同じ次数の係数同士を足したものでした。 a+b=(a_7 X^7 + \cdots + a_0)+(b_7 X^7 + \cdots + b_0) = (a_7 + b_7)X^7 + \cdots + (a_0+b_0). 各係数は 𝔽_2 の要素なので加算は排他的論理和です。それをビットごとにすればよいので、結局整数として排他的論理和を取ればよいです。引き算もaddと同じですね。 typedef uint8_t K; K add(K a, K b) { return a ^ b; } K sub(K a, K b) { return add(a, b); } 多項式の乗算 まずはナイーブな実装から考えましょう。 多項式 a と b を掛けた結果 c=ab を f=X^8+X^4+X^3+X+1 で割ります。f が
RSA署名を正しく理解する
初めに 「署名とはメッセージのハッシュ値を秘密鍵で暗号化したものであり、検証は署名を公開鍵で復号してハッシュ値と等しいかを確認することである」という説明(×)をよく見かけます。 正しい署名の定義と実際のRSA署名がどのようなものであり、上記説明(×)がなぜよくないのかを理解しましょう。 署名の定義 署名の解説は署名の概要でも解説しましたが、再掲します。 署名（方式）は鍵生成（KeyGen）、署名（Sign）、検証（Verify）の3個のアルゴリズムからなります。 KeyGenではアリスが署名鍵sと検証鍵Sを生成します。署名鍵sは自分だけの秘密の値なので秘密鍵、検証鍵Sは他人に渡して使ってもらう鍵なので公開鍵ともいいます。 Signは署名したいデータmに対して署名鍵sを使って署名と呼ばれるデータσを作ります。 データmと署名σのペアを他人（ボブ）に渡します。 Verifyはボブが検証鍵Sを使
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
