<jupyter_start><jupyter_text>Meet in the Middle Attack- Given prime `p`- then `Zp* = {1, 2, 3, ..., p-1}`- let `g` and `h` be elements in `Zp*` such that- such that `h mod p = g^x mod p` where ` 0 < x < 2^40`- find `x` given `h`, `g`, and `p` Idea- let `B = 2^20` then `B^2 = 2^40` - then `x= xo * B + x1` where `xo` and `x1` are in `{0, 1, ..., B-1}`- Then smallest x is `x = 0 * B + O = 0`- Largest x is `x = B * (B-1) + B - 1 = B^2 - B + B -1 = B^2 - 1 = 2^40 - 1`- Then:```h = g^xh = g^(xo * B + x1) h = g^(xo * B) * g^(x1)h / g^(x1) = g^(xo *B)  ```- Find `xo` and `x1` given `g`, `h`, `B`  Strategy- Build a hash table key: `h / g^(x1)`, with value `x1` for `x1` in `{ 0, 1, 2, .., 2^20 - 1}`- For each value `x0` in `{0, 1, 2, ... 20^20 -1}` check if `(g^B)^(x0) mod P` is in hashtable. If it is then you've found `x0` and `x1`- Return `x = xo * B + x1` Modulo Division``` (x mod p) / ( y mod p)  = ((x mod p) * (y_inverse mod p)) mod p   ``` Definition of inverse``` Definition of modular inverse in Zp y_inverse * y mod P = 1 ```  Inverse of  `x` in `Zp*````Given p is prime,then for every element x in set Zp* = {1, ..., p - 1}the element x is invertible (there exist an x_inverse such that: x_inverse * x mod p = 1The following is true (according to Fermat's 1640)> x^(p - 1) mod  = 1 > x ^ (p - 2) * x mod p = 1> x_inverse = x^(p-2)  ``` Notes- Work is `2^20` multiplications and `2^20` lookups in the worst case- If we brute forced it, we would do `2^40` multiplications- So the work is squareroot of brute force Test Numbers```p = 134078079299425970995740249982058461274793658205923933\    77723561443721764030073546976801874298166903427690031\    858186486050853753882811946569946433649006084171g = 11717829880366207009516117596335367088558084999998952205\    59997945906392949973658374667057217647146031292859482967\    5428279466566527115212748467589894601965568h = 323947510405045044356526437872806578864909752095244\    952783479245297198197614329255807385693795855318053\    2878928001494706097394108577585732452307673444020333``` Library used- https://gmpy2.readthedocs.io/en/latest/mpz.html<jupyter_code>from gmpy2 import mpz
from gmpy2 import t_mod, invert, powmod, add, mul, is_prime
def build_table(h, g, p, B):
    table, z = {}, h
    g_inverse = invert(g, p)
    table[h] = 0
    for x1 in range(1, B):
        z = t_mod(mul(z, g_inverse), p)
        table[z] = x1
    return table
def lookup(table, g, p, B):
    gB, z = powmod(g, B, p), 1
    for x0 in range(B):
        if z in table:
            x1 = table[z]
            return x0, x1
        z = t_mod(mul(z, gB), p)
    return None, None
def find_x(h, g, p, B):
    table = build_table(h, g, p, B)
    x0, x1 = lookup(table, g, p, B)
    # assert x0 != None and x1 != None
    Bx0 = mul(x0, B)
    x = add(Bx0, x1)
    print(x0, x1)
    return x
p_string = '13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171'
g_string = '11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568'
h_string = '3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333'

p = mpz(p_string)
g = mpz(g_string)
h = mpz(h_string)
B = mpz(2) ** mpz(20)

assert is_prime(p)
assert g < p
assert h < p

x = find_x(h, g, p, B)
print(x)

assert h == powmod(g, x, p)<jupyter_output>357984 787046
375374217830
{'fraction_non_alphanumeric': 0.13415660959865283, 'fraction_numerical': 0.2969407802413696, 'mean_word_length': 3.8622100954979537, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 7, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '9031', 'license': 'MIT', 'n_tokens_mistral': 2162, 'n_tokens_neox': 1522, 'n_words': 424, 'path': 'simple-exercises/basic-cryptography/5-meet-in-the-middle-attack.ipynb', 'repo_name': 'mithi/algorithm-playground', 'size': '3563'}