ECCツイン多様化

Nov 10 2020

iOSからCommonCryptoを実装しているときに、次のような関数が呼び出されてCCECCryptorTwinDiversifyKeyいることに気付きました。

2つのスカラーを導出することにより、特定のECキーを多様化します $u,v$ 与えられたエントロピーから。

しかし、その説明から、関数が何をするのか、いつ使用されるのかを推測することができました。インターネットで「EC多様化」と「ECツイン多様化」を探してもヒットしませんでした。だから私の質問は：ECキーについて話すときの双子の多様化とは何ですか？それはいつ使用されますか？

回答

2 kelalaka Nov 10 2020 at 20:01

ツインダイバーシファイ

私が見つけた情報源は1つだけです。AppleのCommonCryptoのオープンソース。すべてCommonECCryptor.hから

@function   CCECCryptorTwinDiversifyKey

@abstract   Diversifies a given EC key by deriving two scalars u,v from the
            given entropy.

@discussion entropyLen must be a multiple of two, greater or equal to two
            times the bitsize of the order of the chosen curve plus eight
            bytes, e.g. 2 * (32 + 8) = 80 bytes for NIST P-256.

            Use CCECCryptorTwinDiversifyEntropySize() to determine the
            minimum entropy length that needs to be generated and passed.

            entropy must be chosen from a uniform distribution, e.g.
            random bytes, the output of a DRBG, or the output of a KDF.

            u,v are computed by splitting the entropy into two parts of
            equal size. For each part t (interpreted as a big-endian number),
            a scalar s on the chosen curve will be computed via
            s = (t mod (q-1)) + 1, where q is the order of curve's
            generator G.

            For a public key, this will compute u.P + v.G,
            with G being the generator of the chosen curve.

            For a private key, this will compute d' = (d * u + v) and
            P = d' * G; G being the generator of the chosen curve.

ユースケース

CryptoCurrenciesのように、常にリンクされている同じ公開鍵を使用する場合など、ある程度の匿名性が必要な場合は、多様化が必要です。公開鍵を秘密鍵/公開鍵で多様化できる場合は、多様化した新しいIDを使用でき、元のIDと簡単にリンクすることはできません。

上記のスキームでは、で多様化された新しい公開鍵 $u$ そして $v$ になります $$[u]P + [v]G$$ 多様化した秘密鍵は

$$d' = (d \cdot u + v)$$ 多様化した公開鍵の検証

$$P' = [d']G = [d \cdot u + v]G = [d \cdot u]G + [v]G = [u]P + [v]G $$

要するに、あなたは新しいアイデンティティを持っていますが、カーテンの後ろでは、それはまだあなたです。

安全に多様化できる人は何人いますか？

いくつかの仮定が必要であると答えるために、ユーザーが生成できるようにします $u,v$ ランダムに均一-それは重要です-、 $2^{30}$ システムのユーザー（10億強）、そして各ユーザーは多様化しています $2^{20}$ 彼らの生涯の回-それは百万を少し超えています-。

次に、古典的な誕生日の計算を使用して、周囲にある可能性のある曲線の衝突の確率を確認します。 $2^{256}$ 公開鍵。

ランダムに選択されたユニフォーム間の衝突の確率という事実を使用します $k$ のセットの要素 $n$ 要素は次のように近似できます

$$(2^{k})^2/2^{n}/2=2^{2k-n-1}$$

私たちの $k = 2^{50}$ そして $n = 2^{256}$、その後;

$$(2^{50})^2/2^{256}/2 = 2^{100 - 256 - 1} = 1/2^{157}.$$

衝突確率が近いとき $1/2^{100}$私たちは単にそれが起こらないと言っています。したがって、P-256やCurve25519のような256ビットカーブでは衝突は発生しません。

新しいアイデンティティを作成するだけでなく、これの利点は何ですか？

主な違いは、このIDが最初のIDに接続されていることを簡単に証明できることです。 $u$ そして $v$。ランダムIDを最初のIDに接続することは、Dlogの問題と同じです。