# Investigation Methodology

<details>

<summary><mark style="color:purple;"><strong><code>Task-List</code></strong></mark></summary>

* [ ] <mark style="color:purple;">**Public exponent**</mark>**&#x20;**<mark style="color:orange;">**`e`**</mark>
* [ ] <mark style="color:purple;">**Modulus size (bits)**</mark>
* [ ] <mark style="color:purple;">**Message size (bits)**</mark>
* [ ] <mark style="color:purple;">**Padding implementation**</mark>
* [ ] [<mark style="color:purple;">**Parameter Validation**</mark>](#user-content-fn-1)[^1]
* [ ] [<mark style="color:purple;">**Size Comparison**</mark>](#user-content-fn-2)[^2]
* [ ] [<mark style="color:purple;">**Multiple Sampling**</mark>](#user-content-fn-3)[^3]
* [ ] [<mark style="color:purple;">**Statistical Analysis**</mark>](#user-content-fn-4)[^4]

{% hint style="info" %}
<mark style="color:red;">**`Broadcast Attack Decision Tree`**</mark>

```
├── 🔢 Multiple Moduli + Same Exponent?
│   ├── ✅ YES → Use CRT (Hastad's Attack)
│   └── ❌ NO → Continue analysis
├── 🔗 Known Message Relationships?
│   ├── ✅ Linear → Franklin-Reiter Attack
│   ├── ✅ Polynomial → Coppersmith's Method
│   ├── ✅ Known Differences → Algebraic Solving
│   └── ❌ NO → Continue analysis
├── 🎯 Structured Messages?
│   ├── ✅ YES → Stereotyped Message Attack
│   └── ❌ NO → Continue analysis
├── 📐 Same Modulus?
│   ├── ✅ YES → Direct Algebraic Methods
│   └── ❌ NO → Advanced Lattice Techniques
```
{% endhint %}

</details>

<details>

<summary><mark style="color:purple;"><strong><code>Detection Methods</code></strong></mark></summary>

{% hint style="info" %}
<mark style="color:red;">**`Check for small exponent`**</mark>

{% code overflow="wrap" %}
```python
if e < 65537:
    print("WARNING: Small public exponent detected!"
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check for no padding`**</mark>

{% code overflow="wrap" %}
```python
if message_size == modulus_size:
    print("WARNING: No padding detected!")
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check for multiple encryptions`**</mark>

{% code overflow="wrap" %}
```python
if same_message_encrypted_multiple_times:
    print("WARNING: Broadcast attack possible!")
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check for potential Wiener's vulnerability`**</mark>

{% code overflow="wrap" %}
```python
if e > n**0.5:
    suggestions.append("Wiener's Attack (small d suspected)")
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check for Fermat's vulnerability`**</mark>

{% code overflow="wrap" %}
```python
sqrt_n = int(n**0.5)
if (sqrt_n + 1)**2 - n < sqrt_n:
    suggestions.append("Fermat's Factorization (close primes)"
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check modulus size for general factorization`**</mark>

{% code overflow="wrap" %}
```python
bit_length = n.bit_length()
if bit_length < 1024:
    suggestions.append("General Factorization (weak key size)")
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Check for common modulus`**</mark>

{% code overflow="wrap" %}
```python
if additional_info and 'shared_modulus' in additional_info:
    suggestions.append("Common Modulus Attack")
```
{% endcode %}
{% endhint %}

{% code title="POC" overflow="wrap" %}
```python
def analyze_rsa_parameters(e, n, additional_info=None):
    """
    Analyze RSA parameters to suggest appropriate attacks
    """
    suggestions = []
    
    # Check for small exponent
    if e < 65537:
        suggestions.append("Small Exponent Attack")
    
    # Check for potential Wiener's vulnerability
    if e > n**0.5:
        suggestions.append("Wiener's Attack (small d suspected)")
    
    # Check for Fermat's vulnerability
    sqrt_n = int(n**0.5)
    if (sqrt_n + 1)**2 - n < sqrt_n:
        suggestions.append("Fermat's Factorization (close primes)")
    
    # Check modulus size for general factorization
    bit_length = n.bit_length()
    if bit_length < 1024:
        suggestions.append("General Factorization (weak key size)")
    
    # Check for common modulus
    if additional_info and 'shared_modulus' in additional_info:
        suggestions.append("Common Modulus Attack")
    
    return suggestions
```
{% endcode %}

</details>

<details>

<summary><mark style="color:purple;"><strong><code>Small Parameter Attacks</code></strong></mark></summary>

{% hint style="danger" %}
<mark style="color:red;">**`Elliptic Curve Cryptography`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def small_parameter_ec_attack(curve_order, private_key_bits):
    """
    Attack weak elliptic curves with small parameters
    """
    if curve_order.bit_length() < 256:
        return "Vulnerable to brute force"
    
    if private_key_bits < 128:
        return "Weak private key - brute force possible"
```
{% endcode %}
{% endhint %}

{% hint style="danger" %}
<mark style="color:red;">**`Discrete Logarithm Systems`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def small_subgroup_attack(g, p, q):
    """
    Attack discrete log when subgroup order is small
    """
    if q < 2**80:  # Small subgroup
        return "Vulnerable to Pollard's Rho on small subgroup"
```
{% endcode %}
{% endhint %}

{% hint style="danger" %}
<mark style="color:red;">**`Lattice-Based Cryptography`**</mark>

{% code title="" overflow="wrap" %}
```python
def lattice_small_secret_attack(lattice_basis, error_bound):
    """
    Attack lattice systems with small secrets/errors
    Similar principle to small exponent attacks
    """
    if error_bound < lattice_dimension_threshold:
        return "Vulnerable to lattice reduction attacks"
```
{% endcode %}
{% endhint %}

</details>

<details>

<summary><mark style="color:purple;"><strong><code>Broadcast Attacks</code></strong></mark></summary>

{% hint style="info" %}
<mark style="color:red;">**`Linear Relationship Attack`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def linear_broadcast_attack(c1, c2, n, e, a, b, c, d):
    """
    Attack when messages have linear relationship:
    m₁ = a*m + b
    m₂ = c*m + d
    
    Where m is the target message
    """
    # Given:
    # c₁ ≡ (a*m + b)^e (mod n)
    # c₂ ≡ (c*m + d)^e (mod n)
    
    # For small e (like e=3), we can expand and solve
    if e == 3:
        # Expand (a*m + b)³ and (c*m + d)³
        # Create system of equations in powers of m
        # Solve algebraically
        
        # This is complex algebra - conceptual example
        print("Solving linear system for e=3 case")
        
        # Extract coefficients and solve polynomial system
        # Returns the original message m
        pass
    
    return None

# Example usage:
# If we know m₁ = 2m + 5 and m₂ = 3m + 7
# We can solve even without CRT
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Known Difference Attack`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def known_difference_attack(c1, c2, n, e, diff):
    """
    Attack when messages differ by a known amount:
    m₂ = m₁ + diff
    """
    # Given:
    # c₁ ≡ m₁^e (mod n)  
    # c₂ ≡ (m₁ + diff)^e (mod n)
    
    # For small e, expand (m₁ + diff)^e using binomial theorem
    # Create equation involving only m₁
    
    if e == 3:
        # c₂ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² + diff³ (mod n)
        # Rearrange: c₂ - diff³ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² (mod n)
        # Factor: c₂ - diff³ ≡ m₁(m₁² + 3*m₁*diff + 3*diff²) (mod n)
        
        # This creates a relationship we can exploit
        modified_c2 = (c2 - pow(diff, 3, n)) % n
        
        # Now we have a relationship between c1 and modified_c2
        # Can solve using various techniques
        pass
    
    return None
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Franklin-Reiter Related Message Attack`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def franklin_reiter_attack(c1, c2, n, e, a, b):
    """
    Franklin-Reiter attack for related messages
    m₁ and m₂ where m₂ ≡ a*m₁ + b (mod n)
    
    This DOES NOT use CRT!
    Uses resultants and polynomial GCD
    """
    from sympy import symbols, Poly, resultant
    
    if e < 2:
        return None
    
    x = symbols('x')
    
    # Define polynomials
    # f₁(x) = x^e - c₁
    # f₂(x) = (a*x + b)^e - c₂
    
    f1 = Poly(x**e - c1, x)
    f2 = Poly((a*x + b)**e - c2, x)
    
    # Compute resultant to eliminate x
    # If m₁ is a common root, resultant will be 0
    # This gives us information about m₁
    
    res = resultant(f1, f2, x)
    
    # The resultant gives us a way to find m₁
    # without using CRT - pure polynomial algebra
    
    # Solve for roots of the resultant
    # (Implementation details depend on specific case)
    
    print("Franklin-Reiter uses polynomial resultants, not CRT")
    return None
```
{% endcode %}
{% endhint %}

{% hint style="info" %}
<mark style="color:red;">**`Stereotyped Message Attack`**</mark>

{% code title="POC" overflow="wrap" %}
```python
def stereotyped_message_attack(ciphertexts, n, e, known_parts, unknown_part_size):
    """
    Attack messages with known structure:
    "Dear Alice, [SECRET], Best regards, Bob"
    
    Uses Coppersmith's method, not CRT
    """
    # Messages have form: known_prefix + unknown + known_suffix
    # Use Coppersmith's technique to find small unknown parts
    
    # This works even with a single ciphertext!
    # No need for multiple encryptions or CRT
    
    # Set up polynomial with unknown part as variable
    # Use lattice reduction to find small roots
    
    print("Stereotyped messages use Coppersmith's method")
    print("No CRT required - works on single ciphertext")
    
    return None
```
{% endcode %}
{% endhint %}

</details>

[^1]: <mark style="color:purple;">Check for weak values</mark>

[^2]: <mark style="color:purple;">Message vs modulus relationships</mark>

[^3]: <mark style="color:purple;">Collect multiple encryptions</mark>

[^4]: <mark style="color:purple;">Pattern recognition</mark>
