jvdsn/crypto-attacks暗号攻撃とユーティリティのPython実装。
暗号攻撃とユーティリティのPython実装です。
以下のコマンドで SageMath の Python バージョンを確認できます：``` $ sage -python --version Python 3.9.0
SageMath の Python バージョンが 3.9.0 より古い場合、一部のスクリプトの一部の機能が動作しないことがあります。
## 使用方法
単体テストは `test` ディレクトリにあり、`unittest` モジュールまたは `pytest` を使用して実行できます。それほど時間はかからず、マシンによっては数分程度です。
特定の攻撃を実行するには、実行する前にコードを適切なファイルに追加する必要があります。
### 例
たとえば、次のパラメータ（[test_rsa.py](https://github.com/jvdsn/crypto-attacks/blob/master/test/test_rsa.py) から取得）を使用して、Boneh-Durfee 攻撃で RSA を攻撃するとします。```python
N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511
以下のコードを boneh_durfee.py ファイルの末尾に追加します。```python import logging
logging.basicConfig(level=logging.DEBUG)
N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249 e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511 p_bits = 512 delta = 0.26
p, q = attack(N, e, p_bits, delta=delta, m=3) assert p * q == N print(f"Found {p = } and {q = }")
その後、Sageを使用してファイルを実行するだけです。どこから実行しても問題ありません。Pythonパスは自動的に設定されます（他のPythonファイルから攻撃を呼び出すこともできますが、その場合はPythonパスを自分で修正する必要があります）：```commandline
[crypto-attacks]$ sage -python attacks/rsa/boneh_durfee.py
INFO:root:Trying m = 3, t = 1...
DEBUG:root:Generating shifts...
DEBUG:root:Creating a lattice with 11 shifts (order = 'invlex', sort_shifts_reverse = False, sort_monomials_reverse = False)...
DEBUG:root:Reducing a 11 x 11 lattice...
DEBUG:root:Reconstructing polynomials (divide_original = True, modulus_bound = False, divide_gcd = True)...
DEBUG:root:Polynomial at row 8 is constant, ignoring...
DEBUG:root:Reconstructed polynomial has gcd 1312232632720549890113031660369306919929075823824696839212183146130434668203517349691252841557097914064120078389640402109017308806168467714230057403815071456395553717020189622129706447677967264344568789118172311850383406340547579993263937406518074980025897726255316031512238322022839331135299265704052474541497687419350763703993630899191179705015113329644753599872380152055902238937889027950089072598069861391599563222633064848996619752054685734260976071760984100109990150069201501748622288840900421607423175114026653242500476408861976142751384898489130281755466581359057847077651502734556259387442296763474369957121 with polynomial at 8, dividing...
DEBUG:root:Reconstructed 10 polynomials
DEBUG:root:Computing pairwise gcds to find trivial roots...
DEBUG:root:Using Groebner basis method to find roots...
DEBUG:root:Sequence length: 10, Groebner basis length: 1
DEBUG:root:Sequence length: 9, Groebner basis length: 1
DEBUG:root:Sequence length: 8, Groebner basis length: 1
DEBUG:root:Sequence length: 7, Groebner basis length: 2
DEBUG:root:Found Groebner basis with length 2, trying to find roots...
Found p = 7866790440964395011005623971351568677139336343167390105188826934257986271072664643571727955882500173182140478082778193338086048035817634545367411924942763 and q = 11227048386374621771175649743442169526805922745751610531569607663416378302561807690656370394330458335919244239976798600743588701676542461805061598571009923
出力ログに示されているパラメータ m と t は特に注意が必要です。これらのパラメータは、多くの格子ベース（small roots）アルゴリズムで格子サイズを調整するために使用されます。概念的には、m（k と呼ばれることもあります）と t は格子で使用される「シフト」の数を表し、これは行数にほぼ等しいか、比例します。したがって、m と t を増やすと格子のサイズが大きくなり、格子簡約（現在は LLL を使用）に必要な時間も増加します。一方、m と t が低すぎると、格子簡約が適切なベクトルを生成しない可能性があり、簡約に費やした時間を無駄にしてしまいます。したがって、これはトレードオフです。
プロジェクトの現在のバージョンでは、m は常にユーザーが指定する必要があります（デフォルト値は 1 に設定されています）。t は、攻撃で使用される特定の small roots メソッドに基づいて計算できる場合があります。ただし、ユーザーが調整することも可能です。一般に、この種のパラメータの使用方法には2つの方法があります：
m = 1 から始まるループを実装します（下記の例を参照）。これはシンプルなアプローチですが、小さすぎる格子での無駄な計算に時間を浪費するリスクがあります。```
m = 1
while True:
res = attack(..., m=m)
if res is not None:
# The attack succeeded!
break
m += 1* 使用しようとしている攻撃のデバッグ版（結果が既知のもの）を実装し、良好な格子ベクトルが得られる`m`の値を決定します。その後、正しい`m`値で攻撃メソッドを直接呼び出します。
## 実装済みの攻撃
### 近似共通約数
* [x] [多変数多項式攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/mp.py) [^acd_mp]
* [x] [直交格子に基づく攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/ol.py) [^acd_ol]
* [x] [同時ディオファントス近似攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/sda.py) [^acd_sda]
### CBC
* [x] [ビットフリッピング攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/bit_flipping.py)
* [x] [IV復元攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/iv_recovery.py)
* [x] [パディングオラクル攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/padding_oracle.py)
### CBC + CBC-MAC
* [x] [鍵再利用攻撃（encrypt-and-MAC）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/eam_key_reuse.py)
* [x] [鍵再利用攻撃（encrypt-then-MAC）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/etm_key_reuse.py)
* [x] [鍵再利用攻撃（MAC-then-encrypt）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/mte_key_reuse.py)
### CBC-MAC
* [x] [長さ拡張攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_mac/length_extension.py)
### CTR
* [x] [ビットフリッピング攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ctr/bit_flipping.py)
* [x] [CRIME攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ctr/crime.py)
* [x] [セパレータオラクル攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ctr/separator_oracle.py)
### ECB
* [x] [平文復元攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecb/plaintext_recovery.py)
* [x] [平文復元攻撃（より難しい変種）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecb/plaintext_recovery_harder.py)
* [x] [平文復元攻撃（最も難しい変種）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecb/plaintext_recovery_hardest.py)
### 楕円曲線暗号
* [x] [ECDSAナンス再利用攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/ecdsa_nonce_reuse.py)
* [x] [Frey-Ruck攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/frey_ruck_attack.py) [^ecc_frey_ruck_attack]
* [x] [MOV攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/mov_attack.py) [^ecc_mov_attack]
* [x] [パラメータ復元](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/parameter_recovery.py)
* [x] [特異曲線攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/singular_curve.py)
* [x] [Smart攻撃（拡大体上の曲線）](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py) [^ecc_smart_attack1] [^ecc_smart_attack2]
### ElGamal暗号
* [x] [ナンス再利用攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/elgamal_encryption/nonce_reuse.py)
* [x] [安全でない生成元攻撃](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/elgamal_encryption/unsafe_generator.py)