# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="view-in-github" colab_type="text"
# <a href="https://colab.research.google.com/github/halen48/CriptografiaRSA/blob/main/Criptografia_RSA.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>

# + id="ltABcbe4OE9c" cellView="form"
#@title Dependências
import random
import math
from IPython.core.display import display, HTML


# + [markdown] id="kH5IEH3vJHmS"
# #<a href="https://pt.wikipedia.org/wiki/M%C3%A1ximo_divisor_comum">Máximo divisor comum (MDC) </a>

# + id="Xz5udVqII-FN" cellView="form"
#@title <a href="https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides"> Algoritmo euclidiano </a>
def mdc(a : int, b : int) -> int:
  while b != 0:
    a,b = b, a%b
  return a


# + [markdown] id="_wEpxs4MNhqp"
# #Chave pública

# + [markdown] id="R5qD7TZeMgak"
# >Escolha dois números primos, p e q, e mantenha-os em segredo

# + id="Ao6NW-bDMm9L" cellView="form"
'''
#p_q_indice_e = (111,7,-1) #@param {type:"raw"}
p = p_q_indice_e[0]
q = p_q_indice_e[1]

indice_e = p_q_indice_e[2]  
'''
p = "373" #@param [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 105646155480762397, 439351292910452432574786963588089477522344331]
q = "37" #@param [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 105646155480762397, 864608136454559457049]
indice_e =  -1#@param {type:"raw"}
p,q = int(p),int(q)

# + [markdown] id="ipanm1OpM9qc"
#  >Calcula a chave pública **n**, sendo
#  ```
#  n = p⋅q
#  ```

# + id="_U63fl9rNMW9"
n = p * q

# + colab={"base_uri": "https://localhost:8080/", "height": 64} id="d1qFDY78W1-6" outputId="a40dafeb-34a3-497d-86c7-99ad54fc7362"
display(HTML('<h2>n = %d</h2>'%(n)))


# + [markdown] id="6JI6HhHiMwZz"
# #Calcula ϕ(n)

# + [markdown] id="yIdD_b0eKWpD"
# Sendo:
# ```
# n = p⋅q
# ϕ(n) = lcm(ϕ(p),ϕ(q))
# p e q são primos
# ```

# + [markdown] id="AecRm12NMPrr"
# Assim:
# ```
# ϕ(n) = mdc(p − 1, q − 1)
# ```

# + id="KLfKm8YeYBLI"
def mmc(a : int, b : int) -> int:
  return a*b // mdc(a,b)


# + id="dK5Gdi60KXIa"
def ϕ(p : int, q : int) -> int:
  return mmc(p - 1,q - 1)


# + id="wvWNOIZOXSeP"
phi_n = ϕ(p,q)

# + colab={"base_uri": "https://localhost:8080/", "height": 64} id="6csBuTu3XT7f" outputId="2338ab5b-41b4-467c-ca61-dcd1b0b5f0b5"
display(HTML('<h2>ϕ(%d) = %d</h2>'%((p*q),phi_n)))


# + [markdown] id="quEYObi8PLiN"
# #<a href="https://www.mathsisfun.com/numbers/coprime-calculator.html">Coprimo</a>

# + [markdown] id="_dHDTmnoPTRc"
# >Calcula um número inteiro ***e***, parte da chave pública, onde:
# ```
# 1 < e < ϕ(n) 
# mdc(e, ϕ(n)) = 1;
# ```
# Isto é, ***e*** é um número coprimo de ***ϕ(n)***

# + id="5-0Uk8aKPSx8"
def coprimo(phi_n : int) -> list:
  #A busca começa em 2, uma vez que todo numero é divisível por 1
  e = 2
  res = []
  while e < phi_n:
    if ( mdc(e, phi_n) == 1 ):
      res.append(e)
    e+= 1
  return res


# + id="5LWTWba_Q8PO"
es = coprimo(phi_n)
if(indice_e < 0):
  e = random.choice(es)
else:
  e = es[indice_e]

# + colab={"base_uri": "https://localhost:8080/", "height": 0} id="hsxXmmMIWvZ3" outputId="ca36f3de-9d1e-4e13-84cf-47ba29143bcc"
display(HTML('<h3>Coprimos de %d: %s</h3>'%(phi_n, es)))
display(HTML('<h2>e = %d</h2>'%(e)))


# + [markdown] id="gegfrwMDR45g"
# #Inverso multiplicativo modular

# + [markdown] id="SWa2bFwWR6KV"
# >Sendo:
# ```
# d⋅e ≡ 1 (mod ϕ(n)); 
# ```
# Logo:
# ```
# d ≡ e^−1 (mod ϕ(n))
# ```

# + id="wQJ5-I7tR4E9" cellView="form"
#@title <a href="https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides_estendido"> Algoritmo Euclidiano Estendido </a>
def mdce(a : int, b : int) -> tuple:
  if (a == 0):
    return 0,1,b
  
  x, y, mdc_ = mdce( b % a, a)

  return y - (b//a) * x, x, mdc_


# + id="XBkW_aFCWjEn"
r_mdce = mdce(e, phi_n)
d = r_mdce[0]
if(d < 0):
  d += phi_n

# + colab={"base_uri": "https://localhost:8080/", "height": 0} id="jKeIz_jPXGEa" outputId="bcc1d3f7-95b8-4ac3-8690-45bf2dea4173"
display(HTML('<h2>%d ≡ (%d^-1 * mod %d)</h2>'%(d, e, phi_n)))
display(HTML("<h2> %d * %d + %d * %d = %d </h2>"%(e, r_mdce[0], phi_n, r_mdce[1], r_mdce[2])))

# + [markdown] id="ktiRNdYzZZd4"
# #Chaves

# + colab={"base_uri": "https://localhost:8080/", "height": 195} id="6cpOIDtYZYiS" outputId="c2a39a0a-1d68-40ba-f059-334b6f62fab4"
display(HTML('<h2>n, e, d: (%d, %d, %d)</h2>'%(n, e, d)))
display(HTML('<h2>Chave Pública: (%d, %d)</h2>'%(n, e)))
display(HTML('<h2>Chave Privada: (%d, %d)</h2>'%(n, d)))
display(HTML('<h2>Numero de caracteres (Tamanho do bloco) do byte criptografado: %d</h2>'%(len(format(n,"x")))))


# + [markdown] id="sTUHmpmNppI5"
# #Codificando

# + id="eK6gO_eT2EQk"
def separa_string(string :str, janela : int, padding : bool) -> list:
  #Se a string não for multiplo de janela, faz um padding no final
  if(padding):
    tamanho_padding = len(string)%janela
    if(tamanho_padding != 0):
      string += '0'*(janela-tamanho_padding)
  return [string[i-janela:i] for i in range(janela, len(string)+janela, janela)]


# + id="1NiZJQMc6d-u"
def string_para_bytes(string :str) -> list:
  return separa_string(string, 2, True)


# + id="zS0PAA783nv1"
def bytes_para_string(mensagem_bytes : str) -> str:
  return ''.join([chr(int(b,16)) for b in mensagem_bytes])


# + cellView="form" id="0pXJlJ24pqkn"
mensagem = "Eu gosto de criptografia" #@param {type:"string"}

# + colab={"base_uri": "https://localhost:8080/"} id="ulHtTbYc2QNU" outputId="25328021-fc39-4a8c-927c-21f431ffbe5d"
mensagem_bytes = string_para_bytes(''.join([format(ord(l), 'x') for l in mensagem]))
print('Bytes da mensagem:',mensagem_bytes)

# + colab={"base_uri": "https://localhost:8080/"} id="Wbapdnjr3xt1" outputId="3166800a-8714-4b9a-bfc4-4a9a7dc74c4f"
print("Mensagem: %s"%bytes_para_string(mensagem_bytes))


# + id="2fmmyrgxpr4e"
def rsa_criptografar(valor : int) -> int:
  return pow(valor, e, n)


# + colab={"base_uri": "https://localhost:8080/"} id="yYWen19jp8u3" outputId="b7c825b4-de02-4ac6-c17f-8f275a7d6b9a"
res = [rsa_criptografar(ord(l)) for l in mensagem]

print('Caracteres criptografados:',res)

# + [markdown] id="7Hfluvjo9kG0"
# >Algumas informações interessantes

# + colab={"base_uri": "https://localhost:8080/", "height": 103} id="CC5Uekm29jGQ" outputId="47c16d04-bf26-4146-da81-3338dc39ea3b"
#Vamos assumir que o valor de cada bloco é de 0 até 0xFFF
string = ''+''.join([format(r, 'x') for r in res])

#cada caracter varia de 0 até 0xFF
mensagem_bytes = string_para_bytes(string)

print("Bytes criptografado:", mensagem_bytes)

display(HTML('<h2>Mensagem criptografada: %s</h2>'%(bytes_para_string(mensagem_bytes))))


# + id="OYYe0w8dp_2X"
def rsa_descriptografar(valor : int) -> int:
  return pow(valor, d, n)


# + colab={"base_uri": "https://localhost:8080/", "height": 83} id="oBsQV8b_-JOz" outputId="a3fbc317-c944-4c9d-8439-de519665cfa5"
#Descriptografa
mensagem_bytes = [rsa_descriptografar(l) for l in res]

#Converte de inteiro para hex, para melhor visualização
mensagem_bytes = [format(l,'x') for l in mensagem_bytes]

print("Bytes descriptografados:", mensagem_bytes)

display(HTML('<h2>Mensagem descriptografada: %s</h2>'%(bytes_para_string(mensagem_bytes))))

# + [markdown] id="XNzUZI8bAxVq"
# #Código em uma célula

# + id="s9YoodiWAzDk"
import random
import math

class RSAFactory():
  
  #Métodos privados
  def __mdc(a : int, b : int) -> int:
    while b != 0:
      a,b = b, a%b
    return a
  def __mmc(a : int, b : int) -> int:
    return a*b // mdc(a,b)
  def __ϕ(p : int, q : int) -> int:
    return mmc(p - 1,q - 1)

  def __coprimo(phi_n) -> list:
    #A busca começa em 2, uma vez que todo numero é divisível por 1
    e = 2
    res = []
    while e < phi_n:
      if ( RSAFactory.__mdc(e, phi_n) == 1 ):
        res.append(e)
      e+= 1
    return res

  def __mdce(a : int, b : int) -> tuple:
    if (a == 0):
      return 0,1,b
    
    x, y, mdc_ = RSAFactory.__mdce( b % a, a)

    return y - (b//a) * x, x, mdc_

  def FabricarRSA( p: int, q: int, indice_e: int) -> tuple:
    n = p * q

    phi_n = RSAFactory.__ϕ(p,q)

    es = RSAFactory.__coprimo(phi_n)

    #se indice_e for negativo, escolhe um aleatorio
    if(indice_e < 0):
      e = random.choice(es)
    else:
      e = es[indice_e]

    d,_,_ = RSAFactory.__mdce(e, phi_n)

    if (d < 0):
      d += phi_n
    
    #ignora sempre o 0x... que conta como 2 caracteres
    tamanho_bloco = len(hex(n))-2
    return (n,e,d,tamanho_bloco)
  
class RSA():
  def __init__(self, exp : int, mod : int, tamanho_bloco : int):
    self._exp = exp
    self._mod = mod
    self._tamanho_bloco = tamanho_bloco
    self._mascara = mascara = "%%0%dx"%self._tamanho_bloco

  def __separa_string(self, string :str, janela : int, padding : bool) -> list:
    #Se a string não for multiplo de janela, faz um padding no final
    if(padding):
      tamanho_padding = len(string)%janela
      if(tamanho_padding != 0):
        string += '0'*(janela-tamanho_padding)
    return [int(string[i-janela:i],16) for i in range(janela, len(string)+janela, janela)]

  def _hex_para_bytes(self, string :str) -> list:
    return self.__separa_string(string, 2, True)

  def _bytestream_para_int(self,byte_stream : str) -> list:
    return self.__separa_string(byte_stream, self._tamanho_bloco, False)

  def _operacao(self, valor : int) -> int:
    return pow(valor, self._exp, self._mod)

class RSAPrivado(RSA):
  def __init__(self, n : int, d: int, tamanho_bloco : int):
    RSA.__init__(self,d,n,tamanho_bloco)

  def criptografar(self, mensagem : str) -> bytes:
    
    #Converte char para int, criptografa e converte o resultado para hex
    #faz padding nos numeros que não possuem a quantidade de caracters igual a
    #quantidade da janela
    criptografado = [self._mascara%(self._operacao(ord(l))) for l in mensagem]
    
    criptografado = ''.join(criptografado) 
    return bytes(self._hex_para_bytes(criptografado))

class RSAPublico(RSA):
  def __init__(self, n : int, e: int, tamanho_bloco : int):
    RSA.__init__(self,e,n,tamanho_bloco)

  def descriptografar(self, mensagem : bytes) -> list:
    #Converte de byte para hex, desfazendo a primeira operação na criptografia
    mensagem = ["%02x"%(v) for v in mensagem]
    
    mensagem = ''.join(mensagem)
    criptografado = self._bytestream_para_int(mensagem)
    descriptografado = [self._operacao(l) for l in criptografado] 
    
    """
    Ao criptografar, foi determinado um protocolo onde, caso o numero de bytes
    seja impar (um byte é representado por uma dupla de caracteres), deve-se 
    adicionar um valor 'dummy' (no caso, 0) no final da string.    
    """
    if( int (descriptografado[-1]) == 0):
      descriptografado = descriptografado[:-1]
    return descriptografado


# + colab={"base_uri": "https://localhost:8080/"} id="9k2P6W8fc4-y" outputId="4472f04c-270e-4512-8dfa-f2ab1b87faa4"
n, e, d, tamanho_bloco = RSAFactory.FabricarRSA(p,q,indice_e)
print("n = %d, e = %d, d = %d"%(n, e, d))
print("Tamanho do bloco: %d"%tamanho_bloco)

modulo_criptografia_privado = RSAPrivado(n, e, tamanho_bloco)
modulo_criptografia_publico = RSAPublico(n, d, tamanho_bloco)

mesangem_criptografada = modulo_criptografia_privado.criptografar('Teste mensagem')
print('Stream de bytes criptografados:',mesangem_criptografada)

mensagem_descriptografada = modulo_criptografia_publico.descriptografar(mesangem_criptografada)
mensagem_descriptografada = ''.join([chr(l) for l in mensagem_descriptografada])
print('Stream de bytes descriptografados:',mensagem_descriptografada)

StarcoderdataJupyterScriptsDedupFiltered