jvdsn/crypto-attacksImplementaciones en Python de ataques y utilidades criptográficas.
Implementaciones en Python de ataques y utilidades criptográficas.
Puedes comprobar la versión de Python de SageMath con el siguiente comando:``` $ sage -python --version Python 3.9.0
Si la versión de Python de SageMath es anterior a la 3.9.0, algunas funcionalidades de algunos scripts podrían no funcionar.
## Uso
Las pruebas unitarias se encuentran en el directorio `test` y se pueden ejecutar con el módulo `unittest` o con `pytest`. Esto no debería llevar mucho tiempo, quizás unos minutos dependiendo de tu máquina.
Para ejecutar un ataque específico, debes añadir el código al archivo adecuado antes de ejecutarlo.
### Ejemplo
Por ejemplo, quieres atacar RSA usando el ataque Boneh-Durfee, con los siguientes parámetros (tomados de [test_rsa.py](https://github.com/jvdsn/crypto-attacks/blob/HEAD/test/test_rsa.py)):```python
N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511
Añade el siguiente código al final del archivo 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 = }")
Entonces puedes simplemente ejecutar el archivo usando Sage. No importa desde dónde lo ejecutes, la ruta de Python se establece automágicamente (también puedes llamar a los ataques desde otros archivos de Python, pero entonces tendrás que arreglar la ruta de Python tú mismo):```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
Los parámetros m y t que se muestran en el registro de salida merecen especial atención. Estos parámetros se utilizan en muchos algoritmos basados en retículos (raíces pequeñas) para ajustar el tamaño del retículo. Conceptualmente, m (a veces llamado k) y t representan el número de "desplazamientos" utilizados en el retículo, que es aproximadamente igual o proporcional al número de filas. Por lo tanto, aumentar m y t aumentará el tamaño del retículo, lo que también aumenta el tiempo necesario para realizar la reducción del retículo (actualmente usando LLL). Por otro lado, si m y t son demasiado bajos, es posible que la reducción del retículo no produzca los vectores adecuados, desperdiciando así el tiempo invertido en la reducción. Por lo tanto, hay un equilibrio.
En la versión actual del proyecto, m siempre debe ser proporcionado por el usuario (el valor predeterminado es 1). t puede, en algunos casos, calcularse según el método específico de raíces pequeñas utilizado por el ataque. Sin embargo, el usuario aún puede ajustarlo. En general, hay dos formas de usar este tipo de parámetros:
m = 1 hasta que se encuentre una respuesta (ejemplo a continuación). Este es un enfoque simple, pero corre el riesgo de perder tiempo en cálculos inútiles con retículos demasiado pequeños.```
m = 1
while True:
res = attack(..., m=m)
if res is not None:
# The attack succeeded!
break
m += 1* Implementa una versión de depuración del ataque que intentas usar (con resultados conocidos) y determina el valor de `m` que produce buenos vectores de retículo. Luego llama directamente al método de ataque con el valor de `m` correcto.
## Ataques implementados
### Divisor Común Aproximado
* [x] [Ataque polinómico multivariado](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/acd/mp.py) [^acd_mp]
* [x] [Ataque basado en ortogonalidad](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/acd/ol.py) [^acd_ol]
* [x] [Ataque de aproximación diofántica simultánea](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/acd/sda.py) [^acd_sda]
### CBC
* [x] [Ataque de volteo de bits](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc/bit_flipping.py)
* [x] [Ataque de recuperación del IV](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc/iv_recovery.py)
* [x] [Ataque de oráculo de relleno](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc/padding_oracle.py)
### CBC + CBC-MAC
* [x] [Ataque de reutilización de clave (encrypt-and-MAC)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc_and_cbc_mac/eam_key_reuse.py)
* [x] [Ataque de reutilización de clave (encrypt-then-MAC)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc_and_cbc_mac/etm_key_reuse.py)
* [x] [Ataque de reutilización de clave (MAC-then-encrypt)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc_and_cbc_mac/mte_key_reuse.py)
### CBC-MAC
* [x] [Ataque de extensión de longitud](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/cbc_mac/length_extension.py)
### CTR
* [x] [Ataque de volteo de bits](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ctr/bit_flipping.py)
* [x] [Ataque CRIME](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ctr/crime.py)
* [x] [Ataque de oráculo separador](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ctr/separator_oracle.py)
### ECB
* [x] [Ataque de recuperación de texto plano](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecb/plaintext_recovery.py)
* [x] [Ataque de recuperación de texto plano (variante más difícil)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecb/plaintext_recovery_harder.py)
* [x] [Ataque de recuperación de texto plano (variante de máxima dificultad)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecb/plaintext_recovery_hardest.py)
### Criptografía de curvas elípticas
* [x] [Ataque de reutilización de nonce en ECDSA](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/ecdsa_nonce_reuse.py)
* [x] [Ataque de Frey-Ruck](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/frey_ruck_attack.py) [^ecc_frey_ruck_attack]
* [x] [Ataque MOV](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/mov_attack.py) [^ecc_mov_attack]
* [x] [Recuperación de parámetros](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/parameter_recovery.py)
* [x] [Ataque de curva singular](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/singular_curve.py)
* [x] [Ataque de Smart (con curvas sobre cuerpos de extensión)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ecc/smart_attack.py) [^ecc_smart_attack1] [^ecc_smart_attack2]
### Cifrado ElGamal
* [x] [Ataque de reutilización de nonce](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/elgamal_encryption/nonce_reuse.py)
* [x] [Ataque de generador inseguro](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/elgamal_encryption/unsafe_generator.py)
### Firma ElgGamal
* [ ] Ataque de Bleichenbacher
* [ ] Ataque de Khadir
* [x] [Ataque de reutilización de nonce](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/elgamal_signature/nonce_reuse.py)
### Factorización
* [x] [Factorización por conversión de base](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/base_conversion.py)
* [x] [Ataque de ramificación y poda](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/branch_and_prune.py) [^factorization_branch_and_prune]
* [x] [Factorización por multiplicación compleja (curva elíptica)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/complex_multiplication.py) [^factorization_complex_multiplication]
* [x] [Factorización de Coppersmith](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/coppersmith.py)
* [x] [Factorización de Fermat](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/fermat.py)
* [x] [Ataque de Ghafar-Ariffin-Asbullah](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/gaa.py) [^factorization_gaa]
* [x] [Factorización implícita](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/implicit.py) [^factorization_implicit]
* [x] [Factorización con phi conocido](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/known_phi.py) [^factorization_known_phi]
* [x] [ROCA](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/roca.py) [^factorization_roca]
* [x] [Algoritmo de Shor (clásico)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/shor.py) [^factorization_shor]
* [x] [Factorización de primos gemelos](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/twin_primes.py)
* [x] [Factorización de módulos no balanceados](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/factorization/unbalanced.py) [^factorization_unbalanced]
### GCM
* [x] [Ataque prohibido](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/gcm/forbidden_attack.py) [^gcm_forbidden_attack]
### Problema del Número Oculto
Con aplicaciones a la exposición parcial de nonces en (EC)DSA.
* [x] [Problema del número oculto extendido](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/hnp/extended_hnp.py) [^hnp_extended_hnp]
* [ ] Ataque de análisis de Fourier
* [x] [Ataque basado en retículos](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/hnp/lattice_attack.py)
### IGE
* [x] [Ataque de oráculo de relleno](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/ige/padding_oracle.py)
### Criptosistemas de mochila
* [x] [Ataque de baja densidad](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/knapsack/low_density.py) [^knapsack_low_density]
### Generadores Lineales Congruenciales
* [x] [Recuperación de parámetros de LCG](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/lcg/parameter_recovery.py)
* [x] [Recuperación de parámetros de LCG truncado](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/lcg/truncated_parameter_recovery.py) [^lcg_truncated_parameter_recovery]
* [x] [Recuperación de estado de LCG truncado](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/lcg/truncated_state_recovery.py) [^lcg_truncated_state_recovery]
### Aprendizaje con Errores
* [x] [Ataque de Arora-Ge](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/lwe/arora_ge.py) [^lwe_arora_ge]
* [ ] Ataque de Blum-Kalai-Wasserman
* [ ] Ataque de reducción de retículo
### Mersenne Twister
* [x] [Recuperación de estado](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/mersenne_twister/state_recovery.py)
### One-time Pad
* [x] [Reutilización de clave](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/otp/key_reuse.py)
### Pseudoprimos
* [x] [Generación de pseudoprimos de Miller-Rabin](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/pseudoprimes/miller_rabin.py) [^pseudoprimes_miller_rabin]
### RC4
* [x] [Ataque de Fluhrer-Mantin-Shamir](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rc4/fms.py)
### RSA
* [x] [Ataque de Bleichenbacher](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/bleichenbacher.py) [^rsa_bleichenbacher]
* [x] [Ataque de falsificación de firma de Bleichenbacher](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/bleichenbacher_signature_forgery.py)
* [x] [Ataque de Boneh-Durfee](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/boneh_durfee.py) [^rsa_boneh_durfee]
* [x] [Ataque de Cherkaoui-Semmouni](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/cherkaoui_semmouni.py) [^rsa_cherkaoui_semmouni]
* [x] [Ataque de módulo común](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/common_modulus.py)
* [x] [Ataque de fallo por CRT](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/crt_fault_attack.py)
* [x] [Ataque de fallo en d](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/d_fault_attack.py)
* [x] [Ataque de Desmedt-Odlyzko (falsificación selectiva)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/desmedt_odlyzko.py) [^rsa_desmedt_odlyzko]
* [x] [Ataque de Wiener extendido](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/extended_wiener_attack.py) [^rsa_extended_wiener_attack]
* [x] [Ataque de difusión de Hastad](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/hastad_attack.py)
* [x] [Ataque con exponentes CRT conocidos](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/known_crt_exponents.py) [^rsa_known_crt_exponents]
* [x] [Ataque con exponentes CRT parcialmente conocidos](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/known_crt_exponents.py) [^rsa_partial_known_crt_exponents]
* [x] [Ataque con exponente privado conocido](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/known_d.py)
* [x] [Ataque de exponente público pequeño](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/low_exponent.py)
* [x] [Ataque de oráculo LSB (oráculo de paridad)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/lsb_oracle.py)
* [x] [Ataque de Manger](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/manger.py) [^rsa_manger]
* [x] [Ataque CRT-RSA de Nitaj](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/nitaj_crt_rsa.py) [^rsa_nitaj_crt_rsa]
* [x] [Ataque de exponente público no coprimo](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/non_coprime_exponent.py) [^rsa_non_coprime_exponent]
* [x] [Exposición parcial de clave](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/partial_key_exposure.py) [^rsa_partial_key_exposure1] [^rsa_partial_key_exposure2] [^rsa_partial_key_exposure3]
* [x] [Ataque de mensajes relacionados](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/related_message.py)
* [x] [Ataque de mensaje estereotipado](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/stereotyped_message.py)
* [x] [Ataque de Wiener](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/wiener_attack.py)
* [x] [Ataque de Wiener para RSA de primo común](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/wiener_attack_common_prime.py) [^rsa_wiener_attack_common_prime]
* [x] [Ataque de Wiener (variante heurística de retículos)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/rsa/wiener_attack_lattice.py) [^rsa_wiener_attack_lattice] [^rsa_wiener_attack_lattice_extended] [^small_roots_aono]
### Secreto compartido de Shamir
* [x] [Coeficientes deterministas](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/shamir_secret_sharing/deterministic_coefficients.py)
* [x] [Falsificación de shares](https://github.com/jvdsn/crypto-attacks/blob/HEAD/attacks/shamir_secret_sharing/share_forgery.py)
## Otras implementaciones interesantes
* [x] [Método de extracción de raíces de Adleman-Manders-Miller](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/__init__.py) [^adleman_manders_miller]
* [x] [CRT rápido mediante divide y vencerás](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/crt.py)
* [x] [Inversos modulares rápidos](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/__init__.py)
* [x] [Elevación lineal de Hensel](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/hensel.py)
* [ ] Elevación cuadrática de Hensel
* [x] [Algoritmo del plano más cercano de Babai](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/lattice.py)
* [x] [Logaritmo discreto matricial](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/matrices.py)
* [x] [Logaritmo discreto matricial (ecuación)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/matrices.py)
* [x] [PartialInteger](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/partial_integer.py)
* [x] [MCD polinomial rápido mediante half GCD](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/polynomial.py)
### Generación de curvas elípticas
* [x] [Multiplicación compleja](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
* [x] [Curvas anómalas](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
* [x] [Curvas MNT](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
* [x] [Orden prescrito](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
* [x] [Traza prescrita](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
* [x] [Curvas supersingulares](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/ecc.py)
### Raíces pequeñas
* [x] [Raíces polinomiales mediante bases de Gröbner](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/__init__.py)
* [x] [Raíces polinomiales mediante resultantes](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/__init__.py)
* [x] [Raíces polinomiales mediante la variedad de Sage (descomposición triangular)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/__init__.py)
* [x] [Método de Aono (retículo de suma de Minkowski)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/aono.py) [^small_roots_aono]
* [x] [Método de Blomer-May](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/blomer_may.py) [^small_roots_blomer_may]
* [x] [Método de Boneh-Durfee](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/boneh_durfee.py) [^rsa_boneh_durfee]
* [x] [Método de Coron](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/coron.py) [^small_roots_coron]
* [x] [Método de Coron (directo)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/coron_direct.py) [^small_roots_coron_direct]
* [x] [Métodos de Ernst et al.](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/ernst.py) [^rsa_partial_key_exposure2]
* [x] [Método de Herrmann-May (linealización desenredada)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/herrmann_may.py) [^small_roots_herrmann_may]
* [x] [Método de Herrmann-May (multivariado modular)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/herrmann_may_multivariate.py) [^small_roots_herrmann_may_multivariate]
* [x] [Método de Howgrave-Graham](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/howgrave_graham.py) [^small_roots_howgrave_graham]
* [x] [Método de Jochemsz-May (raíces modulares)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/jochemsz_may_modular.py) [^small_roots_jochemsz_may_modular]
* [x] [Método de Jochemsz-May (raíces enteras)](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/jochemsz_may_integer.py) [^small_roots_jochemsz_may_integer]
* [x] [Método de Nitaj-Fouotsa](https://github.com/jvdsn/crypto-attacks/blob/HEAD/shared/small_roots/nitaj_fouotsa.py) [^small_roots_nitaj_fouotsa]
[^acd_mp]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 5)
[^acd_ol]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 4)
[^acd_sda]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 3)
[^ecc_frey_ruck_attack]: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 3)
[^ecc_mov_attack]: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 2)
[^ecc_smart_attack1]: Smart N. P., "The Discrete Logarithm Problem on Elliptic Curves of Trace One"
[^ecc_smart_attack2]: Hofman S. J., "The Discrete Logarithm Problem on Anomalous Elliptic Curves"
[^factorization_branch_and_prune]: Heninger N., Shacham H., "Reconstructing RSA Private Keys from Random Key Bits"
[^factorization_complex_multiplication]: Sedlacek V. et al., "I want to break square-free: The 4p - 1 factorization method and its RSA backdoor viability"
[^factorization_gaa]: Ghafar AHA. et al., "A New LSB Attack on Special-Structured RSA Primes"
[^factorization_implicit]: Nitaj A., Ariffin MRK., "Implicit factorization of unbalanced RSA moduli"
[^factorization_known_phi]: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
[^factorization_roca]: Nemec M. et al., "The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli"
[^factorization_shor]: M. Johnston A., "Shor’s Algorithm and Factoring: Don’t Throw Away the Odd Orders"
[^factorization_unbalanced]: Brier E. et al., "Factoring Unbalanced Moduli with Known Bits" (Section 4)
[^gcm_forbidden_attack]: Joux A., "Authentication Failures in NIST version of GCM"
[^hnp_extended_hnp]: Hlavac M., Rosa T., "Extended Hidden Number Problem and Its Cryptanalytic Applications" (Section 4)
[^knapsack_low_density]: Coster M. J. et al., "Improved low-density subset sum algorithms"
[^lcg_truncated_parameter_recovery]: Contini S., Shparlinski I. E., "On Stern's Attack Against Secret Truncated Linear Congruential Generators"
[^lcg_truncated_state_recovery]: Frieze, A. et al., "Reconstructing Truncated Integer Variables Satisfying Linear Congruences"
[^lwe_arora_ge]: ["The Learning with Errors Problem: Algorithms"](https://people.csail.mit.edu/vinodv/6876-Fall2018/lecture2.pdf) (Section 1)
[^pseudoprimes_miller_rabin]: R. Albrecht M. et al., "Prime and Prejudice: Primality Testing Under Adversarial Conditions"
[^rsa_bleichenbacher]: Bleichenbacher D., "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1"
[^rsa_boneh_durfee]: Boneh D., Durfee G., "Cryptanalysis of RSA with Private Key d Less than N^0.292"
[^rsa_cherkaoui_semmouni]: Cherkaoui-Semmouni M. et al., "Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits"
[^rsa_desmedt_odlyzko]: Coron J. et al., "Practical Cryptanalysis of ISO 9796-2 and EMV Signatures (Section 3)"
[^rsa_extended_wiener_attack]: Dujella A., "Continued fractions and RSA with small secret exponent"
[^rsa_known_crt_exponents]: Campagna M., Sethi A., "Key Recovery Method for CRT Implementation of RSA"
[^rsa_partial_known_crt_exponents]: May A., Nowakowski J., Sarkar S., "Approximate Divisor Multiples - Factoring with Only a Third of the Secret CRT-Exponents"
[^rsa_manger]: Manger J., "A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0"
[^rsa_nitaj_crt_rsa]: Nitaj A., "A new attack on RSA and CRT-RSA"
[^rsa_non_coprime_exponent]: Shumow D., "Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts"
[^rsa_partial_key_exposure1]: Boneh D., Durfee G., Frankel Y., "An Attack on RSA Given a Small Fraction of the Private Key Bits"
[^rsa_partial_key_exposure2]: Ernst M. et al., "Partial Key Exposure Attacks on RSA Up to Full Size Exponents"
[^rsa_partial_key_exposure3]: Blomer J., May A., "New Partial Key Exposure Attacks on RSA"
[^rsa_wiener_attack_common_prime]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 5)
[^rsa_wiener_attack_lattice]: Nguyen P. Q., "Public-Key Cryptanalysis"
[^rsa_wiener_attack_lattice_extended]: Howgrave-Graham N., Seifert J., "Extending Wiener’s Attack in the Presence of Many Decrypting Exponents"
[^adleman_manders_miller]: Cao Z. et al., "Adleman-Manders-Miller Root Extraction Method Revisited" (Section 5)
[^small_roots_aono]: Aono Y., "Minkowski sum based lattice construction for multivariate simultaneous Coppersmith's technique and applications to RSA" (Section 4)
[^small_roots_blomer_may]: Blomer J., May A., "New Partial Key Exposure Attacks on RSA" (Section 6)
[^small_roots_coron]: Coron J., "Finding Small Roots of Bivariate Integer Polynomial Equations Revisited"
[^small_roots_coron_direct]: Coron J., "Finding Small Roots of Bivariate Integer Polynomial Equations: a Direct Approach"
[^small_roots_herrmann_may]: Herrmann M., May A., "Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA"
[^small_roots_herrmann_may_multivariate]: Herrmann M., May A., "Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits" (Section 3 and 4)
[^small_roots_howgrave_graham]: May A., "New RSA Vulnerabilities Using Lattice Reduction Methods" (Section 3.2)
[^small_roots_jochemsz_may_modular]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 2.1)
[^small_roots_jochemsz_may_integer]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 2.2)
[^small_roots_nitaj_fouotsa]: Nitaj A., Fouotsa E., "A New Attack on RSA and Demytko's Elliptic Curve Cryptosystem"