SRVB暗号システム入門

公開: 2022-03-11

序章

情報セキュリティは、理論計算機科学からソフトウェアエンジニアリングに至るまで、さらには人為的ミスの心理学を観察することさえできる魅力的な知識分野です。

暗号化は現在、私たちの日常生活の多くの匿名の技術的ヒーローの1つです。ソーシャルネットワーク、Webバンキング、ミリタリーインテリジェンス、および機密情報を扱うその他の情報システムはすべて、暗号化に大きく依存しています。暗号化により、プライバシーを確保できます。プライバシーは、12番目の人権と見なされる人もいます。

この記事では、公開鍵暗号システムの背後にある原理を紹介し、記事の作成者とダニエル・サンタナ・ロシャ教授によって開発された暗号システムであるサンタナ・ロシャ・ヴィラス・ボアス（SRVB）を紹介します。これを書いている時点で、アルゴリズムの作者は、コードを解読することに成功した人への金銭的報酬を含むキャンペーンを作成しています。この記事ではアルゴリズム機能について詳しく説明しているので、ここから賞品の獲得を始めるのに最適な場所です。詳細については、SRVBサイトをご覧ください。

暗号システムとは何ですか？

暗号化は、メッセージの解釈可能性を妨げる方法ですが、特定の命令（通常はいわゆる「キー」）が提供されている限り、メッセージを実行可能に解釈する方法を提供します。これは、最も初期の技術を含む非常に広い定義ですが、これが情報セキュリティにあるすべてを網羅しているわけではないことを言及する価値があります。

暗号化手法とそれらを解読する方法の間の技術的競争は、決定的な勝者になることは決してないと予想されます。新世代はそれぞれ、情報セキュリティと暗号解読の基準を引き上げることが期待されています。これは、暗号化されたメッセージを体系的に解読/解読する、つまりセキュリティや暗号化をバイパスする一連の技術です。

暗号システム（暗号化の与えられた技術）がそのユーザーによって安全であると見なされるためには、それは専門家の国際社会の承認を受けなければならず、したがって公に知られている必要があります。これはケルクホフスの原理として知られています。しかし、この状況は、システムを世界の暗号解読コミュニティからの精査にさらします。暗号解読コミュニティは、暗号を体系的に解読する方法を考案しようとします。

意図されたエージェントだけがそれを解読できるように、同時に世界の暗号解読コミュニティがその堅牢性を証明できるように十分に公開されているように、特定の暗号化プロセスをどのように秘密にすることができますか？答えは、暗号学の重要な要素であるコンポーネント、つまりキーです。暗号システムのキーは、暗号化アルゴリズムまたは復号化アルゴリズム、あるいはその両方のパラメーターです。アルゴリズムファミリではなく、パラメータを秘密にしておくことで、両方の矛盾する要件を達成できます。パラメータのファミリが十分に大きく（おそらく無限）、その各コンポーネントが適切なプロパティを持っていることが証明できる場合、攻撃者が検査だけでパラメータを決定することは不可能です。

最後に、キーが効果的に機能するためには、キーを簡単に作成する必要がありますが、推測することはほぼ不可能です。今日のコンピューターの計算能力により、コンピューターは、人間が生成したキーを解読するのに必要な時間は、人間が想像するよりも少なくて済みます。さらに、その方法でキーを生成するのは費用効果が高くないという事実に加えて。そのため、キーはアルゴリズムによって生成される傾向があります。

キー生成アルゴリズムは、通常の使用の結果として予測可能/再現可能な出力を作成してはなりません。アルゴリズムはインテリジェントなプロセスなしで手順を実行するため、問題はこれをどのように実行できるかということです。答えは、キー生成アルゴリズムを、大量の真にランダムなビットをキーに変換するマップに変換することです。真にランダムなビットはオペレーティングシステムから取得でき、宇宙の不確実性からそれらを生成します。一部のソースは、アプリケーションに応じて、マウスの動き、ネットワークパッケージの遅延、または専用のハードウェアです。

公開鍵暗号システム

もう一度驚かれる準備をしてください。これから、今言ったことと一見矛盾する概念、つまり公開鍵を紹介します。

これまで、秘密のパラメータ（キー）が安全に交換された後に安全な通信が作成されるのを見てきましたが、パブリックチャネルを介してパラメータを交換する問題は残っています。ここでは、もう少し明白な問題を解決する概念を紹介します。それは、安全なチャネルの作成です。

アリスがボブと協力していて、暗号化を使用して仕事のやりとりを安全に保ちたいとします。彼らは、キーが付いたUSBフラッシュドライブを互いに与えることで、暗号化キーを満たし、交換することができます。しかし、アリスとボブが異なる大陸にいる場合はどうでしょうか。存在しない安全なチャネルを確立するにはどうすればよいですか？

競合他社のイブが交換を傍受し、キーを使用して暗号化されたすべてのデータを後で読み取ることができるため、電子メールでキーを送信することはできません。この機密データを送信できる他のデジタルチャネルがあれば、そもそも暗号化、つまりキーは必要ありません。そもそも機密情報を交換する必要があるため、物理的なメールでキーを送信することも傍受される可能性があります。他のデータ内に隠してステガノグラフキーを送信するのは賢明ですが、送信者が受信者と受信者だけがそのようなメッセージの存在を認識し、それを抽出する方法を知っていない限り、役に立ちません。たまたま、メッセージの存在を認識し、データからキーを抽出する方法の説明は、それ自体がキーの一種であり、それによって私たちは正方に戻ります。

解決策は、暗号化パラメータが元のメッセージを実行可能に解釈するのに十分ではない暗号システムを考案し^[1] 、メッセージの解釈を可能にするパラメータを自分自身に保持することです。そのパラメータを秘密鍵と呼びます。秘密鍵に基づいて、暗号化ツールの一連のパラメーターを実行可能に生成できます。これらの新しいパラメーター自体で秘密鍵が何であるかを明らかにすることはできません。そのパラメータのセットは、1人だけが復号化できる限り、誰が暗号化できるかはそれほど重要ではないため、公に共有できます。暗号化ツールのこのパラメータセットは公開できるため、公開鍵と呼ばれます。

暗号化キーと復号化キーが異なり、前者を使用して後者を推測できない暗号化は非対称暗号化と呼ばれますが、対称暗号化は、これらのキーが同じであるか、互いに簡単に推測できる場合に使用されます。

アリスはボブに公開鍵を送信します。これは、彼女だけが復号化できるものを暗号化するためにのみ使用できます（彼女が秘密に保持している秘密鍵を使用）。逆に、ボブはアリスに公開鍵を送信します。これは、暗号化にのみ使用できます。彼だけが復号化できること（彼も秘密に保持している彼の秘密鍵を使用して）。しかし、正確な逆アルゴリズムを推測できない暗号化アルゴリズムのパラメーターをどのように公開できるでしょうか。

その答えは、プログラミングに最も近い数学の分野である計算の複雑さの理論にあります。数学の問題を深く掘り下げた人なら誰でも、ある方法では簡単にできるが、逆の方法では難しい変換について聞いたことがあるでしょう。たとえば、微積分学では、教科書の導関数を見つけることは通常簡単な作業ですが、逆（たとえば、わずかに自明でない積分または教科書の物理的なODEまたはPDEを解くなど）を行うには、最初に関数のファミリーを仮定するより調査的なプロセスが必要です。解を含み、逆問題を解いてこれらのファミリーから解を見つけることが保証されています（または少なくとももっともらしい）。

RSA暗号システムで実際に使用されている例は、大きな素数を乗算することと、結果として得られる積を因数分解することです。乗算を行うのは簡単ですが、因数分解では、数百桁の素因数をランダムに^[2]推測する必要があります。操作の重要な特性は、適切にスケーリングする必要があることです。 RSAの素数のサイズに数桁を追加すると、暗号化プロセスの複雑さがわずかに増加する一方で、解読に数千倍の操作を必要とするキーが生成されます。非常に大まかに言えば、素数の積は暗号化に使用され、素因数のペアは復号化に使用されます。

これらすべてを念頭に置いて、SRVB暗号システムがどのように機能するかを見てみましょう。

基礎となるアルゴリズム-SRVBの調査

部分和問題

他の公開鍵暗号システムと同様に、SRVBは、生成が容易な特定の問題を解決することの難しさに依存しています。 SRVBの場合、これはサブセット和問題であり、次のように説明できます。

整数$w$と$v_1が与えられた場合、\ cdot \ cdot \ cdot、v_N \ in Z $は、$ \ sum_のように、シーケンス$ b_1、\ cdot \ cdot \ cdot、b_N \ in{0,1}$を見つけます。 {i = 1} ^ {N} v_i b_i =w$。

明らかに、この問題は、N個の整数をランダムに選択し、それらのサブセットをランダムに選択し、このサブセットを合計することによって発生する可能性があります。これは簡単なことです。

ブルートフォース検索の複雑さは$O（N * 2 ^ N）$であり、$ b$sの値の組み合わせごとに計算されます。より効率的なアプローチは、1972年にHorowitzとSahniによって与えられ、複雑さは$ O（N * 2 ^ {N / 2}）$でした。 $ b$sと$w$を$k$次元の整数ベクトルに置き換えると、問題は少なくとも同じくらい難しくなります。ただし、このより困難な問題が発生する領域には、以下に示すように、同じ問題のより簡単なバージョンが発生するリングとの同型性も必要です。このため、SRVBは、ガウス整数内のサブセット和問題を利用します。ここで、$ k =2$です。

欲張りアルゴリズムを使用することで、この問題を簡単に計算できる特殊なケースがあります。シーケンスのスケーリング係数$v_1、\ cdot \ cdot \ cdot、v_N $を並べ替えると、シーケンス内の各整数は、その前にあるすべての整数の合計よりも大きくなります（$ \ forall i、\ sum_ {j = 1} ^ {i-1} v_j <v_i $）、貪欲なアプローチを使用して、線形時間でシーケンスbを見つけることができます。記述されたプロパティを持つシーケンスは、超増加シーケンスと呼ばれます。

この場合の欲張りソリューションの簡単な説明は次のとおりです。

$ i = N $、現在観測されている係数、および$ w'= w $、残りの$w$から始めます。
現在の倍率が大きすぎて$w$の残りの部分に収まらない場合、つまり$ v_i> w'$の場合は、$ b_i = 0 $に設定して、次の手順に進みます。それ以外の場合は、スケーリング係数がシーケンス内にある必要があることがわかり（残りの係数は$ v_i $より小さいため）、$ b_i =1$に設定します。
$ w'\ Leftarrow w'--v_i * b_i $、$ i \ Leftarrowi-1$。 $ i> 0 $の場合は、手順2に戻ります。
ここで、$ w'== 0 $であることを確認します。そうでない場合、問題は破損しています。

これが機能するのは、現在観測されている乗数よりも小さいすべての乗数が、現在の乗数が可能な限り多くの（サブ）合計$w'$をまとめてカバーできないことがわかっているためです。したがって、残りの合計が現在の係数よりも大きい場合、後続のすべての係数を合わせても、現在の係数の助けがなければ合計に失敗することは確実です。一方、すべての乗数が正であるため、現在の係数$ v_i$が残りの合計$w'$よりも大きい場合、他の係数を追加すると、結果は$w'$をさらに上回ります。

記事の残りの部分の表記を設定しましょう。 $ v_1、\ cdot \ cdot \ cdot、v_n $、および$ w $を超増加シーケンスの係数および合計として選択し、$ u_1、\ cdot \ cdot \ cdot、u_n $、および$y$を公開します。 $ b_1、\ cdot \ cdot \ cdot、b_n$を回復するために提供される使用可能なパラメーター。

シーケンス$u_1、\ cdot \ cdot \ cdot、u_n $が選択されているため、超増加せず、番号$ y $が公開されているため、シーケンス$ b_1、\ cdot \ cdot\cdotを復元するための十分な情報が公開されていません。、b_n$。ただし、シーケンス$ u_1、\ cdot \ cdot \ cdot、u_n$の代わりになり得る超増加シーケンス$v_1、\ cdot \ cdot \ cdot、v_n $がある場合は、このシーケンスを使用して問題を解決できます。貪欲なアプローチ。

以下に、それがどのように機能するかを示します。

以前の暗号システムでのサブセット和の使用

1978年、ラルフ・マークルとマーティン・ヘルマンは、これら2つのナップザックのパラダイムとモジュラス演算の線形性を利用して、前のセクションで説明した2つのシーケンス間の接続を構築する方法を考案しました。アイデアは、秘密のオペランドを使用した線形演算（モジュラス）を使用して、簡単なナップザック（整数の超増加ベクトルで構成されるもの）を難しいもの（このプロパティを欠くもの）に変換することでした。変換は、すべての$v_i$に$\theta $を乗算し、この積の残りを$ \ alpha $で取得することで構成されます。ここで、$ \ alpha \ gt \ sum_ {i = 1} ^ Nv_i$および$\gcd （\ alpha、\ theta）= 1 $（まもなく正当化される2つの制約）。結果、シーケンス$ u_1、\ ldots、u_N $は、もはや超増加しておらず、ハードナップザックと見なすことができます。

シーケンス$u_1、\ ldots、u_N $のランダム順列は、暗号化してメッセージを送信したいパーティに与えられます。順列は、サードパーティが元の超増加シーケンスが何であるかを推測するのに苦労するように行われます。メッセージのビットブロックは、係数$ b_1、\ ldots、b_N$として使用されます。暗号化は、キーシーケンスにこの係数のシーケンスを乗算し、その乗算を合計して結果を算出することで実行されます。これに$y$というラベルを付けます。秘密鍵の所有者のみが、$y$を対応する$w$に変換できます。これは、これらの同じ$ b_1、\ ldots、b_N $ブロックに簡単な整数（シーケンス$ v_1、\ ldots）を掛けた場合に取得されます。、v_N $）。これは、$y$に$\theta ^ {-1} $を掛けることによって行われます。これは、$ \theta$モジュラス$\alpha $の逆数です（その存在は$ \ gcd（\ alpha、\ theta）= 1 $）。つまり、$（\ theta * \ theta ^ {-1}）\ bmod \ alpha =1$です。その後、$ w =（y * \ theta ^ {-1}）\ bmoda$を計算します。これが機能することが保証されている理由は、モジュラスの線形性、つまり、剰余の線形結合が線形結合の残りに等しいためです。

$ u $の定義、商環、および剰余演算子の線形性のプロパティを連続して適用すると、次の対応がわかります。

$ \ begin {align} y＆= \ sum_ {i = 1} ^ N b_iu_i \ newline＆= \ sum_ {i = 1} ^ N b_i（v_i * \ theta \ bmod \ alpha）\ newline＆= \ sum_ { i = 1} ^ N b_i * v_i * \ theta \ bmod \ alpha \ newline＆= \ left [\ sum_ {i = 1} ^ N b_i * v_i * \ theta \ right] \ bmod \ alpha \ newline＆= \ left [\ sum_ {i = 1} ^ N b_i * v_i \ right] * \ theta \ bmod \ alpha \ newline＆= w * \ theta \ bmod \ alpha \ end {align} $

したがって、簡単な合計$ w $は、両側に$ \ theta ^ {-1} $を掛け、モジュラスを$ \alpha$にすることで回復できます。そのためには、$ \alpha$と$\theta $（$ \ theta ^ {-1} $を簡単に計算できる）の両方を知っている必要があります。これらは秘密鍵の一部として秘密にされます。

1つの制約$\alpha \ gt \ sum_ {i = 1} ^ N v_i $は不当に残されており、その説明は次のとおりです。2行目と3行目の等式は、商の剰余クラス間の等式で構成されます。 $ \alpha$を法とする整数環。言い換えると、$ \ alpha $で割ったときの残りのメンバーの同等性のみを示します。これは、メンバー自体の同等性にとって十分な条件ではありません。その結果、$b$値の複数のベクトルを単一の$y$にマッピングできます。これは、可能な最大の包含（つまり、すべての区画$ v_i $の合計）を$ w_{max}$に制限することによって防止されます。 $ b $値の任意の組み合わせについて、$ \alpha$より小さくします。

日常生活の他の例と同じように、すべての仮説を完全に知ることはしばしば不可能であり、決して容易ではありません。その結果、暗号システムが安全に使用できるかどうかを判断する際には、数学的な直感に頼らなければならず、実際の保証はありません。作成から6年後、MH暗号システムはA.Shamirによる攻撃で破壊されました。 MHを復活させるためにさらにいくつかの試みがありましたが、その多くも失敗しました。

サンタナロシャ-ヴィラボアス（SRVB）暗号システム

2016年、この記事の著者と暗号システムのさまざまなインスピレーション^[3]の可能性についてブレインストーミングを行った後、DanielSantanaRochaは$\theta$と$\alpha$をガウス整数に置き換えることを思いつきました。より技術的な理由から、このアプローチは前述のシャミール攻撃に対する抵抗につながります。

彼はまた、ハードナップザックの前述の線形結合の多くのステップで構成されるビットブロックを考案しました。それらのそれぞれで、1に相当する、以前のすべての合計よりも大きい新しい（ガウス）整数がシーケンスの最後に追加され、現在最小のものは削除されます。

異なるがエレガントに類似した制約が$\alpha $に適用されます。これは、現在はガウス整数です。 $ w_ {max} \ leq \ vert \ alpha \ vert ^2$が必要です。理由を形式化するのは非常に困難ですが、幸いなことに、エレガントな説明から簡単に直感的に理解できます。

複素数の平面内の正方格子を想像してください。その辺は、実数軸と虚数軸に平行な、隣辺aとbの直角三角形の斜辺です。そのような格子の例を以下に示します。 $ \ alpha = a + bi $を法とするグアシアン整数は、そのような格子内にある点で表すことができます。このようなラティス内には、$ \ vert \ alpha \ vert ^2$個の異なるポイントがあります。十分な大きさの$\alpha $を選択すると、簡単なナップザックの線形結合をすべて適合させることができます。

これは、同型写像$ f：Z / n \ rightarrow Z [i] /（\ alpha）$のグラフィック表現です。ここで、$ n =13$および$\alpha = a + bi = 3 + 2i $です（$ n$と$\alpha $は、実際に$ n = \ vert \ alpha \ vert ^ 2 = a ^ 2 + b ^ 2 $を必要に応じて満たします）。ドットはガウス整数、つまり複素数$ a + bi $を表します。ここで、$a$と$b$は整数です。いつものように、横軸は実数部を表し、縦軸は虚数部を表します。したがって、1つのドットを右または左に移動することは、現在の値にそれぞれ+1または-1を追加することと同じです。同様に、1つのドットを上または下に移動することは、それぞれ+iまたは-iを追加することに対応します。

赤い点は、$ 0 \ bmod（\ alpha）$に相当するものです。これらとは別に、さらに4組のドットに色を付けました。

色	…modαに相当
オレンジ	$ 1 $
緑	$ i $
青い	$ -1-i $
バイオレット	$ 1-i $

同型$f$は、循環シーケンス$（0,1,2、\ cdot \ cdot \ cdot、10,11,12,0,1,2、\cdotの$i$番目の要素の変換によって定義されます。 \ cdot \ cdot）$を、図のドットの循環シーケンスの$ i $番目の要素に追加します。これは、次の規則に従います。

最初の行の赤い点から始まります。
水平方向の右矢印に従います。それ以外で
矢印をたどると、格子の外側のシーケンスが進み、黒以外のポイントの1つに到達します。そのポイントに移動する代わりに、同じ正方形内の同じ色のポイント（つまり、$ \ alpha $を法とする同等のポイント）にジャンプします。そして最後に
この黒以外の点がたまたま赤になると（他のすべての色が通過した後に発生します）、シーケンスは一番上の赤い点にジャンプし、サイクルを再開します。

少なくとも$Y$の自然整数をマッピングするには、面積が$ \ vert \ alpha \ vert ^ 2 $の正方形をとる必要があります（ここで、$ \ vert \ alpha \ vert = \ sqrt {a ^ 2 + b ^ 2} $は、ピタゴラスの定理によれば、その辺の尺度です）少なくとも同じくらい高いです。

行を上から数えると、各「ジャンプ」によって行番号$r$が$r\ leftarrow（r + b）（mod a + b）$に変更され、同等に$ r \ leftarrow（r + a）（mod a + b）$（下から上に数える場合）。したがって、各行（およびドット）が各サイクルで1回だけローミングされるための必要十分条件は、ジャンプのサイズが行の数と互いに素である、つまり$ gcd（a、a + b）= gcd（b、a + b）=1$。最大公約数演算子の特性により、これらは両方とも$ gcd（a、b）=1$と同等です。

YSヴィラズボアスは、$a$と$b$の共原性の必要性に気づきました。超増加を維持するために、シーケンスの最後に追加された新しい整数$ w $は、現在のすべての整数の合計を超える必要があります（$ w> \ sum_ {i = 1} ^ k v_i $）。彼は、これを達成するために、それらの乗算係数$ b_i $は少なくとも1でなければならず、したがって、各ビットを係数0および1にマッピングできないことを観察しました。係数が0および1の場合、ブロックのみ一つだけで構成されていると、超増加を満足させるでしょう。このため、ビット0と1はそれぞれ乗算係数1と2にマッピングされました。

最後に、それほど簡単ではありません。デコードの各ステップで、方程式$ b_1 v_1 = v_ {n + 1}-\ sum_ {i = 2}^{n}の解として1つの新しい整数$v_1$が見つかります。 b_i v_i $、ここですべての$v_i$と$b_i$は$1<i \ leqn$で知られています。 $ b_1 $もわからないため、1つの方程式と2つの変数を持つシステムになり、1つの自由度が残ります。これを修正するには、常に$ b_1 $に割り当てられる1つの正の値（簡単にするために1）を調停する必要があります。これにより、あいまいさがなくなります。したがって、最初の係数は1に固定されているため、各ステップで$ n $ビットをエンコードするには、整数のシーケンスは$ n +1$要素の長さである必要があります。

解決すべき最後の技術の1つは、メッセージのバイト単位のサイズがブロックサイズの倍数ではない場合です。言い換えると、最後のデータブロックの残りのバイトの可能性をどのように処理して、データブロックが回復されると、元のコンテンツのすべてのバイトが保持されますが、それ以上は保持されないようにしますか？メッセージの最後のバイトを1回繰り返すことで、これを解決しました。このコピーの後には、各コンポーネントが前のコンポーネントと異なるだけでよいランダムシーケンスが続きます。したがって、データブロックが取得されると、最後のデータブロック、または最悪の場合、最後の前のデータブロックがバイトの最後の繰り返しで切り捨てられます。 ^[4]

次に、SRVB暗号システムの例を示します。

パラメータから始めます。

$ k = 4 $;

$ m = 4 $;

これにより、ブロック長は$ l = 4 * 4 = 16 $になり、$ k + 1 = 5 $の自然整数の超増加シーケンスが生成されます。つまり、線形結合され、この線形結合の結果が追加されます。最後の$k+ 1 $要素に削減— $ m =4$回;

簡単にするために、以下を$ v_i $の（超増加）ベクトルとします。

$（1,2,4,8,16）$

実際、2の最初の5乗のシーケンスは、これが5つの要素と可能な限り最小の厳密に正の値を持つ超増加シーケンスであるという理由だけで（したがって、公開鍵の0を回避し、対応する対応する0を自明に与える））。

前に述べたように、$ \ alpha = a + bi $の場合、整数$a$と$b$は互いに素でなければならず、前述の新しい制約に従って、$ a ^ 2 + b^2を要求する必要があります。 = \ vert \ alpha \ vert ^ 2 \ geqW$。簡単に計算すると、$ W =1590$になります。 $ \ sqrt {1590} \ simeq 39.8 $なので、選択するのに非常に便利な$ \ alpha $は、$ \ alpha = 39 + 40i $になります。これは、整数の環を持つ同型を収容するのに十分な大きさであるためです。 $ gcd（a、b）= 1 $も満たしながら、少なくとも1590コンポーネント。また、$ gcd（a、\ theta）= 1 $ ^[5]となるように、できれば低すぎないように$ \ theta $を選択する必要があります。これにより、$（a_1 * \ theta）\％\ alpha \ neq v_1 * \ theta $、（情報の提供を避けるためにも）。 $ \ theta = 60 $がその役割を果たし、次のようになります。

$ -19-1i、1 + 38i、3-3i、6-6i、12-12i $ ^[6]

では、手を汚しましょう。 Hello Toptal!というメッセージを受け取ります。。まず、ASCIIとデータブロックを切り捨てるための規則に従って、バイトの配列にマップします。

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

データブロックは16ビット=2バイトの長さであり、メッセージは13文字であるため、それぞれ2バイトの7つのデータブロックになります。最後のデータブロックには、文字「！」の2倍のビット表現が含まれます。。最初のブロックを段階的に暗号化してみましょう。各バイトのビットは重要度の高い順に取得されるため、細心の注意を払ってください。

$ m = 01001000 01100101 $

最初のバイトの最初のニブル：$（0,0,0,1）\ rightarrow（1,1,1,1,2）\ cdot（-19-1i、1 + 38i、3-3i、6-6i、12 -12i）= 15 + 4i $
最初のバイトの2番目のニブル：$（0,0,1,0）\ rightarrow（1,1,1,2,1）\ cdot（1 + 38i、3-3i、6-6i、12-12i、15 + 4）= 49 + 9i $
2番目のバイトの最初のニブル：$（0,1,0,0）\ rightarrow（1,1,2,1,2）\ cdot（3-3i、6-6i、12-12i、15 + 4i、49 + 9i）= 106-10i $
2番目のバイトの2番目のニブル：$（0,1,1,0）\ rightarrow（1,1,2,2,1）\ cdot（6-6i、12-12i、15 + 4i、49 + 9i、106- 10i）= 252-2i $

したがって、マッピングしたばかりです

「彼」$\Rightarrow（12-12i、15 + 4i、49 + 9i、106-10i、252-2i）$

暗号化されたメッセージの残りの部分は次のとおりです。

「ll」$\Rightarrow（12-12i、21-2i、61-3i、185-31i、367-59i）$

「o」$\Rightarrow（12-12i、25 + 33i、65 + 32i、111 + 44i、244 + 124i）$

「宛先」$\Rightarrow（12-12i、9 + 10i、46 + 12i、149 + 5i、277 + 31i）$

「pt」$\Rightarrow（12-12i、3 + 16i、46 + 12i、73 + 23i、201 + 49i）$

「al」$\Rightarrow（12-12i、4 + 54i、44 + 53i、117 + 193i、231 + 389i）$

” !!” $ \ Rightarrow（12-12i、4 + 54i、32 + 65i、63 + 92i、121 + 247i）$

ここで、復号化のために、$ \ theta ^ {-1} = 60 ^ {-1} = 27 +i$があります。

$（$” He” $ \ Rightarrow）$ $（12-12i、15 + 4i、49 + 9i、106-10i、252-2i）* \ theta ^ {-1} \％\ alpha =（16,47 、93,223,527）$

さて、欲張りアルゴリズムが登場します：

最初に、各寄与係数に1を掛けたものを減算します。これは、それらが最後に少なくとも1回寄与したことがわかっているため、次のようになります。

2番目のバイトの2番目のニブル：

$ T \ leftarrow（527-233-93-47-16）= 148 $

$（T \ geq 223）=（148 \ geq 223）= false \ Rightarrow b_1 = 0; T \ leftarrow（T-0 * 223）= 148 $

$（T \ geq 93）=（148 \ geq 93）= true \ Rightarrow b_2 = 1; T \ leftarrow（T-1 * 93）= 55 $

$（T \ geq 47）= 55 \ geq 47）= true \ Rightarrow b_3 = 1; T \ leftarrow（T-1 * 47）= 8 $

$（T \ geq 16）= 8 \ geq 16）= false \ Rightarrow b_4 = 0; T \ leftarrow（T-0 * 16）= 8 $

結果：0110;

剰余：8（新しい最下位要素としてシーケンスの先頭に追加）。

現在のシーケンスの最後から527をドロップします。

2番目のバイトの最初のニブル：

$ T \ leftarrow（233-93-47-16-8）= 59 $

$（T \ geq 93）=（59 \ geq 93）= false \ Rightarrow b_1 = 0; T \ leftarrow（T-0 * 93）= 59 $

$（T \ geq 47）=（59 \ geq 47）= true \ Rightarrow b_2 = 1; T \ leftarrow（T-1 * 47）= 12 $

$（T \ geq 16）=（12 \ geq 16）= false \ Rightarrow b_3 = 0; T \ leftarrow（T-0 8 16）= 12 $

$（T \ geq 8）=（12 \ geq 8）= true \ Rightarrow b_4 = 1; T \ leftarrow（T-0 * 12）= 4 $

結果：0101;

剰余：4（新しい最下位要素としてシーケンスの先頭に追加）。

現在のシーケンスの最後から233をドロップします。

最初のバイトの2番目のニブル：

$ T \ leftarrow（93-47-16-8-4）= 18 $

$（T \ geq 47）=（18 \ geq 47）= false \ Rightarrow b_1 = 0; T \ leftarrow（T-0 * 47）= 18 $

$（T \ geq 16）=（18 \ geq 16）= true \ Rightarrow b_2 = 1; T \ leftarrow（T-1 * 16）= 2 $

$（T \ geq 8）=（2 \ geq 8）= false \ Rightarrow b_3 = 0; T \ leftarrow（T-0 * 8）= 2 $

$（T \ geq 4）=（2 \ geq 4）= false \ Rightarrow b_4 = 0; T \ leftarrow（T-0 * 4）= 2 $

結果：0100;

剰余：2（新しい最下位要素としてシーケンスの先頭に追加）。

現在のシーケンスの最後から93をドロップします。

最初のバイトの最初のニブル：

$ T \ leftarrow（47-16-8-4-2）= 17 $

$（T \ geq 16）=（17 \ geq 16）= true \ Rightarrow b_1 = 1; T \ leftarrow（T-1 * 16）= 1 $

$（T \ geq 8）=（1 \ geq 8）= false \ Rightarrow b_2 = 0; T \ leftarrow（T-0 * 8）= 1 $

$（T \ geq 4）=（1 \ geq 4）= false \ Rightarrow b_3 = 0; T \ leftarrow（T-0 * 4）= 1 $

$（T \ geq 2）=（1 \ geq 4）= false \ Rightarrow b_4 = 0; T \ leftarrow（T-0 * 2）= 1 $

結果：1000;

剰余：1（新しい最下位要素としてシーケンスの先頭に追加されます）;

現在のシーケンスの最後から47をドロップします。

その結果、メッセージの最初の2文字「He」を含むデータブロック「0100100001100101」を復元しました。それだけでなく、秘密鍵の超増加シーケンス$（1,2,4,8,16）$も正しく取得しました。

他のデータブロックマップも同じように機能します。

主要な公開鍵暗号システムとの比較

SRVBは次のとおりです。

完全に無料で公開されています。
ECC ^[7]よりもかなり単純で、理解と実装が容易です。
たとえば、高価な素数に依存するRSAとは対照的に、キーが豊富で、実質的にコストがかかりません。

最も可能性の高い脆弱性はすでに要約できます。 SRVBはMHの子孫であるため、Shamir攻撃の一般化、またはそれを破壊する他の攻撃に対して脆弱であると容易に推測できます。著者にはこれが当てはまらないと信じる理由がありましたが、それの確認はまだ行われていません（これは暗号システムを扱う場合に非常に一般的です）。

次は何ですか？

Rochaは、使用される商環のいくつかの一般化を観察しました。これは、暗号解読の複雑さの増加につながる可能性があります。これらの可能性についても調査します。

線形代数の不明瞭化

たまたま、SRVBの開発と文書化の間に、Villas Boasは、この記事が長くなりすぎないようにするために、ナップザック公開鍵暗号システムの概念を改善するためのさらに別のアプローチを考え出しました。面倒ですが、ここにそのスキミングがあります。それを把握できなくても、心配しないでください。次の記事のリリースにご期待ください。詳細については、さらに詳しく説明します。たとえば、サブセットの合計$y$を参照してください。 $N$の剰余環要素$u_i$（前と同じように超増加シーケンスの正の整数$ v_i $に同形的に対応します）は、これらの$u_i$の行ベクトルと列ベクトル$B$（ゼロと1のバイナリ） ^[8] 。

$ y = \ sum_ {i = 1} ^ n u_i b_i =（u_1、\ cdot \ cdot \ cdot、u_n）^ T \ cdot（b_1、\ cdot \ cdot \ cdot、b_n）$ = UB、

ここで$b_i\ in {0,1} $

ここで、この$ u_i $のベクトルの代わりに、左側に$ n $ x $ N $（$ n <N $）の行列Vがあり、$ v_i $（超増加からの整数）があると想像してください。シーケンス）ベクトルとして（一般性を失うことなく）その最初の行と他のすべてのエントリがノイズでいっぱいになります。ここで、Vに同じビットベクトルBを掛けると、最初のエントリとして$ w $があり、他のエントリにはノイズがある列ベクトルWが得られることに注意してください。ここで、このV行列を取り、左側にランダムな^[9] n x n行列Rを掛けて、nxN行列Pを定義します。

P = RV

ボブはPを新しい公開鍵として使用するという考え方です。 Rのランダム性のため、ベクトル

$ Y = PB = RV B = RW $

Vの他の行のノイズによって隠された情報$w$を持っています。ボブはまた、事前に計算し、以下を満たす行ベクトルSを格納します。

$ R ^ TS ^ T = e_1 $

アリスがYをボブに送信すると、次の理由でSYが見つかります。

$ SY = S（PB）= S（（RV）B）= SRVB = {e_1} ^ TR ^ {-1}（（RV）B）= $

（これまでのところ定義のみ）

$ {e_1} ^ T（VB）= {e_1} ^ TW = w $

（現在、結合性を利用してRをキャンセルします）

次に、前と同じように、欲張りアルゴリズムを使用して$w$から$b_i$のベクトルを抽出します。

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

謝辞

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

用語集

Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.