SRVB暗号システムから始める

前書き

情報セキュリティは、理論計算からソフトウェアエンジニアリング、さらにはヒューマンエラーの心理学まで、あらゆるものを含むことができる魅力的な知識分野です。

Cryptoは現在、私たちの日常生活における多くの匿名のハイテクヒーローの1人です。ソーシャルメディア、Webバンキング、ミリタリーインテリジェンス、および機密情報を扱うその他の情報システムは、暗号化に大きく依存しています。暗号化により、プライバシーを確​​保できます。 12番目の人権 。

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

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

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

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

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

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

最後に、キーが効果的に機能するためには、簡単に作成できなければなりませんが、推測することはほとんど不可能です。今日のコンピューターの計算能力により、コンピューターは、人間が生成したキーを解読するのに、人間が想像するよりも短い時間で済みます。さらに、その方法でキーを生成することは有益ではありません。そのため、キーはアルゴリズムによって生成される傾向があります。

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

公開鍵暗号システム

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

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

アリスがボブと協力していて、暗号化によって仕事のやりとりを安全に保ちたいとしましょう。 USBフラッシュドライブをキーと一緒に渡すことで、暗号化キーを見つけて交換できます。しかし、アリスとボブが異なる大陸にいる場合はどうなるでしょうか。何もない場所に安全なチャネルを確立するにはどうすればよいですか？

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

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

暗号化キーと復号化キーが異なり、前者を使用して後者を推測できない暗号化は非対称暗号化と呼ばれますが、対称暗号化は、これらのキーが同じであるか、互いに簡単に推測できる場合に使用されます。アリスはボブに自分だけが復号化できるものを暗号化するためにのみ使用できる公開鍵を送信し（彼女は秘密にしておく秘密鍵を使用）、逆に、ボブはアリスに公開鍵を送信します。彼だけが復号化できること（彼も秘密にしておく彼の秘密鍵を使用して）。しかし、正確な逆アルゴリズムを推定できない暗号化アルゴリズムのパラメーターをどのように投稿できますか？

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

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

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

基礎となるアルゴリズム：SRVBを調べる

部分和問題

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

Dado el entero $ w $および$ v_1、 cdot cdot cdot、v_N in Z $ encuentra la secuencia $ b_1、 cdot cdot cdot、b_N in {0,1} $、たとえば$ sum_ {i = 1} ^ {N} v_i b_i = w $。

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

ブルートフォース検索の複雑さは$ O（N * 2 ^ N）$であり、$ b $ sの値の組み合わせごとに計算されます。より効率的なアプローチはによって与えられました 1972年のホロヴィッツとサーニ 、複雑度O（N * 2N / 2）。 $ b $ sと$ w $を$ k $（整数の次元ベクトル）に置き換えると、問題は少なくとも同じくらい難しくなります。ただし、このより困難な問題を実行する必要があるスコープには、 同型 [ring]（https://en.wikipedia.org / wiki / Ring_（math））を使用すると、次に説明するように、同じ問題のより簡単なバージョンが実行されます。このため、SRVBは内のサブセット和問題を悪用します ガウス整数 、ここで$ k = 2 $。。

この問題は、欲張りアルゴリズムを使用して簡単に計算できる特殊なケースがあります。スケールファクター$ v_1、 cdot cdot cdot、v_N $のシーケンスを注文すると、シーケンス内の各整数は、その前にあるすべての整数の合計よりも大きくなります（$ forall i、 sum_ {j = 1 } ^ {i-1} v_j過度の拡大のシーケンス 。

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

1. これは、現在観測されている因子である$ i = N $で始まり、$ w ’= w $で始まり、残りの$ w $

2. 現在のスケール係数が大きすぎて$ w $の余りに収まらない場合は、$ v_i> w '$を意味し、$ b_i = 0 $を設定して、次のステップに進みます。それ以外の場合は、スケール係数がシーケンス内にある必要があることがわかっているため（残りの係数は$ v_i $未満であるため）、$ b_i = 1 $とします。

   メモリリークがあるかどうかを見分ける方法

3. $ w ’ Leftarrow w’-v_i * b_i $、$ i Leftarrow i-1 $。 Si $ i> 0 $、vuelve al paso2。

4. ここで$ 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 $がある場合、このシーケンスを使用して、貪欲なアプローチの問題。

cvvコードをバイパスする方法

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

古い暗号システムでサブセットの合計を使用する

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

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

$ 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} $を簡単に計算できます）。これらは秘密鍵の一部として秘密にしておく必要があります。

単一の制限$ alpha gt sum_ {i = 1} ^ N v_i $は正当化されませんでした。ここに、説明があります。2行目と3行目の等式は、 廃棄物の種類 の 商環 $ alpha $を法とする整数の。言い換えると、$ alpha $で割ったときに、残りのメンバーの同等性のみを設定します。 これはメンバーの平等のための十分条件ではありません 。その結果、$ b $値の複数のベクトルを単一の$ y $にマッピングできます。これは、$ b $値の任意の組み合わせに対して$ w $を$ alpha $未満に制限することで回避できます。

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

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

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

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

異なるがエレガントに類似した制約が$ alpha $に適用され、これは現在ガウス整数になっています。 $ w leq vert alpha vert ^ 2 $が必要です。ここでも、$ w $は、簡単なバックパックの自然整数の最も高い線形結合です。理由を形式化するのは非常に困難ですが、幸いなことに、エレガントな説明から簡単に推測できます。

複素数平面の正方格子を想像してみてください。その辺は直角三角形の斜辺です。 足 aとb、実軸と虚軸に平行。このような格子の例を以下に示します。 $ alpha = a + bi $を法とするガウス整数は、上記の格子内にある点で表すことができます。このネットワーク内には、$ vert alpha vert ^ 2 $の異なるポイントがあります。十分な大きさの$ alpha $を選択すると、簡単なバックパックのすべての線形結合に適合できます。したがって、$ w leftarrow vert alpha vert ^ 2 $の要件を設定しています。ここで、wは[説明どおり]です。

これは、同型写像$ 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を追加することと同じです。同様に、ポイントを上下に移動することは、それぞれ+ iまたは-iを追加することと同じです。

赤い点は$ 0 bmod（ alpha）$に相当します。これらに加えて、さらに4組のポイントに色を付けます。

$ f $同型は、循環シーケンス$（0,1,2、 cdot cdot cdot、10,11,12,0,1,2、 cdotの$ i $番目の要素の変換によって定義されます。 cdot cdot）$は、図の点の循環シーケンスの$ i $番目の要素であり、次の規則に従います。

1. 最初の行の赤い点から始めます。
2. 右の水平矢印に従ってください。それ以外で
3. 矢印をたどると、シーケンスがラティスから外れると、黒以外のポイントの1つに到達します。そのポイントに移動する代わりに、同じ正方形内の同じ色のポイント（つまり、同等のポイントモジュラス$ alpha $）にジャンプします。そして最後に
4. この黒以外のポイントが赤に変わると（他のすべての色が通過した後に発生します）、シーケンスは上の赤のポイントにジャンプし、サイクルを再開します。

少なくとも$ 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 $と同等です。

Y. S.ヴィラズボアスは、$ a $と$ b $の共原性の必要性を指摘しました。スーパーインクリメントを保持するには、シーケンスの最後に追加される新しい整数$ w $は、現在のすべての整数の合計を超える必要があります（$ w> sum_ {i = 1} ^ k v_i $）。これを実現するには、乗算係数$ b_i $が少なくとも1である必要があるため、各ビットを係数0と1にマッピングできないことがわかりました。係数が0と1の場合、1つの複合ブロックのみスーパーインクリメントを満たします。このため、ビット0と1はそれぞれ乗算係数1と2にマッピングされました。

最後に、それほど簡単な方法ではありません。各デコードステップ中に、方程式$ b_1 v_1 = v_ {n + 1}- sum_ {i = 2} ^ {n}の解として新しい整数$ v_1 $が見つかります。 b_i v_i $、ここですべての$ v_i $と$ b_i $は$ 1で知られています

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