<jupyter_start><jupyter_text>Logaritmo Discreto ![Figure 1](./img/dlog.png)El logaritmo discreto, es la base de la seguridad de los metodos anteriores. Consiste en encontrar las llaves privadas de Bob y Alicia, a y b. Imaginemos que existe un tercer sujeto llamado Pancho. Pancho intercepta la comunicación entre Alicia y Bob y lo único que ve en el camino son A y B, es decir $g^a$ y $g^b$. Si Pancho pudiera saber a o b, entonces solo tomo ya sea A o B y lo eleva a la llave que encontro. Para encontrarlo necesita del logaritmo discreto.El logaritmo discreto se define como:$\ g^a \equiv \ A \ mod\ p$Donde A, g y p son conocidos y buscamos a, es decir:$ a \equiv \ log_g(A) \ mod\ p$Hay varias formas de encontrar el logaritmo discreto. Tomemos del ejemplo anterior en el encriptado de <NAME>, los mismos números.  Digamos que Pancho consigue A = 656334248, sabemos que g = 13 y p = 3367900313<jupyter_code>A = 656334248
g = 13
p = 3367900313<jupyter_output><empty_output><jupyter_text>Algoritmo Pohlig-Helman<jupyter_code>from sympy.ntheory import factorint
factorint(3367900312)<jupyter_output><empty_output><jupyter_text>Tomamos primero el factor $2^3$<jupyter_code>int1=int((3367900313-1)/2)

alpha1=pow(13,int1,p)
print("Alpha1 =",alpha1)
beta1=pow(A,int1,p)
print("Beta1 =",beta1)<jupyter_output>Alpha1 = 3367900312
Beta1 = 3367900312<jupyter_text>Por lo tanto $x_0=1$, y ahora incrementamos $2^2$<jupyter_code>s=modinv(g,p)
A1=A*s%p
print(A1)
int2=int((3367900312)/4)
beta2=pow(A1,int2,p)
print("Beta2 =",beta2)
prueba=pow(alpha1,5,p)
print("prueba =",prueba)<jupyter_output>3159318308
Beta2 = 3367900312
prueba = 3367900312<jupyter_text>Por lo tanto $x_1=1$<jupyter_code>s2=modinv(g,p)
A2=A1*s2*s2%p
print(A2)
int3=int((3367900312)/8)
beta3=pow(A2,int3,p)
print("Beta3 =",beta3)<jupyter_output>1732536954
Beta3 = 3367900312<jupyter_text>Por lo tanto $x_2=1$, y la primera ecuación es: $x_1 = x_0+2*x_1+4*x_2 \equiv 7\ mod \ 8$ Tomamos segundo el factor $7$<jupyter_code>int11=int((3367900313-1)/7)

alpha11=pow(13,int11,p)
print("Alpha1 =",alpha11)
beta11=pow(A,int11,p)
print("Beta1 =",beta11)<jupyter_output>Alpha1 = 2974477553
Beta1 = 1<jupyter_text>Por lo tanto  $x_1=0$ y la segunda ecuación es: $x_2 \equiv 0\ mod \ 7$ Tomamos tercero el factor $109$<jupyter_code>int111=int((3367900313-1)/109)

alpha111=pow(13,int111,p)
print("Alpha1 =",alpha111)
beta111=pow(A,int111,p)
print("Beta1 =",beta111)
prueba=pow(alpha111,3,p)
print (prueba)<jupyter_output>2497218448<jupyter_text>Por lo tanto  $x_1=3$ y la segunda ecuación es: $x_3 \equiv 3\ mod \ 109$Tomamos por último el factor $551753$<jupyter_code>int1111=int((3367900313-1)/551753)

alpha1111=pow(13,int1111,p)
print("Alpha1 =",alpha1111)
beta1111=pow(A,int1111,p)
print("Beta1 =",beta1111)
i=0
result=0
while result != beta1111:
    result=pow(alpha1111,i,p)
    i=i+1
print(i-1)
print (result)
print(pow(alpha1111,46552,p))<jupyter_output>2491247764<jupyter_text>Por lo tanto  $x_1=46552$ y la segunda ecuación es: $x_4 \equiv 46552\ mod \ 551753$<jupyter_code>def extended_gcd2(a, b):
    """Return (r, s, d) where a*r + b*s = d and d = gcd(a,b)"""
    x,y = 0, 1
    lastx, lasty = 1, 0

    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y

    return (lastx, lasty, a)
def chinese_remainder_theorem(items):
  """Solve the chinese remainder theorem
  Given a list of items (a_i, n_i) solve for x such that x = a_i (mod n_i)
  such that 0 <= x < product(n_i)
  Assumes that n_i are pairwise co-prime.
  """

  # Determine N, the product of all n_i
  N = 1
  for a, n in items:
    N *= n

  # Find the solution (mod N)
  result = 0
  for a, n in items:
    m = N//n
    r, s, d = extended_gcd2(n, m)
    if d != 1:
      raise "Input not pairwise co-prime"
    result += a*s*m

  # Make sure we return the canonical solution.
  return result % N
result_final=chinese_remainder_theorem([(7,8),(0,7),(3,109),(46552,551753)])
print("a =",result_final)<jupyter_output>a = 12736871<jupyter_text>Fuerza Bruta  Con este algoritmo vamos a intentar descifrar un mensaje encriptado con ROTn. El modo más natural de proceder es intentar con las 25 llaves disponibles. I. Insertamos el mensaje a descifrar.<jupyter_code>mensaje = 'FSCJCQ Y RGLEY.'
alfabeto = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'<jupyter_output><empty_output><jupyter_text>II. Probaremos cada rotación para ver si tiene sentido el mensaje.<jupyter_code>for rot in range(len(alfabeto)):

    resultado = ''

    for letra in mensaje:
        if letra in alfabeto:
            num = alfabeto.find(letra) 
            num = num - rot
        
            if num < 0:
                num = num + len(alfabeto)
       
            resultado = resultado + alfabeto[num]
        
        else:
            
            resultado = resultado + letra

    print('Rot #%s: %s' % (rot, resultado))<jupyter_output>Rot #0: FSCJCQ Y RGLEY.
Rot #1: ERBIBP X QFKDX.
Rot #2: DQAHAO W PEJCW.
Rot #3: CPZGZN V ODIBV.
Rot #4: BOYFYM U NCHAU.
Rot #5: ANXEXL T MBGZT.
Rot #6: ZMWDWK S LAFYS.
Rot #7: YLVCVJ R KZEXR.
Rot #8: XKUBUI Q JYDWQ.
Rot #9: WJTATH P IXCVP.
Rot #10: VISZSG O HWBUO.
Rot #11: UHRYRF N GVATN.
Rot #12: TGQXQE M FUZSM.
Rot #13: SFPWPD L ETYRL.
Rot #14: REOVOC K DSXQK.
Rot #15: QDNUNB J CRWPJ.
Rot #16: PCMTMA I BQVOI.
Rot #17: OBLSLZ H APUNH.
Rot #18: NAKRKY G ZOTMG.
Rot #19: MZJQJX F YNSLF.
Rot #20: LYIPIW E XMRKE.
Rot #21: KXHOHV D WLQJD.
Rot #22: JWGNGU C VKPIC.
Rot #23: IVFMFT B UJOHB.
Rot #24: HUELES A TINGA.
Rot #25: GTDKDR Z SHMFZ.
{'fraction_non_alphanumeric': 0.12332488228902572, 'fraction_numerical': 0.09235784136182543, 'mean_word_length': 4.185915492957746, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 38, 'https://': 0, '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': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '272739', 'license': 'MIT', 'n_tokens_mistral': 2725, 'n_tokens_neox': 2388, 'n_words': 649, 'path': 'ES_Methods/ES_Attacks.ipynb', 'repo_name': 'alfredolozano/AprendeCrypto', 'size': '5529'}