ある当事者が作成した 64 バイトの署名 (ed25519 から) があるとします。この当事者は、署名をさらに圧縮して、基数 2048 で 4 ～ 8 桁になるようにする必要があります。次に、第 2 の当事者がデータから署名を再作成できる必要があります。
10 進数の署名の例を次に示します。
5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098
この署名を基数 2048 で約 4 桁に圧縮するにはどうすればよいですか? これは数独圧縮を使用して可能ですか?
これは不可能だと私は主張します。少なくとも「第二者はデータから署名を再作成できなければならない」と言う部分
この背後にある単純な理由は、エントロピー、つまり各署名に含まれる情報の量です。まず、あなたが説明した「フォーマット」ごとに、最大でどれだけの情報を保存できるかを見てみましょう。
つまり、すでに 2048 ベースの数字の (可能な最大の) 情報ははるかに少なくなっています。関数が存在するためには、2^512 の可能性の中で、十分な冗長情報があることを意味します (つまり、ビット a と b を知っている場合、ビット c を知っている可能性が高いか、値の構成を知っている可能性が高い)可能性のあるすべての出力を 44 (または 88) ビットで特徴付けることは完全に不可能です。
シャノンのソースコーディング定理を見てみましょう:
それぞれがエントロピー H(X) を持つ N iid 確率変数は、N → ∞ のように、情報損失のリスクを無視して N H(X) ビット以上に圧縮できます。しかし逆に、N H(X) ビット未満に圧縮された場合、情報が失われることは事実上確実です。
ここで確率変数は ed25519 署名です。あなたは2つのことを求めています
ed25519 署名には、44 または 88 ビットで格納できるよりも確実に多くのエントロピーがあります。Ed25519の紹介サイトから：
高いセキュリティ レベル。このシステムには 2^128 セキュリティ ターゲットがあります。それを破るには、NIST P-256、最大 3000 ビットの鍵を持つ RSA、強力な 128 ビットのブロック暗号などを破るのと同様の困難があります。既知の最高の攻撃は、実際には平均で 2^140 ビット以上の操作を必要とし、成功すると二次関数的に劣化します。ビット操作の数が減少するにつれて確率が低下します。
しかし、あなたの関数が存在する場合、すべての衝突を徹底的に見つけるために、「逆」関数を適用するたびに 2^44 (または 2^88) 回試行するだけで十分なので、おそらくはるかに簡単です。確かに、仮想的な逆関数のビット操作のコストはわかりませんが、少なくともアイデアは得られます。さらに、誕生日攻撃を使用してこのブルート フォース攻撃を行う場合、必要なのはこの試行回数の平方根 (つまり 2^22 または 2^44) だけです。
逆に、平均 2^140 回の操作でこの攻撃を行い、それぞれ 2^o 回の操作の 2^i 回の反復 (したがって i+o=140) を行う論文を読むと、合理的に列挙する形式を見つけることが期待できます。 2*i ビットの可能なすべての 64 バイト署名。ただし、これは最初の質問にのみ当てはまります。攻撃は、一部の署名値が他の値よりも頻繁に発生するなどのプロパティを利用する可能性があるためです。次に、2*i の最適なストレージ長は、より頻繁に発生する値よりも少ないビットでより頻繁に発生するいくつかの値をコーディングすることによって、すべての値ではなく平均でのみ到達されます。
これに加えて、次のように読みます。
小さな署名。署名は 64 バイトに収まります。これらの署名は、実際には長い署名の圧縮バージョンです。圧縮と解凍の時間は、上記のサイクル カウントに含まれています。
つまり、より大きなキーに冗長性があったとしても、それらはすでに余分な圧縮パスを実行しており、より小さなキーの情報密度が高くないとしても、同じであると合理的に推測できます。つまり、冗長性を見つける可能性はさらに低くなります。
したがって、これは、署名から 44 ～ 88 ビットへの変換を適用すると、情報が失われ、ほとんど64 バイトのハッシュが取得されることを意味します。チェックサムからダウンロードしたファイルを再作成することは不可能であるため、計算したハッシュから ed25519 署名を再作成することは不可能です。