<h1> Logaritmo Discreto




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 Diffie Helman, los mismos números. 

Digamos que Pancho consigue A = 656334248, sabemos que g = 13 y p = 3367900313



```python
A = 656334248
g = 13
p = 3367900313


    
```

<h3> Algoritmo Pohlig-Helman


```python
from sympy.ntheory import factorint
factorint(3367900312)
```




    {2: 3, 7: 1, 109: 1, 551753: 1}



Tomamos primero el factor $2^3$


```python
int1=int((3367900313-1)/2)

alpha1=pow(13,int1,p)
print("Alpha1 =",alpha1)
beta1=pow(A,int1,p)
print("Beta1 =",beta1)

```

    Alpha1 = 3367900312
    Beta1 = 3367900312


Por lo tanto $x_0=1$, y ahora incrementamos $2^2$


```python
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)
```

    3159318308
    Beta2 = 3367900312
    prueba = 3367900312


Por lo tanto $x_1=1$


```python
s2=modinv(g,p)
A2=A1*s2*s2%p
print(A2)
int3=int((3367900312)/8)
beta3=pow(A2,int3,p)
print("Beta3 =",beta3)

```

    1732536954
    Beta3 = 3367900312


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$


```python
int11=int((3367900313-1)/7)

alpha11=pow(13,int11,p)
print("Alpha1 =",alpha11)
beta11=pow(A,int11,p)
print("Beta1 =",beta11)
```

    Alpha1 = 2974477553
    Beta1 = 1


Por lo tanto  $x_1=0$ y la segunda ecuación es: $x_2 \equiv 0\ mod \ 7$

Tomamos tercero el factor $109$


```python
int111=int((3367900313-1)/109)

alpha111=pow(13,int111,p)
print("Alpha1 =",alpha111)
beta111=pow(A,int111,p)
print("Beta1 =",beta111)
```

    Alpha1 = 2920505388
    Beta1 = 2497218448



```python
prueba=pow(alpha111,3,p)
print (prueba)
```

    2497218448


Por lo tanto  $x_1=3$ y la segunda ecuación es: $x_3 \equiv 3\ mod \ 109$


Tomamos por último el factor $551753$


```python
int1111=int((3367900313-1)/551753)

alpha1111=pow(13,int1111,p)
print("Alpha1 =",alpha1111)
beta1111=pow(A,int1111,p)
print("Beta1 =",beta1111)
```

    Alpha1 = 600054388
    Beta1 = 2491247764



```python
i=0
result=0
while result != beta1111:
    result=pow(alpha1111,i,p)
    i=i+1
print(i-1)
print (result)
```

    46552
    2491247764



```python
print(pow(alpha1111,46552,p))
```

    2491247764


Por lo tanto  $x_1=46552$ y la segunda ecuación es: $x_4 \equiv 46552\ mod \ 551753$


```python
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)
```

    a = 12736871


# 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.


```python
mensaje = 'FSCJCQ Y RGLEY.'
```


```python
alfabeto = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
```

II. Probaremos cada rotación para ver si tiene sentido el mensaje.


```python
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))
```

    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.



```python

```

ee73808b6d15415fd46935b884c98a3b52de3506
ipynb
Jupyter Notebook
ES_Methods/ES_Attacks.ipynb
alfredolozano/AprendeCrypto
142ec3ae2b5922fcd0bcc20256246f69b85416b4
MIT
2017-09-26T16:08:29.000Z
2021-05-16T19:41:37.000Z
ES_Methods/ES_Attacks.ipynb
alfredolozano/LearnCrypto
142ec3ae2b5922fcd0bcc20256246f69b85416b4
MIT
ES_Methods/ES_Attacks.ipynb
alfredolozano/LearnCrypto
142ec3ae2b5922fcd0bcc20256246f69b85416b4
MIT
2016-11-24T17:57:44.000Z
2016-11-25T00:31:42.000Z
Qwen/Qwen-72B
1. YES
2. YES